2 * Simplify - do instruction simplification before CSE
4 * Copyright (C) 2004 Linus Torvalds
10 #include "expression.h"
11 #include "linearize.h"
15 /* Find the trivial parent for a phi-source */
16 static struct basic_block
*phi_parent(struct basic_block
*source
, pseudo_t pseudo
)
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
)
24 if (bb_list_size(source
->children
) != 1 || bb_list_size(source
->parents
) != 1)
26 return first_basic_block(source
->parents
);
29 static void clear_phi(struct instruction
*insn
)
34 FOR_EACH_PTR(insn
->phi_list
, phi
) {
35 *THIS_ADDRESS(phi
) = VOID
;
36 } END_FOR_EACH_PTR(phi
);
39 static int if_convert_phi(struct instruction
*insn
)
42 struct basic_block
*parents
[3];
43 struct basic_block
*bb
, *bb1
, *bb2
, *source
;
44 struct instruction
*br
;
48 if (linearize_ptr_list((struct ptr_list
*)insn
->phi_list
, (void **)array
, 3) != 2)
50 if (linearize_ptr_list((struct ptr_list
*)bb
->parents
, (void **)parents
, 3) != 2)
52 p1
= array
[0]->def
->src1
;
53 bb1
= array
[0]->def
->bb
;
54 p2
= array
[1]->def
->src1
;
55 bb2
= array
[1]->def
->bb
;
57 /* Only try the simple "direct parents" case */
58 if ((bb1
!= parents
[0] || bb2
!= parents
[1]) &&
59 (bb1
!= parents
[1] || bb2
!= parents
[0]))
63 * See if we can find a common source for this..
65 source
= phi_parent(bb1
, p1
);
66 if (source
!= phi_parent(bb2
, p2
))
70 * Cool. We now know that 'source' is the exclusive
71 * parent of both phi-nodes, so the exit at the
72 * end of it fully determines which one it is, and
73 * we can turn it into a select.
75 * HOWEVER, right now we only handle regular
76 * conditional branches. No multijumps or computed
77 * stuff. Verify that here.
79 br
= last_instruction(source
->insns
);
80 if (!br
|| br
->opcode
!= OP_BR
)
87 * We're in business. Match up true/false with p1/p2.
89 if (br
->bb_true
== bb2
|| br
->bb_false
== bb1
) {
96 * OK, we can now replace that last
103 * select pseudo, p1, p2
106 * and remove the phi-node. If it then
107 * turns out that 'a' or 'b' is entirely
108 * empty (common case), and now no longer
109 * a phi-source, we'll be able to simplify
110 * the conditional branch too.
112 insert_select(source
, br
, insn
, p1
, p2
);
117 static int clean_up_phi(struct instruction
*insn
)
120 struct instruction
*last
;
125 FOR_EACH_PTR(insn
->phi_list
, phi
) {
126 struct instruction
*def
;
130 if (def
->src1
== VOID
|| !def
->bb
)
133 if (last
->src1
!= def
->src1
)
138 } END_FOR_EACH_PTR(phi
);
141 pseudo_t pseudo
= last
? last
->src1
: VOID
;
142 convert_instruction_target(insn
, pseudo
);
147 return if_convert_phi(insn
);
150 static int delete_pseudo_user_list_entry(struct pseudo_user_list
**list
, pseudo_t
*entry
, int count
)
152 struct pseudo_user
*pu
;
154 FOR_EACH_PTR(*list
, pu
) {
155 if (pu
->userp
== entry
) {
156 DELETE_CURRENT_PTR(pu
);
160 } END_FOR_EACH_PTR(pu
);
163 pack_ptr_list((struct ptr_list
**)list
);
167 static inline void remove_usage(pseudo_t p
, pseudo_t
*usep
)
169 if (has_use_list(p
)) {
170 delete_pseudo_user_list_entry(&p
->users
, usep
, 1);
172 kill_instruction(p
->def
);
176 void kill_use(pseudo_t
*usep
)
181 remove_usage(p
, usep
);
185 void kill_instruction(struct instruction
*insn
)
187 if (!insn
|| !insn
->bb
)
190 switch (insn
->opcode
) {
193 kill_use(&insn
->src3
);
196 case OP_BINARY
... OP_BINCMP_END
:
197 kill_use(&insn
->src2
);
205 case OP_NOT
: case OP_NEG
:
206 kill_use(&insn
->src1
);
214 repeat_phase
|= REPEAT_SYMBOL_CLEANUP
;
218 if (!insn
->bb_true
|| !insn
->bb_false
)
222 case OP_COMPUTEDGOTO
:
223 kill_use(&insn
->cond
);
233 repeat_phase
|= REPEAT_CSE
;
238 * Kill trivially dead instructions
240 static int dead_insn(struct instruction
*insn
, pseudo_t
*src1
, pseudo_t
*src2
, pseudo_t
*src3
)
242 struct pseudo_user
*pu
;
243 FOR_EACH_PTR(insn
->target
->users
, pu
) {
244 if (*pu
->userp
!= VOID
)
246 } END_FOR_EACH_PTR(pu
);
255 static inline int constant(pseudo_t pseudo
)
257 return pseudo
->type
== PSEUDO_VAL
;
260 static int replace_with_pseudo(struct instruction
*insn
, pseudo_t pseudo
)
262 convert_instruction_target(insn
, pseudo
);
264 switch (insn
->opcode
) {
267 kill_use(&insn
->src3
);
268 case OP_BINARY
... OP_BINCMP_END
:
269 kill_use(&insn
->src2
);
277 kill_use(&insn
->src1
);
287 static unsigned int value_size(long long value
)
302 * Try to determine the maximum size of bits in a pseudo.
304 * Right now this only follow casts and constant values, but we
305 * could look at things like logical 'and' instructions etc.
307 static unsigned int operand_size(struct instruction
*insn
, pseudo_t pseudo
)
309 unsigned int size
= insn
->size
;
311 if (pseudo
->type
== PSEUDO_REG
) {
312 struct instruction
*src
= pseudo
->def
;
313 if (src
&& src
->opcode
== OP_CAST
&& src
->orig_type
) {
314 unsigned int orig_size
= src
->orig_type
->bit_size
;
315 if (orig_size
< size
)
319 if (pseudo
->type
== PSEUDO_VAL
) {
320 unsigned int orig_size
= value_size(pseudo
->value
);
321 if (orig_size
< size
)
327 static int simplify_asr(struct instruction
*insn
, pseudo_t pseudo
, long long value
)
329 unsigned int size
= operand_size(insn
, pseudo
);
332 warning(insn
->pos
, "right shift by bigger than source value");
333 return replace_with_pseudo(insn
, value_pseudo(0));
336 return replace_with_pseudo(insn
, pseudo
);
340 static int simplify_mul_div(struct instruction
*insn
, long long value
)
342 unsigned long long sbit
= 1ULL << (insn
->size
- 1);
343 unsigned long long bits
= sbit
| (sbit
- 1);
346 return replace_with_pseudo(insn
, insn
->src1
);
348 switch (insn
->opcode
) {
352 return replace_with_pseudo(insn
, insn
->src2
);
353 if (!(value
& sbit
)) // positive
358 insn
->opcode
= OP_NEG
;
366 static int simplify_constant_rightside(struct instruction
*insn
)
368 long long value
= insn
->src2
->value
;
370 switch (insn
->opcode
) {
373 insn
->opcode
= OP_ADD
;
374 insn
->src2
= value_pseudo(-value
);
379 case OP_OR
: case OP_XOR
:
384 return replace_with_pseudo(insn
, insn
->src1
);
387 return simplify_asr(insn
, insn
->src1
, value
);
389 case OP_DIVU
: case OP_DIVS
:
390 case OP_MULU
: case OP_MULS
:
391 return simplify_mul_div(insn
, value
);
395 return replace_with_pseudo(insn
, insn
->src1
);
399 return replace_with_pseudo(insn
, insn
->src2
);
405 static int simplify_constant_leftside(struct instruction
*insn
)
407 long long value
= insn
->src1
->value
;
409 switch (insn
->opcode
) {
410 case OP_ADD
: case OP_OR
: case OP_XOR
:
412 return replace_with_pseudo(insn
, insn
->src2
);
416 case OP_LSR
: case OP_ASR
:
418 case OP_MULU
: case OP_MULS
:
420 return replace_with_pseudo(insn
, insn
->src1
);
426 static int simplify_constant_binop(struct instruction
*insn
)
428 /* FIXME! Verify signs and sizes!! */
429 long long left
= insn
->src1
->value
;
430 long long right
= insn
->src2
->value
;
431 unsigned long long ul
, ur
;
432 long long res
, mask
, bits
;
434 mask
= 1ULL << (insn
->size
-1);
435 bits
= mask
| (mask
-1);
444 switch (insn
->opcode
) {
465 if (left
== mask
&& right
== -1)
477 if (left
== mask
&& right
== -1)
507 /* Binary comparison */
543 replace_with_pseudo(insn
, value_pseudo(res
));
547 static int simplify_binop(struct instruction
*insn
)
549 if (dead_insn(insn
, &insn
->src1
, &insn
->src2
, NULL
))
551 if (constant(insn
->src1
)) {
552 if (constant(insn
->src2
))
553 return simplify_constant_binop(insn
);
554 return simplify_constant_leftside(insn
);
556 if (constant(insn
->src2
))
557 return simplify_constant_rightside(insn
);
561 static void switch_pseudo(struct instruction
*insn1
, pseudo_t
*pp1
, struct instruction
*insn2
, pseudo_t
*pp2
)
563 pseudo_t p1
= *pp1
, p2
= *pp2
;
565 use_pseudo(insn1
, p2
, pp1
);
566 use_pseudo(insn2
, p1
, pp2
);
567 remove_usage(p1
, pp1
);
568 remove_usage(p2
, pp2
);
571 static int canonical_order(pseudo_t p1
, pseudo_t p2
)
573 /* symbol/constants on the right */
574 if (p1
->type
== PSEUDO_VAL
)
575 return p2
->type
== PSEUDO_VAL
;
577 if (p1
->type
== PSEUDO_SYM
)
578 return p2
->type
== PSEUDO_SYM
|| p2
->type
== PSEUDO_VAL
;
583 static int simplify_commutative_binop(struct instruction
*insn
)
585 if (!canonical_order(insn
->src1
, insn
->src2
)) {
586 switch_pseudo(insn
, &insn
->src1
, insn
, &insn
->src2
);
592 static inline int simple_pseudo(pseudo_t pseudo
)
594 return pseudo
->type
== PSEUDO_VAL
|| pseudo
->type
== PSEUDO_SYM
;
597 static int simplify_associative_binop(struct instruction
*insn
)
599 struct instruction
*def
;
600 pseudo_t pseudo
= insn
->src1
;
602 if (!simple_pseudo(insn
->src2
))
604 if (pseudo
->type
!= PSEUDO_REG
)
609 if (def
->opcode
!= insn
->opcode
)
611 if (!simple_pseudo(def
->src2
))
613 if (ptr_list_size((struct ptr_list
*)def
->target
->users
) != 1)
615 switch_pseudo(def
, &def
->src1
, insn
, &insn
->src2
);
619 static int simplify_constant_unop(struct instruction
*insn
)
621 long long val
= insn
->src1
->value
;
624 switch (insn
->opcode
) {
634 mask
= 1ULL << (insn
->size
-1);
635 res
&= mask
| (mask
-1);
637 replace_with_pseudo(insn
, value_pseudo(res
));
641 static int simplify_unop(struct instruction
*insn
)
643 if (dead_insn(insn
, &insn
->src1
, NULL
, NULL
))
645 if (constant(insn
->src1
))
646 return simplify_constant_unop(insn
);
650 static int simplify_one_memop(struct instruction
*insn
, pseudo_t orig
)
652 pseudo_t addr
= insn
->src
;
655 if (addr
->type
== PSEUDO_REG
) {
656 struct instruction
*def
= addr
->def
;
657 if (def
->opcode
== OP_SYMADDR
&& def
->src
) {
658 kill_use(&insn
->src
);
659 use_pseudo(insn
, def
->src
, &insn
->src
);
660 return REPEAT_CSE
| REPEAT_SYMBOL_CLEANUP
;
662 if (def
->opcode
== OP_ADD
) {
682 warning(insn
->pos
, "crazy programmer");
684 insn
->offset
+= off
->value
;
685 use_pseudo(insn
, new, &insn
->src
);
686 remove_usage(addr
, &insn
->src
);
687 return REPEAT_CSE
| REPEAT_SYMBOL_CLEANUP
;
691 * We walk the whole chain of adds/subs backwards. That's not
692 * only more efficient, but it allows us to find loops.
694 static int simplify_memop(struct instruction
*insn
)
697 pseudo_t orig
= insn
->src
;
700 one
= simplify_one_memop(insn
, orig
);
706 static long long get_cast_value(long long val
, int old_size
, int new_size
, int sign
)
710 if (sign
&& new_size
> old_size
) {
711 mask
= 1 << (old_size
-1);
713 val
|= ~(mask
| (mask
-1));
715 mask
= 1 << (new_size
-1);
716 return val
& (mask
| (mask
-1));
719 static int simplify_cast(struct instruction
*insn
)
721 struct symbol
*orig_type
;
725 if (dead_insn(insn
, &insn
->src
, NULL
, NULL
))
728 orig_type
= insn
->orig_type
;
732 /* Keep casts with pointer on either side (not only case of OP_PTRCAST) */
733 if (is_ptr_type(orig_type
) || is_ptr_type(insn
->type
))
736 orig_size
= orig_type
->bit_size
;
740 /* A cast of a constant? */
742 int sign
= orig_type
->ctype
.modifiers
& MOD_SIGNED
;
743 long long val
= get_cast_value(src
->value
, orig_size
, size
, sign
);
744 src
= value_pseudo(val
);
748 /* A cast of a "and" might be a no-op.. */
749 if (src
->type
== PSEUDO_REG
) {
750 struct instruction
*def
= src
->def
;
751 if (def
->opcode
== OP_AND
&& def
->size
>= size
) {
752 pseudo_t val
= def
->src2
;
753 if (val
->type
== PSEUDO_VAL
) {
754 unsigned long long value
= val
->value
;
755 if (!(value
>> (size
-1)))
761 if (size
== orig_size
) {
762 int op
= (orig_type
->ctype
.modifiers
& MOD_SIGNED
) ? OP_SCAST
: OP_CAST
;
763 if (insn
->opcode
== op
)
770 return replace_with_pseudo(insn
, src
);
773 static int simplify_select(struct instruction
*insn
)
775 pseudo_t cond
, src1
, src2
;
777 if (dead_insn(insn
, &insn
->src1
, &insn
->src2
, &insn
->src3
))
783 if (constant(cond
) || src1
== src2
) {
784 pseudo_t
*kill
, take
;
785 kill_use(&insn
->src1
);
786 take
= cond
->value
? src1
: src2
;
787 kill
= cond
->value
? &insn
->src3
: &insn
->src2
;
789 replace_with_pseudo(insn
, take
);
792 if (constant(src1
) && constant(src2
)) {
793 long long val1
= src1
->value
;
794 long long val2
= src2
->value
;
796 /* The pair 0/1 is special - replace with SETNE/SETEQ */
797 if ((val1
| val2
) == 1) {
798 int opcode
= OP_SET_EQ
;
803 insn
->opcode
= opcode
;
804 /* insn->src1 is already cond */
805 insn
->src2
= src1
; /* Zero */
812 static int is_in_range(pseudo_t src
, long long low
, long long high
)
819 return value
>= low
&& value
<= high
;
825 static int simplify_range(struct instruction
*insn
)
827 pseudo_t src1
, src2
, src3
;
832 if (src2
->type
!= PSEUDO_VAL
|| src3
->type
!= PSEUDO_VAL
)
834 if (is_in_range(src1
, src2
->value
, src3
->value
)) {
835 kill_instruction(insn
);
842 * Simplify "set_ne/eq $0 + br"
844 static int simplify_cond_branch(struct instruction
*br
, pseudo_t cond
, struct instruction
*def
, pseudo_t
*pp
)
846 use_pseudo(br
, *pp
, &br
->cond
);
847 remove_usage(cond
, &br
->cond
);
848 if (def
->opcode
== OP_SET_EQ
) {
849 struct basic_block
*true = br
->bb_true
;
850 struct basic_block
*false = br
->bb_false
;
857 static int simplify_branch(struct instruction
*insn
)
859 pseudo_t cond
= insn
->cond
;
864 /* Constant conditional */
865 if (constant(cond
)) {
866 insert_branch(insn
->bb
, insn
, cond
->value
? insn
->bb_true
: insn
->bb_false
);
871 if (insn
->bb_true
== insn
->bb_false
) {
872 struct basic_block
*bb
= insn
->bb
;
873 struct basic_block
*target
= insn
->bb_false
;
874 remove_bb_from_list(&target
->parents
, bb
, 1);
875 remove_bb_from_list(&bb
->children
, target
, 1);
876 insn
->bb_false
= NULL
;
877 kill_use(&insn
->cond
);
882 /* Conditional on a SETNE $0 or SETEQ $0 */
883 if (cond
->type
== PSEUDO_REG
) {
884 struct instruction
*def
= cond
->def
;
886 if (def
->opcode
== OP_SET_NE
|| def
->opcode
== OP_SET_EQ
) {
887 if (constant(def
->src1
) && !def
->src1
->value
)
888 return simplify_cond_branch(insn
, cond
, def
, &def
->src2
);
889 if (constant(def
->src2
) && !def
->src2
->value
)
890 return simplify_cond_branch(insn
, cond
, def
, &def
->src1
);
892 if (def
->opcode
== OP_SEL
) {
893 if (constant(def
->src2
) && constant(def
->src3
)) {
894 long long val1
= def
->src2
->value
;
895 long long val2
= def
->src3
->value
;
896 if (!val1
&& !val2
) {
897 insert_branch(insn
->bb
, insn
, insn
->bb_false
);
901 insert_branch(insn
->bb
, insn
, insn
->bb_true
);
905 struct basic_block
*true = insn
->bb_true
;
906 struct basic_block
*false = insn
->bb_false
;
907 insn
->bb_false
= true;
908 insn
->bb_true
= false;
910 use_pseudo(insn
, def
->src1
, &insn
->cond
);
911 remove_usage(cond
, &insn
->cond
);
915 if (def
->opcode
== OP_CAST
|| def
->opcode
== OP_SCAST
) {
916 int orig_size
= def
->orig_type
? def
->orig_type
->bit_size
: 0;
917 if (def
->size
> orig_size
) {
918 use_pseudo(insn
, def
->src
, &insn
->cond
);
919 remove_usage(cond
, &insn
->cond
);
927 static int simplify_switch(struct instruction
*insn
)
929 pseudo_t cond
= insn
->cond
;
931 struct multijmp
*jmp
;
935 val
= insn
->cond
->value
;
937 FOR_EACH_PTR(insn
->multijmp_list
, jmp
) {
939 if (jmp
->begin
> jmp
->end
)
941 if (val
>= jmp
->begin
&& val
<= jmp
->end
)
943 } END_FOR_EACH_PTR(jmp
);
944 warning(insn
->pos
, "Impossible case statement");
948 insert_branch(insn
->bb
, insn
, jmp
->target
);
952 int simplify_instruction(struct instruction
*insn
)
956 switch (insn
->opcode
) {
957 case OP_ADD
: case OP_MULS
:
958 case OP_AND
: case OP_OR
: case OP_XOR
:
959 case OP_AND_BOOL
: case OP_OR_BOOL
:
960 if (simplify_binop(insn
))
962 if (simplify_commutative_binop(insn
))
964 return simplify_associative_binop(insn
);
967 case OP_SET_EQ
: case OP_SET_NE
:
968 if (simplify_binop(insn
))
970 return simplify_commutative_binop(insn
);
973 case OP_DIVU
: case OP_DIVS
:
974 case OP_MODU
: case OP_MODS
:
976 case OP_LSR
: case OP_ASR
:
977 case OP_SET_LE
: case OP_SET_GE
:
978 case OP_SET_LT
: case OP_SET_GT
:
979 case OP_SET_B
: case OP_SET_A
:
980 case OP_SET_BE
: case OP_SET_AE
:
981 return simplify_binop(insn
);
983 case OP_NOT
: case OP_NEG
:
984 return simplify_unop(insn
);
985 case OP_LOAD
: case OP_STORE
:
986 return simplify_memop(insn
);
988 if (dead_insn(insn
, NULL
, NULL
, NULL
))
989 return REPEAT_CSE
| REPEAT_SYMBOL_CLEANUP
;
990 return replace_with_pseudo(insn
, insn
->symbol
);
995 return simplify_cast(insn
);
997 if (dead_insn(insn
, NULL
, NULL
, NULL
)) {
1001 return clean_up_phi(insn
);
1003 if (dead_insn(insn
, &insn
->phi_src
, NULL
, NULL
))
1007 return simplify_select(insn
);
1009 return simplify_branch(insn
);
1011 return simplify_switch(insn
);
1013 return simplify_range(insn
);