[PATCH] ignore VOID when trying to if-convert phi-nodes

[PATCH] ignore VOID when trying to if-convert phi-nodes

[Luc Van Oostenryck]

Simple if-then-else expressions can often be
replaced by an OP_SELECT. This is done in a very
generic way by looking not at the test/if part but
at OP_PHIs which contain exactly 2 values.

An implementation detail makes that the address
of valid OP_PHI's sources must not change, so the
list holding these values must not be repacked and such.
As consequence, when a value need to be removed from the
list this value is simply replaced in the list by a VOID.
These VOIDs must then be ignored when processing OP_PHI's
sources.
But for the if-conversion, these VOID are not ignored
and are thus considered like any other value which in turn
make miss some optimizatin opportunities.
For example code like:
	int foo(int a)
	{
		if (a)
			return 0;
		else
			return 1;
		return 2;
	}

will be linearized into something like:
	...
	phi.32      %r2 <- %phi1, %phi2, VOID
	ret.32      %r2
where %phi1 & %phi2 correspond to the 'return 0' & 'return 1'
and the VOID correspond to the dead 'return 2'.
This code should be trivially be converted to a select
but is not because the OP_PHI is considered as having 3
elements instead of 2.

Fix this by filtering out these VOIDs before checking the
conditions of the if-conversion.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
 simplify.c                         | 25 +++++++++++++++++++++++--
 validation/optim/void-if-convert.c | 19 +++++++++++++++++++
 2 files changed, 42 insertions(+), 2 deletions(-)
 create mode 100644 validation/optim/void-if-convert.c

diff --git a/simplify.c b/simplify.c
index 5d00937f1..cf9ca15f2 100644
--- a/simplify.c
+++ b/simplify.c
@@ -26,16 +26,37 @@ static struct basic_block *phi_parent(struct basic_block *source, pseudo_t pseud
 	return first_basic_block(source->parents);
 }
 
