[v1,18/18] ssa: phi worklist

Commit Message

Luc Van Oostenryck March 20, 2018, 12:52 a.m. UTC

This patch optimize the very simple implementation the phi-node
renaming at the end of the SSA conversion.

It avoids to have 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 some 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 to have correctness first.
Signed-off-by: Luc Van Oostenryck <[e-mail]>
---
 linearize.h                   |  1 +
 ssa.c                         | 43 ++++++++++++++++++++++++++++++++++---------
 validation/mem2reg/quadra01.c |  1 -
 3 files changed, 35 insertions(+), 10 deletions(-)

Patch

diff --git a/linearize.h b/linearize.h
index 5592b2c52..a5b06559d 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;
diff --git a/ssa.c b/ssa.c
index 34d922798..d67c8dede 100644
--- a/ssa.c
+++ b/ssa.c
@@ -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 bab337f2b..b71f46969 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\\.