[PATCH v2 0/5] unssa improvements

[PATCH v2 0/5] unssa improvements

[Luc Van Oostenryck]

This serie improves the out-of-SSA step by:
* simplify the conversion of the phi-nodes & phi-sources into copies
* eliminate some copies which are trivially not needed.

The elimination step is significant since on a small corpus which
produced 267 copies, after the patch only 165 remain.


Changes since v1:
  * during unSSA, do not use kill_instruction() on OP_PHI
  * fix related to the fact that after unSSA, pseudos *can*
    again be defined by several instructions. If it's effectively the
    case, their ->def is set to NULL (and must, of course, not be used).

Note: this serie depends on the serie 'fix uses of killed instructions'
    and on the changes to the testsuite for checking after some patterns
    in the output.

This serie can also be found on github:
	https://github.com/lucvoo/sparse/tree/sent/unssa-simple

Luc Van Oostenryck (5):
  unssa: do not try to update liveness
  unssa: simplify rewrite of OP_PHISOURCE
  unssa: try to avoid some OP_PHI copies
  unssa: eliminate trivial phisrc copies
  unssa: update comment about the unneeded copies

 unssa.c | 142 ++++++++++++++++++++++++++++++++++------------------------------
 1 file changed, 75 insertions(+), 67 deletions(-)

-- 
2.10.2

[PATCH v2 1/5] unssa: do not try to update liveness

[Luc Van Oostenryck]

The unSSA step used to try to maintain the liveness info
while creating the copies but this can't be done so simply
(what is updated is only the liveness for the current bb
while it needs to be done for all concerned bbs).

If/when liveness is needed after this step, it need to be
redone by calling track_pseudo_liveness().

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 unssa.c | 3 ---
 1 file changed, 3 deletions(-)

diff --git a/unssa.c b/unssa.c
index 382095d7..85b1388d 100644
--- a/unssa.c
+++ b/unssa.c
@@ -49,9 +49,6 @@ static void replace_phi_node(struct instruction *phi)
 	tmp->ident = phi->target->ident;
 	tmp->def = NULL;		// defined by all the phisrc
 	
-	// update the current liveness
-	remove_pseudo(&phi->bb->needs, phi->target);
-	add_pseudo(&phi->bb->needs, tmp);
 	track_phi_uses(phi);
 
 	phi->opcode = OP_COPY;
-- 
2.10.2

[PATCH v2 2/5] unssa: simplify rewrite of OP_PHISOURCE

[Luc Van Oostenryck]

Using the fact that each OP_PHISOURCE is used by a single OP_PHI,
it's easier to rewrite OP_PHISOURCE at the same time as their
associated OP_PHI (because we have access to the new pseudo just created).

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 unssa.c | 89 ++++++++++++++++-------------------------------------------------
 1 file changed, 21 insertions(+), 68 deletions(-)

diff --git a/unssa.c b/unssa.c
index 85b1388d..2660e94c 100644
--- a/unssa.c
+++ b/unssa.c
@@ -10,9 +10,9 @@
  *
  * This is similar to the "Sreedhar method I" except that the copies to the
  * temporaries are not placed at the end of the predecessor basic blocks, but
- * at the place where the phi-node operands are defined (the same place where the
- * phisrc were present).
- * Is this a problem? 
+ * at the place where the phi-node operands are defined.
+ * This is particulary easy since these copies are essentialy already present
+ * as the corresponding OP_PHISOURCE.
  *
  * While very simple this method create a lot more copies that really necessary.
  * Ideally, "Sreedhar method III" should be used:
@@ -30,31 +30,35 @@
 #include <assert.h>
 
 
-static void remove_phisrc_defines(struct instruction *phisrc)
-{
-	struct instruction *phi;
-	struct basic_block *bb = phisrc->bb;
-
-	FOR_EACH_PTR(phisrc->phi_users, phi) {
-		remove_pseudo(&bb->defines, phi->target);
-	} END_FOR_EACH_PTR(phi);
-}
-
 static void replace_phi_node(struct instruction *phi)
 {
 	pseudo_t tmp;
+	pseudo_t p;
 
 	tmp = alloc_pseudo(NULL);
 	tmp->type = phi->target->type;
 	tmp->ident = phi->target->ident;
 	tmp->def = NULL;		// defined by all the phisrc
-	
-	track_phi_uses(phi);
 
+	// rewrite all it's phi_src to copy to a new tmp
+	FOR_EACH_PTR(phi->phi_list, p) {
+		struct instruction *def = p->def;
+
+		if (p == VOID)
+			continue;
+
+		assert(def->opcode == OP_PHISOURCE);
+
+		def->opcode = OP_COPY;
+		def->target = tmp;
+	} END_FOR_EACH_PTR(p);
+
+	// rewrite the phi node:
+	//	phi	%rt, ...
+	// to:
+	//	copy	%rt, %tmp
 	phi->opcode = OP_COPY;
 	use_pseudo(phi, tmp, &phi->src);
-
-	// FIXME: free phi->phi_list;
 }
 
 static void rewrite_phi_bb(struct basic_block *bb)
