diff options
| author | Luc Van Oostenryck <luc.vanoostenryck@gmail.com> | 2018-03-18 18:43:10 +0100 |
|---|---|---|
| committer | Luc Van Oostenryck <luc.vanoostenryck@gmail.com> | 2018-07-01 00:18:44 +0200 |
| commit | 3f06ccfcc0be01c0d5bc6a982c2fbadf62fa502a (patch) | |
| tree | 5f451f818ca180f2895d2d1a609bd0316776cd56 | |
| parent | f72c77ccd8af3fbfe76a00cdaa6d8ee01d498729 (diff) | |
| download | sparse-dev-3f06ccfcc0be01c0d5bc6a982c2fbadf62fa502a.tar.gz | |
ssa: phi worklist
This patch optimize the very simple implementation of the
phi-node renaming at the end of the SSA conversion.
It avoids the need to rescan the whole function to find the phi-nodes
by using a worklist to put the phi-nodes during the renaming
of non-phi nodes instructions.
This optimization avoids O(n^2) behaviour in some pathological cases.
Note: A lot of optimizations can be done for the renaming.
For the moment, things are kept as simplest as possible,
the goal being to have correctness first.
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
| -rw-r--r-- | linearize.h | 1 | ||||
| -rw-r--r-- | ssa.c | 43 | ||||
| -rw-r--r-- | validation/mem2reg/quadra01.c | 1 |
3 files changed, 35 insertions, 10 deletions
diff --git a/linearize.h b/linearize.h index 0e980578..02f8ceeb 100644 --- a/linearize.h +++ b/linearize.h @@ -104,6 +104,7 @@ struct instruction { struct /* phi_node */ { pseudo_t phi_var; // used for SSA conversion struct pseudo_list *phi_list; + unsigned int used:1; }; struct /* phi source */ { pseudo_t phi_src; @@ -263,6 +263,9 @@ static pseudo_t lookup_var(struct basic_block *bb, struct symbol *var) return undef_pseudo(); } +static struct instruction_list *phis_all; +static struct instruction_list *phis_used; + static void ssa_rename_insn(struct basic_block *bb, struct instruction *insn) { struct symbol *var; @@ -295,6 +298,7 @@ static void ssa_rename_insn(struct basic_block *bb, struct instruction *insn) if (!var || !var->torename) break; phi_map_update(&bb->phi_map, var, insn->target); + add_instruction(&phis_all, insn); break; } } @@ -313,6 +317,21 @@ static void ssa_rename_insns(struct entrypoint *ep) } END_FOR_EACH_PTR(bb); } +static void mark_phi_used(pseudo_t val) +{ + struct instruction *node; + + if (val->type != PSEUDO_REG) + return; + node = val->def; + if (node->opcode != OP_PHI) + return; + if (node->used) + return; + node->used = 1; + add_instruction(&phis_used, node); +} + static void ssa_rename_phi(struct instruction *insn) { struct basic_block *par; @@ -330,22 +349,27 @@ static void ssa_rename_phi(struct instruction *insn) phi->ident = var->ident; add_instruction(&par->insns, term); use_pseudo(insn, phi, add_pseudo(&insn->phi_list, phi)); + mark_phi_used(val); } END_FOR_EACH_PTR(par); } static void ssa_rename_phis(struct entrypoint *ep) { - struct basic_block *bb; + struct instruction *phi; + phis_used = NULL; + FOR_EACH_PTR(phis_all, phi) { + if (has_users(phi->target)) { + phi->used = 1; + add_instruction(&phis_used, phi); + } + } END_FOR_EACH_PTR(phi); - FOR_EACH_PTR(ep->bbs, bb) { - struct instruction *insn; - FOR_EACH_PTR(bb->insns, insn) { - if (!insn->bb || insn->opcode != OP_PHI) - continue; - ssa_rename_phi(insn); - } END_FOR_EACH_PTR(insn); - } END_FOR_EACH_PTR(bb); + FOR_EACH_PTR(phis_used, phi) { + if (!phi->bb) + continue; + ssa_rename_phi(phi); + } END_FOR_EACH_PTR(phi); } void ssa_convert(struct entrypoint *ep) @@ -371,6 +395,7 @@ void ssa_convert(struct entrypoint *ep) } END_FOR_EACH_PTR(pseudo); // rename the converted accesses + phis_all = phis_used = NULL; ssa_rename_insns(ep); ssa_rename_phis(ep); } diff --git a/validation/mem2reg/quadra01.c b/validation/mem2reg/quadra01.c index bab337f2..b71f4696 100644 --- a/validation/mem2reg/quadra01.c +++ b/validation/mem2reg/quadra01.c @@ -20,7 +20,6 @@ static void foo(void) { * check-name: quadratic @ liveness * check-command: test-linearize -I. $file * check-timeout: - * check-known-to-fail * * check-output-ignore * check-output-excludes: phi\\. |