2 * Simplify - do instruction simplification before CSE
4 * Copyright (C) 2004 Linus Torvalds
8 // Instruction simplification
9 // --------------------------
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:
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)`.
45 #include "expression.h"
46 #include "linearize.h"
50 #include "flowgraph.h"
57 // check if a pseudo is a power of 2
58 static inline bool is_pow2(pseudo_t src
)
60 if (src
->type
!= PSEUDO_VAL
)
62 return is_power_of_2(src
->value
);
66 // find the trivial parent for a phi-source
67 static struct basic_block
*phi_parent(struct basic_block
*source
, pseudo_t pseudo
)
69 /* Can't go upwards if the pseudo is defined in the bb it came from.. */
70 if (pseudo
->type
== PSEUDO_REG
) {
71 struct instruction
*def
= pseudo
->def
;
72 if (def
->bb
== source
)
75 if (bb_list_size(source
->children
) != 1 || bb_list_size(source
->parents
) != 1)
77 return first_basic_block(source
->parents
);
81 // copy the phi-node's phisrcs into to given array
82 // @return: 0 if the the list contained the expected
83 // number of element, a positive number if there was
84 // more than expected and a negative one if less.
86 // :note: we can't reuse a function like linearize_ptr_list()
87 // because any VOIDs in the phi-list must be ignored here
88 // as in this context they mean 'entry has been removed'.
89 static int get_phisources(struct instruction
*sources
[], int nbr
, struct instruction
*insn
)
94 assert(insn
->opcode
== OP_PHI
);
95 FOR_EACH_PTR(insn
->phi_list
, phi
) {
96 struct instruction
*def
;
102 assert(def
->opcode
== OP_PHISOURCE
);
104 } END_FOR_EACH_PTR(phi
);
108 static int if_convert_phi(struct instruction
*insn
)
110 struct instruction
*array
[2];
111 struct basic_block
*parents
[3];
112 struct basic_block
*bb
, *bb1
, *bb2
, *source
;
113 struct instruction
*br
;
117 if (get_phisources(array
, 2, insn
))
119 if (linearize_ptr_list((struct ptr_list
*)bb
->parents
, (void **)parents
, 3) != 2)
121 p1
= array
[0]->phi_src
;
123 p2
= array
[1]->phi_src
;
126 /* Only try the simple "direct parents" case */
127 if ((bb1
!= parents
[0] || bb2
!= parents
[1]) &&
128 (bb1
!= parents
[1] || bb2
!= parents
[0]))
132 * See if we can find a common source for this..
134 source
= phi_parent(bb1
, p1
);
135 if (source
!= phi_parent(bb2
, p2
))
139 * Cool. We now know that 'source' is the exclusive
140 * parent of both phi-nodes, so the exit at the
141 * end of it fully determines which one it is, and
142 * we can turn it into a select.
144 * HOWEVER, right now we only handle regular
145 * conditional branches. No multijumps or computed
146 * stuff. Verify that here.
148 br
= last_instruction(source
->insns
);
149 if (!br
|| br
->opcode
!= OP_CBR
)
153 assert(br
->bb_false
);
156 * We're in business. Match up true/false with p1/p2.
158 if (br
->bb_true
== bb2
|| br
->bb_false
== bb1
) {
165 * OK, we can now replace that last
172 * select pseudo, p1, p2
175 * and remove the phi-node. If it then
176 * turns out that 'a' or 'b' is entirely
177 * empty (common case), and now no longer
178 * a phi-source, we'll be able to simplify
179 * the conditional branch too.
181 insert_select(source
, br
, insn
, p1
, p2
);
182 kill_instruction(insn
);
187 // detect trivial phi-nodes
188 // @insn: the phi-node
189 // @pseudo: the candidate resulting pseudo (NULL when starting)
190 // @return: the unique result if the phi-node is trivial, NULL otherwise
192 // A phi-node is trivial if it has a single possible result:
193 // * all operands are the same
194 // * the operands are themselves defined by a chain or cycle of phi-nodes
195 // and the set of all operands involved contains a single value
196 // not defined by these phi-nodes
198 // Since the result is unique, these phi-nodes can be removed.
199 static pseudo_t
trivial_phi(pseudo_t pseudo
, struct instruction
*insn
, struct pseudo_list
**list
)
201 pseudo_t target
= insn
->target
;
204 add_pseudo(list
, target
);
206 FOR_EACH_PTR(insn
->phi_list
, phi
) {
207 struct instruction
*def
;
215 src
= def
->phi_src
; // bypass OP_PHISRC & get the real source
226 if (DEF_OPCODE(def
, src
) == OP_PHI
) {
227 if (pseudo_in_list(*list
, src
))
229 if ((pseudo
= trivial_phi(pseudo
, def
, list
)))
233 } END_FOR_EACH_PTR(phi
);
235 return pseudo
? pseudo
: VOID
;
238 static int clean_up_phi(struct instruction
*insn
)
240 struct pseudo_list
*list
= NULL
;
243 if ((pseudo
= trivial_phi(NULL
, insn
, &list
))) {
244 convert_instruction_target(insn
, pseudo
);
245 kill_instruction(insn
);
249 return if_convert_phi(insn
);
252 static int delete_pseudo_user_list_entry(struct pseudo_user_list
**list
, pseudo_t
*entry
, int count
)
254 struct pseudo_user
*pu
;
256 FOR_EACH_PTR(*list
, pu
) {
257 if (pu
->userp
== entry
) {
258 MARK_CURRENT_DELETED(pu
);
262 } END_FOR_EACH_PTR(pu
);
265 if (pseudo_user_list_empty(*list
))
270 static inline void rem_usage(pseudo_t p
, pseudo_t
*usep
, int kill
)
272 if (has_use_list(p
)) {
273 delete_pseudo_user_list_entry(&p
->users
, usep
, 1);
274 if (kill
&& !p
->users
&& has_definition(p
))
275 kill_instruction(p
->def
);
279 static inline void remove_usage(pseudo_t p
, pseudo_t
*usep
)
281 rem_usage(p
, usep
, 1);
284 void kill_use(pseudo_t
*usep
)
289 rem_usage(p
, usep
, 1);
293 // Like kill_use() but do not (recursively) kill dead instructions
294 void remove_use(pseudo_t
*usep
)
298 rem_usage(p
, usep
, 0);
301 static void kill_use_list(struct pseudo_list
*list
)
304 FOR_EACH_PTR(list
, p
) {
307 kill_use(THIS_ADDRESS(p
));
308 } END_FOR_EACH_PTR(p
);
311 static void kill_asm(struct instruction
*insn
)
313 struct asm_constraint
*con
;
315 FOR_EACH_PTR(insn
->asm_rules
->inputs
, con
) {
316 kill_use(&con
->pseudo
);
317 } END_FOR_EACH_PTR(con
);
321 // kill an instruction
322 // @insn: the instruction to be killed
323 // @force: if unset, the normal case, the instruction is not killed
324 // if not free of possible side-effect; if set the instruction
325 // is unconditionally killed.
327 // The killed instruction is removed from its BB and the usage
328 // of all its operands are removed. The instruction is also
329 // marked as killed by setting its ->bb to NULL.
330 int kill_insn(struct instruction
*insn
, int force
)
332 if (!insn
|| !insn
->bb
)
335 switch (insn
->opcode
) {
338 kill_use(&insn
->src3
);
341 case OP_BINARY
... OP_BINCMP_END
:
342 kill_use(&insn
->src2
);
345 case OP_UNOP
... OP_UNOP_END
:
351 case OP_COMPUTEDGOTO
:
352 kill_use(&insn
->src1
);
356 kill_use_list(insn
->phi_list
);
361 /* a "pure" function can be killed too */
362 struct symbol
*fntype
= first_symbol(insn
->fntypes
);
364 if (!(fntype
->ctype
.modifiers
& MOD_PURE
))
367 kill_use_list(insn
->arguments
);
368 if (insn
->func
->type
== PSEUDO_REG
)
369 kill_use(&insn
->func
);
373 if (!force
&& insn
->is_volatile
)
375 kill_use(&insn
->src
);
381 kill_use(&insn
->src
);
382 kill_use(&insn
->target
);
404 return repeat_phase
|= REPEAT_CSE
;
407 static inline bool has_target(struct instruction
*insn
)
409 return opcode_table
[insn
->opcode
].flags
& OPF_TARGET
;
412 void remove_dead_insns(struct entrypoint
*ep
)
414 struct basic_block
*bb
;
416 FOR_EACH_PTR_REVERSE(ep
->bbs
, bb
) {
417 struct instruction
*insn
;
418 FOR_EACH_PTR_REVERSE(bb
->insns
, insn
) {
421 if (!has_target(insn
))
423 if (!has_users(insn
->target
))
424 kill_instruction(insn
);
425 } END_FOR_EACH_PTR_REVERSE(insn
);
426 } END_FOR_EACH_PTR_REVERSE(bb
);
429 static inline int constant(pseudo_t pseudo
)
431 return pseudo
->type
== PSEUDO_VAL
;
435 // is this same signed value when interpreted with both size?
436 static inline bool is_signed_constant(long long val
, unsigned osize
, unsigned nsize
)
438 return bits_extend(val
, osize
, 1) == bits_extend(val
, nsize
, 1);
442 // is @src generated by an instruction with the given opcode and size?
443 static inline pseudo_t
is_same_op(pseudo_t src
, int op
, unsigned osize
)
445 struct instruction
*def
;
447 if (src
->type
!= PSEUDO_REG
)
450 if (def
->opcode
!= op
)
452 if (def
->orig_type
->bit_size
!= osize
)
458 // replace the operand of an instruction
459 // @insn: the instruction
460 // @pp: the address of the instruction's operand
461 // @new: the new value for the operand
462 // @return: REPEAT_CSE.
463 static inline int replace_pseudo(struct instruction
*insn
, pseudo_t
*pp
, pseudo_t
new)
466 use_pseudo(insn
, new, pp
);
467 remove_usage(old
, pp
);
471 int replace_with_pseudo(struct instruction
*insn
, pseudo_t pseudo
)
473 convert_instruction_target(insn
, pseudo
);
474 return kill_instruction(insn
);
477 static inline int replace_with_value(struct instruction
*insn
, long long val
)
479 return replace_with_pseudo(insn
, value_pseudo(val
));
483 // replace a binop with an unop
484 // @insn: the instruction to be replaced
485 // @op: the instruction's new opcode
486 // @src: the instruction's new operand
487 // @return: REPEAT_CSE
488 static inline int replace_with_unop(struct instruction
*insn
, int op
, pseudo_t src
)
491 replace_pseudo(insn
, &insn
->src1
, src
);
492 remove_usage(insn
->src2
, &insn
->src2
);
497 // replace rightside's value
498 // @insn: the instruction to be replaced
499 // @op: the instruction's new opcode
500 // @src: the instruction's new operand
501 // @return: REPEAT_CSE
502 static inline int replace_binop_value(struct instruction
*insn
, int op
, long long val
)
505 insn
->src2
= value_pseudo(val
);
510 // replace binop's opcode and values
511 // @insn: the instruction to be replaced
512 // @op: the instruction's new opcode
513 // @return: REPEAT_CSE
514 static inline int replace_binop(struct instruction
*insn
, int op
, pseudo_t
*pa
, pseudo_t a
, pseudo_t
*pb
, pseudo_t b
)
519 use_pseudo(insn
, a
, pa
);
520 use_pseudo(insn
, b
, pb
);
521 remove_usage(olda
, pa
);
522 remove_usage(oldb
, pb
);
527 // replace the opcode of an instruction
528 // @return: REPEAT_CSE
529 static inline int replace_opcode(struct instruction
*insn
, int op
)
536 // create an instruction pair OUT(IN(a, b), c)
537 static int replace_insn_pair(struct instruction
*out
, int op_out
, struct instruction
*in
, int op_in
, pseudo_t a
, pseudo_t b
, pseudo_t c
)
539 pseudo_t old_a
= in
->src1
;
540 pseudo_t old_b
= in
->src2
;
541 pseudo_t old_1
= out
->src1
;
542 pseudo_t old_2
= out
->src2
;
544 use_pseudo(in
, a
, &in
->src1
);
545 use_pseudo(in
, b
, &in
->src2
);
546 use_pseudo(out
, in
->target
, &out
->src1
);
547 use_pseudo(out
, c
, &out
->src2
);
549 remove_usage(old_a
, &in
->src1
);
550 remove_usage(old_b
, &in
->src2
);
551 remove_usage(old_1
, &out
->src1
);
552 remove_usage(old_2
, &out
->src2
);
554 out
->opcode
= op_out
;
560 // create an instruction pair OUT(IN(a, b), c) with swapped opcodes
561 static inline int swap_insn(struct instruction
*out
, struct instruction
*in
, pseudo_t a
, pseudo_t b
, pseudo_t c
)
563 return replace_insn_pair(out
, in
->opcode
, in
, out
->opcode
, a
, b
, c
);
567 // create an instruction pair OUT(SELECT(a, b, c), d)
568 static int swap_select(struct instruction
*out
, struct instruction
*in
, pseudo_t a
, pseudo_t b
, pseudo_t c
, pseudo_t d
)
570 use_pseudo(in
, c
, &in
->src3
);
571 swap_insn(out
, in
, a
, b
, d
);
572 kill_use(&out
->src3
);
576 static inline int def_opcode(pseudo_t p
)
578 if (p
->type
!= PSEUDO_REG
)
580 return p
->def
->opcode
;
583 static unsigned int value_size(long long value
)
598 // try to determine the maximum size of bits in a pseudo
600 // Right now this only follow casts and constant values, but we
601 // could look at things like AND instructions, etc.
602 static unsigned int operand_size(struct instruction
*insn
, pseudo_t pseudo
)
604 unsigned int size
= insn
->size
;
606 if (pseudo
->type
== PSEUDO_REG
) {
607 struct instruction
*src
= pseudo
->def
;
608 if (src
&& src
->opcode
== OP_ZEXT
&& src
->orig_type
) {
609 unsigned int orig_size
= src
->orig_type
->bit_size
;
610 if (orig_size
< size
)
614 if (pseudo
->type
== PSEUDO_VAL
) {
615 unsigned int orig_size
= value_size(pseudo
->value
);
616 if (orig_size
< size
)
622 static pseudo_t
eval_op(int op
, unsigned size
, pseudo_t src1
, pseudo_t src2
)
624 /* FIXME! Verify signs and sizes!! */
625 long long left
= src1
->value
;
626 long long right
= src2
->value
;
627 unsigned long long ul
, ur
;
628 long long res
, mask
, bits
;
630 mask
= 1ULL << (size
-1);
631 bits
= mask
| (mask
-1);
665 if (left
== mask
&& right
== -1)
677 if (left
== mask
&& right
== -1)
707 /* Binary comparison */
742 // Warning: this should be done with the output size which may
743 // be different than the input size used here. But it differs
744 // only for compares which are not concerned since only returning
745 // 0 or 1 and for casts which are not handled here.
748 return value_pseudo(res
);
754 static inline pseudo_t
eval_unop(int op
, unsigned size
, pseudo_t src
)
756 return eval_op(op
, size
, src
, VOID
);
764 // try to simplify MASK(OR(AND(x, M'), b), M)
765 // @insn: the masking instruction
766 // @mask: the associated mask (M)
767 // @ora: one of the OR's operands, guaranteed to be PSEUDO_REG
768 // @orb: the other OR's operand
769 // @return: 0 if no changes have been made, one or more REPEAT_* flags otherwise.
770 static int simplify_mask_or_and(struct instruction
*insn
, unsigned long long mask
,
771 pseudo_t ora
, pseudo_t orb
)
773 unsigned long long omask
, nmask
;
774 struct instruction
*and = ora
->def
;
775 pseudo_t src2
= and->src2
;
777 if (and->opcode
!= OP_AND
)
782 nmask
= omask
& mask
;
784 // if (M' & M) == 0: ((a & M') | b) -> b
785 return replace_pseudo(insn
, &insn
->src1
, orb
);
787 if (!one_use(insn
->src1
))
788 return 0; // can't modify anything inside the OR
790 struct instruction
*or = insn
->src1
->def
;
791 pseudo_t
*arg
= (ora
== or->src1
) ? &or->src1
: &or->src2
;
792 // if (M' & M) == M: ((a & M') | b) -> (a | b)
793 return replace_pseudo(or, arg
, and->src1
);
795 if (nmask
!= omask
&& one_use(ora
)) {
796 // if (M' & M) != M': AND(a, M') -> AND(a, (M' & M))
797 and->src2
= value_pseudo(nmask
);
804 // try to simplify MASK(OR(a, b), M)
805 // @insn: the masking instruction
806 // @mask: the associated mask (M)
807 // @or: the OR instruction
808 // @return: 0 if no changes have been made, one or more REPEAT_* flags otherwise.
809 static int simplify_mask_or(struct instruction
*insn
, unsigned long long mask
, struct instruction
*or)
811 pseudo_t src1
= or->src1
;
812 pseudo_t src2
= or->src2
;
815 if (src1
->type
== PSEUDO_REG
) {
816 if ((rc
= simplify_mask_or_and(insn
, mask
, src1
, src2
)))
819 if (src2
->type
== PSEUDO_REG
) {
820 if ((rc
= simplify_mask_or_and(insn
, mask
, src2
, src1
)))
822 } else if (src2
->type
== PSEUDO_VAL
) {
823 unsigned long long oval
= src2
->value
;
824 unsigned long long nval
= oval
& mask
;
828 // if (C & M) == 0: OR(x, C) -> x
829 return replace_pseudo(insn
, &insn
->src1
, src1
);
832 // if (C & M) == M: OR(x, C) -> M
833 return replace_pseudo(insn
, &insn
->src1
, value_pseudo(mask
));
835 if (nval
!= oval
&& one_use(or->target
)) {
836 // if (C & M) != C: OR(x, C) -> OR(x, (C & M))
837 return replace_pseudo(or, &or->src2
, value_pseudo(nval
));
844 // try to simplify MASK(SHIFT(OR(a, b), S), M)
845 // @sh: the shift instruction
846 // @or: the OR instruction
847 // @mask: the mask associated to MASK (M):
848 // @return: 0 if no changes have been made, one or more REPEAT_* flags otherwise.
849 static int simplify_mask_shift_or(struct instruction
*sh
, struct instruction
*or, unsigned long long mask
)
851 unsigned long long smask
= bits_mask(sh
->size
);
852 int shift
= sh
->src2
->value
;
854 if (sh
->opcode
== OP_LSR
)
858 return simplify_mask_or(sh
, smask
& mask
, or);
861 static int simplify_mask_shift(struct instruction
*sh
, unsigned long long mask
)
863 struct instruction
*inner
;
865 if (!constant(sh
->src2
) || sh
->tainted
)
867 switch (DEF_OPCODE(inner
, sh
->src1
)) {
869 if (one_use(sh
->target
))
870 return simplify_mask_shift_or(sh
, inner
, mask
);
876 static pseudo_t
eval_insn(struct instruction
*insn
)
878 unsigned size
= insn
->size
;
880 if (opcode_table
[insn
->opcode
].flags
& OPF_COMPARE
)
881 size
= insn
->itype
->bit_size
;
882 return eval_op(insn
->opcode
, size
, insn
->src1
, insn
->src2
);
885 static long long check_shift_count(struct instruction
*insn
, unsigned long long uval
)
887 unsigned int size
= insn
->size
;
888 long long sval
= uval
;
897 sval
= sign_extend_safe(sval
, size
);
898 sval
= sign_extend_safe(sval
, bits_in_int
);
900 insn
->src2
= value_pseudo(sval
);
904 static int simplify_shift(struct instruction
*insn
, pseudo_t pseudo
, long long value
)
906 struct instruction
*def
;
907 unsigned long long mask
, omask
, nmask
;
908 unsigned long long nval
;
913 return replace_with_pseudo(insn
, pseudo
);
914 value
= check_shift_count(insn
, value
);
919 switch (insn
->opcode
) {
923 if (pseudo
->type
!= PSEUDO_REG
)
926 switch (def
->opcode
) {
929 if (def
== insn
) // cyclic DAG!
932 if (src2
->type
!= PSEUDO_VAL
)
935 if (nval
> insn
->size
|| nval
== 0)
938 if (def
->opcode
== OP_LSR
)
939 insn
->opcode
= OP_LSR
;
940 else if (value
>= size
)
946 // zext.N %t <- (O) %a
949 // zext.N %t <- (O) %a
951 insn
->opcode
= OP_LSR
;
956 size
= operand_size(insn
, pseudo
);
959 switch(DEF_OPCODE(def
, pseudo
)) {
961 // replace (A & M) >> S
962 // by (A >> S) & (M >> S)
963 if (!constant(def
->src2
))
965 mask
= bits_mask(insn
->size
- value
) << value
;
966 omask
= def
->src2
->value
;
967 nmask
= omask
& mask
;
969 return replace_with_value(insn
, 0);
971 return replace_pseudo(insn
, &insn
->src1
, def
->src1
);
972 if (!one_use(pseudo
))
974 def
->opcode
= OP_LSR
;
975 def
->src2
= insn
->src2
;
976 insn
->opcode
= OP_AND
;
977 insn
->src2
= value_pseudo(omask
>> value
);
980 goto case_shift_shift
;
982 mask
= bits_mask(size
);
983 return simplify_mask_shift_or(insn
, def
, mask
);
985 // replace ((x << S) >> S)
986 // by (x & (-1 >> S))
987 if (def
->src2
!= insn
->src2
)
989 mask
= bits_mask(insn
->size
- value
);
996 switch(DEF_OPCODE(def
, pseudo
)) {
998 // simplify (A & M) << S
999 if (!constant(def
->src2
))
1001 mask
= bits_mask(insn
->size
) >> value
;
1002 omask
= def
->src2
->value
;
1003 nmask
= omask
& mask
;
1005 return replace_with_value(insn
, 0);
1007 return replace_pseudo(insn
, &insn
->src1
, def
->src1
);
1008 // do not simplify into ((A << S) & (M << S))
1011 // replace ((x >> S) << S)
1012 // by (x & (-1 << S))
1013 if (def
->src2
!= insn
->src2
)
1015 mask
= bits_mask(insn
->size
- value
) << value
;
1018 mask
= bits_mask(size
);
1019 return simplify_mask_shift_or(insn
, def
, mask
);
1021 case_shift_shift
: // also for LSR - LSR
1022 if (def
== insn
) // cyclic DAG!
1025 if (src2
->type
!= PSEUDO_VAL
)
1028 if (nval
> insn
->size
)
1039 insn
->src2
= value_pseudo(value
);
1040 return replace_pseudo(insn
, &insn
->src1
, pseudo
->def
->src1
);
1043 return replace_with_value(insn
, 0);
1045 insn
->opcode
= OP_AND
;
1046 insn
->src2
= value_pseudo(mask
);
1047 return replace_pseudo(insn
, &insn
->src1
, def
->src1
);
1050 static int simplify_mul_div(struct instruction
*insn
, long long value
)
1052 unsigned long long sbit
= 1ULL << (insn
->size
- 1);
1053 unsigned long long bits
= sbit
| (sbit
- 1);
1056 return replace_with_pseudo(insn
, insn
->src1
);
1058 switch (insn
->opcode
) {
1061 return replace_with_pseudo(insn
, insn
->src2
);
1064 if (!(value
& sbit
)) // positive
1069 insn
->opcode
= OP_NEG
;
1077 static int simplify_seteq_setne(struct instruction
*insn
, long long value
)
1079 pseudo_t old
= insn
->src1
;
1080 struct instruction
*def
;
1085 if (value
!= 0 && value
!= 1)
1088 if (old
->type
!= PSEUDO_REG
)
1094 inverse
= (insn
->opcode
== OP_SET_NE
) == value
;
1095 if (!inverse
&& def
->size
== 1 && insn
->size
== 1) {
1097 // setne %r <- %s, $0
1099 // seteq %r <- %s, $1
1100 // by %s when boolean
1101 return replace_with_pseudo(insn
, old
);
1103 opcode
= def
->opcode
;
1108 if (def
->size
!= insn
->size
)
1110 if (def
->src2
->type
!= PSEUDO_VAL
)
1112 if (def
->src2
->value
!= 1)
1114 return replace_with_pseudo(insn
, old
);
1115 case OP_FPCMP
... OP_BINCMP_END
:
1117 // setcc.n %t <- %a, %b
1118 // setne.m %r <- %t, $0
1120 // setcc.n %t <- %a, %b
1121 // setcc.m %r <- %a, $b
1122 // and similar for setne/eq ... 0/1
1123 insn
->opcode
= inverse
? opcode_table
[opcode
].negate
: opcode
;
1124 insn
->itype
= def
->itype
;
1125 use_pseudo(insn
, def
->src1
, &insn
->src1
);
1126 use_pseudo(insn
, def
->src2
, &insn
->src2
);
1127 remove_usage(old
, &insn
->src1
);
1131 if (value
&& (def
->orig_type
->bit_size
== 1))
1136 // *ext.m %s <- (1) %a
1137 // setne.1 %r <- %s, $0
1139 // setne.1 %s <- %a, $0
1140 // and same for setne/eq ... 0/1
1141 insn
->itype
= def
->orig_type
;
1142 return replace_pseudo(insn
, &insn
->src1
, def
->src
);
1147 // trunc.n %s <- (o) %a
1148 // setne.m %r <- %s, $0
1150 // and.o %s <- %a, $((1 << o) - 1)
1151 // setne.m %r <- %s, $0
1152 // and same for setne/eq ... 0/1
1154 def
->opcode
= OP_AND
;
1155 def
->type
= def
->orig_type
;
1156 def
->size
= def
->type
->bit_size
;
1157 def
->src2
= value_pseudo(bits_mask(osize
));
1163 static int simplify_compare_constant(struct instruction
*insn
, long long value
)
1165 unsigned long long bits
= bits_mask(insn
->itype
->bit_size
);
1166 struct instruction
*def
;
1167 pseudo_t src1
, src2
;
1171 switch (insn
->opcode
) {
1173 if (!value
) // (x < 0) --> 0
1174 return replace_with_pseudo(insn
, value_pseudo(0));
1175 if (value
== 1) // (x < 1) --> (x == 0)
1176 return replace_binop_value(insn
, OP_SET_EQ
, 0);
1177 else if (value
== bits
) // (x < ~0) --> (x != ~0)
1178 return replace_binop_value(insn
, OP_SET_NE
, value
);
1179 else // (x < y) --> (x <= (y-1))
1180 changed
|= replace_binop_value(insn
, OP_SET_BE
, value
- 1);
1183 if (!value
) // (x >= 0) --> 1
1184 return replace_with_pseudo(insn
, value_pseudo(1));
1185 if (value
== 1) // (x >= 1) --> (x != 0)
1186 return replace_binop_value(insn
, OP_SET_NE
, 0);
1187 else if (value
== bits
) // (x >= ~0) --> (x == ~0)
1188 return replace_binop_value(insn
, OP_SET_EQ
, value
);
1189 else // (x >= y) --> (x > (y-1)
1190 changed
|= replace_binop_value(insn
, OP_SET_A
, value
- 1);
1193 if (!value
) // (x <= 0) --> (x == 0)
1194 return replace_opcode(insn
, OP_SET_EQ
);
1195 if (value
== bits
) // (x <= ~0) --> 1
1196 return replace_with_pseudo(insn
, value_pseudo(1));
1197 if (value
== (bits
- 1)) // (x <= ~1) --> (x != ~0)
1198 return replace_binop_value(insn
, OP_SET_NE
, bits
);
1199 if (value
== (bits
>> 1)) // (x u<= SMAX) --> (x s>= 0)
1200 changed
|= replace_binop_value(insn
, OP_SET_GE
, 0);
1203 if (!value
) // (x > 0) --> (x != 0)
1204 return replace_opcode(insn
, OP_SET_NE
);
1205 if (value
== bits
) // (x > ~0) --> 0
1206 return replace_with_pseudo(insn
, value_pseudo(0));
1207 if (value
== (bits
- 1)) // (x > ~1) --> (x == ~0)
1208 return replace_binop_value(insn
, OP_SET_EQ
, bits
);
1209 if (value
== (bits
>> 1)) // (x u> SMAX) --> (x s< 0)
1210 changed
|= replace_binop_value(insn
, OP_SET_LT
, 0);
1216 value
= src2
->value
;
1217 switch (DEF_OPCODE(def
, src1
)) {
1218 case OP_SEXT
: // sext(x) cmp C --> x cmp trunc(C)
1219 osize
= def
->orig_type
->bit_size
;
1220 if (is_signed_constant(value
, osize
, def
->size
)) {
1221 insn
->itype
= def
->orig_type
;
1222 insn
->src2
= value_pseudo(zero_extend(value
, osize
));
1223 return replace_pseudo(insn
, &insn
->src1
, def
->src
);
1225 switch (insn
->opcode
) {
1227 if (value
>= sign_bit(osize
)) {
1228 replace_binop_value(insn
, OP_SET_GE
, 0);
1229 return replace_pseudo(insn
, &insn
->src1
, def
->src
);
1233 if (value
>= sign_bit(osize
)) {
1234 replace_binop_value(insn
, OP_SET_LT
, 0);
1235 return replace_pseudo(insn
, &insn
->src1
, def
->src
);
1238 case OP_SET_LT
: case OP_SET_LE
:
1239 if (value
>= sign_bit(osize
))
1240 return replace_with_value(insn
, 1);
1242 return replace_with_value(insn
, 0);
1244 case OP_SET_GE
: case OP_SET_GT
:
1245 if (value
>= sign_bit(osize
))
1246 return replace_with_value(insn
, 0);
1248 return replace_with_value(insn
, 1);
1253 osize
= def
->orig_type
->bit_size
;
1254 bits
= bits_mask(osize
);
1255 if (value
<= bits
) {
1256 const struct opcode_table
*op
= &opcode_table
[insn
->opcode
];
1257 if (op
->flags
& OPF_SIGNED
)
1258 insn
->opcode
= op
->sign
;
1259 insn
->itype
= def
->orig_type
;
1260 return replace_pseudo(insn
, &insn
->src1
, def
->src
);
1262 switch (insn
->opcode
) {
1263 case OP_SET_LT
: case OP_SET_LE
:
1264 if (sign_extend(value
, def
->size
) > (long long)bits
)
1265 return replace_with_value(insn
, 1);
1267 return replace_with_value(insn
, 0);
1269 case OP_SET_GE
: case OP_SET_GT
:
1270 if (sign_extend(value
, def
->size
) > (long long)bits
)
1271 return replace_with_value(insn
, 0);
1273 return replace_with_value(insn
, 1);
1275 case OP_SET_B
: case OP_SET_BE
:
1276 return replace_with_value(insn
, 1);
1277 case OP_SET_AE
: case OP_SET_A
:
1278 return replace_with_value(insn
, 0);
1285 static int simplify_constant_mask(struct instruction
*insn
, unsigned long long mask
)
1287 pseudo_t old
= insn
->src1
;
1288 unsigned long long omask
;
1289 unsigned long long nmask
;
1290 struct instruction
*def
;
1293 switch (DEF_OPCODE(def
, old
)) {
1294 case OP_FPCMP
... OP_BINCMP_END
:
1298 return simplify_mask_or(insn
, mask
, def
);
1301 return simplify_mask_shift(def
, mask
);
1303 osize
= def
->orig_type
->bit_size
;
1306 omask
= (1ULL << osize
) - 1;
1307 nmask
= mask
& omask
;
1309 // the AND mask is redundant
1310 return replace_with_pseudo(insn
, old
);
1311 if (nmask
!= mask
) {
1312 // can use a smaller mask
1313 insn
->src2
= value_pseudo(nmask
);
1321 static int simplify_const_rightadd(struct instruction
*def
, struct instruction
*insn
)
1323 unsigned size
= insn
->size
;
1324 pseudo_t src2
= insn
->src2
;
1326 switch (def
->opcode
) {
1328 if (constant(def
->src1
)) { // (C - y) + D --> eval(C+D) - y
1329 pseudo_t val
= eval_op(OP_ADD
, size
, def
->src1
, src2
);
1330 insn
->opcode
= OP_SUB
;
1331 use_pseudo(insn
, def
->src2
, &insn
->src2
);
1332 return replace_pseudo(insn
, &insn
->src1
, val
);
1339 static int simplify_constant_rightside(struct instruction
*insn
)
1341 long long value
= insn
->src2
->value
;
1342 long long sbit
= 1ULL << (insn
->size
- 1);
1343 long long bits
= sbit
| (sbit
- 1);
1346 switch (insn
->opcode
) {
1348 if ((value
& bits
) == bits
)
1349 return replace_with_pseudo(insn
, insn
->src2
);
1350 goto case_neutral_zero
;
1353 if ((value
& bits
) == bits
) {
1354 insn
->opcode
= OP_NOT
;
1360 return replace_with_pseudo(insn
, insn
->src1
);
1364 insn
->opcode
= OP_ADD
;
1365 insn
->src2
= eval_unop(OP_NEG
, insn
->size
, insn
->src2
);
1366 changed
= REPEAT_CSE
;
1370 return replace_with_pseudo(insn
, insn
->src1
);
1371 if (insn
->src1
->type
== PSEUDO_REG
) // (x # y) + z
1372 changed
|= simplify_const_rightadd(insn
->src1
->def
, insn
);
1377 return simplify_shift(insn
, insn
->src1
, value
);
1379 case OP_MODU
: case OP_MODS
:
1381 return replace_with_value(insn
, 0);
1384 case OP_DIVU
: case OP_DIVS
:
1386 return simplify_mul_div(insn
, value
);
1390 return replace_with_pseudo(insn
, insn
->src2
);
1391 if ((value
& bits
) == bits
)
1392 return replace_with_pseudo(insn
, insn
->src1
);
1393 return simplify_constant_mask(insn
, value
);
1397 if ((changed
= simplify_seteq_setne(insn
, value
)))
1400 case OP_SET_LT
: case OP_SET_LE
: case OP_SET_GE
: case OP_SET_GT
:
1401 case OP_SET_B
: case OP_SET_BE
: case OP_SET_AE
: case OP_SET_A
:
1402 return simplify_compare_constant(insn
, value
);
1407 static int simplify_const_leftsub(struct instruction
*insn
, struct instruction
*def
)
1409 unsigned size
= insn
->size
;
1410 pseudo_t src1
= insn
->src1
;
1412 switch (def
->opcode
) {
1414 if (constant(def
->src2
)) { // C - (y + D) --> eval(C-D) - y
1415 insn
->src1
= eval_op(OP_SUB
, size
, src1
, def
->src2
);
1416 return replace_pseudo(insn
, &insn
->src2
, def
->src1
);
1420 if (constant(def
->src1
)) { // C - (D - z) --> z + eval(C-D)
1421 pseudo_t val
= eval_op(OP_SUB
, size
, src1
, def
->src1
);
1422 insn
->opcode
= OP_ADD
;
1423 use_pseudo(insn
, def
->src2
, &insn
->src1
);
1424 return replace_pseudo(insn
, &insn
->src2
, val
);
1431 static int simplify_constant_leftside(struct instruction
*insn
)
1433 long long value
= insn
->src1
->value
;
1435 switch (insn
->opcode
) {
1436 case OP_ADD
: case OP_OR
: case OP_XOR
:
1438 return replace_with_pseudo(insn
, insn
->src2
);
1442 case OP_LSR
: case OP_ASR
:
1446 return replace_with_pseudo(insn
, insn
->src1
);
1449 if (!value
) // (0 - x) --> -x
1450 return replace_with_unop(insn
, OP_NEG
, insn
->src2
);
1451 if (insn
->src2
->type
== PSEUDO_REG
)
1452 return simplify_const_leftsub(insn
, insn
->src2
->def
);
1458 static int simplify_constant_binop(struct instruction
*insn
)
1460 pseudo_t res
= eval_insn(insn
);
1465 return replace_with_pseudo(insn
, res
);
1468 static int simplify_binop_same_args(struct instruction
*insn
, pseudo_t arg
)
1470 switch (insn
->opcode
) {
1472 case OP_SET_LT
: case OP_SET_GT
:
1473 case OP_SET_B
: case OP_SET_A
:
1474 if (Wtautological_compare
)
1475 warning(insn
->pos
, "self-comparison always evaluates to false");
1478 return replace_with_value(insn
, 0);
1481 case OP_SET_LE
: case OP_SET_GE
:
1482 case OP_SET_BE
: case OP_SET_AE
:
1483 if (Wtautological_compare
)
1484 warning(insn
->pos
, "self-comparison always evaluates to true");
1485 return replace_with_value(insn
, 1);
1489 return replace_with_pseudo(insn
, arg
);
1498 static int simplify_binop(struct instruction
*insn
)
1500 if (constant(insn
->src1
)) {
1501 if (constant(insn
->src2
))
1502 return simplify_constant_binop(insn
);
1503 return simplify_constant_leftside(insn
);
1505 if (constant(insn
->src2
))
1506 return simplify_constant_rightside(insn
);
1507 if (insn
->src1
== insn
->src2
)
1508 return simplify_binop_same_args(insn
, insn
->src1
);
1512 static int switch_pseudo(struct instruction
*insn1
, pseudo_t
*pp1
, struct instruction
*insn2
, pseudo_t
*pp2
)
1514 pseudo_t p1
= *pp1
, p2
= *pp2
;
1516 use_pseudo(insn1
, p2
, pp1
);
1517 use_pseudo(insn2
, p1
, pp2
);
1518 remove_usage(p1
, pp1
);
1519 remove_usage(p2
, pp2
);
1524 // check if the given pseudos are in canonical order
1526 // The canonical order is VOID < UNDEF < PHI < REG < ARG < SYM < VAL
1527 // The rationale is:
1528 // * VALs at right (they don't need a definition)
1529 // * REGs at left (they need a defining instruction)
1530 // * SYMs & ARGs between REGs & VALs
1531 // * REGs & ARGs are ordered between themselves by their internal number
1532 // * SYMs are ordered between themselves by address
1533 // * VOID, UNDEF and PHI are uninteresting (but VOID should have type 0)
1534 static int canonical_order(pseudo_t p1
, pseudo_t p2
)
1539 /* symbol/constants on the right */
1546 return p1
->sym
<= p2
->sym
;
1549 return p1
->nr
<= p2
->nr
;
1555 static int canonicalize_commutative(struct instruction
*insn
)
1557 if (canonical_order(insn
->src1
, insn
->src2
))
1560 switch_pseudo(insn
, &insn
->src1
, insn
, &insn
->src2
);
1561 return repeat_phase
|= REPEAT_CSE
;
1564 static int canonicalize_compare(struct instruction
*insn
)
1566 if (canonical_order(insn
->src1
, insn
->src2
))
1569 switch_pseudo(insn
, &insn
->src1
, insn
, &insn
->src2
);
1570 insn
->opcode
= opcode_table
[insn
->opcode
].swap
;
1571 return repeat_phase
|= REPEAT_CSE
;
1574 static inline int simple_pseudo(pseudo_t pseudo
)
1576 return pseudo
->type
== PSEUDO_VAL
|| pseudo
->type
== PSEUDO_SYM
;
1580 // test if, in the given BB, the ordering of 2 instructions
1581 static bool insn_before(struct basic_block
*bb
, struct instruction
*x
, struct instruction
*y
)
1583 struct instruction
*insn
;
1585 FOR_EACH_PTR(bb
->insns
, insn
) {
1590 } END_FOR_EACH_PTR(insn
);
1595 // check if it safe for a pseudo to be used by an instruction
1596 static inline bool can_move_to(pseudo_t src
, struct instruction
*dst
)
1598 struct basic_block
*bbs
, *bbd
;
1599 struct instruction
*def
;
1601 if (!one_use(dst
->target
))
1603 if (src
->type
!= PSEUDO_REG
)
1610 return insn_before(bbs
, def
, dst
);
1612 return domtree_dominates(bbs
, bbd
);
1615 static int simplify_associative_binop(struct instruction
*insn
)
1617 struct instruction
*def
;
1618 pseudo_t pseudo
= insn
->src1
;
1620 if (!simple_pseudo(insn
->src2
))
1622 if (pseudo
->type
!= PSEUDO_REG
)
1627 if (def
->opcode
!= insn
->opcode
)
1629 if (!simple_pseudo(def
->src2
))
1631 if (constant(def
->src2
) && constant(insn
->src2
)) {
1632 // (x # C) # K --> x # eval(C # K)
1633 insn
->src2
= eval_op(insn
->opcode
, insn
->size
, insn
->src2
, def
->src2
);
1634 return replace_pseudo(insn
, &insn
->src1
, def
->src1
);
1636 if (!one_use(def
->target
))
1638 switch_pseudo(def
, &def
->src1
, insn
, &insn
->src2
);
1642 static int simplify_add_one_side(struct instruction
*insn
, pseudo_t
*p1
, pseudo_t
*p2
)
1644 struct instruction
*defr
= NULL
;
1645 struct instruction
*def
;
1646 pseudo_t src1
= *p1
;
1647 pseudo_t src2
= *p2
;
1649 switch (DEF_OPCODE(def
, src1
)) {
1651 if (DEF_OPCODE(defr
, *p2
) == OP_MUL
) {
1652 if (defr
->src2
== def
->src2
&& can_move_to(def
->src2
, defr
)) {
1653 // ((x * z) + (y * z)) into ((x + y) * z)
1654 swap_insn(insn
, defr
, def
->src1
, defr
->src1
, def
->src2
);
1657 if (defr
->src1
== def
->src1
&& can_move_to(def
->src1
, defr
)) {
1658 // ((z * x) + (z * y)) into ((x + y) * z)
1659 swap_insn(insn
, defr
, def
->src2
, defr
->src2
, def
->src1
);
1662 if (defr
->src1
== def
->src2
&& can_move_to(def
->src1
, defr
)) {
1663 // ((x * z) + (z * y)) into ((x + y) * z)
1664 swap_insn(insn
, defr
, def
->src1
, defr
->src2
, def
->src2
);
1670 case OP_NEG
: // (-x + y) --> (y - x)
1671 return replace_binop(insn
, OP_SUB
, &insn
->src1
, src2
, &insn
->src2
, def
->src
);
1674 if (def
->src2
== src2
) // (x - y) + y --> x
1675 return replace_with_pseudo(insn
, def
->src1
);
1681 static int simplify_add(struct instruction
*insn
)
1683 return simplify_add_one_side(insn
, &insn
->src1
, &insn
->src2
) ||
1684 simplify_add_one_side(insn
, &insn
->src2
, &insn
->src1
);
1687 static int simplify_sub(struct instruction
*insn
)
1689 pseudo_t src1
= insn
->src1
;
1690 pseudo_t src2
= insn
->src2
;
1691 struct instruction
*def
;
1693 switch (DEF_OPCODE(def
, src1
)) {
1695 if (def
->src1
== src2
) // (x + y) - x --> y
1696 return replace_with_pseudo(insn
, def
->src2
);
1697 if (def
->src2
== src2
) // (x + y) - y --> x
1698 return replace_with_pseudo(insn
, def
->src1
);
1702 switch (DEF_OPCODE(def
, src2
)) {
1704 if (src1
== def
->src1
) // x - (x + z) --> -z
1705 return replace_with_unop(insn
, OP_NEG
, def
->src2
);
1706 if (src1
== def
->src2
) // x - (y + x) --> -y
1707 return replace_with_unop(insn
, OP_NEG
, def
->src1
);
1709 case OP_NEG
: // (x - -y) --> (x + y)
1710 insn
->opcode
= OP_ADD
;
1711 return replace_pseudo(insn
, &insn
->src2
, def
->src
);
1717 static int simplify_compare(struct instruction
*insn
)
1719 pseudo_t src1
= insn
->src1
;
1720 pseudo_t src2
= insn
->src2
;
1721 struct instruction
*def
= NULL
;
1725 switch (DEF_OPCODE(def
, src1
)) {
1726 case OP_SEXT
: case OP_ZEXT
:
1727 osize
= def
->orig_type
->bit_size
;
1728 if ((src
= is_same_op(src2
, def
->opcode
, osize
))) {
1729 const struct opcode_table
*op
= &opcode_table
[insn
->opcode
];
1730 if ((def
->opcode
== OP_ZEXT
) && (op
->flags
& OPF_SIGNED
))
1731 insn
->opcode
= op
->sign
;
1732 insn
->itype
= def
->orig_type
;
1733 replace_pseudo(insn
, &insn
->src1
, def
->src
);
1734 return replace_pseudo(insn
, &insn
->src2
, src
);
1741 static int simplify_and_one_side(struct instruction
*insn
, pseudo_t
*p1
, pseudo_t
*p2
)
1743 struct instruction
*def
, *defr
= NULL
;
1744 pseudo_t src1
= *p1
;
1746 switch (DEF_OPCODE(def
, src1
)) {
1748 if (def
->src
== *p2
)
1749 return replace_with_value(insn
, 0);
1751 case OP_BINCMP
... OP_BINCMP_END
:
1752 if (DEF_OPCODE(defr
, *p2
) == opcode_negate(def
->opcode
)) {
1753 if (def
->src1
== defr
->src1
&& def
->src2
== defr
->src2
)
1754 return replace_with_value(insn
, 0);
1758 if (DEF_OPCODE(defr
, *p2
) == OP_OR
) {
1759 if (defr
->src2
== def
->src2
&& can_move_to(def
->src2
, defr
)) {
1760 // ((x | z) & (y | z)) into ((x & y) | z)
1761 swap_insn(insn
, defr
, def
->src1
, defr
->src1
, def
->src2
);
1764 if (defr
->src1
== def
->src1
&& can_move_to(def
->src1
, defr
)) {
1765 // ((z | x) & (z | y)) into ((x & y) | z)
1766 swap_insn(insn
, defr
, def
->src2
, defr
->src2
, def
->src1
);
1769 if (defr
->src1
== def
->src2
&& can_move_to(def
->src1
, defr
)) {
1770 // ((x | z) & (z | y)) into ((x & y) | z)
1771 swap_insn(insn
, defr
, def
->src1
, defr
->src2
, def
->src2
);
1776 case OP_SHL
: case OP_LSR
: case OP_ASR
:
1777 if (DEF_OPCODE(defr
, *p2
) == def
->opcode
&& defr
->src2
== def
->src2
) {
1778 if (can_move_to(def
->src1
, defr
)) {
1779 // SHIFT(x, s) & SHIFT(y, s) --> SHIFT((x & y), s)
1780 swap_insn(insn
, defr
, def
->src1
, defr
->src1
, def
->src2
);
1789 static int simplify_and(struct instruction
*insn
)
1791 return simplify_and_one_side(insn
, &insn
->src1
, &insn
->src2
) ||
1792 simplify_and_one_side(insn
, &insn
->src2
, &insn
->src1
);
1795 static int simplify_ior_one_side(struct instruction
*insn
, pseudo_t
*p1
, pseudo_t
*p2
)
1797 struct instruction
*def
, *defr
= NULL
;
1798 pseudo_t src1
= *p1
;
1800 switch (DEF_OPCODE(def
, src1
)) {
1802 if (DEF_OPCODE(defr
, *p2
) == OP_AND
) {
1803 if (defr
->src2
== def
->src2
&& can_move_to(def
->src2
, defr
)) {
1804 // ((x & z) | (y & z)) into ((x | y) & z)
1805 swap_insn(insn
, defr
, def
->src1
, defr
->src1
, def
->src2
);
1808 if (defr
->src1
== def
->src1
&& can_move_to(def
->src1
, defr
)) {
1809 // ((z & x) | (z & y)) into ((x | y) & z)
1810 swap_insn(insn
, defr
, def
->src2
, defr
->src2
, def
->src1
);
1813 if (defr
->src1
== def
->src2
&& can_move_to(def
->src1
, defr
)) {
1814 // ((x & z) | (z & y)) into ((x | y) & z)
1815 swap_insn(insn
, defr
, def
->src1
, defr
->src2
, def
->src2
);
1821 if (def
->src
== *p2
)
1822 return replace_with_value(insn
, bits_mask(insn
->size
));
1824 case OP_BINCMP
... OP_BINCMP_END
:
1825 if (DEF_OPCODE(defr
, *p2
) == opcode_negate(def
->opcode
)) {
1826 if (def
->src1
== defr
->src1
&& def
->src2
== defr
->src2
)
1827 return replace_with_value(insn
, 1);
1830 case OP_SHL
: case OP_LSR
: case OP_ASR
:
1831 if (DEF_OPCODE(defr
, *p2
) == def
->opcode
&& defr
->src2
== def
->src2
) {
1832 if (can_move_to(def
->src1
, defr
)) {
1833 // SHIFT(x, s) | SHIFT(y, s) --> SHIFT((x | y), s)
1834 swap_insn(insn
, defr
, def
->src1
, defr
->src1
, def
->src2
);
1843 static int simplify_ior(struct instruction
*insn
)
1845 return simplify_ior_one_side(insn
, &insn
->src1
, &insn
->src2
) ||
1846 simplify_ior_one_side(insn
, &insn
->src2
, &insn
->src1
);
1849 static int simplify_xor_one_side(struct instruction
*insn
, pseudo_t
*p1
, pseudo_t
*p2
)
1851 struct instruction
*def
, *defr
= NULL
;
1852 pseudo_t src1
= *p1
;
1854 switch (DEF_OPCODE(def
, src1
)) {
1856 if (DEF_OPCODE(defr
, *p2
) == OP_AND
) {
1857 if (defr
->src2
== def
->src2
&& can_move_to(def
->src2
, defr
)) {
1858 // ((x & z) ^ (y & z)) into ((x ^ y) & z)
1859 swap_insn(insn
, defr
, def
->src1
, defr
->src1
, def
->src2
);
1862 if (defr
->src1
== def
->src1
&& can_move_to(def
->src1
, defr
)) {
1863 // ((z & x) ^ (z & y)) into ((x ^ y) & z)
1864 swap_insn(insn
, defr
, def
->src2
, defr
->src2
, def
->src1
);
1867 if (defr
->src1
== def
->src2
&& can_move_to(def
->src1
, defr
)) {
1868 // ((x & z) ^ (z & y)) into ((x ^ y) & z)
1869 swap_insn(insn
, defr
, def
->src1
, defr
->src2
, def
->src2
);
1875 if (def
->src
== *p2
)
1876 return replace_with_value(insn
, bits_mask(insn
->size
));
1878 case OP_BINCMP
... OP_BINCMP_END
:
1879 if (DEF_OPCODE(defr
, *p2
) == opcode_negate(def
->opcode
)) {
1880 if (def
->src1
== defr
->src1
&& def
->src2
== defr
->src2
)
1881 return replace_with_value(insn
, 1);
1884 case OP_SHL
: case OP_LSR
: case OP_ASR
:
1885 if (DEF_OPCODE(defr
, *p2
) == def
->opcode
&& defr
->src2
== def
->src2
) {
1886 if (can_move_to(def
->src1
, defr
)) {
1887 // SHIFT(x, s) ^ SHIFT(y, s) --> SHIFT((x ^ y), s)
1888 swap_insn(insn
, defr
, def
->src1
, defr
->src1
, def
->src2
);
1897 static int simplify_xor(struct instruction
*insn
)
1899 return simplify_xor_one_side(insn
, &insn
->src1
, &insn
->src2
) ||
1900 simplify_xor_one_side(insn
, &insn
->src2
, &insn
->src1
);
1903 static int simplify_constant_unop(struct instruction
*insn
)
1905 long long val
= insn
->src1
->value
;
1906 long long res
, mask
;
1908 switch (insn
->opcode
) {
1916 mask
= 1ULL << (insn
->orig_type
->bit_size
-1);
1918 val
|= ~(mask
| (mask
-1));
1927 mask
= 1ULL << (insn
->size
-1);
1928 res
&= mask
| (mask
-1);
1930 return replace_with_value(insn
, res
);
1933 static int simplify_unop(struct instruction
*insn
)
1935 struct instruction
*def
;
1936 pseudo_t src
= insn
->src
;
1939 return simplify_constant_unop(insn
);
1941 switch (insn
->opcode
) {
1943 switch (DEF_OPCODE(def
, src
)) {
1945 if (!constant(def
->src2
))
1947 insn
->opcode
= OP_SUB
; // ~(x + C) --> ~C - x
1948 src
= eval_unop(OP_NOT
, insn
->size
, def
->src2
);
1949 use_pseudo(insn
, def
->src1
, &insn
->src2
);
1950 return replace_pseudo(insn
, &insn
->src1
, src
);
1952 insn
->opcode
= OP_SUB
; // ~(-x) --> x - 1
1953 insn
->src2
= value_pseudo(1);
1954 return replace_pseudo(insn
, &insn
->src1
, def
->src
);
1955 case OP_NOT
: // ~(~x) --> x
1956 return replace_with_pseudo(insn
, def
->src
);
1958 if (!constant(def
->src1
))
1960 insn
->opcode
= OP_ADD
; // ~(C - x) --> x + ~C
1961 insn
->src2
= eval_unop(OP_NOT
, insn
->size
, def
->src1
);
1962 return replace_pseudo(insn
, &insn
->src1
, def
->src2
);
1964 if (!constant(def
->src2
))
1966 insn
->opcode
= OP_XOR
; // ~(x ^ C) --> x ^ ~C
1967 insn
->src2
= eval_unop(OP_NOT
, insn
->size
, def
->src2
);
1968 return replace_pseudo(insn
, &insn
->src1
, def
->src1
);
1972 switch (DEF_OPCODE(def
, src
)) {
1974 if (!constant(def
->src2
))
1976 insn
->opcode
= OP_SUB
; // -(x + C) --> (-C - x)
1977 src
= eval_unop(OP_NEG
, insn
->size
, def
->src2
);
1978 use_pseudo(insn
, def
->src1
, &insn
->src2
);
1979 return replace_pseudo(insn
, &insn
->src1
, src
);
1980 case OP_NEG
: // -(-x) --> x
1981 return replace_with_pseudo(insn
, def
->src
);
1983 insn
->opcode
= OP_ADD
; // -(~x) --> x + 1
1984 insn
->src2
= value_pseudo(1);
1985 return replace_pseudo(insn
, &insn
->src1
, def
->src
);
1987 insn
->opcode
= OP_SUB
; // -(x - y) --> y - x
1988 use_pseudo(insn
, def
->src1
, &insn
->src2
);
1989 return replace_pseudo(insn
, &insn
->src1
, def
->src2
);
1998 static int simplify_one_memop(struct instruction
*insn
, pseudo_t orig
)
2000 pseudo_t addr
= insn
->src
;
2003 if (addr
->type
== PSEUDO_REG
) {
2004 struct instruction
*def
= addr
->def
;
2005 if (def
->opcode
== OP_SYMADDR
&& def
->src
) {
2006 kill_use(&insn
->src
);
2007 use_pseudo(insn
, def
->src
, &insn
->src
);
2010 if (def
->opcode
== OP_ADD
) {
2026 if (new == orig
|| new == addr
) {
2030 * If some BB have been removed it is possible that this
2031 * memop is in fact part of a dead BB. In this case
2032 * we must not warn since nothing is wrong.
2033 * If not part of a dead BB this will be redone after
2034 * the BBs have been cleaned up.
2036 if (repeat_phase
& REPEAT_CFG_CLEANUP
)
2038 warning(insn
->pos
, "crazy programmer");
2039 replace_pseudo(insn
, &insn
->src
, VOID
);
2042 insn
->offset
+= off
->value
;
2043 replace_pseudo(insn
, &insn
->src
, new);
2048 // simplify memops instructions
2050 // :note: We walk the whole chain of adds/subs backwards.
2051 // That's not only more efficient, but it allows us to find loops.
2052 static int simplify_memop(struct instruction
*insn
)
2055 pseudo_t orig
= insn
->src
;
2058 one
= simplify_one_memop(insn
, orig
);
2064 static int simplify_cast(struct instruction
*insn
)
2066 unsigned long long mask
;
2067 struct instruction
*def
;
2068 pseudo_t src
= insn
->src
;
2073 /* A cast of a constant? */
2075 return simplify_constant_unop(insn
);
2077 // can merge with the previous instruction?
2080 switch (def_opcode(src
)) {
2083 if (val
->type
!= PSEUDO_VAL
)
2085 /* A cast of a AND might be a no-op.. */
2086 switch (insn
->opcode
) {
2090 def
->opcode
= OP_TRUNC
;
2091 def
->orig_type
= def
->type
;
2092 def
->type
= insn
->type
;
2095 insn
->opcode
= OP_AND
;
2097 mask
&= (1ULL << size
) - 1;
2098 insn
->src2
= value_pseudo(mask
);
2102 if (val
->value
& (1 << (def
->size
- 1)))
2104 // OK, sign bit is 0
2109 // and.n %b <- %a, M
2110 // *ext.m %c <- (n) %b
2113 // and.m %c <- %b, M
2114 // For ZEXT, the mask will always be small
2115 // enough. For SEXT, it can only be done if
2116 // the mask force the sign bit to 0.
2117 def
->opcode
= OP_ZEXT
;
2118 def
->orig_type
= insn
->orig_type
;
2119 def
->type
= insn
->type
;
2120 def
->size
= insn
->size
;
2121 insn
->opcode
= OP_AND
;
2126 case OP_FPCMP
... OP_BINCMP_END
:
2127 switch (insn
->opcode
) {
2129 if (insn
->size
== 1)
2135 // setcc.n %t <- %a, %b
2136 // zext.m %r <- (n) %t
2138 // setcc.m %r <- %a, %b
2139 // and same for s/zext/trunc/
2140 insn
->opcode
= def
->opcode
;
2141 insn
->itype
= def
->itype
;
2142 use_pseudo(insn
, def
->src2
, &insn
->src2
);
2143 return replace_pseudo(insn
, &insn
->src1
, def
->src1
);
2147 switch (insn
->opcode
) {
2149 mask
= bits_mask(insn
->size
);
2150 return simplify_mask_or(insn
, mask
, def
);
2155 if (insn
->opcode
!= OP_TRUNC
)
2157 mask
= bits_mask(insn
->size
);
2158 return simplify_mask_shift(def
, mask
);
2160 switch (insn
->opcode
) {
2162 insn
->orig_type
= def
->orig_type
;
2163 return replace_pseudo(insn
, &insn
->src1
, def
->src
);
2165 if (size
!= def
->orig_type
->bit_size
)
2167 insn
->opcode
= OP_AND
;
2168 insn
->src2
= value_pseudo((1ULL << def
->size
) - 1);
2169 return replace_pseudo(insn
, &insn
->src1
, def
->src
);
2173 switch (insn
->opcode
) {
2175 insn
->opcode
= OP_ZEXT
;
2178 insn
->orig_type
= def
->orig_type
;
2179 return replace_pseudo(insn
, &insn
->src
, def
->src
);
2183 switch (insn
->opcode
) {
2185 osize
= def
->orig_type
->bit_size
;
2187 return replace_with_pseudo(insn
, def
->src
);
2189 insn
->opcode
= def
->opcode
;
2190 insn
->orig_type
= def
->orig_type
;
2191 return replace_pseudo(insn
, &insn
->src
, def
->src
);
2193 switch (insn
->opcode
) {
2195 insn
->orig_type
= def
->orig_type
;
2196 return replace_pseudo(insn
, &insn
->src
, def
->src
);
2204 static int simplify_select(struct instruction
*insn
)
2206 pseudo_t cond
, src1
, src2
;
2207 struct instruction
*def
;
2214 return replace_with_pseudo(insn
, cond
->value
? src1
: src2
);
2216 return replace_with_pseudo(insn
, src1
);
2218 if (constant(src1
) && constant(src2
)) {
2219 long long val1
= src1
->value
;
2220 long long val2
= src2
->value
;
2222 /* The pair 0/1 is special - replace with SETNE/SETEQ */
2223 if ((val1
| val2
) == 1) {
2224 int opcode
= OP_SET_EQ
;
2229 insn
->opcode
= opcode
;
2230 /* insn->src1 is already cond */
2231 insn
->src2
= src1
; /* Zero */
2235 if (cond
== src2
&& is_zero(src1
)) // SEL(x, 0, x) --> 0
2236 return replace_with_pseudo(insn
, src1
);
2237 if (cond
== src1
&& is_zero(src2
)) // SEL(x, x, 0) --> x
2238 return replace_with_pseudo(insn
, cond
);
2240 switch (DEF_OPCODE(def
, cond
)) {
2242 if (src1
== def
->src1
&& src2
== def
->src2
)
2243 return replace_with_pseudo(insn
, src2
); // SEL(x==y,x,y) --> y
2244 if (src2
== def
->src1
&& src1
== def
->src2
)
2245 return replace_with_pseudo(insn
, src2
); // SEL(y==x,x,y) --> y
2248 if (src1
== def
->src1
&& src2
== def
->src2
)
2249 return replace_with_pseudo(insn
, src1
); // SEL(x!=y,x,y) --> x
2250 if (src2
== def
->src1
&& src1
== def
->src2
)
2251 return replace_with_pseudo(insn
, src1
); // SEL(y!=x,x,y) --> x
2254 if (constant(def
->src2
) && constant(def
->src3
)) {
2255 // Is the def of the conditional another select?
2256 // And if that one results in a "zero or not", use the
2257 // original conditional instead.
2258 // SEL(SEL(x, C, 0), y, z) --> SEL(x, y, z)
2259 // SEL(SEL(x, C, 0), C, 0) --> SEL(x, C, 0) == cond
2260 // SEL(SEL(x, 0, C), y, z) --> SEL(x, z, y)
2261 // SEL(SEL(x, C1, C2), y, z) --> y
2262 if (!def
->src3
->value
) {
2263 if ((src1
== def
->src2
) && (src2
== def
->src3
))
2264 return replace_with_pseudo(insn
, cond
);
2265 return replace_pseudo(insn
, &insn
->cond
, def
->cond
);
2267 if (!def
->src2
->value
) {
2268 switch_pseudo(insn
, &insn
->src2
, insn
, &insn
->src3
);
2269 return replace_pseudo(insn
, &insn
->cond
, def
->cond
);
2271 // both values must be non-zero
2272 return replace_with_pseudo(insn
, src1
);
2275 if (is_pow2(def
->src2
) && is_pow2(src1
) && is_zero(src2
) && insn
->size
== def
->size
&& one_use(cond
)) {
2276 unsigned s1
= log2_exact(def
->src2
->value
);
2277 unsigned s2
= log2_exact(insn
->src2
->value
);
2281 return replace_with_pseudo(insn
, cond
);
2283 // SEL(x & A, B, 0) --> SHIFT(x & A, S)
2284 insn
->opcode
= (s1
< s2
) ? OP_SHL
: OP_LSR
;
2285 shift
= (s1
< s2
) ? (s2
- s1
) : (s1
- s2
);
2286 insn
->src2
= value_pseudo(shift
);
2292 switch (DEF_OPCODE(def
, src1
)) {
2293 case OP_ADD
: case OP_OR
: case OP_XOR
:
2294 if ((def
->src1
== src2
) && can_move_to(cond
, def
)) {
2295 // SEL(x, OP(y,z), y) --> OP(SEL(x, z, 0), y)
2296 swap_select(insn
, def
, cond
, def
->src2
, value_pseudo(0), src2
);
2299 if ((def
->src2
== src2
) && can_move_to(cond
, def
)) {
2300 // SEL(x, OP(z,y), y) --> OP(SEL(x, z, 0), y)
2301 swap_select(insn
, def
, cond
, def
->src1
, value_pseudo(0), src2
);
2307 switch (DEF_OPCODE(def
, src2
)) {
2308 case OP_ADD
: case OP_OR
: case OP_XOR
:
2309 if ((def
->src1
== src1
) && can_move_to(cond
, def
)) {
2310 // SEL(x, y, OP(y,z)) --> OP(SEL(x, 0, z), y)
2311 swap_select(insn
, def
, cond
, value_pseudo(0), def
->src2
, src1
);
2314 if ((def
->src2
== src1
) && can_move_to(cond
, def
)) {
2315 // SEL(x, y, OP(z,y)) --> OP(SEL(x, 0, z), y)
2316 swap_select(insn
, def
, cond
, value_pseudo(0), def
->src1
, src1
);
2324 static int is_in_range(pseudo_t src
, long long low
, long long high
)
2328 switch (src
->type
) {
2331 return value
>= low
&& value
<= high
;
2337 static int simplify_range(struct instruction
*insn
)
2339 pseudo_t src1
, src2
, src3
;
2344 if (src2
->type
!= PSEUDO_VAL
|| src3
->type
!= PSEUDO_VAL
)
2346 if (is_in_range(src1
, src2
->value
, src3
->value
)) {
2347 kill_instruction(insn
);
2354 // simplify SET_NE/EQ $0 + BR
2355 static int simplify_cond_branch(struct instruction
*br
, struct instruction
*def
, pseudo_t newcond
)
2357 replace_pseudo(br
, &br
->cond
, newcond
);
2358 if (def
->opcode
== OP_SET_EQ
) {
2359 struct basic_block
*tmp
= br
->bb_true
;
2360 br
->bb_true
= br
->bb_false
;
2366 static int simplify_branch(struct instruction
*insn
)
2368 pseudo_t cond
= insn
->cond
;
2370 /* Constant conditional */
2371 if (constant(cond
)) {
2372 insert_branch(insn
->bb
, insn
, cond
->value
? insn
->bb_true
: insn
->bb_false
);
2377 if (insn
->bb_true
== insn
->bb_false
) {
2378 struct basic_block
*bb
= insn
->bb
;
2379 struct basic_block
*target
= insn
->bb_false
;
2380 remove_bb_from_list(&target
->parents
, bb
, 1);
2381 remove_bb_from_list(&bb
->children
, target
, 1);
2382 insn
->bb_false
= NULL
;
2383 kill_use(&insn
->cond
);
2385 insn
->opcode
= OP_BR
;
2386 return REPEAT_CSE
|REPEAT_CFG_CLEANUP
;
2389 /* Conditional on a SETNE $0 or SETEQ $0 */
2390 if (cond
->type
== PSEUDO_REG
) {
2391 struct instruction
*def
= cond
->def
;
2393 if (def
->opcode
== OP_SET_NE
|| def
->opcode
== OP_SET_EQ
) {
2394 if (constant(def
->src1
) && !def
->src1
->value
)
2395 return simplify_cond_branch(insn
, def
, def
->src2
);
2396 if (constant(def
->src2
) && !def
->src2
->value
)
2397 return simplify_cond_branch(insn
, def
, def
->src1
);
2399 if (def
->opcode
== OP_SEL
) {
2400 if (constant(def
->src2
) && constant(def
->src3
)) {
2401 long long val1
= def
->src2
->value
;
2402 long long val2
= def
->src3
->value
;
2403 if (!val1
&& !val2
) {
2404 insert_branch(insn
->bb
, insn
, insn
->bb_false
);
2408 insert_branch(insn
->bb
, insn
, insn
->bb_true
);
2412 struct basic_block
*tmp
= insn
->bb_true
;
2413 insn
->bb_true
= insn
->bb_false
;
2414 insn
->bb_false
= tmp
;
2416 return replace_pseudo(insn
, &insn
->cond
, def
->src1
);
2419 if (def
->opcode
== OP_SEXT
|| def
->opcode
== OP_ZEXT
)
2420 return replace_pseudo(insn
, &insn
->cond
, def
->src
);
2425 static int simplify_switch(struct instruction
*insn
)
2427 pseudo_t cond
= insn
->cond
;
2429 struct multijmp
*jmp
;
2431 if (!constant(cond
))
2433 val
= insn
->cond
->value
;
2435 FOR_EACH_PTR(insn
->multijmp_list
, jmp
) {
2437 if (jmp
->begin
> jmp
->end
)
2439 if (val
>= jmp
->begin
&& val
<= jmp
->end
)
2441 } END_FOR_EACH_PTR(jmp
);
2442 warning(insn
->pos
, "Impossible case statement");
2446 insert_branch(insn
->bb
, insn
, jmp
->target
);
2450 static struct basic_block
*is_label(pseudo_t pseudo
)
2452 struct instruction
*def
;
2454 if (DEF_OPCODE(def
, pseudo
) != OP_LABEL
)
2456 return def
->bb_true
;
2459 static int simplify_cgoto(struct instruction
*insn
)
2461 struct basic_block
*target
, *bb
= insn
->bb
;
2462 struct basic_block
*bbt
, *bbf
;
2463 struct instruction
*def
;
2464 struct multijmp
*jmp
;
2466 switch (DEF_OPCODE(def
, insn
->src
)) {
2467 case OP_SEL
: // CGOTO(SEL(x, L1, L2)) --> CBR x, L1, L2
2468 if ((bbt
= is_label(def
->src2
)) && (bbf
= is_label(def
->src3
))) {
2469 insn
->opcode
= OP_CBR
;
2470 insn
->bb_true
= bbt
;
2471 insn
->bb_false
= bbf
;
2472 return replace_pseudo(insn
, &insn
->src1
, def
->cond
);
2476 target
= def
->bb_true
;
2479 FOR_EACH_PTR(insn
->multijmp_list
, jmp
) {
2480 if (jmp
->target
== target
)
2482 remove_bb_from_list(&jmp
->target
->parents
, bb
, 1);
2483 remove_bb_from_list(&bb
->children
, jmp
->target
, 1);
2484 MARK_CURRENT_DELETED(jmp
);
2485 } END_FOR_EACH_PTR(jmp
);
2486 kill_use(&insn
->src
);
2487 insn
->opcode
= OP_BR
;
2488 insn
->bb_true
= target
;
2489 return REPEAT_CSE
|REPEAT_CFG_CLEANUP
;
2494 static int simplify_setval(struct instruction
*insn
)
2496 struct expression
*val
= insn
->val
;
2498 switch (val
->type
) {
2500 insn
->opcode
= OP_LABEL
;
2501 insn
->bb_true
= val
->symbol
->bb_target
;
2509 int simplify_instruction(struct instruction
*insn
)
2514 flags
= opcode_table
[insn
->opcode
].flags
;
2515 if (flags
& OPF_TARGET
) {
2516 if (!has_users(insn
->target
))
2517 return kill_instruction(insn
);
2519 if (flags
& OPF_COMMU
)
2520 canonicalize_commutative(insn
) ;
2521 if (flags
& OPF_COMPARE
)
2522 canonicalize_compare(insn
) ;
2523 if (flags
& OPF_BINOP
) {
2524 if ((changed
= simplify_binop(insn
)))
2527 if (flags
& OPF_ASSOC
) {
2528 if ((changed
= simplify_associative_binop(insn
)))
2531 if (flags
& OPF_UNOP
) {
2532 if ((changed
= simplify_unop(insn
)))
2536 switch (insn
->opcode
) {
2537 case OP_ADD
: return simplify_add(insn
);
2538 case OP_SUB
: return simplify_sub(insn
);
2539 case OP_AND
: return simplify_and(insn
);
2540 case OP_OR
: return simplify_ior(insn
);
2541 case OP_XOR
: return simplify_xor(insn
);
2553 case OP_BINCMP
... OP_BINCMP_END
:
2554 return simplify_compare(insn
);
2557 return simplify_memop(insn
);
2559 return replace_with_pseudo(insn
, insn
->src
);
2560 case OP_SEXT
: case OP_ZEXT
:
2562 return simplify_cast(insn
);
2564 case OP_FCVTU
: case OP_FCVTS
:
2565 case OP_UCVTF
: case OP_SCVTF
:
2571 return replace_with_pseudo(insn
, insn
->src
);
2575 return simplify_setval(insn
);
2580 return clean_up_phi(insn
);
2584 return simplify_select(insn
);
2586 return simplify_branch(insn
);
2588 return simplify_switch(insn
);
2589 case OP_COMPUTEDGOTO
:
2590 return simplify_cgoto(insn
);
2592 return simplify_range(insn
);