[PATCH] Fix PR tree-optimization/71170

[PATCH] Fix PR tree-optimization/71170

[Martin Liška]

[-- Attachment #1: Type: text/plain, Size: 223 bytes --]

Hello.

Following patch fixes the ICE as it defensively finds the right
place where a new STMT should be inserted.

Patch bootstraps on x86_64-linux-gnu and no new regression is introduced.

Ready for trunk?
Thanks,
Martin

[-- Attachment #2: 0001-Fix-PR-tree-optimization-71170.patch --]
[-- Type: text/x-patch, Size: 2208 bytes --]

From de9f966a20cf08721dc8bdb83144b07f72e6cc59 Mon Sep 17 00:00:00 2001
From: marxin <mliska@suse.cz>
Date: Wed, 18 May 2016 13:21:36 +0200
Subject: [PATCH] Fix PR tree-optimization/71170

gcc/ChangeLog:

2016-05-18  Martin Liska  <mliska@suse.cz>

	* tree-ssa-reassoc.c (rewrite_expr_tree): Insert a new gimple
	stmt if we would use a SSA_NAME before its definition.
---
 gcc/tree-ssa-reassoc.c | 9 +++------
 1 file changed, 3 insertions(+), 6 deletions(-)

diff --git a/gcc/tree-ssa-reassoc.c b/gcc/tree-ssa-reassoc.c
index 3b5f36b..a8fd889 100644
--- a/gcc/tree-ssa-reassoc.c
+++ b/gcc/tree-ssa-reassoc.c
@@ -3813,7 +3813,8 @@ rewrite_expr_tree (gimple *stmt, unsigned int opindex,
 	     some redundant operations, so unless we are just swapping the
 	     arguments or unless there is no change at all (then we just
 	     return lhs), force creation of a new SSA_NAME.  */
-	  if (changed || ((rhs1 != oe2->op || rhs2 != oe1->op) && opindex))
+	  if (changed || ((rhs1 != oe2->op || rhs2 != oe1->op) && opindex)
+	      || find_insert_point (stmt, oe1->op, oe2->op) != stmt)
 	    {
 	      gimple *insert_point
 		= find_insert_point (stmt, oe1->op, oe2->op);
@@ -3830,8 +3831,6 @@ rewrite_expr_tree (gimple *stmt, unsigned int opindex,
 	    }
 	  else
 	    {
-	      gcc_checking_assert (find_insert_point (stmt, oe1->op, oe2->op)
-				   == stmt);
 	      gimple_assign_set_rhs1 (stmt, oe1->op);
 	      gimple_assign_set_rhs2 (stmt, oe2->op);
 	      update_stmt (stmt);
@@ -3876,7 +3875,7 @@ rewrite_expr_tree (gimple *stmt, unsigned int opindex,
 	 Otherwise ensure the old lhs SSA_NAME is not reused and
 	 create a new stmt as well, so that any debug stmts will be
 	 properly adjusted.  */
-      if (changed)
+      if (changed || find_insert_point (stmt, new_rhs1, oe->op) != stmt)
 	{
 	  gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
 	  unsigned int uid = gimple_uid (stmt);
@@ -3894,8 +3893,6 @@ rewrite_expr_tree (gimple *stmt, unsigned int opindex,
 	}
       else
 	{
-	  gcc_checking_assert (find_insert_point (stmt, new_rhs1, oe->op)
-			       == stmt);
 	  gimple_assign_set_rhs1 (stmt, new_rhs1);
 	  gimple_assign_set_rhs2 (stmt, oe->op);
 	  update_stmt (stmt);
-- 
2.8.2

Re: [PATCH] Fix PR tree-optimization/71170

[Richard Biener]

On Thu, May 19, 2016 at 10:04 AM, Martin Liška <mliska@suse.cz> wrote:
> Hello.
>
> Following patch fixes the ICE as it defensively finds the right
> place where a new STMT should be inserted.
>
> Patch bootstraps on x86_64-linux-gnu and no new regression is introduced.
>
> Ready for trunk?

@@ -3813,7 +3813,8 @@ rewrite_expr_tree (gimple *stmt, unsigned int opindex,
             some redundant operations, so unless we are just swapping the
             arguments or unless there is no change at all (then we just
             return lhs), force creation of a new SSA_NAME.  */
-         if (changed || ((rhs1 != oe2->op || rhs2 != oe1->op) && opindex))
+         if (changed || ((rhs1 != oe2->op || rhs2 != oe1->op) && opindex)
+             || find_insert_point (stmt, oe1->op, oe2->op) != stmt)
            {
              gimple *insert_point
                = find_insert_point (stmt, oe1->op, oe2->op);
@@ -3830,8 +3831,6 @@ rewrite_expr_tree (gimple *stmt, unsigned int opindex,
            }
          else
            {
-             gcc_checking_assert (find_insert_point (stmt, oe1->op, oe2->op)
-                                  == stmt);
              gimple_assign_set_rhs1 (stmt, oe1->op);
              gimple_assign_set_rhs2 (stmt, oe2->op);
              update_stmt (stmt);

please CSE the find_insert_point call(s).  The whole code looks somewhat odd
as an insert point of 'stmt' seems to mean we can replace it?!

That said, you might paper over an issue elsewhere here...

That said, I absolutely hate this "insert-point" stuff in reassoc.
Please somebody
sit down and write a simple "scheduler" on GIMPLE and remove all this code from
reassoc.

Richard.

> Thanks,
> Martin

Re: [PATCH] Fix PR tree-optimization/71170

[Kugan Vivekanandarajah]

[-- Attachment #1: Type: text/plain, Size: 1215 bytes --]

Hi Martin,

Thanks for the fix. Just to elaborate (as mentioned in PR)

At tree-ssa-reassoc.c:3897, we have:

stmt:
_15 = _4 + c_7(D);

oe->op def_stmt:
_17 = c_7(D) * 3;


<bb 2>:
a1_6 = s_5(D) * 2;
_1 = (long int) a1_6;
x1_8 = _1 + c_7(D);
a2_9 = s_5(D) * 4;
_2 = (long int) a2_9;
a3_11 = s_5(D) * 6;
_3 = (long int) a3_11;
_16 = x1_8 + c_7(D);
_18 = _1 + _2;
_4 = _16 + _2;
_15 = _4 + c_7(D);
_17 = c_7(D) * 3;
x_13 = _15 + _3;
return x_13;


The root cause of this the place in which we are adding (_17 = c_7(D)
* 3). Finding the right place is not always straightforward as this
case shows.

We could try  Martin Liška's approach, We could also move _17 = c_7(D)
* 3; at tree-ssa-reassoc.c:3897 satisfy the gcc_assert. We could do
this based on the use count of _17.


This patch does this. I have no preferences. Any thoughts ?


Thanks,
Kugan



On 19 May 2016 at 18:04, Martin Liška <mliska@suse.cz> wrote:
> Hello.
>
> Following patch fixes the ICE as it defensively finds the right
> place where a new STMT should be inserted.
>
> Patch bootstraps on x86_64-linux-gnu and no new regression is introduced.
>
> Ready for trunk?
> Thanks,
> Martin

[-- Attachment #2: p4.txt --]
[-- Type: text/plain, Size: 1974 bytes --]

diff --git a/gcc/tree-ssa-reassoc.c b/gcc/tree-ssa-reassoc.c
index 3b5f36b..11beb28 100644
--- a/gcc/tree-ssa-reassoc.c
+++ b/gcc/tree-ssa-reassoc.c
@@ -3830,6 +3830,29 @@ rewrite_expr_tree (gimple *stmt, unsigned int opindex,
 	    }
 	  else
 	    {
+	      /* Change the position of newly added stmt.  */
+	      if (TREE_CODE (oe1->op) == SSA_NAME
+		  && has_zero_uses (oe1->op)
+		  && reassoc_stmt_dominates_stmt_p (stmt, SSA_NAME_DEF_STMT (oe1->op)))
+		{
+		  gimple *def_stmt = SSA_NAME_DEF_STMT (oe1->op);
+		  gimple_stmt_iterator gsi = gsi_for_stmt (def_stmt);
+		  gsi_remove (&gsi, true);
+		  gsi = gsi_for_stmt (stmt);
+		  gsi_insert_before (&gsi, def_stmt, GSI_SAME_STMT);
+		}
+
+	      /* Change the position of newly added stmt.  */
+	      if (TREE_CODE (oe2->op) == SSA_NAME
+		  && has_zero_uses (oe2->op)
+		  && reassoc_stmt_dominates_stmt_p (stmt, SSA_NAME_DEF_STMT (oe2->op)))
+		{
+		  gimple *def_stmt = SSA_NAME_DEF_STMT (oe2->op);
+		  gimple_stmt_iterator gsi = gsi_for_stmt (def_stmt);
+		  gsi_remove (&gsi, true);
+		  gsi = gsi_for_stmt (stmt);
+		  gsi_insert_before (&gsi, def_stmt, GSI_SAME_STMT);
+		}
 	      gcc_checking_assert (find_insert_point (stmt, oe1->op, oe2->op)
 				   == stmt);
 	      gimple_assign_set_rhs1 (stmt, oe1->op);
@@ -3894,6 +3917,17 @@ rewrite_expr_tree (gimple *stmt, unsigned int opindex,
 	}
       else
 	{
+	  /* Change the position of newly added stmt.  */
+	  if (TREE_CODE (oe->op) == SSA_NAME
+	      && has_zero_uses (oe->op)
+	      && reassoc_stmt_dominates_stmt_p (stmt, SSA_NAME_DEF_STMT (oe->op)))
+	    {
+	      gimple *def_stmt = SSA_NAME_DEF_STMT (oe->op);
+	      gimple_stmt_iterator gsi = gsi_for_stmt (def_stmt);
+	      gsi_remove (&gsi, true);
+	      gsi = gsi_for_stmt (stmt);
+	      gsi_insert_before (&gsi, def_stmt, GSI_SAME_STMT);
+	    }
 	  gcc_checking_assert (find_insert_point (stmt, new_rhs1, oe->op)
 			       == stmt);
 	  gimple_assign_set_rhs1 (stmt, new_rhs1);

Re: [PATCH] Fix PR tree-optimization/71170

[Richard Biener]

On Thu, May 19, 2016 at 10:12 AM, Kugan Vivekanandarajah
<kugan.vivekanandarajah@linaro.org> wrote:
> Hi Martin,
>
> Thanks for the fix. Just to elaborate (as mentioned in PR)
>
> At tree-ssa-reassoc.c:3897, we have:
>
> stmt:
> _15 = _4 + c_7(D);
>
> oe->op def_stmt:
> _17 = c_7(D) * 3;
>
>
> <bb 2>:
> a1_6 = s_5(D) * 2;
> _1 = (long int) a1_6;
> x1_8 = _1 + c_7(D);
> a2_9 = s_5(D) * 4;
> _2 = (long int) a2_9;
> a3_11 = s_5(D) * 6;
> _3 = (long int) a3_11;
> _16 = x1_8 + c_7(D);
> _18 = _1 + _2;
> _4 = _16 + _2;
> _15 = _4 + c_7(D);
> _17 = c_7(D) * 3;
> x_13 = _15 + _3;
> return x_13;
>
>
> The root cause of this the place in which we are adding (_17 = c_7(D)
> * 3). Finding the right place is not always straightforward as this
> case shows.
>
> We could try  Martin Liška's approach, We could also move _17 = c_7(D)
> * 3; at tree-ssa-reassoc.c:3897 satisfy the gcc_assert. We could do
> this based on the use count of _17.
>
>
> This patch does this. I have no preferences. Any thoughts ?

I think the issue may be that you fail to set changed to true for the
degenerate case of ending up with a multiply only.

Not sure because neither patch contains a testcase.

Richard.

>
> Thanks,
> Kugan
>
>
>
> On 19 May 2016 at 18:04, Martin Liška <mliska@suse.cz> wrote:
>> Hello.
>>
>> Following patch fixes the ICE as it defensively finds the right
>> place where a new STMT should be inserted.
>>
>> Patch bootstraps on x86_64-linux-gnu and no new regression is introduced.
>>
>> Ready for trunk?
>> Thanks,
>> Martin

Re: [PATCH] Fix PR tree-optimization/71170

[Kugan]

Hi,


On 19/05/16 18:21, Richard Biener wrote:
> On Thu, May 19, 2016 at 10:12 AM, Kugan Vivekanandarajah
> <kugan.vivekanandarajah@linaro.org> wrote:
>> Hi Martin,
>>
>> Thanks for the fix. Just to elaborate (as mentioned in PR)
>>
>> At tree-ssa-reassoc.c:3897, we have:
>>
>> stmt:
>> _15 = _4 + c_7(D);
>>
>> oe->op def_stmt:
>> _17 = c_7(D) * 3;
>>
>>
>> <bb 2>:
>> a1_6 = s_5(D) * 2;
>> _1 = (long int) a1_6;
>> x1_8 = _1 + c_7(D);
>> a2_9 = s_5(D) * 4;
>> _2 = (long int) a2_9;
>> a3_11 = s_5(D) * 6;
>> _3 = (long int) a3_11;
>> _16 = x1_8 + c_7(D);
>> _18 = _1 + _2;
>> _4 = _16 + _2;
>> _15 = _4 + c_7(D);
>> _17 = c_7(D) * 3;
>> x_13 = _15 + _3;
>> return x_13;
>>
>>
>> The root cause of this the place in which we are adding (_17 = c_7(D)
>> * 3). Finding the right place is not always straightforward as this
>> case shows.
>>
>> We could try  Martin Liška's approach, We could also move _17 = c_7(D)
>> * 3; at tree-ssa-reassoc.c:3897 satisfy the gcc_assert. We could do
>> this based on the use count of _17.
>>
>>
>> This patch does this. I have no preferences. Any thoughts ?
> 
> I think the issue may be that you fail to set changed to true for the
> degenerate case of ending up with a multiply only.
> 
> Not sure because neither patch contains a testcase.
> 

Sorry, I should have been specific. There is an existing test-case that
is failing. Thats why I didn't include a test case.

FAIL: gcc.dg/tree-ssa/slsr-30.c (internal compiler error)


Thanks,
Kugan

Re: [PATCH] Fix PR tree-optimization/71170

[Richard Biener]

On Thu, May 19, 2016 at 10:26 AM, Kugan
<kugan.vivekanandarajah@linaro.org> wrote:
> Hi,
>
>
> On 19/05/16 18:21, Richard Biener wrote:
>> On Thu, May 19, 2016 at 10:12 AM, Kugan Vivekanandarajah
>> <kugan.vivekanandarajah@linaro.org> wrote:
>>> Hi Martin,
>>>
>>> Thanks for the fix. Just to elaborate (as mentioned in PR)
>>>
>>> At tree-ssa-reassoc.c:3897, we have:
>>>
>>> stmt:
>>> _15 = _4 + c_7(D);
>>>
>>> oe->op def_stmt:
>>> _17 = c_7(D) * 3;
>>>
>>>
>>> <bb 2>:
>>> a1_6 = s_5(D) * 2;
>>> _1 = (long int) a1_6;
>>> x1_8 = _1 + c_7(D);
>>> a2_9 = s_5(D) * 4;
>>> _2 = (long int) a2_9;
>>> a3_11 = s_5(D) * 6;
>>> _3 = (long int) a3_11;
>>> _16 = x1_8 + c_7(D);
>>> _18 = _1 + _2;
>>> _4 = _16 + _2;
>>> _15 = _4 + c_7(D);
>>> _17 = c_7(D) * 3;
>>> x_13 = _15 + _3;
>>> return x_13;
>>>
>>>
>>> The root cause of this the place in which we are adding (_17 = c_7(D)
>>> * 3). Finding the right place is not always straightforward as this
>>> case shows.
>>>
>>> We could try  Martin Liška's approach, We could also move _17 = c_7(D)
>>> * 3; at tree-ssa-reassoc.c:3897 satisfy the gcc_assert. We could do
>>> this based on the use count of _17.
>>>
>>>
>>> This patch does this. I have no preferences. Any thoughts ?
>>
>> I think the issue may be that you fail to set changed to true for the
>> degenerate case of ending up with a multiply only.
>>
>> Not sure because neither patch contains a testcase.
>>
>
> Sorry, I should have been specific. There is an existing test-case that
> is failing. Thats why I didn't include a test case.
>
> FAIL: gcc.dg/tree-ssa/slsr-30.c (internal compiler error)

Btw, it also looks like ops are not sorted after rank:

(gdb) p ops.m_vec->m_vecdata[0]
$4 = (operand_entry *) 0x27a82e0
(gdb) p ops.m_vec->m_vecdata[1]
$5 = (operand_entry *) 0x27a82a0
(gdb) p ops.m_vec->m_vecdata[2]
$6 = (operand_entry *) 0x27a8260
(gdb) p ops.m_vec->m_vecdata[3]
$7 = (operand_entry *) 0x27a8300
(gdb) p *$4
$8 = {rank = 7, id = 5, op = <ssa_name 0x7ffff6890990>, count = 1}
(gdb) p *$5
$9 = {rank = 5, id = 3, op = <ssa_name 0x7ffff6890e58>, count = 1}
(gdb) p *$6
$10 = {rank = 7, id = 1, op = <ssa_name 0x7ffff6890900>, count = 1}
(gdb) p *$7
$11 = {rank = 7, id = 6, op = <ssa_name 0x7ffff6890948>, count = 1}

Richard.

>
> Thanks,
> Kugan

Re: [PATCH] Fix PR tree-optimization/71170

[Kugan Vivekanandarajah]

[-- Attachment #1: Type: text/plain, Size: 3301 bytes --]

On 19 May 2016 at 18:55, Richard Biener <richard.guenther@gmail.com> wrote:
> On Thu, May 19, 2016 at 10:26 AM, Kugan
> <kugan.vivekanandarajah@linaro.org> wrote:
>> Hi,
>>
>>
>> On 19/05/16 18:21, Richard Biener wrote:
>>> On Thu, May 19, 2016 at 10:12 AM, Kugan Vivekanandarajah
>>> <kugan.vivekanandarajah@linaro.org> wrote:
>>>> Hi Martin,
>>>>
>>>> Thanks for the fix. Just to elaborate (as mentioned in PR)
>>>>
>>>> At tree-ssa-reassoc.c:3897, we have:
>>>>
>>>> stmt:
>>>> _15 = _4 + c_7(D);
>>>>
>>>> oe->op def_stmt:
>>>> _17 = c_7(D) * 3;
>>>>
>>>>
>>>> <bb 2>:
>>>> a1_6 = s_5(D) * 2;
>>>> _1 = (long int) a1_6;
>>>> x1_8 = _1 + c_7(D);
>>>> a2_9 = s_5(D) * 4;
>>>> _2 = (long int) a2_9;
>>>> a3_11 = s_5(D) * 6;
>>>> _3 = (long int) a3_11;
>>>> _16 = x1_8 + c_7(D);
>>>> _18 = _1 + _2;
>>>> _4 = _16 + _2;
>>>> _15 = _4 + c_7(D);
>>>> _17 = c_7(D) * 3;
>>>> x_13 = _15 + _3;
>>>> return x_13;
>>>>
>>>>
>>>> The root cause of this the place in which we are adding (_17 = c_7(D)
>>>> * 3). Finding the right place is not always straightforward as this
>>>> case shows.
>>>>
>>>> We could try  Martin Liška's approach, We could also move _17 = c_7(D)
>>>> * 3; at tree-ssa-reassoc.c:3897 satisfy the gcc_assert. We could do
>>>> this based on the use count of _17.
>>>>
>>>>
>>>> This patch does this. I have no preferences. Any thoughts ?
>>>
>>> I think the issue may be that you fail to set changed to true for the
>>> degenerate case of ending up with a multiply only.
>>>
>>> Not sure because neither patch contains a testcase.
>>>
>>
>> Sorry, I should have been specific. There is an existing test-case that
>> is failing. Thats why I didn't include a test case.
>>
>> FAIL: gcc.dg/tree-ssa/slsr-30.c (internal compiler error)
>
> Btw, it also looks like ops are not sorted after rank:
>
> (gdb) p ops.m_vec->m_vecdata[0]
> $4 = (operand_entry *) 0x27a82e0
> (gdb) p ops.m_vec->m_vecdata[1]
> $5 = (operand_entry *) 0x27a82a0
> (gdb) p ops.m_vec->m_vecdata[2]
> $6 = (operand_entry *) 0x27a8260
> (gdb) p ops.m_vec->m_vecdata[3]
> $7 = (operand_entry *) 0x27a8300
> (gdb) p *$4
> $8 = {rank = 7, id = 5, op = <ssa_name 0x7ffff6890990>, count = 1}
> (gdb) p *$5
> $9 = {rank = 5, id = 3, op = <ssa_name 0x7ffff6890e58>, count = 1}
> (gdb) p *$6
> $10 = {rank = 7, id = 1, op = <ssa_name 0x7ffff6890900>, count = 1}
> (gdb) p *$7
> $11 = {rank = 7, id = 6, op = <ssa_name 0x7ffff6890948>, count = 1}
>

Hi Richard,

It is sorted but in swap_ops_for_binary_stmt (ops, len - 3, stmt), it
is reordered for some form optimization. Commenting this is not
helping the ICE.

In the ops list, the operand defined by multiplication has to be the
last due to the way we add the multiplication stmt. We don’t have the
knowledge to find the optimal point without going through some
complicated logic.

Therefore, I think we either should reorder the stmt (like my previous
patch) Or change the rank of the operand produced by the multiply such
that it will always be the last. This looks like a reasonable think to
do. Please let me know what you think. I am attaching the patch (not
tested). I will do the proper test and report the results if you think
this approach is OK.


Thanks,
Kugan

[-- Attachment #2: p.txt --]
[-- Type: text/plain, Size: 972 bytes --]

diff --git a/gcc/tree-ssa-reassoc.c b/gcc/tree-ssa-reassoc.c
index 3b5f36b..52414d3 100644
--- a/gcc/tree-ssa-reassoc.c
+++ b/gcc/tree-ssa-reassoc.c
@@ -553,12 +553,12 @@ sort_by_operand_rank (const void *pa, const void *pb)
 /* Add an operand entry to *OPS for the tree operand OP.  */
 
 static void
-add_to_ops_vec (vec<operand_entry *> *ops, tree op)
+add_to_ops_vec (vec<operand_entry *> *ops, tree op, int rank = 0)
 {
   operand_entry *oe = operand_entry_pool.allocate ();
 
   oe->op = op;
-  oe->rank = get_rank (op);
+  oe->rank = rank ? rank : get_rank (op);
   oe->id = next_operand_entry_id++;
   oe->count = 1;
   ops->safe_push (oe);
@@ -1824,7 +1824,7 @@ transform_add_to_multiply (gimple *stmt, vec<operand_entry *> *ops)
       else
 	insert_stmt_after (mul_stmt, def_stmt);
       gimple_set_visited (mul_stmt, true);
-      add_to_ops_vec (ops, tmp);
+      add_to_ops_vec (ops, tmp, bb_rank [gimple_bb (stmt)->index]);
       changed = true;
     }
 

Re: [PATCH] Fix PR tree-optimization/71170

[Richard Biener]

On Thu, May 19, 2016 at 2:18 PM, Kugan Vivekanandarajah
<kugan.vivekanandarajah@linaro.org> wrote:
> On 19 May 2016 at 18:55, Richard Biener <richard.guenther@gmail.com> wrote:
>> On Thu, May 19, 2016 at 10:26 AM, Kugan
>> <kugan.vivekanandarajah@linaro.org> wrote:
>>> Hi,
>>>
>>>
>>> On 19/05/16 18:21, Richard Biener wrote:
>>>> On Thu, May 19, 2016 at 10:12 AM, Kugan Vivekanandarajah
>>>> <kugan.vivekanandarajah@linaro.org> wrote:
>>>>> Hi Martin,
>>>>>
>>>>> Thanks for the fix. Just to elaborate (as mentioned in PR)
>>>>>
>>>>> At tree-ssa-reassoc.c:3897, we have:
>>>>>
>>>>> stmt:
>>>>> _15 = _4 + c_7(D);
>>>>>
>>>>> oe->op def_stmt:
>>>>> _17 = c_7(D) * 3;
>>>>>
>>>>>
>>>>> <bb 2>:
>>>>> a1_6 = s_5(D) * 2;
>>>>> _1 = (long int) a1_6;
>>>>> x1_8 = _1 + c_7(D);
>>>>> a2_9 = s_5(D) * 4;
>>>>> _2 = (long int) a2_9;
>>>>> a3_11 = s_5(D) * 6;
>>>>> _3 = (long int) a3_11;
>>>>> _16 = x1_8 + c_7(D);
>>>>> _18 = _1 + _2;
>>>>> _4 = _16 + _2;
>>>>> _15 = _4 + c_7(D);
>>>>> _17 = c_7(D) * 3;
>>>>> x_13 = _15 + _3;
>>>>> return x_13;
>>>>>
>>>>>
>>>>> The root cause of this the place in which we are adding (_17 = c_7(D)
>>>>> * 3). Finding the right place is not always straightforward as this
>>>>> case shows.
>>>>>
>>>>> We could try  Martin Liška's approach, We could also move _17 = c_7(D)
>>>>> * 3; at tree-ssa-reassoc.c:3897 satisfy the gcc_assert. We could do
>>>>> this based on the use count of _17.
>>>>>
>>>>>
>>>>> This patch does this. I have no preferences. Any thoughts ?
>>>>
>>>> I think the issue may be that you fail to set changed to true for the
>>>> degenerate case of ending up with a multiply only.
>>>>
>>>> Not sure because neither patch contains a testcase.
>>>>
>>>
>>> Sorry, I should have been specific. There is an existing test-case that
>>> is failing. Thats why I didn't include a test case.
>>>
>>> FAIL: gcc.dg/tree-ssa/slsr-30.c (internal compiler error)
>>
>> Btw, it also looks like ops are not sorted after rank:
>>
>> (gdb) p ops.m_vec->m_vecdata[0]
>> $4 = (operand_entry *) 0x27a82e0
>> (gdb) p ops.m_vec->m_vecdata[1]
>> $5 = (operand_entry *) 0x27a82a0
>> (gdb) p ops.m_vec->m_vecdata[2]
>> $6 = (operand_entry *) 0x27a8260
>> (gdb) p ops.m_vec->m_vecdata[3]
>> $7 = (operand_entry *) 0x27a8300
>> (gdb) p *$4
>> $8 = {rank = 7, id = 5, op = <ssa_name 0x7ffff6890990>, count = 1}
>> (gdb) p *$5
>> $9 = {rank = 5, id = 3, op = <ssa_name 0x7ffff6890e58>, count = 1}
>> (gdb) p *$6
>> $10 = {rank = 7, id = 1, op = <ssa_name 0x7ffff6890900>, count = 1}
>> (gdb) p *$7
>> $11 = {rank = 7, id = 6, op = <ssa_name 0x7ffff6890948>, count = 1}
>>
>
> Hi Richard,
>
> It is sorted but in swap_ops_for_binary_stmt (ops, len - 3, stmt), it
> is reordered for some form optimization. Commenting this is not
> helping the ICE.
>
> In the ops list, the operand defined by multiplication has to be the
> last due to the way we add the multiplication stmt. We don’t have the
> knowledge to find the optimal point without going through some
> complicated logic.

I think it should have the same rank as op or op + 1 which is the current
behavior.  Sth else doesn't work correctly here I think, like inserting the
multiplication not near the definition of op.

Well, the whole "clever insertion" logic is simply flawed.

I'd say that ideally we would delay inserting the multiplication to
rewrite_expr_tree time.  For example by adding a ops->stmt_to_insert
member.

Richard.

> Therefore, I think we either should reorder the stmt (like my previous
> patch) Or change the rank of the operand produced by the multiply such
> that it will always be the last. This looks like a reasonable think to
> do. Please let me know what you think. I am attaching the patch (not
> tested). I will do the proper test and report the results if you think
> this approach is OK.
>
>
> Thanks,
> Kugan

Re: [PATCH] Fix PR tree-optimization/71170

[Kugan Vivekanandarajah]

[-- Attachment #1: Type: text/plain, Size: 1356 bytes --]

Hi Richard,

> I think it should have the same rank as op or op + 1 which is the current
> behavior.  Sth else doesn't work correctly here I think, like inserting the
> multiplication not near the definition of op.
>
> Well, the whole "clever insertion" logic is simply flawed.

What I meant to say was that the simple logic we have now wouldn’t
work. "clever logic" is knowing where exactly where it is needed and
inserting there.  I think thats what  you are suggesting below in a
simple to implement way.

> I'd say that ideally we would delay inserting the multiplication to
> rewrite_expr_tree time.  For example by adding a ops->stmt_to_insert
> member.
>

Here is an implementation based on above. Bootstrap on x86-linux-gnu
is OK. regression testing is ongoing.

Thanks,
Kugan

gcc/ChangeLog:

2016-05-20  Kugan Vivekanandarajah  <kugan.vivekanandarajah@linaro.org>

    * tree-ssa-reassoc.c (struct operand_entry): Add field stmt_to_insert.
    (add_to_ops_vec): Add stmt_to_insert.
    (add_repeat_to_ops_vec): Init stmt_to_insert.
    (transform_add_to_multiply): Remove mult_stmt insertion and add it
to ops vector.
    (get_ops): Init stmt_to_insert.
    (maybe_optimize_range_tests): Likewise.
    (rewrite_expr_tree): Insert  stmt_to_insert before use stmt.
    (rewrite_expr_tree_parallel): Likewise.

[-- Attachment #2: p.txt --]
[-- Type: text/plain, Size: 5719 bytes --]

diff --git a/gcc/tree-ssa-reassoc.c b/gcc/tree-ssa-reassoc.c
index 3b5f36b..69441ce 100644
--- a/gcc/tree-ssa-reassoc.c
+++ b/gcc/tree-ssa-reassoc.c
@@ -195,6 +195,7 @@ struct operand_entry
   int id;
   tree op;
   unsigned int count;
+  gimple *stmt_to_insert;
 };
 
 static object_allocator<operand_entry> operand_entry_pool
@@ -553,7 +554,7 @@ sort_by_operand_rank (const void *pa, const void *pb)
 /* Add an operand entry to *OPS for the tree operand OP.  */
 
 static void
-add_to_ops_vec (vec<operand_entry *> *ops, tree op)
+add_to_ops_vec (vec<operand_entry *> *ops, tree op, gimple *stmt_to_insert = NULL)
 {
   operand_entry *oe = operand_entry_pool.allocate ();
 
@@ -561,6 +562,7 @@ add_to_ops_vec (vec<operand_entry *> *ops, tree op)
   oe->rank = get_rank (op);
   oe->id = next_operand_entry_id++;
   oe->count = 1;
+  oe->stmt_to_insert = stmt_to_insert;
   ops->safe_push (oe);
 }
 
@@ -577,6 +579,7 @@ add_repeat_to_ops_vec (vec<operand_entry *> *ops, tree op,
   oe->rank = get_rank (op);
   oe->id = next_operand_entry_id++;
   oe->count = repeat;
+  oe->stmt_to_insert = NULL;
   ops->safe_push (oe);
 
   reassociate_stats.pows_encountered++;
@@ -1810,21 +1813,12 @@ transform_add_to_multiply (gimple *stmt, vec<operand_entry *> *ops)
 	ops->unordered_remove (i);
       tree tmp = make_ssa_name (TREE_TYPE (op));
       tree cst = build_int_cst (integer_type_node, count);
-      gimple *def_stmt = SSA_NAME_DEF_STMT (op);
       gassign *mul_stmt
 	= gimple_build_assign (tmp, MULT_EXPR,
 			       op, fold_convert (TREE_TYPE (op), cst));
-      if (gimple_code (def_stmt) == GIMPLE_NOP
-	  || gimple_bb (stmt) != gimple_bb (def_stmt))
-	{
-	  gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
-	  gimple_set_uid (mul_stmt, gimple_uid (stmt));
-	  gsi_insert_before (&gsi, mul_stmt, GSI_NEW_STMT);
-	}
-      else
-	insert_stmt_after (mul_stmt, def_stmt);
+      gimple_set_uid (mul_stmt, gimple_uid (stmt));
       gimple_set_visited (mul_stmt, true);
-      add_to_ops_vec (ops, tmp);
+      add_to_ops_vec (ops, tmp, mul_stmt);
       changed = true;
     }
 
@@ -3224,6 +3218,7 @@ get_ops (tree var, enum tree_code code, vec<operand_entry *> *ops,
 	oe->rank = code;
 	oe->id = 0;
 	oe->count = 1;
+	oe->stmt_to_insert = NULL;
 	ops->safe_push (oe);
       }
   return true;
@@ -3464,6 +3459,7 @@ maybe_optimize_range_tests (gimple *stmt)
 	      oe->rank = code;
 	      oe->id = 0;
 	      oe->count = 1;
+	      oe->stmt_to_insert = NULL;
 	      ops.safe_push (oe);
 	      bb_ent.last_idx++;
 	    }
@@ -3501,6 +3497,7 @@ maybe_optimize_range_tests (gimple *stmt)
 	     is.  */
 	  oe->id = bb->index;
 	  oe->count = 1;
+	  oe->stmt_to_insert = NULL;
 	  ops.safe_push (oe);
 	  bb_ent.op = NULL;
 	  bb_ent.last_idx++;
@@ -3798,6 +3795,19 @@ rewrite_expr_tree (gimple *stmt, unsigned int opindex,
       oe1 = ops[opindex];
       oe2 = ops[opindex + 1];
 
+      /* If the stmt that defines operand has to be inserted, insert it
+	 before the use.  */
+      if (oe1->stmt_to_insert)
+	{
+	  gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
+	  gsi_insert_before (&gsi, oe1->stmt_to_insert, GSI_NEW_STMT);
+	}
+      if (oe2->stmt_to_insert)
+	{
+	  gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
+	  gsi_insert_before (&gsi, oe2->stmt_to_insert, GSI_NEW_STMT);
+	}
+
       if (rhs1 != oe1->op || rhs2 != oe2->op)
 	{
 	  gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
@@ -3855,6 +3865,14 @@ rewrite_expr_tree (gimple *stmt, unsigned int opindex,
   /* Rewrite the next operator.  */
   oe = ops[opindex];
 
+  /* If the stmt that defines operand has to be inserted, insert it
+     before the use.  */
+  if (oe->stmt_to_insert)
+    {
+      gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
+      gsi_insert_before (&gsi, oe->stmt_to_insert, GSI_NEW_STMT);
+    }
+
   /* Recurse on the LHS of the binary operator, which is guaranteed to
      be the non-leaf side.  */
   tree new_rhs1
@@ -3999,6 +4017,7 @@ rewrite_expr_tree_parallel (gassign *stmt, int width,
   int stmt_index = 0;
   int ready_stmts_end = 0;
   int i = 0;
+  gimple *stmt1 = NULL, *stmt2 = NULL;
   tree last_rhs1 = gimple_assign_rhs1 (stmt);
 
   /* We start expression rewriting from the top statements.
@@ -4027,7 +4046,11 @@ rewrite_expr_tree_parallel (gassign *stmt, int width,
 	  if (ready_stmts_end > stmt_index)
 	    op2 = gimple_assign_lhs (stmts[stmt_index++]);
 	  else if (op_index >= 0)
-	    op2 = ops[op_index--]->op;
+	    {
+	      operand_entry *oe = ops[op_index--];
+	      stmt2 = oe->stmt_to_insert;
+	      op2 = oe->op;
+	    }
 	  else
 	    {
 	      gcc_assert (stmt_index < i);
@@ -4041,8 +4064,12 @@ rewrite_expr_tree_parallel (gassign *stmt, int width,
 	{
 	  if (op_index > 1)
 	    swap_ops_for_binary_stmt (ops, op_index - 2, NULL);
-	  op2 = ops[op_index--]->op;
-	  op1 = ops[op_index--]->op;
+	  operand_entry *oe2 = ops[op_index--];
+	  operand_entry *oe1 = ops[op_index--];
+	  op2 = oe2->op;
+	  stmt2 = oe2->stmt_to_insert;
+	  op1 = oe1->op;
+	  stmt1 = oe1->stmt_to_insert;
 	}
 
       /* If we emit the last statement then we should put
@@ -4057,6 +4084,19 @@ rewrite_expr_tree_parallel (gassign *stmt, int width,
 	  print_gimple_stmt (dump_file, stmts[i], 0, 0);
 	}
 
+      /* If the stmt that defines operand has to be inserted, insert it
+	 before the use.  */
+      if (stmt1)
+	{
+	  gimple_stmt_iterator gsi = gsi_for_stmt (stmts[i]);
+	  gsi_insert_before (&gsi, stmt1, GSI_NEW_STMT);
+	}
+      if (stmt2)
+	{
+	  gimple_stmt_iterator gsi = gsi_for_stmt (stmts[i]);
+	  gsi_insert_before (&gsi, stmt2, GSI_NEW_STMT);
+	}
+
       /* We keep original statement only for the last one.  All
 	 others are recreated.  */
       if (i == stmt_num - 1)

Re: [PATCH] Fix PR tree-optimization/71170

[Richard Biener]

On Fri, May 20, 2016 at 1:51 AM, Kugan Vivekanandarajah
<kugan.vivekanandarajah@linaro.org> wrote:
> Hi Richard,
>
>> I think it should have the same rank as op or op + 1 which is the current
>> behavior.  Sth else doesn't work correctly here I think, like inserting the
>> multiplication not near the definition of op.
>>
>> Well, the whole "clever insertion" logic is simply flawed.
>
> What I meant to say was that the simple logic we have now wouldn’t
> work. "clever logic" is knowing where exactly where it is needed and
> inserting there.  I think thats what  you are suggesting below in a
> simple to implement way.
>
>> I'd say that ideally we would delay inserting the multiplication to
>> rewrite_expr_tree time.  For example by adding a ops->stmt_to_insert
>> member.
>>
>
> Here is an implementation based on above. Bootstrap on x86-linux-gnu
> is OK. regression testing is ongoing.

I like it.  Please push the insertion code to a helper as I think you need
to post-pone setting the stmts UID to that point.

Ideally we'd make use of the same machinery in attempt_builtin_powi,
removing the special-casing of powi_result.  (same as I said that ideally
the plus->mult stuff would use the repeat-ops machinery...)

I'm not 100% convinced the place you insert the stmt is correct but I
haven't spent too much time to decipher reassoc in this area.

Thanks,
Richard.

> Thanks,
> Kugan
>
> gcc/ChangeLog:
>
> 2016-05-20  Kugan Vivekanandarajah  <kugan.vivekanandarajah@linaro.org>
>
>     * tree-ssa-reassoc.c (struct operand_entry): Add field stmt_to_insert.
>     (add_to_ops_vec): Add stmt_to_insert.
>     (add_repeat_to_ops_vec): Init stmt_to_insert.
>     (transform_add_to_multiply): Remove mult_stmt insertion and add it
> to ops vector.
>     (get_ops): Init stmt_to_insert.
>     (maybe_optimize_range_tests): Likewise.
>     (rewrite_expr_tree): Insert  stmt_to_insert before use stmt.
>     (rewrite_expr_tree_parallel): Likewise.

Re: [PATCH] Fix PR tree-optimization/71170

[Kugan Vivekanandarajah]

[-- Attachment #1: Type: text/plain, Size: 2425 bytes --]

On 20 May 2016 at 21:07, Richard Biener <richard.guenther@gmail.com> wrote:
> On Fri, May 20, 2016 at 1:51 AM, Kugan Vivekanandarajah
> <kugan.vivekanandarajah@linaro.org> wrote:
>> Hi Richard,
>>
>>> I think it should have the same rank as op or op + 1 which is the current
>>> behavior.  Sth else doesn't work correctly here I think, like inserting the
>>> multiplication not near the definition of op.
>>>
>>> Well, the whole "clever insertion" logic is simply flawed.
>>
>> What I meant to say was that the simple logic we have now wouldn’t
>> work. "clever logic" is knowing where exactly where it is needed and
>> inserting there.  I think thats what  you are suggesting below in a
>> simple to implement way.
>>
>>> I'd say that ideally we would delay inserting the multiplication to
>>> rewrite_expr_tree time.  For example by adding a ops->stmt_to_insert
>>> member.
>>>
>>
>> Here is an implementation based on above. Bootstrap on x86-linux-gnu
>> is OK. regression testing is ongoing.
>
> I like it.  Please push the insertion code to a helper as I think you need
> to post-pone setting the stmts UID to that point.
>
> Ideally we'd make use of the same machinery in attempt_builtin_powi,
> removing the special-casing of powi_result.  (same as I said that ideally
> the plus->mult stuff would use the repeat-ops machinery...)
>
> I'm not 100% convinced the place you insert the stmt is correct but I
> haven't spent too much time to decipher reassoc in this area.


Hi Richard,

Thanks. Here is a tested version of the patch. I did miss one place
which I fixed now (tranform_stmt_to_copy) I also created a function to
do the insertion.


Bootstrap and regression testing on x86_64-linux-gnu are fine. Is this
OK for trunk.

Thanks,
Kugan


gcc/ChangeLog:

2016-05-21  Kugan Vivekanandarajah  <kuganv@linaro.org>

    PR middle-end/71170
    * tree-ssa-reassoc.c (struct operand_entry): Add field stmt_to_insert.
    (add_to_ops_vec): Add stmt_to_insert.
    (add_repeat_to_ops_vec): Init stmt_to_insert.
    (insert_stmt_before_use): New.
    (transform_add_to_multiply): Remove mult_stmt insertion and add it
to ops vector.
    (get_ops): Init stmt_to_insert.
    (maybe_optimize_range_tests): Likewise.
    (rewrite_expr_tree): Insert  stmt_to_insert before use stmt.
    (rewrite_expr_tree_parallel): Likewise.
    (reassociate_bb): Likewise.

[-- Attachment #2: p.txt --]
[-- Type: text/plain, Size: 7615 bytes --]

diff --git a/gcc/tree-ssa-reassoc.c b/gcc/tree-ssa-reassoc.c
index 3b5f36b..0b905e9 100644
--- a/gcc/tree-ssa-reassoc.c
+++ b/gcc/tree-ssa-reassoc.c
@@ -195,6 +195,7 @@ struct operand_entry
   int id;
   tree op;
   unsigned int count;
+  gimple *stmt_to_insert;
 };
 
 static object_allocator<operand_entry> operand_entry_pool
@@ -553,7 +554,7 @@ sort_by_operand_rank (const void *pa, const void *pb)
 /* Add an operand entry to *OPS for the tree operand OP.  */
 
 static void
-add_to_ops_vec (vec<operand_entry *> *ops, tree op)
+add_to_ops_vec (vec<operand_entry *> *ops, tree op, gimple *stmt_to_insert = NULL)
 {
   operand_entry *oe = operand_entry_pool.allocate ();
 
@@ -561,6 +562,7 @@ add_to_ops_vec (vec<operand_entry *> *ops, tree op)
   oe->rank = get_rank (op);
   oe->id = next_operand_entry_id++;
   oe->count = 1;
+  oe->stmt_to_insert = stmt_to_insert;
   ops->safe_push (oe);
 }
 
@@ -577,6 +579,7 @@ add_repeat_to_ops_vec (vec<operand_entry *> *ops, tree op,
   oe->rank = get_rank (op);
   oe->id = next_operand_entry_id++;
   oe->count = repeat;
+  oe->stmt_to_insert = NULL;
   ops->safe_push (oe);
 
   reassociate_stats.pows_encountered++;
@@ -1756,10 +1759,21 @@ eliminate_redundant_comparison (enum tree_code opcode,
   return false;
 }
 
+/* If the stmt that defines operand has to be inserted, insert it
+   before the use.  */
+static void
+insert_stmt_before_use (gimple *stmt, gimple *stmt_to_insert)
+{
+  gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
+  gimple_set_uid (stmt_to_insert, gimple_uid (stmt));
+  gsi_insert_before (&gsi, stmt_to_insert, GSI_NEW_STMT);
+}
+
+
 /* Transform repeated addition of same values into multiply with
    constant.  */
 static bool
-transform_add_to_multiply (gimple *stmt, vec<operand_entry *> *ops)
+transform_add_to_multiply (vec<operand_entry *> *ops)
 {
   operand_entry *oe;
   tree op = NULL_TREE;
@@ -1810,21 +1824,11 @@ transform_add_to_multiply (gimple *stmt, vec<operand_entry *> *ops)
 	ops->unordered_remove (i);
       tree tmp = make_ssa_name (TREE_TYPE (op));
       tree cst = build_int_cst (integer_type_node, count);
-      gimple *def_stmt = SSA_NAME_DEF_STMT (op);
       gassign *mul_stmt
 	= gimple_build_assign (tmp, MULT_EXPR,
 			       op, fold_convert (TREE_TYPE (op), cst));
-      if (gimple_code (def_stmt) == GIMPLE_NOP
-	  || gimple_bb (stmt) != gimple_bb (def_stmt))
-	{
-	  gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
-	  gimple_set_uid (mul_stmt, gimple_uid (stmt));
-	  gsi_insert_before (&gsi, mul_stmt, GSI_NEW_STMT);
-	}
-      else
-	insert_stmt_after (mul_stmt, def_stmt);
       gimple_set_visited (mul_stmt, true);
-      add_to_ops_vec (ops, tmp);
+      add_to_ops_vec (ops, tmp, mul_stmt);
       changed = true;
     }
 
@@ -3224,6 +3228,7 @@ get_ops (tree var, enum tree_code code, vec<operand_entry *> *ops,
 	oe->rank = code;
 	oe->id = 0;
 	oe->count = 1;
+	oe->stmt_to_insert = NULL;
 	ops->safe_push (oe);
       }
   return true;
@@ -3464,6 +3469,7 @@ maybe_optimize_range_tests (gimple *stmt)
 	      oe->rank = code;
 	      oe->id = 0;
 	      oe->count = 1;
+	      oe->stmt_to_insert = NULL;
 	      ops.safe_push (oe);
 	      bb_ent.last_idx++;
 	    }
@@ -3501,6 +3507,7 @@ maybe_optimize_range_tests (gimple *stmt)
 	     is.  */
 	  oe->id = bb->index;
 	  oe->count = 1;
+	  oe->stmt_to_insert = NULL;
 	  ops.safe_push (oe);
 	  bb_ent.op = NULL;
 	  bb_ent.last_idx++;
@@ -3798,6 +3805,7 @@ rewrite_expr_tree (gimple *stmt, unsigned int opindex,
       oe1 = ops[opindex];
       oe2 = ops[opindex + 1];
 
+
       if (rhs1 != oe1->op || rhs2 != oe2->op)
 	{
 	  gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
@@ -3817,6 +3825,12 @@ rewrite_expr_tree (gimple *stmt, unsigned int opindex,
 	    {
 	      gimple *insert_point
 		= find_insert_point (stmt, oe1->op, oe2->op);
+	      /* If the stmt that defines operand has to be inserted, insert it
+		 before the use.  */
+	      if (oe1->stmt_to_insert)
+		insert_stmt_before_use (stmt, oe1->stmt_to_insert);
+	      if (oe2->stmt_to_insert)
+		insert_stmt_before_use (stmt, oe2->stmt_to_insert);
 	      lhs = make_ssa_name (TREE_TYPE (lhs));
 	      stmt
 		= gimple_build_assign (lhs, gimple_assign_rhs_code (stmt),
@@ -3832,6 +3846,12 @@ rewrite_expr_tree (gimple *stmt, unsigned int opindex,
 	    {
 	      gcc_checking_assert (find_insert_point (stmt, oe1->op, oe2->op)
 				   == stmt);
+	      /* If the stmt that defines operand has to be inserted, insert it
+		 before the use.  */
+	      if (oe1->stmt_to_insert)
+		insert_stmt_before_use (stmt, oe1->stmt_to_insert);
+	      if (oe2->stmt_to_insert)
+		insert_stmt_before_use (stmt, oe2->stmt_to_insert);
 	      gimple_assign_set_rhs1 (stmt, oe1->op);
 	      gimple_assign_set_rhs2 (stmt, oe2->op);
 	      update_stmt (stmt);
@@ -3855,6 +3875,11 @@ rewrite_expr_tree (gimple *stmt, unsigned int opindex,
   /* Rewrite the next operator.  */
   oe = ops[opindex];
 
+  /* If the stmt that defines operand has to be inserted, insert it
+     before the use.  */
+  if (oe->stmt_to_insert)
+    insert_stmt_before_use (stmt, oe->stmt_to_insert);
+
   /* Recurse on the LHS of the binary operator, which is guaranteed to
      be the non-leaf side.  */
   tree new_rhs1
@@ -3999,6 +4024,7 @@ rewrite_expr_tree_parallel (gassign *stmt, int width,
   int stmt_index = 0;
   int ready_stmts_end = 0;
   int i = 0;
+  gimple *stmt1 = NULL, *stmt2 = NULL;
   tree last_rhs1 = gimple_assign_rhs1 (stmt);
 
   /* We start expression rewriting from the top statements.
@@ -4027,7 +4053,11 @@ rewrite_expr_tree_parallel (gassign *stmt, int width,
 	  if (ready_stmts_end > stmt_index)
 	    op2 = gimple_assign_lhs (stmts[stmt_index++]);
 	  else if (op_index >= 0)
-	    op2 = ops[op_index--]->op;
+	    {
+	      operand_entry *oe = ops[op_index--];
+	      stmt2 = oe->stmt_to_insert;
+	      op2 = oe->op;
+	    }
 	  else
 	    {
 	      gcc_assert (stmt_index < i);
@@ -4041,8 +4071,12 @@ rewrite_expr_tree_parallel (gassign *stmt, int width,
 	{
 	  if (op_index > 1)
 	    swap_ops_for_binary_stmt (ops, op_index - 2, NULL);
-	  op2 = ops[op_index--]->op;
-	  op1 = ops[op_index--]->op;
+	  operand_entry *oe2 = ops[op_index--];
+	  operand_entry *oe1 = ops[op_index--];
+	  op2 = oe2->op;
+	  stmt2 = oe2->stmt_to_insert;
+	  op1 = oe1->op;
+	  stmt1 = oe1->stmt_to_insert;
 	}
 
       /* If we emit the last statement then we should put
@@ -4057,6 +4091,13 @@ rewrite_expr_tree_parallel (gassign *stmt, int width,
 	  print_gimple_stmt (dump_file, stmts[i], 0, 0);
 	}
 
+      /* If the stmt that defines operand has to be inserted, insert it
+	 before the use.  */
+      if (stmt1)
+	insert_stmt_before_use (stmts[i], stmt1);
+      if (stmt2)
+	insert_stmt_before_use (stmts[i], stmt2);
+
       /* We keep original statement only for the last one.  All
 	 others are recreated.  */
       if (i == stmt_num - 1)
@@ -5187,7 +5228,7 @@ reassociate_bb (basic_block bb)
 		}
 
 	      if (rhs_code == PLUS_EXPR
-		  && transform_add_to_multiply (stmt, &ops))
+		  && transform_add_to_multiply (&ops))
 		ops.qsort (sort_by_operand_rank);
 
 	      if (rhs_code == BIT_IOR_EXPR || rhs_code == BIT_AND_EXPR)
@@ -5214,7 +5255,11 @@ reassociate_bb (basic_block bb)
 	      else if (ops.length () == 1)
 		{
 		  tree last_op = ops.last ()->op;
-		  
+
+		  /* If the stmt that defines operand has to be inserted, insert it
+		     before the use.  */
+		  if (ops.last ()->stmt_to_insert)
+		    insert_stmt_before_use (stmt, ops.last ()->stmt_to_insert);
 		  if (powi_result)
 		    transform_stmt_to_multiply (&gsi, stmt, last_op,
 						powi_result);

Re: [PATCH] Fix PR tree-optimization/71170

[Richard Biener]

On Sat, May 21, 2016 at 8:08 AM, Kugan Vivekanandarajah
<kugan.vivekanandarajah@linaro.org> wrote:
> On 20 May 2016 at 21:07, Richard Biener <richard.guenther@gmail.com> wrote:
>> On Fri, May 20, 2016 at 1:51 AM, Kugan Vivekanandarajah
>> <kugan.vivekanandarajah@linaro.org> wrote:
>>> Hi Richard,
>>>
>>>> I think it should have the same rank as op or op + 1 which is the current
>>>> behavior.  Sth else doesn't work correctly here I think, like inserting the
>>>> multiplication not near the definition of op.
>>>>
>>>> Well, the whole "clever insertion" logic is simply flawed.
>>>
>>> What I meant to say was that the simple logic we have now wouldn’t
>>> work. "clever logic" is knowing where exactly where it is needed and
>>> inserting there.  I think thats what  you are suggesting below in a
>>> simple to implement way.
>>>
>>>> I'd say that ideally we would delay inserting the multiplication to
>>>> rewrite_expr_tree time.  For example by adding a ops->stmt_to_insert
>>>> member.
>>>>
>>>
>>> Here is an implementation based on above. Bootstrap on x86-linux-gnu
>>> is OK. regression testing is ongoing.
>>
>> I like it.  Please push the insertion code to a helper as I think you need
>> to post-pone setting the stmts UID to that point.
>>
>> Ideally we'd make use of the same machinery in attempt_builtin_powi,
>> removing the special-casing of powi_result.  (same as I said that ideally
>> the plus->mult stuff would use the repeat-ops machinery...)
>>
>> I'm not 100% convinced the place you insert the stmt is correct but I
>> haven't spent too much time to decipher reassoc in this area.
>
>
> Hi Richard,
>
> Thanks. Here is a tested version of the patch. I did miss one place
> which I fixed now (tranform_stmt_to_copy) I also created a function to
> do the insertion.
>
>
> Bootstrap and regression testing on x86_64-linux-gnu are fine. Is this
> OK for trunk.

@@ -3798,6 +3805,7 @@ rewrite_expr_tree (gimple *stmt, unsigned int opindex,
       oe1 = ops[opindex];
       oe2 = ops[opindex + 1];

+
       if (rhs1 != oe1->op || rhs2 != oe2->op)
        {
          gimple_stmt_iterator gsi = gsi_for_stmt (stmt);

please remove this stray change.

Ok with that change.

Thanks,
Richard.

> Thanks,
> Kugan
>
>
> gcc/ChangeLog:
>
> 2016-05-21  Kugan Vivekanandarajah  <kuganv@linaro.org>
>
>     PR middle-end/71170
>     * tree-ssa-reassoc.c (struct operand_entry): Add field stmt_to_insert.
>     (add_to_ops_vec): Add stmt_to_insert.
>     (add_repeat_to_ops_vec): Init stmt_to_insert.
>     (insert_stmt_before_use): New.
>     (transform_add_to_multiply): Remove mult_stmt insertion and add it
> to ops vector.
>     (get_ops): Init stmt_to_insert.
>     (maybe_optimize_range_tests): Likewise.
>     (rewrite_expr_tree): Insert  stmt_to_insert before use stmt.
>     (rewrite_expr_tree_parallel): Likewise.
>     (reassociate_bb): Likewise.

Re: [PATCH] Fix PR tree-optimization/71170

[Kugan Vivekanandarajah]

[-- Attachment #1: Type: text/plain, Size: 3102 bytes --]

On 23 May 2016 at 21:35, Richard Biener <richard.guenther@gmail.com> wrote:
> On Sat, May 21, 2016 at 8:08 AM, Kugan Vivekanandarajah
> <kugan.vivekanandarajah@linaro.org> wrote:
>> On 20 May 2016 at 21:07, Richard Biener <richard.guenther@gmail.com> wrote:
>>> On Fri, May 20, 2016 at 1:51 AM, Kugan Vivekanandarajah
>>> <kugan.vivekanandarajah@linaro.org> wrote:
>>>> Hi Richard,
>>>>
>>>>> I think it should have the same rank as op or op + 1 which is the current
>>>>> behavior.  Sth else doesn't work correctly here I think, like inserting the
>>>>> multiplication not near the definition of op.
>>>>>
>>>>> Well, the whole "clever insertion" logic is simply flawed.
>>>>
>>>> What I meant to say was that the simple logic we have now wouldn’t
>>>> work. "clever logic" is knowing where exactly where it is needed and
>>>> inserting there.  I think thats what  you are suggesting below in a
>>>> simple to implement way.
>>>>
>>>>> I'd say that ideally we would delay inserting the multiplication to
>>>>> rewrite_expr_tree time.  For example by adding a ops->stmt_to_insert
>>>>> member.
>>>>>
>>>>
>>>> Here is an implementation based on above. Bootstrap on x86-linux-gnu
>>>> is OK. regression testing is ongoing.
>>>
>>> I like it.  Please push the insertion code to a helper as I think you need
>>> to post-pone setting the stmts UID to that point.
>>>
>>> Ideally we'd make use of the same machinery in attempt_builtin_powi,
>>> removing the special-casing of powi_result.  (same as I said that ideally
>>> the plus->mult stuff would use the repeat-ops machinery...)
>>>
>>> I'm not 100% convinced the place you insert the stmt is correct but I
>>> haven't spent too much time to decipher reassoc in this area.
>>
>>
>> Hi Richard,
>>
>> Thanks. Here is a tested version of the patch. I did miss one place
>> which I fixed now (tranform_stmt_to_copy) I also created a function to
>> do the insertion.
>>
>>
>> Bootstrap and regression testing on x86_64-linux-gnu are fine. Is this
>> OK for trunk.
>
> @@ -3798,6 +3805,7 @@ rewrite_expr_tree (gimple *stmt, unsigned int opindex,
>        oe1 = ops[opindex];
>        oe2 = ops[opindex + 1];
>
> +
>        if (rhs1 != oe1->op || rhs2 != oe2->op)
>         {
>           gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
>
> please remove this stray change.
>
> Ok with that change.

Hi Richard,

Thanks for the review. I also found another issue with this patch.
I.e. for the stmt_to_insert we will get gimple_bb of NULL which is not
expected in sort_by_operand_rank. This only showed up only while
building a version of glibc.

Bootstrap and regression testing are ongoing.Is this OK for trunk if
passes regression and bootstrap.

Thanks,
Kugan


gcc/ChangeLog:

2016-05-24  Kugan Vivekanandarajah  <kuganv@linaro.org>

    * tree-ssa-reassoc.c (sort_by_operand_rank): Check for gimple_bb of NULL
    for stmt_to_insert.


gcc/testsuite/ChangeLog:

2016-05-24  Kugan Vivekanandarajah  <kuganv@linaro.org>

    * gcc.dg/tree-ssa/reassoc-44.c: New test.

[-- Attachment #2: p.txt --]
[-- Type: text/plain, Size: 893 bytes --]

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/reassoc-44.c b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-44.c
index e69de29..9b12212 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/reassoc-44.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-44.c
@@ -0,0 +1,10 @@
+
+/* { dg-do compile } */
+/* { dg-options "-O2" } */
+
+unsigned int a;
+int b, c;
+void fn1 ()
+{
+  b = a + c + c;
+}
diff --git a/gcc/tree-ssa-reassoc.c b/gcc/tree-ssa-reassoc.c
index fb683ad..06f4d1b 100644
--- a/gcc/tree-ssa-reassoc.c
+++ b/gcc/tree-ssa-reassoc.c
@@ -525,7 +525,7 @@ sort_by_operand_rank (const void *pa, const void *pb)
 	  gimple *stmtb = SSA_NAME_DEF_STMT (oeb->op);
 	  basic_block bba = gimple_bb (stmta);
 	  basic_block bbb = gimple_bb (stmtb);
-	  if (bbb != bba)
+	  if (bba && bbb && bbb != bba)
 	    {
 	      if (bb_rank[bbb->index] != bb_rank[bba->index])
 		return bb_rank[bbb->index] - bb_rank[bba->index];

Re: [PATCH] Fix PR tree-optimization/71170

[Christophe Lyon]

On 24 May 2016 at 05:13, Kugan Vivekanandarajah
<kugan.vivekanandarajah@linaro.org> wrote:
> On 23 May 2016 at 21:35, Richard Biener <richard.guenther@gmail.com> wrote:
>> On Sat, May 21, 2016 at 8:08 AM, Kugan Vivekanandarajah
>> <kugan.vivekanandarajah@linaro.org> wrote:
>>> On 20 May 2016 at 21:07, Richard Biener <richard.guenther@gmail.com> wrote:
>>>> On Fri, May 20, 2016 at 1:51 AM, Kugan Vivekanandarajah
>>>> <kugan.vivekanandarajah@linaro.org> wrote:
>>>>> Hi Richard,
>>>>>
>>>>>> I think it should have the same rank as op or op + 1 which is the current
>>>>>> behavior.  Sth else doesn't work correctly here I think, like inserting the
>>>>>> multiplication not near the definition of op.
>>>>>>
>>>>>> Well, the whole "clever insertion" logic is simply flawed.
>>>>>
>>>>> What I meant to say was that the simple logic we have now wouldn’t
>>>>> work. "clever logic" is knowing where exactly where it is needed and
>>>>> inserting there.  I think thats what  you are suggesting below in a
>>>>> simple to implement way.
>>>>>
>>>>>> I'd say that ideally we would delay inserting the multiplication to
>>>>>> rewrite_expr_tree time.  For example by adding a ops->stmt_to_insert
>>>>>> member.
>>>>>>
>>>>>
>>>>> Here is an implementation based on above. Bootstrap on x86-linux-gnu
>>>>> is OK. regression testing is ongoing.
>>>>
>>>> I like it.  Please push the insertion code to a helper as I think you need
>>>> to post-pone setting the stmts UID to that point.
>>>>
>>>> Ideally we'd make use of the same machinery in attempt_builtin_powi,
>>>> removing the special-casing of powi_result.  (same as I said that ideally
>>>> the plus->mult stuff would use the repeat-ops machinery...)
>>>>
>>>> I'm not 100% convinced the place you insert the stmt is correct but I
>>>> haven't spent too much time to decipher reassoc in this area.
>>>
>>>
>>> Hi Richard,
>>>
>>> Thanks. Here is a tested version of the patch. I did miss one place
>>> which I fixed now (tranform_stmt_to_copy) I also created a function to
>>> do the insertion.
>>>
>>>
>>> Bootstrap and regression testing on x86_64-linux-gnu are fine. Is this
>>> OK for trunk.
>>
>> @@ -3798,6 +3805,7 @@ rewrite_expr_tree (gimple *stmt, unsigned int opindex,
>>        oe1 = ops[opindex];
>>        oe2 = ops[opindex + 1];
>>
>> +
>>        if (rhs1 != oe1->op || rhs2 != oe2->op)
>>         {
>>           gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
>>
>> please remove this stray change.
>>
>> Ok with that change.
>
> Hi Richard,
>
> Thanks for the review. I also found another issue with this patch.
> I.e. for the stmt_to_insert we will get gimple_bb of NULL which is not
> expected in sort_by_operand_rank. This only showed up only while
> building a version of glibc.
>
> Bootstrap and regression testing are ongoing.Is this OK for trunk if
> passes regression and bootstrap.
>

I'm seeing build failures in glibc after you committed r236619.
This new patch is fixing it, right?


> Thanks,
> Kugan
>
>
> gcc/ChangeLog:
>
> 2016-05-24  Kugan Vivekanandarajah  <kuganv@linaro.org>
>
>     * tree-ssa-reassoc.c (sort_by_operand_rank): Check for gimple_bb of NULL
>     for stmt_to_insert.
>
>
> gcc/testsuite/ChangeLog:
>
> 2016-05-24  Kugan Vivekanandarajah  <kuganv@linaro.org>
>
>     * gcc.dg/tree-ssa/reassoc-44.c: New test.

Re: [PATCH] Fix PR tree-optimization/71170

[Kugan Vivekanandarajah]

[-- Attachment #1: Type: text/plain, Size: 3657 bytes --]

On 24 May 2016 at 18:36, Christophe Lyon <christophe.lyon@linaro.org> wrote:
> On 24 May 2016 at 05:13, Kugan Vivekanandarajah
> <kugan.vivekanandarajah@linaro.org> wrote:
>> On 23 May 2016 at 21:35, Richard Biener <richard.guenther@gmail.com> wrote:
>>> On Sat, May 21, 2016 at 8:08 AM, Kugan Vivekanandarajah
>>> <kugan.vivekanandarajah@linaro.org> wrote:
>>>> On 20 May 2016 at 21:07, Richard Biener <richard.guenther@gmail.com> wrote:
>>>>> On Fri, May 20, 2016 at 1:51 AM, Kugan Vivekanandarajah
>>>>> <kugan.vivekanandarajah@linaro.org> wrote:
>>>>>> Hi Richard,
>>>>>>
>>>>>>> I think it should have the same rank as op or op + 1 which is the current
>>>>>>> behavior.  Sth else doesn't work correctly here I think, like inserting the
>>>>>>> multiplication not near the definition of op.
>>>>>>>
>>>>>>> Well, the whole "clever insertion" logic is simply flawed.
>>>>>>
>>>>>> What I meant to say was that the simple logic we have now wouldn’t
>>>>>> work. "clever logic" is knowing where exactly where it is needed and
>>>>>> inserting there.  I think thats what  you are suggesting below in a
>>>>>> simple to implement way.
>>>>>>
>>>>>>> I'd say that ideally we would delay inserting the multiplication to
>>>>>>> rewrite_expr_tree time.  For example by adding a ops->stmt_to_insert
>>>>>>> member.
>>>>>>>
>>>>>>
>>>>>> Here is an implementation based on above. Bootstrap on x86-linux-gnu
>>>>>> is OK. regression testing is ongoing.
>>>>>
>>>>> I like it.  Please push the insertion code to a helper as I think you need
>>>>> to post-pone setting the stmts UID to that point.
>>>>>
>>>>> Ideally we'd make use of the same machinery in attempt_builtin_powi,
>>>>> removing the special-casing of powi_result.  (same as I said that ideally
>>>>> the plus->mult stuff would use the repeat-ops machinery...)
>>>>>
>>>>> I'm not 100% convinced the place you insert the stmt is correct but I
>>>>> haven't spent too much time to decipher reassoc in this area.
>>>>
>>>>
>>>> Hi Richard,
>>>>
>>>> Thanks. Here is a tested version of the patch. I did miss one place
>>>> which I fixed now (tranform_stmt_to_copy) I also created a function to
>>>> do the insertion.
>>>>
>>>>
>>>> Bootstrap and regression testing on x86_64-linux-gnu are fine. Is this
>>>> OK for trunk.
>>>
>>> @@ -3798,6 +3805,7 @@ rewrite_expr_tree (gimple *stmt, unsigned int opindex,
>>>        oe1 = ops[opindex];
>>>        oe2 = ops[opindex + 1];
>>>
>>> +
>>>        if (rhs1 != oe1->op || rhs2 != oe2->op)
>>>         {
>>>           gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
>>>
>>> please remove this stray change.
>>>
>>> Ok with that change.
>>
>> Hi Richard,
>>
>> Thanks for the review. I also found another issue with this patch.
>> I.e. for the stmt_to_insert we will get gimple_bb of NULL which is not
>> expected in sort_by_operand_rank. This only showed up only while
>> building a version of glibc.
>>
>> Bootstrap and regression testing are ongoing.Is this OK for trunk if
>> passes regression and bootstrap.
>>
>
> I'm seeing build failures in glibc after you committed r236619.
> This new patch is fixing it, right?


Yes (same patch attached). Also Bootstrap and regression testing on
x86_64-linux-gnu didn’t have no new failures.

Is this OK for trunk?

Thanks,
Kugan

gcc/ChangeLog:

2016-05-24  Kugan Vivekanandarajah  <kuganv@linaro.org>

    * tree-ssa-reassoc.c (sort_by_operand_rank): Check fgimple_bb for NULL.


gcc/testsuite/ChangeLog:

2016-05-24  Kugan Vivekanandarajah  <kuganv@linaro.org>

    * gcc.dg/tree-ssa/reassoc-44.c: New test.

[-- Attachment #2: p.txt --]
[-- Type: text/plain, Size: 893 bytes --]

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/reassoc-44.c b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-44.c
index e69de29..9b12212 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/reassoc-44.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-44.c
@@ -0,0 +1,10 @@
+
+/* { dg-do compile } */
+/* { dg-options "-O2" } */
+
+unsigned int a;
+int b, c;
+void fn1 ()
+{
+  b = a + c + c;
+}
diff --git a/gcc/tree-ssa-reassoc.c b/gcc/tree-ssa-reassoc.c
index fb683ad..06f4d1b 100644
--- a/gcc/tree-ssa-reassoc.c
+++ b/gcc/tree-ssa-reassoc.c
@@ -525,7 +525,7 @@ sort_by_operand_rank (const void *pa, const void *pb)
 	  gimple *stmtb = SSA_NAME_DEF_STMT (oeb->op);
 	  basic_block bba = gimple_bb (stmta);
 	  basic_block bbb = gimple_bb (stmtb);
-	  if (bbb != bba)
+	  if (bba && bbb && bbb != bba)
 	    {
 	      if (bb_rank[bbb->index] != bb_rank[bba->index])
 		return bb_rank[bbb->index] - bb_rank[bba->index];

Re: [PATCH] Fix PR tree-optimization/71170

[Richard Biener]

On Tue, May 24, 2016 at 5:13 AM, Kugan Vivekanandarajah
<kugan.vivekanandarajah@linaro.org> wrote:
> On 23 May 2016 at 21:35, Richard Biener <richard.guenther@gmail.com> wrote:
>> On Sat, May 21, 2016 at 8:08 AM, Kugan Vivekanandarajah
>> <kugan.vivekanandarajah@linaro.org> wrote:
>>> On 20 May 2016 at 21:07, Richard Biener <richard.guenther@gmail.com> wrote:
>>>> On Fri, May 20, 2016 at 1:51 AM, Kugan Vivekanandarajah
>>>> <kugan.vivekanandarajah@linaro.org> wrote:
>>>>> Hi Richard,
>>>>>
>>>>>> I think it should have the same rank as op or op + 1 which is the current
>>>>>> behavior.  Sth else doesn't work correctly here I think, like inserting the
>>>>>> multiplication not near the definition of op.
>>>>>>
>>>>>> Well, the whole "clever insertion" logic is simply flawed.
>>>>>
>>>>> What I meant to say was that the simple logic we have now wouldn’t
>>>>> work. "clever logic" is knowing where exactly where it is needed and
>>>>> inserting there.  I think thats what  you are suggesting below in a
>>>>> simple to implement way.
>>>>>
>>>>>> I'd say that ideally we would delay inserting the multiplication to
>>>>>> rewrite_expr_tree time.  For example by adding a ops->stmt_to_insert
>>>>>> member.
>>>>>>
>>>>>
>>>>> Here is an implementation based on above. Bootstrap on x86-linux-gnu
>>>>> is OK. regression testing is ongoing.
>>>>
>>>> I like it.  Please push the insertion code to a helper as I think you need
>>>> to post-pone setting the stmts UID to that point.
>>>>
>>>> Ideally we'd make use of the same machinery in attempt_builtin_powi,
>>>> removing the special-casing of powi_result.  (same as I said that ideally
>>>> the plus->mult stuff would use the repeat-ops machinery...)
>>>>
>>>> I'm not 100% convinced the place you insert the stmt is correct but I
>>>> haven't spent too much time to decipher reassoc in this area.
>>>
>>>
>>> Hi Richard,
>>>
>>> Thanks. Here is a tested version of the patch. I did miss one place
>>> which I fixed now (tranform_stmt_to_copy) I also created a function to
>>> do the insertion.
>>>
>>>
>>> Bootstrap and regression testing on x86_64-linux-gnu are fine. Is this
>>> OK for trunk.
>>
>> @@ -3798,6 +3805,7 @@ rewrite_expr_tree (gimple *stmt, unsigned int opindex,
>>        oe1 = ops[opindex];
>>        oe2 = ops[opindex + 1];
>>
>> +
>>        if (rhs1 != oe1->op || rhs2 != oe2->op)
>>         {
>>           gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
>>
>> please remove this stray change.
>>
>> Ok with that change.
>
> Hi Richard,
>
> Thanks for the review. I also found another issue with this patch.
> I.e. for the stmt_to_insert we will get gimple_bb of NULL which is not
> expected in sort_by_operand_rank. This only showed up only while
> building a version of glibc.
>
> Bootstrap and regression testing are ongoing.Is this OK for trunk if
> passes regression and bootstrap.

Hmm, I'd rather fall thru to the SSA_NAME_VERSION or id comparison here
than to stmt_dominates_stmt which is only well-defined for stmts in the same BB.

So sth like

Index: gcc/tree-ssa-reassoc.c
===================================================================
--- gcc/tree-ssa-reassoc.c      (revision 236630)
+++ gcc/tree-ssa-reassoc.c      (working copy)
@@ -519,6 +519,8 @@ sort_by_operand_rank (const void *pa, co
         See PR60418.  */
       if (!SSA_NAME_IS_DEFAULT_DEF (oea->op)
          && !SSA_NAME_IS_DEFAULT_DEF (oeb->op)
+         && !oea->stmt_to_insert
+         && !oeb->stmt_to_insert
          && SSA_NAME_VERSION (oeb->op) != SSA_NAME_VERSION (oea->op))
        {
          gimple *stmta = SSA_NAME_DEF_STMT (oea->op);

ok with that change.

Richard.

> Thanks,
> Kugan
>
>
> gcc/ChangeLog:
>
> 2016-05-24  Kugan Vivekanandarajah  <kuganv@linaro.org>
>
>     * tree-ssa-reassoc.c (sort_by_operand_rank): Check for gimple_bb of NULL
>     for stmt_to_insert.
>
>
> gcc/testsuite/ChangeLog:
>
> 2016-05-24  Kugan Vivekanandarajah  <kuganv@linaro.org>
>
>     * gcc.dg/tree-ssa/reassoc-44.c: New test.

Re: [PATCH] Fix PR tree-optimization/71170

[Jakub Jelinek]

On Tue, May 24, 2016 at 06:46:49PM +1000, Kugan Vivekanandarajah wrote:
> 2016-05-24  Kugan Vivekanandarajah  <kuganv@linaro.org>
> 
>     * tree-ssa-reassoc.c (sort_by_operand_rank): Check fgimple_bb for NULL.

s/fgimple/gimple/ ?

> --- a/gcc/testsuite/gcc.dg/tree-ssa/reassoc-44.c
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-44.c
> @@ -0,0 +1,10 @@
> +
> +/* { dg-do compile } */

Why the empty line above?  Either stick there a PR number if one is filed,
or leave it out.

> +/* { dg-options "-O2" } */
> +
> +unsigned int a;
> +int b, c;
> +void fn1 ()
> +{
> +  b = a + c + c;
> +}
> diff --git a/gcc/tree-ssa-reassoc.c b/gcc/tree-ssa-reassoc.c
> index fb683ad..06f4d1b 100644
> --- a/gcc/tree-ssa-reassoc.c
> +++ b/gcc/tree-ssa-reassoc.c
> @@ -525,7 +525,7 @@ sort_by_operand_rank (const void *pa, const void *pb)
>  	  gimple *stmtb = SSA_NAME_DEF_STMT (oeb->op);
>  	  basic_block bba = gimple_bb (stmta);
>  	  basic_block bbb = gimple_bb (stmtb);
> -	  if (bbb != bba)
> +	  if (bba && bbb && bbb != bba)
>  	    {
>  	      if (bb_rank[bbb->index] != bb_rank[bba->index])
>  		return bb_rank[bbb->index] - bb_rank[bba->index];

Can bb_rank be ever the same for bbb != bba?  If yes, perhaps it would be
better to fallthrough into the reassoc_stmt_dominates_stmt_p testing
code, if not, perhaps just assert that it is different and just
return the difference unconditionally?

	Jakub