2 * Flow - walk the linearized flowgraph, simplifying it as we
5 * Copyright (C) 2004 Linus Torvalds
16 #include "expression.h"
17 #include "linearize.h"
20 unsigned long bb_generation
;
23 * Dammit, if we have a phi-node followed by a conditional
24 * branch on that phi-node, we should damn well be able to
25 * do something about the source. Maybe.
27 static int rewrite_branch(struct basic_block
*bb
,
28 struct basic_block
**ptr
,
29 struct basic_block
*old
,
30 struct basic_block
*new)
32 if (*ptr
!= old
|| new == old
)
35 /* We might find new if-conversions or non-dominating CSEs */
36 repeat_phase
|= REPEAT_CSE
;
38 replace_bb_in_list(&bb
->children
, old
, new, 1);
39 remove_bb_from_list(&old
->parents
, bb
, 1);
40 add_bb(&new->parents
, bb
);
45 * Return the known truth value of a pseudo, or -1 if
48 static int pseudo_truth_value(pseudo_t pseudo
)
50 switch (pseudo
->type
) {
52 return !!pseudo
->value
;
55 struct instruction
*insn
= pseudo
->def
;
56 if (insn
->opcode
== OP_SETVAL
&& insn
->target
== pseudo
) {
57 struct expression
*expr
= insn
->val
;
59 /* A symbol address is always considered true.. */
62 if (expr
->type
== EXPR_VALUE
)
73 * Does a basic block depend on the pseudos that "src" defines?
75 static int bb_depends_on(struct basic_block
*target
, struct basic_block
*src
)
79 FOR_EACH_PTR(src
->defines
, pseudo
) {
80 if (pseudo_in_list(target
->needs
, pseudo
))
82 } END_FOR_EACH_PTR(pseudo
);
87 * When we reach here, we have:
88 * - a basic block that ends in a conditional branch and
89 * that has no side effects apart from the pseudos it
91 * - the phi-node that the conditional branch depends on
92 * - full pseudo liveness information
94 * We need to check if any of the _sources_ of the phi-node
95 * may be constant, and not actually need this block at all.
97 static int try_to_simplify_bb(struct basic_block
*bb
, struct instruction
*first
, struct instruction
*second
)
102 FOR_EACH_PTR(first
->phi_list
, phi
) {
103 struct instruction
*def
= phi
->def
;
104 struct basic_block
*source
, *target
;
106 struct instruction
*br
;
113 if (!pseudo
|| !source
)
115 br
= last_instruction(source
->insns
);
118 if (br
->opcode
!= OP_BR
)
120 true = pseudo_truth_value(pseudo
);
123 target
= true ? second
->bb_true
: second
->bb_false
;
124 if (bb_depends_on(target
, bb
))
126 changed
|= rewrite_branch(source
, &br
->bb_true
, bb
, target
);
127 changed
|= rewrite_branch(source
, &br
->bb_false
, bb
, target
);
128 } END_FOR_EACH_PTR(phi
);
132 static int bb_has_side_effects(struct basic_block
*bb
)
134 struct instruction
*insn
;
135 FOR_EACH_PTR(bb
->insns
, insn
) {
136 switch (insn
->opcode
) {
138 /* Fixme! This should take "const" etc into account */
146 /* Fixme! This should take "volatile" etc into account */
152 } END_FOR_EACH_PTR(insn
);
156 static int simplify_phi_branch(struct basic_block
*bb
, struct instruction
*br
)
158 pseudo_t cond
= br
->cond
;
159 struct instruction
*def
;
161 if (cond
->type
!= PSEUDO_REG
)
164 if (def
->bb
!= bb
|| def
->opcode
!= OP_PHI
)
166 if (bb_has_side_effects(bb
))
168 return try_to_simplify_bb(bb
, def
, br
);
171 static int simplify_branch_branch(struct basic_block
*bb
, struct instruction
*br
,
172 struct basic_block
**target_p
, int true)
174 struct basic_block
*target
= *target_p
, *final
;
175 struct instruction
*insn
;
180 insn
= last_instruction(target
->insns
);
181 if (!insn
|| insn
->opcode
!= OP_BR
|| insn
->cond
!= br
->cond
)
184 * Ahhah! We've found a branch to a branch on the same conditional!
185 * Now we just need to see if we can rewrite the branch..
188 final
= true ? insn
->bb_true
: insn
->bb_false
;
189 if (bb_has_side_effects(target
))
190 goto try_to_rewrite_target
;
191 if (bb_depends_on(final
, target
))
192 goto try_to_rewrite_target
;
193 return rewrite_branch(bb
, target_p
, target
, final
);
195 try_to_rewrite_target
:
197 * If we're the only parent, at least we can rewrite the
198 * now-known second branch.
200 if (bb_list_size(target
->parents
) != 1)
202 insert_branch(target
, insn
, final
);
206 static int simplify_one_branch(struct basic_block
*bb
, struct instruction
*br
)
208 if (simplify_phi_branch(bb
, br
))
210 return simplify_branch_branch(bb
, br
, &br
->bb_true
, 1) |
211 simplify_branch_branch(bb
, br
, &br
->bb_false
, 0);
214 static int simplify_branch_nodes(struct entrypoint
*ep
)
217 struct basic_block
*bb
;
219 FOR_EACH_PTR(ep
->bbs
, bb
) {
220 struct instruction
*br
= last_instruction(bb
->insns
);
222 if (!br
|| br
->opcode
!= OP_BR
|| !br
->bb_false
)
224 changed
|= simplify_one_branch(bb
, br
);
225 } END_FOR_EACH_PTR(bb
);
230 * This is called late - when we have intra-bb liveness information..
232 int simplify_flow(struct entrypoint
*ep
)
234 return simplify_branch_nodes(ep
);
237 static inline void concat_user_list(struct pseudo_ptr_list
*src
, struct pseudo_ptr_list
**dst
)
239 concat_ptr_list((struct ptr_list
*)src
, (struct ptr_list
**)dst
);
242 void convert_instruction_target(struct instruction
*insn
, pseudo_t src
)
244 pseudo_t target
, *usep
;
247 * Go through the "insn->users" list and replace them all..
249 target
= insn
->target
;
252 FOR_EACH_PTR(target
->users
, usep
) {
254 assert(*usep
== target
);
257 } END_FOR_EACH_PTR(usep
);
258 concat_user_list(target
->users
, &src
->users
);
259 target
->users
= NULL
;
262 void convert_load_instruction(struct instruction
*insn
, pseudo_t src
)
264 convert_instruction_target(insn
, src
);
265 /* Turn the load into a no-op */
266 insn
->opcode
= OP_LNOP
;
270 static int overlapping_memop(struct instruction
*a
, struct instruction
*b
)
272 unsigned int a_start
= a
->offset
<< 3;
273 unsigned int b_start
= b
->offset
<< 3;
274 unsigned int a_size
= a
->size
;
275 unsigned int b_size
= b
->size
;
277 if (a_size
+ a_start
<= b_start
)
279 if (b_size
+ b_start
<= a_start
)
284 static inline int same_memop(struct instruction
*a
, struct instruction
*b
)
286 return a
->offset
== b
->offset
&& a
->size
== b
->size
;
290 * Return 1 if "one" dominates the access to 'pseudo'
293 * Return 0 if it doesn't, and -1 if you don't know.
295 int dominates(pseudo_t pseudo
, struct instruction
*insn
, struct instruction
*dom
, int local
)
297 int opcode
= dom
->opcode
;
299 if (opcode
== OP_CALL
|| opcode
== OP_ENTRY
)
300 return local
? 0 : -1;
301 if (opcode
!= OP_LOAD
&& opcode
!= OP_STORE
)
303 if (dom
->src
!= pseudo
) {
306 /* We don't think two explicitly different symbols ever alias */
307 if (dom
->src
->type
== PSEUDO_SYM
)
309 /* We could try to do some alias analysis here */
312 if (!same_memop(insn
, dom
)) {
313 if (dom
->opcode
== OP_LOAD
)
315 if (!overlapping_memop(insn
, dom
))
322 static int find_dominating_parents(pseudo_t pseudo
, struct instruction
*insn
,
323 struct basic_block
*bb
, unsigned long generation
, struct pseudo_list
**dominators
,
324 int local
, int loads
)
326 struct basic_block
*parent
;
331 if (bb_list_size(bb
->parents
) > 1)
333 FOR_EACH_PTR(bb
->parents
, parent
) {
334 struct instruction
*one
;
335 struct instruction
*br
;
338 FOR_EACH_PTR_REVERSE(parent
->insns
, one
) {
342 dominance
= dominates(pseudo
, insn
, one
, local
);
344 if (one
->opcode
== OP_LOAD
)
350 if (one
->opcode
== OP_LOAD
&& !loads
)
352 goto found_dominator
;
353 } END_FOR_EACH_PTR_REVERSE(one
);
355 if (parent
->generation
== generation
)
357 parent
->generation
= generation
;
359 if (!find_dominating_parents(pseudo
, insn
, parent
, generation
, dominators
, local
, loads
))
364 br
= delete_last_instruction(&parent
->insns
);
365 phi
= alloc_phi(parent
, one
->target
, one
->size
);
366 phi
->ident
= phi
->ident
? : pseudo
->ident
;
367 add_instruction(&parent
->insns
, br
);
368 use_pseudo(phi
, add_pseudo(dominators
, phi
));
369 } END_FOR_EACH_PTR(parent
);
374 * We should probably sort the phi list just to make it easier to compare
375 * later for equality.
377 void rewrite_load_instruction(struct instruction
*insn
, struct pseudo_list
*dominators
)
382 * Check for somewhat common case of duplicate
385 new = first_pseudo(dominators
)->def
->src1
;
386 FOR_EACH_PTR(dominators
, phi
) {
387 if (new != phi
->def
->src1
)
389 new->ident
= new->ident
? : phi
->ident
;
390 } END_FOR_EACH_PTR(phi
);
393 * All the same pseudo - mark the phi-nodes unused
394 * and convert the load into a LNOP and replace the
397 FOR_EACH_PTR(dominators
, phi
) {
399 } END_FOR_EACH_PTR(phi
);
400 convert_load_instruction(insn
, new);
404 /* We leave symbol pseudos with a bogus usage list here */
405 if (insn
->src
->type
!= PSEUDO_SYM
)
406 kill_use(&insn
->src
);
407 insn
->opcode
= OP_PHI
;
408 insn
->phi_list
= dominators
;
411 static int find_dominating_stores(pseudo_t pseudo
, struct instruction
*insn
,
412 unsigned long generation
, int local
)
414 struct basic_block
*bb
= insn
->bb
;
415 struct instruction
*one
, *dom
= NULL
;
416 struct pseudo_list
*dominators
;
419 /* Unreachable load? Undo it */
421 insn
->opcode
= OP_LNOP
;
426 FOR_EACH_PTR(bb
->insns
, one
) {
430 dominance
= dominates(pseudo
, insn
, one
, local
);
432 /* Ignore partial load dominators */
433 if (one
->opcode
== OP_LOAD
)
443 } END_FOR_EACH_PTR(one
);
445 warning(pseudo
->sym
->pos
, "unable to find symbol read");
452 convert_load_instruction(insn
, dom
->target
);
456 /* Ok, go find the parents */
457 bb
->generation
= generation
;
460 if (!find_dominating_parents(pseudo
, insn
, bb
, generation
, &dominators
, local
, 1))
463 /* This happens with initial assignments to structures etc.. */
467 convert_load_instruction(insn
, value_pseudo(0));
472 * If we find just one dominating instruction, we
473 * can turn it into a direct thing. Otherwise we'll
474 * have to turn the load into a phi-node of the
477 rewrite_load_instruction(insn
, dominators
);
481 static void kill_store(struct instruction
*insn
)
485 insn
->opcode
= OP_SNOP
;
486 kill_use(&insn
->target
);
490 /* Kill a pseudo that is dead on exit from the bb */
491 static void kill_dead_stores(pseudo_t pseudo
, unsigned long generation
, struct basic_block
*bb
, int local
)
493 struct instruction
*insn
;
494 struct basic_block
*parent
;
496 if (bb
->generation
== generation
)
498 bb
->generation
= generation
;
499 FOR_EACH_PTR_REVERSE(bb
->insns
, insn
) {
500 int opcode
= insn
->opcode
;
502 if (opcode
!= OP_LOAD
&& opcode
!= OP_STORE
) {
505 if (opcode
== OP_CALL
)
509 if (insn
->src
== pseudo
) {
510 if (opcode
== OP_LOAD
)
517 if (insn
->src
->type
!= PSEUDO_SYM
)
519 } END_FOR_EACH_PTR_REVERSE(insn
);
521 FOR_EACH_PTR(bb
->parents
, parent
) {
522 struct basic_block
*child
;
523 FOR_EACH_PTR(parent
->children
, child
) {
524 if (child
&& child
!= bb
)
526 } END_FOR_EACH_PTR(child
);
527 kill_dead_stores(pseudo
, generation
, parent
, local
);
528 } END_FOR_EACH_PTR(parent
);
532 * This should see if the "insn" trivially dominates some previous store, and kill the
533 * store if unnecessary.
535 static void kill_dominated_stores(pseudo_t pseudo
, struct instruction
*insn
,
536 unsigned long generation
, struct basic_block
*bb
, int local
, int found
)
538 struct instruction
*one
;
539 struct basic_block
*parent
;
541 /* Unreachable store? Undo it */
546 if (bb
->generation
== generation
)
548 bb
->generation
= generation
;
549 FOR_EACH_PTR_REVERSE(bb
->insns
, one
) {
557 dominance
= dominates(pseudo
, insn
, one
, local
);
562 if (one
->opcode
== OP_LOAD
)
565 } END_FOR_EACH_PTR_REVERSE(one
);
568 warning(bb
->pos
, "Unable to find instruction");
572 FOR_EACH_PTR(bb
->parents
, parent
) {
573 struct basic_block
*child
;
574 FOR_EACH_PTR(parent
->children
, child
) {
575 if (child
&& child
!= bb
)
577 } END_FOR_EACH_PTR(child
);
578 kill_dominated_stores(pseudo
, insn
, generation
, parent
, local
, found
);
579 } END_FOR_EACH_PTR(parent
);
582 static void simplify_one_symbol(struct entrypoint
*ep
, struct symbol
*sym
)
584 pseudo_t pseudo
, src
, *pp
;
585 struct instruction
*def
;
587 int all
, stores
, complex;
589 /* Never used as a symbol? */
590 pseudo
= sym
->pseudo
;
594 /* We don't do coverage analysis of volatiles.. */
595 if (sym
->ctype
.modifiers
& MOD_VOLATILE
)
598 /* ..and symbols with external visibility need more care */
599 mod
= sym
->ctype
.modifiers
& (MOD_NONLOCAL
| MOD_STATIC
| MOD_ADDRESSABLE
);
601 goto external_visibility
;
606 FOR_EACH_PTR(pseudo
->users
, pp
) {
607 /* We know that the symbol-pseudo use is the "src" in the instruction */
608 struct instruction
*insn
= container(pp
, struct instruction
, src
);
610 switch (insn
->opcode
) {
620 mod
|= MOD_ADDRESSABLE
;
621 goto external_visibility
;
628 warning(sym
->pos
, "symbol '%s' pseudo used in unexpected way", show_ident(sym
->ident
));
630 complex |= insn
->offset
;
631 } END_FOR_EACH_PTR(pp
);
639 * Goodie, we have a single store (if even that) in the whole
640 * thing. Replace all loads with moves from the pseudo,
641 * replace the store with a def.
647 FOR_EACH_PTR(pseudo
->users
, pp
) {
648 struct instruction
*insn
= container(pp
, struct instruction
, src
);
649 if (insn
->opcode
== OP_LOAD
)
650 convert_load_instruction(insn
, src
);
651 } END_FOR_EACH_PTR(pp
);
653 /* Turn the store into a no-op */
661 FOR_EACH_PTR_REVERSE(pseudo
->users
, pp
) {
662 struct instruction
*insn
= container(pp
, struct instruction
, src
);
663 if (insn
->opcode
== OP_LOAD
)
664 all
&= find_dominating_stores(pseudo
, insn
, ++bb_generation
, !mod
);
665 } END_FOR_EACH_PTR_REVERSE(pp
);
667 /* If we converted all the loads, remove the stores. They are dead */
669 FOR_EACH_PTR(pseudo
->users
, pp
) {
670 struct instruction
*insn
= container(pp
, struct instruction
, src
);
671 if (insn
->opcode
== OP_STORE
)
673 } END_FOR_EACH_PTR(pp
);
676 * If we couldn't take the shortcut, see if we can at least kill some
679 FOR_EACH_PTR(pseudo
->users
, pp
) {
680 struct instruction
*insn
= container(pp
, struct instruction
, src
);
681 if (insn
->opcode
== OP_STORE
)
682 kill_dominated_stores(pseudo
, insn
, ++bb_generation
, insn
->bb
, !mod
, 0);
683 } END_FOR_EACH_PTR(pp
);
685 if (!(mod
& (MOD_NONLOCAL
| MOD_STATIC
))) {
686 struct basic_block
*bb
;
687 FOR_EACH_PTR(ep
->bbs
, bb
) {
689 kill_dead_stores(pseudo
, ++bb_generation
, bb
, !mod
);
690 } END_FOR_EACH_PTR(bb
);
697 void simplify_symbol_usage(struct entrypoint
*ep
)
701 FOR_EACH_PTR(ep
->accesses
, sym
) {
702 simplify_one_symbol(ep
, sym
);
703 } END_FOR_EACH_PTR(sym
);
706 static void mark_bb_reachable(struct basic_block
*bb
, unsigned long generation
)
708 struct basic_block
*child
;
710 if (bb
->generation
== generation
)
712 bb
->generation
= generation
;
713 FOR_EACH_PTR(bb
->children
, child
) {
714 mark_bb_reachable(child
, generation
);
715 } END_FOR_EACH_PTR(child
);
718 static void kill_defs(struct instruction
*insn
)
720 pseudo_t target
= insn
->target
;
722 if (!has_use_list(target
))
724 if (target
->def
!= insn
)
727 convert_instruction_target(insn
, VOID
);
730 void kill_bb(struct basic_block
*bb
)
732 struct instruction
*insn
;
733 struct basic_block
*child
, *parent
;
735 FOR_EACH_PTR(bb
->insns
, insn
) {
736 kill_instruction(insn
);
739 * We kill unreachable instructions even if they
740 * otherwise aren't "killable". Eg volatile loads
744 } END_FOR_EACH_PTR(insn
);
747 FOR_EACH_PTR(bb
->children
, child
) {
748 remove_bb_from_list(&child
->parents
, bb
, 0);
749 } END_FOR_EACH_PTR(child
);
752 FOR_EACH_PTR(bb
->parents
, parent
) {
753 remove_bb_from_list(&parent
->children
, bb
, 0);
754 } END_FOR_EACH_PTR(parent
);
758 void kill_unreachable_bbs(struct entrypoint
*ep
)
760 struct basic_block
*bb
;
761 unsigned long generation
= ++bb_generation
;
763 mark_bb_reachable(ep
->entry
->bb
, generation
);
764 FOR_EACH_PTR(ep
->bbs
, bb
) {
765 if (bb
->generation
== generation
)
767 /* Mark it as being dead */
770 DELETE_CURRENT_PTR(bb
);
771 } END_FOR_EACH_PTR(bb
);
772 PACK_PTR_LIST(&ep
->bbs
);
775 static int rewrite_parent_branch(struct basic_block
*bb
, struct basic_block
*old
, struct basic_block
*new)
778 struct instruction
*insn
= last_instruction(bb
->insns
);
783 /* Infinite loops: let's not "optimize" them.. */
787 switch (insn
->opcode
) {
789 changed
|= rewrite_branch(bb
, &insn
->bb_true
, old
, new);
790 changed
|= rewrite_branch(bb
, &insn
->bb_false
, old
, new);
794 struct multijmp
*jmp
;
795 FOR_EACH_PTR(insn
->multijmp_list
, jmp
) {
796 changed
|= rewrite_branch(bb
, &jmp
->target
, old
, new);
797 } END_FOR_EACH_PTR(jmp
);
806 static struct basic_block
* rewrite_branch_bb(struct basic_block
*bb
, struct instruction
*br
)
808 struct basic_block
*parent
;
809 struct basic_block
*target
= br
->bb_true
;
810 struct basic_block
*false = br
->bb_false
;
812 if (target
&& false) {
813 pseudo_t cond
= br
->cond
;
814 if (cond
->type
!= PSEUDO_VAL
)
816 target
= cond
->value
? target
: false;
820 * We can't do FOR_EACH_PTR() here, because the parent list
821 * may change when we rewrite the parent.
823 while ((parent
= first_basic_block(bb
->parents
)) != NULL
) {
824 if (!rewrite_parent_branch(parent
, bb
, target
))
830 static void vrfy_bb_in_list(struct basic_block
*bb
, struct basic_block_list
*list
)
833 struct basic_block
*tmp
;
834 int no_bb_in_list
= 0;
836 FOR_EACH_PTR(list
, tmp
) {
839 } END_FOR_EACH_PTR(tmp
);
840 assert(no_bb_in_list
);
844 static void vrfy_parents(struct basic_block
*bb
)
846 struct basic_block
*tmp
;
847 FOR_EACH_PTR(bb
->parents
, tmp
) {
848 vrfy_bb_in_list(bb
, tmp
->children
);
849 } END_FOR_EACH_PTR(tmp
);
852 static void vrfy_children(struct basic_block
*bb
)
854 struct basic_block
*tmp
;
855 struct instruction
*br
= last_instruction(bb
->insns
);
858 assert(!bb
->children
);
861 switch (br
->opcode
) {
862 struct multijmp
*jmp
;
864 vrfy_bb_in_list(br
->bb_true
, bb
->children
);
865 vrfy_bb_in_list(br
->bb_false
, bb
->children
);
868 case OP_COMPUTEDGOTO
:
869 FOR_EACH_PTR(br
->multijmp_list
, jmp
) {
870 vrfy_bb_in_list(jmp
->target
, bb
->children
);
871 } END_FOR_EACH_PTR(jmp
);
877 FOR_EACH_PTR(bb
->children
, tmp
) {
878 vrfy_bb_in_list(bb
, tmp
->parents
);
879 } END_FOR_EACH_PTR(tmp
);
882 static void vrfy_bb_flow(struct basic_block
*bb
)
888 void vrfy_flow(struct entrypoint
*ep
)
890 struct basic_block
*bb
;
891 struct basic_block
*entry
= ep
->entry
->bb
;
893 FOR_EACH_PTR(ep
->bbs
, bb
) {
897 } END_FOR_EACH_PTR(bb
);
901 void pack_basic_blocks(struct entrypoint
*ep
)
903 struct basic_block
*bb
;
905 /* See if we can merge a bb into another one.. */
906 FOR_EACH_PTR(ep
->bbs
, bb
) {
907 struct instruction
*first
, *insn
;
908 struct basic_block
*parent
, *child
, *last
;
910 if (!bb_reachable(bb
))
916 FOR_EACH_PTR(bb
->insns
, first
) {
919 switch (first
->opcode
) {
920 case OP_NOP
: case OP_LNOP
: case OP_SNOP
:
923 struct basic_block
*replace
;
924 replace
= rewrite_branch_bb(bb
, first
);
934 } END_FOR_EACH_PTR(first
);
938 * See if we only have one parent..
941 FOR_EACH_PTR(bb
->parents
, parent
) {
948 } END_FOR_EACH_PTR(parent
);
951 if (!parent
|| parent
== bb
)
955 * Goodie. See if the parent can merge..
957 FOR_EACH_PTR(parent
->children
, child
) {
960 } END_FOR_EACH_PTR(child
);
965 repeat_phase
|= REPEAT_CSE
;
968 * But don't allow phi-source merges after this.
969 * FIXME, FIXME! I really need to think about this.
970 * Is it true? I think it's ok to merge phi-sources,
971 * as long as we keep their relative position in
972 * the stream. It's the re-ordering we can't have.
975 merge_phi_sources
= 0;
977 parent
->children
= bb
->children
;
981 FOR_EACH_PTR(parent
->children
, child
) {
982 replace_bb_in_list(&child
->parents
, bb
, parent
, 0);
983 } END_FOR_EACH_PTR(child
);
985 delete_last_instruction(&parent
->insns
);
986 FOR_EACH_PTR(bb
->insns
, insn
) {
988 assert(insn
->bb
== bb
);
991 add_instruction(&parent
->insns
, insn
);
992 } END_FOR_EACH_PTR(insn
);
997 } END_FOR_EACH_PTR(bb
);