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 *
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);
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;
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 }
|
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 "flow.h"
48 #include "symbol.h"
49
50 ///
51 // Utilities
52 // ^^^^^^^^^
53
54 ///
55 // find the trivial parent for a phi-source
56 static struct basic_block *phi_parent(struct basic_block *source, pseudo_t pseudo)
57 {
58 /* Can't go upwards if the pseudo is defined in the bb it came from.. */
59 if (pseudo->type == PSEUDO_REG) {
60 struct instruction *def = pseudo->def;
61 if (def->bb == source)
62 return source;
63 }
64 if (bb_list_size(source->children) != 1 || bb_list_size(source->parents) != 1)
65 return source;
66 return first_basic_block(source->parents);
67 }
68
69 ///
70 // copy the phi-node's phisrcs into to given array
71 // @return: 0 if the the list contained the expected
72 // number of element, a positive number if there was
73 // more than expected and a negative one if less.
74 //
75 // :note: we can't reuse a function like linearize_ptr_list()
76 // because any VOIDs in the phi-list must be ignored here
77 // as in this context they mean 'entry has been removed'.
78 static int get_phisources(struct instruction *sources[], int nbr, struct instruction *insn)
79 {
80 pseudo_t phi;
81 int i = 0;
82
83 assert(insn->opcode == OP_PHI);
84 FOR_EACH_PTR(insn->phi_list, phi) {
85 struct instruction *def;
86 if (phi == VOID)
87 continue;
88 if (i >= nbr)
89 return 1;
90 def = phi->def;
91 assert(def->opcode == OP_PHISOURCE);
92 sources[i++] = def;
93 } END_FOR_EACH_PTR(phi);
94 return i - nbr;
95 }
96
97 static int if_convert_phi(struct instruction *insn)
98 {
99 struct instruction *array[2];
100 struct basic_block *parents[3];
101 struct basic_block *bb, *bb1, *bb2, *source;
102 struct instruction *br;
103 pseudo_t p1, p2;
104
105 bb = insn->bb;
106 if (get_phisources(array, 2, insn))
107 return 0;
108 if (linearize_ptr_list((struct ptr_list *)bb->parents, (void **)parents, 3) != 2)
109 return 0;
110 p1 = array[0]->phi_src;
111 bb1 = array[0]->bb;
112 p2 = array[1]->phi_src;
113 bb2 = array[1]->bb;
114
115 /* Only try the simple "direct parents" case */
116 if ((bb1 != parents[0] || bb2 != parents[1]) &&
117 (bb1 != parents[1] || bb2 != parents[0]))
118 return 0;
119
120 /*
121 * See if we can find a common source for this..
122 */
123 source = phi_parent(bb1, p1);
124 if (source != phi_parent(bb2, p2))
125 return 0;
126
127 /*
128 * Cool. We now know that 'source' is the exclusive
129 * parent of both phi-nodes, so the exit at the
130 * end of it fully determines which one it is, and
131 * we can turn it into a select.
132 *
155 *
156 * br cond, a, b
157 *
158 * with the sequence
159 *
160 * setcc cond
161 * select pseudo, p1, p2
162 * br cond, a, b
163 *
164 * and remove the phi-node. If it then
165 * turns out that 'a' or 'b' is entirely
166 * empty (common case), and now no longer
167 * a phi-source, we'll be able to simplify
168 * the conditional branch too.
169 */
170 insert_select(source, br, insn, p1, p2);
171 kill_instruction(insn);
172 return REPEAT_CSE;
173 }
174
175 ///
176 // detect trivial phi-nodes
177 // @insn: the phi-node
178 // @pseudo: the candidate resulting pseudo (NULL when starting)
179 // @return: the unique result if the phi-node is trivial, NULL otherwise
180 //
181 // A phi-node is trivial if it has a single possible result:
182 // * all operands are the same
183 // * the operands are themselves defined by a chain or cycle of phi-nodes
184 // and the set of all operands involved contains a single value
185 // not defined by these phi-nodes
186 //
187 // Since the result is unique, these phi-nodes can be removed.
188 static pseudo_t trivial_phi(pseudo_t pseudo, struct instruction *insn, struct pseudo_list **list)
189 {
190 pseudo_t target = insn->target;
191 pseudo_t phi;
192
193 add_pseudo(list, target);
194
195 FOR_EACH_PTR(insn->phi_list, phi) {
196 struct instruction *def;
197 pseudo_t src;
198
199 if (phi == VOID)
200 continue;
201 def = phi->def;
202 if (!def->bb)
203 continue;
204 src = def->phi_src; // bypass OP_PHISRC & get the real source
205 if (src == VOID)
206 continue;
207 if (!pseudo) {
208 pseudo = src;
209 continue;
210 }
211 if (src == pseudo)
212 continue;
213 if (src == target)
214 continue;
215 if (DEF_OPCODE(def, src) == OP_PHI) {
216 if (pseudo_in_list(*list, src))
217 continue;
218 if ((pseudo = trivial_phi(pseudo, def, list)))
219 continue;
220 }
221 return NULL;
222 } END_FOR_EACH_PTR(phi);
223
224 return pseudo ? pseudo : VOID;
225 }
226
227 static int clean_up_phi(struct instruction *insn)
228 {
229 struct pseudo_list *list = NULL;
230 pseudo_t pseudo;
231
232 if ((pseudo = trivial_phi(NULL, insn, &list))) {
233 convert_instruction_target(insn, pseudo);
234 kill_instruction(insn);
235 return REPEAT_CSE;
236 }
237
238 return if_convert_phi(insn);
239 }
240
241 static int delete_pseudo_user_list_entry(struct pseudo_user_list **list, pseudo_t *entry, int count)
242 {
243 struct pseudo_user *pu;
244
245 FOR_EACH_PTR(*list, pu) {
246 if (pu->userp == entry) {
247 MARK_CURRENT_DELETED(pu);
248 if (!--count)
249 goto out;
250 }
251 } END_FOR_EACH_PTR(pu);
252 assert(count <= 0);
253 out:
254 if (pseudo_user_list_empty(*list))
255 *list = NULL;
256 return count;
257 }
258
259 static inline void rem_usage(pseudo_t p, pseudo_t *usep, int kill)
260 {
261 if (has_use_list(p)) {
262 if (p->type == PSEUDO_SYM)
263 repeat_phase |= REPEAT_SYMBOL_CLEANUP;
264 delete_pseudo_user_list_entry(&p->users, usep, 1);
265 if (kill && !p->users)
266 kill_instruction(p->def);
267 }
268 }
269
270 static inline void remove_usage(pseudo_t p, pseudo_t *usep)
271 {
272 rem_usage(p, usep, 1);
273 }
274
275 void kill_use(pseudo_t *usep)
276 {
277 if (usep) {
278 pseudo_t p = *usep;
279 *usep = VOID;
280 rem_usage(p, usep, 1);
281 }
282 }
283
284 // Like kill_use() but do not (recursively) kill dead instructions
285 void remove_use(pseudo_t *usep)
286 {
287 pseudo_t p = *usep;
288 *usep = VOID;
289 rem_usage(p, usep, 0);
290 }
291
292 static void kill_use_list(struct pseudo_list *list)
293 {
294 pseudo_t p;
295 FOR_EACH_PTR(list, p) {
296 if (p == VOID)
297 continue;
298 kill_use(THIS_ADDRESS(p));
299 } END_FOR_EACH_PTR(p);
300 }
301
302 ///
303 // kill an instruction
304 // @insn: the instruction to be killed
305 // @force: if unset, the normal case, the instruction is not killed
306 // if not free of possible side-effect; if set the instruction
307 // is unconditionally killed.
308 //
309 // The killed instruction is removed from its BB and the usage
310 // of all its operands are removed. The instruction is also
311 // marked as killed by setting its ->bb to NULL.
312 int kill_insn(struct instruction *insn, int force)
313 {
314 if (!insn || !insn->bb)
315 return 0;
316
317 switch (insn->opcode) {
318 case OP_SEL:
319 case OP_RANGE:
320 kill_use(&insn->src3);
321 /* fall through */
322
323 case OP_BINARY ... OP_BINCMP_END:
324 kill_use(&insn->src2);
325 /* fall through */
326
327 case OP_UNOP ... OP_UNOP_END:
328 case OP_SETVAL:
329 case OP_SLICE:
330 kill_use(&insn->src1);
331 break;
332
333 case OP_PHI:
334 kill_use_list(insn->phi_list);
335 break;
336 case OP_PHISOURCE:
337 kill_use(&insn->phi_src);
338 break;
339
340 case OP_SYMADDR:
341 kill_use(&insn->src);
342 repeat_phase |= REPEAT_SYMBOL_CLEANUP;
343 break;
344
345 case OP_CBR:
346 case OP_SWITCH:
347 case OP_COMPUTEDGOTO:
348 kill_use(&insn->cond);
349 break;
350
351 case OP_CALL:
352 if (!force) {
353 /* a "pure" function can be killed too */
354 if (!(insn->func->type == PSEUDO_SYM))
355 return 0;
356 if (!(insn->func->sym->ctype.modifiers & MOD_PURE))
357 return 0;
358 }
359 kill_use_list(insn->arguments);
360 if (insn->func->type == PSEUDO_REG)
361 kill_use(&insn->func);
362 break;
363
364 case OP_LOAD:
365 if (!force && insn->is_volatile)
366 return 0;
367 kill_use(&insn->src);
368 break;
369
370 case OP_STORE:
371 if (!force)
372 return 0;
373 kill_use(&insn->src);
374 kill_use(&insn->target);
375 break;
376
377 case OP_ENTRY:
378 /* ignore */
379 return 0;
380
381 case OP_BR:
382 case OP_SETFVAL:
383 default:
384 break;
385 }
386
387 insn->bb = NULL;
388 return repeat_phase |= REPEAT_CSE;
389 }
390
391 ///
392 // kill trivially dead instructions
393 static int dead_insn(struct instruction *insn, pseudo_t *src1, pseudo_t *src2, pseudo_t *src3)
394 {
395 if (has_users(insn->target))
396 return 0;
397
398 insn->bb = NULL;
399 kill_use(src1);
400 kill_use(src2);
401 kill_use(src3);
402 return REPEAT_CSE;
403 }
404
405 static inline bool has_target(struct instruction *insn)
406 {
407 return opcode_table[insn->opcode].flags & OPF_TARGET;
408 }
409
410 void remove_dead_insns(struct entrypoint *ep)
411 {
412 struct basic_block *bb;
413
414 FOR_EACH_PTR_REVERSE(ep->bbs, bb) {
415 struct instruction *insn;
416 FOR_EACH_PTR_REVERSE(bb->insns, insn) {
417 if (!insn->bb)
418 continue;
419 if (!has_target(insn))
420 continue;
421 if (!has_users(insn->target))
422 kill_instruction(insn);
423 } END_FOR_EACH_PTR_REVERSE(insn);
424 } END_FOR_EACH_PTR_REVERSE(bb);
425 }
426
427 static inline int constant(pseudo_t pseudo)
428 {
429 return pseudo->type == PSEUDO_VAL;
430 }
431
432 ///
433 // replace the operand of an instruction
434 // @insn: the instruction
435 // @pp: the address of the instruction's operand
436 // @new: the new value for the operand
437 // @return: REPEAT_CSE.
438 static inline int replace_pseudo(struct instruction *insn, pseudo_t *pp, pseudo_t new)
439 {
440 pseudo_t old = *pp;
441 use_pseudo(insn, new, pp);
442 remove_usage(old, pp);
443 return REPEAT_CSE;
444 }
445
446 static int replace_with_pseudo(struct instruction *insn, pseudo_t pseudo)
447 {
448 convert_instruction_target(insn, pseudo);
449
450 switch (insn->opcode) {
451 case OP_SEL:
452 case OP_RANGE:
453 kill_use(&insn->src3);
454 case OP_BINARY ... OP_BINCMP_END:
455 kill_use(&insn->src2);
456 case OP_UNOP ... OP_UNOP_END:
457 case OP_SYMADDR:
458 kill_use(&insn->src1);
459 break;
460
461 default:
462 assert(0);
463 }
464 insn->bb = NULL;
465 return REPEAT_CSE;
466 }
467
468 static inline int def_opcode(pseudo_t p)
469 {
470 if (p->type != PSEUDO_REG)
471 return OP_BADOP;
472 return p->def->opcode;
473 }
474
475 static unsigned int value_size(long long value)
476 {
477 value >>= 8;
478 if (!value)
479 return 8;
480 value >>= 8;
481 if (!value)
482 return 16;
483 value >>= 16;
484 if (!value)
485 return 32;
486 return 64;
487 }
488
489 ///
490 // try to determine the maximum size of bits in a pseudo
491 //
492 // Right now this only follow casts and constant values, but we
493 // could look at things like AND instructions, etc.
494 static unsigned int operand_size(struct instruction *insn, pseudo_t pseudo)
495 {
496 unsigned int size = insn->size;
497
498 if (pseudo->type == PSEUDO_REG) {
499 struct instruction *src = pseudo->def;
500 if (src && src->opcode == OP_ZEXT && src->orig_type) {
501 unsigned int orig_size = src->orig_type->bit_size;
502 if (orig_size < size)
503 size = orig_size;
504 }
505 }
506 if (pseudo->type == PSEUDO_VAL) {
507 unsigned int orig_size = value_size(pseudo->value);
508 if (orig_size < size)
509 size = orig_size;
510 }
511 return size;
512 }
513
514 static pseudo_t eval_insn(struct instruction *insn)
515 {
516 /* FIXME! Verify signs and sizes!! */
517 unsigned int size = insn->size;
518 long long left = insn->src1->value;
519 long long right = insn->src2->value;
520 unsigned long long ul, ur;
521 long long res, mask, bits;
522
523 mask = 1ULL << (size-1);
524 bits = mask | (mask-1);
525
526 if (left & mask)
527 left |= ~bits;
528 if (right & mask)
529 right |= ~bits;
530 ul = left & bits;
531 ur = right & bits;
532
533 switch (insn->opcode) {
534 case OP_ADD:
535 res = left + right;
536 break;
537 case OP_SUB:
538 res = left - right;
539 break;
540 case OP_MUL:
541 res = ul * ur;
542 break;
543 case OP_DIVU:
544 if (!ur)
545 goto undef;
546 res = ul / ur;
547 break;
548 case OP_DIVS:
549 if (!right)
550 goto undef;
551 if (left == mask && right == -1)
552 goto undef;
553 res = left / right;
554 break;
555 case OP_MODU:
556 if (!ur)
557 goto undef;
558 res = ul % ur;
559 break;
560 case OP_MODS:
561 if (!right)
562 goto undef;
563 if (left == mask && right == -1)
564 goto undef;
565 res = left % right;
566 break;
567 case OP_SHL:
568 if (ur >= size)
569 goto undef;
570 res = left << right;
571 break;
572 case OP_LSR:
573 if (ur >= size)
574 goto undef;
575 res = ul >> ur;
576 break;
577 case OP_ASR:
578 if (ur >= size)
579 goto undef;
580 res = left >> right;
581 break;
582 /* Logical */
583 case OP_AND:
584 res = left & right;
585 break;
586 case OP_OR:
587 res = left | right;
588 break;
589 case OP_XOR:
590 res = left ^ right;
591 break;
592
593 /* Binary comparison */
594 case OP_SET_EQ:
595 res = left == right;
596 break;
597 case OP_SET_NE:
598 res = left != right;
599 break;
600 case OP_SET_LE:
601 res = left <= right;
602 break;
603 case OP_SET_GE:
604 res = left >= right;
605 break;
606 case OP_SET_LT:
607 res = left < right;
608 break;
609 case OP_SET_GT:
610 res = left > right;
611 break;
612 case OP_SET_B:
613 res = ul < ur;
614 break;
615 case OP_SET_A:
616 res = ul > ur;
617 break;
618 case OP_SET_BE:
619 res = ul <= ur;
620 break;
621 case OP_SET_AE:
622 res = ul >= ur;
623 break;
624 default:
625 return NULL;
626 }
627 res &= bits;
628
629 return value_pseudo(res);
630
631 undef:
632 return NULL;
633 }
634
635 ///
636 // Simplifications
637 // ^^^^^^^^^^^^^^^
638
639 ///
640 // try to simplify MASK(OR(AND(x, M'), b), M)
641 // @insn: the masking instruction
642 // @mask: the associated mask (M)
643 // @ora: one of the OR's operands, guaranteed to be PSEUDO_REG
644 // @orb: the other OR's operand
645 // @return: 0 if no changes have been made, one or more REPEAT_* flags otherwise.
646 static int simplify_mask_or_and(struct instruction *insn, unsigned long long mask,
647 pseudo_t ora, pseudo_t orb)
648 {
649 unsigned long long omask, nmask;
650 struct instruction *and = ora->def;
651 pseudo_t src2 = and->src2;
652
653 if (and->opcode != OP_AND)
654 return 0;
655 if (!constant(src2))
656 return 0;
657 omask = src2->value;
658 nmask = omask & mask;
659 if (nmask == 0) {
660 // if (M' & M) == 0: ((a & M') | b) -> b
661 return replace_pseudo(insn, &insn->src1, orb);
662 }
663 if (multi_users(insn->src1))
664 return 0; // can't modify anything inside the OR
665 if (nmask == mask) {
666 struct instruction *or = insn->src1->def;
667 pseudo_t *arg = (ora == or->src1) ? &or->src1 : &or->src2;
668 // if (M' & M) == M: ((a & M') | b) -> (a | b)
669 return replace_pseudo(or, arg, and->src1);
670 }
671 if (nmask != omask && !multi_users(ora)) {
672 // if (M' & M) != M': AND(a, M') -> AND(a, (M' & M))
673 and->src2 = value_pseudo(nmask);
674 return REPEAT_CSE;
675 }
676 return 0;
677 }
678
679 ///
680 // try to simplify MASK(OR(a, b), M)
681 // @insn: the masking instruction
682 // @mask: the associated mask (M)
683 // @or: the OR instruction
684 // @return: 0 if no changes have been made, one or more REPEAT_* flags otherwise.
685 static int simplify_mask_or(struct instruction *insn, unsigned long long mask, struct instruction *or)
686 {
687 pseudo_t src1 = or->src1;
688 pseudo_t src2 = or->src2;
689 int rc;
690
691 if (src1->type == PSEUDO_REG) {
692 if ((rc = simplify_mask_or_and(insn, mask, src1, src2)))
693 return rc;
694 }
695 if (src2->type == PSEUDO_REG) {
696 if ((rc = simplify_mask_or_and(insn, mask, src2, src1)))
697 return rc;
698 } else if (src2->type == PSEUDO_VAL) {
699 unsigned long long oval = src2->value;
700 unsigned long long nval = oval & mask;
701 // Try to simplify:
702 // MASK(OR(x, C), M)
703 if (nval == 0) {
704 // if (C & M) == 0: OR(x, C) -> x
705 return replace_pseudo(insn, &insn->src1, src1);
706 }
707 if (nval == mask) {
708 // if (C & M) == M: OR(x, C) -> M
709 return replace_pseudo(insn, &insn->src1, value_pseudo(mask));
710 }
711 if (nval != oval && !multi_users(or->target)) {
712 // if (C & M) != C: OR(x, C) -> OR(x, (C & M))
713 return replace_pseudo(or, &or->src2, value_pseudo(nval));
714 }
715 }
716 return 0;
717 }
718
719 ///
720 // try to simplify MASK(SHIFT(OR(a, b), S), M)
721 // @sh: the shift instruction
722 // @or: the OR instruction
723 // @mask: the mask associated to MASK (M):
724 // @return: 0 if no changes have been made, one or more REPEAT_* flags otherwise.
725 static int simplify_mask_shift_or(struct instruction *sh, struct instruction *or, unsigned long long mask)
726 {
727 unsigned long long smask = bits_mask(sh->size);
728 int shift = sh->src2->value;
729
730 if (sh->opcode == OP_LSR)
731 mask <<= shift;
732 else
733 mask >>= shift;
734 return simplify_mask_or(sh, smask & mask, or);
735 }
736
737 static int simplify_mask_shift(struct instruction *sh, unsigned long long mask)
738 {
739 struct instruction *inner;
740
741 if (!constant(sh->src2) || sh->tainted)
742 return 0;
743 switch (DEF_OPCODE(inner, sh->src1)) {
744 case OP_OR:
745 if (!multi_users(sh->target))
746 return simplify_mask_shift_or(sh, inner, mask);
747 break;
748 }
749 return 0;
750 }
751
752 static long long check_shift_count(struct instruction *insn, unsigned long long uval)
753 {
754 unsigned int size = insn->size;
755 long long sval = uval;
756
757 if (uval < size)
758 return uval;
759
760 sval = sign_extend_safe(sval, size);
761 sval = sign_extend_safe(sval, bits_in_int);
762 if (sval < 0)
763 insn->src2 = value_pseudo(sval);
764 if (insn->tainted)
765 return sval;
766
767 if (sval < 0 && Wshift_count_negative)
768 warning(insn->pos, "shift count is negative (%lld)", sval);
769 if (sval > 0 && Wshift_count_overflow) {
770 struct symbol *ctype = insn->type;
771 const char *tname;
772 if (ctype->type == SYM_NODE)
773 ctype = ctype->ctype.base_type;
774 tname = show_typename(ctype);
775 warning(insn->pos, "shift too big (%llu) for type %s", sval, tname);
776 }
777 insn->tainted = 1;
778 return sval;
779 }
780
781 static int simplify_shift(struct instruction *insn, pseudo_t pseudo, long long value)
782 {
783 struct instruction *def;
784 unsigned long long mask, omask, nmask;
785 unsigned long long nval;
786 unsigned int size;
787 pseudo_t src2;
788
789 if (!value)
790 return replace_with_pseudo(insn, pseudo);
791 value = check_shift_count(insn, value);
792 if (value < 0)
793 return 0;
794
795 size = insn->size;
796 switch (insn->opcode) {
797 case OP_ASR:
798 if (value >= size)
799 return 0;
800 if (pseudo->type != PSEUDO_REG)
801 break;
802 def = pseudo->def;
803 switch (def->opcode) {
804 case OP_LSR:
805 case OP_ASR:
806 if (def == insn) // cyclic DAG!
807 break;
808 src2 = def->src2;
809 if (src2->type != PSEUDO_VAL)
810 break;
811 nval = src2->value;
812 if (nval > insn->size || nval == 0)
813 break;
814 value += nval;
815 if (def->opcode == OP_LSR)
816 insn->opcode = OP_LSR;
817 else if (value >= size)
818 value = size - 1;
819 goto new_value;
820
821 case OP_ZEXT:
822 // transform:
823 // zext.N %t <- (O) %a
824 // asr.N %r <- %t, C
825 // into
826 // zext.N %t <- (O) %a
827 // lsr.N %r <- %t, C
828 insn->opcode = OP_LSR;
829 return REPEAT_CSE;
830 }
831 break;
832 case OP_LSR:
833 size = operand_size(insn, pseudo);
834 if (value >= size)
835 goto zero;
836 switch(DEF_OPCODE(def, pseudo)) {
837 case OP_AND:
838 // replace (A & M) >> S
839 // by (A >> S) & (M >> S)
840 if (!constant(def->src2))
841 break;
842 mask = bits_mask(insn->size - value) << value;
843 omask = def->src2->value;
844 nmask = omask & mask;
845 if (nmask == 0)
846 return replace_with_pseudo(insn, value_pseudo(0));
847 if (nmask == mask)
848 return replace_pseudo(insn, &insn->src1, def->src1);
849 if (nbr_users(pseudo) > 1)
850 break;
851 def->opcode = OP_LSR;
852 def->src2 = insn->src2;
853 insn->opcode = OP_AND;
854 insn->src2 = value_pseudo(omask >> value);
855 return REPEAT_CSE;
856 case OP_LSR:
857 goto case_shift_shift;
858 case OP_OR:
859 mask = bits_mask(size);
860 return simplify_mask_shift_or(insn, def, mask);
861 case OP_SHL:
862 // replace ((x << S) >> S)
863 // by (x & (-1 >> S))
864 if (def->src2 != insn->src2)
865 break;
866 mask = bits_mask(insn->size - value);
867 goto replace_mask;
868 }
869 break;
870 case OP_SHL:
871 if (value >= size)
872 goto zero;
873 switch(DEF_OPCODE(def, pseudo)) {
874 case OP_AND:
875 // simplify (A & M) << S
876 if (!constant(def->src2))
877 break;
878 mask = bits_mask(insn->size) >> value;
879 omask = def->src2->value;
880 nmask = omask & mask;
881 if (nmask == 0)
882 return replace_with_pseudo(insn, value_pseudo(0));
883 if (nmask == mask)
884 return replace_pseudo(insn, &insn->src1, def->src1);
885 // do not simplify into ((A << S) & (M << S))
886 break;
887 case OP_LSR:
888 // replace ((x >> S) << S)
889 // by (x & (-1 << S))
890 if (def->src2 != insn->src2)
891 break;
892 mask = bits_mask(insn->size - value) << value;
893 goto replace_mask;
894 case OP_OR:
895 mask = bits_mask(size);
896 return simplify_mask_shift_or(insn, def, mask);
897 case OP_SHL:
898 case_shift_shift: // also for LSR - LSR
899 if (def == insn) // cyclic DAG!
900 break;
901 src2 = def->src2;
902 if (src2->type != PSEUDO_VAL)
903 break;
904 nval = src2->value;
905 if (nval > insn->size)
906 break;
907 value += nval;
908 goto new_value;
909 }
910 break;
911 }
912 return 0;
913
914 new_value:
915 if (value < size) {
916 insn->src2 = value_pseudo(value);
917 return replace_pseudo(insn, &insn->src1, pseudo->def->src1);
918 }
919 zero:
920 return replace_with_pseudo(insn, value_pseudo(0));
921 replace_mask:
922 insn->opcode = OP_AND;
923 insn->src2 = value_pseudo(mask);
924 return replace_pseudo(insn, &insn->src1, def->src1);
925 }
926
927 static int simplify_mul_div(struct instruction *insn, long long value)
928 {
929 unsigned long long sbit = 1ULL << (insn->size - 1);
930 unsigned long long bits = sbit | (sbit - 1);
931
932 if (value == 1)
933 return replace_with_pseudo(insn, insn->src1);
934
935 switch (insn->opcode) {
936 case OP_MUL:
937 if (value == 0)
938 return replace_with_pseudo(insn, insn->src2);
939 /* Fall through */
940 case OP_DIVS:
941 if (!(value & sbit)) // positive
942 break;
943
944 value |= ~bits;
945 if (value == -1) {
946 insn->opcode = OP_NEG;
947 return REPEAT_CSE;
948 }
949 }
950
951 return 0;
952 }
953
954 static int simplify_seteq_setne(struct instruction *insn, long long value)
955 {
956 pseudo_t old = insn->src1;
957 struct instruction *def;
958 unsigned osize;
959 int inverse;
960 int opcode;
961
962 if (value != 0 && value != 1)
963 return 0;
964
965 if (old->type != PSEUDO_REG)
966 return 0;
967 def = old->def;
968 if (!def)
969 return 0;
970
971 inverse = (insn->opcode == OP_SET_NE) == value;
972 if (!inverse && def->size == 1 && insn->size == 1) {
973 // Replace:
974 // setne %r <- %s, $0
975 // or:
976 // seteq %r <- %s, $1
977 // by %s when boolean
978 return replace_with_pseudo(insn, old);
979 }
980 opcode = def->opcode;
981 switch (opcode) {
982 case OP_AND:
983 if (inverse)
984 break;
985 if (def->size != insn->size)
986 break;
987 if (def->src2->type != PSEUDO_VAL)
988 break;
989 if (def->src2->value != 1)
990 break;
991 return replace_with_pseudo(insn, old);
992 case OP_FPCMP ... OP_BINCMP_END:
993 // Convert:
994 // setcc.n %t <- %a, %b
995 // setne.m %r <- %t, $0
996 // into:
997 // setcc.n %t <- %a, %b
998 // setcc.m %r <- %a, $b
999 // and similar for setne/eq ... 0/1
1000 insn->opcode = inverse ? opcode_table[opcode].negate : opcode;
1001 use_pseudo(insn, def->src1, &insn->src1);
1002 use_pseudo(insn, def->src2, &insn->src2);
1003 remove_usage(old, &insn->src1);
1004 return REPEAT_CSE;
1005
1006 case OP_SEXT:
1007 if (value && (def->orig_type->bit_size == 1))
1008 break;
1009 /* Fall through */
1010 case OP_ZEXT:
1011 // Convert:
1012 // *ext.m %s <- (1) %a
1013 // setne.1 %r <- %s, $0
1014 // into:
1015 // setne.1 %s <- %a, $0
1016 // and same for setne/eq ... 0/1
1017 return replace_pseudo(insn, &insn->src1, def->src);
1018 case OP_TRUNC:
1019 if (multi_users(old))
1020 break;
1021 // convert
1022 // trunc.n %s <- (o) %a
1023 // setne.m %r <- %s, $0
1024 // into:
1025 // and.o %s <- %a, $((1 << o) - 1)
1026 // setne.m %r <- %s, $0
1027 // and same for setne/eq ... 0/1
1028 osize = def->size;
1029 def->opcode = OP_AND;
1030 def->type = def->orig_type;
1031 def->size = def->type->bit_size;
1032 def->src2 = value_pseudo(bits_mask(osize));
1033 return REPEAT_CSE;
1034 }
1035 return 0;
1036 }
1037
1038 static int simplify_constant_mask(struct instruction *insn, unsigned long long mask)
1039 {
1040 pseudo_t old = insn->src1;
1041 unsigned long long omask;
1042 unsigned long long nmask;
1043 struct instruction *def;
1044 int osize;
1045
1046 switch (DEF_OPCODE(def, old)) {
1047 case OP_FPCMP ... OP_BINCMP_END:
1048 osize = 1;
1049 goto oldsize;
1050 case OP_OR:
1051 return simplify_mask_or(insn, mask, def);
1052 case OP_LSR:
1053 case OP_SHL:
1054 return simplify_mask_shift(def, mask);
1055 case OP_ZEXT:
1056 osize = def->orig_type->bit_size;
1057 /* fall through */
1058 oldsize:
1059 omask = (1ULL << osize) - 1;
1060 nmask = mask & omask;
1061 if (nmask == omask)
1062 // the AND mask is redundant
1063 return replace_with_pseudo(insn, old);
1064 if (nmask != mask) {
1065 // can use a smaller mask
1066 insn->src2 = value_pseudo(nmask);
1067 return REPEAT_CSE;
1068 }
1069 break;
1070 }
1071 return 0;
1072 }
1073
1074 static int simplify_constant_rightside(struct instruction *insn)
1075 {
1076 long long value = insn->src2->value;
1077 long long sbit = 1ULL << (insn->size - 1);
1078 long long bits = sbit | (sbit - 1);
1079
1080 switch (insn->opcode) {
1081 case OP_OR:
1082 if ((value & bits) == bits)
1083 return replace_with_pseudo(insn, insn->src2);
1084 goto case_neutral_zero;
1085
1086 case OP_XOR:
1087 if ((value & bits) == bits) {
1088 insn->opcode = OP_NOT;
1089 return REPEAT_CSE;
1090 }
1091 goto case_neutral_zero;
1092
1093 case OP_SUB:
1094 if (value) {
1095 insn->opcode = OP_ADD;
1096 insn->src2 = value_pseudo(-value);
1097 return REPEAT_CSE;
1098 }
1099 /* Fall through */
1100 case OP_ADD:
1101 case_neutral_zero:
1102 if (!value)
1103 return replace_with_pseudo(insn, insn->src1);
1104 return 0;
1105 case OP_ASR:
1106 case OP_SHL:
1107 case OP_LSR:
1108 return simplify_shift(insn, insn->src1, value);
1109
1110 case OP_MODU: case OP_MODS:
1111 if (value == 1)
1112 return replace_with_pseudo(insn, value_pseudo(0));
1113 return 0;
1114
1115 case OP_DIVU: case OP_DIVS:
1116 case OP_MUL:
1117 return simplify_mul_div(insn, value);
1118
1119 case OP_AND:
1120 if (!value)
1121 return replace_with_pseudo(insn, insn->src2);
1122 if ((value & bits) == bits)
1123 return replace_with_pseudo(insn, insn->src1);
1124 return simplify_constant_mask(insn, value);
1125
1126 case OP_SET_NE:
1127 case OP_SET_EQ:
1128 return simplify_seteq_setne(insn, value);
1129 }
1130 return 0;
1131 }
1132
1133 static int simplify_constant_leftside(struct instruction *insn)
1134 {
1135 long long value = insn->src1->value;
1136
1137 switch (insn->opcode) {
1138 case OP_ADD: case OP_OR: case OP_XOR:
1139 if (!value)
1140 return replace_with_pseudo(insn, insn->src2);
1141 return 0;
1142
1143 case OP_SHL:
1144 case OP_LSR: case OP_ASR:
1145 case OP_AND:
1146 case OP_MUL:
1147 if (!value)
1148 return replace_with_pseudo(insn, insn->src1);
1149 return 0;
1150 }
1151 return 0;
1152 }
1153
1154 static int simplify_constant_binop(struct instruction *insn)
1155 {
1156 pseudo_t res = eval_insn(insn);
1157
1158 if (!res)
1159 return 0;
1160
1161 replace_with_pseudo(insn, res);
1162 return REPEAT_CSE;
1163 }
1164
1165 static int simplify_binop_same_args(struct instruction *insn, pseudo_t arg)
1166 {
1167 switch (insn->opcode) {
1168 case OP_SET_NE:
1169 case OP_SET_LT: case OP_SET_GT:
1170 case OP_SET_B: case OP_SET_A:
1171 if (Wtautological_compare)
1172 warning(insn->pos, "self-comparison always evaluates to false");
1173 case OP_SUB:
1174 case OP_XOR:
1175 return replace_with_pseudo(insn, value_pseudo(0));
1176
1177 case OP_SET_EQ:
1178 case OP_SET_LE: case OP_SET_GE:
1179 case OP_SET_BE: case OP_SET_AE:
1180 if (Wtautological_compare)
1181 warning(insn->pos, "self-comparison always evaluates to true");
1182 return replace_with_pseudo(insn, value_pseudo(1));
1183
1184 case OP_AND:
1185 case OP_OR:
1186 return replace_with_pseudo(insn, arg);
1187
1188 default:
1189 break;
1190 }
1191
1192 return 0;
1193 }
1194
1195 static int simplify_binop(struct instruction *insn)
1196 {
1197 if (dead_insn(insn, &insn->src1, &insn->src2, NULL))
1198 return REPEAT_CSE;
1199 if (constant(insn->src1)) {
1200 if (constant(insn->src2))
1201 return simplify_constant_binop(insn);
1202 return simplify_constant_leftside(insn);
1203 }
1204 if (constant(insn->src2))
1205 return simplify_constant_rightside(insn);
1206 if (insn->src1 == insn->src2)
1207 return simplify_binop_same_args(insn, insn->src1);
1213 pseudo_t p1 = *pp1, p2 = *pp2;
1214
1215 use_pseudo(insn1, p2, pp1);
1216 use_pseudo(insn2, p1, pp2);
1217 remove_usage(p1, pp1);
1218 remove_usage(p2, pp2);
1219 }
1220
1221 static int canonical_order(pseudo_t p1, pseudo_t p2)
1222 {
1223 /* symbol/constants on the right */
1224 if (p1->type == PSEUDO_VAL)
1225 return p2->type == PSEUDO_VAL;
1226
1227 if (p1->type == PSEUDO_SYM)
1228 return p2->type == PSEUDO_SYM || p2->type == PSEUDO_VAL;
1229
1230 return 1;
1231 }
1232
1233 static int canonicalize_commutative(struct instruction *insn)
1234 {
1235 if (canonical_order(insn->src1, insn->src2))
1236 return 0;
1237
1238 switch_pseudo(insn, &insn->src1, insn, &insn->src2);
1239 return repeat_phase |= REPEAT_CSE;
1240 }
1241
1242 static int canonicalize_compare(struct instruction *insn)
1243 {
1244 if (canonical_order(insn->src1, insn->src2))
1245 return 0;
1246
1247 switch_pseudo(insn, &insn->src1, insn, &insn->src2);
1248 insn->opcode = opcode_table[insn->opcode].swap;
1249 return repeat_phase |= REPEAT_CSE;
1250 }
1251
1252 static inline int simple_pseudo(pseudo_t pseudo)
1253 {
1254 return pseudo->type == PSEUDO_VAL || pseudo->type == PSEUDO_SYM;
1255 }
1256
1257 static int simplify_associative_binop(struct instruction *insn)
1258 {
1259 struct instruction *def;
1260 pseudo_t pseudo = insn->src1;
1261
1262 if (!simple_pseudo(insn->src2))
1263 return 0;
1264 if (pseudo->type != PSEUDO_REG)
1265 return 0;
1266 def = pseudo->def;
1267 if (def == insn)
1268 return 0;
1269 if (def->opcode != insn->opcode)
1270 return 0;
1271 if (!simple_pseudo(def->src2))
1272 return 0;
1273 if (multi_users(def->target))
1274 return 0;
1275 switch_pseudo(def, &def->src1, insn, &insn->src2);
1276 return REPEAT_CSE;
1277 }
1278
1279 static int simplify_constant_unop(struct instruction *insn)
1280 {
1281 long long val = insn->src1->value;
1282 long long res, mask;
1283
1284 switch (insn->opcode) {
1285 case OP_NOT:
1286 res = ~val;
1287 break;
1288 case OP_NEG:
1289 res = -val;
1290 break;
1291 case OP_SEXT:
1292 mask = 1ULL << (insn->orig_type->bit_size-1);
1293 if (val & mask)
1294 val |= ~(mask | (mask-1));
1295 /* fall through */
1296 case OP_ZEXT:
1297 case OP_TRUNC:
1298 res = val;
1299 break;
1300 default:
1301 return 0;
1302 }
1303 mask = 1ULL << (insn->size-1);
1304 res &= mask | (mask-1);
1305
1306 replace_with_pseudo(insn, value_pseudo(res));
1307 return REPEAT_CSE;
1308 }
1309
1310 static int simplify_unop(struct instruction *insn)
1311 {
1312 if (dead_insn(insn, &insn->src1, NULL, NULL))
1313 return REPEAT_CSE;
1314 if (constant(insn->src1))
1315 return simplify_constant_unop(insn);
1316
1317 switch (insn->opcode) {
1318 struct instruction *def;
1319
1320 case OP_NOT:
1321 def = insn->src->def;
1322 if (def && def->opcode == OP_NOT)
1323 return replace_with_pseudo(insn, def->src);
1324 break;
1325 case OP_NEG:
1326 def = insn->src->def;
1344 kill_use(&insn->src);
1345 use_pseudo(insn, def->src, &insn->src);
1346 return REPEAT_CSE | REPEAT_SYMBOL_CLEANUP;
1347 }
1348 if (def->opcode == OP_ADD) {
1349 new = def->src1;
1350 off = def->src2;
1351 if (constant(off))
1352 goto offset;
1353 new = off;
1354 off = def->src1;
1355 if (constant(off))
1356 goto offset;
1357 return 0;
1358 }
1359 }
1360 return 0;
1361
1362 offset:
1363 /* Invalid code */
1364 if (new == orig || new == addr) {
1365 if (new == VOID)
1366 return 0;
1367 /*
1368 * If some BB have been removed it is possible that this
1369 * memop is in fact part of a dead BB. In this case
1370 * we must not warn since nothing is wrong.
1371 * If not part of a dead BB this will be redone after
1372 * the BBs have been cleaned up.
1373 */
1374 if (repeat_phase & REPEAT_CFG_CLEANUP)
1375 return 0;
1376 warning(insn->pos, "crazy programmer");
1377 replace_pseudo(insn, &insn->src, VOID);
1378 return 0;
1379 }
1380 insn->offset += off->value;
1381 replace_pseudo(insn, &insn->src, new);
1382 return REPEAT_CSE | REPEAT_SYMBOL_CLEANUP;
1383 }
1384
1385 ///
1386 // simplify memops instructions
1387 //
1388 // :note: We walk the whole chain of adds/subs backwards.
1389 // That's not only more efficient, but it allows us to find loops.
1390 static int simplify_memop(struct instruction *insn)
1391 {
1392 int one, ret = 0;
1393 pseudo_t orig = insn->src;
1394
1395 do {
1396 one = simplify_one_memop(insn, orig);
1397 ret |= one;
1398 } while (one);
1399 return ret;
1400 }
1401
1402 static int simplify_cast(struct instruction *insn)
1403 {
1404 unsigned long long mask;
1405 struct instruction *def;
1406 pseudo_t src;
1407 pseudo_t val;
1408 int osize;
1409 int size;
1410
1411 if (dead_insn(insn, &insn->src, NULL, NULL))
1412 return REPEAT_CSE;
1413
1414 src = insn->src;
1415
1416 /* A cast of a constant? */
1417 if (constant(src))
1418 return simplify_constant_unop(insn);
1419
1420 // can merge with the previous instruction?
1421 size = insn->size;
1422 def = src->def;
1423 switch (def_opcode(src)) {
1424 case OP_AND:
1425 val = def->src2;
1426 if (val->type != PSEUDO_VAL)
1427 break;
1428 /* A cast of a AND might be a no-op.. */
1429 switch (insn->opcode) {
1430 case OP_TRUNC:
1431 if (multi_users(src))
1432 break;
1433 def->opcode = OP_TRUNC;
1434 def->orig_type = def->type;
1435 def->type = insn->type;
1436 def->size = size;
1437
1438 insn->opcode = OP_AND;
1439 mask = val->value;
1440 mask &= (1ULL << size) - 1;
1441 insn->src2 = value_pseudo(mask);
1442 return REPEAT_CSE;
1443
1444 case OP_SEXT:
1445 if (val->value & (1 << (def->size - 1)))
1446 break;
1447 // OK, sign bit is 0
1448 case OP_ZEXT:
1449 if (multi_users(src))
1450 break;
1451 // transform:
1452 // and.n %b <- %a, M
1453 // *ext.m %c <- (n) %b
1454 // into:
1455 // zext.m %b <- %a
1456 // and.m %c <- %b, M
1457 // For ZEXT, the mask will always be small
1458 // enough. For SEXT, it can only be done if
1459 // the mask force the sign bit to 0.
1460 def->opcode = OP_ZEXT;
1461 def->orig_type = insn->orig_type;
1462 def->type = insn->type;
1463 def->size = insn->size;
1464 insn->opcode = OP_AND;
1465 insn->src2 = val;
1466 return REPEAT_CSE;
1467 }
1468 break;
1469 case OP_FPCMP ... OP_BINCMP_END:
1470 switch (insn->opcode) {
1471 case OP_SEXT:
1472 if (insn->size == 1)
1473 break;
1474 /* fall through */
1475 case OP_ZEXT:
1476 case OP_TRUNC:
1477 // simplify:
1478 // setcc.n %t <- %a, %b
1479 // zext.m %r <- (n) %t
1480 // into:
1481 // setcc.m %r <- %a, %b
1482 // and same for s/zext/trunc/
1483 insn->opcode = def->opcode;
1484 use_pseudo(insn, def->src2, &insn->src2);
1485 return replace_pseudo(insn, &insn->src1, def->src1);
1486 }
1487 break;
1488 case OP_OR:
1489 switch (insn->opcode) {
1490 case OP_TRUNC:
1491 mask = bits_mask(insn->size);
1492 return simplify_mask_or(insn, mask, def);
1493 }
1494 break;
1495 case OP_LSR:
1496 case OP_SHL:
1497 if (insn->opcode != OP_TRUNC)
1498 break;
1499 mask = bits_mask(insn->size);
1500 return simplify_mask_shift(def, mask);
1501 case OP_TRUNC:
1502 switch (insn->opcode) {
1503 case OP_TRUNC:
1504 insn->orig_type = def->orig_type;
1505 return replace_pseudo(insn, &insn->src1, def->src);
1506 case OP_ZEXT:
1507 if (size != def->orig_type->bit_size)
1508 break;
1509 insn->opcode = OP_AND;
1510 insn->src2 = value_pseudo((1ULL << def->size) - 1);
1511 return replace_pseudo(insn, &insn->src1, def->src);
1512 }
1513 break;
1514 case OP_ZEXT:
1515 switch (insn->opcode) {
1516 case OP_SEXT:
1517 insn->opcode = OP_ZEXT;
1518 /* fall through */
1519 case OP_ZEXT:
1520 insn->orig_type = def->orig_type;
1521 return replace_pseudo(insn, &insn->src, def->src);
1522 }
1523 /* fall through */
1524 case OP_SEXT:
1525 switch (insn->opcode) {
1526 case OP_TRUNC:
1527 osize = def->orig_type->bit_size;
1528 if (size == osize)
1529 return replace_with_pseudo(insn, def->src);
1530 if (size > osize)
1531 insn->opcode = def->opcode;
1532 insn->orig_type = def->orig_type;
1533 return replace_pseudo(insn, &insn->src, def->src);
1534 }
1535 switch (insn->opcode) {
1536 case OP_SEXT:
1537 insn->orig_type = def->orig_type;
1538 return replace_pseudo(insn, &insn->src, def->src);
1539 }
1540 break;
1541 }
1542
1543 return 0;
1544 }
1545
1546 static int simplify_select(struct instruction *insn)
1547 {
1548 pseudo_t cond, src1, src2;
1549
1550 if (dead_insn(insn, &insn->src1, &insn->src2, &insn->src3))
1551 return REPEAT_CSE;
1552
1553 cond = insn->src1;
1554 src1 = insn->src2;
1555 src2 = insn->src3;
1556 if (constant(cond) || src1 == src2) {
1557 pseudo_t *kill, take;
1558 kill_use(&insn->src1);
1559 take = cond->value ? src1 : src2;
1560 kill = cond->value ? &insn->src3 : &insn->src2;
1561 kill_use(kill);
1562 replace_with_pseudo(insn, take);
1563 return REPEAT_CSE;
1564 }
1565 if (constant(src1) && constant(src2)) {
1566 long long val1 = src1->value;
1567 long long val2 = src2->value;
1568
1569 /* The pair 0/1 is special - replace with SETNE/SETEQ */
1570 if ((val1 | val2) == 1) {
1571 int opcode = OP_SET_EQ;
1572 if (val1) {
1573 src1 = src2;
1574 opcode = OP_SET_NE;
1575 }
1576 insn->opcode = opcode;
1577 /* insn->src1 is already cond */
1578 insn->src2 = src1; /* Zero */
1579 return REPEAT_CSE;
1580 }
1581 }
1582 if (cond == src2 && is_zero(src1)) {
1583 kill_use(&insn->src1);
1584 kill_use(&insn->src3);
1585 replace_with_pseudo(insn, value_pseudo(0));
1586 return REPEAT_CSE;
1587 }
1588 return 0;
1589 }
1590
1591 static int is_in_range(pseudo_t src, long long low, long long high)
1592 {
1593 long long value;
1594
1595 switch (src->type) {
1596 case PSEUDO_VAL:
1597 value = src->value;
1598 return value >= low && value <= high;
1599 default:
1600 return 0;
1601 }
1602 }
1603
1604 static int simplify_range(struct instruction *insn)
1605 {
1606 pseudo_t src1, src2, src3;
1607
1608 src1 = insn->src1;
1609 src2 = insn->src2;
1610 src3 = insn->src3;
1611 if (src2->type != PSEUDO_VAL || src3->type != PSEUDO_VAL)
1612 return 0;
1613 if (is_in_range(src1, src2->value, src3->value)) {
1614 kill_instruction(insn);
1615 return REPEAT_CSE;
1616 }
1617 return 0;
1618 }
1619
1620 ///
1621 // simplify SET_NE/EQ $0 + BR
1622 static int simplify_cond_branch(struct instruction *br, struct instruction *def, pseudo_t newcond)
1623 {
1624 replace_pseudo(br, &br->cond, newcond);
1625 if (def->opcode == OP_SET_EQ) {
1626 struct basic_block *tmp = br->bb_true;
1627 br->bb_true = br->bb_false;
1628 br->bb_false = tmp;
1629 }
1630 return REPEAT_CSE;
1631 }
1632
1633 static int simplify_branch(struct instruction *insn)
1634 {
1635 pseudo_t cond = insn->cond;
1636
1637 /* Constant conditional */
1638 if (constant(cond)) {
1639 insert_branch(insn->bb, insn, cond->value ? insn->bb_true : insn->bb_false);
1640 return REPEAT_CSE;
1641 }
1642
1643 /* Same target? */
1644 if (insn->bb_true == insn->bb_false) {
1645 struct basic_block *bb = insn->bb;
1646 struct basic_block *target = insn->bb_false;
1647 remove_bb_from_list(&target->parents, bb, 1);
1648 remove_bb_from_list(&bb->children, target, 1);
1649 insn->bb_false = NULL;
1650 kill_use(&insn->cond);
1651 insn->cond = NULL;
1652 insn->opcode = OP_BR;
1653 return REPEAT_CSE;
1654 }
1655
1656 /* Conditional on a SETNE $0 or SETEQ $0 */
1657 if (cond->type == PSEUDO_REG) {
1658 struct instruction *def = cond->def;
1659
1660 if (def->opcode == OP_SET_NE || def->opcode == OP_SET_EQ) {
1661 if (constant(def->src1) && !def->src1->value)
1662 return simplify_cond_branch(insn, def, def->src2);
1663 if (constant(def->src2) && !def->src2->value)
1664 return simplify_cond_branch(insn, def, def->src1);
1665 }
1666 if (def->opcode == OP_SEL) {
1667 if (constant(def->src2) && constant(def->src3)) {
1668 long long val1 = def->src2->value;
1669 long long val2 = def->src3->value;
1670 if (!val1 && !val2) {
1671 insert_branch(insn->bb, insn, insn->bb_false);
1672 return REPEAT_CSE;
1673 }
1674 if (val1 && val2) {
1675 insert_branch(insn->bb, insn, insn->bb_true);
1676 return REPEAT_CSE;
1677 }
1678 if (val2) {
1679 struct basic_block *tmp = insn->bb_true;
1680 insn->bb_true = insn->bb_false;
1681 insn->bb_false = tmp;
1682 }
1683 return replace_pseudo(insn, &insn->cond, def->src1);
1684 }
1685 }
1686 if (def->opcode == OP_SEXT || def->opcode == OP_ZEXT)
1687 return replace_pseudo(insn, &insn->cond, def->src);
1688 }
1689 return 0;
1690 }
1691
1692 static int simplify_switch(struct instruction *insn)
1693 {
1694 pseudo_t cond = insn->cond;
1695 long long val;
1696 struct multijmp *jmp;
1697
1698 if (!constant(cond))
1699 return 0;
1700 val = insn->cond->value;
1701
1702 FOR_EACH_PTR(insn->multijmp_list, jmp) {
1703 /* Default case */
1704 if (jmp->begin > jmp->end)
1705 goto found;
1706 if (val >= jmp->begin && val <= jmp->end)
1707 goto found;
1708 } END_FOR_EACH_PTR(jmp);
1709 warning(insn->pos, "Impossible case statement");
1710 return 0;
1711
1712 found:
1713 insert_branch(insn->bb, insn, jmp->target);
1714 return REPEAT_CSE;
1715 }
1716
1717 int simplify_instruction(struct instruction *insn)
1718 {
1719 if (!insn->bb)
1720 return 0;
1721 switch (insn->opcode) {
1722 case OP_ADD: case OP_MUL:
1723 case OP_AND: case OP_OR: case OP_XOR:
1724 canonicalize_commutative(insn);
1725 if (simplify_binop(insn))
1726 return REPEAT_CSE;
1727 return simplify_associative_binop(insn);
1728
1729 case OP_SET_EQ: case OP_SET_NE:
1730 canonicalize_commutative(insn);
1731 return simplify_binop(insn);
1732
1733 case OP_SET_LE: case OP_SET_GE:
1734 case OP_SET_LT: case OP_SET_GT:
1735 case OP_SET_B: case OP_SET_A:
1736 case OP_SET_BE: case OP_SET_AE:
1737 canonicalize_compare(insn);
1738 /* fall through */
1739 case OP_SUB:
1740 case OP_DIVU: case OP_DIVS:
1741 case OP_MODU: case OP_MODS:
1742 case OP_SHL:
1743 case OP_LSR: case OP_ASR:
1744 return simplify_binop(insn);
1745
1746 case OP_NOT: case OP_NEG: case OP_FNEG:
1747 return simplify_unop(insn);
1748 case OP_LOAD:
1749 if (!has_users(insn->target))
1750 return kill_instruction(insn);
1751 /* fall-through */
1752 case OP_STORE:
1753 return simplify_memop(insn);
1754 case OP_SYMADDR:
1755 if (dead_insn(insn, &insn->src, NULL, NULL))
1756 return REPEAT_CSE | REPEAT_SYMBOL_CLEANUP;
1757 return replace_with_pseudo(insn, insn->src);
1758 case OP_SEXT: case OP_ZEXT:
1759 case OP_TRUNC:
1760 return simplify_cast(insn);
1761 case OP_FCVTU: case OP_FCVTS:
1762 case OP_UCVTF: case OP_SCVTF:
1763 case OP_FCVTF:
1764 case OP_PTRCAST:
1765 if (dead_insn(insn, &insn->src, NULL, NULL))
1766 return REPEAT_CSE;
1767 break;
1768 case OP_UTPTR:
1769 case OP_PTRTU:
1770 return replace_with_pseudo(insn, insn->src);
1771 case OP_SLICE:
1772 if (dead_insn(insn, &insn->src, NULL, NULL))
1773 return REPEAT_CSE;
1774 break;
1775 case OP_SETVAL:
1776 case OP_SETFVAL:
1777 if (dead_insn(insn, NULL, NULL, NULL))
1778 return REPEAT_CSE;
1779 break;
1780 case OP_PHI:
1781 if (dead_insn(insn, NULL, NULL, NULL)) {
1782 kill_use_list(insn->phi_list);
1783 return REPEAT_CSE;
1784 }
1785 return clean_up_phi(insn);
1786 case OP_PHISOURCE:
1787 if (dead_insn(insn, &insn->phi_src, NULL, NULL))
1788 return REPEAT_CSE;
1789 break;
1790 case OP_SEL:
1791 return simplify_select(insn);
1792 case OP_CBR:
1793 return simplify_branch(insn);
1794 case OP_SWITCH:
1795 return simplify_switch(insn);
1796 case OP_RANGE:
1797 return simplify_range(insn);
1798 case OP_FADD:
1799 case OP_FSUB:
1800 case OP_FMUL:
1801 case OP_FDIV:
1802 if (dead_insn(insn, &insn->src1, &insn->src2, NULL))
1803 return REPEAT_CSE;
1804 break;
1805 }
1806 return 0;
1807 }
|