[PATCH 1/2] better dealing with OP_PHISOURCE insn

[PATCH 1/2] better dealing with OP_PHISOURCE insn

[Jan Pokorný]

When (sure that) we are dealing with OP_PHISOURCE instruction, we should
use `phi_src' rather then `src1', which is dedicated to "binops and sel"
(linearize.h) and, by chance/intention, aliases with the former one.

On changed places, I used asserts to ensure the only type of
instructions involved in these changes are OP_PHISOURCE and proceeded
sparse itself and linux-2.6.35.12 sources with no assertion violation
encountered.  I'll provide a cumulative patch for this patch series
including these asserts, mainly for testing purposes.

Signed-off-by: Jan Pokorny <pokorny_jan@seznam.cz>
---
 cse.c       |    6 +++---
 flow.c      |    2 +-
 linearize.c |    2 +-
 simplify.c  |    6 +++---
 4 files changed, 8 insertions(+), 8 deletions(-)

diff --git a/cse.c b/cse.c
index 2a15745..dc4d53c 100644
--- a/cse.c
+++ b/cse.c
@@ -27,8 +27,8 @@ static int phi_compare(pseudo_t phi1, pseudo_t phi2)
 	const struct instruction *def1 = phi1->def;
 	const struct instruction *def2 = phi2->def;
 
-	if (def1->src1 != def2->src1)
-		return def1->src1 < def2->src1 ? -1 : 1;
+	if (def1->phi_src != def2->phi_src)
+		return def1->phi_src < def2->phi_src ? -1 : 1;
 	if (def1->bb != def2->bb)
 		return def1->bb < def2->bb ? -1 : 1;
 	return 0;
@@ -105,7 +105,7 @@ static void clean_up_one_instruction(struct basic_block *bb, struct instruction
 			if (phi == VOID || !phi->def)
 				continue;
 			def = phi->def;
-			hash += hashval(def->src1);
+			hash += hashval(def->phi_src);
 			hash += hashval(def->bb);
 		} END_FOR_EACH_PTR(phi);
 		break;
diff --git a/flow.c b/flow.c
index 5bd9a1d..b6e46c7 100644
--- a/flow.c
+++ b/flow.c
@@ -105,7 +105,7 @@ static int try_to_simplify_bb(struct basic_block *bb, struct instruction *first,
 		if (!def)
 			continue;
 		source = def->bb;
-		pseudo = def->src1;
+		pseudo = def->phi_src;
 		if (!pseudo || !source)
 			continue;
 		br = last_instruction(source->insns);
diff --git a/linearize.c b/linearize.c
index f2034ce..f940862 100644
--- a/linearize.c
+++ b/linearize.c
@@ -1643,7 +1643,7 @@ static pseudo_t linearize_compound_statement(struct entrypoint *ep, struct state
 		if (pseudo_list_size(phi_node->phi_list)==1) {
 			pseudo = first_pseudo(phi_node->phi_list);
 			assert(pseudo->type == PSEUDO_PHI);
-			return pseudo->def->src1;
+			return pseudo->def->phi_src;
 		}
 		return phi_node->target;
 	}
diff --git a/simplify.c b/simplify.c
index 8200584..2d3c19d 100644
--- a/simplify.c
+++ b/simplify.c
@@ -126,10 +126,10 @@ static int clean_up_phi(struct instruction *insn)
 		if (phi == VOID)
 			continue;
 		def = phi->def;
-		if (def->src1 == VOID || !def->bb)
+		if (def->phi_src == VOID || !def->bb)
 			continue;
 		if (last) {
-			if (last->src1 != def->src1)
+			if (last->phi_src != def->phi_src)
 				same = 0;
 			continue;
 		}
@@ -137,7 +137,7 @@ static int clean_up_phi(struct instruction *insn)
 	} END_FOR_EACH_PTR(phi);
 
 	if (same) {
-		pseudo_t pseudo = last ? last->src1 : VOID;
+		pseudo_t pseudo = last ? last->phi_src : VOID;
 		convert_instruction_target(insn, pseudo);
 		clear_phi(insn);
 		return REPEAT_CSE;
-- 
1.7.1

[PATCH 2/2] better dealing with OP_PHISOURCE insn

[Jan Pokorný]

Remove checking for a case that (most probably) never happens as the
only expected instruction is OP_PHISOURCE.

For the sake of assurance, assert added with a comment easing the fix if
the assumption of OP_PHISOURCE is wrong (better then masking a problem).

Also, use `def' as existing shortcut for `phi->def'.

Tested the same way as the previous patch (together).

Signed-off-by: Jan Pokorny <pokorny_jan@seznam.cz>
---
 liveness.c |    8 +++-----
 1 files changed, 3 insertions(+), 5 deletions(-)

diff --git a/liveness.c b/liveness.c
index eeff0f7..02ceed9 100644
--- a/liveness.c
+++ b/liveness.c
@@ -23,11 +23,9 @@ static void phi_defines(struct instruction * phi_node, pseudo_t target,
 		def = phi->def;
 		if (!def || !def->bb)
 			continue;
-		if (def->opcode == OP_PHI) {
-			phi_defines(def, target, defines);
-			continue;
-		}
-		defines(def->bb, phi->def, target);
+		/* if this ever fails (very unlikely), it's a sign of a regression */
+		assert(def->opcode == OP_PHISOURCE);
+		defines(def->bb, def, target);
 	} END_FOR_EACH_PTR(phi);
 }
 
