1 /*
2 * Simplify - do instruction simplification before CSE
3 *
4 * Copyright (C) 2004 Linus Torvalds
5 */
6
7 ///
8 // Instruction simplification
9 // --------------------------
10 //
11 // Notation
12 // ^^^^^^^^
13 // The following conventions are used to describe the simplications:
14 // * Uppercase letters are reserved for constants:
15 // * `M` for a constant mask,
16 // * `S` for a constant shift,
17 // * `N` for a constant number of bits (usually other than a shift),
18 // * `C` or 'K' for others constants.
19 // * Lowercase letters `a`, `b`, `x`, `y`, ... are used for non-constants
20 // or when it doesn't matter if the pseudo is a constant or not.
21 // * Primes are used if needed to distinguish symbols (`M`, `M'`, ...).
22 // * Expressions or sub-expressions involving only constants are
23 // understood to be evaluated.
24 // * `$mask(N)` is used for `((1 << N) -1)`
25 // * `$trunc(x, N)` is used for `(x & $mask(N))`
26 // * Expressions like `(-1 << S)`, `(-1 >> S)` and others formulae are
27 // understood to be truncated to the size of the current instruction
28 // (needed, since in general this size is not the same as the one used
29 // by sparse for the evaluation of arithmetic operations).
30 // * `TRUNC(x, N)` is used for a truncation *to* a size of `N` bits
31 // * `ZEXT(x, N)` is used for a zero-extension *from* a size of `N` bits
32 // * `OP(x, C)` is used to represent some generic operation using a constant,
33 // including when the constant is implicit (e.g. `TRUNC(x, N)`).
34 // * `MASK(x, M)` is used to respresent a 'masking' instruction:
35 // - `AND(x, M)`
36 // - `LSR(x, S)`, with `M` = (-1 << S)
37 // - `SHL(x, S)`, with `M` = (-1 >> S)
38 // - `TRUNC(x, N)`, with `M` = $mask(N)
39 // - `ZEXT(x, N)`, with `M` = $mask(N)
40 // * `SHIFT(x, S)` is used for `LSR(x, S)` or `SHL(x, S)`.
41
42 #include <assert.h>
43
44 #include "parse.h"
45 #include "expression.h"
46 #include "linearize.h"
47 #include "simplify.h"
48 #include "flow.h"
49 #include "symbol.h"
50 #include "flowgraph.h"
51
52 ///
53 // Utilities
54 // ^^^^^^^^^
55
56 ///
57 // check if a pseudo is a power of 2
is_pow2(pseudo_t src)58 static inline bool is_pow2(pseudo_t src)
59 {
60 if (src->type != PSEUDO_VAL)
61 return false;
62 return is_power_of_2(src->value);
63 }
64
65 ///
66 // find the trivial parent for a phi-source
phi_parent(struct basic_block * source,pseudo_t pseudo)67 static struct basic_block *phi_parent(struct basic_block *source, pseudo_t pseudo)
68 {
69 /* Can't go upwards if the pseudo is defined in the bb it came from.. */
70 if (pseudo->type == PSEUDO_REG) {
71 struct instruction *def = pseudo->def;
72 if (def->bb == source)
73 return source;
74 }
75 if (bb_list_size(source->children) != 1 || bb_list_size(source->parents) != 1)
76 return source;
77 return first_basic_block(source->parents);
78 }
79
80 ///
81 // copy the phi-node's phisrcs into to given array
82 // @return: 0 if the the list contained the expected
83 // number of element, a positive number if there was
84 // more than expected and a negative one if less.
85 //
86 // :note: we can't reuse ptr_list_to_array() for the phi-sources
87 // because any VOIDs in the phi-list must be ignored here
88 // as in this context they mean 'entry has been removed'.
get_phisources(struct instruction * sources[],int nbr,struct instruction * insn)89 static int get_phisources(struct instruction *sources[], int nbr, struct instruction *insn)
90 {
91 pseudo_t phi;
92 int i = 0;
93
94 assert(insn->opcode == OP_PHI);
95 FOR_EACH_PTR(insn->phi_list, phi) {
96 struct instruction *def;
97 if (phi == VOID)
98 continue;
99 if (i >= nbr)
100 return 1;
101 def = phi->def;
102 assert(def->opcode == OP_PHISOURCE);
103 sources[i++] = def;
104 } END_FOR_EACH_PTR(phi);
105 return i - nbr;
106 }
107
if_convert_phi(struct instruction * insn)108 static int if_convert_phi(struct instruction *insn)
109 {
110 struct instruction *array[2];
111 struct basic_block *parents[2];
112 struct basic_block *bb, *bb1, *bb2, *source;
113 struct instruction *br;
114 pseudo_t p1, p2;
115
116 bb = insn->bb;
117 if (get_phisources(array, 2, insn))
118 return 0;
119 if (ptr_list_to_array(bb->parents, parents, 2) != 2)
120 return 0;
121 p1 = array[0]->phi_src;
122 bb1 = array[0]->bb;
123 p2 = array[1]->phi_src;
124 bb2 = array[1]->bb;
125
126 /* Only try the simple "direct parents" case */
127 if ((bb1 != parents[0] || bb2 != parents[1]) &&
128 (bb1 != parents[1] || bb2 != parents[0]))
129 return 0;
130
131 /*
132 * See if we can find a common source for this..
133 */
134 source = phi_parent(bb1, p1);
135 if (source != phi_parent(bb2, p2))
136 return 0;
137
138 /*
139 * Cool. We now know that 'source' is the exclusive
140 * parent of both phi-nodes, so the exit at the
141 * end of it fully determines which one it is, and
142 * we can turn it into a select.
143 *
144 * HOWEVER, right now we only handle regular
145 * conditional branches. No multijumps or computed
146 * stuff. Verify that here.
147 */
148 br = last_instruction(source->insns);
149 if (!br || br->opcode != OP_CBR)
150 return 0;
151
152 assert(br->cond);
153 assert(br->bb_false);
154
155 /*
156 * We're in business. Match up true/false with p1/p2.
157 */
158 if (br->bb_true == bb2 || br->bb_false == bb1) {
159 pseudo_t p = p1;
160 p1 = p2;
161 p2 = p;
162 }
163
164 /*
165 * OK, we can now replace that last
166 *
167 * br cond, a, b
168 *
169 * with the sequence
170 *
171 * setcc cond
172 * select pseudo, p1, p2
173 * br cond, a, b
174 *
175 * and remove the phi-node. If it then
176 * turns out that 'a' or 'b' is entirely
177 * empty (common case), and now no longer
178 * a phi-source, we'll be able to simplify
179 * the conditional branch too.
180 */
181 insert_select(source, br, insn, p1, p2);
182 kill_instruction(insn);
183 return REPEAT_CSE;
184 }
185
186 ///
187 // detect trivial phi-nodes
188 // @insn: the phi-node
189 // @pseudo: the candidate resulting pseudo (NULL when starting)
190 // @return: the unique result if the phi-node is trivial, NULL otherwise
191 //
192 // A phi-node is trivial if it has a single possible result:
193 // * all operands are the same
194 // * the operands are themselves defined by a chain or cycle of phi-nodes
195 // and the set of all operands involved contains a single value
196 // not defined by these phi-nodes
197 //
198 // Since the result is unique, these phi-nodes can be removed.
trivial_phi(pseudo_t pseudo,struct instruction * insn,struct pseudo_list ** list)199 static pseudo_t trivial_phi(pseudo_t pseudo, struct instruction *insn, struct pseudo_list **list)
200 {
201 pseudo_t target = insn->target;
202 pseudo_t phi;
203
204 add_pseudo(list, target);
205
206 FOR_EACH_PTR(insn->phi_list, phi) {
207 struct instruction *def;
208 pseudo_t src;
209
210 if (phi == VOID)
211 continue;
212 def = phi->def;
213 if (!def->bb)
214 continue;
215 src = def->phi_src; // bypass OP_PHISRC & get the real source
216 if (src == VOID)
217 continue;
218 if (src == target)
219 continue;
220 if (!pseudo) {
221 pseudo = src;
222 continue;
223 }
224 if (src == pseudo)
225 continue;
226 if (DEF_OPCODE(def, src) == OP_PHI) {
227 if (pseudo_in_list(*list, src))
228 continue;
229 if ((pseudo = trivial_phi(pseudo, def, list)))
230 continue;
231 }
232 return NULL;
233 } END_FOR_EACH_PTR(phi);
234
235 return pseudo ? pseudo : VOID;
236 }
237
clean_up_phi(struct instruction * insn)238 static int clean_up_phi(struct instruction *insn)
239 {
240 struct pseudo_list *list = NULL;
241 pseudo_t pseudo;
242
243 if ((pseudo = trivial_phi(NULL, insn, &list))) {
244 convert_instruction_target(insn, pseudo);
245 kill_instruction(insn);
246 return REPEAT_CSE;
247 }
248
249 return if_convert_phi(insn);
250 }
251
delete_pseudo_user_list_entry(struct pseudo_user_list ** list,pseudo_t * entry,int count)252 static int delete_pseudo_user_list_entry(struct pseudo_user_list **list, pseudo_t *entry, int count)
253 {
254 struct pseudo_user *pu;
255
256 FOR_EACH_PTR(*list, pu) {
257 if (pu->userp == entry) {
258 MARK_CURRENT_DELETED(pu);
259 if (!--count)
260 goto out;
261 }
262 } END_FOR_EACH_PTR(pu);
263 assert(count <= 0);
264 out:
265 if (pseudo_user_list_empty(*list))
266 *list = NULL;
267 return count;
268 }
269
rem_usage(pseudo_t p,pseudo_t * usep,int kill)270 static inline void rem_usage(pseudo_t p, pseudo_t *usep, int kill)
271 {
272 if (has_use_list(p)) {
273 delete_pseudo_user_list_entry(&p->users, usep, 1);
274 if (kill && !p->users && has_definition(p))
275 kill_instruction(p->def);
276 }
277 }
278
remove_usage(pseudo_t p,pseudo_t * usep)279 static inline void remove_usage(pseudo_t p, pseudo_t *usep)
280 {
281 rem_usage(p, usep, 1);
282 }
283
kill_use(pseudo_t * usep)284 void kill_use(pseudo_t *usep)
285 {
286 if (usep) {
287 pseudo_t p = *usep;
288 *usep = VOID;
289 rem_usage(p, usep, 1);
290 }
291 }
292
293 // Like kill_use() but do not (recursively) kill dead instructions
remove_use(pseudo_t * usep)294 void remove_use(pseudo_t *usep)
295 {
296 pseudo_t p = *usep;
297 *usep = VOID;
298 rem_usage(p, usep, 0);
299 }
300
kill_use_list(struct pseudo_list * list)301 static void kill_use_list(struct pseudo_list *list)
302 {
303 pseudo_t p;
304 FOR_EACH_PTR(list, p) {
305 if (p == VOID)
306 continue;
307 kill_use(THIS_ADDRESS(p));
308 } END_FOR_EACH_PTR(p);
309 }
310
kill_asm(struct instruction * insn)311 static void kill_asm(struct instruction *insn)
312 {
313 struct asm_constraint *con;
314
315 FOR_EACH_PTR(insn->asm_rules->inputs, con) {
316 kill_use(&con->pseudo);
317 } END_FOR_EACH_PTR(con);
318 }
319
320 ///
321 // kill an instruction
322 // @insn: the instruction to be killed
323 // @force: if unset, the normal case, the instruction is not killed
324 // if not free of possible side-effect; if set the instruction
325 // is unconditionally killed.
326 //
327 // The killed instruction is removed from its BB and the usage
328 // of all its operands are removed. The instruction is also
329 // marked as killed by setting its ->bb to NULL.
kill_insn(struct instruction * insn,int force)330 int kill_insn(struct instruction *insn, int force)
331 {
332 if (!insn || !insn->bb)
333 return 0;
334
335 switch (insn->opcode) {
336 case OP_SEL:
337 case OP_RANGE:
338 kill_use(&insn->src3);
339 /* fall through */
340
341 case OP_BINARY ... OP_BINCMP_END:
342 kill_use(&insn->src2);
343 /* fall through */
344
345 case OP_UNOP ... OP_UNOP_END:
346 case OP_SLICE:
347 case OP_PHISOURCE:
348 case OP_SYMADDR:
349 case OP_CBR:
350 case OP_SWITCH:
351 case OP_COMPUTEDGOTO:
352 kill_use(&insn->src1);
353 break;
354
355 case OP_PHI:
356 kill_use_list(insn->phi_list);
357 break;
358
359 case OP_CALL:
360 if (!force) {
361 /* a "pure" function can be killed too */
362 struct symbol *fntype = first_symbol(insn->fntypes);
363
364 if (!(fntype->ctype.modifiers & MOD_PURE))
365 return 0;
366 }
367 kill_use_list(insn->arguments);
368 if (insn->func->type == PSEUDO_REG)
369 kill_use(&insn->func);
370 break;
371
372 case OP_LOAD:
373 if (!force && insn->is_volatile)
374 return 0;
375 kill_use(&insn->src);
376 break;
377
378 case OP_STORE:
379 if (!force)
380 return 0;
381 kill_use(&insn->src);
382 kill_use(&insn->target);
383 break;
384
385 case OP_ASM:
386 if (!force)
387 return 0;
388 kill_asm(insn);
389 break;
390
391 case OP_ENTRY:
392 /* ignore */
393 return 0;
394
395 case OP_BR:
396 case OP_LABEL:
397 case OP_SETVAL:
398 case OP_SETFVAL:
399 default:
400 break;
401 }
402
403 insn->bb = NULL;
404 return repeat_phase |= REPEAT_CSE;
405 }
406
has_target(struct instruction * insn)407 static inline bool has_target(struct instruction *insn)
408 {
409 return opcode_table[insn->opcode].flags & OPF_TARGET;
410 }
411
remove_dead_insns(struct entrypoint * ep)412 void remove_dead_insns(struct entrypoint *ep)
413 {
414 struct basic_block *bb;
415
416 FOR_EACH_PTR_REVERSE(ep->bbs, bb) {
417 struct instruction *insn;
418 FOR_EACH_PTR_REVERSE(bb->insns, insn) {
419 if (!insn->bb)
420 continue;
421 if (!has_target(insn))
422 continue;
423 if (!has_users(insn->target))
424 kill_instruction(insn);
425 } END_FOR_EACH_PTR_REVERSE(insn);
426 } END_FOR_EACH_PTR_REVERSE(bb);
427 }
428
constant(pseudo_t pseudo)429 static inline int constant(pseudo_t pseudo)
430 {
431 return pseudo->type == PSEUDO_VAL;
432 }
433
434 ///
435 // is this same signed value when interpreted with both size?
is_signed_constant(long long val,unsigned osize,unsigned nsize)436 static inline bool is_signed_constant(long long val, unsigned osize, unsigned nsize)
437 {
438 return bits_extend(val, osize, 1) == bits_extend(val, nsize, 1);
439 }
440
441 ///
442 // is @src generated by an instruction with the given opcode and size?
is_same_op(pseudo_t src,int op,unsigned osize)443 static inline pseudo_t is_same_op(pseudo_t src, int op, unsigned osize)
444 {
445 struct instruction *def;
446
447 if (src->type != PSEUDO_REG)
448 return NULL;
449 def = src->def;
450 if (def->opcode != op)
451 return NULL;
452 if (def->orig_type->bit_size != osize)
453 return NULL;
454 return def->src;
455 }
456
is_negate_of(pseudo_t p,pseudo_t ref)457 static bool is_negate_of(pseudo_t p, pseudo_t ref)
458 {
459 struct instruction *def;
460
461 return (DEF_OPCODE(def, p) == OP_NEG) && (def->src == ref);
462 }
463
464 ///
465 // replace the operand of an instruction
466 // @insn: the instruction
467 // @pp: the address of the instruction's operand
468 // @new: the new value for the operand
469 // @return: REPEAT_CSE.
replace_pseudo(struct instruction * insn,pseudo_t * pp,pseudo_t new)470 static inline int replace_pseudo(struct instruction *insn, pseudo_t *pp, pseudo_t new)
471 {
472 pseudo_t old = *pp;
473 use_pseudo(insn, new, pp);
474 remove_usage(old, pp);
475 return REPEAT_CSE;
476 }
477
replace_with_pseudo(struct instruction * insn,pseudo_t pseudo)478 int replace_with_pseudo(struct instruction *insn, pseudo_t pseudo)
479 {
480 convert_instruction_target(insn, pseudo);
481 return kill_instruction(insn);
482 }
483
replace_with_value(struct instruction * insn,long long val)484 static inline int replace_with_value(struct instruction *insn, long long val)
485 {
486 return replace_with_pseudo(insn, value_pseudo(val));
487 }
488
489 ///
490 // replace a binop with an unop
491 // @insn: the instruction to be replaced
492 // @op: the instruction's new opcode
493 // @src: the instruction's new operand
494 // @return: REPEAT_CSE
replace_with_unop(struct instruction * insn,int op,pseudo_t src)495 static inline int replace_with_unop(struct instruction *insn, int op, pseudo_t src)
496 {
497 insn->opcode = op;
498 replace_pseudo(insn, &insn->src1, src);
499 remove_usage(insn->src2, &insn->src2);
500 return REPEAT_CSE;
501 }
502
503 ///
504 // replace rightside's value
505 // @insn: the instruction to be replaced
506 // @op: the instruction's new opcode
507 // @src: the instruction's new operand
508 // @return: REPEAT_CSE
replace_binop_value(struct instruction * insn,int op,long long val)509 static inline int replace_binop_value(struct instruction *insn, int op, long long val)
510 {
511 insn->opcode = op;
512 insn->src2 = value_pseudo(val);
513 return REPEAT_CSE;
514 }
515
516 ///
517 // replace binop's opcode and values
518 // @insn: the instruction to be replaced
519 // @op: the instruction's new opcode
520 // @return: REPEAT_CSE
replace_binop(struct instruction * insn,int op,pseudo_t * pa,pseudo_t a,pseudo_t * pb,pseudo_t b)521 static inline int replace_binop(struct instruction *insn, int op, pseudo_t *pa, pseudo_t a, pseudo_t *pb, pseudo_t b)
522 {
523 pseudo_t olda = *pa;
524 pseudo_t oldb = *pb;
525 insn->opcode = op;
526 use_pseudo(insn, a, pa);
527 use_pseudo(insn, b, pb);
528 remove_usage(olda, pa);
529 remove_usage(oldb, pb);
530 return REPEAT_CSE;
531 }
532
533 ///
534 // replace the opcode of an instruction
535 // @return: REPEAT_CSE
replace_opcode(struct instruction * insn,int op)536 static inline int replace_opcode(struct instruction *insn, int op)
537 {
538 insn->opcode = op;
539 return REPEAT_CSE;
540 }
541
542 ///
543 // create an instruction pair OUT(IN(a, b), c)
replace_insn_pair(struct instruction * out,int op_out,struct instruction * in,int op_in,pseudo_t a,pseudo_t b,pseudo_t c)544 static int replace_insn_pair(struct instruction *out, int op_out, struct instruction *in, int op_in, pseudo_t a, pseudo_t b, pseudo_t c)
545 {
546 pseudo_t old_a = in->src1;
547 pseudo_t old_b = in->src2;
548 pseudo_t old_1 = out->src1;
549 pseudo_t old_2 = out->src2;
550
551 use_pseudo(in, a, &in->src1);
552 use_pseudo(in, b, &in->src2);
553 use_pseudo(out, in->target, &out->src1);
554 use_pseudo(out, c, &out->src2);
555
556 remove_usage(old_a, &in->src1);
557 remove_usage(old_b, &in->src2);
558 remove_usage(old_1, &out->src1);
559 remove_usage(old_2, &out->src2);
560
561 out->opcode = op_out;
562 in->opcode = op_in;
563 return REPEAT_CSE;
564 }
565
566 ///
567 // create an instruction pair OUT(IN(a, b), c) with swapped opcodes
swap_insn(struct instruction * out,struct instruction * in,pseudo_t a,pseudo_t b,pseudo_t c)568 static inline int swap_insn(struct instruction *out, struct instruction *in, pseudo_t a, pseudo_t b, pseudo_t c)
569 {
570 return replace_insn_pair(out, in->opcode, in, out->opcode, a, b, c);
571 }
572
573 ///
574 // create an instruction pair OUT(SELECT(a, b, c), d)
swap_select(struct instruction * out,struct instruction * in,pseudo_t a,pseudo_t b,pseudo_t c,pseudo_t d)575 static int swap_select(struct instruction *out, struct instruction *in, pseudo_t a, pseudo_t b, pseudo_t c, pseudo_t d)
576 {
577 use_pseudo(in, c, &in->src3);
578 swap_insn(out, in, a, b, d);
579 kill_use(&out->src3);
580 return REPEAT_CSE;
581 }
582
def_opcode(pseudo_t p)583 static inline int def_opcode(pseudo_t p)
584 {
585 if (p->type != PSEUDO_REG)
586 return OP_BADOP;
587 return p->def->opcode;
588 }
589
value_size(long long value)590 static unsigned int value_size(long long value)
591 {
592 value >>= 8;
593 if (!value)
594 return 8;
595 value >>= 8;
596 if (!value)
597 return 16;
598 value >>= 16;
599 if (!value)
600 return 32;
601 return 64;
602 }
603
604 ///
605 // try to determine the maximum size of bits in a pseudo
606 //
607 // Right now this only follow casts and constant values, but we
608 // could look at things like AND instructions, etc.
operand_size(struct instruction * insn,pseudo_t pseudo)609 static unsigned int operand_size(struct instruction *insn, pseudo_t pseudo)
610 {
611 unsigned int size = insn->size;
612
613 if (pseudo->type == PSEUDO_REG) {
614 struct instruction *src = pseudo->def;
615 if (src && src->opcode == OP_ZEXT && src->orig_type) {
616 unsigned int orig_size = src->orig_type->bit_size;
617 if (orig_size < size)
618 size = orig_size;
619 }
620 }
621 if (pseudo->type == PSEUDO_VAL) {
622 unsigned int orig_size = value_size(pseudo->value);
623 if (orig_size < size)
624 size = orig_size;
625 }
626 return size;
627 }
628
eval_op(int op,unsigned size,pseudo_t src1,pseudo_t src2)629 static pseudo_t eval_op(int op, unsigned size, pseudo_t src1, pseudo_t src2)
630 {
631 /* FIXME! Verify signs and sizes!! */
632 long long left = src1->value;
633 long long right = src2->value;
634 unsigned long long ul, ur;
635 long long res, mask, bits;
636
637 mask = 1ULL << (size-1);
638 bits = mask | (mask-1);
639
640 if (left & mask)
641 left |= ~bits;
642 if (right & mask)
643 right |= ~bits;
644 ul = left & bits;
645 ur = right & bits;
646
647 switch (op) {
648 case OP_NEG:
649 res = -left;
650 break;
651 case OP_NOT:
652 res = ~ul;
653 break;
654
655 case OP_ADD:
656 res = left + right;
657 break;
658 case OP_SUB:
659 res = left - right;
660 break;
661 case OP_MUL:
662 res = ul * ur;
663 break;
664 case OP_DIVU:
665 if (!ur)
666 goto undef;
667 res = ul / ur;
668 break;
669 case OP_DIVS:
670 if (!right)
671 goto undef;
672 if (left == mask && right == -1)
673 goto undef;
674 res = left / right;
675 break;
676 case OP_MODU:
677 if (!ur)
678 goto undef;
679 res = ul % ur;
680 break;
681 case OP_MODS:
682 if (!right)
683 goto undef;
684 if (left == mask && right == -1)
685 goto undef;
686 res = left % right;
687 break;
688 case OP_SHL:
689 if (ur >= size)
690 goto undef;
691 res = left << right;
692 break;
693 case OP_LSR:
694 if (ur >= size)
695 goto undef;
696 res = ul >> ur;
697 break;
698 case OP_ASR:
699 if (ur >= size)
700 goto undef;
701 res = left >> right;
702 break;
703 /* Logical */
704 case OP_AND:
705 res = left & right;
706 break;
707 case OP_OR:
708 res = left | right;
709 break;
710 case OP_XOR:
711 res = left ^ right;
712 break;
713
714 /* Binary comparison */
715 case OP_SET_EQ:
716 res = left == right;
717 break;
718 case OP_SET_NE:
719 res = left != right;
720 break;
721 case OP_SET_LE:
722 res = left <= right;
723 break;
724 case OP_SET_GE:
725 res = left >= right;
726 break;
727 case OP_SET_LT:
728 res = left < right;
729 break;
730 case OP_SET_GT:
731 res = left > right;
732 break;
733 case OP_SET_B:
734 res = ul < ur;
735 break;
736 case OP_SET_A:
737 res = ul > ur;
738 break;
739 case OP_SET_BE:
740 res = ul <= ur;
741 break;
742 case OP_SET_AE:
743 res = ul >= ur;
744 break;
745 default:
746 return NULL;
747 }
748
749 // Warning: this should be done with the output size which may
750 // be different than the input size used here. But it differs
751 // only for compares which are not concerned since only returning
752 // 0 or 1 and for casts which are not handled here.
753 res &= bits;
754
755 return value_pseudo(res);
756
757 undef:
758 return NULL;
759 }
760
eval_unop(int op,unsigned size,pseudo_t src)761 static inline pseudo_t eval_unop(int op, unsigned size, pseudo_t src)
762 {
763 return eval_op(op, size, src, VOID);
764 }
765
766 ///
767 // Simplifications
768 // ^^^^^^^^^^^^^^^
769
770 ///
771 // try to simplify MASK(OR(AND(x, M'), b), M)
772 // @insn: the masking instruction
773 // @mask: the associated mask (M)
774 // @ora: one of the OR's operands, guaranteed to be PSEUDO_REG
775 // @orb: the other OR's operand
776 // @return: 0 if no changes have been made, one or more REPEAT_* flags otherwise.
simplify_mask_or_and(struct instruction * insn,unsigned long long mask,pseudo_t ora,pseudo_t orb)777 static int simplify_mask_or_and(struct instruction *insn, unsigned long long mask,
778 pseudo_t ora, pseudo_t orb)
779 {
780 unsigned long long omask, nmask;
781 struct instruction *and = ora->def;
782 pseudo_t src2 = and->src2;
783
784 if (and->opcode != OP_AND)
785 return 0;
786 if (!constant(src2))
787 return 0;
788 omask = src2->value;
789 nmask = omask & mask;
790 if (nmask == 0) {
791 // if (M' & M) == 0: ((a & M') | b) -> b
792 return replace_pseudo(insn, &insn->src1, orb);
793 }
794 if (!one_use(insn->src1))
795 return 0; // can't modify anything inside the OR
796 if (nmask == mask) {
797 struct instruction *or = insn->src1->def;
798 pseudo_t *arg = (ora == or->src1) ? &or->src1 : &or->src2;
799 // if (M' & M) == M: ((a & M') | b) -> (a | b)
800 return replace_pseudo(or, arg, and->src1);
801 }
802 if (nmask != omask && one_use(ora)) {
803 // if (M' & M) != M': AND(a, M') -> AND(a, (M' & M))
804 and->src2 = value_pseudo(nmask);
805 return REPEAT_CSE;
806 }
807 return 0;
808 }
809
810 ///
811 // try to simplify MASK(OR(a, b), M)
812 // @insn: the masking instruction
813 // @mask: the associated mask (M)
814 // @or: the OR instruction
815 // @return: 0 if no changes have been made, one or more REPEAT_* flags otherwise.
simplify_mask_or(struct instruction * insn,unsigned long long mask,struct instruction * or)816 static int simplify_mask_or(struct instruction *insn, unsigned long long mask, struct instruction *or)
817 {
818 pseudo_t src1 = or->src1;
819 pseudo_t src2 = or->src2;
820 int rc;
821
822 if (src1->type == PSEUDO_REG) {
823 if ((rc = simplify_mask_or_and(insn, mask, src1, src2)))
824 return rc;
825 }
826 if (src2->type == PSEUDO_REG) {
827 if ((rc = simplify_mask_or_and(insn, mask, src2, src1)))
828 return rc;
829 } else if (src2->type == PSEUDO_VAL) {
830 unsigned long long oval = src2->value;
831 unsigned long long nval = oval & mask;
832 // Try to simplify:
833 // MASK(OR(x, C), M)
834 if (nval == 0) {
835 // if (C & M) == 0: OR(x, C) -> x
836 return replace_pseudo(insn, &insn->src1, src1);
837 }
838 if (nval == mask) {
839 // if (C & M) == M: OR(x, C) -> M
840 return replace_pseudo(insn, &insn->src1, value_pseudo(mask));
841 }
842 if (nval != oval && one_use(or->target)) {
843 // if (C & M) != C: OR(x, C) -> OR(x, (C & M))
844 return replace_pseudo(or, &or->src2, value_pseudo(nval));
845 }
846 }
847 return 0;
848 }
849
850 ///
851 // try to simplify MASK(SHIFT(OR(a, b), S), M)
852 // @sh: the shift instruction
853 // @or: the OR instruction
854 // @mask: the mask associated to MASK (M):
855 // @return: 0 if no changes have been made, one or more REPEAT_* flags otherwise.
simplify_mask_shift_or(struct instruction * sh,struct instruction * or,unsigned long long mask)856 static int simplify_mask_shift_or(struct instruction *sh, struct instruction *or, unsigned long long mask)
857 {
858 unsigned long long smask = bits_mask(sh->size);
859 int shift = sh->src2->value;
860
861 if (sh->opcode == OP_LSR)
862 mask <<= shift;
863 else
864 mask >>= shift;
865 return simplify_mask_or(sh, smask & mask, or);
866 }
867
simplify_mask_shift(struct instruction * sh,unsigned long long mask)868 static int simplify_mask_shift(struct instruction *sh, unsigned long long mask)
869 {
870 struct instruction *inner;
871
872 if (!constant(sh->src2) || sh->tainted)
873 return 0;
874 switch (DEF_OPCODE(inner, sh->src1)) {
875 case OP_OR:
876 if (one_use(sh->target))
877 return simplify_mask_shift_or(sh, inner, mask);
878 break;
879 }
880 return 0;
881 }
882
eval_insn(struct instruction * insn)883 static pseudo_t eval_insn(struct instruction *insn)
884 {
885 unsigned size = insn->size;
886
887 if (opcode_table[insn->opcode].flags & OPF_COMPARE)
888 size = insn->itype->bit_size;
889 return eval_op(insn->opcode, size, insn->src1, insn->src2);
890 }
891
check_shift_count(struct instruction * insn,unsigned long long uval)892 static long long check_shift_count(struct instruction *insn, unsigned long long uval)
893 {
894 unsigned int size = insn->size;
895 long long sval = uval;
896
897 if (insn->tainted)
898 return -1;
899
900 if (uval < size)
901 return uval;
902
903 insn->tainted = 1;
904 sval = sign_extend_safe(sval, size);
905 sval = sign_extend_safe(sval, bits_in_int);
906 if (sval < 0)
907 insn->src2 = value_pseudo(sval);
908 return -1;
909 }
910
simplify_shift(struct instruction * insn,pseudo_t pseudo,long long value)911 static int simplify_shift(struct instruction *insn, pseudo_t pseudo, long long value)
912 {
913 struct instruction *def;
914 unsigned long long mask, omask, nmask;
915 unsigned long long nval;
916 unsigned int size;
917 pseudo_t src2;
918
919 if (!value)
920 return replace_with_pseudo(insn, pseudo);
921 value = check_shift_count(insn, value);
922 if (value < 0)
923 return 0;
924
925 size = insn->size;
926 switch (insn->opcode) {
927 case OP_ASR:
928 if (value >= size)
929 return 0;
930 if (pseudo->type != PSEUDO_REG)
931 break;
932 def = pseudo->def;
933 switch (def->opcode) {
934 case OP_LSR:
935 case OP_ASR:
936 if (def == insn) // cyclic DAG!
937 break;
938 src2 = def->src2;
939 if (src2->type != PSEUDO_VAL)
940 break;
941 nval = src2->value;
942 if (nval > insn->size || nval == 0)
943 break;
944 value += nval;
945 if (def->opcode == OP_LSR)
946 insn->opcode = OP_LSR;
947 else if (value >= size)
948 value = size - 1;
949 goto new_value;
950
951 case OP_ZEXT:
952 // transform:
953 // zext.N %t <- (O) %a
954 // asr.N %r <- %t, C
955 // into
956 // zext.N %t <- (O) %a
957 // lsr.N %r <- %t, C
958 insn->opcode = OP_LSR;
959 return REPEAT_CSE;
960 }
961 break;
962 case OP_LSR:
963 size = operand_size(insn, pseudo);
964 if (value >= size)
965 goto zero;
966 switch(DEF_OPCODE(def, pseudo)) {
967 case OP_AND:
968 // replace (A & M) >> S
969 // by (A >> S) & (M >> S)
970 if (!constant(def->src2))
971 break;
972 mask = bits_mask(insn->size - value) << value;
973 omask = def->src2->value;
974 nmask = omask & mask;
975 if (nmask == 0)
976 return replace_with_value(insn, 0);
977 if (nmask == mask)
978 return replace_pseudo(insn, &insn->src1, def->src1);
979 if (!one_use(pseudo))
980 break;
981 def->opcode = OP_LSR;
982 def->src2 = insn->src2;
983 insn->opcode = OP_AND;
984 insn->src2 = value_pseudo(omask >> value);
985 return REPEAT_CSE;
986 case OP_LSR:
987 goto case_shift_shift;
988 case OP_OR:
989 mask = bits_mask(size);
990 return simplify_mask_shift_or(insn, def, mask);
991 case OP_SHL:
992 // replace ((x << S) >> S)
993 // by (x & (-1 >> S))
994 if (def->src2 != insn->src2)
995 break;
996 mask = bits_mask(insn->size - value);
997 goto replace_mask;
998 }
999 break;
1000 case OP_SHL:
1001 if (value >= size)
1002 goto zero;
1003 switch(DEF_OPCODE(def, pseudo)) {
1004 case OP_AND:
1005 // simplify (A & M) << S
1006 if (!constant(def->src2))
1007 break;
1008 mask = bits_mask(insn->size) >> value;
1009 omask = def->src2->value;
1010 nmask = omask & mask;
1011 if (nmask == 0)
1012 return replace_with_value(insn, 0);
1013 if (nmask == mask)
1014 return replace_pseudo(insn, &insn->src1, def->src1);
1015 // do not simplify into ((A << S) & (M << S))
1016 break;
1017 case OP_LSR:
1018 // replace ((x >> S) << S)
1019 // by (x & (-1 << S))
1020 if (def->src2 != insn->src2)
1021 break;
1022 mask = bits_mask(insn->size - value) << value;
1023 goto replace_mask;
1024 case OP_OR:
1025 mask = bits_mask(size);
1026 return simplify_mask_shift_or(insn, def, mask);
1027 case OP_SHL:
1028 case_shift_shift: // also for LSR - LSR
1029 if (def == insn) // cyclic DAG!
1030 break;
1031 src2 = def->src2;
1032 if (src2->type != PSEUDO_VAL)
1033 break;
1034 nval = src2->value;
1035 if (nval > insn->size)
1036 break;
1037 value += nval;
1038 goto new_value;
1039 }
1040 break;
1041 }
1042 return 0;
1043
1044 new_value:
1045 if (value < size) {
1046 insn->src2 = value_pseudo(value);
1047 return replace_pseudo(insn, &insn->src1, pseudo->def->src1);
1048 }
1049 zero:
1050 return replace_with_value(insn, 0);
1051 replace_mask:
1052 insn->opcode = OP_AND;
1053 insn->src2 = value_pseudo(mask);
1054 return replace_pseudo(insn, &insn->src1, def->src1);
1055 }
1056
simplify_mul_div(struct instruction * insn,long long value)1057 static int simplify_mul_div(struct instruction *insn, long long value)
1058 {
1059 unsigned long long sbit = 1ULL << (insn->size - 1);
1060 unsigned long long bits = sbit | (sbit - 1);
1061
1062 if (value == 1)
1063 return replace_with_pseudo(insn, insn->src1);
1064
1065 switch (insn->opcode) {
1066 case OP_MUL:
1067 if (value == 0)
1068 return replace_with_pseudo(insn, insn->src2);
1069 /* Fall through */
1070 case OP_DIVS:
1071 if (!(value & sbit)) // positive
1072 break;
1073
1074 value |= ~bits;
1075 if (value == -1) {
1076 insn->opcode = OP_NEG;
1077 return REPEAT_CSE;
1078 }
1079 }
1080
1081 return 0;
1082 }
1083
simplify_seteq_setne(struct instruction * insn,long long value)1084 static int simplify_seteq_setne(struct instruction *insn, long long value)
1085 {
1086 pseudo_t old = insn->src1;
1087 struct instruction *def;
1088 unsigned osize;
1089 int inverse;
1090 int opcode;
1091
1092 if (value != 0 && value != 1)
1093 return 0;
1094
1095 if (old->type != PSEUDO_REG)
1096 return 0;
1097 def = old->def;
1098 if (!def)
1099 return 0;
1100
1101 inverse = (insn->opcode == OP_SET_NE) == value;
1102 if (!inverse && def->size == 1 && insn->size == 1) {
1103 // Replace:
1104 // setne %r <- %s, $0
1105 // or:
1106 // seteq %r <- %s, $1
1107 // by %s when boolean
1108 return replace_with_pseudo(insn, old);
1109 }
1110 opcode = def->opcode;
1111 switch (opcode) {
1112 case OP_AND:
1113 if (inverse)
1114 break;
1115 if (def->size != insn->size)
1116 break;
1117 if (def->src2->type != PSEUDO_VAL)
1118 break;
1119 if (def->src2->value != 1)
1120 break;
1121 return replace_with_pseudo(insn, old);
1122 case OP_FPCMP ... OP_BINCMP_END:
1123 // Convert:
1124 // setcc.n %t <- %a, %b
1125 // setne.m %r <- %t, $0
1126 // into:
1127 // setcc.n %t <- %a, %b
1128 // setcc.m %r <- %a, $b
1129 // and similar for setne/eq ... 0/1
1130 insn->opcode = inverse ? opcode_table[opcode].negate : opcode;
1131 insn->itype = def->itype;
1132 use_pseudo(insn, def->src1, &insn->src1);
1133 use_pseudo(insn, def->src2, &insn->src2);
1134 remove_usage(old, &insn->src1);
1135 return REPEAT_CSE;
1136
1137 case OP_SEXT:
1138 if (value && (def->orig_type->bit_size == 1))
1139 break;
1140 /* Fall through */
1141 case OP_ZEXT:
1142 // Convert:
1143 // *ext.m %s <- (1) %a
1144 // setne.1 %r <- %s, $0
1145 // into:
1146 // setne.1 %s <- %a, $0
1147 // and same for setne/eq ... 0/1
1148 insn->itype = def->orig_type;
1149 return replace_pseudo(insn, &insn->src1, def->src);
1150 case OP_TRUNC:
1151 if (!one_use(old))
1152 break;
1153 // convert
1154 // trunc.n %s <- (o) %a
1155 // setne.m %r <- %s, $0
1156 // into:
1157 // and.o %s <- %a, $((1 << o) - 1)
1158 // setne.m %r <- %s, $0
1159 // and same for setne/eq ... 0/1
1160 osize = def->size;
1161 def->opcode = OP_AND;
1162 def->type = def->orig_type;
1163 def->size = def->type->bit_size;
1164 def->src2 = value_pseudo(bits_mask(osize));
1165 return REPEAT_CSE;
1166 }
1167 return 0;
1168 }
1169
simplify_compare_constant(struct instruction * insn,long long value)1170 static int simplify_compare_constant(struct instruction *insn, long long value)
1171 {
1172 unsigned size = insn->itype->bit_size;
1173 unsigned long long bits = bits_mask(size);
1174 struct instruction *def;
1175 pseudo_t src1, src2;
1176 unsigned int osize;
1177 int changed = 0;
1178
1179 switch (insn->opcode) {
1180 case OP_SET_LT:
1181 if (!value)
1182 break;
1183 if (value == sign_bit(size)) // (x < SMIN) --> 0
1184 return replace_with_pseudo(insn, value_pseudo(0));
1185 if (value == sign_mask(size)) // (x < SMAX) --> (x != SMAX)
1186 return replace_opcode(insn, OP_SET_NE);
1187 if (value == sign_bit(size) + 1)// (x < SMIN + 1) --> (x == SMIN)
1188 return replace_binop_value(insn, OP_SET_EQ, sign_bit(size));
1189 if (!(value & sign_bit(size)))
1190 changed |= replace_binop_value(insn, OP_SET_LE, (value - 1) & bits);
1191 break;
1192 case OP_SET_LE:
1193 if (!value)
1194 break;
1195 if (value == sign_mask(size)) // (x <= SMAX) --> 1
1196 return replace_with_pseudo(insn, value_pseudo(1));
1197 if (value == sign_bit(size)) // (x <= SMIN) --> (x == SMIN)
1198 return replace_opcode(insn, OP_SET_EQ);
1199 if (value == sign_mask(size) - 1) // (x <= SMAX - 1) --> (x != SMAX)
1200 return replace_binop_value(insn, OP_SET_NE, sign_mask(size));
1201 if (value & sign_bit(size))
1202 changed |= replace_binop_value(insn, OP_SET_LT, (value + 1) & bits);
1203 break;
1204 case OP_SET_GE:
1205 if (!value)
1206 break;
1207 if (value == sign_bit(size)) // (x >= SMIN) --> 1
1208 return replace_with_pseudo(insn, value_pseudo(1));
1209 if (value == sign_mask(size)) // (x >= SMAX) --> (x == SMAX)
1210 return replace_opcode(insn, OP_SET_EQ);
1211 if (value == sign_bit(size) + 1)// (x >= SMIN + 1) --> (x != SMIN)
1212 return replace_binop_value(insn, OP_SET_NE, sign_bit(size));
1213 if (!(value & sign_bit(size)))
1214 changed |= replace_binop_value(insn, OP_SET_GT, (value - 1) & bits);
1215 break;
1216 case OP_SET_GT:
1217 if (!value)
1218 break;
1219 if (value == sign_mask(size)) // (x > SMAX) --> 0
1220 return replace_with_pseudo(insn, value_pseudo(0));
1221 if (value == sign_bit(size)) // (x > SMIN) --> (x != SMIN)
1222 return replace_opcode(insn, OP_SET_NE);
1223 if (value == sign_mask(size) - 1) // (x > SMAX - 1) --> (x == SMAX)
1224 return replace_binop_value(insn, OP_SET_EQ, sign_mask(size));
1225 if (value & sign_bit(size))
1226 changed |= replace_binop_value(insn, OP_SET_GE, (value + 1) & bits);
1227 break;
1228
1229 case OP_SET_B:
1230 if (!value) // (x < 0) --> 0
1231 return replace_with_pseudo(insn, value_pseudo(0));
1232 if (value == 1) // (x < 1) --> (x == 0)
1233 return replace_binop_value(insn, OP_SET_EQ, 0);
1234 else if (value == bits) // (x < ~0) --> (x != ~0)
1235 return replace_binop_value(insn, OP_SET_NE, value);
1236 else // (x < y) --> (x <= (y-1))
1237 changed |= replace_binop_value(insn, OP_SET_BE, (value - 1) & bits);
1238 break;
1239 case OP_SET_AE:
1240 if (!value) // (x >= 0) --> 1
1241 return replace_with_pseudo(insn, value_pseudo(1));
1242 if (value == 1) // (x >= 1) --> (x != 0)
1243 return replace_binop_value(insn, OP_SET_NE, 0);
1244 else if (value == bits) // (x >= ~0) --> (x == ~0)
1245 return replace_binop_value(insn, OP_SET_EQ, value);
1246 else // (x >= y) --> (x > (y-1)
1247 changed |= replace_binop_value(insn, OP_SET_A, (value - 1) & bits);
1248 break;
1249 case OP_SET_BE:
1250 if (!value) // (x <= 0) --> (x == 0)
1251 return replace_opcode(insn, OP_SET_EQ);
1252 if (value == bits) // (x <= ~0) --> 1
1253 return replace_with_pseudo(insn, value_pseudo(1));
1254 if (value == (bits - 1)) // (x <= ~1) --> (x != ~0)
1255 return replace_binop_value(insn, OP_SET_NE, bits);
1256 if (value == (bits >> 1)) // (x u<= SMAX) --> (x s>= 0)
1257 changed |= replace_binop_value(insn, OP_SET_GE, 0);
1258 break;
1259 case OP_SET_A:
1260 if (!value) // (x > 0) --> (x != 0)
1261 return replace_opcode(insn, OP_SET_NE);
1262 if (value == bits) // (x > ~0) --> 0
1263 return replace_with_pseudo(insn, value_pseudo(0));
1264 if (value == (bits - 1)) // (x > ~1) --> (x == ~0)
1265 return replace_binop_value(insn, OP_SET_EQ, bits);
1266 if (value == (bits >> 1)) // (x u> SMAX) --> (x s< 0)
1267 changed |= replace_binop_value(insn, OP_SET_LT, 0);
1268 break;
1269 }
1270
1271 src1 = insn->src1;
1272 src2 = insn->src2;
1273 value = src2->value;
1274 switch (DEF_OPCODE(def, src1)) {
1275 case OP_AND:
1276 if (!constant(def->src2))
1277 break;
1278 bits = def->src2->value;
1279 switch (insn->opcode) {
1280 case OP_SET_EQ:
1281 if ((value & bits) != value)
1282 return replace_with_value(insn, 0);
1283 if (value == bits && is_power_of_2(bits))
1284 return replace_binop_value(insn, OP_SET_NE, 0);
1285 break;
1286 case OP_SET_NE:
1287 if ((value & bits) != value)
1288 return replace_with_value(insn, 1);
1289 if (value == bits && is_power_of_2(bits))
1290 return replace_binop_value(insn, OP_SET_EQ, 0);
1291 break;
1292 case OP_SET_LE: case OP_SET_LT:
1293 value = sign_extend(value, def->size);
1294 if (insn->opcode == OP_SET_LT)
1295 value -= 1;
1296 if (bits & sign_bit(def->size))
1297 break;
1298 if (value < 0)
1299 return replace_with_value(insn, 0);
1300 if (value >= (long long)bits)
1301 return replace_with_value(insn, 1);
1302 if (value == 0)
1303 return replace_opcode(insn, OP_SET_EQ);
1304 break;
1305 case OP_SET_GT: case OP_SET_GE:
1306 value = sign_extend(value, def->size);
1307 if (insn->opcode == OP_SET_GE)
1308 value -= 1;
1309 if (bits & sign_bit(def->size))
1310 break;
1311 if (value < 0)
1312 return replace_with_value(insn, 1);
1313 if (value >= (long long)bits)
1314 return replace_with_value(insn, 0);
1315 if (value == 0)
1316 return replace_opcode(insn, OP_SET_NE);
1317 break;
1318 case OP_SET_B:
1319 if (value > bits)
1320 return replace_with_value(insn, 1);
1321 break;
1322 case OP_SET_BE:
1323 if (value >= bits)
1324 return replace_with_value(insn, 1);
1325 break;
1326 case OP_SET_AE:
1327 if (value > bits)
1328 return replace_with_value(insn, 0);
1329 break;
1330 case OP_SET_A:
1331 if (value >= bits)
1332 return replace_with_value(insn, 0);
1333 break;
1334 }
1335 break;
1336 case OP_OR:
1337 if (!constant(def->src2))
1338 break;
1339 bits = def->src2->value;
1340 switch (insn->opcode) {
1341 case OP_SET_EQ:
1342 if ((value & bits) != bits)
1343 return replace_with_value(insn, 0);
1344 break;
1345 case OP_SET_NE:
1346 if ((value & bits) != bits)
1347 return replace_with_value(insn, 1);
1348 break;
1349 case OP_SET_B:
1350 if (bits >= value)
1351 return replace_with_value(insn, 0);
1352 break;
1353 case OP_SET_BE:
1354 if (bits > value)
1355 return replace_with_value(insn, 0);
1356 break;
1357 case OP_SET_AE:
1358 if (bits > value)
1359 return replace_with_value(insn, 1);
1360 break;
1361 case OP_SET_A:
1362 if (bits >= value)
1363 return replace_with_value(insn, 1);
1364 break;
1365 case OP_SET_LT:
1366 value -= 1;
1367 case OP_SET_LE:
1368 if (bits & sign_bit(def->size)) {
1369 value = sign_extend(value, def->size);
1370 if (value >= -1)
1371 return replace_with_value(insn, 1);
1372 }
1373 break;
1374 case OP_SET_GE:
1375 value -= 1;
1376 case OP_SET_GT:
1377 if (bits & sign_bit(def->size)) {
1378 value = sign_extend(value, def->size);
1379 if (value >= -1)
1380 return replace_with_value(insn, 0);
1381 }
1382 break;
1383 }
1384 break;
1385 case OP_SEXT: // sext(x) cmp C --> x cmp trunc(C)
1386 osize = def->orig_type->bit_size;
1387 if (is_signed_constant(value, osize, size)) {
1388 insn->itype = def->orig_type;
1389 insn->src2 = value_pseudo(zero_extend(value, osize));
1390 return replace_pseudo(insn, &insn->src1, def->src);
1391 }
1392 switch (insn->opcode) {
1393 case OP_SET_BE:
1394 if (value >= sign_bit(osize)) {
1395 insn->itype = def->orig_type;
1396 replace_binop_value(insn, OP_SET_GE, 0);
1397 return replace_pseudo(insn, &insn->src1, def->src);
1398 }
1399 break;
1400 case OP_SET_A:
1401 if (value >= sign_bit(osize)) {
1402 insn->itype = def->orig_type;
1403 replace_binop_value(insn, OP_SET_LT, 0);
1404 return replace_pseudo(insn, &insn->src1, def->src);
1405 }
1406 break;
1407 case OP_SET_LT: case OP_SET_LE:
1408 if (value < sign_bit(size))
1409 return replace_with_value(insn, 1);
1410 else
1411 return replace_with_value(insn, 0);
1412 break;
1413 case OP_SET_GE: case OP_SET_GT:
1414 if (value < sign_bit(size))
1415 return replace_with_value(insn, 0);
1416 else
1417 return replace_with_value(insn, 1);
1418 break;
1419 }
1420 break;
1421 case OP_TRUNC:
1422 osize = def->orig_type->bit_size;
1423 switch (insn->opcode) {
1424 case OP_SET_EQ: case OP_SET_NE:
1425 if (one_use(def->target)) {
1426 insn->itype = def->orig_type;
1427 def->type = def->orig_type;
1428 def->size = osize;
1429 def->src2 = value_pseudo(bits);
1430 return replace_opcode(def, OP_AND);
1431 }
1432 break;
1433 }
1434 break;
1435 case OP_ZEXT:
1436 osize = def->orig_type->bit_size;
1437 bits = bits_mask(osize);
1438 if (value <= bits) {
1439 const struct opcode_table *op = &opcode_table[insn->opcode];
1440 if (op->flags & OPF_SIGNED)
1441 insn->opcode = op->sign;
1442 insn->itype = def->orig_type;
1443 return replace_pseudo(insn, &insn->src1, def->src);
1444 }
1445 switch (insn->opcode) {
1446 case OP_SET_LT: case OP_SET_LE:
1447 if (sign_extend(value, size) > (long long)bits)
1448 return replace_with_value(insn, 1);
1449 else
1450 return replace_with_value(insn, 0);
1451 break;
1452 case OP_SET_GE: case OP_SET_GT:
1453 if (sign_extend(value, size) > (long long)bits)
1454 return replace_with_value(insn, 0);
1455 else
1456 return replace_with_value(insn, 1);
1457 break;
1458 case OP_SET_B: case OP_SET_BE:
1459 return replace_with_value(insn, 1);
1460 case OP_SET_AE: case OP_SET_A:
1461 return replace_with_value(insn, 0);
1462 }
1463 break;
1464 }
1465 return changed;
1466 }
1467
simplify_constant_mask(struct instruction * insn,unsigned long long mask)1468 static int simplify_constant_mask(struct instruction *insn, unsigned long long mask)
1469 {
1470 pseudo_t old = insn->src1;
1471 unsigned long long omask;
1472 unsigned long long nmask;
1473 struct instruction *def;
1474 int osize;
1475
1476 switch (DEF_OPCODE(def, old)) {
1477 case OP_FPCMP ... OP_BINCMP_END:
1478 osize = 1;
1479 goto oldsize;
1480 case OP_OR:
1481 return simplify_mask_or(insn, mask, def);
1482 case OP_LSR:
1483 case OP_SHL:
1484 return simplify_mask_shift(def, mask);
1485 case OP_ZEXT:
1486 osize = def->orig_type->bit_size;
1487 /* fall through */
1488 oldsize:
1489 omask = (1ULL << osize) - 1;
1490 nmask = mask & omask;
1491 if (nmask == omask)
1492 // the AND mask is redundant
1493 return replace_with_pseudo(insn, old);
1494 if (nmask != mask) {
1495 // can use a smaller mask
1496 insn->src2 = value_pseudo(nmask);
1497 return REPEAT_CSE;
1498 }
1499 break;
1500 }
1501 return 0;
1502 }
1503
simplify_const_rightadd(struct instruction * def,struct instruction * insn)1504 static int simplify_const_rightadd(struct instruction *def, struct instruction *insn)
1505 {
1506 unsigned size = insn->size;
1507 pseudo_t src2 = insn->src2;
1508
1509 switch (def->opcode) {
1510 case OP_SUB:
1511 if (constant(def->src1)) { // (C - y) + D --> eval(C+D) - y
1512 pseudo_t val = eval_op(OP_ADD, size, def->src1, src2);
1513 insn->opcode = OP_SUB;
1514 use_pseudo(insn, def->src2, &insn->src2);
1515 return replace_pseudo(insn, &insn->src1, val);
1516 }
1517 break;
1518 }
1519 return 0;
1520 }
1521
simplify_constant_rightside(struct instruction * insn)1522 static int simplify_constant_rightside(struct instruction *insn)
1523 {
1524 long long value = insn->src2->value;
1525 long long sbit = 1ULL << (insn->size - 1);
1526 long long bits = sbit | (sbit - 1);
1527 int changed = 0;
1528
1529 switch (insn->opcode) {
1530 case OP_OR:
1531 if ((value & bits) == bits)
1532 return replace_with_pseudo(insn, insn->src2);
1533 goto case_neutral_zero;
1534
1535 case OP_XOR:
1536 if ((value & bits) == bits) {
1537 insn->opcode = OP_NOT;
1538 return REPEAT_CSE;
1539 }
1540 /* fallthrough */
1541 case_neutral_zero:
1542 if (!value)
1543 return replace_with_pseudo(insn, insn->src1);
1544 return 0;
1545
1546 case OP_SUB:
1547 insn->opcode = OP_ADD;
1548 insn->src2 = eval_unop(OP_NEG, insn->size, insn->src2);
1549 changed = REPEAT_CSE;
1550 /* fallthrough */
1551 case OP_ADD:
1552 if (!value)
1553 return replace_with_pseudo(insn, insn->src1);
1554 if (insn->src1->type == PSEUDO_REG) // (x # y) + z
1555 changed |= simplify_const_rightadd(insn->src1->def, insn);
1556 return changed;
1557 case OP_ASR:
1558 case OP_SHL:
1559 case OP_LSR:
1560 return simplify_shift(insn, insn->src1, value);
1561
1562 case OP_MODU: case OP_MODS:
1563 if (value == 1)
1564 return replace_with_value(insn, 0);
1565 return 0;
1566
1567 case OP_DIVU: case OP_DIVS:
1568 case OP_MUL:
1569 return simplify_mul_div(insn, value);
1570
1571 case OP_AND:
1572 if (!value)
1573 return replace_with_pseudo(insn, insn->src2);
1574 if ((value & bits) == bits)
1575 return replace_with_pseudo(insn, insn->src1);
1576 return simplify_constant_mask(insn, value);
1577
1578 case OP_SET_NE:
1579 case OP_SET_EQ:
1580 if ((changed = simplify_seteq_setne(insn, value)))
1581 return changed;
1582 /* fallthrough */
1583 case OP_SET_LT: case OP_SET_LE: case OP_SET_GE: case OP_SET_GT:
1584 case OP_SET_B: case OP_SET_BE: case OP_SET_AE: case OP_SET_A:
1585 return simplify_compare_constant(insn, value);
1586 }
1587 return 0;
1588 }
1589
simplify_const_leftsub(struct instruction * insn,struct instruction * def)1590 static int simplify_const_leftsub(struct instruction *insn, struct instruction *def)
1591 {
1592 unsigned size = insn->size;
1593 pseudo_t src1 = insn->src1;
1594
1595 switch (def->opcode) {
1596 case OP_ADD:
1597 if (constant(def->src2)) { // C - (y + D) --> eval(C-D) - y
1598 insn->src1 = eval_op(OP_SUB, size, src1, def->src2);
1599 return replace_pseudo(insn, &insn->src2, def->src1);
1600 }
1601 break;
1602 case OP_SUB:
1603 if (constant(def->src1)) { // C - (D - z) --> z + eval(C-D)
1604 pseudo_t val = eval_op(OP_SUB, size, src1, def->src1);
1605 insn->opcode = OP_ADD;
1606 use_pseudo(insn, def->src2, &insn->src1);
1607 return replace_pseudo(insn, &insn->src2, val);
1608 }
1609 break;
1610 }
1611 return 0;
1612 }
1613
simplify_constant_leftside(struct instruction * insn)1614 static int simplify_constant_leftside(struct instruction *insn)
1615 {
1616 long long value = insn->src1->value;
1617
1618 switch (insn->opcode) {
1619 case OP_ADD: case OP_OR: case OP_XOR:
1620 if (!value)
1621 return replace_with_pseudo(insn, insn->src2);
1622 return 0;
1623
1624 case OP_SHL:
1625 case OP_LSR: case OP_ASR:
1626 case OP_AND:
1627 case OP_MUL:
1628 if (!value)
1629 return replace_with_pseudo(insn, insn->src1);
1630 return 0;
1631 case OP_SUB:
1632 if (!value) // (0 - x) --> -x
1633 return replace_with_unop(insn, OP_NEG, insn->src2);
1634 if (insn->src2->type == PSEUDO_REG)
1635 return simplify_const_leftsub(insn, insn->src2->def);
1636 break;
1637 }
1638 return 0;
1639 }
1640
simplify_constant_binop(struct instruction * insn)1641 static int simplify_constant_binop(struct instruction *insn)
1642 {
1643 pseudo_t res = eval_insn(insn);
1644
1645 if (!res)
1646 return 0;
1647
1648 return replace_with_pseudo(insn, res);
1649 }
1650
simplify_binop_same_args(struct instruction * insn,pseudo_t arg)1651 static int simplify_binop_same_args(struct instruction *insn, pseudo_t arg)
1652 {
1653 switch (insn->opcode) {
1654 case OP_SET_NE:
1655 case OP_SET_LT: case OP_SET_GT:
1656 case OP_SET_B: case OP_SET_A:
1657 if (Wtautological_compare)
1658 warning(insn->pos, "self-comparison always evaluates to false");
1659 case OP_SUB:
1660 case OP_XOR:
1661 return replace_with_value(insn, 0);
1662
1663 case OP_SET_EQ:
1664 case OP_SET_LE: case OP_SET_GE:
1665 case OP_SET_BE: case OP_SET_AE:
1666 if (Wtautological_compare)
1667 warning(insn->pos, "self-comparison always evaluates to true");
1668 return replace_with_value(insn, 1);
1669
1670 case OP_AND:
1671 case OP_OR:
1672 return replace_with_pseudo(insn, arg);
1673
1674 default:
1675 break;
1676 }
1677
1678 return 0;
1679 }
1680
simplify_binop(struct instruction * insn)1681 static int simplify_binop(struct instruction *insn)
1682 {
1683 if (constant(insn->src1)) {
1684 if (constant(insn->src2))
1685 return simplify_constant_binop(insn);
1686 return simplify_constant_leftside(insn);
1687 }
1688 if (constant(insn->src2))
1689 return simplify_constant_rightside(insn);
1690 if (insn->src1 == insn->src2)
1691 return simplify_binop_same_args(insn, insn->src1);
1692 return 0;
1693 }
1694
switch_pseudo(struct instruction * insn1,pseudo_t * pp1,struct instruction * insn2,pseudo_t * pp2)1695 static int switch_pseudo(struct instruction *insn1, pseudo_t *pp1, struct instruction *insn2, pseudo_t *pp2)
1696 {
1697 pseudo_t p1 = *pp1, p2 = *pp2;
1698
1699 use_pseudo(insn1, p2, pp1);
1700 use_pseudo(insn2, p1, pp2);
1701 remove_usage(p1, pp1);
1702 remove_usage(p2, pp2);
1703 return REPEAT_CSE;
1704 }
1705
1706 ///
1707 // check if the given pseudos are in canonical order
1708 //
1709 // The canonical order is VOID < UNDEF < PHI < REG < ARG < SYM < VAL
1710 // The rationale is:
1711 // * VALs at right (they don't need a definition)
1712 // * REGs at left (they need a defining instruction)
1713 // * SYMs & ARGs between REGs & VALs
1714 // * REGs & ARGs are ordered between themselves by their internal number
1715 // * SYMs are ordered between themselves by address
1716 // * VOID, UNDEF and PHI are uninteresting (but VOID should have type 0)
canonical_order(pseudo_t p1,pseudo_t p2)1717 static int canonical_order(pseudo_t p1, pseudo_t p2)
1718 {
1719 int t1 = p1->type;
1720 int t2 = p2->type;
1721
1722 /* symbol/constants on the right */
1723 if (t1 < t2)
1724 return 1;
1725 if (t1 > t2)
1726 return 0;
1727 switch (t1) {
1728 case PSEUDO_SYM:
1729 return p1->sym <= p2->sym;
1730 case PSEUDO_REG:
1731 case PSEUDO_ARG:
1732 return p1->nr <= p2->nr;
1733 default:
1734 return 1;
1735 }
1736 }
1737
canonicalize_commutative(struct instruction * insn)1738 static int canonicalize_commutative(struct instruction *insn)
1739 {
1740 if (canonical_order(insn->src1, insn->src2))
1741 return 0;
1742
1743 switch_pseudo(insn, &insn->src1, insn, &insn->src2);
1744 return repeat_phase |= REPEAT_CSE;
1745 }
1746
canonicalize_compare(struct instruction * insn)1747 static int canonicalize_compare(struct instruction *insn)
1748 {
1749 if (canonical_order(insn->src1, insn->src2))
1750 return 0;
1751
1752 switch_pseudo(insn, &insn->src1, insn, &insn->src2);
1753 insn->opcode = opcode_table[insn->opcode].swap;
1754 return repeat_phase |= REPEAT_CSE;
1755 }
1756
simple_pseudo(pseudo_t pseudo)1757 static inline int simple_pseudo(pseudo_t pseudo)
1758 {
1759 return pseudo->type == PSEUDO_VAL || pseudo->type == PSEUDO_SYM;
1760 }
1761
1762 ///
1763 // test if, in the given BB, the ordering of 2 instructions
insn_before(struct basic_block * bb,struct instruction * x,struct instruction * y)1764 static bool insn_before(struct basic_block *bb, struct instruction *x, struct instruction *y)
1765 {
1766 struct instruction *insn;
1767
1768 FOR_EACH_PTR(bb->insns, insn) {
1769 if (insn == x)
1770 return true;
1771 if (insn == y)
1772 return false;
1773 } END_FOR_EACH_PTR(insn);
1774 return false;
1775 }
1776
1777 ///
1778 // check if it safe for a pseudo to be used by an instruction
can_move_to(pseudo_t src,struct instruction * dst)1779 static inline bool can_move_to(pseudo_t src, struct instruction *dst)
1780 {
1781 struct basic_block *bbs, *bbd;
1782 struct instruction *def;
1783
1784 if (!one_use(dst->target))
1785 return false;
1786 if (src->type != PSEUDO_REG)
1787 return true;
1788
1789 def = src->def;
1790 if (dst == def)
1791 return false;
1792 bbs = def->bb;
1793 bbd = dst->bb;
1794 if (bbs == bbd)
1795 return insn_before(bbs, def, dst);
1796 else
1797 return domtree_dominates(bbs, bbd);
1798 }
1799
simplify_associative_binop(struct instruction * insn)1800 static int simplify_associative_binop(struct instruction *insn)
1801 {
1802 struct instruction *def;
1803 pseudo_t pseudo = insn->src1;
1804
1805 if (!simple_pseudo(insn->src2))
1806 return 0;
1807 if (pseudo->type != PSEUDO_REG)
1808 return 0;
1809 def = pseudo->def;
1810 if (def == insn)
1811 return 0;
1812 if (def->opcode != insn->opcode)
1813 return 0;
1814 if (!simple_pseudo(def->src2))
1815 return 0;
1816 if (constant(def->src2) && constant(insn->src2)) {
1817 // (x # C) # K --> x # eval(C # K)
1818 insn->src2 = eval_op(insn->opcode, insn->size, insn->src2, def->src2);
1819 return replace_pseudo(insn, &insn->src1, def->src1);
1820 }
1821 if (!one_use(def->target))
1822 return 0;
1823 switch_pseudo(def, &def->src1, insn, &insn->src2);
1824 return REPEAT_CSE;
1825 }
1826
simplify_add_one_side(struct instruction * insn,pseudo_t * p1,pseudo_t * p2)1827 static int simplify_add_one_side(struct instruction *insn, pseudo_t *p1, pseudo_t *p2)
1828 {
1829 struct instruction *defr = NULL;
1830 struct instruction *def;
1831 pseudo_t src1 = *p1;
1832 pseudo_t src2 = *p2;
1833
1834 switch (DEF_OPCODE(def, src1)) {
1835 case OP_MUL:
1836 if (DEF_OPCODE(defr, *p2) == OP_MUL) {
1837 if (defr->src2 == def->src2 && can_move_to(def->src2, defr)) {
1838 // ((x * z) + (y * z)) into ((x + y) * z)
1839 swap_insn(insn, defr, def->src1, defr->src1, def->src2);
1840 return REPEAT_CSE;
1841 }
1842 if (defr->src1 == def->src1 && can_move_to(def->src1, defr)) {
1843 // ((z * x) + (z * y)) into ((x + y) * z)
1844 swap_insn(insn, defr, def->src2, defr->src2, def->src1);
1845 return REPEAT_CSE;
1846 }
1847 if (defr->src1 == def->src2 && can_move_to(def->src1, defr)) {
1848 // ((x * z) + (z * y)) into ((x + y) * z)
1849 swap_insn(insn, defr, def->src1, defr->src2, def->src2);
1850 return REPEAT_CSE;
1851 }
1852 }
1853 break;
1854
1855 case OP_NEG: // (-x + y) --> (y - x)
1856 return replace_binop(insn, OP_SUB, &insn->src1, src2, &insn->src2, def->src);
1857
1858 case OP_SUB:
1859 if (def->src2 == src2) // (x - y) + y --> x
1860 return replace_with_pseudo(insn, def->src1);
1861 break;
1862 }
1863 return 0;
1864 }
1865
simplify_add(struct instruction * insn)1866 static int simplify_add(struct instruction *insn)
1867 {
1868 return simplify_add_one_side(insn, &insn->src1, &insn->src2) ||
1869 simplify_add_one_side(insn, &insn->src2, &insn->src1);
1870 }
1871
simplify_sub(struct instruction * insn)1872 static int simplify_sub(struct instruction *insn)
1873 {
1874 pseudo_t src1 = insn->src1;
1875 pseudo_t src2 = insn->src2;
1876 struct instruction *def;
1877
1878 switch (DEF_OPCODE(def, src1)) {
1879 case OP_ADD:
1880 if (def->src1 == src2) // (x + y) - x --> y
1881 return replace_with_pseudo(insn, def->src2);
1882 if (def->src2 == src2) // (x + y) - y --> x
1883 return replace_with_pseudo(insn, def->src1);
1884 break;
1885 }
1886
1887 switch (DEF_OPCODE(def, src2)) {
1888 case OP_ADD:
1889 if (src1 == def->src1) // x - (x + z) --> -z
1890 return replace_with_unop(insn, OP_NEG, def->src2);
1891 if (src1 == def->src2) // x - (y + x) --> -y
1892 return replace_with_unop(insn, OP_NEG, def->src1);
1893 break;
1894 case OP_NEG: // (x - -y) --> (x + y)
1895 insn->opcode = OP_ADD;
1896 return replace_pseudo(insn, &insn->src2, def->src);
1897 }
1898
1899 return 0;
1900 }
1901
simplify_compare(struct instruction * insn)1902 static int simplify_compare(struct instruction *insn)
1903 {
1904 pseudo_t src1 = insn->src1;
1905 pseudo_t src2 = insn->src2;
1906 struct instruction *def = NULL;
1907 unsigned int osize;
1908 pseudo_t src;
1909
1910 switch (DEF_OPCODE(def, src1)) {
1911 case OP_SEXT: case OP_ZEXT:
1912 osize = def->orig_type->bit_size;
1913 if ((src = is_same_op(src2, def->opcode, osize))) {
1914 const struct opcode_table *op = &opcode_table[insn->opcode];
1915 if ((def->opcode == OP_ZEXT) && (op->flags & OPF_SIGNED))
1916 insn->opcode = op->sign;
1917 insn->itype = def->orig_type;
1918 replace_pseudo(insn, &insn->src1, def->src);
1919 return replace_pseudo(insn, &insn->src2, src);
1920 }
1921 break;
1922 }
1923 return 0;
1924 }
1925
simplify_and_one_side(struct instruction * insn,pseudo_t * p1,pseudo_t * p2)1926 static int simplify_and_one_side(struct instruction *insn, pseudo_t *p1, pseudo_t *p2)
1927 {
1928 struct instruction *def, *defr = NULL;
1929 pseudo_t src1 = *p1;
1930
1931 switch (DEF_OPCODE(def, src1)) {
1932 case OP_NOT:
1933 if (def->src == *p2)
1934 return replace_with_value(insn, 0);
1935 break;
1936 case OP_BINCMP ... OP_BINCMP_END:
1937 if (DEF_OPCODE(defr, *p2) == opcode_negate(def->opcode)) {
1938 if (def->src1 == defr->src1 && def->src2 == defr->src2)
1939 return replace_with_value(insn, 0);
1940 }
1941 if (def->opcode == OP_SET_GE && is_zero(def->src2)) {
1942 switch (DEF_OPCODE(defr, *p2)) {
1943 case OP_SET_LE:
1944 if (!is_positive(defr->src2, defr->itype->bit_size))
1945 break;
1946 // (x >= 0) && (x <= C) --> (x u<= C)
1947 insn->itype = defr->itype;
1948 replace_binop(insn, OP_SET_BE, &insn->src1, defr->src1, &insn->src2, defr->src2);
1949 return REPEAT_CSE;
1950 }
1951 }
1952 break;
1953 case OP_OR:
1954 if (DEF_OPCODE(defr, *p2) == OP_OR) {
1955 if (defr->src2 == def->src2 && can_move_to(def->src2, defr)) {
1956 // ((x | z) & (y | z)) into ((x & y) | z)
1957 swap_insn(insn, defr, def->src1, defr->src1, def->src2);
1958 return REPEAT_CSE;
1959 }
1960 if (defr->src1 == def->src1 && can_move_to(def->src1, defr)) {
1961 // ((z | x) & (z | y)) into ((x & y) | z)
1962 swap_insn(insn, defr, def->src2, defr->src2, def->src1);
1963 return REPEAT_CSE;
1964 }
1965 if (defr->src1 == def->src2 && can_move_to(def->src1, defr)) {
1966 // ((x | z) & (z | y)) into ((x & y) | z)
1967 swap_insn(insn, defr, def->src1, defr->src2, def->src2);
1968 return REPEAT_CSE;
1969 }
1970 }
1971 break;
1972 case OP_SHL: case OP_LSR: case OP_ASR:
1973 if (DEF_OPCODE(defr, *p2) == def->opcode && defr->src2 == def->src2) {
1974 if (can_move_to(def->src1, defr)) {
1975 // SHIFT(x, s) & SHIFT(y, s) --> SHIFT((x & y), s)
1976 swap_insn(insn, defr, def->src1, defr->src1, def->src2);
1977 return REPEAT_CSE;
1978 }
1979 }
1980 break;
1981 }
1982 return 0;
1983 }
1984
simplify_and(struct instruction * insn)1985 static int simplify_and(struct instruction *insn)
1986 {
1987 return simplify_and_one_side(insn, &insn->src1, &insn->src2) ||
1988 simplify_and_one_side(insn, &insn->src2, &insn->src1);
1989 }
1990
simplify_ior_one_side(struct instruction * insn,pseudo_t * p1,pseudo_t * p2)1991 static int simplify_ior_one_side(struct instruction *insn, pseudo_t *p1, pseudo_t *p2)
1992 {
1993 struct instruction *def, *defr = NULL;
1994 pseudo_t src1 = *p1;
1995
1996 switch (DEF_OPCODE(def, src1)) {
1997 case OP_AND:
1998 if (DEF_OPCODE(defr, *p2) == OP_AND) {
1999 if (defr->src2 == def->src2 && can_move_to(def->src2, defr)) {
2000 // ((x & z) | (y & z)) into ((x | y) & z)
2001 swap_insn(insn, defr, def->src1, defr->src1, def->src2);
2002 return REPEAT_CSE;
2003 }
2004 if (defr->src1 == def->src1 && can_move_to(def->src1, defr)) {
2005 // ((z & x) | (z & y)) into ((x | y) & z)
2006 swap_insn(insn, defr, def->src2, defr->src2, def->src1);
2007 return REPEAT_CSE;
2008 }
2009 if (defr->src1 == def->src2 && can_move_to(def->src1, defr)) {
2010 // ((x & z) | (z & y)) into ((x | y) & z)
2011 swap_insn(insn, defr, def->src1, defr->src2, def->src2);
2012 return REPEAT_CSE;
2013 }
2014 }
2015 break;
2016 case OP_NOT:
2017 if (def->src == *p2)
2018 return replace_with_value(insn, bits_mask(insn->size));
2019 break;
2020 case OP_BINCMP ... OP_BINCMP_END:
2021 if (DEF_OPCODE(defr, *p2) == opcode_negate(def->opcode)) {
2022 if (def->src1 == defr->src1 && def->src2 == defr->src2)
2023 return replace_with_value(insn, 1);
2024 }
2025 break;
2026 case OP_SHL: case OP_LSR: case OP_ASR:
2027 if (DEF_OPCODE(defr, *p2) == def->opcode && defr->src2 == def->src2) {
2028 if (can_move_to(def->src1, defr)) {
2029 // SHIFT(x, s) | SHIFT(y, s) --> SHIFT((x | y), s)
2030 swap_insn(insn, defr, def->src1, defr->src1, def->src2);
2031 return REPEAT_CSE;
2032 }
2033 }
2034 break;
2035 }
2036 return 0;
2037 }
2038
simplify_ior(struct instruction * insn)2039 static int simplify_ior(struct instruction *insn)
2040 {
2041 return simplify_ior_one_side(insn, &insn->src1, &insn->src2) ||
2042 simplify_ior_one_side(insn, &insn->src2, &insn->src1);
2043 }
2044
simplify_xor_one_side(struct instruction * insn,pseudo_t * p1,pseudo_t * p2)2045 static int simplify_xor_one_side(struct instruction *insn, pseudo_t *p1, pseudo_t *p2)
2046 {
2047 struct instruction *def, *defr = NULL;
2048 pseudo_t src1 = *p1;
2049
2050 switch (DEF_OPCODE(def, src1)) {
2051 case OP_AND:
2052 if (DEF_OPCODE(defr, *p2) == OP_AND) {
2053 if (defr->src2 == def->src2 && can_move_to(def->src2, defr)) {
2054 // ((x & z) ^ (y & z)) into ((x ^ y) & z)
2055 swap_insn(insn, defr, def->src1, defr->src1, def->src2);
2056 return REPEAT_CSE;
2057 }
2058 if (defr->src1 == def->src1 && can_move_to(def->src1, defr)) {
2059 // ((z & x) ^ (z & y)) into ((x ^ y) & z)
2060 swap_insn(insn, defr, def->src2, defr->src2, def->src1);
2061 return REPEAT_CSE;
2062 }
2063 if (defr->src1 == def->src2 && can_move_to(def->src1, defr)) {
2064 // ((x & z) ^ (z & y)) into ((x ^ y) & z)
2065 swap_insn(insn, defr, def->src1, defr->src2, def->src2);
2066 return REPEAT_CSE;
2067 }
2068 }
2069 break;
2070 case OP_NOT:
2071 if (def->src == *p2)
2072 return replace_with_value(insn, bits_mask(insn->size));
2073 break;
2074 case OP_BINCMP ... OP_BINCMP_END:
2075 if (DEF_OPCODE(defr, *p2) == opcode_negate(def->opcode)) {
2076 if (def->src1 == defr->src1 && def->src2 == defr->src2)
2077 return replace_with_value(insn, 1);
2078 }
2079 break;
2080 case OP_SHL: case OP_LSR: case OP_ASR:
2081 if (DEF_OPCODE(defr, *p2) == def->opcode && defr->src2 == def->src2) {
2082 if (can_move_to(def->src1, defr)) {
2083 // SHIFT(x, s) ^ SHIFT(y, s) --> SHIFT((x ^ y), s)
2084 swap_insn(insn, defr, def->src1, defr->src1, def->src2);
2085 return REPEAT_CSE;
2086 }
2087 }
2088 break;
2089 }
2090 return 0;
2091 }
2092
simplify_xor(struct instruction * insn)2093 static int simplify_xor(struct instruction *insn)
2094 {
2095 return simplify_xor_one_side(insn, &insn->src1, &insn->src2) ||
2096 simplify_xor_one_side(insn, &insn->src2, &insn->src1);
2097 }
2098
simplify_constant_unop(struct instruction * insn)2099 static int simplify_constant_unop(struct instruction *insn)
2100 {
2101 long long val = insn->src1->value;
2102 long long res, mask;
2103
2104 switch (insn->opcode) {
2105 case OP_NOT:
2106 res = ~val;
2107 break;
2108 case OP_NEG:
2109 res = -val;
2110 break;
2111 case OP_SEXT:
2112 mask = 1ULL << (insn->orig_type->bit_size-1);
2113 if (val & mask)
2114 val |= ~(mask | (mask-1));
2115 /* fall through */
2116 case OP_ZEXT:
2117 case OP_TRUNC:
2118 res = val;
2119 break;
2120 default:
2121 return 0;
2122 }
2123 mask = 1ULL << (insn->size-1);
2124 res &= mask | (mask-1);
2125
2126 return replace_with_value(insn, res);
2127 }
2128
simplify_unop(struct instruction * insn)2129 static int simplify_unop(struct instruction *insn)
2130 {
2131 struct instruction *def;
2132 pseudo_t src = insn->src;
2133
2134 if (constant(src))
2135 return simplify_constant_unop(insn);
2136
2137 switch (insn->opcode) {
2138 case OP_NOT:
2139 switch (DEF_OPCODE(def, src)) {
2140 case OP_ADD:
2141 if (!constant(def->src2))
2142 break;
2143 insn->opcode = OP_SUB; // ~(x + C) --> ~C - x
2144 src = eval_unop(OP_NOT, insn->size, def->src2);
2145 use_pseudo(insn, def->src1, &insn->src2);
2146 return replace_pseudo(insn, &insn->src1, src);
2147 case OP_NEG:
2148 insn->opcode = OP_SUB; // ~(-x) --> x - 1
2149 insn->src2 = value_pseudo(1);
2150 return replace_pseudo(insn, &insn->src1, def->src);
2151 case OP_NOT: // ~(~x) --> x
2152 return replace_with_pseudo(insn, def->src);
2153 case OP_SUB:
2154 if (!constant(def->src1))
2155 break;
2156 insn->opcode = OP_ADD; // ~(C - x) --> x + ~C
2157 insn->src2 = eval_unop(OP_NOT, insn->size, def->src1);
2158 return replace_pseudo(insn, &insn->src1, def->src2);
2159 case OP_XOR:
2160 if (!constant(def->src2))
2161 break;
2162 insn->opcode = OP_XOR; // ~(x ^ C) --> x ^ ~C
2163 insn->src2 = eval_unop(OP_NOT, insn->size, def->src2);
2164 return replace_pseudo(insn, &insn->src1, def->src1);
2165 }
2166 break;
2167 case OP_NEG:
2168 switch (DEF_OPCODE(def, src)) {
2169 case OP_ADD:
2170 if (!constant(def->src2))
2171 break;
2172 insn->opcode = OP_SUB; // -(x + C) --> (-C - x)
2173 src = eval_unop(OP_NEG, insn->size, def->src2);
2174 use_pseudo(insn, def->src1, &insn->src2);
2175 return replace_pseudo(insn, &insn->src1, src);
2176 case OP_NEG: // -(-x) --> x
2177 return replace_with_pseudo(insn, def->src);
2178 case OP_NOT:
2179 insn->opcode = OP_ADD; // -(~x) --> x + 1
2180 insn->src2 = value_pseudo(1);
2181 return replace_pseudo(insn, &insn->src1, def->src);
2182 case OP_SUB:
2183 insn->opcode = OP_SUB; // -(x - y) --> y - x
2184 use_pseudo(insn, def->src1, &insn->src2);
2185 return replace_pseudo(insn, &insn->src1, def->src2);
2186 }
2187 break;
2188 default:
2189 return 0;
2190 }
2191 return 0;
2192 }
2193
simplify_one_memop(struct instruction * insn,pseudo_t orig)2194 static int simplify_one_memop(struct instruction *insn, pseudo_t orig)
2195 {
2196 pseudo_t addr = insn->src;
2197 pseudo_t new, off;
2198
2199 if (addr->type == PSEUDO_REG) {
2200 struct instruction *def = addr->def;
2201 if (def->opcode == OP_SYMADDR && def->src) {
2202 kill_use(&insn->src);
2203 use_pseudo(insn, def->src, &insn->src);
2204 return REPEAT_CSE;
2205 }
2206 if (def->opcode == OP_ADD) {
2207 new = def->src1;
2208 off = def->src2;
2209 if (constant(off))
2210 goto offset;
2211 new = off;
2212 off = def->src1;
2213 if (constant(off))
2214 goto offset;
2215 return 0;
2216 }
2217 }
2218 return 0;
2219
2220 offset:
2221 /* Invalid code */
2222 if (new == orig || new == addr) {
2223 if (new == VOID)
2224 return 0;
2225 /*
2226 * If some BB have been removed it is possible that this
2227 * memop is in fact part of a dead BB. In this case
2228 * we must not warn since nothing is wrong.
2229 * If not part of a dead BB this will be redone after
2230 * the BBs have been cleaned up.
2231 */
2232 if (repeat_phase & REPEAT_CFG_CLEANUP)
2233 return 0;
2234 warning(insn->pos, "crazy programmer");
2235 replace_pseudo(insn, &insn->src, VOID);
2236 return 0;
2237 }
2238 insn->offset += off->value;
2239 replace_pseudo(insn, &insn->src, new);
2240 return REPEAT_CSE;
2241 }
2242
2243 ///
2244 // simplify memops instructions
2245 //
2246 // :note: We walk the whole chain of adds/subs backwards.
2247 // That's not only more efficient, but it allows us to find loops.
simplify_memop(struct instruction * insn)2248 static int simplify_memop(struct instruction *insn)
2249 {
2250 int one, ret = 0;
2251 pseudo_t orig = insn->src;
2252
2253 do {
2254 one = simplify_one_memop(insn, orig);
2255 ret |= one;
2256 } while (one);
2257 return ret;
2258 }
2259
simplify_cast(struct instruction * insn)2260 static int simplify_cast(struct instruction *insn)
2261 {
2262 unsigned long long mask;
2263 struct instruction *def, *def2;
2264 pseudo_t src = insn->src;
2265 pseudo_t val;
2266 int osize;
2267 int size;
2268
2269 /* A cast of a constant? */
2270 if (constant(src))
2271 return simplify_constant_unop(insn);
2272
2273 // can merge with the previous instruction?
2274 size = insn->size;
2275 def = src->def;
2276 switch (def_opcode(src)) {
2277 case OP_AND:
2278 val = def->src2;
2279 if (val->type != PSEUDO_VAL)
2280 break;
2281 /* A cast of a AND might be a no-op.. */
2282 switch (insn->opcode) {
2283 case OP_TRUNC:
2284 if (!one_use(src))
2285 break;
2286 def->opcode = OP_TRUNC;
2287 def->orig_type = def->type;
2288 def->type = insn->type;
2289 def->size = size;
2290
2291 insn->opcode = OP_AND;
2292 mask = val->value;
2293 mask &= (1ULL << size) - 1;
2294 insn->src2 = value_pseudo(mask);
2295 return REPEAT_CSE;
2296
2297 case OP_SEXT:
2298 if (val->value & (1 << (def->size - 1)))
2299 break;
2300 // OK, sign bit is 0
2301 case OP_ZEXT:
2302 if (!one_use(src))
2303 break;
2304 // transform:
2305 // and.n %b <- %a, M
2306 // *ext.m %c <- (n) %b
2307 // into:
2308 // zext.m %b <- %a
2309 // and.m %c <- %b, M
2310 // For ZEXT, the mask will always be small
2311 // enough. For SEXT, it can only be done if
2312 // the mask force the sign bit to 0.
2313 def->opcode = OP_ZEXT;
2314 def->orig_type = insn->orig_type;
2315 def->type = insn->type;
2316 def->size = insn->size;
2317 insn->opcode = OP_AND;
2318 insn->src2 = val;
2319 return REPEAT_CSE;
2320 }
2321 break;
2322 case OP_FPCMP ... OP_BINCMP_END:
2323 switch (insn->opcode) {
2324 case OP_SEXT:
2325 if (insn->size == 1)
2326 break;
2327 /* fall through */
2328 case OP_ZEXT:
2329 case OP_TRUNC:
2330 // simplify:
2331 // setcc.n %t <- %a, %b
2332 // zext.m %r <- (n) %t
2333 // into:
2334 // setcc.m %r <- %a, %b
2335 // and same for s/zext/trunc/
2336 insn->opcode = def->opcode;
2337 insn->itype = def->itype;
2338 use_pseudo(insn, def->src2, &insn->src2);
2339 return replace_pseudo(insn, &insn->src1, def->src1);
2340 }
2341 break;
2342 case OP_NOT:
2343 switch (insn->opcode) {
2344 case OP_TRUNC:
2345 if (one_use(src)) {
2346 // TRUNC(NOT(x)) --> NOT(TRUNC(x))
2347 insn->opcode = OP_NOT;
2348 def->orig_type = def->type;
2349 def->opcode = OP_TRUNC;
2350 def->type = insn->type;
2351 def->size = insn->size;
2352 return REPEAT_CSE;
2353 }
2354 break;
2355 }
2356 break;
2357 case OP_OR:
2358 switch (insn->opcode) {
2359 case OP_TRUNC:
2360 mask = bits_mask(insn->size);
2361 return simplify_mask_or(insn, mask, def);
2362 }
2363 break;
2364 case OP_LSR:
2365 case OP_SHL:
2366 if (insn->opcode != OP_TRUNC)
2367 break;
2368 mask = bits_mask(insn->size);
2369 return simplify_mask_shift(def, mask);
2370 case OP_TRUNC:
2371 switch (insn->opcode) {
2372 case OP_TRUNC:
2373 insn->orig_type = def->orig_type;
2374 return replace_pseudo(insn, &insn->src1, def->src);
2375 case OP_SEXT:
2376 if (size != def->orig_type->bit_size)
2377 break;
2378 if (DEF_OPCODE(def2, def->src) != OP_LSR)
2379 break;
2380 if (def2->src2 != value_pseudo(size - def->size))
2381 break;
2382 // SEXT(TRUNC(LSR(x, N))) --> ASR(x, N)
2383 insn->opcode = OP_ASR;
2384 insn->src2 = def2->src2;
2385 return replace_pseudo(insn, &insn->src1, def2->src1);
2386 case OP_ZEXT:
2387 if (size != def->orig_type->bit_size)
2388 break;
2389 insn->opcode = OP_AND;
2390 insn->src2 = value_pseudo((1ULL << def->size) - 1);
2391 return replace_pseudo(insn, &insn->src1, def->src);
2392 }
2393 break;
2394 case OP_ZEXT:
2395 switch (insn->opcode) {
2396 case OP_SEXT:
2397 insn->opcode = OP_ZEXT;
2398 /* fall through */
2399 case OP_ZEXT:
2400 insn->orig_type = def->orig_type;
2401 return replace_pseudo(insn, &insn->src, def->src);
2402 }
2403 /* fall through */
2404 case OP_SEXT:
2405 switch (insn->opcode) {
2406 case OP_TRUNC:
2407 osize = def->orig_type->bit_size;
2408 if (size == osize)
2409 return replace_with_pseudo(insn, def->src);
2410 if (size > osize)
2411 insn->opcode = def->opcode;
2412 insn->orig_type = def->orig_type;
2413 return replace_pseudo(insn, &insn->src, def->src);
2414 }
2415 switch (insn->opcode) {
2416 case OP_SEXT:
2417 insn->orig_type = def->orig_type;
2418 return replace_pseudo(insn, &insn->src, def->src);
2419 }
2420 break;
2421 }
2422
2423 return 0;
2424 }
2425
simplify_select(struct instruction * insn)2426 static int simplify_select(struct instruction *insn)
2427 {
2428 pseudo_t cond, src1, src2;
2429 struct instruction *def;
2430
2431 cond = insn->src1;
2432 src1 = insn->src2;
2433 src2 = insn->src3;
2434
2435 if (constant(cond))
2436 return replace_with_pseudo(insn, cond->value ? src1 : src2);
2437 if (src1 == src2)
2438 return replace_with_pseudo(insn, src1);
2439
2440 if (constant(src1) && constant(src2)) {
2441 long long val1 = src1->value;
2442 long long val2 = src2->value;
2443
2444 /* The pair 0/1 is special - replace with SETNE/SETEQ */
2445 if ((val1 | val2) == 1) {
2446 int opcode = OP_SET_EQ;
2447 if (val1) {
2448 src1 = src2;
2449 opcode = OP_SET_NE;
2450 }
2451 insn->opcode = opcode;
2452 /* insn->src1 is already cond */
2453 insn->src2 = src1; /* Zero */
2454 return REPEAT_CSE;
2455 }
2456 }
2457 if (cond == src2 && is_zero(src1)) // SEL(x, 0, x) --> 0
2458 return replace_with_pseudo(insn, src1);
2459 if (cond == src1 && is_zero(src2)) // SEL(x, x, 0) --> x
2460 return replace_with_pseudo(insn, cond);
2461
2462 switch (DEF_OPCODE(def, cond)) {
2463 case OP_SET_EQ:
2464 if (src1 == def->src1 && src2 == def->src2)
2465 return replace_with_pseudo(insn, src2); // SEL(x==y,x,y) --> y
2466 if (src2 == def->src1 && src1 == def->src2)
2467 return replace_with_pseudo(insn, src2); // SEL(y==x,x,y) --> y
2468 break;
2469 case OP_SET_NE:
2470 if (src1 == def->src1 && src2 == def->src2)
2471 return replace_with_pseudo(insn, src1); // SEL(x!=y,x,y) --> x
2472 if (src2 == def->src1 && src1 == def->src2)
2473 return replace_with_pseudo(insn, src1); // SEL(y!=x,x,y) --> x
2474 break;
2475 case OP_SET_LE: case OP_SET_LT:
2476 case OP_SET_BE: case OP_SET_B:
2477 if (!one_use(cond))
2478 break;
2479 // SEL(x {<,<=} y, a, b) --> SEL(x {>=,>} y, b, a)
2480 def->opcode = opcode_negate(def->opcode);
2481 return switch_pseudo(insn, &insn->src2, insn, &insn->src3);
2482 case OP_SET_GT:
2483 if (one_use(cond) && is_zero(def->src2)) {
2484 if (is_negate_of(src2, src1))
2485 // SEL(x > 0, a, -a) --> SEL(x >= 0, a, -a)
2486 return replace_opcode(def, OP_SET_GE);
2487 }
2488 break;
2489 case OP_SEL:
2490 if (constant(def->src2) && constant(def->src3)) {
2491 // Is the def of the conditional another select?
2492 // And if that one results in a "zero or not", use the
2493 // original conditional instead.
2494 // SEL(SEL(x, C, 0), y, z) --> SEL(x, y, z)
2495 // SEL(SEL(x, C, 0), C, 0) --> SEL(x, C, 0) == cond
2496 // SEL(SEL(x, 0, C), y, z) --> SEL(x, z, y)
2497 // SEL(SEL(x, C1, C2), y, z) --> y
2498 if (!def->src3->value) {
2499 if ((src1 == def->src2) && (src2 == def->src3))
2500 return replace_with_pseudo(insn, cond);
2501 return replace_pseudo(insn, &insn->cond, def->cond);
2502 }
2503 if (!def->src2->value) {
2504 switch_pseudo(insn, &insn->src2, insn, &insn->src3);
2505 return replace_pseudo(insn, &insn->cond, def->cond);
2506 }
2507 // both values must be non-zero
2508 return replace_with_pseudo(insn, src1);
2509 }
2510 case OP_AND:
2511 if (is_pow2(def->src2) && is_pow2(src1) && is_zero(src2) && insn->size == def->size && one_use(cond)) {
2512 unsigned s1 = log2_exact(def->src2->value);
2513 unsigned s2 = log2_exact(insn->src2->value);
2514 unsigned shift;
2515
2516 if (s1 == s2)
2517 return replace_with_pseudo(insn, cond);
2518
2519 // SEL(x & A, B, 0) --> SHIFT(x & A, S)
2520 insn->opcode = (s1 < s2) ? OP_SHL : OP_LSR;
2521 shift = (s1 < s2) ? (s2 - s1) : (s1 - s2);
2522 insn->src2 = value_pseudo(shift);
2523 return REPEAT_CSE;
2524 }
2525 break;
2526 }
2527
2528 switch (DEF_OPCODE(def, src1)) {
2529 case OP_ADD: case OP_OR: case OP_XOR:
2530 if ((def->src1 == src2) && can_move_to(cond, def)) {
2531 // SEL(x, OP(y,z), y) --> OP(SEL(x, z, 0), y)
2532 swap_select(insn, def, cond, def->src2, value_pseudo(0), src2);
2533 return REPEAT_CSE;
2534 }
2535 if ((def->src2 == src2) && can_move_to(cond, def)) {
2536 // SEL(x, OP(z,y), y) --> OP(SEL(x, z, 0), y)
2537 swap_select(insn, def, cond, def->src1, value_pseudo(0), src2);
2538 return REPEAT_CSE;
2539 }
2540 break;
2541 }
2542
2543 switch (DEF_OPCODE(def, src2)) {
2544 case OP_ADD: case OP_OR: case OP_XOR:
2545 if ((def->src1 == src1) && can_move_to(cond, def)) {
2546 // SEL(x, y, OP(y,z)) --> OP(SEL(x, 0, z), y)
2547 swap_select(insn, def, cond, value_pseudo(0), def->src2, src1);
2548 return REPEAT_CSE;
2549 }
2550 if ((def->src2 == src1) && can_move_to(cond, def)) {
2551 // SEL(x, y, OP(z,y)) --> OP(SEL(x, 0, z), y)
2552 swap_select(insn, def, cond, value_pseudo(0), def->src1, src1);
2553 return REPEAT_CSE;
2554 }
2555 break;
2556 }
2557 return 0;
2558 }
2559
is_in_range(pseudo_t src,long long low,long long high)2560 static int is_in_range(pseudo_t src, long long low, long long high)
2561 {
2562 long long value;
2563
2564 switch (src->type) {
2565 case PSEUDO_VAL:
2566 value = src->value;
2567 return value >= low && value <= high;
2568 default:
2569 return 0;
2570 }
2571 }
2572
simplify_range(struct instruction * insn)2573 static int simplify_range(struct instruction *insn)
2574 {
2575 pseudo_t src1, src2, src3;
2576
2577 src1 = insn->src1;
2578 src2 = insn->src2;
2579 src3 = insn->src3;
2580 if (src2->type != PSEUDO_VAL || src3->type != PSEUDO_VAL)
2581 return 0;
2582 if (is_in_range(src1, src2->value, src3->value)) {
2583 kill_instruction(insn);
2584 return REPEAT_CSE;
2585 }
2586 return 0;
2587 }
2588
2589 ///
2590 // simplify SET_NE/EQ $0 + BR
simplify_cond_branch(struct instruction * br,struct instruction * def,pseudo_t newcond)2591 static int simplify_cond_branch(struct instruction *br, struct instruction *def, pseudo_t newcond)
2592 {
2593 replace_pseudo(br, &br->cond, newcond);
2594 if (def->opcode == OP_SET_EQ) {
2595 struct basic_block *tmp = br->bb_true;
2596 br->bb_true = br->bb_false;
2597 br->bb_false = tmp;
2598 }
2599 return REPEAT_CSE;
2600 }
2601
simplify_branch(struct instruction * insn)2602 static int simplify_branch(struct instruction *insn)
2603 {
2604 pseudo_t cond = insn->cond;
2605
2606 /* Constant conditional */
2607 if (constant(cond))
2608 return convert_to_jump(insn, cond->value ? insn->bb_true : insn->bb_false);
2609
2610 /* Same target? */
2611 if (insn->bb_true == insn->bb_false)
2612 return convert_to_jump(insn, insn->bb_true);
2613
2614 /* Conditional on a SETNE $0 or SETEQ $0 */
2615 if (cond->type == PSEUDO_REG) {
2616 struct instruction *def = cond->def;
2617
2618 if (def->opcode == OP_SET_NE || def->opcode == OP_SET_EQ) {
2619 if (constant(def->src1) && !def->src1->value)
2620 return simplify_cond_branch(insn, def, def->src2);
2621 if (constant(def->src2) && !def->src2->value)
2622 return simplify_cond_branch(insn, def, def->src1);
2623 }
2624 if (def->opcode == OP_SEL) {
2625 if (constant(def->src2) && constant(def->src3)) {
2626 long long val1 = def->src2->value;
2627 long long val2 = def->src3->value;
2628 if (!val1 && !val2)
2629 return convert_to_jump(insn, insn->bb_false);
2630 if (val1 && val2)
2631 return convert_to_jump(insn, insn->bb_true);
2632 if (val2) {
2633 struct basic_block *tmp = insn->bb_true;
2634 insn->bb_true = insn->bb_false;
2635 insn->bb_false = tmp;
2636 }
2637 return replace_pseudo(insn, &insn->cond, def->src1);
2638 }
2639 }
2640 if (def->opcode == OP_SEXT || def->opcode == OP_ZEXT)
2641 return replace_pseudo(insn, &insn->cond, def->src);
2642 }
2643 return 0;
2644 }
2645
simplify_switch(struct instruction * insn)2646 static int simplify_switch(struct instruction *insn)
2647 {
2648 pseudo_t cond = insn->cond;
2649 long long val;
2650 struct multijmp *jmp;
2651
2652 if (!constant(cond))
2653 return 0;
2654 val = insn->cond->value;
2655
2656 FOR_EACH_PTR(insn->multijmp_list, jmp) {
2657 /* Default case */
2658 if (jmp->begin > jmp->end)
2659 goto found;
2660 if (val >= jmp->begin && val <= jmp->end)
2661 goto found;
2662 } END_FOR_EACH_PTR(jmp);
2663 warning(insn->pos, "Impossible case statement");
2664 return 0;
2665
2666 found:
2667 return convert_to_jump(insn, jmp->target);
2668 }
2669
is_label(pseudo_t pseudo)2670 static struct basic_block *is_label(pseudo_t pseudo)
2671 {
2672 struct instruction *def;
2673
2674 if (DEF_OPCODE(def, pseudo) != OP_LABEL)
2675 return NULL;
2676 return def->bb_true;
2677 }
2678
simplify_cgoto(struct instruction * insn)2679 static int simplify_cgoto(struct instruction *insn)
2680 {
2681 struct basic_block *target, *bb = insn->bb;
2682 struct basic_block *bbt, *bbf;
2683 struct instruction *def;
2684 struct multijmp *jmp;
2685
2686 switch (DEF_OPCODE(def, insn->src)) {
2687 case OP_SEL: // CGOTO(SEL(x, L1, L2)) --> CBR x, L1, L2
2688 if ((bbt = is_label(def->src2)) && (bbf = is_label(def->src3))) {
2689 insn->opcode = OP_CBR;
2690 insn->bb_true = bbt;
2691 insn->bb_false = bbf;
2692 return replace_pseudo(insn, &insn->src1, def->cond);
2693 }
2694 break;
2695 case OP_LABEL:
2696 target = def->bb_true;
2697 if (!target->ep)
2698 return 0;
2699 FOR_EACH_PTR(insn->multijmp_list, jmp) {
2700 if (jmp->target == target)
2701 continue;
2702 remove_bb_from_list(&jmp->target->parents, bb, 1);
2703 remove_bb_from_list(&bb->children, jmp->target, 1);
2704 DELETE_CURRENT_PTR(jmp);
2705 } END_FOR_EACH_PTR(jmp);
2706 kill_use(&insn->src);
2707 insn->opcode = OP_BR;
2708 insn->bb_true = target;
2709 return REPEAT_CSE|REPEAT_CFG_CLEANUP;
2710 }
2711 return 0;
2712 }
2713
simplify_setval(struct instruction * insn)2714 static int simplify_setval(struct instruction *insn)
2715 {
2716 struct expression *val = insn->val;
2717
2718 switch (val->type) {
2719 case EXPR_LABEL:
2720 insn->opcode = OP_LABEL;
2721 insn->bb_true = val->symbol->bb_target;
2722 return REPEAT_CSE;
2723 default:
2724 break;
2725 }
2726 return 0;
2727 }
2728
simplify_instruction(struct instruction * insn)2729 int simplify_instruction(struct instruction *insn)
2730 {
2731 unsigned flags;
2732 int changed = 0;
2733
2734 flags = opcode_table[insn->opcode].flags;
2735 if (flags & OPF_TARGET) {
2736 if (!has_users(insn->target))
2737 return kill_instruction(insn);
2738 }
2739 if (flags & OPF_COMMU)
2740 canonicalize_commutative(insn) ;
2741 if (flags & OPF_COMPARE)
2742 canonicalize_compare(insn) ;
2743 if (flags & OPF_BINOP) {
2744 if ((changed = simplify_binop(insn)))
2745 return changed;
2746 }
2747 if (flags & OPF_ASSOC) {
2748 if ((changed = simplify_associative_binop(insn)))
2749 return changed;
2750 }
2751 if (flags & OPF_UNOP) {
2752 if ((changed = simplify_unop(insn)))
2753 return changed;
2754 }
2755
2756 switch (insn->opcode) {
2757 case OP_ADD: return simplify_add(insn);
2758 case OP_SUB: return simplify_sub(insn);
2759 case OP_AND: return simplify_and(insn);
2760 case OP_OR: return simplify_ior(insn);
2761 case OP_XOR: return simplify_xor(insn);
2762 case OP_MUL:
2763 case OP_SHL:
2764 case OP_LSR:
2765 case OP_ASR:
2766 case OP_NOT:
2767 case OP_NEG:
2768 case OP_DIVU:
2769 case OP_DIVS:
2770 case OP_MODU:
2771 case OP_MODS:
2772 break;
2773 case OP_BINCMP ... OP_BINCMP_END:
2774 return simplify_compare(insn);
2775 case OP_LOAD:
2776 case OP_STORE:
2777 return simplify_memop(insn);
2778 case OP_SYMADDR:
2779 return replace_with_pseudo(insn, insn->src);
2780 case OP_SEXT: case OP_ZEXT:
2781 case OP_TRUNC:
2782 return simplify_cast(insn);
2783 case OP_FNEG:
2784 case OP_FCVTU: case OP_FCVTS:
2785 case OP_UCVTF: case OP_SCVTF:
2786 case OP_FCVTF:
2787 case OP_PTRCAST:
2788 break;
2789 case OP_UTPTR:
2790 case OP_PTRTU:
2791 return replace_with_pseudo(insn, insn->src);
2792 case OP_SLICE:
2793 break;
2794 case OP_SETVAL:
2795 return simplify_setval(insn);
2796 case OP_LABEL:
2797 case OP_SETFVAL:
2798 break;
2799 case OP_PHI:
2800 return clean_up_phi(insn);
2801 case OP_PHISOURCE:
2802 break;
2803 case OP_SEL:
2804 return simplify_select(insn);
2805 case OP_CBR:
2806 return simplify_branch(insn);
2807 case OP_SWITCH:
2808 return simplify_switch(insn);
2809 case OP_COMPUTEDGOTO:
2810 return simplify_cgoto(insn);
2811 case OP_RANGE:
2812 return simplify_range(insn);
2813 case OP_FADD:
2814 case OP_FSUB:
2815 case OP_FMUL:
2816 case OP_FDIV:
2817 break;
2818 }
2819 return 0;
2820 }
2821