diff options
| author | Linus Torvalds <torvalds@ppc970.osdl.org> | 2004-11-23 15:39:21 -0700 |
|---|---|---|
| committer | Linus Torvalds <torvalds@ppc970.osdl.org> | 2005-04-07 21:04:37 -0700 |
| commit | 3cbf846f9e4e4cf7fa530301d906c4418e3515af (patch) | |
| tree | dc46aefa103f836c1225b2b4cef125ebdcf0408b | |
| parent | 7f7110e1135157694390f558d7541b8dd9295b3e (diff) | |
| download | sparse-dev-3cbf846f9e4e4cf7fa530301d906c4418e3515af.tar.gz | |
Add simple-stupid dominance testing for CSE.
This makes us able to CSE stuff where one subexpression
directly dominates another.
But we still don't do any fancy code motion in the non-
dominance case.
| -rw-r--r-- | cse.c | 34 | ||||
| -rw-r--r-- | flow.c | 2 | ||||
| -rw-r--r-- | flow.h | 2 |
3 files changed, 35 insertions, 3 deletions
@@ -228,7 +228,29 @@ static struct instruction * cse_one_instruction(struct instruction *insn, struct return def; } -static struct instruction * try_to_cse(struct instruction *i1, struct instruction *i2) +/* + * Does "bb1" dominate "bb2"? + */ +static int bb_dominates(struct entrypoint *ep, struct basic_block *bb1, struct basic_block *bb2, unsigned long generation) +{ + struct basic_block *parent; + + /* Nothing dominates the entrypoint.. */ + if (bb2 == ep->entry) + return 0; + FOR_EACH_PTR(bb2->parents, parent) { + if (parent == bb1) + continue; + if (parent->generation == generation) + continue; + parent->generation = generation; + if (!bb_dominates(ep, bb1, parent, generation)) + return 0; + } END_FOR_EACH_PTR(parent); + return 1; +} + +static struct instruction * try_to_cse(struct entrypoint *ep, struct instruction *i1, struct instruction *i2) { struct basic_block *b1, *b2; @@ -252,7 +274,15 @@ static struct instruction * try_to_cse(struct instruction *i1, struct instructio return cse_one_instruction(i1, i2); } END_FOR_EACH_PTR(insn); warning(b1->pos, "Whaa? unable to find CSE instructions"); + return NULL; } + if (bb_dominates(ep, b1, b2, ++bb_generation)) + return cse_one_instruction(i2, i1); + + if (bb_dominates(ep, b2, b1, ++bb_generation)) + return cse_one_instruction(i1, i2); + + /* No direct dominance - but we could try to find a common ancestor.. */ return NULL; } @@ -275,7 +305,7 @@ repeat: FOR_EACH_PTR(*list, insn) { if (last) { if (!insn_compare(last, insn)) { - struct instruction *def = try_to_cse(last, insn); + struct instruction *def = try_to_cse(ep, last, insn); if (def) { success++; insn = def; @@ -16,7 +16,7 @@ #include "linearize.h" #include "flow.h" -static unsigned long bb_generation; +unsigned long bb_generation; /* * Dammit, if we have a phi-node followed by a conditional @@ -1,6 +1,8 @@ #ifndef FLOW_H #define FLOW_H +extern unsigned long bb_generation; + extern void simplify_symbol_usage(struct entrypoint *ep); extern void simplify_phi_nodes(struct entrypoint *ep); extern void pack_basic_blocks(struct entrypoint *ep); |