-- 
1.7.1

Re: [PATCH 2/2] better dealing with OP_PHISOURCE insn

[Jan Pokorný]

This is promised cummulative patch of the two plus added assertions,
mainly intended for convenient testing.

Signed-off-by: Jan Pokorny <pokorny_jan@seznam.cz>
---
 cse.c       |    9 ++++++---
 flow.c      |    3 ++-
 linearize.c |    3 ++-
 liveness.c  |    8 +++-----
 simplify.c  |    7 ++++---
 5 files changed, 17 insertions(+), 13 deletions(-)

diff --git a/cse.c b/cse.c
index 2a15745..b96d5ae 100644
--- a/cse.c
+++ b/cse.c
@@ -26,9 +26,11 @@ static int phi_compare(pseudo_t phi1, pseudo_t phi2)
 {
 	const struct instruction *def1 = phi1->def;
 	const struct instruction *def2 = phi2->def;
+	assert(def1->opcode == OP_PHISOURCE);
+	assert(def2->opcode == OP_PHISOURCE);
 
-	if (def1->src1 != def2->src1)
-		return def1->src1 < def2->src1 ? -1 : 1;
+	if (def1->phi_src != def2->phi_src)
+		return def1->phi_src < def2->phi_src ? -1 : 1;
 	if (def1->bb != def2->bb)
 		return def1->bb < def2->bb ? -1 : 1;
 	return 0;
@@ -105,7 +107,8 @@ static void clean_up_one_instruction(struct basic_block *bb, struct instruction
 			if (phi == VOID || !phi->def)
 				continue;
 			def = phi->def;
-			hash += hashval(def->src1);
+			assert(def->opcode == OP_PHISOURCE);
+			hash += hashval(def->phi_src);
 			hash += hashval(def->bb);
 		} END_FOR_EACH_PTR(phi);
 		break;
diff --git a/flow.c b/flow.c
index 5bd9a1d..9af105b 100644
--- a/flow.c
+++ b/flow.c
@@ -104,8 +104,9 @@ static int try_to_simplify_bb(struct basic_block *bb, struct instruction *first,
 
 		if (!def)
 			continue;
+		assert(def->opcode == OP_PHISOURCE);
 		source = def->bb;
-		pseudo = def->src1;
+		pseudo = def->phi_src;
 		if (!pseudo || !source)
 			continue;
 		br = last_instruction(source->insns);
diff --git a/linearize.c b/linearize.c
index f2034ce..9c13011 100644
--- a/linearize.c
+++ b/linearize.c
@@ -1643,7 +1643,8 @@ static pseudo_t linearize_compound_statement(struct entrypoint *ep, struct state
 		if (pseudo_list_size(phi_node->phi_list)==1) {
 			pseudo = first_pseudo(phi_node->phi_list);
 			assert(pseudo->type == PSEUDO_PHI);
-			return pseudo->def->src1;
+			assert(pseudo->def->opcode == OP_PHISOURCE);
+			return pseudo->def->phi_src;
 		}
 		return phi_node->target;
 	}
diff --git a/liveness.c b/liveness.c
index eeff0f7..02ceed9 100644
--- a/liveness.c
+++ b/liveness.c
@@ -23,11 +23,9 @@ static void phi_defines(struct instruction * phi_node, pseudo_t target,
 		def = phi->def;
 		if (!def || !def->bb)
 			continue;
-		if (def->opcode == OP_PHI) {
-			phi_defines(def, target, defines);
-			continue;
-		}
-		defines(def->bb, phi->def, target);
+		/* if this ever fails (very unlikely), it's a sign of a regression */
+		assert(def->opcode == OP_PHISOURCE);
+		defines(def->bb, def, target);
 	} END_FOR_EACH_PTR(phi);
 }
 
diff --git a/simplify.c b/simplify.c
index 8200584..b18610a 100644
--- a/simplify.c
+++ b/simplify.c
@@ -126,10 +126,11 @@ static int clean_up_phi(struct instruction *insn)
 		if (phi == VOID)
 			continue;
 		def = phi->def;
-		if (def->src1 == VOID || !def->bb)
+		assert(def->opcode == OP_PHISOURCE);
+		if (def->phi_src == VOID || !def->bb)
 			continue;
 		if (last) {
-			if (last->src1 != def->src1)
+			if (last->phi_src != def->phi_src)
 				same = 0;
 			continue;
 		}
@@ -137,7 +138,7 @@ static int clean_up_phi(struct instruction *insn)
 	} END_FOR_EACH_PTR(phi);
 
 	if (same) {
-		pseudo_t pseudo = last ? last->src1 : VOID;
+		pseudo_t pseudo = last ? last->phi_src : VOID;
 		convert_instruction_target(insn, pseudo);
 		clear_phi(insn);
 		return REPEAT_CSE;
-- 
1.7.1

Re: [PATCH 2/2] better dealing with OP_PHISOURCE insn

[Christopher Li]

On Sat, Apr 9, 2011 at 5:12 AM, Jan Pokorný <pokorny_jan@seznam.cz> wrote:
> -               if (def->opcode == OP_PHI) {
> -                       phi_defines(def, target, defines);
> -                       continue;
> -               }
> -               defines(def->bb, phi->def, target);
> +               /* if this ever fails (very unlikely), it's a sign of a regression */
> +               assert(def->opcode == OP_PHISOURCE);
> +               defines(def->bb, def, target);
>        } END_FOR_EACH_PTR(phi);