@@ -73,53 +77,6 @@ static void rewrite_phi_bb(struct basic_block *bb)
 	} END_FOR_EACH_PTR(insn);
 }
 
-static void rewrite_phisrc_bb(struct basic_block *bb)
-{
-	struct instruction *insn;
-
-	// Replace all the phisrc by one or several copies to
-	// the temporaries associated to each phi-node it defines.
-	FOR_EACH_PTR_REVERSE(bb->insns, insn) {
-		struct instruction *phi;
-		int i;
-
-		if (!insn->bb)
-			continue;
-		if (insn->opcode != OP_PHISOURCE)
-			continue;
-
-		i = 0;
-		FOR_EACH_PTR(insn->phi_users, phi) {
-			pseudo_t tmp = phi->src;
-			pseudo_t src = insn->phi_src;
-
-			if (i == 0) {	// first phi: we overwrite the phisrc
-				insn->opcode = OP_COPY;
-				insn->target = tmp;
-				insn->src = src;
-			} else {
-				struct instruction *copy = __alloc_instruction(0);
-
-				copy->bb = bb;
-				copy->opcode = OP_COPY;
-				copy->size = insn->size;
-				copy->pos = insn->pos;
-				copy->target = tmp;
-				copy->src = src;
-
-				INSERT_CURRENT(copy, insn);
-			}
-			// update the liveness info
-			remove_phisrc_defines(insn);
-			// FIXME: should really something like add_pseudo_exclusive()
-			add_pseudo(&bb->defines, tmp);
-
-			i++;
-		} END_FOR_EACH_PTR(phi);
-
-	} END_FOR_EACH_PTR_REVERSE(insn);
-}
-
 int unssa(struct entrypoint *ep)
 {
 	struct basic_block *bb;
@@ -128,9 +85,5 @@ int unssa(struct entrypoint *ep)
 		rewrite_phi_bb(bb);
 	} END_FOR_EACH_PTR(bb);
 
-	FOR_EACH_PTR(ep->bbs, bb) {
-		rewrite_phisrc_bb(bb);
-	} END_FOR_EACH_PTR(bb);

[PATCH v2 3/5] unssa: try to avoid some OP_PHI copies

[Luc Van Oostenryck]

