Possible linearizer issue

Possible linearizer issue

[Dibyendu Majumdar]

Hi

I am investigating a failure in one of the tests. The generated
linearized code has instructions such as:

.L363:
 br          VOID, .L366, .L439
.L366:
 load.32     %r413 <- 44[%arg1]
 br          %r413, .L368, .L369
.L368:
 load.64     %r415 <- 0[s7813er]
 call.32     %r416 <- printf, %r415, $2
 br          .L369
.L369:
 phisrc.32   %phi97(rc) <- $2
 br          .L439
.L439:
 phi.32      %r557 <- %phi95(rc), VOID, %phi97(rc), VOID, VOID, VOID

The test program is here:

https://github.com/dibyendumajumdar/dmr_c/blob/master/tests/set1/cq2.c

Regards
Dibyendu

Re: Possible linearizer issue

[Dibyendu Majumdar]

On 18 March 2017 at 11:41, Dibyendu Majumdar <mobile@majumdar.org.uk> wrote:
> I am investigating a failure in one of the tests. The generated
> linearized code has instructions such as:
>
> .L363:
>  br          VOID, .L366, .L439
> .L366:
>  load.32     %r413 <- 44[%arg1]
>  br          %r413, .L368, .L369
> .L368:
>  load.64     %r415 <- 0[s7813er]
>  call.32     %r416 <- printf, %r415, $2
>  br          .L369
> .L369:
>  phisrc.32   %phi97(rc) <- $2
>  br          .L439
> .L439:
>  phi.32      %r557 <- %phi95(rc), VOID, %phi97(rc), VOID, VOID, VOID
>
> The test program is here:
>
> https://github.com/dibyendumajumdar/dmr_c/blob/master/tests/set1/cq2.c
>

It seems that the issue is occurring in simplify_flow(). If I disable
the call to this, then the program compiles successfully and also
runs. None of my other tests fail with this step disabled.

Any clues what might be going wrong?

Does disabling simplify_flow() have any other effect except for missed
optimizations?

Thanks and Regards
Dibyendu

Re: Possible linearizer issue

[Luc Van Oostenryck]

On Mon, Mar 20, 2017 at 11:43:33PM +0000, Dibyendu Majumdar wrote:
> On 18 March 2017 at 11:41, Dibyendu Majumdar <mobile@majumdar.org.uk> wrote:
> > I am investigating a failure in one of the tests. The generated
> > linearized code has instructions such as:
> >
> > .L363:
> >  br          VOID, .L366, .L439
> > .L366:
> >  load.32     %r413 <- 44[%arg1]
> >  br          %r413, .L368, .L369
> > .L368:
> >  load.64     %r415 <- 0[s7813er]
> >  call.32     %r416 <- printf, %r415, $2
> >  br          .L369
> > .L369:
> >  phisrc.32   %phi97(rc) <- $2
> >  br          .L439
> > .L439:
> >  phi.32      %r557 <- %phi95(rc), VOID, %phi97(rc), VOID, VOID, VOID
> >
> > The test program is here:
> >
> > https://github.com/dibyendumajumdar/dmr_c/blob/master/tests/set1/cq2.c
> >

It's quite old as there is several instance of very similar code that
are quite OK and just this last one is wrong.
I'll look at it tomorrow.
 
> It seems that the issue is occurring in simplify_flow(). If I disable
> the call to this, then the program compiles successfully and also
> runs. None of my other tests fail with this step disabled.
> 
> Any clues what might be going wrong?

I suspect an issue with the tracking of pseudo usage.
 
> Does disabling simplify_flow() have any other effect except for missed
> optimizations?

It should not.

-- Luc

Re: Possible linearizer issue

[Luc Van Oostenryck]

On Sat, Mar 18, 2017 at 11:41:26AM +0000, Dibyendu Majumdar wrote:
> Hi
> 
> I am investigating a failure in one of the tests. The generated
> linearized code has instructions such as:
> 
> .L363:
>  br          VOID, .L366, .L439
> .L366:
>  load.32     %r413 <- 44[%arg1]
>  br          %r413, .L368, .L369
> .L368:
>  load.64     %r415 <- 0[s7813er]
>  call.32     %r416 <- printf, %r415, $2
>  br          .L369
> .L369:
>  phisrc.32   %phi97(rc) <- $2
>  br          .L439
> .L439:
>  phi.32      %r557 <- %phi95(rc), VOID, %phi97(rc), VOID, VOID, VOID
> 
> The test program is here:
> 
> https://github.com/dibyendumajumdar/dmr_c/blob/master/tests/set1/cq2.c

I have looked a bit at this.
Reverting the patch (11b1a83b1 "fix OP_PHI usage in try_to_simplify_bb()")
should fix this but I'm not 100% sure about the consequence.
I'm looking for a proper solution though (but it need a bit infrastructure
code that I first need to put in place, so it will take a bit time).