That comment usually means there is some thing fishy going on there.
I think you are on to some thing. The original code mean to recursively
define all the phi source, if the phi source is come from another phi node.
But the original code seems wrong. It should lookat def->phi_src->def->opcode
instead of def->opcode. I don't think we should remove the phi_defines there.
I need to double check this as well.

Chris
--
To unsubscribe from this list: send the line "unsubscribe linux-sparse" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH 2/2] better dealing with OP_PHISOURCE insn

[Jan Pokorný]

This is my proposal of how to fix incorrect handling of a recursive
"(PHISOURCE->PHI->)+ PHISOURCE->PHI" chain in `phi_defines'.

It should be applied instead of my previous 2/2 patch posted on
2011-04-09 which treated this case unwisely as spotted by Chris Li
who also outlined respective correction in his reply from 2011-04-14.

The fix required to move `trackable_pseudo' (if we want to avoid
a forward declaration).

I also added `src_pseudo' in the role of a shortcut and removed `def' to
reduce the number of levels of such shortcuts (to keep it more readable).

I tried few comparisons (some of them in very carefully) and it seems to
do the job (as explained in included comment) right.

Signed-off-by: Jan Pokorny <pokorny_jan@seznam.cz>
---
 liveness.c |   39 +++++++++++++++++++++++++--------------
 1 files changed, 25 insertions(+), 14 deletions(-)

diff --git a/liveness.c b/liveness.c
index eeff0f7..c9460de 100644
--- a/liveness.c
+++ b/liveness.c
@@ -12,22 +12,38 @@
 #include "linearize.h"
 #include "flow.h"
 
+
+static inline int trackable_pseudo(pseudo_t pseudo)
+{
+	return pseudo && (pseudo->type == PSEUDO_REG || pseudo->type == PSEUDO_ARG);
+}
+
 static void phi_defines(struct instruction * phi_node, pseudo_t target,
-	void (*defines)(struct basic_block *, struct instruction *, pseudo_t))
+	void (*defines)(struct basic_block *, struct instruction *, pseudo_t),
+	unsigned long generation)
 {
 	pseudo_t phi;
 	FOR_EACH_PTR(phi_node->phi_list, phi) {
-		struct instruction *def;
 		if (phi == VOID)
 			continue;
-		def = phi->def;
-		if (!def || !def->bb)
-			continue;
-		if (def->opcode == OP_PHI) {
-			phi_defines(def, target, defines);
+		if (!phi->def || !phi->def->bb)
 			continue;
+
+		/*
+		 * In case of "(PHISOURCE->PHI->)+ PHISOURCE->PHI" chain, move
+		 * "defines" information upstream to the BB of a very first PHISOURCE
+		 * (recursion guarded using "generation" marking of PHI insn BBs).
+		 */
+		pseudo_t src_pseudo = phi->def->phi_src;
+		if (trackable_pseudo(src_pseudo) && src_pseudo->def->opcode == OP_PHI) {
+			phi_node->bb->generation = generation;
+			if (src_pseudo->def->bb->generation != generation) {
+				phi_defines(src_pseudo->def, target, defines, generation);
+				continue;
+			}
 		}
-		defines(def->bb, phi->def, target);
+
+		defines(phi->def->bb, phi->def, target);
 	} END_FOR_EACH_PTR(phi);
 }
 
@@ -103,7 +119,7 @@ static void track_instruction_usage(struct basic_block *bb, struct instruction *
 	/* Other */
 	case OP_PHI:
 		/* Phi-nodes are "backwards" nodes. Their def doesn't matter */
-		phi_defines(insn, insn->target, def);
+		phi_defines(insn, insn->target, def, ++bb_generation);
 		break;
 
 	case OP_PHISOURCE:
@@ -179,11 +195,6 @@ static void add_pseudo_exclusive(struct pseudo_list **list, pseudo_t pseudo)
 	}
 }
 
