diff options
| -rw-r--r-- | cse.c | 10 | ||||
| -rw-r--r-- | flow.c | 244 | ||||
| -rw-r--r-- | flow.h | 3 | ||||
| -rw-r--r-- | linearize.c | 50 | ||||
| -rw-r--r-- | linearize.h | 9 | ||||
| -rw-r--r-- | memops.c | 10 | ||||
| -rw-r--r-- | simplify.c | 34 | ||||
| -rw-r--r-- | ssa.c | 6 | ||||
| -rw-r--r-- | validation/optim/bad-phisrc1.c | 15 | ||||
| -rw-r--r-- | validation/optim/bad-phisrc1a.c | 23 | ||||
| -rw-r--r-- | validation/optim/bad-phisrc2.c | 16 | ||||
| -rw-r--r-- | validation/optim/bad-phisrc3.c | 20 | ||||
| -rw-r--r-- | validation/optim/multi-phisrc.c | 23 | ||||
| -rw-r--r-- | validation/optim/phi-count00.c | 27 |
14 files changed, 290 insertions, 200 deletions
@@ -298,14 +298,6 @@ static inline void remove_instruction(struct instruction_list **list, struct ins delete_ptr_list_entry((struct ptr_list **)list, insn, count); } -static void add_instruction_to_end(struct instruction *insn, struct basic_block *bb) -{ - struct instruction *br = delete_last_instruction(&bb->insns); - insn->bb = bb; - add_instruction(&bb->insns, insn); - add_instruction(&bb->insns, br); -} - static struct instruction * try_to_cse(struct entrypoint *ep, struct instruction *i1, struct instruction *i2) { struct basic_block *b1, *b2, *common; @@ -343,7 +335,7 @@ static struct instruction * try_to_cse(struct entrypoint *ep, struct instruction if (common) { i1 = cse_one_instruction(i2, i1); remove_instruction(&b1->insns, i1, 1); - add_instruction_to_end(i1, common); + insert_last_instruction(common, i1); } else { i1 = i2; } @@ -19,10 +19,69 @@ #include "simplify.h" #include "flow.h" #include "target.h" -#include "flowgraph.h" unsigned long bb_generation; +/// +// remove phi-sources from a removed edge +// +// :note: It's possible to have several edges between the same BBs. +// It's common with switches but it's also possible with branches. +// This function will only remove a single phi-source per edge. +int remove_phisources(struct basic_block *par, struct basic_block *old) +{ + struct instruction *insn; + int changed = 0; + + FOR_EACH_PTR(old->insns, insn) { + pseudo_t phi; + + if (!insn->bb) + continue; + if (insn->opcode != OP_PHI) + return changed; + + // found a phi-node in the target BB, + // now look after its phi-sources. + FOR_EACH_PTR(insn->phi_list, phi) { + struct instruction *phisrc = phi->def; + + if (phi == VOID) + continue; + assert(phisrc->phi_node == insn); + if (phisrc->bb != par) + continue; + // found a phi-source corresponding to this edge: + // remove it but avoid the recursive killing. + REPLACE_CURRENT_PTR(phi, VOID); + remove_use(&phisrc->src); + phisrc->bb = NULL; + changed |= REPEAT_CSE; + // Only the first one must be removed. + goto next; + } END_FOR_EACH_PTR(phi); +next: ; + } END_FOR_EACH_PTR(insn); + return changed; +} + +/// +// remove all phisources but the one corresponding to the given target +static int remove_other_phisources(struct basic_block *bb, struct multijmp_list *list, struct basic_block *target) +{ + struct multijmp *jmp; + int changed = 0; + + FOR_EACH_PTR(list, jmp) { + if (jmp->target == target) { + target = NULL; + continue; + } + changed |= remove_phisources(bb, jmp->target); + } END_FOR_EACH_PTR(jmp); + return changed; +} + /* * Dammit, if we have a phi-node followed by a conditional * branch on that phi-node, we should damn well be able to @@ -69,34 +128,6 @@ static int pseudo_truth_value(pseudo_t pseudo) } } -/// -// check if the BB is empty or only contains phi-sources -static int bb_is_trivial(struct basic_block *bb) -{ - struct instruction *insn; - int n = 0; - - FOR_EACH_PTR(bb->insns, insn) { - if (!insn->bb) - continue; - switch (insn->opcode) { - case OP_TERMINATOR ... OP_TERMINATOR_END: - return n ? -1 : 1; - case OP_NOP: - case OP_INLINED_CALL: - continue; - case OP_PHISOURCE: - n++; - continue; - default: - goto out; - } - } END_FOR_EACH_PTR(insn); - -out: - return 0; -} - /* * Does a basic block depend on the pseudos that "src" defines? */ @@ -159,78 +190,24 @@ out: } /// -// do jump threading in dominated BBs -// @dom: the BB which must dominate the modified BBs. -// @old: the old target BB -// @new: the new target BB -// @return: 0 if no chnages have been made, 1 otherwise. -// -// In all BB dominated by @dom, rewrite branches to @old into branches to @new -static int retarget_bb(struct basic_block *dom, struct basic_block *old, struct basic_block *new) +// check if the sources of a phi-node match with the parent BBs +static bool phi_check(struct instruction *node) { struct basic_block *bb; - int changed = 0; - - if (new == old) - return 0; - -restart: - FOR_EACH_PTR(old->parents, bb) { - struct instruction *last; - struct multijmp *jmp; + pseudo_t phi; - if (!domtree_dominates(dom, bb)) + PREPARE_PTR_LIST(node->bb->parents, bb); + FOR_EACH_PTR(node->phi_list, phi) { + if (phi == VOID || !phi->def) continue; - last = last_instruction(bb->insns); - switch (last->opcode) { - case OP_BR: - changed |= rewrite_branch(bb, &last->bb_true, old, new); - break; - case OP_CBR: - changed |= rewrite_branch(bb, &last->bb_true, old, new); - changed |= rewrite_branch(bb, &last->bb_false, old, new); - break; - case OP_SWITCH: - case OP_COMPUTEDGOTO: - FOR_EACH_PTR(last->multijmp_list, jmp) { - changed |= rewrite_branch(bb, &jmp->target, old, new); - } END_FOR_EACH_PTR(jmp); - break; - default: - continue; - } - - // since rewrite_branch() will modify old->parents() the list - // iteration won't work correctly. Several solution exist for - // this but in this case the simplest is to restart the loop. - goto restart; - } END_FOR_EACH_PTR(bb); - return changed; -} - -static int simplify_cbr_cbr(struct instruction *insn) -{ - struct instruction *last; - struct basic_block *bot = insn->bb; - struct basic_block *top = bot->idom; - int changed = 0; - int trivial; - - if (!top) - return 0; - - trivial = bb_is_trivial(bot); - if (trivial == 0) - return 0; - if (trivial < 0) - return 0; - last = last_instruction(top->insns); - if (last->opcode != OP_CBR || last->cond != insn->cond) - return 0; - - changed |= retarget_bb(last->bb_true , bot, insn->bb_true); - changed |= retarget_bb(last->bb_false, bot, insn->bb_false); - return changed; + if (phi->def->bb != bb) + return false; + NEXT_PTR_LIST(bb); + } END_FOR_EACH_PTR(phi); + if (bb) + return false; + FINISH_PTR_LIST(bb); + return true; } /* @@ -255,7 +232,7 @@ static int try_to_simplify_bb(struct basic_block *bb, struct instruction *first, * simplify_symbol_usage()/conversion to SSA form. * No sane simplification can be done when we have this. */ - bogus = bb_list_size(bb->parents) != pseudo_list_size(first->phi_list); + bogus = !phi_check(first); FOR_EACH_PTR(first->phi_list, phi) { struct instruction *def = phi->def; @@ -372,7 +349,7 @@ try_to_rewrite_target: */ if (bb_list_size(target->parents) != 1) return retval; - insert_branch(target, insn, final); + convert_to_jump(insn, final); return 1; } @@ -380,8 +357,6 @@ static int simplify_one_branch(struct basic_block *bb, struct instruction *br) { if (simplify_phi_branch(bb, br)) return 1; - if (simplify_cbr_cbr(br)) - return 1; return simplify_branch_branch(bb, br, &br->bb_true, 1) | simplify_branch_branch(bb, br, &br->bb_false, 0); } @@ -815,6 +790,43 @@ void vrfy_flow(struct entrypoint *ep) assert(!entry); } +/// +// change a switch or a conditional branch into a branch +int convert_to_jump(struct instruction *insn, struct basic_block *target) +{ + struct basic_block *bb = insn->bb; + struct basic_block *child; + int changed = REPEAT_CSE; + + switch (insn->opcode) { + case OP_CBR: + changed |= remove_phisources(insn->bb, insn->bb_true == target ? insn->bb_false : insn->bb_true); + break; + case OP_SWITCH: + changed |= remove_other_phisources(insn->bb, insn->multijmp_list, target); + break; + } + kill_use(&insn->cond); + insn->bb_true = target; + insn->bb_false = NULL; + insn->cond = NULL; + insn->size = 0; + insn->opcode = OP_BR; + + FOR_EACH_PTR(bb->children, child) { + if (child == target) { + target = NULL; // leave first occurence + continue; + } + DELETE_CURRENT_PTR(child); + remove_bb_from_list(&child->parents, bb, 1); + changed |= REPEAT_CFG_CLEANUP; + } END_FOR_EACH_PTR(child); + PACK_PTR_LIST(&bb->children); + repeat_phase |= changed; + return changed; +} + static int retarget_parents(struct basic_block *bb, struct basic_block *target) { struct basic_block *parent; @@ -831,21 +843,26 @@ static int retarget_parents(struct basic_block *bb, struct basic_block *target) return REPEAT_CFG_CLEANUP; } -static void remove_merging_phisrc(struct basic_block *top, struct instruction *insn) +static void remove_merging_phisrc(struct instruction *insn, struct basic_block *bot) { - struct instruction *user = insn->phi_node; + struct instruction *node = insn->phi_node; pseudo_t phi; - FOR_EACH_PTR(user->phi_list, phi) { + if (!node) { + kill_instruction(insn); + return; + } + + FOR_EACH_PTR(node->phi_list, phi) { struct instruction *phisrc; if (phi == VOID) continue; phisrc = phi->def; - if (phisrc->bb != top) - continue; - REPLACE_CURRENT_PTR(phi, VOID); - kill_instruction(phisrc); + if (phisrc->bb == bot) { + kill_instruction(insn); + return; + } } END_FOR_EACH_PTR(phi); } @@ -889,6 +906,14 @@ static int merge_bb(struct basic_block *top, struct basic_block *bot) replace_bb_in_list(&bb->parents, bot, top, 1); } END_FOR_EACH_PTR(bb); + FOR_EACH_PTR(top->insns, insn) { + if (!insn->bb) + continue; + if (insn->opcode != OP_PHISOURCE) + continue; + remove_merging_phisrc(insn, bot); + } END_FOR_EACH_PTR(insn); + kill_instruction(delete_last_instruction(&top->insns)); FOR_EACH_PTR(bot->insns, insn) { if (!insn->bb) @@ -898,9 +923,6 @@ static int merge_bb(struct basic_block *top, struct basic_block *bot) case OP_PHI: remove_merging_phi(top, insn); continue; - case OP_PHISOURCE: - remove_merging_phisrc(top, insn); - break; } insn->bb = top; add_instruction(&top->insns, insn); @@ -11,6 +11,8 @@ extern unsigned long bb_generation; struct entrypoint; struct instruction; +extern int remove_phisources(struct basic_block *par, struct basic_block *old); + extern int simplify_flow(struct entrypoint *ep); extern void kill_dead_stores(struct entrypoint *ep, pseudo_t addr, int local); @@ -18,6 +20,7 @@ extern void simplify_symbol_usage(struct entrypoint *ep); extern void simplify_memops(struct entrypoint *ep); extern void pack_basic_blocks(struct entrypoint *ep); extern int simplify_cfg_early(struct entrypoint *ep); +extern int convert_to_jump(struct instruction *insn, struct basic_block *target); extern void convert_instruction_target(struct instruction *insn, pseudo_t src); extern void remove_dead_insns(struct entrypoint *); diff --git a/linearize.c b/linearize.c index cf87545c..d9aed61b 100644 --- a/linearize.c +++ b/linearize.c @@ -692,52 +692,12 @@ static void set_activeblock(struct entrypoint *ep, struct basic_block *bb) add_bb(&ep->bbs, bb); } -static void remove_parent(struct basic_block *child, struct basic_block *parent) -{ - remove_bb_from_list(&child->parents, parent, 1); - if (!child->parents) - repeat_phase |= REPEAT_CFG_CLEANUP; -} - -/* Change a "switch" or a conditional branch into a branch */ -void insert_branch(struct basic_block *bb, struct instruction *jmp, struct basic_block *target) -{ - struct instruction *br, *old; - struct basic_block *child; - - /* Remove the switch */ - old = delete_last_instruction(&bb->insns); - assert(old == jmp); - kill_instruction(old); - - br = alloc_instruction(OP_BR, 0); - br->bb = bb; - br->bb_true = target; - add_instruction(&bb->insns, br); - - FOR_EACH_PTR(bb->children, child) { - if (child == target) { - target = NULL; /* Trigger just once */ - continue; - } - DELETE_CURRENT_PTR(child); - remove_parent(child, bb); - } END_FOR_EACH_PTR(child); - PACK_PTR_LIST(&bb->children); - repeat_phase |= REPEAT_CFG_CLEANUP; -} - - void insert_select(struct basic_block *bb, struct instruction *br, struct instruction *phi_node, pseudo_t if_true, pseudo_t if_false) { pseudo_t target; struct instruction *select; - /* Remove the 'br' */ - delete_last_instruction(&bb->insns); - select = alloc_typed_instruction(OP_SEL, phi_node->type); - select->bb = bb; assert(br->cond); use_pseudo(select, br->cond, &select->src1); @@ -750,8 +710,7 @@ void insert_select(struct basic_block *bb, struct instruction *br, struct instru use_pseudo(select, if_true, &select->src2); use_pseudo(select, if_false, &select->src3); - add_instruction(&bb->insns, select); - add_instruction(&bb->insns, br); + insert_last_instruction(bb, select); } static inline int bb_empty(struct basic_block *bb) @@ -1750,10 +1709,9 @@ static void insert_phis(struct basic_block *bb, pseudo_t src, struct symbol *cty struct basic_block *parent; FOR_EACH_PTR(bb->parents, parent) { - struct instruction *br = delete_last_instruction(&parent->insns); - pseudo_t phi = alloc_phi(parent, src, ctype); - add_instruction(&parent->insns, br); - link_phi(node, phi); + struct instruction *phisrc = alloc_phisrc(src, ctype); + insert_last_instruction(parent, phisrc); + link_phi(node, phisrc->target); } END_FOR_EACH_PTR(parent); } diff --git a/linearize.h b/linearize.h index 86ae119c..b11a1937 100644 --- a/linearize.h +++ b/linearize.h @@ -195,6 +195,14 @@ static inline void add_instruction(struct instruction_list **list, struct instru add_ptr_list(list, insn); } +static inline void insert_last_instruction(struct basic_block *bb, struct instruction *insn) +{ + struct instruction *last = delete_last_instruction(&bb->insns); + add_instruction(&bb->insns, insn); + add_instruction(&bb->insns, last); + insn->bb = bb; +} + static inline void add_multijmp(struct multijmp_list **list, struct multijmp *multijmp) { add_ptr_list(list, multijmp); @@ -319,7 +327,6 @@ struct entrypoint { }; extern void insert_select(struct basic_block *bb, struct instruction *br, struct instruction *phi, pseudo_t if_true, pseudo_t if_false); -extern void insert_branch(struct basic_block *bb, struct instruction *br, struct basic_block *target); struct instruction *alloc_phisrc(pseudo_t pseudo, struct symbol *type); struct instruction *alloc_phi_node(struct basic_block *bb, struct symbol *type, struct ident *ident); @@ -60,8 +60,8 @@ static int find_dominating_parents(struct instruction *insn, struct basic_block *parent; FOR_EACH_PTR(bb->parents, parent) { + struct instruction *phisrc; struct instruction *one; - struct instruction *br; pseudo_t phi; FOR_EACH_PTR_REVERSE(parent->insns, one) { @@ -90,12 +90,12 @@ no_dominance: continue; found_dominator: - br = delete_last_instruction(&parent->insns); - phi = alloc_phi(parent, one->target, one->type); + phisrc = alloc_phisrc(one->target, one->type); + phisrc->phi_node = insn; + insert_last_instruction(parent, phisrc); + phi = phisrc->target; phi->ident = phi->ident ? : one->target->ident; - add_instruction(&parent->insns, br); use_pseudo(insn, phi, add_pseudo(dominators, phi)); - phi->def->phi_node = insn; } END_FOR_EACH_PTR(parent); return 1; } @@ -2538,23 +2538,12 @@ static int simplify_branch(struct instruction *insn) pseudo_t cond = insn->cond; /* Constant conditional */ - if (constant(cond)) { - insert_branch(insn->bb, insn, cond->value ? insn->bb_true : insn->bb_false); - return REPEAT_CSE; - } + if (constant(cond)) + return convert_to_jump(insn, cond->value ? insn->bb_true : insn->bb_false); /* Same target? */ - if (insn->bb_true == insn->bb_false) { - struct basic_block *bb = insn->bb; - struct basic_block *target = insn->bb_false; - remove_bb_from_list(&target->parents, bb, 1); - remove_bb_from_list(&bb->children, target, 1); - insn->bb_false = NULL; - kill_use(&insn->cond); - insn->cond = NULL; - insn->opcode = OP_BR; - return REPEAT_CSE|REPEAT_CFG_CLEANUP; - } + if (insn->bb_true == insn->bb_false) + return convert_to_jump(insn, insn->bb_true); /* Conditional on a SETNE $0 or SETEQ $0 */ if (cond->type == PSEUDO_REG) { @@ -2570,14 +2559,10 @@ static int simplify_branch(struct instruction *insn) if (constant(def->src2) && constant(def->src3)) { long long val1 = def->src2->value; long long val2 = def->src3->value; - if (!val1 && !val2) { - insert_branch(insn->bb, insn, insn->bb_false); - return REPEAT_CSE; - } - if (val1 && val2) { - insert_branch(insn->bb, insn, insn->bb_true); - return REPEAT_CSE; - } + if (!val1 && !val2) + return convert_to_jump(insn, insn->bb_false); + if (val1 && val2) + return convert_to_jump(insn, insn->bb_true); if (val2) { struct basic_block *tmp = insn->bb_true; insn->bb_true = insn->bb_false; @@ -2613,8 +2598,7 @@ static int simplify_switch(struct instruction *insn) return 0; found: - insert_branch(insn->bb, insn, jmp->target); - return REPEAT_CSE; + return convert_to_jump(insn, jmp->target); } static struct basic_block *is_label(pseudo_t pseudo) @@ -327,12 +327,12 @@ static void ssa_rename_phi(struct instruction *insn) if (!var->torename) return; FOR_EACH_PTR(insn->bb->parents, par) { - struct instruction *term = delete_last_instruction(&par->insns); struct instruction *def = lookup_var(par, var); pseudo_t val = def ? def->target : undef_pseudo(); - pseudo_t phi = alloc_phi(par, val, var); + struct instruction *phisrc = alloc_phisrc(val, var); + pseudo_t phi = phisrc->target; phi->ident = var->ident; - add_instruction(&par->insns, term); + insert_last_instruction(par, phisrc); link_phi(insn, phi); mark_phi_used(val); } END_FOR_EACH_PTR(par); diff --git a/validation/optim/bad-phisrc1.c b/validation/optim/bad-phisrc1.c new file mode 100644 index 00000000..aa12dd0a --- /dev/null +++ b/validation/optim/bad-phisrc1.c @@ -0,0 +1,15 @@ +void foo(int a, int b) +{ + if (b) + while ((a += 5) > a) + ; +} + +/* + * check-name: bad-phisrc1 + * check-command: test-linearize -Wno-decl $file + * + * check-output-ignore + * check-output-excludes: phi\\. + * check-output-excludes: phisource\\. + */ diff --git a/validation/optim/bad-phisrc1a.c b/validation/optim/bad-phisrc1a.c new file mode 100644 index 00000000..b7519ee7 --- /dev/null +++ b/validation/optim/bad-phisrc1a.c @@ -0,0 +1,23 @@ +int def(void); + +int fun4(struct xfrm_state *net, int cnt) +{ + int err = 0; + if (err) + goto out; + for (; net;) + err = def(); + if (cnt) +out: + return err; + return 0; +} + +/* + * check-name: bad-phisrc1a + * check-command: test-linearize -Wno-decl $file + * + * check-output-ignore + * check-output-contains: select\\. + */ + diff --git a/validation/optim/bad-phisrc2.c b/validation/optim/bad-phisrc2.c new file mode 100644 index 00000000..78eae288 --- /dev/null +++ b/validation/optim/bad-phisrc2.c @@ -0,0 +1,16 @@ +int bad_phisrc2(int p, int a, int r) +{ + if (p) + r = a; + else if (r) + ; + return r; +} + +/* + * check-name: bad-phisrc2 + * check-command: test-linearize -Wno-decl $file + * + * check-output-ignore + * check-output-contains: select\\. + */ diff --git a/validation/optim/bad-phisrc3.c b/validation/optim/bad-phisrc3.c new file mode 100644 index 00000000..41537420 --- /dev/null +++ b/validation/optim/bad-phisrc3.c @@ -0,0 +1,20 @@ +void foo(void) +{ + int c = 1; + switch (3) { + case 0: + do { + ; + case 3: ; + } while (c++); + } +} + +/* + * check-name: bad-phisrc3 + * check-command: test-linearize -Wno-decl $file + * + * check-output-ignore + * check-output-pattern(2): phisrc\\. + * check-output-pattern(1): phi\\. + */ diff --git a/validation/optim/multi-phisrc.c b/validation/optim/multi-phisrc.c new file mode 100644 index 00000000..ff31c083 --- /dev/null +++ b/validation/optim/multi-phisrc.c @@ -0,0 +1,23 @@ +void fun(void); + +void foo(int p, int a) +{ + if (p == p) { + switch (p) { + case 0: + break; + case 1: + a = 0; + } + } + if (a) + fun(); +} + +/* + * check-name: multi-phisrc + * check-command: test-linearize -Wno-decl $file + * + * check-output-ignore + * check-output-excludes: phi + */ diff --git a/validation/optim/phi-count00.c b/validation/optim/phi-count00.c new file mode 100644 index 00000000..38db0eda --- /dev/null +++ b/validation/optim/phi-count00.c @@ -0,0 +1,27 @@ +inline int inl(int d, int e, int f) +{ + switch (d) { + case 0: + return e; + case 1: + return f; + default: + return 0; + } +} + +void foo(int a, int b, int c) +{ + while (1) { + if (inl(a, b, c)) + break; + } +} + +/* + * check-name: phi-count00 + * check-command: test-linearize -Wno-decl $file + * + * check-output-ignore + * check-output-pattern(0,2): phisrc + */ |