OP_PHI's target can interfer with it's own source swhen defined
in the same basic block. Such interference can create problem
like the 'swap problem' (which only exist if the phi-node are
'processed' sequentially if they're processed in parallel such
problems don't exist) when phi-nodes are destructed. To avoid
such problems OP_PHI are rewritten as OP_COPY.

if an OP_PHI and it's OP_PHISOURCE are in different basic blocks
no such interference is possible and the copy is not needed.

This patch detect such situation and eliminate these unneeded copies.

Note: during unSSA we're removing the OP_PHI & OP_PHISOURCE
  but we need to use the def-use chains between them. We must
  thus not use kill_instruction() in OP_PHI (this would break
  def-use chains and leave stray OP_PHISOURCE), it's enough
  to set their bb to NULL.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 unssa.c | 32 ++++++++++++++++++++++++++++++++
 1 file changed, 32 insertions(+)

diff --git a/unssa.c b/unssa.c
index 2660e94c..50782352 100644
--- a/unssa.c
+++ b/unssa.c
@@ -30,6 +30,32 @@
 #include <assert.h>
 
 
+static int simplify_phi_node(struct instruction *phi, pseudo_t tmp)
+{
+	pseudo_t target = phi->target;
+	struct pseudo_user *pu;
+	pseudo_t src;
+
+	// verify if this phi can be simplified
+	FOR_EACH_PTR(phi->phi_list, src) {
+		struct instruction *def = src->def;
+
+		if (!def)
+			continue;
+		if (def->bb == phi->bb)
+			return 0;
+	} END_FOR_EACH_PTR(src);
+
+	// no need to make a copy of this one
+	// -> replace the target pseudo by the tmp
+	FOR_EACH_PTR(target->users, pu) {
+		use_pseudo(pu->insn, tmp, pu->userp);
+	} END_FOR_EACH_PTR(pu);
+
+	phi->bb = NULL;
+	return 1;
+}
+
 static void replace_phi_node(struct instruction *phi)
 {
 	pseudo_t tmp;
@@ -40,6 +66,9 @@ static void replace_phi_node(struct instruction *phi)
 	tmp->ident = phi->target->ident;
 	tmp->def = NULL;		// defined by all the phisrc
 
+	// can we avoid to make of copy?
+	simplify_phi_node(phi, tmp);
+
 	// rewrite all it's phi_src to copy to a new tmp
 	FOR_EACH_PTR(phi->phi_list, p) {
 		struct instruction *def = p->def;
@@ -53,6 +82,9 @@ static void replace_phi_node(struct instruction *phi)
 		def->target = tmp;
 	} END_FOR_EACH_PTR(p);
 
+	if (!phi->bb)
+		return;
+
 	// rewrite the phi node:
 	//	phi	%rt, ...
 	// to:
-- 
2.10.2

[PATCH v2 4/5] unssa: eliminate trivial phisrc copies

[Luc Van Oostenryck]

A OP_PHISOURCE which is the only user of its operand
can be trivially eliminated. For example, in:
	add	%r6, ...
	...
	phisrc	%rt, %r6
the phisrc can safely be eliminated if no other instruction use %r6.
With this patch it's rewritten as:
	add	%rt, ...
	...

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 unssa.c | 22 ++++++++++++++++++++++
 1 file changed, 22 insertions(+)

diff --git a/unssa.c b/unssa.c
index 50782352..a7085ca0 100644
--- a/unssa.c
+++ b/unssa.c
@@ -30,6 +30,11 @@
 #include <assert.h>
 
 
+static inline int nbr_pseudo_users(pseudo_t p)
+{
+	return ptr_list_size((struct ptr_list *)p->users);
+}
+
 static int simplify_phi_node(struct instruction *phi, pseudo_t tmp)
 {
 	pseudo_t target = phi->target;
@@ -72,6 +77,7 @@ static void replace_phi_node(struct instruction *phi)
 	// rewrite all it's phi_src to copy to a new tmp
 	FOR_EACH_PTR(phi->phi_list, p) {
 		struct instruction *def = p->def;
+		pseudo_t src;
 
 		if (p == VOID)
 			continue;
@@ -80,6 +86,22 @@ static void replace_phi_node(struct instruction *phi)
 
 		def->opcode = OP_COPY;
 		def->target = tmp;
+
+		// can we eliminate the copy?
+		src = def->phi_src;
+		if (src->type != PSEUDO_REG)
+			continue;
+		switch (nbr_pseudo_users(src)) {
+			struct instruction *insn;
+		case 1:
+			insn = src->def;
+			if (!insn)
+				break;
+			insn->target = tmp;
+		case 0:
+			kill_instruction(def);
+			def->bb = NULL;
+		}
 	} END_FOR_EACH_PTR(p);
 
 	if (!phi->bb)
-- 
2.10.2

[PATCH v2 5/5] unssa: update comment about the unneeded copies

[Luc Van Oostenryck]

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 unssa.c | 4 ++++
 1 file changed, 4 insertions(+)

diff --git a/unssa.c b/unssa.c
index a7085ca0..e7c9154d 100644
--- a/unssa.c
+++ b/unssa.c
@@ -15,10 +15,14 @@
  * as the corresponding OP_PHISOURCE.
  *
  * While very simple this method create a lot more copies that really necessary.
+ * We eliminate some of these copies but most probably most of them are still
+ * useless.
  * Ideally, "Sreedhar method III" should be used:
  * "Translating Out of Static Single Assignment Form", V. C. Sreedhar, R. D.-C. Ju,
  * D. M. Gillies and V. Santhanam.  SAS'99, Vol. 1694 of Lecture Notes in Computer
  * Science, Springer-Verlag, pp. 194-210, 1999.
+ * But for this we need precise liveness, on each %phi and not only on OP_PHI's
+ * target pseudos.
  *
  * Copyright (C) 2005 Luc Van Oostenryck
  */
-- 
2.10.2