1 /*
2 * Simplify - do instruction simplification before CSE
3 *
4 * Copyright (C) 2004 Linus Torvalds
5 */
6
7 #include <assert.h>
8
9 #include "parse.h"
10 #include "expression.h"
11 #include "linearize.h"
12 #include "flow.h"
13 #include "symbol.h"
14
15 /* Find the trivial parent for a phi-source */
16 static struct basic_block *phi_parent(struct basic_block *source, pseudo_t pseudo)
17 {
18 /* Can't go upwards if the pseudo is defined in the bb it came from.. */
19 if (pseudo->type == PSEUDO_REG) {
20 struct instruction *def = pseudo->def;
21 if (def->bb == source)
22 return source;
23 }
24 if (bb_list_size(source->children) != 1 || bb_list_size(source->parents) != 1)
25 return source;
26 return first_basic_block(source->parents);
27 }
28
29 /*
30 * Copy the phi-node's phisrcs into to given array.
31 * Returns 0 if the the list contained the expected
32 * number of element, a positive number if there was
33 * more than expected and a negative one if less.
34 *
35 * Note: we can't reuse a function like linearize_ptr_list()
36 * because any VOIDs in the phi-list must be ignored here
37 * as in this context they mean 'entry has been removed'.
38 */
39 static int get_phisources(struct instruction *sources[], int nbr, struct instruction *insn)
40 {
41 pseudo_t phi;
42 int i = 0;
43
44 assert(insn->opcode == OP_PHI);
45 FOR_EACH_PTR(insn->phi_list, phi) {
46 struct instruction *def;
47 if (phi == VOID)
48 continue;
49 if (i >= nbr)
50 return 1;
51 def = phi->def;
52 assert(def->opcode == OP_PHISOURCE);
53 sources[i++] = def;
54 } END_FOR_EACH_PTR(phi);
55 return i - nbr;
56 }
57
58 static int if_convert_phi(struct instruction *insn)
59 {
60 struct instruction *array[2];
61 struct basic_block *parents[3];
62 struct basic_block *bb, *bb1, *bb2, *source;
63 struct instruction *br;
64 pseudo_t p1, p2;
65
66 bb = insn->bb;
67 if (get_phisources(array, 2, insn))
68 return 0;
69 if (linearize_ptr_list((struct ptr_list *)bb->parents, (void **)parents, 3) != 2)
70 return 0;
71 p1 = array[0]->src1;
72 bb1 = array[0]->bb;
73 p2 = array[1]->src1;
74 bb2 = array[1]->bb;
75
76 /* Only try the simple "direct parents" case */
77 if ((bb1 != parents[0] || bb2 != parents[1]) &&
78 (bb1 != parents[1] || bb2 != parents[0]))
79 return 0;
80
81 /*
82 * See if we can find a common source for this..
83 */
84 source = phi_parent(bb1, p1);
85 if (source != phi_parent(bb2, p2))
86 return 0;
87
88 /*
89 * Cool. We now know that 'source' is the exclusive
90 * parent of both phi-nodes, so the exit at the
91 * end of it fully determines which one it is, and
92 * we can turn it into a select.
93 *
94 * HOWEVER, right now we only handle regular
95 * conditional branches. No multijumps or computed
96 * stuff. Verify that here.
97 */
98 br = last_instruction(source->insns);
99 if (!br || br->opcode != OP_CBR)
100 return 0;
101
102 assert(br->cond);
103 assert(br->bb_false);
104
105 /*
106 * We're in business. Match up true/false with p1/p2.
107 */
108 if (br->bb_true == bb2 || br->bb_false == bb1) {
109 pseudo_t p = p1;
110 p1 = p2;
111 p2 = p;
112 }
113
114 /*
115 * OK, we can now replace that last
116 *
117 * br cond, a, b
118 *
119 * with the sequence
120 *
121 * setcc cond
122 * select pseudo, p1, p2
123 * br cond, a, b
124 *
125 * and remove the phi-node. If it then
126 * turns out that 'a' or 'b' is entirely
127 * empty (common case), and now no longer
128 * a phi-source, we'll be able to simplify
129 * the conditional branch too.
130 */
131 insert_select(source, br, insn, p1, p2);
132 kill_instruction(insn);
133 return REPEAT_CSE;
134 }
135
136 static int clean_up_phi(struct instruction *insn)
137 {
138 pseudo_t phi;
139 struct instruction *last;
140 int same;
141
142 last = NULL;
143 same = 1;
144 FOR_EACH_PTR(insn->phi_list, phi) {
145 struct instruction *def;
146 if (phi == VOID)
147 continue;
148 def = phi->def;
149 if (def->src1 == VOID || !def->bb)
150 continue;
151 if (last) {
152 if (last->src1 != def->src1)
153 same = 0;
154 continue;
155 }
156 last = def;
157 } END_FOR_EACH_PTR(phi);
158
159 if (same) {
160 pseudo_t pseudo = last ? last->src1 : VOID;
161 convert_instruction_target(insn, pseudo);
162 kill_instruction(insn);
163 return REPEAT_CSE;
164 }
165
166 return if_convert_phi(insn);
167 }
168
169 static int delete_pseudo_user_list_entry(struct pseudo_user_list **list, pseudo_t *entry, int count)
170 {
171 struct pseudo_user *pu;
172
173 FOR_EACH_PTR(*list, pu) {
174 if (pu->userp == entry) {
175 MARK_CURRENT_DELETED(pu);
176 if (!--count)
177 goto out;
178 }
179 } END_FOR_EACH_PTR(pu);
180 assert(count <= 0);
181 out:
182 if (ptr_list_size((struct ptr_list *) *list) == 0)
183 *list = NULL;
184 return count;
185 }
186
187 static inline void remove_usage(pseudo_t p, pseudo_t *usep)
188 {
189 if (has_use_list(p)) {
190 delete_pseudo_user_list_entry(&p->users, usep, 1);
191 if (!p->users)
192 kill_instruction(p->def);
193 }
194 }
195
196 void kill_use(pseudo_t *usep)
197 {
198 if (usep) {
199 pseudo_t p = *usep;
200 *usep = VOID;
201 remove_usage(p, usep);
202 }
203 }
204
205 static void kill_use_list(struct pseudo_list *list)
206 {
207 pseudo_t p;
208 FOR_EACH_PTR(list, p) {
209 if (p == VOID)
210 continue;
211 kill_use(THIS_ADDRESS(p));
212 } END_FOR_EACH_PTR(p);
213 }
214
215 /*
216 * kill an instruction:
217 * - remove it from its bb
218 * - remove the usage of all its operands
219 * If forse is zero, the normal case, the function only for
220 * instructions free of (possible) side-effects. Otherwise
221 * the function does that unconditionally (must only be used
222 * for unreachable instructions.
223 */
224 void kill_insn(struct instruction *insn, int force)
225 {
226 if (!insn || !insn->bb)
227 return;
228
229 switch (insn->opcode) {
230 case OP_SEL:
231 case OP_RANGE:
232 kill_use(&insn->src3);
233 /* fall through */
234
235 case OP_BINARY ... OP_BINCMP_END:
236 kill_use(&insn->src2);
237 /* fall through */
238
239 case OP_CAST:
240 case OP_SCAST:
241 case OP_FPCAST:
242 case OP_PTRCAST:
243 case OP_SETVAL:
244 case OP_NOT: case OP_NEG:
245 case OP_SLICE:
246 kill_use(&insn->src1);
247 break;
248
249 case OP_PHI:
250 kill_use_list(insn->phi_list);
251 break;
252 case OP_PHISOURCE:
253 kill_use(&insn->phi_src);
254 break;
255
256 case OP_SYMADDR:
257 repeat_phase |= REPEAT_SYMBOL_CLEANUP;
258 break;
259
260 case OP_CBR:
261 case OP_COMPUTEDGOTO:
262 kill_use(&insn->cond);
263 break;
264
265 case OP_CALL:
266 if (!force) {
267 /* a "pure" function can be killed too */
268 if (!(insn->func->type == PSEUDO_SYM))
269 return;
270 if (!(insn->func->sym->ctype.modifiers & MOD_PURE))
271 return;
272 }
273 kill_use_list(insn->arguments);
274 if (insn->func->type == PSEUDO_REG)
275 kill_use(&insn->func);
276 break;
277
278 case OP_LOAD:
279 if (!force && insn->type->ctype.modifiers & MOD_VOLATILE)
280 return;
281 kill_use(&insn->src);
282 break;
283
284 case OP_STORE:
285 if (!force)
286 return;
287 kill_use(&insn->src);
288 kill_use(&insn->target);
289 break;
290
291 case OP_ENTRY:
292 /* ignore */
293 return;
294
295 case OP_BR:
296 default:
297 break;
298 }
299
300 insn->bb = NULL;
301 repeat_phase |= REPEAT_CSE;
302 return;
303 }
304
305 /*
306 * Kill trivially dead instructions
307 */
308 static int dead_insn(struct instruction *insn, pseudo_t *src1, pseudo_t *src2, pseudo_t *src3)
309 {
310 struct pseudo_user *pu;
311 FOR_EACH_PTR(insn->target->users, pu) {
312 if (*pu->userp != VOID)
313 return 0;
314 } END_FOR_EACH_PTR(pu);
315
316 insn->bb = NULL;
317 kill_use(src1);
318 kill_use(src2);
319 kill_use(src3);
320 return REPEAT_CSE;
321 }
322
323 static inline int constant(pseudo_t pseudo)
324 {
325 return pseudo->type == PSEUDO_VAL;
326 }
327
328 static int replace_with_pseudo(struct instruction *insn, pseudo_t pseudo)
329 {
330 convert_instruction_target(insn, pseudo);
331
332 switch (insn->opcode) {
333 case OP_SEL:
334 case OP_RANGE:
335 kill_use(&insn->src3);
336 case OP_BINARY ... OP_BINCMP_END:
337 kill_use(&insn->src2);
338 case OP_NOT:
339 case OP_NEG:
340 case OP_SYMADDR:
341 case OP_CAST:
342 case OP_SCAST:
343 case OP_FPCAST:
344 case OP_PTRCAST:
345 kill_use(&insn->src1);
346 break;
347
348 default:
349 assert(0);
350 }
351 insn->bb = NULL;
352 return REPEAT_CSE;
353 }
354
355 unsigned int value_size(long long value)
356 {
357 value >>= 8;
358 if (!value)
359 return 8;
360 value >>= 8;
361 if (!value)
362 return 16;
363 value >>= 16;
364 if (!value)
365 return 32;
366 return 64;
367 }
368
369 /*
370 * Try to determine the maximum size of bits in a pseudo.
371 *
372 * Right now this only follow casts and constant values, but we
373 * could look at things like logical 'and' instructions etc.
374 */
375 static unsigned int operand_size(struct instruction *insn, pseudo_t pseudo)
376 {
377 unsigned int size = insn->size;
378
379 if (pseudo->type == PSEUDO_REG) {
380 struct instruction *src = pseudo->def;
381 if (src && src->opcode == OP_CAST && src->orig_type) {
382 unsigned int orig_size = src->orig_type->bit_size;
383 if (orig_size < size)
384 size = orig_size;
385 }
386 }
387 if (pseudo->type == PSEUDO_VAL) {
388 unsigned int orig_size = value_size(pseudo->value);
389 if (orig_size < size)
390 size = orig_size;
391 }
392 return size;
393 }
394
395 static int simplify_asr(struct instruction *insn, pseudo_t pseudo, long long value)
396 {
397 unsigned int size = operand_size(insn, pseudo);
398
399 if (value >= size) {
400 warning(insn->pos, "right shift by bigger than source value");
401 return replace_with_pseudo(insn, value_pseudo(insn->type, 0));
402 }
403 if (!value)
404 return replace_with_pseudo(insn, pseudo);
405 return 0;
406 }
407
408 static int simplify_mul_div(struct instruction *insn, long long value)
409 {
410 unsigned long long sbit = 1ULL << (insn->size - 1);
411 unsigned long long bits = sbit | (sbit - 1);
412
413 if (value == 1)
414 return replace_with_pseudo(insn, insn->src1);
415
416 switch (insn->opcode) {
417 case OP_MULS:
418 case OP_MULU:
419 if (value == 0)
420 return replace_with_pseudo(insn, insn->src2);
421 /* Fall through */
422 case OP_DIVS:
423 if (!(value & sbit)) // positive
424 break;
425
426 value |= ~bits;
427 if (value == -1) {
428 insn->opcode = OP_NEG;
429 return REPEAT_CSE;
430 }
431 }
432
433 return 0;
434 }
435
436 static int compare_opcode(int opcode, int inverse)
437 {
438 if (!inverse)
439 return opcode;
440
441 switch (opcode) {
442 case OP_SET_EQ: return OP_SET_NE;
443 case OP_SET_NE: return OP_SET_EQ;
444
445 case OP_SET_LT: return OP_SET_GE;
446 case OP_SET_LE: return OP_SET_GT;
447 case OP_SET_GT: return OP_SET_LE;
448 case OP_SET_GE: return OP_SET_LT;
449
450 case OP_SET_A: return OP_SET_BE;
451 case OP_SET_AE: return OP_SET_B;
452 case OP_SET_B: return OP_SET_AE;
453 case OP_SET_BE: return OP_SET_A;
454
455 default:
456 return opcode;
457 }
458 }
459
460 static int simplify_seteq_setne(struct instruction *insn, long long value)
461 {
462 pseudo_t old = insn->src1;
463 struct instruction *def = old->def;
464 pseudo_t src1, src2;
465 int inverse;
466 int opcode;
467
468 if (value != 0 && value != 1)
469 return 0;
470
471 if (!def)
472 return 0;
473
474 inverse = (insn->opcode == OP_SET_NE) == value;
475 opcode = def->opcode;
476 switch (opcode) {
477 case OP_BINCMP ... OP_BINCMP_END:
478 // Convert:
479 // setcc.n %t <- %a, %b
480 // setne.m %r <- %t, $0
481 // into:
482 // setcc.n %t <- %a, %b
483 // setcc.m %r <- %a, $b
484 // and similar for setne/eq ... 0/1
485 src1 = def->src1;
486 src2 = def->src2;
487 insn->opcode = compare_opcode(opcode, inverse);
488 use_pseudo(insn, src1, &insn->src1);
489 use_pseudo(insn, src2, &insn->src2);
490 remove_usage(old, &insn->src1);
491 return REPEAT_CSE;
492
493 default:
494 return 0;
495 }
496 }
497
498 static int simplify_constant_rightside(struct instruction *insn)
499 {
500 long long value = insn->src2->value;
501
502 switch (insn->opcode) {
503 case OP_OR_BOOL:
504 if (value == 1)
505 return replace_with_pseudo(insn, insn->src2);
506 goto case_neutral_zero;
507
508 case OP_SUB:
509 if (value) {
510 insn->opcode = OP_ADD;
511 insn->src2 = value_pseudo(insn->type, -value);
512 return REPEAT_CSE;
513 }
514 /* Fall through */
515 case OP_ADD:
516 case OP_OR: case OP_XOR:
517 case OP_SHL:
518 case OP_LSR:
519 case_neutral_zero:
520 if (!value)
521 return replace_with_pseudo(insn, insn->src1);
522 return 0;
523 case OP_ASR:
524 return simplify_asr(insn, insn->src1, value);
525
526 case OP_MODU: case OP_MODS:
527 if (value == 1)
528 return replace_with_pseudo(insn, value_pseudo(insn->type, 0));
529 return 0;
530
531 case OP_DIVU: case OP_DIVS:
532 case OP_MULU: case OP_MULS:
533 return simplify_mul_div(insn, value);
534
535 case OP_AND_BOOL:
536 if (value == 1)
537 return replace_with_pseudo(insn, insn->src1);
538 /* Fall through */
539 case OP_AND:
540 if (!value)
541 return replace_with_pseudo(insn, insn->src2);
542 return 0;
543
544 case OP_SET_NE:
545 case OP_SET_EQ:
546 return simplify_seteq_setne(insn, value);
547 }
548 return 0;
549 }
550
551 static int simplify_constant_leftside(struct instruction *insn)
552 {
553 long long value = insn->src1->value;
554
555 switch (insn->opcode) {
556 case OP_ADD: case OP_OR: case OP_XOR:
557 if (!value)
558 return replace_with_pseudo(insn, insn->src2);
559 return 0;
560
561 case OP_SHL:
562 case OP_LSR: case OP_ASR:
563 case OP_AND:
564 case OP_MULU: case OP_MULS:
565 if (!value)
566 return replace_with_pseudo(insn, insn->src1);
567 return 0;
568 }
569 return 0;
570 }
571
572 static int simplify_constant_binop(struct instruction *insn)
573 {
574 /* FIXME! Verify signs and sizes!! */
575 long long left = insn->src1->value;
576 long long right = insn->src2->value;
577 unsigned long long ul, ur;
578 long long res, mask, bits;
579
580 mask = 1ULL << (insn->size-1);
581 bits = mask | (mask-1);
582
583 if (left & mask)
584 left |= ~bits;
585 if (right & mask)
586 right |= ~bits;
587 ul = left & bits;
588 ur = right & bits;
589
590 switch (insn->opcode) {
591 case OP_ADD:
592 res = left + right;
593 break;
594 case OP_SUB:
595 res = left - right;
596 break;
597 case OP_MULU:
598 res = ul * ur;
599 break;
600 case OP_MULS:
601 res = left * right;
602 break;
603 case OP_DIVU:
604 if (!ur)
605 return 0;
606 res = ul / ur;
607 break;
608 case OP_DIVS:
609 if (!right)
610 return 0;
611 if (left == mask && right == -1)
612 return 0;
613 res = left / right;
614 break;
615 case OP_MODU:
616 if (!ur)
617 return 0;
618 res = ul % ur;
619 break;
620 case OP_MODS:
621 if (!right)
622 return 0;
623 if (left == mask && right == -1)
624 return 0;
625 res = left % right;
626 break;
627 case OP_SHL:
628 res = left << right;
629 break;
630 case OP_LSR:
631 res = ul >> ur;
632 break;
633 case OP_ASR:
634 res = left >> right;
635 break;
636 /* Logical */
637 case OP_AND:
638 res = left & right;
639 break;
640 case OP_OR:
641 res = left | right;
642 break;
643 case OP_XOR:
644 res = left ^ right;
645 break;
646 case OP_AND_BOOL:
647 res = left && right;
648 break;
649 case OP_OR_BOOL:
650 res = left || right;
651 break;
652
653 /* Binary comparison */
654 case OP_SET_EQ:
655 res = left == right;
656 break;
657 case OP_SET_NE:
658 res = left != right;
659 break;
660 case OP_SET_LE:
661 res = left <= right;
662 break;
663 case OP_SET_GE:
664 res = left >= right;
665 break;
666 case OP_SET_LT:
667 res = left < right;
668 break;
669 case OP_SET_GT:
670 res = left > right;
671 break;
672 case OP_SET_B:
673 res = ul < ur;
674 break;
675 case OP_SET_A:
676 res = ul > ur;
677 break;
678 case OP_SET_BE:
679 res = ul <= ur;
680 break;
681 case OP_SET_AE:
682 res = ul >= ur;
683 break;
684 default:
685 return 0;
686 }
687 res &= bits;
688
689 replace_with_pseudo(insn, value_pseudo(insn->type, res));
690 return REPEAT_CSE;
691 }
692
693 static int simplify_binop_same_args(struct instruction *insn, pseudo_t arg)
694 {
695 switch (insn->opcode) {
696 case OP_SET_NE:
697 case OP_SET_LT: case OP_SET_GT:
698 case OP_SET_B: case OP_SET_A:
699 if (Wtautological_compare)
700 warning(insn->pos, "self-comparison always evaluates to false");
701 case OP_SUB:
702 case OP_XOR:
703 return replace_with_pseudo(insn, value_pseudo(insn->type, 0));
704
705 case OP_SET_EQ:
706 case OP_SET_LE: case OP_SET_GE:
707 case OP_SET_BE: case OP_SET_AE:
708 if (Wtautological_compare)
709 warning(insn->pos, "self-comparison always evaluates to true");
710 return replace_with_pseudo(insn, value_pseudo(insn->type, 1));
711
712 case OP_AND:
713 case OP_OR:
714 return replace_with_pseudo(insn, arg);
715
716 case OP_AND_BOOL:
717 case OP_OR_BOOL:
718 remove_usage(arg, &insn->src2);
719 insn->src2 = value_pseudo(insn->type, 0);
720 insn->opcode = OP_SET_NE;
721 return REPEAT_CSE;
722
723 default:
724 break;
725 }
726
727 return 0;
728 }
729
730 static int simplify_binop(struct instruction *insn)
731 {
732 if (dead_insn(insn, &insn->src1, &insn->src2, NULL))
733 return REPEAT_CSE;
734 if (constant(insn->src1)) {
735 if (constant(insn->src2))
736 return simplify_constant_binop(insn);
737 return simplify_constant_leftside(insn);
738 }
739 if (constant(insn->src2))
740 return simplify_constant_rightside(insn);
741 if (insn->src1 == insn->src2)
742 return simplify_binop_same_args(insn, insn->src1);
743 return 0;
744 }
745
746 static void switch_pseudo(struct instruction *insn1, pseudo_t *pp1, struct instruction *insn2, pseudo_t *pp2)
747 {
748 pseudo_t p1 = *pp1, p2 = *pp2;
749
750 use_pseudo(insn1, p2, pp1);
751 use_pseudo(insn2, p1, pp2);
752 remove_usage(p1, pp1);
753 remove_usage(p2, pp2);
754 }
755
756 static int canonical_order(pseudo_t p1, pseudo_t p2)
757 {
758 /* symbol/constants on the right */
759 if (p1->type == PSEUDO_VAL)
760 return p2->type == PSEUDO_VAL;
761
762 if (p1->type == PSEUDO_SYM)
763 return p2->type == PSEUDO_SYM || p2->type == PSEUDO_VAL;
764
765 return 1;
766 }
767
768 static int simplify_commutative_binop(struct instruction *insn)
769 {
770 if (!canonical_order(insn->src1, insn->src2)) {
771 switch_pseudo(insn, &insn->src1, insn, &insn->src2);
772 return REPEAT_CSE;
773 }
774 return 0;
775 }
776
777 static inline int simple_pseudo(pseudo_t pseudo)
778 {
779 return pseudo->type == PSEUDO_VAL || pseudo->type == PSEUDO_SYM;
780 }
781
782 static int simplify_associative_binop(struct instruction *insn)
783 {
784 struct instruction *def;
785 pseudo_t pseudo = insn->src1;
786
787 if (!simple_pseudo(insn->src2))
788 return 0;
789 if (pseudo->type != PSEUDO_REG)
790 return 0;
791 def = pseudo->def;
792 if (def == insn)
793 return 0;
794 if (def->opcode != insn->opcode)
795 return 0;
796 if (!simple_pseudo(def->src2))
797 return 0;
798 if (ptr_list_size((struct ptr_list *)def->target->users) != 1)
799 return 0;
800 switch_pseudo(def, &def->src1, insn, &insn->src2);
801 return REPEAT_CSE;
802 }
803
804 static int simplify_constant_unop(struct instruction *insn)
805 {
806 long long val = insn->src1->value;
807 long long res, mask;
808
809 switch (insn->opcode) {
810 case OP_NOT:
811 res = ~val;
812 break;
813 case OP_NEG:
814 res = -val;
815 break;
816 default:
817 return 0;
818 }
819 mask = 1ULL << (insn->size-1);
820 res &= mask | (mask-1);
821
822 replace_with_pseudo(insn, value_pseudo(insn->type, res));
823 return REPEAT_CSE;
824 }
825
826 static int simplify_unop(struct instruction *insn)
827 {
828 if (dead_insn(insn, &insn->src1, NULL, NULL))
829 return REPEAT_CSE;
830 if (constant(insn->src1))
831 return simplify_constant_unop(insn);
832
833 switch (insn->opcode) {
834 struct instruction *def;
835
836 case OP_NOT:
837 def = insn->src->def;
838 if (def && def->opcode == OP_NOT)
839 return replace_with_pseudo(insn, def->src);
840 break;
841 case OP_NEG:
842 def = insn->src->def;
843 if (def && def->opcode == OP_NEG)
844 return replace_with_pseudo(insn, def->src);
845 break;
846 default:
847 return 0;
848 }
849 return 0;
850 }
851
852 static int simplify_one_memop(struct instruction *insn, pseudo_t orig)
853 {
854 pseudo_t addr = insn->src;
855 pseudo_t new, off;
856
857 if (addr->type == PSEUDO_REG) {
858 struct instruction *def = addr->def;
859 if (def->opcode == OP_SYMADDR && def->src) {
860 kill_use(&insn->src);
861 use_pseudo(insn, def->src, &insn->src);
862 return REPEAT_CSE | REPEAT_SYMBOL_CLEANUP;
863 }
864 if (def->opcode == OP_ADD) {
865 new = def->src1;
866 off = def->src2;
867 if (constant(off))
868 goto offset;
869 new = off;
870 off = def->src1;
871 if (constant(off))
872 goto offset;
873 return 0;
874 }
875 }
876 return 0;
877
878 offset:
879 /* Invalid code */
880 if (new == orig) {
881 if (new == VOID)
882 return 0;
883 /*
884 * If some BB have been removed it is possible that this
885 * memop is in fact part of a dead BB. In this case
886 * we must not warn since nothing is wrong.
887 * If not part of a dead BB this will be redone after
888 * the BBs have been cleaned up.
889 */
890 if (repeat_phase & REPEAT_CFG_CLEANUP)
891 return 0;
892 new = VOID;
893 warning(insn->pos, "crazy programmer");
894 }
895 insn->offset += off->value;
896 use_pseudo(insn, new, &insn->src);
897 remove_usage(addr, &insn->src);
898 return REPEAT_CSE | REPEAT_SYMBOL_CLEANUP;
899 }
900
901 /*
902 * We walk the whole chain of adds/subs backwards. That's not
903 * only more efficient, but it allows us to find loops.
904 */
905 static int simplify_memop(struct instruction *insn)
906 {
907 int one, ret = 0;
908 pseudo_t orig = insn->src;
909
910 do {
911 one = simplify_one_memop(insn, orig);
912 ret |= one;
913 } while (one);
914 return ret;
915 }
916
917 static long long get_cast_value(long long val, int old_size, int new_size, int sign)
918 {
919 long long mask;
920
921 if (sign && new_size > old_size) {
922 mask = 1 << (old_size-1);
923 if (val & mask)
924 val |= ~(mask | (mask-1));
925 }
926 mask = 1 << (new_size-1);
927 return val & (mask | (mask-1));
928 }
929
930 static int simplify_cast(struct instruction *insn)
931 {
932 struct symbol *orig_type;
933 int orig_size, size;
934 pseudo_t src;
935
936 if (dead_insn(insn, &insn->src, NULL, NULL))
937 return REPEAT_CSE;
938
939 orig_type = insn->orig_type;
940 if (!orig_type)
941 return 0;
942
943 /* Keep casts with pointer on either side (not only case of OP_PTRCAST) */
944 if (is_ptr_type(orig_type) || is_ptr_type(insn->type))
945 return 0;
946
947 orig_size = orig_type->bit_size;
948 size = insn->size;
949 src = insn->src;
950
951 /* A cast of a constant? */
952 if (constant(src)) {
953 int sign = orig_type->ctype.modifiers & MOD_SIGNED;
954 long long val = get_cast_value(src->value, orig_size, size, sign);
955 src = value_pseudo(orig_type, val);
956 goto simplify;
957 }
958
959 /* A cast of a "and" might be a no-op.. */
960 if (src->type == PSEUDO_REG) {
961 struct instruction *def = src->def;
962 if (def->opcode == OP_AND && def->size >= size) {
963 pseudo_t val = def->src2;
964 if (val->type == PSEUDO_VAL) {
965 unsigned long long value = val->value;
966 if (!(value >> (size-1)))
967 goto simplify;
968 }
969 }
970 }
971
972 if (size == orig_size) {
973 int op = (orig_type->ctype.modifiers & MOD_SIGNED) ? OP_SCAST : OP_CAST;
974 if (insn->opcode == op)
975 goto simplify;
976 if (insn->opcode == OP_FPCAST && is_float_type(orig_type))
977 goto simplify;
978 }
979
980 return 0;
981
982 simplify:
983 return replace_with_pseudo(insn, src);
984 }
985
986 static int simplify_select(struct instruction *insn)
987 {
988 pseudo_t cond, src1, src2;
989
990 if (dead_insn(insn, &insn->src1, &insn->src2, &insn->src3))
991 return REPEAT_CSE;
992
993 cond = insn->src1;
994 src1 = insn->src2;
995 src2 = insn->src3;
996 if (constant(cond) || src1 == src2) {
997 pseudo_t *kill, take;
998 kill_use(&insn->src1);
999 take = cond->value ? src1 : src2;
1000 kill = cond->value ? &insn->src3 : &insn->src2;
1001 kill_use(kill);
1002 replace_with_pseudo(insn, take);
1003 return REPEAT_CSE;
1004 }
1005 if (constant(src1) && constant(src2)) {
1006 long long val1 = src1->value;
1007 long long val2 = src2->value;
1008
1009 /* The pair 0/1 is special - replace with SETNE/SETEQ */
1010 if ((val1 | val2) == 1) {
1011 int opcode = OP_SET_EQ;
1012 if (val1) {
1013 src1 = src2;
1014 opcode = OP_SET_NE;
1015 }
1016 insn->opcode = opcode;
1017 /* insn->src1 is already cond */
1018 insn->src2 = src1; /* Zero */
1019 return REPEAT_CSE;
1020 }
1021 }
1022 return 0;
1023 }
1024
1025 static int is_in_range(pseudo_t src, long long low, long long high)
1026 {
1027 long long value;
1028
1029 switch (src->type) {
1030 case PSEUDO_VAL:
1031 value = src->value;
1032 return value >= low && value <= high;
1033 default:
1034 return 0;
1035 }
1036 }
1037
1038 static int simplify_range(struct instruction *insn)
1039 {
1040 pseudo_t src1, src2, src3;
1041
1042 src1 = insn->src1;
1043 src2 = insn->src2;
1044 src3 = insn->src3;
1045 if (src2->type != PSEUDO_VAL || src3->type != PSEUDO_VAL)
1046 return 0;
1047 if (is_in_range(src1, src2->value, src3->value)) {
1048 kill_instruction(insn);
1049 return REPEAT_CSE;
1050 }
1051 return 0;
1052 }
1053
1054 /*
1055 * Simplify "set_ne/eq $0 + br"
1056 */
1057 static int simplify_cond_branch(struct instruction *br, pseudo_t cond, struct instruction *def, pseudo_t *pp)
1058 {
1059 use_pseudo(br, *pp, &br->cond);
1060 remove_usage(cond, &br->cond);
1061 if (def->opcode == OP_SET_EQ) {
1062 struct basic_block *true = br->bb_true;
1063 struct basic_block *false = br->bb_false;
1064 br->bb_false = true;
1065 br->bb_true = false;
1066 }
1067 return REPEAT_CSE;
1068 }
1069
1070 static int simplify_branch(struct instruction *insn)
1071 {
1072 pseudo_t cond = insn->cond;
1073
1074 /* Constant conditional */
1075 if (constant(cond)) {
1076 insert_branch(insn->bb, insn, cond->value ? insn->bb_true : insn->bb_false);
1077 return REPEAT_CSE;
1078 }
1079
1080 /* Same target? */
1081 if (insn->bb_true == insn->bb_false) {
1082 struct basic_block *bb = insn->bb;
1083 struct basic_block *target = insn->bb_false;
1084 remove_bb_from_list(&target->parents, bb, 1);
1085 remove_bb_from_list(&bb->children, target, 1);
1086 insn->bb_false = NULL;
1087 kill_use(&insn->cond);
1088 insn->cond = NULL;
1089 insn->opcode = OP_BR;
1090 return REPEAT_CSE;
1091 }
1092
1093 /* Conditional on a SETNE $0 or SETEQ $0 */
1094 if (cond->type == PSEUDO_REG) {
1095 struct instruction *def = cond->def;
1096
1097 if (def->opcode == OP_SET_NE || def->opcode == OP_SET_EQ) {
1098 if (constant(def->src1) && !def->src1->value)
1099 return simplify_cond_branch(insn, cond, def, &def->src2);
1100 if (constant(def->src2) && !def->src2->value)
1101 return simplify_cond_branch(insn, cond, def, &def->src1);
1102 }
1103 if (def->opcode == OP_SEL) {
1104 if (constant(def->src2) && constant(def->src3)) {
1105 long long val1 = def->src2->value;
1106 long long val2 = def->src3->value;
1107 if (!val1 && !val2) {
1108 insert_branch(insn->bb, insn, insn->bb_false);
1109 return REPEAT_CSE;
1110 }
1111 if (val1 && val2) {
1112 insert_branch(insn->bb, insn, insn->bb_true);
1113 return REPEAT_CSE;
1114 }
1115 if (val2) {
1116 struct basic_block *true = insn->bb_true;
1117 struct basic_block *false = insn->bb_false;
1118 insn->bb_false = true;
1119 insn->bb_true = false;
1120 }
1121 use_pseudo(insn, def->src1, &insn->cond);
1122 remove_usage(cond, &insn->cond);
1123 return REPEAT_CSE;
1124 }
1125 }
1126 if (def->opcode == OP_CAST || def->opcode == OP_SCAST) {
1127 int orig_size = def->orig_type ? def->orig_type->bit_size : 0;
1128 if (def->size > orig_size) {
1129 use_pseudo(insn, def->src, &insn->cond);
1130 remove_usage(cond, &insn->cond);
1131 return REPEAT_CSE;
1132 }
1133 }
1134 }
1135 return 0;
1136 }
1137
1138 static int simplify_switch(struct instruction *insn)
1139 {
1140 pseudo_t cond = insn->cond;
1141 long long val;
1142 struct multijmp *jmp;
1143
1144 if (!constant(cond))
1145 return 0;
1146 val = insn->cond->value;
1147
1148 FOR_EACH_PTR(insn->multijmp_list, jmp) {
1149 /* Default case */
1150 if (jmp->begin > jmp->end)
1151 goto found;
1152 if (val >= jmp->begin && val <= jmp->end)
1153 goto found;
1154 } END_FOR_EACH_PTR(jmp);
1155 warning(insn->pos, "Impossible case statement");
1156 return 0;
1157
1158 found:
1159 insert_branch(insn->bb, insn, jmp->target);
1160 return REPEAT_CSE;
1161 }
1162
1163 int simplify_instruction(struct instruction *insn)
1164 {
1165 if (!insn->bb)
1166 return 0;
1167 switch (insn->opcode) {
1168 case OP_ADD: case OP_MULS:
1169 case OP_AND: case OP_OR: case OP_XOR:
1170 case OP_AND_BOOL: case OP_OR_BOOL:
1171 if (simplify_binop(insn))
1172 return REPEAT_CSE;
1173 if (simplify_commutative_binop(insn))
1174 return REPEAT_CSE;
1175 return simplify_associative_binop(insn);
1176
1177 case OP_MULU:
1178 case OP_SET_EQ: case OP_SET_NE:
1179 if (simplify_binop(insn))
1180 return REPEAT_CSE;
1181 return simplify_commutative_binop(insn);
1182
1183 case OP_SUB:
1184 case OP_DIVU: case OP_DIVS:
1185 case OP_MODU: case OP_MODS:
1186 case OP_SHL:
1187 case OP_LSR: case OP_ASR:
1188 case OP_SET_LE: case OP_SET_GE:
1189 case OP_SET_LT: case OP_SET_GT:
1190 case OP_SET_B: case OP_SET_A:
1191 case OP_SET_BE: case OP_SET_AE:
1192 return simplify_binop(insn);
1193
1194 case OP_NOT: case OP_NEG:
1195 return simplify_unop(insn);
1196 case OP_LOAD: case OP_STORE:
1197 return simplify_memop(insn);
1198 case OP_SYMADDR:
1199 if (dead_insn(insn, NULL, NULL, NULL))
1200 return REPEAT_CSE | REPEAT_SYMBOL_CLEANUP;
1201 return replace_with_pseudo(insn, insn->symbol);
1202 case OP_CAST:
1203 case OP_SCAST:
1204 case OP_FPCAST:
1205 case OP_PTRCAST:
1206 return simplify_cast(insn);
1207 case OP_PHI:
1208 if (dead_insn(insn, NULL, NULL, NULL)) {
1209 kill_use_list(insn->phi_list);
1210 return REPEAT_CSE;
1211 }
1212 return clean_up_phi(insn);
1213 case OP_PHISOURCE:
1214 if (dead_insn(insn, &insn->phi_src, NULL, NULL))
1215 return REPEAT_CSE;
1216 break;
1217 case OP_SEL:
1218 return simplify_select(insn);
1219 case OP_CBR:
1220 return simplify_branch(insn);
1221 case OP_SWITCH:
1222 return simplify_switch(insn);
1223 case OP_RANGE:
1224 return simplify_range(insn);
1225 }
1226 return 0;
1227 }