aboutsummaryrefslogtreecommitdiffstats
path: root/cse.c
diff options
context:
space:
mode:
authorLinus Torvalds <torvalds@ppc970.osdl.org>2004-11-25 10:37:34 -0700
committerLinus Torvalds <torvalds@ppc970.osdl.org>2005-04-07 21:04:49 -0700
commit384b8be31a6ae2813867cea7fcccc464b788b812 (patch)
tree99e95fc21f76ebf3899819a1a8c91720a4309e85 /cse.c
parent0cde10b1951b7175edab953b3325f8c0c990eea1 (diff)
downloadsparse-384b8be31a6ae2813867cea7fcccc464b788b812.tar.gz
sparse-384b8be31a6ae2813867cea7fcccc464b788b812.tar.xz
sparse-384b8be31a6ae2813867cea7fcccc464b788b812.zip
Move instruction simplification to new file "simplify.c".
Also, allow marking a pseudo unused by setting it to VOID, which just disables further renaming of that use. This is needed to make phi-source instructions (that can be shared among multiple phi-nodes thanks to CSE) be collectable. We used to just mark the phi source dead, but that was wrong, since _another_ phi node might be using it.
Diffstat (limited to 'cse.c')
-rw-r--r--cse.c211
1 files changed, 18 insertions, 193 deletions
diff --git a/cse.c b/cse.c
index 8c00a6b..016c7f5 100644
--- a/cse.c
+++ b/cse.c
@@ -36,187 +36,6 @@ static int phi_compare(pseudo_t phi1, pseudo_t phi2)
return 0;
}
-/* Find the trivial parent for a phi-source */
-static struct basic_block *phi_parent(struct basic_block *source, pseudo_t pseudo)
-{
- /* Can't go upwards if the pseudo is defined in the bb it came from.. */
- if (pseudo->type == PSEUDO_REG) {
- struct instruction *def = pseudo->def;
- if (def->bb == source)
- return source;
- }
- if (bb_list_size(source->children) != 1 || bb_list_size(source->parents) != 1)
- return source;
- return first_basic_block(source->parents);
-}
-
-static void clear_phi(struct instruction *insn)
-{
- pseudo_t phi;
-
- insn->bb = NULL;
- FOR_EACH_PTR(insn->phi_list, phi) {
- struct instruction *def = phi->def;
- def->bb = NULL;
- } END_FOR_EACH_PTR(phi);
-}
-
-static void if_convert_phi(struct instruction *insn)
-{
- pseudo_t array[3];
- struct basic_block *parents[3];
- struct basic_block *bb, *bb1, *bb2, *source;
- struct instruction *br;
- pseudo_t p1, p2;
-
- bb = insn->bb;
- if (linearize_ptr_list((struct ptr_list *)insn->phi_list, (void **)array, 3) != 2)
- return;
- if (linearize_ptr_list((struct ptr_list *)bb->parents, (void **)parents, 3) != 2)
- return;
- p1 = array[0]->def->src1;
- bb1 = array[0]->def->bb;
- p2 = array[1]->def->src1;
- bb2 = array[1]->def->bb;
-
- /* Only try the simple "direct parents" case */
- if ((bb1 != parents[0] || bb2 != parents[1]) &&
- (bb1 != parents[1] || bb2 != parents[0]))
- return;
-
- /*
- * See if we can find a common source for this..
- */
- source = phi_parent(bb1, p1);
- if (phi_parent(bb2, p2) != source)
- return;
-
- /*
- * Cool. We now know that 'source' is the exclusive
- * parent of both phi-nodes, so the exit at the
- * end of it fully determines which one it is, and
- * we can turn it into a select.
- *
- * HOWEVER, right now we only handle regular
- * conditional branches. No multijumps or computed
- * stuff. Verify that here.
- */
- br = last_instruction(source->insns);
- if (!br || br->opcode != OP_BR)
- return;
-
- /*
- * We're in business. Match up true/false with p1/p2.
- */
- if (br->bb_true == bb2 || br->bb_false == bb1) {
- pseudo_t p = p1;
- p1 = p2;
- p2 = p;
- }
-
- /*
- * Ok, we can now replace that last
- *
- * br cond, a, b
- *
- * with the sequence
- *
- * setcc cond
- * select pseudo, p1, p2
- * br cond, a, b
- *
- * and remove the phi-node. If it then
- * turns out that 'a' or 'b' is entirely
- * empty (common case), and now no longer
- * a phi-source, we'll be able to simplify
- * the conditional branch too.
- */
- insert_select(source, br, insn, p1, p2);
- clear_phi(insn);
- cse_repeat = 1;
-}
-
-static unsigned long clean_up_phi(struct instruction *insn)
-{
- pseudo_t phi;
- struct instruction *last;
- unsigned long hash = 0;
- int same;
-
- last = NULL;
- same = 1;
- FOR_EACH_PTR(insn->phi_list, phi) {
- struct instruction *def = phi->def;
- if (def->src1 == VOID)
- continue;
- if (last) {
- if (last->src1 != def->src1)
- same = 0;
- continue;
- }
- last = def;
- hash += hashval(def->src1);
- hash += hashval(def->bb);
- } END_FOR_EACH_PTR(phi);
-
- if (same) {
- pseudo_t pseudo = last ? last->src1 : VOID;
- convert_instruction_target(insn, pseudo);
- cse_repeat = 1;
- insn->bb = NULL;
- /* This one is bogus, but no worse than anything else */
- return hash;
- }
-
- if_convert_phi(insn);
-
- return hash;
-}
-
-static void try_to_kill(struct instruction *);
-
-static void kill_use(pseudo_t pseudo)
-{
- if (pseudo->type == PSEUDO_REG) {
- if (ptr_list_size((struct ptr_list *)pseudo->users) == 1) {
- try_to_kill(pseudo->def);
- }
- }
-}
-
-static void try_to_kill(struct instruction *insn)
-{
- int opcode = insn->opcode;
- switch (opcode) {
- case OP_BINARY ... OP_BINCMP_END:
- insn->bb = NULL;
- kill_use(insn->src1);
- kill_use(insn->src2);
- return;
- case OP_NOT: case OP_NEG:
- insn->bb = NULL;
- kill_use(insn->src1);
- return;
-
- case OP_PHI: case OP_SETVAL:
- insn->bb = NULL;
- return;
- }
-}
-
-/*
- * Kill trivially dead instructions
- */
-static int dead_insn(struct instruction *insn, pseudo_t src1, pseudo_t src2)
-{
- if (!insn->target->users) {
- insn->bb = NULL;
- kill_use(src1);
- kill_use(src2);
- return 1;
- }
- return 0;
-}
static void clean_up_one_instruction(struct basic_block *bb, struct instruction *insn)
{
@@ -225,6 +44,8 @@ static void clean_up_one_instruction(struct basic_block *bb, struct instruction
if (!insn->bb)
return;
assert(insn->bb == bb);
+ if (simplify_instruction(insn))
+ cse_repeat = 1;
hash = insn->opcode;
switch (insn->opcode) {
@@ -245,34 +66,33 @@ static void clean_up_one_instruction(struct basic_block *bb, struct instruction
case OP_SET_LT: case OP_SET_GT:
case OP_SET_B: case OP_SET_A:
case OP_SET_BE: case OP_SET_AE:
- if (dead_insn(insn, insn->src1, insn->src2))
- return;
hash += hashval(insn->src1);
hash += hashval(insn->src2);
break;
/* Unary */
case OP_NOT: case OP_NEG:
- if (dead_insn(insn, insn->src1, VOID))
- return;
hash += hashval(insn->src1);
break;
case OP_SETVAL:
- if (dead_insn(insn, VOID, VOID))
- return;
hash += hashval(insn->val);
hash += hashval(insn->symbol);
break;
/* Other */
- case OP_PHI:
- if (dead_insn(insn, VOID, VOID)) {
- clear_phi(insn);
- return;
- }
- hash += clean_up_phi(insn);
+ case OP_PHI: {
+ pseudo_t phi;
+ FOR_EACH_PTR(insn->phi_list, phi) {
+ struct instruction *def;
+ if (phi == VOID)
+ continue;
+ def = phi->def;
+ hash += hashval(def->src1);
+ hash += hashval(def->bb);
+ } END_FOR_EACH_PTR(phi);
break;
+ }
case OP_PHISOURCE:
hash += hashval(insn->src1);
@@ -315,6 +135,11 @@ static int phi_list_compare(struct pseudo_list *l1, struct pseudo_list *l2)
for (;;) {
int cmp;
+ while (phi1 == VOID)
+ NEXT_PTR_LIST(phi1);
+ while (phi2 == VOID)
+ NEXT_PTR_LIST(phi2);
+
if (!phi1)
return phi2 ? -1 : 0;
if (!phi2)