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 struct basic_block
*trivial_common_parent(struct basic_block
*s1
, pseudo_t p1
,
29 struct basic_block
*s2
, pseudo_t p2
)
31 s1
= phi_parent(s1
, p1
);
32 s2
= phi_parent(s2
, p2
);
38 static void clear_phi(struct instruction
*insn
)
43 FOR_EACH_PTR(insn
->phi_list
, phi
) {
44 *THIS_ADDRESS(phi
) = VOID
;
45 } END_FOR_EACH_PTR(phi
);
48 static int if_convert_phi(struct instruction
*insn
)
51 struct basic_block
*parents
[3];
52 struct basic_block
*bb
, *bb1
, *bb2
, *source
;
53 struct instruction
*br
;
57 if (linearize_ptr_list((struct ptr_list
*)insn
->phi_list
, (void **)array
, 3) != 2)
59 if (linearize_ptr_list((struct ptr_list
*)bb
->parents
, (void **)parents
, 3) != 2)
61 p1
= array
[0]->def
->src1
;
62 bb1
= array
[0]->def
->bb
;
63 p2
= array
[1]->def
->src1
;
64 bb2
= array
[1]->def
->bb
;
66 /* Only try the simple "direct parents" case */
67 if ((bb1
!= parents
[0] || bb2
!= parents
[1]) &&
68 (bb1
!= parents
[1] || bb2
!= parents
[0]))
72 * See if we can find a common source for this..
74 source
= trivial_common_parent(bb1
, p1
, bb2
, p2
);
79 * Cool. We now know that 'source' is the exclusive
80 * parent of both phi-nodes, so the exit at the
81 * end of it fully determines which one it is, and
82 * we can turn it into a select.
84 * HOWEVER, right now we only handle regular
85 * conditional branches. No multijumps or computed
86 * stuff. Verify that here.
88 br
= last_instruction(source
->insns
);
89 if (!br
|| br
->opcode
!= OP_BR
)
96 * We're in business. Match up true/false with p1/p2.
98 if (br
->bb_true
== bb2
|| br
->bb_false
== bb1
) {
105 * Ok, we can now replace that last
112 * select pseudo, p1, p2
115 * and remove the phi-node. If it then
116 * turns out that 'a' or 'b' is entirely
117 * empty (common case), and now no longer
118 * a phi-source, we'll be able to simplify
119 * the conditional branch too.
121 insert_select(source
, br
, insn
, p1
, p2
);
126 static int clean_up_phi(struct instruction
*insn
)
129 struct instruction
*last
;
134 FOR_EACH_PTR(insn
->phi_list
, phi
) {
135 struct instruction
*def
;
139 if (def
->src1
== VOID
|| !def
->bb
)
142 if (last
->src1
!= def
->src1
)
147 } END_FOR_EACH_PTR(phi
);
150 pseudo_t pseudo
= last
? last
->src1
: VOID
;
151 convert_instruction_target(insn
, pseudo
);
156 return if_convert_phi(insn
);
159 static inline void remove_usage(pseudo_t p
, pseudo_t
*usep
)
161 if (has_use_list(p
)) {
162 delete_ptr_list_entry((struct ptr_list
**)&p
->users
, usep
, 1);
164 kill_instruction(p
->def
);
168 void kill_use(pseudo_t
*usep
)
173 remove_usage(p
, usep
);
177 void kill_instruction(struct instruction
*insn
)
179 if (!insn
|| !insn
->bb
)
182 switch (insn
->opcode
) {
183 case OP_BINARY
... OP_BINCMP_END
:
185 kill_use(&insn
->src1
);
186 kill_use(&insn
->src2
);
187 repeat_phase
|= REPEAT_CSE
;
190 case OP_NOT
: case OP_NEG
:
192 kill_use(&insn
->src1
);
193 repeat_phase
|= REPEAT_CSE
;
198 repeat_phase
|= REPEAT_CSE
;
203 repeat_phase
|= REPEAT_CSE
;
205 repeat_phase
|= REPEAT_SYMBOL_CLEANUP
;
211 * Kill trivially dead instructions
213 static int dead_insn(struct instruction
*insn
, pseudo_t
*src1
, pseudo_t
*src2
)
216 FOR_EACH_PTR(insn
->target
->users
, usep
) {
219 } END_FOR_EACH_PTR(usep
);
227 static inline int constant(pseudo_t pseudo
)
229 return pseudo
->type
== PSEUDO_VAL
;
232 static int replace_with_pseudo(struct instruction
*insn
, pseudo_t pseudo
)
234 convert_instruction_target(insn
, pseudo
);
239 static int simplify_constant_rightside(struct instruction
*insn
)
241 long long value
= insn
->src2
->value
;
243 switch (insn
->opcode
) {
246 insn
->opcode
= OP_ADD
;
247 insn
->src2
= value_pseudo(-value
);
252 case OP_OR
: case OP_XOR
:
253 case OP_SHL
: case OP_SHR
:
255 return replace_with_pseudo(insn
, insn
->src1
);
258 case OP_AND
: case OP_MUL
:
260 return replace_with_pseudo(insn
, insn
->src2
);
266 static int simplify_constant_leftside(struct instruction
*insn
)
268 long long value
= insn
->src1
->value
;
270 switch (insn
->opcode
) {
271 case OP_ADD
: case OP_OR
: case OP_XOR
:
273 return replace_with_pseudo(insn
, insn
->src2
);
276 case OP_SHL
: case OP_SHR
:
277 case OP_AND
: case OP_MUL
:
279 return replace_with_pseudo(insn
, insn
->src1
);
285 static int simplify_constant_binop(struct instruction
*insn
)
287 /* FIXME! Verify signs and sizes!! */
288 long long left
= insn
->src1
->value
;
289 long long right
= insn
->src2
->value
;
292 switch (insn
->opcode
) {
300 /* FIXME! Check sign! */
306 /* FIXME! Check sign! */
312 /* FIXME! Check sign! */
319 /* FIXME! Check sign! */
339 /* Binary comparison */
347 /* FIXME! Check sign! */
351 /* FIXME! Check sign! */
355 /* FIXME! Check sign! */
359 /* FIXME! Check sign! */
363 /* FIXME! Check sign! */
364 res
= (unsigned long long) left
< (unsigned long long) right
;
367 /* FIXME! Check sign! */
368 res
= (unsigned long long) left
> (unsigned long long) right
;
371 /* FIXME! Check sign! */
372 res
= (unsigned long long) left
<= (unsigned long long) right
;
375 /* FIXME! Check sign! */
376 res
= (unsigned long long) left
>= (unsigned long long) right
;
381 mask
= 1ULL << (insn
->size
-1);
382 res
&= mask
| (mask
-1);
384 /* FIXME!! Sign??? */
385 replace_with_pseudo(insn
, value_pseudo(res
));
389 static int simplify_binop(struct instruction
*insn
)
391 if (dead_insn(insn
, &insn
->src1
, &insn
->src2
))
393 if (constant(insn
->src1
)) {
394 if (constant(insn
->src2
))
395 return simplify_constant_binop(insn
);
396 return simplify_constant_leftside(insn
);
398 if (constant(insn
->src2
))
399 return simplify_constant_rightside(insn
);
403 static int simplify_constant_unop(struct instruction
*insn
)
408 static int simplify_unop(struct instruction
*insn
)
410 if (dead_insn(insn
, &insn
->src1
, NULL
))
412 if (constant(insn
->src1
))
413 return simplify_constant_unop(insn
);
417 static int simplify_memop(struct instruction
*insn
)
419 pseudo_t addr
= insn
->src
;
422 if (addr
->type
== PSEUDO_REG
) {
423 struct instruction
*def
= addr
->def
;
424 if (def
->opcode
== OP_SETVAL
&& def
->src
) {
425 kill_use(&insn
->src
);
426 use_pseudo(def
->src
, &insn
->src
);
427 return REPEAT_CSE
| REPEAT_SYMBOL_CLEANUP
;
429 if (def
->opcode
== OP_ADD
) {
444 insn
->offset
+= off
->value
;
445 use_pseudo(new, &insn
->src
);
446 remove_usage(addr
, &insn
->src
);
447 return REPEAT_CSE
| REPEAT_SYMBOL_CLEANUP
;
450 int simplify_instruction(struct instruction
*insn
)
453 static struct instruction
*last_setcc
;
454 struct instruction
*setcc
= last_setcc
;
460 switch (insn
->opcode
) {
461 case OP_BINARY
... OP_BINCMP_END
:
462 return simplify_binop(insn
);
464 case OP_NOT
: case OP_NEG
:
465 return simplify_unop(insn
);
466 case OP_LOAD
: case OP_STORE
:
467 return simplify_memop(insn
);
469 if (dead_insn(insn
, NULL
, NULL
))
470 return REPEAT_CSE
| REPEAT_SYMBOL_CLEANUP
;
473 if (dead_insn(insn
, NULL
, NULL
)) {
477 return clean_up_phi(insn
);
479 if (dead_insn(insn
, &insn
->src1
, NULL
))
486 assert(setcc
&& setcc
->bb
);
487 if (dead_insn(insn
, &insn
->src1
, &insn
->src2
)) {
492 if (!constant(cond
) && insn
->src1
!= insn
->src2
)
495 kill_use(&setcc
->cond
);
496 replace_with_pseudo(insn
, cond
->value
? insn
->src1
: insn
->src2
);
500 if (!cond
|| !constant(cond
))
502 insert_branch(insn
->bb
, insn
, cond
->value
? insn
->bb_true
: insn
->bb_false
);