-- Luc

Re: Possible linearizer issue

[Dibyendu Majumdar]

Hi Luc,

On 21 March 2017 at 15:05, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> On Sat, Mar 18, 2017 at 11:41:26AM +0000, Dibyendu Majumdar wrote:
>> I am investigating a failure in one of the tests. The generated
>> linearized code has instructions such as:
>>
>> .L363:
>>  br          VOID, .L366, .L439
>> .L366:
>>  load.32     %r413 <- 44[%arg1]
>>  br          %r413, .L368, .L369
>> .L368:
>>  load.64     %r415 <- 0[s7813er]
>>  call.32     %r416 <- printf, %r415, $2
>>  br          .L369
>> .L369:
>>  phisrc.32   %phi97(rc) <- $2
>>  br          .L439
>> .L439:
>>  phi.32      %r557 <- %phi95(rc), VOID, %phi97(rc), VOID, VOID, VOID
>>
>> The test program is here:
>>
>> https://github.com/dibyendumajumdar/dmr_c/blob/master/tests/set1/cq2.c
>
> I have looked a bit at this.
> Reverting the patch (11b1a83b1 "fix OP_PHI usage in try_to_simplify_bb()")
> should fix this but I'm not 100% sure about the consequence.
> I'm looking for a proper solution though (but it need a bit infrastructure
> code that I first need to put in place, so it will take a bit time).
>

I can confirm that removing that patch did fix the issue.

Thanks and Regards
Dibyendu

[PATCH] fix OP_PHI usage in try_to_simplify_bb(), correctly

[Luc Van Oostenryck]

Patch 11b1a83b1 solved an issue with dangling PSEUDO_PHI
by killing it's use after a branch rewrite.

However, the change didn't took in account the fact that,
even after the branch rewrite, some other paths may exist
where this pseudo was needed.

Fix this by cheking that no such path exist before killing
the (usage of the) pseudo.

Fixes: 11b1a83b1 "fix OP_PHI usage in try_to_simplify_bb()"
Reported-by: Dibyendu Majumdar <mobile@majumdar.org.uk>
Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 flow.c                       | 35 ++++++++++++++++++++++++++++++++++-
 validation/kill-phi-ttsbb2.c | 40 ++++++++++++++++++++++++++++++++++++++++
 2 files changed, 74 insertions(+), 1 deletion(-)
 create mode 100644 validation/kill-phi-ttsbb2.c

diff --git a/flow.c b/flow.c
index a5332203f..c12bc0716 100644
--- a/flow.c
+++ b/flow.c
@@ -79,6 +79,39 @@ static int bb_depends_on(struct basic_block *target, struct basic_block *src)
 	return 0;
 }
 
+/*
+ * Return 1 if 'pseudo' is needed in some parent of 'bb'.
+ * Need liveness info.
+ */
+static int needed_phisrc(struct instruction *phi, struct basic_block *curr, unsigned long generation)
+{
+	pseudo_t target = phi->target;
+	struct basic_block *bb;
+	int rc = 0;
+
+	curr->generation = generation;
+	FOR_EACH_PTR(curr->children, bb) {
+		if (bb->generation == generation)
+			continue;
+		if (bb == phi->bb)
+			continue;
+		if (pseudo_in_list(bb->defines, target)) {
+			continue;
+		}
+		if (pseudo_in_list(bb->needs, target)) {
+			rc = 1;
+			goto ret;
+		}
+		rc = needed_phisrc(phi, bb, generation);
+		if (rc)
+			goto ret;
+
+	} END_FOR_EACH_PTR(bb);
+
+ret:
+	return rc;
+}
+
 /*
  * When we reach here, we have:
  *  - a basic block that ends in a conditional branch and
@@ -121,7 +154,7 @@ static int try_to_simplify_bb(struct basic_block *bb, struct instruction *first,
 			continue;
 		changed |= rewrite_branch(source, &br->bb_true, bb, target);
 		changed |= rewrite_branch(source, &br->bb_false, bb, target);
-		if (changed)
+		if (changed && !needed_phisrc(first, source, ++bb_generation))
 			kill_use(THIS_ADDRESS(phi));
 	} END_FOR_EACH_PTR(phi);
 	return changed;
diff --git a/validation/kill-phi-ttsbb2.c b/validation/kill-phi-ttsbb2.c
new file mode 100644
index 000000000..c7d89aa0e
--- /dev/null
+++ b/validation/kill-phi-ttsbb2.c
@@ -0,0 +1,40 @@
+extern int error(int);
+
+int foo(int perr);
+int foo(int perr)
+{
+	int err = 0;
+	int rc = 0;
+	int j = 0;
+	int i = 1;
+
+	i && j++;
+
+	i-- && j;
+
+	i && j--;
+
+	if (j != 1) {
+		err = 1;
+		if (perr)
+			error(1);
+	}
+
+	if (err != 0)
+		rc = 1;
+
+	return rc;
+}
+
+/*
+ * check-name: kill-phi-ttsbb2
+ * check-description:
+ *	Verify if OP_PHI usage is adjusted after successful try_to_simplify_bb()
+ * check-warning: this test is sensitive to details of code generation
+ *                with proper bb packing (taking care of phi-nodes) it
+ *		  will be optimized away and test nothing. You have been warned.
+ * check-command: test-linearize $file
+ * check-output-ignore
+ *
+ * check-output-excludes: VOID
+ */
-- 
2.12.0