+/*
+ * Essentially the same as linearize_ptr_list()
+ * but ignoring VOID.
+ * Returns 0 if the the list contained the expected
+ * number of element, 1 or -1 if there was more or less.
+ */
+static int get_phi_list(pseudo_t array[], int n, struct pseudo_list *list)
+{
+	pseudo_t phi;
+	int i = 0;
+
+	FOR_EACH_PTR(list, phi) {
+		if (phi == VOID)
+			continue;
+		if (i >= n)
+			return 1;
+		array[i++] = phi;
+	} END_FOR_EACH_PTR(phi);
+	return (i == n) ? 0 : -1;
+}
+
 static int if_convert_phi(struct instruction *insn)
 {
-	pseudo_t array[3];
+	pseudo_t array[2];
 	struct basic_block *parents[3];
 	struct basic_block *bb, *bb1, *bb2, *source;
 	struct instruction *br;
 	pseudo_t p1, p2;
 
 	bb = insn->bb;
-	if (linearize_ptr_list((struct ptr_list *)insn->phi_list, (void **)array, 3) != 2)
+	if (get_phi_list(array, 2, insn->phi_list) != 0)
 		return 0;
 	if (linearize_ptr_list((struct ptr_list *)bb->parents, (void **)parents, 3) != 2)
 		return 0;
diff --git a/validation/optim/void-if-convert.c b/validation/optim/void-if-convert.c
new file mode 100644
index 000000000..66513c4dc
--- /dev/null
+++ b/validation/optim/void-if-convert.c
@@ -0,0 +1,19 @@
+int foo(int a)
+{
+	if (a)
+		return 0;
+	else
+		return 1;
+	return 2;
+}
+
+/*
+ * check-name: Ignore VOID in if-convert
+ * check-command: test-linearize -Wno-decl $file
+ * check-output-ignore
+ *
+ * check-output-excludes: phisrc\\.
+ * check-output-excludes: phi\\.
+ * check-output-excludes: VOID
+ * check-output-contains: seteq\\.
+ */
-- 
2.12.0

Re: [PATCH] ignore VOID when trying to if-convert phi-nodes

[Christopher Li]

Over all looks good. Some minor comment follows.

On Tue, May 9, 2017 at 3:06 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> +/*
> + * Essentially the same as linearize_ptr_list()
> + * but ignoring VOID.
> + * Returns 0 if the the list contained the expected
> + * number of element, 1 or -1 if there was more or less.
> + */
> +static int get_phi_list(pseudo_t array[], int n, struct pseudo_list *list)

The function name does not reflect that it is going to skip the VOID entry
and the API to return value is a little bit non straight forward. e.g.
If the result entries is less than the quest one, there is no way to get
know the exact number of entry returned.

Just RFC here, how about having one helper function to do
the normal linearize ptr and skip the VOID entry. Which return how
many entry it scanned. (it return n+1 if there is more than n request one).

Then the second function you can do the compare to "n" thing.
After inline it would behave exactly like your current function.

> +{
> +       pseudo_t phi;
> +       int i = 0;
> +
> +       FOR_EACH_PTR(list, phi) {
> +               if (phi == VOID)
> +                       continue;
> +               if (i >= n)
> +                       return 1;
> +               array[i++] = phi;
> +       } END_FOR_EACH_PTR(phi);
> +       return (i == n) ? 0 : -1;

Maybe here can be use (i - n)?, it will return -2 if 2 entry less than
requested.

> -       pseudo_t array[3];
> +       pseudo_t array[2];
>         struct basic_block *parents[3];
>         struct basic_block *bb, *bb1, *bb2, *source;
>         struct instruction *br;
>         pseudo_t p1, p2;
>
>         bb = insn->bb;
> -       if (linearize_ptr_list((struct ptr_list *)insn->phi_list, (void **)array, 3) != 2)
> +       if (get_phi_list(array, 2, insn->phi_list) != 0)

It is not necessary to compare to zero.

Chris

Re: [PATCH] ignore VOID when trying to if-convert phi-nodes

[Luc Van Oostenryck]

On Thu, May 11, 2017 at 7:13 PM, Christopher Li <sparse@chrisli.org> wrote:
> Over all looks good. Some minor comment follows.
>
> On Tue, May 9, 2017 at 3:06 PM, Luc Van Oostenryck
> <luc.vanoostenryck@gmail.com> wrote:
>> +/*
>> + * Essentially the same as linearize_ptr_list()
>> + * but ignoring VOID.
>> + * Returns 0 if the the list contained the expected
>> + * number of element, 1 or -1 if there was more or less.
>> + */
>> +static int get_phi_list(pseudo_t array[], int n, struct pseudo_list *list)
>
> The function name does not reflect that it is going to skip the VOID entry

Well yes, but I wasn't ready to use a name like 'get_real_phi_list()' or
something like this. These VOIDs really mean 'there is no element here/
the entry has been removed'. So, I think that it's the right thing to put
the VOID thing in the comment and have such a function name.

But I can look after another name.

> and the API to return value is a little bit non straight forward. e.g.
> If the result entries is less than the quest one, there is no way to get
> know the exact number of entry returned.

Yes, I know.
My first version did this but then I changed my mind because
it was slightly easier so and having the exact number returned
is not needed (it's not like we're we're doing some dynamic allocation
and redo a malloc() with the right number if the initial guess was too
small). The only thing that really matters here is if the effective number
of phisrc is the one we're interested in: 2.

OTOH, I don't have a strong opinion on how it should best be done
and other uses can maybe be interested in the exact number.

> Just RFC here, how about having one helper function to do
> the normal linearize ptr and skip the VOID entry. Which return how
> many entry it scanned. (it return n+1 if there is more than n request one).
>
> Then the second function you can do the compare to "n" thing.
> After inline it would behave exactly like your current function.

I'll see what I can do in this direction.

>> +{
>> +       pseudo_t phi;
>> +       int i = 0;
>> +
>> +       FOR_EACH_PTR(list, phi) {
>> +               if (phi == VOID)
>> +                       continue;
>> +               if (i >= n)
>> +                       return 1;
>> +               array[i++] = phi;
>> +       } END_FOR_EACH_PTR(phi);
>> +       return (i == n) ? 0 : -1;
>
> Maybe here can be use (i - n)?, it will return -2 if 2 entry less than
> requested.

Yes, it's a possibility.

>> -       pseudo_t array[3];
>> +       pseudo_t array[2];
>>         struct basic_block *parents[3];
>>         struct basic_block *bb, *bb1, *bb2, *source;
>>         struct instruction *br;
>>         pseudo_t p1, p2;
>>
>>         bb = insn->bb;
>> -       if (linearize_ptr_list((struct ptr_list *)insn->phi_list, (void **)array, 3) != 2)
>> +       if (get_phi_list(array, 2, insn->phi_list) != 0)
>
> It is not necessary to compare to zero.

Indeed.

-- Luc

Re: [PATCH] ignore VOID when trying to if-convert phi-nodes

[Luc Van Oostenryck]

On Thu, May 11, 2017 at 8:50 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> On Thu, May 11, 2017 at 7:13 PM, Christopher Li <sparse@chrisli.org> wrote:
>> Over all looks good. Some minor comment follows.
>>
>> On Tue, May 9, 2017 at 3:06 PM, Luc Van Oostenryck
>> <luc.vanoostenryck@gmail.com> wrote:
>>> +/*
>>> + * Essentially the same as linearize_ptr_list()
>>> + * but ignoring VOID.
>>> + * Returns 0 if the the list contained the expected
>>> + * number of element, 1 or -1 if there was more or less.
>>> + */
>>> +static int get_phi_list(pseudo_t array[], int n, struct pseudo_list *list)
>>
>> The function name does not reflect that it is going to skip the VOID entry
>
> Well yes, but I wasn't ready to use a name like 'get_real_phi_list()' or
> something like this. These VOIDs really mean 'there is no element here/
> the entry has been removed'. So, I think that it's the right thing to put
> the VOID thing in the comment and have such a function name.
>
> But I can look after another name.
>
>> and the API to return value is a little bit non straight forward. e.g.
>> If the result entries is less than the quest one, there is no way to get
>> know the exact number of entry returned.
>
> Yes, I know.
> My first version did this but then I changed my mind because
> it was slightly easier so and having the exact number returned
> is not needed (it's not like we're we're doing some dynamic allocation
> and redo a malloc() with the right number if the initial guess was too
> small). The only thing that really matters here is if the effective number
> of phisrc is the one we're interested in: 2.
>
> OTOH, I don't have a strong opinion on how it should best be done
> and other uses can maybe be interested in the exact number.
>
>> Just RFC here, how about having one helper function to do
>> the normal linearize ptr and skip the VOID entry. Which return how
>> many entry it scanned. (it return n+1 if there is more than n request one).
>>
>> Then the second function you can do the compare to "n" thing.
>> After inline it would behave exactly like your current function.
>
> I'll see what I can do in this direction.

I've looked at this and I really think that it would make things more
complicated than needed for no advantages.

The function is really a local helper, something specialized, unlike
linearize_ptr_list(). So I've changed a bit the name, the comment,
the prototype and the meaning of the function to make this more
obvious (and yes avoid to (mis)reuse this function in others contexts).

New version is coming.

-- Luc

[PATCH v2] ignore VOID when trying to if-convert phi-nodes

[Luc Van Oostenryck]

Simple if-then-else expressions can often be
replaced by an OP_SELECT. This is done in a very
generic way by looking not at the test/if part but
at OP_PHIs which contain exactly 2 values.

An implementation detail makes that the address
of valid OP_PHI's sources must not change, so the
list holding these values must not be repacked and such.
As consequence, when a value need to be removed from the
list this value is simply replaced in the list by a VOID.
These VOIDs must then be ignored when processing OP_PHI's
sources.
But for the if-conversion, these VOID are not ignored
and are thus considered like any other value which in turn
make miss some optimization opportunities.
For example code like:
	int foo(int a)
	{
		if (a)
			return 0;
		else
			return 1;
		return 2;
	}

will be linearized into something like:
	...
	phi.32      %r2 <- %phi1, %phi2, VOID
	ret.32      %r2
where %phi1 & %phi2 correspond to the 'return 0' & 'return 1'
and the VOID correspond to the dead 'return 2'.
This code should be trivially be converted to a select
but is not because the OP_PHI is considered as having 3
elements instead of 2.

Worse, if at some moment we would have a phi list with:
	phi.32      %r2 <- %phi1, VOID
then the optimization would trigger but the corresponding
code make the assumption that the pseudos are the target
of an OP_PHISOURCE instruction, which VOIDs, of course,
are not and a crash should ensue.

Fix this by filtering out these VOIDs before checking the
conditions of the if-conversion.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---
Changes since v1:
- partially address Chris remarks:
  - change how the negative return value is calculated
  - change the unneeded compare against zero
- change the name, comment, prototype and meaning of the
  function to make clear that what we're interested in here
  is the OP_PHISOURCE, not the %phi pseudos.
- add check to insure that we're indeed dealing with OP_PHISOURCEs
- add a paragraph in the commit log about a potential crash

 simplify.c                         | 41 ++++++++++++++++++++++++++++++++------
 validation/optim/void-if-convert.c | 19 ++++++++++++++++++
 2 files changed, 54 insertions(+), 6 deletions(-)
 create mode 100644 validation/optim/void-if-convert.c

diff --git a/simplify.c b/simplify.c
index 5d00937f1..7ae34b58f 100644
--- a/simplify.c
+++ b/simplify.c
@@ -26,23 +26,52 @@ static struct basic_block *phi_parent(struct basic_block *source, pseudo_t pseud
 	return first_basic_block(source->parents);
 }
 
+/*
+ * Copy the phi-node's phisrcs into to given array.
+ * Returns 0 if the the list contained the expected
+ * number of element, a positive number if there was
+ * more than expected and a negative one if less.
+ *
+ * Note: we can't reuse a function like linearize_ptr_list()
+ * because any VOIDs in the phi-list must be ignored here
+ * as in this context they mean 'entry has been removed'.
+ */
+static int get_phisources(struct instruction *sources[], int nbr, struct instruction *insn)
+{
+	pseudo_t phi;
+	int i = 0;
+
+	assert(insn->opcode == OP_PHI);
+	FOR_EACH_PTR(insn->phi_list, phi) {
+		struct instruction *def;
+		if (phi == VOID)
+			continue;
+		if (i >= nbr)
+			return 1;
+		def = phi->def;
+		assert(def->opcode == OP_PHISOURCE);
+		sources[i++] = def;
+	} END_FOR_EACH_PTR(phi);
+	return nbr - i;
+}
+
 static int if_convert_phi(struct instruction *insn)
 {
-	pseudo_t array[3];
+	struct instruction *array[2];
 	struct basic_block *parents[3];
 	struct basic_block *bb, *bb1, *bb2, *source;
 	struct instruction *br;
 	pseudo_t p1, p2;
 
 	bb = insn->bb;
-	if (linearize_ptr_list((struct ptr_list *)insn->phi_list, (void **)array, 3) != 2)
+	if (get_phisources(array, 2, insn))
 		return 0;
 	if (linearize_ptr_list((struct ptr_list *)bb->parents, (void **)parents, 3) != 2)
 		return 0;
-	p1 = array[0]->def->src1;
-	bb1 = array[0]->def->bb;
-	p2 = array[1]->def->src1;
-	bb2 = array[1]->def->bb;
+	p1 = array[0]->src1;
+	bb1 = array[0]->bb;
+	p2 = array[1]->src1;
+	bb2 = array[1]->bb;
 
 	/* Only try the simple "direct parents" case */
 	if ((bb1 != parents[0] || bb2 != parents[1]) &&
diff --git a/validation/optim/void-if-convert.c b/validation/optim/void-if-convert.c
new file mode 100644
index 000000000..66513c4dc
--- /dev/null
+++ b/validation/optim/void-if-convert.c
@@ -0,0 +1,19 @@
+int foo(int a)
+{
+	if (a)
+		return 0;
+	else
+		return 1;
+	return 2;
+}
+
+/*
+ * check-name: Ignore VOID in if-convert
+ * check-command: test-linearize -Wno-decl $file
+ * check-output-ignore
+ *
+ * check-output-excludes: phisrc\\.
+ * check-output-excludes: phi\\.
+ * check-output-excludes: VOID
+ * check-output-contains: seteq\\.
+ */
-- 
2.12.2

Re: [PATCH v2] ignore VOID when trying to if-convert phi-nodes

[Christopher Li]

Looks good.

Signed-of-by: <sparse@chrisli.org>

On Thu, May 11, 2017 at 1:46 PM, Luc Van Oostenryck
<luc.vanoostenryck@gmail.com> wrote:
> +static int get_phisources(struct instruction *sources[], int nbr, struct instruction *insn)
> +{
> +       pseudo_t phi;
> +       int i = 0;
> +
> +       assert(insn->opcode == OP_PHI);
> +       FOR_EACH_PTR(insn->phi_list, phi) {
> +               struct instruction *def;
> +               if (phi == VOID)
> +                       continue;
> +               if (i >= nbr)
> +                       return 1;
> +               def = phi->def;
> +               assert(def->opcode == OP_PHISOURCE);
> +               sources[i++] = def;
> +       } END_FOR_EACH_PTR(phi);
> +       return nbr - i;

Here if you want to return negative value it should be i - nbr.
Of course if you only care about return zero or not then it does
not matter. The call in this patch does only compare to zero
any way.

Chris

Re: [PATCH v2] ignore VOID when trying to if-convert phi-nodes

[Luc Van Oostenryck]

On Thu, May 11, 2017 at 10:57 PM, Christopher Li <sparse@chrisli.org> wrote:

>> +       return nbr - i;
>
> Here if you want to return negative value it should be i - nbr.
> Of course if you only care about return zero or not then it does
> not matter. The call in this patch does only compare to zero
> any way.

You're right, I wanted a negative number and the comment says
so. v3 is coming. Must be tired today.

Thanks for noticing this.

-- Luc

[PATCH v3] ignore VOID when trying to if-convert phi-nodes

[Luc Van Oostenryck]

Simple if-then-else expressions can often be
replaced by an OP_SELECT. This is done in a very
generic way by looking not at the test/if part but
at OP_PHIs which contain exactly 2 values.

An implementation detail makes that the address
of valid OP_PHI's sources must not change, so the
list holding these values must not be repacked and such.
As consequence, when a value need to be removed from the
list this value is simply replaced in the list by a VOID.
These VOIDs must then be ignored when processing OP_PHI's
sources.
But for the if-conversion, these VOID are not ignored
and are thus considered like any other value which in turn
make miss some optimization opportunities.
For example code like:
	int foo(int a)
	{
		if (a)
			return 0;
		else
			return 1;
		return 2;
	}

will be linearized into something like:
	...
	phi.32      %r2 <- %phi1, %phi2, VOID
	ret.32      %r2
where %phi1 & %phi2 correspond to the 'return 0' & 'return 1'
and the VOID correspond to the dead 'return 2'.
This code should be trivially be converted to a select
but is not because the OP_PHI is considered as having 3
elements instead of 2.

Worse, if at some moment we would have a phi list with:
	phi.32      %r2 <- %phi1, VOID
then the optimization would trigger but the corresponding
code make the assumption that the pseudos are the target
of an OP_PHISOURCE instruction, which VOIDs, of course,
are not and a crash should ensue.

Fix this by filtering out these VOIDs before checking the
conditions of the if-conversion.

Signed-off-by: Luc Van Oostenryck <luc.vanoostenryck@gmail.com>
---

Changes since v2:
- fix get_phisources()'s return value to be negative
  as specified in the function comment
 
Changes since v1:
- partially address Chris remarks:
  - change how the negative return value is calculated
  - change the unneeded compare against zero
- change the name, comment, prototype and meaning of the
  function to make clear that what we're interested in here
  is the OP_PHISOURCE, not the %phi pseudos.
- add check to insure that we're indeed dealing with OP_PHISOURCEs
- add a paragraph in the commit log about a potential crash

 simplify.c                         | 41 ++++++++++++++++++++++++++++++++------
 validation/optim/void-if-convert.c | 19 ++++++++++++++++++
 2 files changed, 54 insertions(+), 6 deletions(-)
 create mode 100644 validation/optim/void-if-convert.c

diff --git a/simplify.c b/simplify.c
index 5d00937f1..a141ddd43 100644
--- a/simplify.c
+++ b/simplify.c
@@ -26,23 +26,52 @@ static struct basic_block *phi_parent(struct basic_block *source, pseudo_t pseud
 	return first_basic_block(source->parents);
 }
 
+/*
+ * Copy the phi-node's phisrcs into to given array.
+ * Returns 0 if the the list contained the expected
+ * number of element, a positive number if there was
+ * more than expected and a negative one if less.
+ *
+ * Note: we can't reuse a function like linearize_ptr_list()
+ * because any VOIDs in the phi-list must be ignored here
+ * as in this context they mean 'entry has been removed'.
+ */
+static int get_phisources(struct instruction *sources[], int nbr, struct instruction *insn)
+{
+	pseudo_t phi;
+	int i = 0;
+
+	assert(insn->opcode == OP_PHI);
+	FOR_EACH_PTR(insn->phi_list, phi) {
+		struct instruction *def;
+		if (phi == VOID)
+			continue;
+		if (i >= nbr)
+			return 1;
+		def = phi->def;
+		assert(def->opcode == OP_PHISOURCE);
+		sources[i++] = def;
+	} END_FOR_EACH_PTR(phi);
+	return i - nbr;
+}
+
 static int if_convert_phi(struct instruction *insn)
 {
-	pseudo_t array[3];
+	struct instruction *array[2];
 	struct basic_block *parents[3];
 	struct basic_block *bb, *bb1, *bb2, *source;
 	struct instruction *br;
 	pseudo_t p1, p2;
 
 	bb = insn->bb;
-	if (linearize_ptr_list((struct ptr_list *)insn->phi_list, (void **)array, 3) != 2)
+	if (get_phisources(array, 2, insn))
 		return 0;
 	if (linearize_ptr_list((struct ptr_list *)bb->parents, (void **)parents, 3) != 2)
 		return 0;
-	p1 = array[0]->def->src1;
-	bb1 = array[0]->def->bb;
-	p2 = array[1]->def->src1;
-	bb2 = array[1]->def->bb;
+	p1 = array[0]->src1;
+	bb1 = array[0]->bb;
+	p2 = array[1]->src1;
+	bb2 = array[1]->bb;
 
 	/* Only try the simple "direct parents" case */
 	if ((bb1 != parents[0] || bb2 != parents[1]) &&
diff --git a/validation/optim/void-if-convert.c b/validation/optim/void-if-convert.c
new file mode 100644
index 000000000..66513c4dc
--- /dev/null
+++ b/validation/optim/void-if-convert.c
@@ -0,0 +1,19 @@
+int foo(int a)
+{
+	if (a)
+		return 0;
+	else
+		return 1;
+	return 2;
+}
+
+/*
+ * check-name: Ignore VOID in if-convert
+ * check-command: test-linearize -Wno-decl $file
+ * check-output-ignore
+ *
+ * check-output-excludes: phisrc\\.
+ * check-output-excludes: phi\\.
+ * check-output-excludes: VOID
+ * check-output-contains: seteq\\.
+ */
-- 
2.12.2