A bug in vrp_meet?

A bug in vrp_meet?

[Qing Zhao]

Hi,

I have been debugging a runtime error caused by value range propagation. and finally located to the following gcc routine:

vrp_meet_1 in gcc/tree-vrp.c

====
/* Meet operation for value ranges.  Given two value ranges VR0 and
   VR1, store in VR0 a range that contains both VR0 and VR1.  This
   may not be the smallest possible such range.  */

static void 
vrp_meet_1 (value_range *vr0, const value_range *vr1)
{
  value_range saved;

  if (vr0->type == VR_UNDEFINED)
    {    
      set_value_range (vr0, vr1->type, vr1->min, vr1->max, vr1->equiv);
      return;
    }    

  if (vr1->type == VR_UNDEFINED)
    {    
      /* VR0 already has the resulting range.  */
      return;
    }    
====

In the above, when one of vr0 or vr1 is VR_UNDEFINED,  the meet result of these two will be  the other VALUE. 

This seems not correct to me. 

For example, the following is the located incorrect value range propagation:  (portion from the dump file *.181t.dom3)

====
Visiting PHI node: i_83 = PHI <_152(20), 0(22)>
    Argument #0 (20 -> 10 executable)
        _152: UNDEFINED
    Argument #1 (22 -> 10 executable)
        0: [0, 0]
Meeting
  UNDEFINED
and
  [0, 0]
to
  [0, 0]
Intersecting
  [0, 0]
and
  [0, 65535]
to
  [0, 0]
====


In the above, “i_83” is defined as PHI <_152(20), 0(22)>,   the 1st argument is UNDEFINED at this time(but its value range definitely is NOT [0,0]),
 and the 2nd argument is 0.

“vrp_meet” generate a VR_RANGE with [0,0] for “i_83” based on the current algorithm.  Obviously, this result VR_RANGE with [0,0] does NOT 
contain the value ranges for _152. 

 the result of “vrp_meet” is Not correct.  and this incorrect value range result finally caused the runtime error. 

I ‘d like to modify the vrp_meet_1 as following:

====
static void 
vrp_meet_1 (value_range *vr0, const value_range *vr1)
{
  value_range saved;

  if (vr0->type == VR_UNDEFINED)
    {    
      /* VR0 already has the resulting range. */
      return;
    }    

  if (vr1->type == VR_UNDEFINED)
    {    
      set_value_range_to_undefined (vr0)
     return;
    }    
====

let me know your opinion.

thanks a lot for the help.

Qing

Re: A bug in vrp_meet?

[Jeff Law]

On 2/28/19 10:05 AM, Qing Zhao wrote:
> Hi,
> 
> I have been debugging a runtime error caused by value range propagation. and finally located to the following gcc routine:
> 
> vrp_meet_1 in gcc/tree-vrp.c
> 
> ====
> /* Meet operation for value ranges.  Given two value ranges VR0 and
>    VR1, store in VR0 a range that contains both VR0 and VR1.  This
>    may not be the smallest possible such range.  */
> 
> static void 
> vrp_meet_1 (value_range *vr0, const value_range *vr1)
> {
>   value_range saved;
> 
>   if (vr0->type == VR_UNDEFINED)
>     {    
>       set_value_range (vr0, vr1->type, vr1->min, vr1->max, vr1->equiv);
>       return;
>     }    
> 
>   if (vr1->type == VR_UNDEFINED)
>     {    
>       /* VR0 already has the resulting range.  */
>       return;
>     }    
> ====
> 
> In the above, when one of vr0 or vr1 is VR_UNDEFINED,  the meet result of these two will be  the other VALUE. 
> 
> This seems not correct to me. 
That's the optimistic nature of VRP.  It's generally desired behavior.

> 
> For example, the following is the located incorrect value range propagation:  (portion from the dump file *.181t.dom3)
> 
> ====
> Visiting PHI node: i_83 = PHI <_152(20), 0(22)>
>     Argument #0 (20 -> 10 executable)
>         _152: UNDEFINED
>     Argument #1 (22 -> 10 executable)
>         0: [0, 0]
> Meeting
>   UNDEFINED
> and
>   [0, 0]
> to
>   [0, 0]
> Intersecting
>   [0, 0]
> and
>   [0, 65535]
> to
>   [0, 0]
> ====
> 
> 
> In the above, “i_83” is defined as PHI <_152(20), 0(22)>,   the 1st argument is UNDEFINED at this time(but its value range definitely is NOT [0,0]),
>  and the 2nd argument is 0.
If it's value is undefined then it can be any value we want.  We choose
to make it equal to the other argument.

If VRP later finds that _152 changes, then it will go back and
reevaluate the PHI.  That's one of the basic design principles of the
optimistic propagators.

> 
> “vrp_meet” generate a VR_RANGE with [0,0] for “i_83” based on the current algorithm.  Obviously, this result VR_RANGE with [0,0] does NOT 
> contain the value ranges for _152. 
> 
>  the result of “vrp_meet” is Not correct.  and this incorrect value range result finally caused the runtime error. 
> 
> I ‘d like to modify the vrp_meet_1 as following:
> 
> ====
> static void 
> vrp_meet_1 (value_range *vr0, const value_range *vr1)
> {
>   value_range saved;
> 
>   if (vr0->type == VR_UNDEFINED)
>     {    
>       /* VR0 already has the resulting range. */
>       return;
>     }    
> 
>   if (vr1->type == VR_UNDEFINED)
>     {    
>       set_value_range_to_undefined (vr0)
>      return;
>     }    
> ====
> 
> let me know your opinion.
> 
> thanks a lot for the help.
I think we (Richi and I) went through this about a year ago and the
conclusion was we should be looking at how you're getting into the
vrp_meet with the VR_UNDEFINED.

If it happens because the user's code has an undefined use, then, the
consensus has been to go ahead and optimize it.

If it happens for any other reason, then it's likely a bug in GCC.  We
had a couple of these when we made EVRP a re-usable module and started
exploiting its data in the jump threader.

So you need to work backwards from this point to figure out how you got
here.

jeff

Re: A bug in vrp_meet?

[Qing Zhao]

Jeff,

thanks a lot for the reply.

this is really helpful.

I double checked the dumped intermediate file for pass “dom3", and located the following for _152:

****BEFORE the pass “dom3”, there is no _152, the corresponding Block looks like:

  <bb 4> [local count: 12992277]:
  _98 = (int) ufcMSR_52(D);
  k_105 = (sword) ufcMSR_52(D);
  i_49 = _98 > 0 ? k_105 : 0;

***During the pass “doms”,  _152 is generated as following:

Optimizing block #4
….
Visiting statement:
i_49 = _98 > 0 ? k_105 : 0;
Meeting
  [0, 65535]
and
  [0, 0]
to
  [0, 65535]
Intersecting
  [0, 65535]
and
  [0, 65535]
to
  [0, 65535]
Optimizing statement i_49 = _98 > 0 ? k_105 : 0;
  Replaced 'k_105' with variable '_98'
gimple_simplified to _152 = MAX_EXPR <_98, 0>;
i_49 = _152;
  Folded to: i_49 = _152;
LKUP STMT i_49 = _152
==== ASGN i_49 = _152

then bb 4 becomes:

  <bb 4> [local count: 12992277]:
  _98 = (int) ufcMSR_52(D);
  k_105 = _98;
  _152 = MAX_EXPR <_98, 0>;
  i_49 = _152;

and all the i_49 are replaced with _152. 

However, the value range info for _152 doesnot reflect the one for i_49, it keeps as UNDEFINED. 

is this the root problem?  

thanks a lot.

Qing

> On Feb 28, 2019, at 1:54 PM, Jeff Law <law@redhat.com> wrote:
> 
> On 2/28/19 10:05 AM, Qing Zhao wrote:
>> Hi,
>> 
>> I have been debugging a runtime error caused by value range propagation. and finally located to the following gcc routine:
>> 
>> vrp_meet_1 in gcc/tree-vrp.c
>> 
>> ====
>> /* Meet operation for value ranges.  Given two value ranges VR0 and
>>   VR1, store in VR0 a range that contains both VR0 and VR1.  This
>>   may not be the smallest possible such range.  */
>> 
>> static void 
>> vrp_meet_1 (value_range *vr0, const value_range *vr1)
>> {
>>  value_range saved;
>> 
>>  if (vr0->type == VR_UNDEFINED)
>>    {    
>>      set_value_range (vr0, vr1->type, vr1->min, vr1->max, vr1->equiv);
>>      return;
>>    }    
>> 
>>  if (vr1->type == VR_UNDEFINED)
>>    {    
>>      /* VR0 already has the resulting range.  */
>>      return;
>>    }    
>> ====
>> 
>> In the above, when one of vr0 or vr1 is VR_UNDEFINED,  the meet result of these two will be  the other VALUE. 
>> 
>> This seems not correct to me. 
> That's the optimistic nature of VRP.  It's generally desired behavior.
> 
>> 
>> For example, the following is the located incorrect value range propagation:  (portion from the dump file *.181t.dom3)
>> 
>> ====
>> Visiting PHI node: i_83 = PHI <_152(20), 0(22)>
>>    Argument #0 (20 -> 10 executable)
>>        _152: UNDEFINED
>>    Argument #1 (22 -> 10 executable)
>>        0: [0, 0]
>> Meeting
>>  UNDEFINED
>> and
>>  [0, 0]
>> to
>>  [0, 0]
>> Intersecting
>>  [0, 0]
>> and
>>  [0, 65535]
>> to
>>  [0, 0]
>> ====
>> 
>> 
>> In the above, “i_83” is defined as PHI <_152(20), 0(22)>,   the 1st argument is UNDEFINED at this time(but its value range definitely is NOT [0,0]),
>> and the 2nd argument is 0.
> If it's value is undefined then it can be any value we want.  We choose
> to make it equal to the other argument.
> 
> If VRP later finds that _152 changes, then it will go back and
> reevaluate the PHI.  That's one of the basic design principles of the
> optimistic propagators.
> 
>> 
>> “vrp_meet” generate a VR_RANGE with [0,0] for “i_83” based on the current algorithm.  Obviously, this result VR_RANGE with [0,0] does NOT 
>> contain the value ranges for _152. 
>> 
>> the result of “vrp_meet” is Not correct.  and this incorrect value range result finally caused the runtime error. 
>> 
>> I ‘d like to modify the vrp_meet_1 as following:
>> 
>> ====
>> static void 
>> vrp_meet_1 (value_range *vr0, const value_range *vr1)
>> {
>>  value_range saved;
>> 
>>  if (vr0->type == VR_UNDEFINED)
>>    {    
>>      /* VR0 already has the resulting range. */
>>      return;
>>    }    
>> 
>>  if (vr1->type == VR_UNDEFINED)
>>    {    
>>      set_value_range_to_undefined (vr0)
>>     return;
>>    }    
>> ====
>> 
>> let me know your opinion.
>> 
>> thanks a lot for the help.
> I think we (Richi and I) went through this about a year ago and the
> conclusion was we should be looking at how you're getting into the
> vrp_meet with the VR_UNDEFINED.
> 
> If it happens because the user's code has an undefined use, then, the
> consensus has been to go ahead and optimize it.
> 
> If it happens for any other reason, then it's likely a bug in GCC.  We
> had a couple of these when we made EVRP a re-usable module and started
> exploiting its data in the jump threader.
> 
> So you need to work backwards from this point to figure out how you got
> here.
> 
> jeff

Re: A bug in vrp_meet?

[Richard Biener]

On March 1, 2019 6:49:20 PM GMT+01:00, Qing Zhao <qing.zhao@oracle.com> wrote:
>Jeff,
>
>thanks a lot for the reply.
>
>this is really helpful.
>
>I double checked the dumped intermediate file for pass “dom3", and
>located the following for _152:
>
>****BEFORE the pass “dom3”, there is no _152, the corresponding Block
>looks like:
>
>  <bb 4> [local count: 12992277]:
>  _98 = (int) ufcMSR_52(D);
>  k_105 = (sword) ufcMSR_52(D);
>  i_49 = _98 > 0 ? k_105 : 0;
>
>***During the pass “doms”,  _152 is generated as following:
>
>Optimizing block #4
>….
>Visiting statement:
>i_49 = _98 > 0 ? k_105 : 0;
>Meeting
>  [0, 65535]
>and
>  [0, 0]
>to
>  [0, 65535]
>Intersecting
>  [0, 65535]
>and
>  [0, 65535]
>to
>  [0, 65535]
>Optimizing statement i_49 = _98 > 0 ? k_105 : 0;
>  Replaced 'k_105' with variable '_98'
>gimple_simplified to _152 = MAX_EXPR <_98, 0>;
>i_49 = _152;
>  Folded to: i_49 = _152;
>LKUP STMT i_49 = _152
>==== ASGN i_49 = _152
>
>then bb 4 becomes:
>
>  <bb 4> [local count: 12992277]:
>  _98 = (int) ufcMSR_52(D);
>  k_105 = _98;
>  _152 = MAX_EXPR <_98, 0>;
>  i_49 = _152;
>
>and all the i_49 are replaced with _152. 
>
>However, the value range info for _152 doesnot reflect the one for
>i_49, it keeps as UNDEFINED. 
>
>is this the root problem?  

It looks like DOM fails to visit stmts generated by simplification. Can you open a bug report with a testcase?

Richard. 

>thanks a lot.
>
>Qing
>
>> On Feb 28, 2019, at 1:54 PM, Jeff Law <law@redhat.com> wrote:
>> 
>> On 2/28/19 10:05 AM, Qing Zhao wrote:
>>> Hi,
>>> 
>>> I have been debugging a runtime error caused by value range
>propagation. and finally located to the following gcc routine:
>>> 
>>> vrp_meet_1 in gcc/tree-vrp.c
>>> 
>>> ====
>>> /* Meet operation for value ranges.  Given two value ranges VR0 and
>>>   VR1, store in VR0 a range that contains both VR0 and VR1.  This
>>>   may not be the smallest possible such range.  */
>>> 
>>> static void 
>>> vrp_meet_1 (value_range *vr0, const value_range *vr1)
>>> {
>>>  value_range saved;
>>> 
>>>  if (vr0->type == VR_UNDEFINED)
>>>    {    
>>>      set_value_range (vr0, vr1->type, vr1->min, vr1->max,
>vr1->equiv);
>>>      return;
>>>    }    
>>> 
>>>  if (vr1->type == VR_UNDEFINED)
>>>    {    
>>>      /* VR0 already has the resulting range.  */
>>>      return;
>>>    }    
>>> ====
>>> 
>>> In the above, when one of vr0 or vr1 is VR_UNDEFINED,  the meet
>result of these two will be  the other VALUE. 
>>> 
>>> This seems not correct to me. 
>> That's the optimistic nature of VRP.  It's generally desired
>behavior.
>> 
>>> 
>>> For example, the following is the located incorrect value range
>propagation:  (portion from the dump file *.181t.dom3)
>>> 
>>> ====
>>> Visiting PHI node: i_83 = PHI <_152(20), 0(22)>
>>>    Argument #0 (20 -> 10 executable)
>>>        _152: UNDEFINED
>>>    Argument #1 (22 -> 10 executable)
>>>        0: [0, 0]
>>> Meeting
>>>  UNDEFINED
>>> and
>>>  [0, 0]
>>> to
>>>  [0, 0]
>>> Intersecting
>>>  [0, 0]
>>> and
>>>  [0, 65535]
>>> to
>>>  [0, 0]
>>> ====
>>> 
>>> 
>>> In the above, “i_83” is defined as PHI <_152(20), 0(22)>,   the 1st
>argument is UNDEFINED at this time(but its value range definitely is
>NOT [0,0]),
>>> and the 2nd argument is 0.
>> If it's value is undefined then it can be any value we want.  We
>choose
>> to make it equal to the other argument.
>> 
>> If VRP later finds that _152 changes, then it will go back and
>> reevaluate the PHI.  That's one of the basic design principles of the
>> optimistic propagators.
>> 
>>> 
>>> “vrp_meet” generate a VR_RANGE with [0,0] for “i_83” based on the
>current algorithm.  Obviously, this result VR_RANGE with [0,0] does NOT
>
>>> contain the value ranges for _152. 
>>> 
>>> the result of “vrp_meet” is Not correct.  and this incorrect value
>range result finally caused the runtime error. 
>>> 
>>> I ‘d like to modify the vrp_meet_1 as following:
>>> 
>>> ====
>>> static void 
>>> vrp_meet_1 (value_range *vr0, const value_range *vr1)
>>> {
>>>  value_range saved;
>>> 
>>>  if (vr0->type == VR_UNDEFINED)
>>>    {    
>>>      /* VR0 already has the resulting range. */
>>>      return;
>>>    }    
>>> 
>>>  if (vr1->type == VR_UNDEFINED)
>>>    {    
>>>      set_value_range_to_undefined (vr0)
>>>     return;
>>>    }    
>>> ====
>>> 
>>> let me know your opinion.
>>> 
>>> thanks a lot for the help.
>> I think we (Richi and I) went through this about a year ago and the
>> conclusion was we should be looking at how you're getting into the
>> vrp_meet with the VR_UNDEFINED.
>> 
>> If it happens because the user's code has an undefined use, then, the
>> consensus has been to go ahead and optimize it.
>> 
>> If it happens for any other reason, then it's likely a bug in GCC. 
>We
>> had a couple of these when we made EVRP a re-usable module and
>started
>> exploiting its data in the jump threader.
>> 
>> So you need to work backwards from this point to figure out how you
>got
>> here.
>> 
>> jeff

Re: A bug in vrp_meet?

[Qing Zhao]

> On Mar 1, 2019, at 1:25 PM, Richard Biener <richard.guenther@gmail.com> wrote:
> 
> On March 1, 2019 6:49:20 PM GMT+01:00, Qing Zhao <qing.zhao@oracle.com <mailto:qing.zhao@oracle.com>> wrote:
>> Jeff,
>> 
>> thanks a lot for the reply.
>> 
>> this is really helpful.
>> 
>> I double checked the dumped intermediate file for pass “dom3", and
>> located the following for _152:
>> 
>> ****BEFORE the pass “dom3”, there is no _152, the corresponding Block
>> looks like:
>> 
>> <bb 4> [local count: 12992277]:
>> _98 = (int) ufcMSR_52(D);
>> k_105 = (sword) ufcMSR_52(D);
>> i_49 = _98 > 0 ? k_105 : 0;
>> 
>> ***During the pass “doms”,  _152 is generated as following:
>> 
>> Optimizing block #4
>> ….
>> Visiting statement:
>> i_49 = _98 > 0 ? k_105 : 0;
>> Meeting
>> [0, 65535]
>> and
>> [0, 0]
>> to
>> [0, 65535]
>> Intersecting
>> [0, 65535]
>> and
>> [0, 65535]
>> to
>> [0, 65535]
>> Optimizing statement i_49 = _98 > 0 ? k_105 : 0;
>> Replaced 'k_105' with variable '_98'
>> gimple_simplified to _152 = MAX_EXPR <_98, 0>;
>> i_49 = _152;
>> Folded to: i_49 = _152;
>> LKUP STMT i_49 = _152
>> ==== ASGN i_49 = _152
>> 
>> then bb 4 becomes:
>> 
>> <bb 4> [local count: 12992277]:
>> _98 = (int) ufcMSR_52(D);
>> k_105 = _98;
>> _152 = MAX_EXPR <_98, 0>;
>> i_49 = _152;
>> 
>> and all the i_49 are replaced with _152. 
>> 
>> However, the value range info for _152 doesnot reflect the one for
>> i_49, it keeps as UNDEFINED. 
>> 
>> is this the root problem?  
> 
> It looks like DOM fails to visit stmts generated by simplification. Can you open a bug report with a testcase?

The problem is, It took me quite some time in order to come up with a small and independent testcase for this problem,
a little bit change made the error disappear.  

do you have any suggestion on this?  or can you give me some hint on how to fix this in DOM?  then I can try the fix on my side?

Thanks a lot.

Qing


> 
> Richard. 
> 

Re: A bug in vrp_meet?

[Richard Biener]

On Fri, Mar 1, 2019 at 10:02 PM Qing Zhao <qing.zhao@oracle.com> wrote:
>
>
> On Mar 1, 2019, at 1:25 PM, Richard Biener <richard.guenther@gmail.com> wrote:
>
> On March 1, 2019 6:49:20 PM GMT+01:00, Qing Zhao <qing.zhao@oracle.com> wrote:
>
> Jeff,
>
> thanks a lot for the reply.
>
> this is really helpful.
>
> I double checked the dumped intermediate file for pass “dom3", and
> located the following for _152:
>
> ****BEFORE the pass “dom3”, there is no _152, the corresponding Block
> looks like:
>
> <bb 4> [local count: 12992277]:
> _98 = (int) ufcMSR_52(D);
> k_105 = (sword) ufcMSR_52(D);
> i_49 = _98 > 0 ? k_105 : 0;
>
> ***During the pass “doms”,  _152 is generated as following:
>
> Optimizing block #4
> ….
> Visiting statement:
> i_49 = _98 > 0 ? k_105 : 0;
> Meeting
> [0, 65535]
> and
> [0, 0]
> to
> [0, 65535]
> Intersecting
> [0, 65535]
> and
> [0, 65535]
> to
> [0, 65535]
> Optimizing statement i_49 = _98 > 0 ? k_105 : 0;
> Replaced 'k_105' with variable '_98'
> gimple_simplified to _152 = MAX_EXPR <_98, 0>;
> i_49 = _152;
> Folded to: i_49 = _152;
> LKUP STMT i_49 = _152
> ==== ASGN i_49 = _152
>
> then bb 4 becomes:
>
> <bb 4> [local count: 12992277]:
> _98 = (int) ufcMSR_52(D);
> k_105 = _98;
> _152 = MAX_EXPR <_98, 0>;
> i_49 = _152;
>
> and all the i_49 are replaced with _152.
>
> However, the value range info for _152 doesnot reflect the one for
> i_49, it keeps as UNDEFINED.
>
> is this the root problem?
>
>
> It looks like DOM fails to visit stmts generated by simplification. Can you open a bug report with a testcase?
>
>
> The problem is, It took me quite some time in order to come up with a small and independent testcase for this problem,
> a little bit change made the error disappear.
>
> do you have any suggestion on this?  or can you give me some hint on how to fix this in DOM?  then I can try the fix on my side?

I remember running into similar issues in the past where I tried to
extract temporary nonnull ranges from divisions.
I have there

@@ -1436,11 +1436,16 @@ dom_opt_dom_walker::before_dom_children
   m_avail_exprs_stack->pop_to_marker ();

   edge taken_edge = NULL;
-  for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
-    {
-      evrp_range_analyzer.record_ranges_from_stmt (gsi_stmt (gsi), false);
-      taken_edge = this->optimize_stmt (bb, gsi);
-    }
+  gsi = gsi_start_bb (bb);
+  if (!gsi_end_p (gsi))
+    while (1)
+      {
+       evrp_range_analyzer.record_def_ranges_from_stmt (gsi_stmt (gsi), false);
+       taken_edge = this->optimize_stmt (bb, &gsi);
+       if (gsi_end_p (gsi))
+         break;
+       evrp_range_analyzer.record_use_ranges_from_stmt (gsi_stmt (gsi));
+      }

   /* Now prepare to process dominated blocks.  */
   record_edge_info (bb);

OTOH the issue in your case is that fold emits new stmts before gsi but the
above loop will never look at them.  See tree-ssa-forwprop.c for code how
to deal with this (setting a pass-local flag on stmts visited and walking back
to unvisited, newly inserted ones).  The fold_stmt interface could in theory
also be extended to insert new stmts on a sequence passed to it so the
caller would be responsible for inserting them into the IL and could then
more easily revisit them (but that's a bigger task).

So, does the following help?

Index: gcc/tree-ssa-dom.c
===================================================================
--- gcc/tree-ssa-dom.c  (revision 269361)
+++ gcc/tree-ssa-dom.c  (working copy)
@@ -1482,8 +1482,25 @@ dom_opt_dom_walker::before_dom_children
   edge taken_edge = NULL;
   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
     {
+      gimple_stmt_iterator pgsi = gsi;
+      gsi_prev (&pgsi);
       evrp_range_analyzer.record_ranges_from_stmt (gsi_stmt (gsi), false);
       taken_edge = this->optimize_stmt (bb, gsi);
+      gimple_stmt_iterator npgsi = gsi;
+      gsi_prev (&npgsi);
+      /* Walk new stmts eventually inserted by DOM.  gsi_stmt (gsi) itself
+        while it may be changed should not have gotten a new definition.  */
+      if (gsi_stmt (pgsi) != gsi_stmt (npgsi))
+       do
+         {
+           if (gsi_end_p (pgsi))
+             pgsi = gsi_start_bb (bb);
+           else
+             gsi_next (&pgsi);
+           evrp_range_analyzer.record_ranges_from_stmt (gsi_stmt (pgsi),
+                                                        false);
+         }
+       while (gsi_stmt (pgsi) != gsi_stmt (gsi));
     }

   /* Now prepare to process dominated blocks.  */


Richard.

> Thanks a lot.
>
> Qing
>
>
>
> Richard.
>
>

Re: A bug in vrp_meet?

[Qing Zhao]

Richard,

thanks a lot for your suggested fix. 

I will try it.

Qing
> On Mar 4, 2019, at 5:45 AM, Richard Biener <richard.guenther@gmail.com> wrote:
> 
> On Fri, Mar 1, 2019 at 10:02 PM Qing Zhao <qing.zhao@oracle.com> wrote:
>> 
>> 
>> On Mar 1, 2019, at 1:25 PM, Richard Biener <richard.guenther@gmail.com> wrote:
>> 
>> On March 1, 2019 6:49:20 PM GMT+01:00, Qing Zhao <qing.zhao@oracle.com> wrote:
>> 
>> Jeff,
>> 
>> thanks a lot for the reply.
>> 
>> this is really helpful.
>> 
>> I double checked the dumped intermediate file for pass “dom3", and
>> located the following for _152:
>> 
>> ****BEFORE the pass “dom3”, there is no _152, the corresponding Block
>> looks like:
>> 
>> <bb 4> [local count: 12992277]:
>> _98 = (int) ufcMSR_52(D);
>> k_105 = (sword) ufcMSR_52(D);
>> i_49 = _98 > 0 ? k_105 : 0;
>> 
>> ***During the pass “doms”,  _152 is generated as following:
>> 
>> Optimizing block #4
>> ….
>> Visiting statement:
>> i_49 = _98 > 0 ? k_105 : 0;
>> Meeting
>> [0, 65535]
>> and
>> [0, 0]
>> to
>> [0, 65535]
>> Intersecting
>> [0, 65535]
>> and
>> [0, 65535]
>> to
>> [0, 65535]
>> Optimizing statement i_49 = _98 > 0 ? k_105 : 0;
>> Replaced 'k_105' with variable '_98'
>> gimple_simplified to _152 = MAX_EXPR <_98, 0>;
>> i_49 = _152;
>> Folded to: i_49 = _152;
>> LKUP STMT i_49 = _152
>> ==== ASGN i_49 = _152
>> 
>> then bb 4 becomes:
>> 
>> <bb 4> [local count: 12992277]:
>> _98 = (int) ufcMSR_52(D);
>> k_105 = _98;
>> _152 = MAX_EXPR <_98, 0>;
>> i_49 = _152;
>> 
>> and all the i_49 are replaced with _152.
>> 
>> However, the value range info for _152 doesnot reflect the one for
>> i_49, it keeps as UNDEFINED.
>> 
>> is this the root problem?
>> 
>> 
>> It looks like DOM fails to visit stmts generated by simplification. Can you open a bug report with a testcase?
>> 
>> 
>> The problem is, It took me quite some time in order to come up with a small and independent testcase for this problem,
>> a little bit change made the error disappear.
>> 
>> do you have any suggestion on this?  or can you give me some hint on how to fix this in DOM?  then I can try the fix on my side?
> 
> I remember running into similar issues in the past where I tried to
> extract temporary nonnull ranges from divisions.
> I have there
> 
> @@ -1436,11 +1436,16 @@ dom_opt_dom_walker::before_dom_children
>   m_avail_exprs_stack->pop_to_marker ();
> 
>   edge taken_edge = NULL;
> -  for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
> -    {
> -      evrp_range_analyzer.record_ranges_from_stmt (gsi_stmt (gsi), false);
> -      taken_edge = this->optimize_stmt (bb, gsi);
> -    }
> +  gsi = gsi_start_bb (bb);
> +  if (!gsi_end_p (gsi))
> +    while (1)
> +      {
> +       evrp_range_analyzer.record_def_ranges_from_stmt (gsi_stmt (gsi), false);
> +       taken_edge = this->optimize_stmt (bb, &gsi);
> +       if (gsi_end_p (gsi))
> +         break;
> +       evrp_range_analyzer.record_use_ranges_from_stmt (gsi_stmt (gsi));
> +      }
> 
>   /* Now prepare to process dominated blocks.  */
>   record_edge_info (bb);
> 
> OTOH the issue in your case is that fold emits new stmts before gsi but the
> above loop will never look at them.  See tree-ssa-forwprop.c for code how
> to deal with this (setting a pass-local flag on stmts visited and walking back
> to unvisited, newly inserted ones).  The fold_stmt interface could in theory
> also be extended to insert new stmts on a sequence passed to it so the
> caller would be responsible for inserting them into the IL and could then
> more easily revisit them (but that's a bigger task).
> 
> So, does the following help?
> 
> Index: gcc/tree-ssa-dom.c
> ===================================================================
> --- gcc/tree-ssa-dom.c  (revision 269361)
> +++ gcc/tree-ssa-dom.c  (working copy)
> @@ -1482,8 +1482,25 @@ dom_opt_dom_walker::before_dom_children
>   edge taken_edge = NULL;
>   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
>     {
> +      gimple_stmt_iterator pgsi = gsi;
> +      gsi_prev (&pgsi);
>       evrp_range_analyzer.record_ranges_from_stmt (gsi_stmt (gsi), false);
>       taken_edge = this->optimize_stmt (bb, gsi);
> +      gimple_stmt_iterator npgsi = gsi;
> +      gsi_prev (&npgsi);
> +      /* Walk new stmts eventually inserted by DOM.  gsi_stmt (gsi) itself
> +        while it may be changed should not have gotten a new definition.  */
> +      if (gsi_stmt (pgsi) != gsi_stmt (npgsi))
> +       do
> +         {
> +           if (gsi_end_p (pgsi))
> +             pgsi = gsi_start_bb (bb);
> +           else
> +             gsi_next (&pgsi);
> +           evrp_range_analyzer.record_ranges_from_stmt (gsi_stmt (pgsi),
> +                                                        false);
> +         }
> +       while (gsi_stmt (pgsi) != gsi_stmt (gsi));
>     }
> 
>   /* Now prepare to process dominated blocks.  */
> 
> 
> Richard.
> 
>> Thanks a lot.
>> 
>> Qing
>> 
>> 
>> 
>> Richard.
>> 
>> 

Re: A bug in vrp_meet?

[Qing Zhao]

Hi, Richard,

> On Mar 4, 2019, at 5:45 AM, Richard Biener <richard.guenther@gmail.com> wrote:
>> 
>> It looks like DOM fails to visit stmts generated by simplification. Can you open a bug report with a testcase?
>> 
>> 
>> The problem is, It took me quite some time in order to come up with a small and independent testcase for this problem,
>> a little bit change made the error disappear.
>> 
>> do you have any suggestion on this?  or can you give me some hint on how to fix this in DOM?  then I can try the fix on my side?
> 
> I remember running into similar issues in the past where I tried to
> extract temporary nonnull ranges from divisions.
> I have there
> 
> @@ -1436,11 +1436,16 @@ dom_opt_dom_walker::before_dom_children
>   m_avail_exprs_stack->pop_to_marker ();
> 
>   edge taken_edge = NULL;
> -  for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
> -    {
> -      evrp_range_analyzer.record_ranges_from_stmt (gsi_stmt (gsi), false);
> -      taken_edge = this->optimize_stmt (bb, gsi);
> -    }
> +  gsi = gsi_start_bb (bb);
> +  if (!gsi_end_p (gsi))
> +    while (1)
> +      {
> +       evrp_range_analyzer.record_def_ranges_from_stmt (gsi_stmt (gsi), false);
> +       taken_edge = this->optimize_stmt (bb, &gsi);
> +       if (gsi_end_p (gsi))
> +         break;
> +       evrp_range_analyzer.record_use_ranges_from_stmt (gsi_stmt (gsi));
> +      }
> 
>   /* Now prepare to process dominated blocks.  */
>   record_edge_info (bb);
> 
> OTOH the issue in your case is that fold emits new stmts before gsi but the
> above loop will never look at them.  See tree-ssa-forwprop.c for code how
> to deal with this (setting a pass-local flag on stmts visited and walking back
> to unvisited, newly inserted ones).  The fold_stmt interface could in theory
> also be extended to insert new stmts on a sequence passed to it so the
> caller would be responsible for inserting them into the IL and could then
> more easily revisit them (but that's a bigger task).
> 
> So, does the following help?

Yes, this change fixed the error in my side, now, in the dumped file for pass dom3:

====
Visiting statement:
i_49 = _98 > 0 ? k_105 : 0;
Meeting
  [0, 65535]
and
  [0, 0]
to
  [0, 65535]
Intersecting
  [0, 65535]
and
  [0, 65535]
to
  [0, 65535]
Optimizing statement i_49 = _98 > 0 ? k_105 : 0;
  Replaced 'k_105' with variable '_98'
gimple_simplified to _152 = MAX_EXPR <_98, 0>;
i_49 = _152;
  Folded to: i_49 = _152;
LKUP STMT i_49 = _152
==== ASGN i_49 = _152

Visiting statement:
_152 = MAX_EXPR <_98, 0>;

Visiting statement:
i_49 = _152;
Intersecting
  [0, 65535]  EQUIVALENCES: { _152 } (1 elements)
and
  [0, 65535]
to
  [0, 65535]  EQUIVALENCES: { _152 } (1 elements)
====

We can clearly see from the above, all the new stmts generated by fold are visited now. 

it is also confirmed that the runtime error caused by this bug was gone with this fix.

So, what’s the next step for this issue?

will you commit this fix to gcc9 and gcc8  (we need it in gcc8)?

or I can test this fix on my side and commit it to both gcc9 and gcc8?

thanks.

Qing

> 
> Index: gcc/tree-ssa-dom.c
> ===================================================================
> --- gcc/tree-ssa-dom.c  (revision 269361)
> +++ gcc/tree-ssa-dom.c  (working copy)
> @@ -1482,8 +1482,25 @@ dom_opt_dom_walker::before_dom_children
>   edge taken_edge = NULL;
>   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
>     {
> +      gimple_stmt_iterator pgsi = gsi;
> +      gsi_prev (&pgsi);
>       evrp_range_analyzer.record_ranges_from_stmt (gsi_stmt (gsi), false);
>       taken_edge = this->optimize_stmt (bb, gsi);
> +      gimple_stmt_iterator npgsi = gsi;
> +      gsi_prev (&npgsi);
> +      /* Walk new stmts eventually inserted by DOM.  gsi_stmt (gsi) itself
> +        while it may be changed should not have gotten a new definition.  */
> +      if (gsi_stmt (pgsi) != gsi_stmt (npgsi))
> +       do
> +         {
> +           if (gsi_end_p (pgsi))
> +             pgsi = gsi_start_bb (bb);
> +           else
> +             gsi_next (&pgsi);
> +           evrp_range_analyzer.record_ranges_from_stmt (gsi_stmt (pgsi),
> +                                                        false);
> +         }
> +       while (gsi_stmt (pgsi) != gsi_stmt (gsi));
>     }
> 
>   /* Now prepare to process dominated blocks.  */
> 
> 
> Richard.
> 
>> Thanks a lot.
>> 
>> Qing
>> 
>> 
>> 
>> Richard.
>> 
>> 

Re: A bug in vrp_meet?

[Richard Biener]

On Mon, Mar 4, 2019 at 11:01 PM Qing Zhao <qing.zhao@oracle.com> wrote:
>
> Hi, Richard,
>
> > On Mar 4, 2019, at 5:45 AM, Richard Biener <richard.guenther@gmail.com> wrote:
> >>
> >> It looks like DOM fails to visit stmts generated by simplification. Can you open a bug report with a testcase?
> >>
> >>
> >> The problem is, It took me quite some time in order to come up with a small and independent testcase for this problem,
> >> a little bit change made the error disappear.
> >>
> >> do you have any suggestion on this?  or can you give me some hint on how to fix this in DOM?  then I can try the fix on my side?
> >
> > I remember running into similar issues in the past where I tried to
> > extract temporary nonnull ranges from divisions.
> > I have there
> >
> > @@ -1436,11 +1436,16 @@ dom_opt_dom_walker::before_dom_children
> >   m_avail_exprs_stack->pop_to_marker ();
> >
> >   edge taken_edge = NULL;
> > -  for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
> > -    {
> > -      evrp_range_analyzer.record_ranges_from_stmt (gsi_stmt (gsi), false);
> > -      taken_edge = this->optimize_stmt (bb, gsi);
> > -    }
> > +  gsi = gsi_start_bb (bb);
> > +  if (!gsi_end_p (gsi))
> > +    while (1)
> > +      {
> > +       evrp_range_analyzer.record_def_ranges_from_stmt (gsi_stmt (gsi), false);
> > +       taken_edge = this->optimize_stmt (bb, &gsi);
> > +       if (gsi_end_p (gsi))
> > +         break;
> > +       evrp_range_analyzer.record_use_ranges_from_stmt (gsi_stmt (gsi));
> > +      }
> >
> >   /* Now prepare to process dominated blocks.  */
> >   record_edge_info (bb);
> >
> > OTOH the issue in your case is that fold emits new stmts before gsi but the
> > above loop will never look at them.  See tree-ssa-forwprop.c for code how
> > to deal with this (setting a pass-local flag on stmts visited and walking back
> > to unvisited, newly inserted ones).  The fold_stmt interface could in theory
> > also be extended to insert new stmts on a sequence passed to it so the
> > caller would be responsible for inserting them into the IL and could then
> > more easily revisit them (but that's a bigger task).
> >
> > So, does the following help?
>
> Yes, this change fixed the error in my side, now, in the dumped file for pass dom3:
>
> ====
> Visiting statement:
> i_49 = _98 > 0 ? k_105 : 0;
> Meeting
>   [0, 65535]
> and
>   [0, 0]
> to
>   [0, 65535]
> Intersecting
>   [0, 65535]
> and
>   [0, 65535]
> to
>   [0, 65535]
> Optimizing statement i_49 = _98 > 0 ? k_105 : 0;
>   Replaced 'k_105' with variable '_98'
> gimple_simplified to _152 = MAX_EXPR <_98, 0>;
> i_49 = _152;

Ah, that looks interesting.  From this detail we might be
able to derive a testcase as well - a GIMPLE one
eventually because DOM runs quite late.  It's also interesting
to see the inefficient code here (the extra copy), probably
some known issue with match-and-simplify, I'd have to check.

>   Folded to: i_49 = _152;
> LKUP STMT i_49 = _152
> ==== ASGN i_49 = _152
>
> Visiting statement:
> _152 = MAX_EXPR <_98, 0>;
>
> Visiting statement:
> i_49 = _152;
> Intersecting
>   [0, 65535]  EQUIVALENCES: { _152 } (1 elements)
> and
>   [0, 65535]
> to
>   [0, 65535]  EQUIVALENCES: { _152 } (1 elements)
> ====
>
> We can clearly see from the above, all the new stmts generated by fold are visited now.

We can also see that DOMs optimize_stmt code is not executed on the first stmt
of the folding result (the MAX_EXPR), so the fix can be probably
amended/simplified
with that in mind.

> it is also confirmed that the runtime error caused by this bug was gone with this fix.
>
> So, what’s the next step for this issue?
>
> will you commit this fix to gcc9 and gcc8  (we need it in gcc8)?

I'll see to carve out some cycles trying to find a testcase and amend
the fix a bit
and will take care of testing/submitting the fix.  Thanks for testing
that it works
for your case.

Richard.

> or I can test this fix on my side and commit it to both gcc9 and gcc8?
>
> thanks.
>
> Qing
>
> >
> > Index: gcc/tree-ssa-dom.c
> > ===================================================================
> > --- gcc/tree-ssa-dom.c  (revision 269361)
> > +++ gcc/tree-ssa-dom.c  (working copy)
> > @@ -1482,8 +1482,25 @@ dom_opt_dom_walker::before_dom_children
> >   edge taken_edge = NULL;
> >   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
> >     {
> > +      gimple_stmt_iterator pgsi = gsi;
> > +      gsi_prev (&pgsi);
> >       evrp_range_analyzer.record_ranges_from_stmt (gsi_stmt (gsi), false);
> >       taken_edge = this->optimize_stmt (bb, gsi);
> > +      gimple_stmt_iterator npgsi = gsi;
> > +      gsi_prev (&npgsi);
> > +      /* Walk new stmts eventually inserted by DOM.  gsi_stmt (gsi) itself
> > +        while it may be changed should not have gotten a new definition.  */
> > +      if (gsi_stmt (pgsi) != gsi_stmt (npgsi))
> > +       do
> > +         {
> > +           if (gsi_end_p (pgsi))
> > +             pgsi = gsi_start_bb (bb);
> > +           else
> > +             gsi_next (&pgsi);
> > +           evrp_range_analyzer.record_ranges_from_stmt (gsi_stmt (pgsi),
> > +                                                        false);
> > +         }
> > +       while (gsi_stmt (pgsi) != gsi_stmt (gsi));
> >     }
> >
> >   /* Now prepare to process dominated blocks.  */
> >
> >
> > Richard.
> >
> >> Thanks a lot.
> >>
> >> Qing
> >>
> >>
> >>
> >> Richard.
> >>
> >>
>

Re: A bug in vrp_meet?

[Richard Biener]

On Tue, Mar 5, 2019 at 10:48 AM Richard Biener
<richard.guenther@gmail.com> wrote:
>
> On Mon, Mar 4, 2019 at 11:01 PM Qing Zhao <qing.zhao@oracle.com> wrote:
> >
> > Hi, Richard,
> >
> > > On Mar 4, 2019, at 5:45 AM, Richard Biener <richard.guenther@gmail.com> wrote:
> > >>
> > >> It looks like DOM fails to visit stmts generated by simplification. Can you open a bug report with a testcase?
> > >>
> > >>
> > >> The problem is, It took me quite some time in order to come up with a small and independent testcase for this problem,
> > >> a little bit change made the error disappear.
> > >>
> > >> do you have any suggestion on this?  or can you give me some hint on how to fix this in DOM?  then I can try the fix on my side?
> > >
> > > I remember running into similar issues in the past where I tried to
> > > extract temporary nonnull ranges from divisions.
> > > I have there
> > >
> > > @@ -1436,11 +1436,16 @@ dom_opt_dom_walker::before_dom_children
> > >   m_avail_exprs_stack->pop_to_marker ();
> > >
> > >   edge taken_edge = NULL;
> > > -  for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
> > > -    {
> > > -      evrp_range_analyzer.record_ranges_from_stmt (gsi_stmt (gsi), false);
> > > -      taken_edge = this->optimize_stmt (bb, gsi);
> > > -    }
> > > +  gsi = gsi_start_bb (bb);
> > > +  if (!gsi_end_p (gsi))
> > > +    while (1)
> > > +      {
> > > +       evrp_range_analyzer.record_def_ranges_from_stmt (gsi_stmt (gsi), false);
> > > +       taken_edge = this->optimize_stmt (bb, &gsi);
> > > +       if (gsi_end_p (gsi))
> > > +         break;
> > > +       evrp_range_analyzer.record_use_ranges_from_stmt (gsi_stmt (gsi));
> > > +      }
> > >
> > >   /* Now prepare to process dominated blocks.  */
> > >   record_edge_info (bb);
> > >
> > > OTOH the issue in your case is that fold emits new stmts before gsi but the
> > > above loop will never look at them.  See tree-ssa-forwprop.c for code how
> > > to deal with this (setting a pass-local flag on stmts visited and walking back
> > > to unvisited, newly inserted ones).  The fold_stmt interface could in theory
> > > also be extended to insert new stmts on a sequence passed to it so the
> > > caller would be responsible for inserting them into the IL and could then
> > > more easily revisit them (but that's a bigger task).
> > >
> > > So, does the following help?
> >
> > Yes, this change fixed the error in my side, now, in the dumped file for pass dom3:
> >
> > ====
> > Visiting statement:
> > i_49 = _98 > 0 ? k_105 : 0;
> > Meeting
> >   [0, 65535]
> > and
> >   [0, 0]
> > to
> >   [0, 65535]
> > Intersecting
> >   [0, 65535]
> > and
> >   [0, 65535]
> > to
> >   [0, 65535]
> > Optimizing statement i_49 = _98 > 0 ? k_105 : 0;
> >   Replaced 'k_105' with variable '_98'
> > gimple_simplified to _152 = MAX_EXPR <_98, 0>;
> > i_49 = _152;
>
> Ah, that looks interesting.  From this detail we might be
> able to derive a testcase as well - a GIMPLE one
> eventually because DOM runs quite late.  It's also interesting
> to see the inefficient code here (the extra copy), probably
> some known issue with match-and-simplify, I'd have to check.
>
> >   Folded to: i_49 = _152;
> > LKUP STMT i_49 = _152
> > ==== ASGN i_49 = _152
> >
> > Visiting statement:
> > _152 = MAX_EXPR <_98, 0>;
> >
> > Visiting statement:
> > i_49 = _152;
> > Intersecting
> >   [0, 65535]  EQUIVALENCES: { _152 } (1 elements)
> > and
> >   [0, 65535]
> > to
> >   [0, 65535]  EQUIVALENCES: { _152 } (1 elements)
> > ====
> >
> > We can clearly see from the above, all the new stmts generated by fold are visited now.
>
> We can also see that DOMs optimize_stmt code is not executed on the first stmt
> of the folding result (the MAX_EXPR), so the fix can be probably
> amended/simplified
> with that in mind.
>
> > it is also confirmed that the runtime error caused by this bug was gone with this fix.
> >
> > So, what’s the next step for this issue?
> >
> > will you commit this fix to gcc9 and gcc8  (we need it in gcc8)?
>
> I'll see to carve out some cycles trying to find a testcase and amend
> the fix a bit
> and will take care of testing/submitting the fix.  Thanks for testing
> that it works
> for your case.

I filed PR89595 with a testcase.

Richard.

> Richard.
>
> > or I can test this fix on my side and commit it to both gcc9 and gcc8?
> >
> > thanks.
> >
> > Qing
> >
> > >
> > > Index: gcc/tree-ssa-dom.c
> > > ===================================================================
> > > --- gcc/tree-ssa-dom.c  (revision 269361)
> > > +++ gcc/tree-ssa-dom.c  (working copy)
> > > @@ -1482,8 +1482,25 @@ dom_opt_dom_walker::before_dom_children
> > >   edge taken_edge = NULL;
> > >   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
> > >     {
> > > +      gimple_stmt_iterator pgsi = gsi;
> > > +      gsi_prev (&pgsi);
> > >       evrp_range_analyzer.record_ranges_from_stmt (gsi_stmt (gsi), false);
> > >       taken_edge = this->optimize_stmt (bb, gsi);
> > > +      gimple_stmt_iterator npgsi = gsi;
> > > +      gsi_prev (&npgsi);
> > > +      /* Walk new stmts eventually inserted by DOM.  gsi_stmt (gsi) itself
> > > +        while it may be changed should not have gotten a new definition.  */
> > > +      if (gsi_stmt (pgsi) != gsi_stmt (npgsi))
> > > +       do
> > > +         {
> > > +           if (gsi_end_p (pgsi))
> > > +             pgsi = gsi_start_bb (bb);
> > > +           else
> > > +             gsi_next (&pgsi);
> > > +           evrp_range_analyzer.record_ranges_from_stmt (gsi_stmt (pgsi),
> > > +                                                        false);
> > > +         }
> > > +       while (gsi_stmt (pgsi) != gsi_stmt (gsi));
> > >     }
> > >
> > >   /* Now prepare to process dominated blocks.  */
> > >
> > >
> > > Richard.
> > >
> > >> Thanks a lot.
> > >>
> > >> Qing
> > >>
> > >>
> > >>
> > >> Richard.
> > >>
> > >>
> >

Re: A bug in vrp_meet?

[Richard Biener]

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

On Tue, Mar 5, 2019 at 11:44 AM Richard Biener
<richard.guenther@gmail.com> wrote:
>
> On Tue, Mar 5, 2019 at 10:48 AM Richard Biener
> <richard.guenther@gmail.com> wrote:
> >
> > On Mon, Mar 4, 2019 at 11:01 PM Qing Zhao <qing.zhao@oracle.com> wrote:
> > >
> > > Hi, Richard,
> > >
> > > > On Mar 4, 2019, at 5:45 AM, Richard Biener <richard.guenther@gmail.com> wrote:
> > > >>
> > > >> It looks like DOM fails to visit stmts generated by simplification. Can you open a bug report with a testcase?
> > > >>
> > > >>
> > > >> The problem is, It took me quite some time in order to come up with a small and independent testcase for this problem,
> > > >> a little bit change made the error disappear.
> > > >>
> > > >> do you have any suggestion on this?  or can you give me some hint on how to fix this in DOM?  then I can try the fix on my side?
> > > >
> > > > I remember running into similar issues in the past where I tried to
> > > > extract temporary nonnull ranges from divisions.
> > > > I have there
> > > >
> > > > @@ -1436,11 +1436,16 @@ dom_opt_dom_walker::before_dom_children
> > > >   m_avail_exprs_stack->pop_to_marker ();
> > > >
> > > >   edge taken_edge = NULL;
> > > > -  for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
> > > > -    {
> > > > -      evrp_range_analyzer.record_ranges_from_stmt (gsi_stmt (gsi), false);
> > > > -      taken_edge = this->optimize_stmt (bb, gsi);
> > > > -    }
> > > > +  gsi = gsi_start_bb (bb);
> > > > +  if (!gsi_end_p (gsi))
> > > > +    while (1)
> > > > +      {
> > > > +       evrp_range_analyzer.record_def_ranges_from_stmt (gsi_stmt (gsi), false);
> > > > +       taken_edge = this->optimize_stmt (bb, &gsi);
> > > > +       if (gsi_end_p (gsi))
> > > > +         break;
> > > > +       evrp_range_analyzer.record_use_ranges_from_stmt (gsi_stmt (gsi));
> > > > +      }
> > > >
> > > >   /* Now prepare to process dominated blocks.  */
> > > >   record_edge_info (bb);
> > > >
> > > > OTOH the issue in your case is that fold emits new stmts before gsi but the
> > > > above loop will never look at them.  See tree-ssa-forwprop.c for code how
> > > > to deal with this (setting a pass-local flag on stmts visited and walking back
> > > > to unvisited, newly inserted ones).  The fold_stmt interface could in theory
> > > > also be extended to insert new stmts on a sequence passed to it so the
> > > > caller would be responsible for inserting them into the IL and could then
> > > > more easily revisit them (but that's a bigger task).
> > > >
> > > > So, does the following help?
> > >
> > > Yes, this change fixed the error in my side, now, in the dumped file for pass dom3:
> > >
> > > ====
> > > Visiting statement:
> > > i_49 = _98 > 0 ? k_105 : 0;
> > > Meeting
> > >   [0, 65535]
> > > and
> > >   [0, 0]
> > > to
> > >   [0, 65535]
> > > Intersecting
> > >   [0, 65535]
> > > and
> > >   [0, 65535]
> > > to
> > >   [0, 65535]
> > > Optimizing statement i_49 = _98 > 0 ? k_105 : 0;
> > >   Replaced 'k_105' with variable '_98'
> > > gimple_simplified to _152 = MAX_EXPR <_98, 0>;
> > > i_49 = _152;
> >
> > Ah, that looks interesting.  From this detail we might be
> > able to derive a testcase as well - a GIMPLE one
> > eventually because DOM runs quite late.  It's also interesting
> > to see the inefficient code here (the extra copy), probably
> > some known issue with match-and-simplify, I'd have to check.
> >
> > >   Folded to: i_49 = _152;
> > > LKUP STMT i_49 = _152
> > > ==== ASGN i_49 = _152
> > >
> > > Visiting statement:
> > > _152 = MAX_EXPR <_98, 0>;
> > >
> > > Visiting statement:
> > > i_49 = _152;
> > > Intersecting
> > >   [0, 65535]  EQUIVALENCES: { _152 } (1 elements)
> > > and
> > >   [0, 65535]
> > > to
> > >   [0, 65535]  EQUIVALENCES: { _152 } (1 elements)
> > > ====
> > >
> > > We can clearly see from the above, all the new stmts generated by fold are visited now.
> >
> > We can also see that DOMs optimize_stmt code is not executed on the first stmt
> > of the folding result (the MAX_EXPR), so the fix can be probably
> > amended/simplified
> > with that in mind.
> >
> > > it is also confirmed that the runtime error caused by this bug was gone with this fix.
> > >
> > > So, what’s the next step for this issue?
> > >
> > > will you commit this fix to gcc9 and gcc8  (we need it in gcc8)?
> >
> > I'll see to carve out some cycles trying to find a testcase and amend
> > the fix a bit
> > and will take care of testing/submitting the fix.  Thanks for testing
> > that it works
> > for your case.
>
> I filed PR89595 with a testcase.

So fixing it properly with also re-optimize_stmt those stmts so we'd CSE
the MAX_EXPR introduced by folding makes it somewhat ugly.

Bootstrapped on x86_64-unknown-linux-gnu, testing in progress.

Any ideas how to make it less so?  I can split out making optimize_stmt
take a gsi * btw, in case that's a more obvious change and it makes the
patch a little smaller.

Richard.

2019-03-05  Richard Biener  <rguenther@suse.de>

        PR tree-optimization/89595
        * tree-ssa-dom.c (dom_opt_dom_walker::optimize_stmt): Take
        stmt iterator as reference, take boolean output parameter to
        indicate whether the stmt was removed and thus the iterator
        already advanced.
        (dom_opt_dom_walker::before_dom_children): Re-iterate over
        stmts created by folding.

        * gcc.dg/torture/pr89595.c: New testcase.

[-- Attachment #2: fix-pr89595 --]
[-- Type: application/octet-stream, Size: 5460 bytes --]

2019-03-05  Richard Biener  <rguenther@suse.de>

	PR tree-optimization/89595
	* tree-ssa-dom.c (dom_opt_dom_walker::optimize_stmt): Take
	stmt iterator as reference, take boolean output parameter to
	indicate whether the stmt was removed and thus the iterator
	already advanced.
	(dom_opt_dom_walker::before_dom_children): Re-iterate over
	stmts created by folding.

	* gcc.dg/torture/pr89595.c: New testcase.

Index: gcc/tree-ssa-dom.c
===================================================================
--- gcc/tree-ssa-dom.c	(revision 269385)
+++ gcc/tree-ssa-dom.c	(working copy)
@@ -618,7 +618,7 @@ private:
      various tables mantained by DOM.  Returns the taken edge if
      the statement is a conditional with a statically determined
      value.  */
-  edge optimize_stmt (basic_block, gimple_stmt_iterator);
+  edge optimize_stmt (basic_block, gimple_stmt_iterator *, bool *);
 };
 
 /* Jump threading, redundancy elimination and const/copy propagation.
@@ -1480,11 +1480,47 @@ dom_opt_dom_walker::before_dom_children
   m_avail_exprs_stack->pop_to_marker ();
 
   edge taken_edge = NULL;
-  for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+  /* Walk new stmts eventually inserted by optimize_stmt folding after
+     substituting into the stmt at gsi.  Do not optimize stmt itself again.
+     We keep a stack of iteration endpoints for this purpose.  */
+  auto_vec<gimple_stmt_iterator, 8> gends;
+  gends.quick_push (gsi_none ());
+  gimple_stmt_iterator pgsi = gsi_none ();
+  gsi = gsi_start_bb (bb);
+  do
     {
+      if (gsi_stmt (gsi) == gsi_stmt (gends.last ()))
+	{
+	  gsi = gends.pop ();
+	  if (gsi_end_p (gsi))
+	    break;
+	  pgsi = gsi;
+	  gsi_next (&gsi);
+	  continue;
+	}
       evrp_range_analyzer.record_ranges_from_stmt (gsi_stmt (gsi), false);
-      taken_edge = this->optimize_stmt (bb, gsi);
+      bool removed_p = false;
+      taken_edge = this->optimize_stmt (bb, &gsi, &removed_p);
+      if (removed_p)
+	/* pgsi should still be right before gsi.  */
+	;
+      else
+	{
+	  if (gsi_end_p (pgsi))
+	    pgsi = gsi_start_bb (bb);
+	  else
+	    gsi_next (&pgsi);
+	  if (gsi_stmt (pgsi) != gsi_stmt (gsi))
+	    {
+	      gends.safe_push (gsi);
+	      gsi = pgsi;
+	      gsi_prev (&pgsi);
+	    }
+	  else
+	    gsi_next (&gsi);
+	}
     }
+  while (1);
 
   /* Now prepare to process dominated blocks.  */
   record_edge_info (bb);
@@ -1951,7 +1987,8 @@ test_for_singularity (gimple *stmt, gcon
       condition to an equality condition.  */
 
 edge
-dom_opt_dom_walker::optimize_stmt (basic_block bb, gimple_stmt_iterator si)
+dom_opt_dom_walker::optimize_stmt (basic_block bb, gimple_stmt_iterator *si,
+				   bool *removed_p)
 {
   gimple *stmt, *old_stmt;
   bool may_optimize_p;
@@ -1959,7 +1996,7 @@ dom_opt_dom_walker::optimize_stmt (basic
   bool was_noreturn;
   edge retval = NULL;
 
-  old_stmt = stmt = gsi_stmt (si);
+  old_stmt = stmt = gsi_stmt (*si);
   was_noreturn = is_gimple_call (stmt) && gimple_call_noreturn_p (stmt);
 
   if (dump_file && (dump_flags & TDF_DETAILS))
@@ -1982,9 +2019,9 @@ dom_opt_dom_walker::optimize_stmt (basic
 
       /* Try to fold the statement making sure that STMT is kept
 	 up to date.  */
-      if (fold_stmt (&si))
+      if (fold_stmt (si))
 	{
-	  stmt = gsi_stmt (si);
+	  stmt = gsi_stmt (*si);
 	  gimple_set_modified (stmt, true);
 
 	  if (dump_file && (dump_flags & TDF_DETAILS))
@@ -2032,8 +2069,8 @@ dom_opt_dom_walker::optimize_stmt (basic
 	  if (callee
 	      && fndecl_built_in_p (callee, BUILT_IN_CONSTANT_P))
 	    {
-	      propagate_tree_value_into_stmt (&si, integer_zero_node);
-	      stmt = gsi_stmt (si);
+	      propagate_tree_value_into_stmt (si, integer_zero_node);
+	      stmt = gsi_stmt (*si);
 	    }
 	}
 
@@ -2089,9 +2126,9 @@ dom_opt_dom_walker::optimize_stmt (basic
 	}
 
       update_stmt_if_modified (stmt);
-      eliminate_redundant_computations (&si, m_const_and_copies,
+      eliminate_redundant_computations (si, m_const_and_copies,
 					m_avail_exprs_stack);
-      stmt = gsi_stmt (si);
+      stmt = gsi_stmt (*si);
 
       /* Perform simple redundant store elimination.  */
       if (gimple_assign_single_p (stmt)
@@ -2118,13 +2155,14 @@ dom_opt_dom_walker::optimize_stmt (basic
 	    {
 	      basic_block bb = gimple_bb (stmt);
 	      unlink_stmt_vdef (stmt);
-	      if (gsi_remove (&si, true))
+	      if (gsi_remove (si, true))
 		{
 		  bitmap_set_bit (need_eh_cleanup, bb->index);
 		  if (dump_file && (dump_flags & TDF_DETAILS))
 		    fprintf (dump_file, "  Flagged to clear EH edges.\n");
 		}
 	      release_defs (stmt);
+	      *removed_p = true;
 	      return retval;
 	    }
 	}
Index: gcc/testsuite/gcc.dg/torture/pr89595.c
===================================================================
--- gcc/testsuite/gcc.dg/torture/pr89595.c	(nonexistent)
+++ gcc/testsuite/gcc.dg/torture/pr89595.c	(working copy)
@@ -0,0 +1,39 @@
+/* { dg-do run } */
+/* { dg-additional-options "-fgimple" } */
+
+int __attribute__((noipa))
+__GIMPLE(startwith("dom")) bar(int cond, int val)
+{
+  int i;
+
+  if (0 != 0)
+    goto bb_6;
+  else
+    goto bb_2;
+
+bb_2:
+  if (cond_5(D) != 0)
+    goto bb_4;
+  else
+    goto bb_5;
+
+bb_4:
+  i_6 = val_2(D);
+  i_1 = val_2(D) > 0 ? i_6 : 0;
+
+bb_5:
+  i_3 = __PHI (bb_4: i_1, bb_2: 0);
+  return i_3;
+
+bb_6:
+  i_4 = 1;
+  i_9 = 2;
+  goto bb_2;
+}
+
+int main()
+{
+  if (bar (1, 1) != 1)
+    __builtin_abort ();
+  return 0;
+}

Re: A bug in vrp_meet?

[Jeff Law]

On 3/5/19 7:44 AM, Richard Biener wrote:

> So fixing it properly with also re-optimize_stmt those stmts so we'd CSE
> the MAX_EXPR introduced by folding makes it somewhat ugly.
> 
> Bootstrapped on x86_64-unknown-linux-gnu, testing in progress.
> 
> Any ideas how to make it less so?  I can split out making optimize_stmt
> take a gsi * btw, in case that's a more obvious change and it makes the
> patch a little smaller.
> 
> Richard.
> 
> 2019-03-05  Richard Biener  <rguenther@suse.de>
> 
>         PR tree-optimization/89595
>         * tree-ssa-dom.c (dom_opt_dom_walker::optimize_stmt): Take
>         stmt iterator as reference, take boolean output parameter to
>         indicate whether the stmt was removed and thus the iterator
>         already advanced.
>         (dom_opt_dom_walker::before_dom_children): Re-iterate over
>         stmts created by folding.
> 
>         * gcc.dg/torture/pr89595.c: New testcase.
> 

Well, all the real logic changs are in the before_dom_children method.
The bits in optimize_stmt are trivial enough to effectively ignore.

I don't see a better way to discover and process statements that are
created in the bowels of fold_stmt.

Jeff

Re: A bug in vrp_meet?

[Richard Biener]

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

On Tue, Mar 5, 2019 at 10:36 PM Jeff Law <law@redhat.com> wrote:
>
> On 3/5/19 7:44 AM, Richard Biener wrote:
>
> > So fixing it properly with also re-optimize_stmt those stmts so we'd CSE
> > the MAX_EXPR introduced by folding makes it somewhat ugly.
> >
> > Bootstrapped on x86_64-unknown-linux-gnu, testing in progress.
> >
> > Any ideas how to make it less so?  I can split out making optimize_stmt
> > take a gsi * btw, in case that's a more obvious change and it makes the
> > patch a little smaller.
> >
> > Richard.
> >
> > 2019-03-05  Richard Biener  <rguenther@suse.de>
> >
> >         PR tree-optimization/89595
> >         * tree-ssa-dom.c (dom_opt_dom_walker::optimize_stmt): Take
> >         stmt iterator as reference, take boolean output parameter to
> >         indicate whether the stmt was removed and thus the iterator
> >         already advanced.
> >         (dom_opt_dom_walker::before_dom_children): Re-iterate over
> >         stmts created by folding.
> >
> >         * gcc.dg/torture/pr89595.c: New testcase.
> >
>
> Well, all the real logic changs are in the before_dom_children method.
> The bits in optimize_stmt are trivial enough to effectively ignore.
>
> I don't see a better way to discover and process statements that are
> created in the bowels of fold_stmt.

I'm not entirely happy so I created the following alternative which
is a bit larger and slower due to the pre-pass clearing the visited flag
but is IMHO easier to follow.  I guess there's plenty of TLC opportunity
here but then I also hope to retire the VN parts of DOM in favor
of the non-iterating RPO-VN code...

So - I'd lean to this variant even though it has the extra loop over stmts,
would you agree?

Bootstrap / regtest running on x86_64-unknown-linux-gnu.

Richard.

2019-03-06  Richard Biener  <rguenther@suse.de>

        PR tree-optimization/89595
        * tree-ssa-dom.c (dom_opt_dom_walker::optimize_stmt): Take
        stmt iterator as reference, take boolean output parameter to
        indicate whether the stmt was removed and thus the iterator
        already advanced.
        (dom_opt_dom_walker::before_dom_children): Re-iterate over
        stmts created by folding.

        * gcc.dg/torture/pr89595.c: New testcase.

[-- Attachment #2: fix-pr89595-2 --]
[-- Type: application/octet-stream, Size: 5562 bytes --]

2019-03-06  Richard Biener  <rguenther@suse.de>

	PR tree-optimization/89595
	* tree-ssa-dom.c (dom_opt_dom_walker::optimize_stmt): Take
	stmt iterator as reference, take boolean output parameter to
	indicate whether the stmt was removed and thus the iterator
	already advanced.
	(dom_opt_dom_walker::before_dom_children): Re-iterate over
	stmts created by folding.

	* gcc.dg/torture/pr89595.c: New testcase.

Index: gcc/tree-ssa-dom.c
===================================================================
--- gcc/tree-ssa-dom.c	(revision 269411)
+++ gcc/tree-ssa-dom.c	(working copy)
@@ -618,7 +618,7 @@ private:
      various tables mantained by DOM.  Returns the taken edge if
      the statement is a conditional with a statically determined
      value.  */
-  edge optimize_stmt (basic_block, gimple_stmt_iterator);
+  edge optimize_stmt (basic_block, gimple_stmt_iterator *, bool *);
 };
 
 /* Jump threading, redundancy elimination and const/copy propagation.
@@ -1480,10 +1480,48 @@ dom_opt_dom_walker::before_dom_children
   m_avail_exprs_stack->pop_to_marker ();
 
   edge taken_edge = NULL;
+  /* Initialize visited flag ahead of us, it has undefined state on
+     pass entry.  */
   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+    gimple_set_visited (gsi_stmt (gsi), false);
+  for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
     {
+      /* Do not optimize a stmt twice, substitution might end up with
+         _3 = _3 which is not valid.  */
+      if (gimple_visited_p (gsi_stmt (gsi)))
+	{
+	  gsi_next (&gsi);
+	  continue;
+	}
+
+      /* Compute range information and optimize the stmt.  */
       evrp_range_analyzer.record_ranges_from_stmt (gsi_stmt (gsi), false);
-      taken_edge = this->optimize_stmt (bb, gsi);
+      bool removed_p = false;
+      taken_edge = this->optimize_stmt (bb, &gsi, &removed_p);
+      if (!removed_p)
+	gimple_set_visited (gsi_stmt (gsi), true);
+
+      /* Go back and visit stmts inserted by folding after substituting
+	 into the stmt at gsi.  */
+      if (gsi_end_p (gsi))
+	{
+	  gcc_checking_assert (removed_p);
+	  gsi = gsi_last_bb (bb);
+	  while (!gsi_end_p (gsi) && !gimple_visited_p (gsi_stmt (gsi)))
+	    gsi_prev (&gsi);
+	}
+      else
+	{
+	  do
+	    {
+	      gsi_prev (&gsi);
+	    }
+	  while (!gsi_end_p (gsi) && !gimple_visited_p (gsi_stmt (gsi)));
+	}
+      if (gsi_end_p (gsi))
+	gsi = gsi_start_bb (bb);
+      else
+	gsi_next (&gsi);
     }
 
   /* Now prepare to process dominated blocks.  */
@@ -1951,7 +1989,8 @@ test_for_singularity (gimple *stmt, gcon
       condition to an equality condition.  */
 
 edge
-dom_opt_dom_walker::optimize_stmt (basic_block bb, gimple_stmt_iterator si)
+dom_opt_dom_walker::optimize_stmt (basic_block bb, gimple_stmt_iterator *si,
+				   bool *removed_p)
 {
   gimple *stmt, *old_stmt;
   bool may_optimize_p;
@@ -1959,7 +1998,7 @@ dom_opt_dom_walker::optimize_stmt (basic
   bool was_noreturn;
   edge retval = NULL;
 
-  old_stmt = stmt = gsi_stmt (si);
+  old_stmt = stmt = gsi_stmt (*si);
   was_noreturn = is_gimple_call (stmt) && gimple_call_noreturn_p (stmt);
 
   if (dump_file && (dump_flags & TDF_DETAILS))
@@ -1982,9 +2021,9 @@ dom_opt_dom_walker::optimize_stmt (basic
 
       /* Try to fold the statement making sure that STMT is kept
 	 up to date.  */
-      if (fold_stmt (&si))
+      if (fold_stmt (si))
 	{
-	  stmt = gsi_stmt (si);
+	  stmt = gsi_stmt (*si);
 	  gimple_set_modified (stmt, true);
 
 	  if (dump_file && (dump_flags & TDF_DETAILS))
@@ -2032,8 +2071,8 @@ dom_opt_dom_walker::optimize_stmt (basic
 	  if (callee
 	      && fndecl_built_in_p (callee, BUILT_IN_CONSTANT_P))
 	    {
-	      propagate_tree_value_into_stmt (&si, integer_zero_node);
-	      stmt = gsi_stmt (si);
+	      propagate_tree_value_into_stmt (si, integer_zero_node);
+	      stmt = gsi_stmt (*si);
 	    }
 	}
 
@@ -2089,9 +2128,9 @@ dom_opt_dom_walker::optimize_stmt (basic
 	}
 
       update_stmt_if_modified (stmt);
-      eliminate_redundant_computations (&si, m_const_and_copies,
+      eliminate_redundant_computations (si, m_const_and_copies,
 					m_avail_exprs_stack);
-      stmt = gsi_stmt (si);
+      stmt = gsi_stmt (*si);
 
       /* Perform simple redundant store elimination.  */
       if (gimple_assign_single_p (stmt)
@@ -2118,13 +2157,14 @@ dom_opt_dom_walker::optimize_stmt (basic
 	    {
 	      basic_block bb = gimple_bb (stmt);
 	      unlink_stmt_vdef (stmt);
-	      if (gsi_remove (&si, true))
+	      if (gsi_remove (si, true))
 		{
 		  bitmap_set_bit (need_eh_cleanup, bb->index);
 		  if (dump_file && (dump_flags & TDF_DETAILS))
 		    fprintf (dump_file, "  Flagged to clear EH edges.\n");
 		}
 	      release_defs (stmt);
+	      *removed_p = true;
 	      return retval;
 	    }
 	}
Index: gcc/testsuite/gcc.dg/torture/pr89595.c
===================================================================
--- gcc/testsuite/gcc.dg/torture/pr89595.c	(nonexistent)
+++ gcc/testsuite/gcc.dg/torture/pr89595.c	(working copy)
@@ -0,0 +1,39 @@
+/* { dg-do run } */
+/* { dg-additional-options "-fgimple" } */
+
+int __attribute__((noipa))
+__GIMPLE(startwith("dom")) bar(int cond, int val)
+{
+  int i;
+
+  if (0 != 0)
+    goto bb_6;
+  else
+    goto bb_2;
+
+bb_2:
+  if (cond_5(D) != 0)
+    goto bb_4;
+  else
+    goto bb_5;
+
+bb_4:
+  i_6 = val_2(D);
+  i_1 = val_2(D) > 0 ? i_6 : 0;
+
+bb_5:
+  i_3 = __PHI (bb_4: i_1, bb_2: 0);
+  return i_3;
+
+bb_6:
+  i_4 = 1;
+  i_9 = 2;
+  goto bb_2;
+}
+
+int main()
+{
+  if (bar (1, 1) != 1)
+    __builtin_abort ();
+  return 0;
+}

Re: A bug in vrp_meet?

[Richard Biener]

On Wed, Mar 6, 2019 at 11:05 AM Richard Biener
<richard.guenther@gmail.com> wrote:
>
> On Tue, Mar 5, 2019 at 10:36 PM Jeff Law <law@redhat.com> wrote:
> >
> > On 3/5/19 7:44 AM, Richard Biener wrote:
> >
> > > So fixing it properly with also re-optimize_stmt those stmts so we'd CSE
> > > the MAX_EXPR introduced by folding makes it somewhat ugly.
> > >
> > > Bootstrapped on x86_64-unknown-linux-gnu, testing in progress.
> > >
> > > Any ideas how to make it less so?  I can split out making optimize_stmt
> > > take a gsi * btw, in case that's a more obvious change and it makes the
> > > patch a little smaller.
> > >
> > > Richard.
> > >
> > > 2019-03-05  Richard Biener  <rguenther@suse.de>
> > >
> > >         PR tree-optimization/89595
> > >         * tree-ssa-dom.c (dom_opt_dom_walker::optimize_stmt): Take
> > >         stmt iterator as reference, take boolean output parameter to
> > >         indicate whether the stmt was removed and thus the iterator
> > >         already advanced.
> > >         (dom_opt_dom_walker::before_dom_children): Re-iterate over
> > >         stmts created by folding.
> > >
> > >         * gcc.dg/torture/pr89595.c: New testcase.
> > >
> >
> > Well, all the real logic changs are in the before_dom_children method.
> > The bits in optimize_stmt are trivial enough to effectively ignore.
> >
> > I don't see a better way to discover and process statements that are
> > created in the bowels of fold_stmt.
>
> I'm not entirely happy so I created the following alternative which
> is a bit larger and slower due to the pre-pass clearing the visited flag
> but is IMHO easier to follow.  I guess there's plenty of TLC opportunity
> here but then I also hope to retire the VN parts of DOM in favor
> of the non-iterating RPO-VN code...
>
> So - I'd lean to this variant even though it has the extra loop over stmts,
> would you agree?

I have now applied this variant.

Richard.

> Bootstrap / regtest running on x86_64-unknown-linux-gnu.
>
> Richard.
>
> 2019-03-06  Richard Biener  <rguenther@suse.de>
>
>         PR tree-optimization/89595
>         * tree-ssa-dom.c (dom_opt_dom_walker::optimize_stmt): Take
>         stmt iterator as reference, take boolean output parameter to
>         indicate whether the stmt was removed and thus the iterator
>         already advanced.
>         (dom_opt_dom_walker::before_dom_children): Re-iterate over
>         stmts created by folding.
>
>         * gcc.dg/torture/pr89595.c: New testcase.

Re: A bug in vrp_meet?

[Eric Botcazou]

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

> I have now applied this variant.

You backported it onto the 8 branch on Friday:

2019-05-03  Richard Biener  <rguenther@suse.de>

        Backport from mainline
[...]
        2019-03-07  Richard Biener  <rguenther@suse.de>

        PR tree-optimization/89595
        * tree-ssa-dom.c (dom_opt_dom_walker::optimize_stmt): Take
        stmt iterator as reference, take boolean output parameter to
        indicate whether the stmt was removed and thus the iterator
        already advanced.
        (dom_opt_dom_walker::before_dom_children): Re-iterate over
        stmts created by folding.

and this introduced a regression for the attached Ada testcase at -O:

Program received signal SIGSEGV, Segmentation fault.
0x000000000102173c in set_value_range (
    vr=0x17747a0 <vr_values::get_value_range(tree_node 
const*)::vr_const_varying>, t=VR_RANGE, min=0x7ffff6c3df78, max=<optimized 
out>, equiv=0x0)
    at /home/eric/svn/gcc-8-branch/gcc/tree-vrp.c:298
298       vr->type = t;

on x86-64 at least.  Mainline and 9 branch are not affected.

-- 
Eric Botcazou

[-- Attachment #2: opt78.ads --]
[-- Type: text/x-adasrc, Size: 242 bytes --]

package Opt78 is

   subtype Reasonable is Integer range 1..10;

   type UC (D: Reasonable := 2) is record
      S: String (1 .. D) := "Hi";
   end record;

   type AUC is access all UC;

   procedure Proc (P : UC; Msg : String);

end Opt78;

[-- Attachment #3: opt78.adb --]
[-- Type: text/x-adasrc, Size: 287 bytes --]

-- { dg-do compile }
-- { dg-options "-O" }

package body Opt78 is

   procedure Proc (P : UC; Msg : String) is
      Default : UC := (1, "!");
   begin
      if P = Default then
         raise Program_Error;
      else
         raise Constraint_Error;
      end if;
   end;

end Opt78;

Re: A bug in vrp_meet?

[Richard Biener]

On Sun, May 5, 2019 at 11:09 PM Eric Botcazou <ebotcazou@adacore.com> wrote:
>
> > I have now applied this variant.
>
> You backported it onto the 8 branch on Friday:
>
> 2019-05-03  Richard Biener  <rguenther@suse.de>
>
>         Backport from mainline
> [...]
>         2019-03-07  Richard Biener  <rguenther@suse.de>
>
>         PR tree-optimization/89595
>         * tree-ssa-dom.c (dom_opt_dom_walker::optimize_stmt): Take
>         stmt iterator as reference, take boolean output parameter to
>         indicate whether the stmt was removed and thus the iterator
>         already advanced.
>         (dom_opt_dom_walker::before_dom_children): Re-iterate over
>         stmts created by folding.
>
> and this introduced a regression for the attached Ada testcase at -O:
>
> Program received signal SIGSEGV, Segmentation fault.
> 0x000000000102173c in set_value_range (
>     vr=0x17747a0 <vr_values::get_value_range(tree_node
> const*)::vr_const_varying>, t=VR_RANGE, min=0x7ffff6c3df78, max=<optimized
> out>, equiv=0x0)
>     at /home/eric/svn/gcc-8-branch/gcc/tree-vrp.c:298
> 298       vr->type = t;
>
> on x86-64 at least.  Mainline and 9 branch are not affected.

It looks like backporting r269597 might fix it though reverting that on trunk
doesn't make the testcase fail there.

Richard.

> --
> Eric Botcazou

Re: A bug in vrp_meet?

[Jeff Law]

On 3/6/19 3:05 AM, Richard Biener wrote:
> On Tue, Mar 5, 2019 at 10:36 PM Jeff Law <law@redhat.com> wrote:
>>
>> On 3/5/19 7:44 AM, Richard Biener wrote:
>>
>>> So fixing it properly with also re-optimize_stmt those stmts so we'd CSE
>>> the MAX_EXPR introduced by folding makes it somewhat ugly.
>>>
>>> Bootstrapped on x86_64-unknown-linux-gnu, testing in progress.
>>>
>>> Any ideas how to make it less so?  I can split out making optimize_stmt
>>> take a gsi * btw, in case that's a more obvious change and it makes the
>>> patch a little smaller.
>>>
>>> Richard.
>>>
>>> 2019-03-05  Richard Biener  <rguenther@suse.de>
>>>
>>>         PR tree-optimization/89595
>>>         * tree-ssa-dom.c (dom_opt_dom_walker::optimize_stmt): Take
>>>         stmt iterator as reference, take boolean output parameter to
>>>         indicate whether the stmt was removed and thus the iterator
>>>         already advanced.
>>>         (dom_opt_dom_walker::before_dom_children): Re-iterate over
>>>         stmts created by folding.
>>>
>>>         * gcc.dg/torture/pr89595.c: New testcase.
>>>
>>
>> Well, all the real logic changs are in the before_dom_children method.
>> The bits in optimize_stmt are trivial enough to effectively ignore.
>>
>> I don't see a better way to discover and process statements that are
>> created in the bowels of fold_stmt.
> 
> I'm not entirely happy so I created the following alternative which
> is a bit larger and slower due to the pre-pass clearing the visited flag
> but is IMHO easier to follow.  I guess there's plenty of TLC opportunity
> here but then I also hope to retire the VN parts of DOM in favor
> of the non-iterating RPO-VN code...
> 
> So - I'd lean to this variant even though it has the extra loop over stmts,
> would you agree?
> 
> Bootstrap / regtest running on x86_64-unknown-linux-gnu.
> 
> Richard.
> 
> 2019-03-06  Richard Biener  <rguenther@suse.de>
> 
>         PR tree-optimization/89595
>         * tree-ssa-dom.c (dom_opt_dom_walker::optimize_stmt): Take
>         stmt iterator as reference, take boolean output parameter to
>         indicate whether the stmt was removed and thus the iterator
>         already advanced.
>         (dom_opt_dom_walker::before_dom_children): Re-iterate over
>         stmts created by folding.
> 
>         * gcc.dg/torture/pr89595.c: New testcase.
This one is easier to follow from a logic standpoint.  I don't think the
gimple_set_visited bits are going to be terribly expensive in general.

Is that flag in a known state for new statements?  I'm guessing it's
cleared by some structure-sized memset as we create the raw statement?

Might be worth clarifying that in the comments in gimple.h.

jeff

Re: A bug in vrp_meet?

[Richard Biener]

On Tue, Mar 19, 2019 at 8:53 PM Jeff Law <law@redhat.com> wrote:
>
> On 3/6/19 3:05 AM, Richard Biener wrote:
> > On Tue, Mar 5, 2019 at 10:36 PM Jeff Law <law@redhat.com> wrote:
> >>
> >> On 3/5/19 7:44 AM, Richard Biener wrote:
> >>
> >>> So fixing it properly with also re-optimize_stmt those stmts so we'd CSE
> >>> the MAX_EXPR introduced by folding makes it somewhat ugly.
> >>>
> >>> Bootstrapped on x86_64-unknown-linux-gnu, testing in progress.
> >>>
> >>> Any ideas how to make it less so?  I can split out making optimize_stmt
> >>> take a gsi * btw, in case that's a more obvious change and it makes the
> >>> patch a little smaller.
> >>>
> >>> Richard.
> >>>
> >>> 2019-03-05  Richard Biener  <rguenther@suse.de>
> >>>
> >>>         PR tree-optimization/89595
> >>>         * tree-ssa-dom.c (dom_opt_dom_walker::optimize_stmt): Take
> >>>         stmt iterator as reference, take boolean output parameter to
> >>>         indicate whether the stmt was removed and thus the iterator
> >>>         already advanced.
> >>>         (dom_opt_dom_walker::before_dom_children): Re-iterate over
> >>>         stmts created by folding.
> >>>
> >>>         * gcc.dg/torture/pr89595.c: New testcase.
> >>>
> >>
> >> Well, all the real logic changs are in the before_dom_children method.
> >> The bits in optimize_stmt are trivial enough to effectively ignore.
> >>
> >> I don't see a better way to discover and process statements that are
> >> created in the bowels of fold_stmt.
> >
> > I'm not entirely happy so I created the following alternative which
> > is a bit larger and slower due to the pre-pass clearing the visited flag
> > but is IMHO easier to follow.  I guess there's plenty of TLC opportunity
> > here but then I also hope to retire the VN parts of DOM in favor
> > of the non-iterating RPO-VN code...
> >
> > So - I'd lean to this variant even though it has the extra loop over stmts,
> > would you agree?
> >
> > Bootstrap / regtest running on x86_64-unknown-linux-gnu.
> >
> > Richard.
> >
> > 2019-03-06  Richard Biener  <rguenther@suse.de>
> >
> >         PR tree-optimization/89595
> >         * tree-ssa-dom.c (dom_opt_dom_walker::optimize_stmt): Take
> >         stmt iterator as reference, take boolean output parameter to
> >         indicate whether the stmt was removed and thus the iterator
> >         already advanced.
> >         (dom_opt_dom_walker::before_dom_children): Re-iterate over
> >         stmts created by folding.
> >
> >         * gcc.dg/torture/pr89595.c: New testcase.
> This one is easier to follow from a logic standpoint.  I don't think the
> gimple_set_visited bits are going to be terribly expensive in general.
>
> Is that flag in a known state for new statements?  I'm guessing it's
> cleared by some structure-sized memset as we create the raw statement?

Yes, it's of course not documented that way but IMHo the only reasonable
state.

> Might be worth clarifying that in the comments in gimple.h.
>
> jeff
>

Re: A bug in vrp_meet?

[Jeff Law]

On 3/4/19 4:45 AM, Richard Biener wrote:
> On Fri, Mar 1, 2019 at 10:02 PM Qing Zhao <qing.zhao@oracle.com> wrote:
>>
>>
>> On Mar 1, 2019, at 1:25 PM, Richard Biener <richard.guenther@gmail.com> wrote:
>>
>> On March 1, 2019 6:49:20 PM GMT+01:00, Qing Zhao <qing.zhao@oracle.com> wrote:
>>
>> Jeff,
>>
>> thanks a lot for the reply.
>>
>> this is really helpful.
>>
>> I double checked the dumped intermediate file for pass “dom3", and
>> located the following for _152:
>>
>> ****BEFORE the pass “dom3”, there is no _152, the corresponding Block
>> looks like:
>>
>> <bb 4> [local count: 12992277]:
>> _98 = (int) ufcMSR_52(D);
>> k_105 = (sword) ufcMSR_52(D);
>> i_49 = _98 > 0 ? k_105 : 0;
>>
>> ***During the pass “doms”,  _152 is generated as following:
>>
>> Optimizing block #4
>> ….
>> Visiting statement:
>> i_49 = _98 > 0 ? k_105 : 0;
>> Meeting
>> [0, 65535]
>> and
>> [0, 0]
>> to
>> [0, 65535]
>> Intersecting
>> [0, 65535]
>> and
>> [0, 65535]
>> to
>> [0, 65535]
>> Optimizing statement i_49 = _98 > 0 ? k_105 : 0;
>> Replaced 'k_105' with variable '_98'
>> gimple_simplified to _152 = MAX_EXPR <_98, 0>;
>> i_49 = _152;
>> Folded to: i_49 = _152;
>> LKUP STMT i_49 = _152
>> ==== ASGN i_49 = _152
>>
>> then bb 4 becomes:
>>
>> <bb 4> [local count: 12992277]:
>> _98 = (int) ufcMSR_52(D);
>> k_105 = _98;
>> _152 = MAX_EXPR <_98, 0>;
>> i_49 = _152;
>>
>> and all the i_49 are replaced with _152.
>>
>> However, the value range info for _152 doesnot reflect the one for
>> i_49, it keeps as UNDEFINED.
>>
>> is this the root problem?
>>
>>
>> It looks like DOM fails to visit stmts generated by simplification. Can you open a bug report with a testcase?
>>
>>
>> The problem is, It took me quite some time in order to come up with a small and independent testcase for this problem,
>> a little bit change made the error disappear.
>>
>> do you have any suggestion on this?  or can you give me some hint on how to fix this in DOM?  then I can try the fix on my side?
> 
> I remember running into similar issues in the past where I tried to
> extract temporary nonnull ranges from divisions.
> I have there
> 
> @@ -1436,11 +1436,16 @@ dom_opt_dom_walker::before_dom_children
>    m_avail_exprs_stack->pop_to_marker ();
> 
>    edge taken_edge = NULL;
> -  for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
> -    {
> -      evrp_range_analyzer.record_ranges_from_stmt (gsi_stmt (gsi), false);
> -      taken_edge = this->optimize_stmt (bb, gsi);
> -    }
> +  gsi = gsi_start_bb (bb);
> +  if (!gsi_end_p (gsi))
> +    while (1)
> +      {
> +       evrp_range_analyzer.record_def_ranges_from_stmt (gsi_stmt (gsi), false);
> +       taken_edge = this->optimize_stmt (bb, &gsi);
> +       if (gsi_end_p (gsi))
> +         break;
> +       evrp_range_analyzer.record_use_ranges_from_stmt (gsi_stmt (gsi));
> +      }
> 
>    /* Now prepare to process dominated blocks.  */
>    record_edge_info (bb);
> 
> OTOH the issue in your case is that fold emits new stmts before gsi but the
> above loop will never look at them.  See tree-ssa-forwprop.c for code how
> to deal with this (setting a pass-local flag on stmts visited and walking back
> to unvisited, newly inserted ones).  The fold_stmt interface could in theory
> also be extended to insert new stmts on a sequence passed to it so the
> caller would be responsible for inserting them into the IL and could then
> more easily revisit them (but that's a bigger task).
Grr. This all sounds very familiar.  I know I've tracked down a bug of
this  nature before and would like to review how it was fixed in light
of your comment about tree-ssa-forwprop's handling of the same
situation.  I just can't seem to find it..  Ugh.

I assume you're referring to the PLF stuff?


Jeff

Re: A bug in vrp_meet?

[Jeff Law]

On 3/1/19 10:49 AM, Qing Zhao wrote:
> Jeff,
> 
> thanks a lot for the reply.
> 
> this is really helpful.
> 
> I double checked the dumped intermediate file for pass “dom3", and
> located the following for _152:
> 
> ****BEFORE the pass “dom3”, there is no _152, the corresponding Block
> looks like:
> 
>   <bb 4> [local count: 12992277]:
>   _98 = (int) ufcMSR_52(D);
>   k_105 = (sword) ufcMSR_52(D);
>   i_49 = _98 > 0 ? k_105 : 0;
> 
> ***During the pass “doms”,  _152 is generated as following:
> 
> Optimizing block #4
> ….
> Visiting statement:
> i_49 = _98 > 0 ? k_105 : 0;
> Meeting
>   [0, 65535]
> and
>   [0, 0]
> to
>   [0, 65535]
> Intersecting
>   [0, 65535]
> and
>   [0, 65535]
> to
>   [0, 65535]
> Optimizing statement i_49 = _98 > 0 ? k_105 : 0;
>   Replaced 'k_105' with variable '_98'
> gimple_simplified to _152 = MAX_EXPR <_98, 0>;
> i_49 = _152;
>   Folded to: i_49 = _152;
> LKUP STMT i_49 = _152
> ==== ASGN i_49 = _152
> 
> then bb 4 becomes:
> 
>   <bb 4> [local count: 12992277]:
>   _98 = (int) ufcMSR_52(D);
>   k_105 = _98;
>   _152 = MAX_EXPR <_98, 0>;
>   i_49 = _152;
> 
> and all the i_49 are replaced with _152. 
> 
> However, the value range info for _152 doesnot reflect the one for i_49,
> it keeps as UNDEFINED. 
> 
> is this the root problem?  
Yes, I think so.  It's like we didn't record anything for _152 when we
simplified the RHS to a MAX_EXPR.

Jeff