-static inline int trackable_pseudo(pseudo_t pseudo)
-{
-	return pseudo && (pseudo->type == PSEUDO_REG || pseudo->type == PSEUDO_ARG);
-}

Re: [PATCH 2/2] better dealing with OP_PHISOURCE insn

[Jan Pokorný]

Evolution of patch I proposed on 2011-04-15 (to be applied instead
of my first 2/2 patch posted on 2011-04-09).

In fact, no need to use `trackable_pseudo' as we are only interested in
PSEUDO_REG and we do not expect this pseudo to be NULL (round of testing
with additional assert added hadn't proven such test is relevant).

Signed-off-by: Jan Pokorny <pokorny_jan@seznam.cz>
---
 liveness.c |   29 ++++++++++++++++++++---------
 1 files changed, 20 insertions(+), 9 deletions(-)

diff --git a/liveness.c b/liveness.c
index eeff0f7..060d599 100644
--- a/liveness.c
+++ b/liveness.c
@@ -13,21 +13,32 @@
 #include "flow.h"
 
 static void phi_defines(struct instruction * phi_node, pseudo_t target,
-	void (*defines)(struct basic_block *, struct instruction *, pseudo_t))
+	void (*defines)(struct basic_block *, struct instruction *, pseudo_t),
+	unsigned long generation)
 {
 	pseudo_t phi;
 	FOR_EACH_PTR(phi_node->phi_list, phi) {
-		struct instruction *def;
 		if (phi == VOID)
 			continue;
-		def = phi->def;
-		if (!def || !def->bb)
-			continue;
-		if (def->opcode == OP_PHI) {
-			phi_defines(def, target, defines);
+		if (!phi->def || !phi->def->bb)
 			continue;
+
+		/*
+		 * In case of "(PHISOURCE->PHI->)+ PHISOURCE->PHI" chain, move
+		 * "defines" information upstream to the very first PHISOURCE;
+		 * recursion guarded by generation marking of PHI instructions BBs.
+		 */
+		pseudo_t src_pseudo = phi->def->phi_src;
+		if (src_pseudo->type == PSEUDO_REG
+			&& src_pseudo->def->opcode == OP_PHI) {
+			phi_node->bb->generation = generation;
+			if (src_pseudo->def->bb->generation != generation) {
+				phi_defines(src_pseudo->def, target, defines, generation);
+				continue;
+			}
 		}
-		defines(def->bb, phi->def, target);
+
+		defines(phi->def->bb, phi->def, target);
 	} END_FOR_EACH_PTR(phi);
 }
 
@@ -103,7 +114,7 @@ static void track_instruction_usage(struct basic_block *bb, struct instruction *
 	/* Other */
 	case OP_PHI:
 		/* Phi-nodes are "backwards" nodes. Their def doesn't matter */
-		phi_defines(insn, insn->target, def);
+		phi_defines(insn, insn->target, def, ++bb_generation);
 		break;
 
 	case OP_PHISOURCE:
-- 
1.7.1

Re: [PATCH 2/2] better dealing with OP_PHISOURCE insn

[Jan Pokorný]

(Sorry, I do not use tabs normally so not aware of all these
exceptions as with continued "if")

Signed-off-by: Jan Pokorny <pokorny_jan@seznam.cz>
---
 liveness.c |   29 ++++++++++++++++++++---------
 1 files changed, 20 insertions(+), 9 deletions(-)

diff --git a/liveness.c b/liveness.c
index eeff0f7..90c9d56 100644
--- a/liveness.c
+++ b/liveness.c
@@ -13,21 +13,32 @@
 #include "flow.h"
 
 static void phi_defines(struct instruction * phi_node, pseudo_t target,
-	void (*defines)(struct basic_block *, struct instruction *, pseudo_t))
+	void (*defines)(struct basic_block *, struct instruction *, pseudo_t),
+	unsigned long generation)
 {
 	pseudo_t phi;
 	FOR_EACH_PTR(phi_node->phi_list, phi) {
-		struct instruction *def;
 		if (phi == VOID)
 			continue;
-		def = phi->def;
-		if (!def || !def->bb)
-			continue;
-		if (def->opcode == OP_PHI) {
-			phi_defines(def, target, defines);
+		if (!phi->def || !phi->def->bb)
 			continue;
+
+		/*
+		 * In case of "(PHISOURCE->PHI->)+ PHISOURCE->PHI" chain, move
+		 * "defines" information upstream to the very first PHISOURCE;
+		 * recursion guarded by generation marking of PHI instructions BBs.
+		 */
+		pseudo_t src_pseudo = phi->def->phi_src;
+		if (src_pseudo->type == PSEUDO_REG
+		    && src_pseudo->def->opcode == OP_PHI) {
+			phi_node->bb->generation = generation;
+			if (src_pseudo->def->bb->generation != generation) {
+				phi_defines(src_pseudo->def, target, defines, generation);
+				continue;
+			}
 		}
-		defines(def->bb, phi->def, target);
+
+		defines(phi->def->bb, phi->def, target);
 	} END_FOR_EACH_PTR(phi);
 }
 
@@ -103,7 +114,7 @@ static void track_instruction_usage(struct basic_block *bb, struct instruction *
 	/* Other */
 	case OP_PHI:
 		/* Phi-nodes are "backwards" nodes. Their def doesn't matter */
-		phi_defines(insn, insn->target, def);
+		phi_defines(insn, insn->target, def, ++bb_generation);
 		break;
 
 	case OP_PHISOURCE:
-- 
1.7.1

Re: [PATCH 2/2] better dealing with OP_PHISOURCE insn

[Jan Pokorný]

Only adding that after applying this patch, the sum of warnings/errors
when checking linux-2.6.35.12 sources (defconfig, x86) is not influenced.

-- 
Jan

Re: [PATCH 2/2] better dealing with OP_PHISOURCE insn

[Jan Pokorný]

Reformulated comment to better describe what it does.

(Sorry for inconvenience)

Signed-off-by: Jan Pokorny <pokorny_jan@seznam.cz>
---
 liveness.c |   29 ++++++++++++++++++++---------
 1 files changed, 20 insertions(+), 9 deletions(-)

diff --git a/liveness.c b/liveness.c
index eeff0f7..8c15645 100644
--- a/liveness.c
+++ b/liveness.c
@@ -13,21 +13,32 @@
 #include "flow.h"
 
 static void phi_defines(struct instruction * phi_node, pseudo_t target,
-	void (*defines)(struct basic_block *, struct instruction *, pseudo_t))
+	void (*defines)(struct basic_block *, struct instruction *, pseudo_t),
+	unsigned long generation)
 {
 	pseudo_t phi;
 	FOR_EACH_PTR(phi_node->phi_list, phi) {
-		struct instruction *def;
 		if (phi == VOID)
 			continue;
-		def = phi->def;
-		if (!def || !def->bb)
-			continue;
-		if (def->opcode == OP_PHI) {
-			phi_defines(def, target, defines);
+		if (!phi->def || !phi->def->bb)
 			continue;
+
+		/*
+		 * In case of "(PHISOURCE->PHI->)+ PHISOURCE->PHI" chain, move
+		 * "defines" information upstream to BBs of very initial PHISOURCEs;
+		 * recursion guarded by generation marking of PHI instructions BBs.
+		 */
+		pseudo_t src_pseudo = phi->def->phi_src;
+		if (src_pseudo->type == PSEUDO_REG
+		    && src_pseudo->def->opcode == OP_PHI) {
+			phi_node->bb->generation = generation;
+			if (src_pseudo->def->bb->generation != generation) {
+				phi_defines(src_pseudo->def, target, defines, generation);
+				continue;
+			}
 		}
-		defines(def->bb, phi->def, target);
+
+		defines(phi->def->bb, phi->def, target);
 	} END_FOR_EACH_PTR(phi);
 }
 
@@ -103,7 +114,7 @@ static void track_instruction_usage(struct basic_block *bb, struct instruction *
 	/* Other */
 	case OP_PHI:
 		/* Phi-nodes are "backwards" nodes. Their def doesn't matter */
-		phi_defines(insn, insn->target, def);
+		phi_defines(insn, insn->target, def, ++bb_generation);
 		break;
 
 	case OP_PHISOURCE:
-- 
1.7.1