Re: [PATCH] fix OP_PHI usage in try_to_simplify_bb(), correctly

[Christopher Li]

On Wed, Mar 22, 2017 at 6:53 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> Patch 11b1a83b1 solved an issue with dangling PSEUDO_PHI
> by killing it's use after a branch rewrite.
>
> However, the change didn't took in account the fact that,
> even after the branch rewrite, some other paths may exist
> where this pseudo was needed.
>
> Fix this by cheking that no such path exist before killing
> the (usage of the) pseudo.
>
> Fixes: 11b1a83b1 "fix OP_PHI usage in try_to_simplify_bb()"
> Reported-by: Dibyendu Majumdar <mobile@majumdar.org.uk>
> Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
> ---
>  flow.c                       | 35 ++++++++++++++++++++++++++++++++++-
>  validation/kill-phi-ttsbb2.c | 40 ++++++++++++++++++++++++++++++++++++++++
>  2 files changed, 74 insertions(+), 1 deletion(-)
>  create mode 100644 validation/kill-phi-ttsbb2.c
>
> diff --git a/flow.c b/flow.c
> index a5332203f..c12bc0716 100644
> --- a/flow.c
> +++ b/flow.c
> @@ -79,6 +79,39 @@ static int bb_depends_on(struct basic_block *target, struct basic_block *src)
>         return 0;
>  }
>
> +/*
> + * Return 1 if 'pseudo' is needed in some parent of 'bb'.
> + * Need liveness info.
> + */
> +static int needed_phisrc(struct instruction *phi, struct basic_block *curr, unsigned long generation)
> +{
> +       pseudo_t target = phi->target;
> +       struct basic_block *bb;
> +       int rc = 0;
> +
> +       curr->generation = generation;
> +       FOR_EACH_PTR(curr->children, bb) {
> +               if (bb->generation == generation)
> +                       continue;
> +               if (bb == phi->bb)
> +                       continue;
> +               if (pseudo_in_list(bb->defines, target)) {
> +                       continue;
> +               }

For just one line continue, there is no need for {}

> +               if (pseudo_in_list(bb->needs, target)) {
> +                       rc = 1;
> +                       goto ret;

Can this simplify as "return 1;"

> +               }
> +               rc = needed_phisrc(phi, bb, generation);
> +               if (rc)
> +                       goto ret;
needed_phisrc(phi, bb, generation)

And "return 1;" here
> +
> +       } END_FOR_EACH_PTR(bb);


> +
> +ret:
> +       return rc;

"return 0" here.
There is no need for rc variable.

Chris

Re: [PATCH] fix OP_PHI usage in try_to_simplify_bb(), correctly

[Luc Van Oostenryck]

On Sat, Apr 1, 2017 at 1:27 AM, Christopher Li <sparse@chrisli.org> wrote:

>> +       curr->generation = generation;
>> +       FOR_EACH_PTR(curr->children, bb) {
>> +               if (bb->generation == generation)
>> +                       continue;
>> +               if (bb == phi->bb)
>> +                       continue;
>> +               if (pseudo_in_list(bb->defines, target)) {
>> +                       continue;
>> +               }
>
> For just one line continue, there is no need for {}
>
>> +               if (pseudo_in_list(bb->needs, target)) {
>> +                       rc = 1;
>> +                       goto ret;
>
> Can this simplify as "return 1;"
>
>> +               }
>> +               rc = needed_phisrc(phi, bb, generation);
>> +               if (rc)
>> +                       goto ret;
> needed_phisrc(phi, bb, generation)
>
> And "return 1;" here
>> +
>> +       } END_FOR_EACH_PTR(bb);
>
>
>> +
>> +ret:
>> +       return rc;
>
> "return 0" here.
> There is no need for rc variable.

Yes, sure. This is some debugging leftover.
In truth, I detest this patch, it's a bandaid more than anything else
but I haven't anything better for the moment.

I'll respin it but it will most probably be for Sunday.

-- Luc