2 * Simplify - do instruction simplification before CSE
4 * Copyright (C) 2004 Linus Torvalds
10 #include "expression.h"
11 #include "linearize.h"
14 /* Find the trivial parent for a phi-source */
15 static struct basic_block
*phi_parent(struct basic_block
*source
, pseudo_t pseudo
)
17 /* Can't go upwards if the pseudo is defined in the bb it came from.. */
18 if (pseudo
->type
== PSEUDO_REG
) {
19 struct instruction
*def
= pseudo
->def
;
20 if (def
->bb
== source
)
23 if (bb_list_size(source
->children
) != 1 || bb_list_size(source
->parents
) != 1)
25 return first_basic_block(source
->parents
);
28 static void clear_phi(struct instruction
*insn
)
33 FOR_EACH_PTR(insn
->phi_list
, phi
) {
34 *THIS_ADDRESS(phi
) = VOID
;
35 } END_FOR_EACH_PTR(phi
);
38 static int if_convert_phi(struct instruction
*insn
)
41 struct basic_block
*parents
[3];
42 struct basic_block
*bb
, *bb1
, *bb2
, *source
;
43 struct instruction
*br
;
47 if (linearize_ptr_list((struct ptr_list
*)insn
->phi_list
, (void **)array
, 3) != 2)
49 if (linearize_ptr_list((struct ptr_list
*)bb
->parents
, (void **)parents
, 3) != 2)
51 p1
= array
[0]->def
->src1
;
52 bb1
= array
[0]->def
->bb
;
53 p2
= array
[1]->def
->src1
;
54 bb2
= array
[1]->def
->bb
;
56 /* Only try the simple "direct parents" case */
57 if ((bb1
!= parents
[0] || bb2
!= parents
[1]) &&
58 (bb1
!= parents
[1] || bb2
!= parents
[0]))
62 * See if we can find a common source for this..
64 source
= phi_parent(bb1
, p1
);
65 if (source
!= phi_parent(bb2
, p2
))
69 * Cool. We now know that 'source' is the exclusive
70 * parent of both phi-nodes, so the exit at the
71 * end of it fully determines which one it is, and
72 * we can turn it into a select.
74 * HOWEVER, right now we only handle regular
75 * conditional branches. No multijumps or computed
76 * stuff. Verify that here.
78 br
= last_instruction(source
->insns
);
79 if (!br
|| br
->opcode
!= OP_BR
)
86 * We're in business. Match up true/false with p1/p2.
88 if (br
->bb_true
== bb2
|| br
->bb_false
== bb1
) {
95 * Ok, we can now replace that last
102 * select pseudo, p1, p2
105 * and remove the phi-node. If it then
106 * turns out that 'a' or 'b' is entirely
107 * empty (common case), and now no longer
108 * a phi-source, we'll be able to simplify
109 * the conditional branch too.
111 insert_select(source
, br
, insn
, p1
, p2
);
116 static int clean_up_phi(struct instruction
*insn
)
119 struct instruction
*last
;
124 FOR_EACH_PTR(insn
->phi_list
, phi
) {
125 struct instruction
*def
;
129 if (def
->src1
== VOID
|| !def
->bb
)
132 if (last
->src1
!= def
->src1
)
137 } END_FOR_EACH_PTR(phi
);
140 pseudo_t pseudo
= last
? last
->src1
: VOID
;
141 convert_instruction_target(insn
, pseudo
);
146 return if_convert_phi(insn
);
149 static inline void remove_usage(pseudo_t p
, pseudo_t
*usep
)
151 if (has_use_list(p
)) {
152 delete_ptr_list_entry((struct ptr_list
**)&p
->users
, usep
, 1);
154 kill_instruction(p
->def
);
158 void kill_use(pseudo_t
*usep
)
163 remove_usage(p
, usep
);
167 void kill_instruction(struct instruction
*insn
)
169 if (!insn
|| !insn
->bb
)
172 switch (insn
->opcode
) {
173 case OP_BINARY
... OP_BINCMP_END
:
175 kill_use(&insn
->src1
);
176 kill_use(&insn
->src2
);
177 repeat_phase
|= REPEAT_CSE
;
180 case OP_NOT
: case OP_NEG
:
182 kill_use(&insn
->src1
);
183 repeat_phase
|= REPEAT_CSE
;
188 repeat_phase
|= REPEAT_CSE
;
193 repeat_phase
|= REPEAT_CSE
| REPEAT_SYMBOL_CLEANUP
;
198 repeat_phase
|= REPEAT_CSE
;
199 kill_use(&insn
->src1
);
200 kill_use(&insn
->src2
);
201 kill_use(&insn
->src3
);
207 * Kill trivially dead instructions
209 static int dead_insn(struct instruction
*insn
, pseudo_t
*src1
, pseudo_t
*src2
, pseudo_t
*src3
)
212 FOR_EACH_PTR(insn
->target
->users
, usep
) {
215 } END_FOR_EACH_PTR(usep
);
224 static inline int constant(pseudo_t pseudo
)
226 return pseudo
->type
== PSEUDO_VAL
;
229 static int replace_with_pseudo(struct instruction
*insn
, pseudo_t pseudo
)
231 convert_instruction_target(insn
, pseudo
);
236 static int simplify_constant_rightside(struct instruction
*insn
)
238 long long value
= insn
->src2
->value
;
240 switch (insn
->opcode
) {
243 insn
->opcode
= OP_ADD
;
244 insn
->src2
= value_pseudo(-value
);
249 case OP_OR
: case OP_XOR
:
252 case OP_LSR
: case OP_ASR
:
254 return replace_with_pseudo(insn
, insn
->src1
);
257 case OP_MULU
: case OP_MULS
:
260 return replace_with_pseudo(insn
, insn
->src1
);
264 return replace_with_pseudo(insn
, insn
->src2
);
270 static int simplify_constant_leftside(struct instruction
*insn
)
272 long long value
= insn
->src1
->value
;
274 switch (insn
->opcode
) {
275 case OP_ADD
: case OP_OR
: case OP_XOR
:
277 return replace_with_pseudo(insn
, insn
->src2
);
281 case OP_LSR
: case OP_ASR
:
283 case OP_MULU
: case OP_MULS
:
285 return replace_with_pseudo(insn
, insn
->src1
);
291 static int simplify_constant_binop(struct instruction
*insn
)
293 /* FIXME! Verify signs and sizes!! */
294 long long left
= insn
->src1
->value
;
295 long long right
= insn
->src2
->value
;
296 unsigned long long ul
, ur
;
297 long long res
, mask
, bits
;
299 mask
= 1ULL << (insn
->size
-1);
300 bits
= mask
| (mask
-1);
309 switch (insn
->opcode
) {
368 /* Binary comparison */
404 replace_with_pseudo(insn
, value_pseudo(res
));
408 static int simplify_binop(struct instruction
*insn
)
410 if (dead_insn(insn
, &insn
->src1
, &insn
->src2
, NULL
))
412 if (constant(insn
->src1
)) {
413 if (constant(insn
->src2
))
414 return simplify_constant_binop(insn
);
415 return simplify_constant_leftside(insn
);
417 if (constant(insn
->src2
))
418 return simplify_constant_rightside(insn
);
422 static void switch_pseudo(pseudo_t
*pp1
, pseudo_t
*pp2
)
424 pseudo_t p1
= *pp1
, p2
= *pp2
;
428 remove_usage(p1
, pp1
);
429 remove_usage(p2
, pp2
);
432 static int canonical_order(pseudo_t p1
, pseudo_t p2
)
434 /* symbol/constants on the right */
435 if (p1
->type
== PSEUDO_VAL
)
436 return p2
->type
== PSEUDO_VAL
;
438 if (p1
->type
== PSEUDO_SYM
)
439 return p2
->type
== PSEUDO_SYM
|| p2
->type
== PSEUDO_VAL
;
444 static int simplify_commutative_binop(struct instruction
*insn
)
446 if (!canonical_order(insn
->src1
, insn
->src2
)) {
447 switch_pseudo(&insn
->src1
, &insn
->src2
);
453 static inline int simple_pseudo(pseudo_t pseudo
)
455 return pseudo
->type
== PSEUDO_VAL
|| pseudo
->type
== PSEUDO_SYM
;
458 static int simplify_associative_binop(struct instruction
*insn
)
460 struct instruction
*def
;
461 pseudo_t pseudo
= insn
->src1
;
463 if (!simple_pseudo(insn
->src2
))
465 if (pseudo
->type
!= PSEUDO_REG
)
470 if (def
->opcode
!= insn
->opcode
)
472 if (!simple_pseudo(def
->src2
))
474 if (ptr_list_size((struct ptr_list
*)def
->target
->users
) != 1)
476 switch_pseudo(&def
->src1
, &insn
->src2
);
480 static int simplify_constant_unop(struct instruction
*insn
)
482 long long val
= insn
->src1
->value
;
485 switch (insn
->opcode
) {
495 mask
= 1ULL << (insn
->size
-1);
496 res
&= mask
| (mask
-1);
498 replace_with_pseudo(insn
, value_pseudo(res
));
502 static int simplify_unop(struct instruction
*insn
)
504 if (dead_insn(insn
, &insn
->src1
, NULL
, NULL
))
506 if (constant(insn
->src1
))
507 return simplify_constant_unop(insn
);
511 static int simplify_one_memop(struct instruction
*insn
, pseudo_t orig
)
513 pseudo_t addr
= insn
->src
;
516 if (addr
->type
== PSEUDO_REG
) {
517 struct instruction
*def
= addr
->def
;
518 if (def
->opcode
== OP_SYMADDR
&& def
->src
) {
519 kill_use(&insn
->src
);
520 use_pseudo(def
->src
, &insn
->src
);
521 return REPEAT_CSE
| REPEAT_SYMBOL_CLEANUP
;
523 if (def
->opcode
== OP_ADD
) {
543 warning(insn
->pos
, "crazy programmer");
545 insn
->offset
+= off
->value
;
546 use_pseudo(new, &insn
->src
);
547 remove_usage(addr
, &insn
->src
);
548 return REPEAT_CSE
| REPEAT_SYMBOL_CLEANUP
;
552 * We walk the whole chain of adds/subs backwards. That's not
553 * only more efficient, but it allows us to find looops.
555 static int simplify_memop(struct instruction
*insn
)
558 pseudo_t orig
= insn
->src
;
561 one
= simplify_one_memop(insn
, orig
);
567 static long long get_cast_value(long long val
, int old_size
, int new_size
, int sign
)
571 if (sign
&& new_size
> old_size
) {
572 mask
= 1 << (old_size
-1);
574 val
|= ~(mask
| (mask
-1));
576 mask
= 1 << (new_size
-1);
577 return val
& (mask
| (mask
-1));
580 static int simplify_cast(struct instruction
*insn
)
582 struct symbol
*orig_type
;
586 if (dead_insn(insn
, &insn
->src
, NULL
, NULL
))
589 orig_type
= insn
->orig_type
;
592 orig_size
= orig_type
->bit_size
;
596 /* A cast of a constant? */
598 int sign
= orig_type
->ctype
.modifiers
& MOD_SIGNED
;
599 long long val
= get_cast_value(src
->value
, orig_size
, size
, sign
);
600 src
= value_pseudo(val
);
604 /* A cast of a "and" might be a no-op.. */
605 if (src
->type
== PSEUDO_REG
) {
606 struct instruction
*def
= src
->def
;
607 if (def
->opcode
== OP_AND
&& def
->size
>= size
) {
608 pseudo_t val
= def
->src2
;
609 if (val
->type
== PSEUDO_VAL
) {
610 unsigned long long value
= val
->value
;
611 if (!(value
>> (size
-1)))
617 if (size
== orig_size
) {
618 int op
= (orig_type
->ctype
.modifiers
& MOD_SIGNED
) ? OP_SCAST
: OP_CAST
;
619 if (insn
->opcode
== op
)
626 return replace_with_pseudo(insn
, src
);
629 static int simplify_select(struct instruction
*insn
)
631 pseudo_t cond
, src1
, src2
;
633 if (dead_insn(insn
, &insn
->src1
, &insn
->src2
, &insn
->src3
))
639 if (constant(cond
) || src1
== src2
) {
640 pseudo_t
*kill
, take
;
641 kill_use(&insn
->src1
);
642 take
= cond
->value
? src1
: src2
;
643 kill
= cond
->value
? &insn
->src3
: &insn
->src2
;
645 replace_with_pseudo(insn
, take
);
648 if (constant(src1
) && constant(src2
)) {
649 long long val1
= src1
->value
;
650 long long val2
= src2
->value
;
652 /* The pair 0/1 is special - replace with SETNE/SETEQ */
653 if ((val1
| val2
) == 1) {
654 int opcode
= OP_SET_EQ
;
659 insn
->opcode
= opcode
;
660 /* insn->src1 is already cond */
661 insn
->src2
= src1
; /* Zero */
668 static int is_in_range(pseudo_t src
, long long low
, long long high
)
675 return value
>= low
&& value
<= high
;
681 static int simplify_range(struct instruction
*insn
)
683 pseudo_t src1
, src2
, src3
;
688 if (src2
->type
!= PSEUDO_VAL
|| src3
->type
!= PSEUDO_VAL
)
690 if (is_in_range(src1
, src2
->value
, src3
->value
)) {
691 kill_instruction(insn
);
698 * Simplify "set_ne/eq $0 + br"
700 static int simplify_cond_branch(struct instruction
*br
, pseudo_t cond
, struct instruction
*def
, pseudo_t
*pp
)
702 use_pseudo(*pp
, &br
->cond
);
703 remove_usage(cond
, &br
->cond
);
704 if (def
->opcode
== OP_SET_EQ
) {
705 struct basic_block
*true = br
->bb_true
;
706 struct basic_block
*false = br
->bb_false
;
713 static int simplify_branch(struct instruction
*insn
)
715 pseudo_t cond
= insn
->cond
;
720 /* Constant conditional */
721 if (constant(cond
)) {
722 insert_branch(insn
->bb
, insn
, cond
->value
? insn
->bb_true
: insn
->bb_false
);
727 if (insn
->bb_true
== insn
->bb_false
) {
728 struct basic_block
*bb
= insn
->bb
;
729 struct basic_block
*target
= insn
->bb_false
;
730 remove_bb_from_list(&target
->parents
, bb
, 1);
731 remove_bb_from_list(&bb
->children
, target
, 1);
732 insn
->bb_false
= NULL
;
733 kill_use(&insn
->cond
);
738 /* Conditional on a SETNE $0 or SETEQ $0 */
739 if (cond
->type
== PSEUDO_REG
) {
740 struct instruction
*def
= cond
->def
;
742 if (def
->opcode
== OP_SET_NE
|| def
->opcode
== OP_SET_EQ
) {
743 if (constant(def
->src1
) && !def
->src1
->value
)
744 return simplify_cond_branch(insn
, cond
, def
, &def
->src2
);
745 if (constant(def
->src2
) && !def
->src2
->value
)
746 return simplify_cond_branch(insn
, cond
, def
, &def
->src1
);
748 if (def
->opcode
== OP_SEL
) {
749 if (constant(def
->src2
) && constant(def
->src3
)) {
750 long long val1
= def
->src2
->value
;
751 long long val2
= def
->src3
->value
;
752 if (!val1
&& !val2
) {
753 insert_branch(insn
->bb
, insn
, insn
->bb_false
);
757 insert_branch(insn
->bb
, insn
, insn
->bb_true
);
761 struct basic_block
*true = insn
->bb_true
;
762 struct basic_block
*false = insn
->bb_false
;
763 insn
->bb_false
= true;
764 insn
->bb_true
= false;
766 use_pseudo(def
->src1
, &insn
->cond
);
767 remove_usage(cond
, &insn
->cond
);
771 if (def
->opcode
== OP_CAST
|| def
->opcode
== OP_SCAST
) {
772 int orig_size
= def
->orig_type
? def
->orig_type
->bit_size
: 0;
773 if (def
->size
> orig_size
) {
774 use_pseudo(def
->src
, &insn
->cond
);
775 remove_usage(cond
, &insn
->cond
);
783 static int simplify_switch(struct instruction
*insn
)
785 pseudo_t cond
= insn
->cond
;
787 struct multijmp
*jmp
;
791 val
= insn
->cond
->value
;
793 FOR_EACH_PTR(insn
->multijmp_list
, jmp
) {
795 if (jmp
->begin
> jmp
->end
)
797 if (val
>= jmp
->begin
&& val
<= jmp
->end
)
799 } END_FOR_EACH_PTR(jmp
);
800 warning(insn
->pos
, "Impossible case statement");
804 insert_branch(insn
->bb
, insn
, jmp
->target
);
808 int simplify_instruction(struct instruction
*insn
)
812 switch (insn
->opcode
) {
813 case OP_ADD
: case OP_MULS
:
814 case OP_AND
: case OP_OR
: case OP_XOR
:
815 case OP_AND_BOOL
: case OP_OR_BOOL
:
816 if (simplify_binop(insn
))
818 if (simplify_commutative_binop(insn
))
820 return simplify_associative_binop(insn
);
823 case OP_SET_EQ
: case OP_SET_NE
:
824 if (simplify_binop(insn
))
826 return simplify_commutative_binop(insn
);
829 case OP_DIVU
: case OP_DIVS
:
830 case OP_MODU
: case OP_MODS
:
832 case OP_LSR
: case OP_ASR
:
833 case OP_SET_LE
: case OP_SET_GE
:
834 case OP_SET_LT
: case OP_SET_GT
:
835 case OP_SET_B
: case OP_SET_A
:
836 case OP_SET_BE
: case OP_SET_AE
:
837 return simplify_binop(insn
);
839 case OP_NOT
: case OP_NEG
:
840 return simplify_unop(insn
);
841 case OP_LOAD
: case OP_STORE
:
842 return simplify_memop(insn
);
844 if (dead_insn(insn
, NULL
, NULL
, NULL
))
845 return REPEAT_CSE
| REPEAT_SYMBOL_CLEANUP
;
846 return replace_with_pseudo(insn
, insn
->symbol
);
851 return simplify_cast(insn
);
853 if (dead_insn(insn
, NULL
, NULL
, NULL
)) {
857 return clean_up_phi(insn
);
859 if (dead_insn(insn
, &insn
->phi_src
, NULL
, NULL
))
863 return simplify_select(insn
);
865 return simplify_branch(insn
);
867 return simplify_switch(insn
);
869 return simplify_range(insn
);