undefined behavior in value_range::equiv_add()?

undefined behavior in value_range::equiv_add()?

[Aldy Hernandez]

As per the API, and the original documentation to value_range, 
VR_UNDEFINED and VR_VARYING should never have equivalences.  However, 
equiv_add is tacking on equivalences blindly, and there are various 
regressions that happen if I fix this oversight.

void
value_range::equiv_add (const_tree var,
			const value_range *var_vr,
			bitmap_obstack *obstack)
{
   if (!m_equiv)
     m_equiv = BITMAP_ALLOC (obstack);
   unsigned ver = SSA_NAME_VERSION (var);
   bitmap_set_bit (m_equiv, ver);
   if (var_vr && var_vr->m_equiv)
     bitmap_ior_into (m_equiv, var_vr->m_equiv);
}

Is this a bug in the documentation / API, or is equiv_add incorrect and 
we should fix the fall-out elsewhere?

Thanks.
Aldy

Re: undefined behavior in value_range::equiv_add()?

[Richard Biener]

On Wed, May 29, 2019 at 2:18 PM Aldy Hernandez <aldyh@redhat.com> wrote:
>
> As per the API, and the original documentation to value_range,
> VR_UNDEFINED and VR_VARYING should never have equivalences.  However,
> equiv_add is tacking on equivalences blindly, and there are various
> regressions that happen if I fix this oversight.
>
> void
> value_range::equiv_add (const_tree var,
>                         const value_range *var_vr,
>                         bitmap_obstack *obstack)
> {
>    if (!m_equiv)
>      m_equiv = BITMAP_ALLOC (obstack);
>    unsigned ver = SSA_NAME_VERSION (var);
>    bitmap_set_bit (m_equiv, ver);
>    if (var_vr && var_vr->m_equiv)
>      bitmap_ior_into (m_equiv, var_vr->m_equiv);
> }
>
> Is this a bug in the documentation / API, or is equiv_add incorrect and
> we should fix the fall-out elsewhere?

I think this must have been crept in during the classification.  If you
go back to say GCC 7 you shouldn't see value-ranges with
UNDEFINED/VARYING state in the lattice that have equivalences.

It may not be easy to avoid with the new classy interface but we're
certainly not tacking on them "blindly".  At least we're not supposed
to.  As usual the intermediate state might be "broken" but
intermediateness is not sth the new class "likes".

Richard.

>
> Thanks.
> Aldy

Re: undefined behavior in value_range::equiv_add()?

[Aldy Hernandez]

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

On 5/29/19 9:24 AM, Richard Biener wrote:
> On Wed, May 29, 2019 at 2:18 PM Aldy Hernandez <aldyh@redhat.com> wrote:
>>
>> As per the API, and the original documentation to value_range,
>> VR_UNDEFINED and VR_VARYING should never have equivalences.  However,
>> equiv_add is tacking on equivalences blindly, and there are various
>> regressions that happen if I fix this oversight.
>>
>> void
>> value_range::equiv_add (const_tree var,
>>                          const value_range *var_vr,
>>                          bitmap_obstack *obstack)
>> {
>>     if (!m_equiv)
>>       m_equiv = BITMAP_ALLOC (obstack);
>>     unsigned ver = SSA_NAME_VERSION (var);
>>     bitmap_set_bit (m_equiv, ver);
>>     if (var_vr && var_vr->m_equiv)
>>       bitmap_ior_into (m_equiv, var_vr->m_equiv);
>> }
>>
>> Is this a bug in the documentation / API, or is equiv_add incorrect and
>> we should fix the fall-out elsewhere?
> 
> I think this must have been crept in during the classification.  If you
> go back to say GCC 7 you shouldn't see value-ranges with
> UNDEFINED/VARYING state in the lattice that have equivalences.
> 
> It may not be easy to avoid with the new classy interface but we're
> certainly not tacking on them "blindly".  At least we're not supposed
> to.  As usual the intermediate state might be "broken" but
> intermediateness is not sth the new class "likes".

It looks like extract_range_from_stmt (by virtue of 
vrp_visit_assignment_or_call and then extract_range_from_ssa_name) 
returns one of these intermediate ranges.  It would seem to me that an 
outward looking API method like vr_values::extract_range_from_stmt 
shouldn't be returning inconsistent ranges.  Or are there no guarantees 
for value_ranges from within all of vr_values?

Perhaps I should give a little background.  As part of your 
value_range_base re-factoring last year, you mentioned that you didn't 
split out intersect like you did union because of time or oversight.  I 
have code to implement intersect (attached), for which I've noticed that 
I must leave equivalences intact, even when transitioning to VR_UNDEFINED:

[from the attached patch]
+  /* If THIS is varying we want to pick up equivalences from OTHER.
+     Just special-case this here rather than trying to fixup after the
+     fact.  */
+  if (this->varying_p ())
+    this->deep_copy (other);
+  else if (this->undefined_p ())
+    /* ?? Leave any equivalences already present in an undefined.
+       This is technically not allowed, but we may get an in-flight
+       value_range in an intermediate state.  */
+    ;

What is happening is that in evrp's record_ranges_from_stmt, we call 
extract_range_from_stmt which returns an inconsistent VR_UNDEFINED with 
an equivalence, which is then fed to update_value_range() and finally 
value_range::intersect.  The VR_UNDEFINED equivalence must not be 
removed in the intersect, because update_value_range() will get confused 
as to whether this is a new VR or not (because VR_UNDEFINED with no 
equivalences is not the same as VR_UNDEFINED with equivalences-- see 
"is_new" in update_value_range).

I'd rather not special case VR_UNDEFINED in the intersect code as above, 
but if you think extract_range_from_stmt() can return an "intermediate" 
range, and thus intersect must handle them too, then I suppose we could 
leave this in.

What do you suggest?

Oh yeah, is the attached patch OK for trunk?  I can post in a separate 
thread if you prefer, but thought it relevant here :).

Aldy


[-- Attachment #2: curr.patch --]
[-- Type: text/x-patch, Size: 8734 bytes --]

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 9f194540327..9494520ba33 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,19 @@
+2019-05-29  Aldy Hernandez  <aldyh@redhat.com>
+
+	* tree-vrp.h (value_range_base::intersect): New.
+	(value_range::intersect_helper): Move from here...
+	(value_range_base::intersect_helper): ...to here.
+	* tree-vrp.c (value_range::intersect_helper): Rename to...
+	(value_range_base::intersect_helper): ...this, and rewrite to
+	return a value instead of modifying THIS in place.
+	Also, move equivalence handling...
+	(value_range::intersect): ...here, while calling intersect_helper.
+	* gimple-fold.c (size_must_be_zero_p): Use value_range_base when
+	calling intersect.
+	* gimple-ssa-evrp-analyze.c (ecord_ranges_from_incoming_edge):
+	Same.
+	* vr-values.c (vrp_evaluate_conditional_warnv_with_ops): Same.
+
 2019-05-29  Aldy Hernandez  <aldyh@redhat.com>
 	* tree-vrp.h (value_range_base::non_zero_p): New.
 	* tree-vrp.c (range_is_null): Remove.
diff --git a/gcc/gimple-fold.c b/gcc/gimple-fold.c
index b3e931744f8..8b8331eb555 100644
--- a/gcc/gimple-fold.c
+++ b/gcc/gimple-fold.c
@@ -684,10 +684,10 @@ size_must_be_zero_p (tree size)
   /* Compute the value of SSIZE_MAX, the largest positive value that
      can be stored in ssize_t, the signed counterpart of size_t.  */
   wide_int ssize_max = wi::lshift (wi::one (prec), prec - 1) - 1;
-  value_range valid_range (VR_RANGE,
-			   build_int_cst (type, 0),
-			   wide_int_to_tree (type, ssize_max));
-  value_range vr;
+  value_range_base valid_range (VR_RANGE,
+				build_int_cst (type, 0),
+				wide_int_to_tree (type, ssize_max));
+  value_range_base vr;
   get_range_info (size, vr);
   vr.intersect (&valid_range);
   return vr.zero_p ();
diff --git a/gcc/gimple-ssa-evrp-analyze.c b/gcc/gimple-ssa-evrp-analyze.c
index bb4e2d6e798..4c68af847e1 100644
--- a/gcc/gimple-ssa-evrp-analyze.c
+++ b/gcc/gimple-ssa-evrp-analyze.c
@@ -210,9 +210,10 @@ evrp_range_analyzer::record_ranges_from_incoming_edge (basic_block bb)
 	         getting first [64, +INF] and then ~[0, 0] from
 		 conditions like (s & 0x3cc0) == 0).  */
 	      value_range *old_vr = get_value_range (vrs[i].first);
-	      value_range tem (old_vr->kind (), old_vr->min (), old_vr->max ());
+	      value_range_base tem (old_vr->kind (), old_vr->min (),
+				    old_vr->max ());
 	      tem.intersect (vrs[i].second);
-	      if (tem.equal_p (*old_vr, /*ignore_equivs=*/true))
+	      if (tem.equal_p (*old_vr))
 		continue;
 	      push_value_range (vrs[i].first, vrs[i].second);
 	      if (is_fallthru
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index d65dbcfaeee..2a5103c38aa 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -6033,30 +6033,26 @@ intersect_ranges (enum value_range_kind *vr0type,
 }
 
 
-/* Intersect the two value-ranges *VR0 and *VR1 and store the result
-   in *VR0.  This may not be the smallest possible such range.  */
+/* Helper for the intersection operation for value ranges.  Given two
+   value ranges VR0 and VR1, return the intersection of the two
+   ranges.  This may not be the smallest possible such range.  */
 
-void
-value_range::intersect_helper (value_range *vr0, const value_range *vr1)
+value_range_base
+value_range_base::intersect_helper (const value_range_base *vr0,
+				    const value_range_base *vr1)
 {
   /* If either range is VR_VARYING the other one wins.  */
   if (vr1->varying_p ())
-    return;
+    return *vr0;
   if (vr0->varying_p ())
-    {
-      vr0->deep_copy (vr1);
-      return;
-    }
+    return *vr1;
 
   /* When either range is VR_UNDEFINED the resulting range is
      VR_UNDEFINED, too.  */
   if (vr0->undefined_p ())
-    return;
+    return *vr0;
   if (vr1->undefined_p ())
-    {
-      vr0->set_undefined ();
-      return;
-    }
+    return *vr1;
 
   value_range_kind vr0type = vr0->kind ();
   tree vr0min = vr0->min ();
@@ -6066,28 +6062,34 @@ value_range::intersect_helper (value_range *vr0, const value_range *vr1)
   /* Make sure to canonicalize the result though as the inversion of a
      VR_RANGE can still be a VR_RANGE.  Work on a temporary so we can
      fall back to vr0 when this turns things to varying.  */
-  value_range tem;
+  value_range_base tem;
   tem.set_and_canonicalize (vr0type, vr0min, vr0max);
   /* If that failed, use the saved original VR0.  */
   if (tem.varying_p ())
-    return;
-  vr0->update (tem.kind (), tem.min (), tem.max ());
+    return *vr0;
 
-  /* If the result is VR_UNDEFINED there is no need to mess with
-     the equivalencies.  */
-  if (vr0->undefined_p ())
-    return;
+  return tem;
+}
+
+void
+value_range_base::intersect (const value_range_base *other)
+{
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "Intersecting\n  ");
+      dump_value_range (dump_file, this);
+      fprintf (dump_file, "\nand\n  ");
+      dump_value_range (dump_file, other);
+      fprintf (dump_file, "\n");
+    }
 
-  /* The resulting set of equivalences for range intersection is the union of
-     the two sets.  */
-  if (vr0->m_equiv && vr1->m_equiv && vr0->m_equiv != vr1->m_equiv)
-    bitmap_ior_into (vr0->m_equiv, vr1->m_equiv);
-  else if (vr1->m_equiv && !vr0->m_equiv)
+  *this = intersect_helper (this, other);
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
     {
-      /* All equivalence bitmaps are allocated from the same obstack.  So
-	 we can use the obstack associated with VR to allocate vr0->equiv.  */
-      vr0->m_equiv = BITMAP_ALLOC (vr1->m_equiv->obstack);
-      bitmap_copy (m_equiv, vr1->m_equiv);
+      fprintf (dump_file, "to\n  ");
+      dump_value_range (dump_file, this);
+      fprintf (dump_file, "\n");
     }
 }
 
@@ -6102,7 +6104,41 @@ value_range::intersect (const value_range *other)
       dump_value_range (dump_file, other);
       fprintf (dump_file, "\n");
     }
-  intersect_helper (this, other);
+
+  /* If THIS is varying we want to pick up equivalences from OTHER.
+     Just special-case this here rather than trying to fixup after the
+     fact.  */
+  if (this->varying_p ())
+    this->deep_copy (other);
+  else if (this->undefined_p ())
+    /* ?? Leave any equivalences already present in an undefined.
+       This is technically not allowed, but we may get an in-flight
+       value_range in an intermediate state.  */
+    ;
+  else
+    {
+      value_range_base tem = intersect_helper (this, other);
+      this->update (tem.kind (), tem.min (), tem.max ());
+
+      /* If the result is VR_UNDEFINED there is no need to mess with
+	 equivalencies.  */
+      if (!undefined_p ())
+	{
+	  /* The resulting set of equivalences for range intersection
+	     is the union of the two sets.  */
+	  if (m_equiv && other->m_equiv && m_equiv != other->m_equiv)
+	    bitmap_ior_into (m_equiv, other->m_equiv);
+	  else if (other->m_equiv && !m_equiv)
+	    {
+	      /* All equivalence bitmaps are allocated from the same
+		 obstack.  So we can use the obstack associated with
+		 VR to allocate this->m_equiv.  */
+	      m_equiv = BITMAP_ALLOC (other->m_equiv->obstack);
+	      bitmap_copy (m_equiv, other->m_equiv);
+	    }
+	}
+    }
+
   if (dump_file && (dump_flags & TDF_DETAILS))
     {
       fprintf (dump_file, "to\n  ");
diff --git a/gcc/tree-vrp.h b/gcc/tree-vrp.h
index 9ae5e9514c6..945abe992d3 100644
--- a/gcc/tree-vrp.h
+++ b/gcc/tree-vrp.h
@@ -62,6 +62,7 @@ public:
   void set_undefined ();
 
   void union_ (const value_range_base *);
+  void intersect (const value_range_base *);
 
   bool operator== (const value_range_base &) const /* = delete */;
   bool operator!= (const value_range_base &) const /* = delete */;
@@ -80,6 +81,8 @@ protected:
   void check ();
   static value_range_base union_helper (const value_range_base *,
 					const value_range_base *);
+  static value_range_base intersect_helper (const value_range_base *,
+					    const value_range_base *);
 
   enum value_range_kind m_kind;
 
@@ -146,7 +149,6 @@ class GTY((user)) value_range : public value_range_base
   /* Deep-copies bitmap argument.  */
   void set_equiv (bitmap);
   void check ();
-  void intersect_helper (value_range *, const value_range *);
 
   /* Set of SSA names whose value ranges are equivalent to this one.
      This set is only valid when TYPE is VR_RANGE or VR_ANTI_RANGE.  */
diff --git a/gcc/vr-values.c b/gcc/vr-values.c
index 0e10aca92bb..41fd9cc7712 100644
--- a/gcc/vr-values.c
+++ b/gcc/vr-values.c
@@ -2343,7 +2343,7 @@ vr_values::vrp_evaluate_conditional_warnv_with_ops (enum tree_code code,
 	}
       else
 	{
-	  value_range vro, vri;
+	  value_range_base vro, vri;
 	  if (code == GT_EXPR || code == GE_EXPR)
 	    {
 	      vro.set (VR_ANTI_RANGE, TYPE_MIN_VALUE (TREE_TYPE (op0)), x);

Re: undefined behavior in value_range::equiv_add()?

[Jeff Law]

On 5/29/19 9:58 AM, Aldy Hernandez wrote:
> On 5/29/19 9:24 AM, Richard Biener wrote:
>> On Wed, May 29, 2019 at 2:18 PM Aldy Hernandez <aldyh@redhat.com> wrote:
>>>
>>> As per the API, and the original documentation to value_range,
>>> VR_UNDEFINED and VR_VARYING should never have equivalences.  However,
>>> equiv_add is tacking on equivalences blindly, and there are various
>>> regressions that happen if I fix this oversight.
>>>
>>> void
>>> value_range::equiv_add (const_tree var,
>>>                          const value_range *var_vr,
>>>                          bitmap_obstack *obstack)
>>> {
>>>     if (!m_equiv)
>>>       m_equiv = BITMAP_ALLOC (obstack);
>>>     unsigned ver = SSA_NAME_VERSION (var);
>>>     bitmap_set_bit (m_equiv, ver);
>>>     if (var_vr && var_vr->m_equiv)
>>>       bitmap_ior_into (m_equiv, var_vr->m_equiv);
>>> }
>>>
>>> Is this a bug in the documentation / API, or is equiv_add incorrect and
>>> we should fix the fall-out elsewhere?
>>
>> I think this must have been crept in during the classification.  If you
>> go back to say GCC 7 you shouldn't see value-ranges with
>> UNDEFINED/VARYING state in the lattice that have equivalences.
>>
>> It may not be easy to avoid with the new classy interface but we're
>> certainly not tacking on them "blindly".  At least we're not supposed
>> to.  As usual the intermediate state might be "broken" but
>> intermediateness is not sth the new class "likes".
> 
> It looks like extract_range_from_stmt (by virtue of
> vrp_visit_assignment_or_call and then extract_range_from_ssa_name)
> returns one of these intermediate ranges.  It would seem to me that an
> outward looking API method like vr_values::extract_range_from_stmt
> shouldn't be returning inconsistent ranges.  Or are there no guarantees
> for value_ranges from within all of vr_values?
ISTM that if we have an implementation constraint that says a VR_VARYING
or VR_UNDEFINED range can't have equivalences, then we need to honor
that at the minimum for anything returned by an external API.  Returning
an inconsistent state is bad.  I'd even state that we should try damn
hard to avoid it in internal APIs as well.

> 
> Perhaps I should give a little background.  As part of your
> value_range_base re-factoring last year, you mentioned that you didn't
> split out intersect like you did union because of time or oversight.  I
> have code to implement intersect (attached), for which I've noticed that
> I must leave equivalences intact, even when transitioning to VR_UNDEFINED:
> 
> [from the attached patch]
> +  /* If THIS is varying we want to pick up equivalences from OTHER.
> +     Just special-case this here rather than trying to fixup after the
> +     fact.  */
> +  if (this->varying_p ())
> +    this->deep_copy (other);
> +  else if (this->undefined_p ())
> +    /* ?? Leave any equivalences already present in an undefined.
> +       This is technically not allowed, but we may get an in-flight
> +       value_range in an intermediate state.  */
Where/when does this happen?

> +    ;
> 
> What is happening is that in evrp's record_ranges_from_stmt, we call
> extract_range_from_stmt which returns an inconsistent VR_UNDEFINED with
> an equivalence, which is then fed to update_value_range() and finally
> value_range::intersect.  The VR_UNDEFINED equivalence must not be
> removed in the intersect, because update_value_range() will get confused
> as to whether this is a new VR or not (because VR_UNDEFINED with no
> equivalences is not the same as VR_UNDEFINED with equivalences-- see
> "is_new" in update_value_range).
Ugh.  I hate some of the gyrations we have to do for update_value_range.
 Regardless I tend to think the problem is in the inconsistent state we
get back from extract_range_from_stmt.

Jeff

Re: undefined behavior in value_range::equiv_add()?

[Aldy Hernandez]

On 5/29/19 12:12 PM, Jeff Law wrote:
> On 5/29/19 9:58 AM, Aldy Hernandez wrote:
>> On 5/29/19 9:24 AM, Richard Biener wrote:
>>> On Wed, May 29, 2019 at 2:18 PM Aldy Hernandez <aldyh@redhat.com> wrote:
>>>>
>>>> As per the API, and the original documentation to value_range,
>>>> VR_UNDEFINED and VR_VARYING should never have equivalences.  However,
>>>> equiv_add is tacking on equivalences blindly, and there are various
>>>> regressions that happen if I fix this oversight.
>>>>
>>>> void
>>>> value_range::equiv_add (const_tree var,
>>>>                           const value_range *var_vr,
>>>>                           bitmap_obstack *obstack)
>>>> {
>>>>      if (!m_equiv)
>>>>        m_equiv = BITMAP_ALLOC (obstack);
>>>>      unsigned ver = SSA_NAME_VERSION (var);
>>>>      bitmap_set_bit (m_equiv, ver);
>>>>      if (var_vr && var_vr->m_equiv)
>>>>        bitmap_ior_into (m_equiv, var_vr->m_equiv);
>>>> }
>>>>
>>>> Is this a bug in the documentation / API, or is equiv_add incorrect and
>>>> we should fix the fall-out elsewhere?
>>>
>>> I think this must have been crept in during the classification.  If you
>>> go back to say GCC 7 you shouldn't see value-ranges with
>>> UNDEFINED/VARYING state in the lattice that have equivalences.
>>>
>>> It may not be easy to avoid with the new classy interface but we're
>>> certainly not tacking on them "blindly".  At least we're not supposed
>>> to.  As usual the intermediate state might be "broken" but
>>> intermediateness is not sth the new class "likes".
>>
>> It looks like extract_range_from_stmt (by virtue of
>> vrp_visit_assignment_or_call and then extract_range_from_ssa_name)
>> returns one of these intermediate ranges.  It would seem to me that an
>> outward looking API method like vr_values::extract_range_from_stmt
>> shouldn't be returning inconsistent ranges.  Or are there no guarantees
>> for value_ranges from within all of vr_values?
> ISTM that if we have an implementation constraint that says a VR_VARYING
> or VR_UNDEFINED range can't have equivalences, then we need to honor
> that at the minimum for anything returned by an external API.  Returning
> an inconsistent state is bad.  I'd even state that we should try damn
> hard to avoid it in internal APIs as well.

Agreed * 2.

> 
>>
>> Perhaps I should give a little background.  As part of your
>> value_range_base re-factoring last year, you mentioned that you didn't
>> split out intersect like you did union because of time or oversight.  I
>> have code to implement intersect (attached), for which I've noticed that
>> I must leave equivalences intact, even when transitioning to VR_UNDEFINED:
>>
>> [from the attached patch]
>> +  /* If THIS is varying we want to pick up equivalences from OTHER.
>> +     Just special-case this here rather than trying to fixup after the
>> +     fact.  */
>> +  if (this->varying_p ())
>> +    this->deep_copy (other);
>> +  else if (this->undefined_p ())
>> +    /* ?? Leave any equivalences already present in an undefined.
>> +       This is technically not allowed, but we may get an in-flight
>> +       value_range in an intermediate state.  */
> Where/when does this happen?

The above snippet is not currently in mainline.  It's in the patch I'm 
proposing to clean up intersect.  It's just that while cleaning up 
intersect I noticed that if we keep to the value_range API, we end up 
clobbering an equivalence to a VR_UNDEFINED that we depend up further up 
the call chain.

The reason it doesn't happen in mainline is because intersect_helper 
bails early on an undefined, thus leaving the problematic equivalence 
intact.

You can see it in mainline though, with the following testcase:

int f(int x)
{
   if (x != 0 && x != 1)
     return -2;

   return !x;
}

Break in evrp_range_analyzer::record_ranges_from_stmt() and see that the 
call to extract_range_from_stmt() returns a VR of undefined *WITH* 
equivalences:

       vr_values->extract_range_from_stmt (stmt, &taken_edge, &output, &vr);

This VR is later fed to update_value_range() and ultimately intersect(), 
which in mainline, leaves the equivalences alone, but IMO should respect 
that API and nuke them.

For my proposed overhaul of intersect, I have to special-case the 
undefined to make sure we don't clobber it's inconsistent use of 
equivalences.

> 
>> +    ;
>>
>> What is happening is that in evrp's record_ranges_from_stmt, we call
>> extract_range_from_stmt which returns an inconsistent VR_UNDEFINED with
>> an equivalence, which is then fed to update_value_range() and finally
>> value_range::intersect.  The VR_UNDEFINED equivalence must not be
>> removed in the intersect, because update_value_range() will get confused
>> as to whether this is a new VR or not (because VR_UNDEFINED with no
>> equivalences is not the same as VR_UNDEFINED with equivalences-- see
>> "is_new" in update_value_range).
> Ugh.  I hate some of the gyrations we have to do for update_value_range.
>   Regardless I tend to think the problem is in the inconsistent state we
> get back from extract_range_from_stmt.

Agreed.

Aldy

Re: undefined behavior in value_range::equiv_add()?

[Jeff Law]

On 5/29/19 10:20 AM, Aldy Hernandez wrote:
> On 5/29/19 12:12 PM, Jeff Law wrote:
>> On 5/29/19 9:58 AM, Aldy Hernandez wrote:
>>> On 5/29/19 9:24 AM, Richard Biener wrote:
>>>> On Wed, May 29, 2019 at 2:18 PM Aldy Hernandez <aldyh@redhat.com>
>>>> wrote:
>>>>>
>>>>> As per the API, and the original documentation to value_range,
>>>>> VR_UNDEFINED and VR_VARYING should never have equivalences.  However,
>>>>> equiv_add is tacking on equivalences blindly, and there are various
>>>>> regressions that happen if I fix this oversight.
>>>>>
>>>>> void
>>>>> value_range::equiv_add (const_tree var,
>>>>>                           const value_range *var_vr,
>>>>>                           bitmap_obstack *obstack)
>>>>> {
>>>>>      if (!m_equiv)
>>>>>        m_equiv = BITMAP_ALLOC (obstack);
>>>>>      unsigned ver = SSA_NAME_VERSION (var);
>>>>>      bitmap_set_bit (m_equiv, ver);
>>>>>      if (var_vr && var_vr->m_equiv)
>>>>>        bitmap_ior_into (m_equiv, var_vr->m_equiv);
>>>>> }
>>>>>
>>>>> Is this a bug in the documentation / API, or is equiv_add incorrect
>>>>> and
>>>>> we should fix the fall-out elsewhere?
>>>>
>>>> I think this must have been crept in during the classification.  If you
>>>> go back to say GCC 7 you shouldn't see value-ranges with
>>>> UNDEFINED/VARYING state in the lattice that have equivalences.
>>>>
>>>> It may not be easy to avoid with the new classy interface but we're
>>>> certainly not tacking on them "blindly".  At least we're not supposed
>>>> to.  As usual the intermediate state might be "broken" but
>>>> intermediateness is not sth the new class "likes".
>>>
>>> It looks like extract_range_from_stmt (by virtue of
>>> vrp_visit_assignment_or_call and then extract_range_from_ssa_name)
>>> returns one of these intermediate ranges.  It would seem to me that an
>>> outward looking API method like vr_values::extract_range_from_stmt
>>> shouldn't be returning inconsistent ranges.  Or are there no guarantees
>>> for value_ranges from within all of vr_values?
>> ISTM that if we have an implementation constraint that says a VR_VARYING
>> or VR_UNDEFINED range can't have equivalences, then we need to honor
>> that at the minimum for anything returned by an external API.  Returning
>> an inconsistent state is bad.  I'd even state that we should try damn
>> hard to avoid it in internal APIs as well.
> 
> Agreed * 2.
> 
>>
>>>
>>> Perhaps I should give a little background.  As part of your
>>> value_range_base re-factoring last year, you mentioned that you didn't
>>> split out intersect like you did union because of time or oversight.  I
>>> have code to implement intersect (attached), for which I've noticed that
>>> I must leave equivalences intact, even when transitioning to
>>> VR_UNDEFINED:
>>>
>>> [from the attached patch]
>>> +  /* If THIS is varying we want to pick up equivalences from OTHER.
>>> +     Just special-case this here rather than trying to fixup after the
>>> +     fact.  */
>>> +  if (this->varying_p ())
>>> +    this->deep_copy (other);
>>> +  else if (this->undefined_p ())
>>> +    /* ?? Leave any equivalences already present in an undefined.
>>> +       This is technically not allowed, but we may get an in-flight
>>> +       value_range in an intermediate state.  */
>> Where/when does this happen?
> 
> The above snippet is not currently in mainline.  It's in the patch I'm
> proposing to clean up intersect.  It's just that while cleaning up
> intersect I noticed that if we keep to the value_range API, we end up
> clobbering an equivalence to a VR_UNDEFINED that we depend up further up
> the call chain.
> 
> The reason it doesn't happen in mainline is because intersect_helper
> bails early on an undefined, thus leaving the problematic equivalence
> intact.
> 
> You can see it in mainline though, with the following testcase:
> 
> int f(int x)
> {
>   if (x != 0 && x != 1)
>     return -2;
> 
>   return !x;
> }
> 
> Break in evrp_range_analyzer::record_ranges_from_stmt() and see that the
> call to extract_range_from_stmt() returns a VR of undefined *WITH*
> equivalences:
> 
>       vr_values->extract_range_from_stmt (stmt, &taken_edge, &output, &vr);
> 
> This VR is later fed to update_value_range() and ultimately intersect(),
> which in mainline, leaves the equivalences alone, but IMO should respect
> that API and nuke them.
So I think this is coming from extract_range_from_ssa_name:

> void
> vr_values::extract_range_from_ssa_name (value_range *vr, tree var)
> {
>   value_range *var_vr = get_value_range (var);
> 
>   if (!var_vr->varying_p ())
>     vr->deep_copy (var_vr);
>   else
>     vr->set (var);
> 
>   vr->equiv_add (var, get_value_range (var), &vrp_equiv_obstack);
> }

Where we blindly add VAR to the equiv bitmap in the range.

AFAICT gcc-7 has equivalent code, it's just not inside the class.

I don't know what the fallout might be, but we could conditionalize the
call to add_equivalence to avoid the inconsistent state.

Jeff

Re: undefined behavior in value_range::equiv_add()?

[Richard Biener]

On Fri, May 31, 2019 at 2:27 AM Jeff Law <law@redhat.com> wrote:
>
> On 5/29/19 10:20 AM, Aldy Hernandez wrote:
> > On 5/29/19 12:12 PM, Jeff Law wrote:
> >> On 5/29/19 9:58 AM, Aldy Hernandez wrote:
> >>> On 5/29/19 9:24 AM, Richard Biener wrote:
> >>>> On Wed, May 29, 2019 at 2:18 PM Aldy Hernandez <aldyh@redhat.com>
> >>>> wrote:
> >>>>>
> >>>>> As per the API, and the original documentation to value_range,
> >>>>> VR_UNDEFINED and VR_VARYING should never have equivalences.  However,
> >>>>> equiv_add is tacking on equivalences blindly, and there are various
> >>>>> regressions that happen if I fix this oversight.
> >>>>>
> >>>>> void
> >>>>> value_range::equiv_add (const_tree var,
> >>>>>                           const value_range *var_vr,
> >>>>>                           bitmap_obstack *obstack)
> >>>>> {
> >>>>>      if (!m_equiv)
> >>>>>        m_equiv = BITMAP_ALLOC (obstack);
> >>>>>      unsigned ver = SSA_NAME_VERSION (var);
> >>>>>      bitmap_set_bit (m_equiv, ver);
> >>>>>      if (var_vr && var_vr->m_equiv)
> >>>>>        bitmap_ior_into (m_equiv, var_vr->m_equiv);
> >>>>> }
> >>>>>
> >>>>> Is this a bug in the documentation / API, or is equiv_add incorrect
> >>>>> and
> >>>>> we should fix the fall-out elsewhere?
> >>>>
> >>>> I think this must have been crept in during the classification.  If you
> >>>> go back to say GCC 7 you shouldn't see value-ranges with
> >>>> UNDEFINED/VARYING state in the lattice that have equivalences.
> >>>>
> >>>> It may not be easy to avoid with the new classy interface but we're
> >>>> certainly not tacking on them "blindly".  At least we're not supposed
> >>>> to.  As usual the intermediate state might be "broken" but
> >>>> intermediateness is not sth the new class "likes".
> >>>
> >>> It looks like extract_range_from_stmt (by virtue of
> >>> vrp_visit_assignment_or_call and then extract_range_from_ssa_name)
> >>> returns one of these intermediate ranges.  It would seem to me that an
> >>> outward looking API method like vr_values::extract_range_from_stmt
> >>> shouldn't be returning inconsistent ranges.  Or are there no guarantees
> >>> for value_ranges from within all of vr_values?
> >> ISTM that if we have an implementation constraint that says a VR_VARYING
> >> or VR_UNDEFINED range can't have equivalences, then we need to honor
> >> that at the minimum for anything returned by an external API.  Returning
> >> an inconsistent state is bad.  I'd even state that we should try damn
> >> hard to avoid it in internal APIs as well.
> >
> > Agreed * 2.
> >
> >>
> >>>
> >>> Perhaps I should give a little background.  As part of your
> >>> value_range_base re-factoring last year, you mentioned that you didn't
> >>> split out intersect like you did union because of time or oversight.  I
> >>> have code to implement intersect (attached), for which I've noticed that
> >>> I must leave equivalences intact, even when transitioning to
> >>> VR_UNDEFINED:
> >>>
> >>> [from the attached patch]
> >>> +  /* If THIS is varying we want to pick up equivalences from OTHER.
> >>> +     Just special-case this here rather than trying to fixup after the
> >>> +     fact.  */
> >>> +  if (this->varying_p ())
> >>> +    this->deep_copy (other);
> >>> +  else if (this->undefined_p ())
> >>> +    /* ?? Leave any equivalences already present in an undefined.
> >>> +       This is technically not allowed, but we may get an in-flight
> >>> +       value_range in an intermediate state.  */
> >> Where/when does this happen?
> >
> > The above snippet is not currently in mainline.  It's in the patch I'm
> > proposing to clean up intersect.  It's just that while cleaning up
> > intersect I noticed that if we keep to the value_range API, we end up
> > clobbering an equivalence to a VR_UNDEFINED that we depend up further up
> > the call chain.
> >
> > The reason it doesn't happen in mainline is because intersect_helper
> > bails early on an undefined, thus leaving the problematic equivalence
> > intact.
> >
> > You can see it in mainline though, with the following testcase:
> >
> > int f(int x)
> > {
> >   if (x != 0 && x != 1)
> >     return -2;
> >
> >   return !x;
> > }
> >
> > Break in evrp_range_analyzer::record_ranges_from_stmt() and see that the
> > call to extract_range_from_stmt() returns a VR of undefined *WITH*
> > equivalences:
> >
> >       vr_values->extract_range_from_stmt (stmt, &taken_edge, &output, &vr);
> >
> > This VR is later fed to update_value_range() and ultimately intersect(),
> > which in mainline, leaves the equivalences alone, but IMO should respect
> > that API and nuke them.
> So I think this is coming from extract_range_from_ssa_name:
>
> > void
> > vr_values::extract_range_from_ssa_name (value_range *vr, tree var)
> > {
> >   value_range *var_vr = get_value_range (var);
> >
> >   if (!var_vr->varying_p ())
> >     vr->deep_copy (var_vr);
> >   else
> >     vr->set (var);
> >
> >   vr->equiv_add (var, get_value_range (var), &vrp_equiv_obstack);
> > }
>
> Where we blindly add VAR to the equiv bitmap in the range.
>
> AFAICT gcc-7 has equivalent code, it's just not inside the class.
>
> I don't know what the fallout might be, but we could conditionalize the
> call to add_equivalence to avoid the inconsistent state.

Well, the issue is that the equivalence _is_ there.  So above we
know that we never end up with VARYING but the deep_copy
can bring over UNDEFINED to us.  I guess we _could_ elide
the equiv adding then.  OTOH the equivalence does look
useful for predicate simplification which IIRC doesn't treat
UNDEFINED != x in a useful way.  Which would mean allowing
equivalences on UNDEFINED.  That somewhat makes sense
since UNDEFINED is bottom-most in the lattice and one up
(CONSTANT) we have equivalences while just on topmost
(VARYING) we do not.

That said, I never liked equivalences - they are an odd way
to represent ranges intersected from multiple ranges thus
a way out of our too simplistic range representation.

So lets fix this in a way avoiding testsuite fallout.  But please
not with special hacks in consumers.  Does guariding the
above equiv_add with !vr->undefined_p () fix things?

Richard.

> Jeff

Re: undefined behavior in value_range::equiv_add()?

[Jeff Law]

On 5/31/19 3:00 AM, Richard Biener wrote:
> On Fri, May 31, 2019 at 2:27 AM Jeff Law <law@redhat.com> wrote:
>>
>> On 5/29/19 10:20 AM, Aldy Hernandez wrote:
>>> On 5/29/19 12:12 PM, Jeff Law wrote:
>>>> On 5/29/19 9:58 AM, Aldy Hernandez wrote:
>>>>> On 5/29/19 9:24 AM, Richard Biener wrote:
>>>>>> On Wed, May 29, 2019 at 2:18 PM Aldy Hernandez <aldyh@redhat.com>
>>>>>> wrote:
>>>>>>>
>>>>>>> As per the API, and the original documentation to value_range,
>>>>>>> VR_UNDEFINED and VR_VARYING should never have equivalences.  However,
>>>>>>> equiv_add is tacking on equivalences blindly, and there are various
>>>>>>> regressions that happen if I fix this oversight.
>>>>>>>
>>>>>>> void
>>>>>>> value_range::equiv_add (const_tree var,
>>>>>>>                           const value_range *var_vr,
>>>>>>>                           bitmap_obstack *obstack)
>>>>>>> {
>>>>>>>      if (!m_equiv)
>>>>>>>        m_equiv = BITMAP_ALLOC (obstack);
>>>>>>>      unsigned ver = SSA_NAME_VERSION (var);
>>>>>>>      bitmap_set_bit (m_equiv, ver);
>>>>>>>      if (var_vr && var_vr->m_equiv)
>>>>>>>        bitmap_ior_into (m_equiv, var_vr->m_equiv);
>>>>>>> }
>>>>>>>
>>>>>>> Is this a bug in the documentation / API, or is equiv_add incorrect
>>>>>>> and
>>>>>>> we should fix the fall-out elsewhere?
>>>>>>
>>>>>> I think this must have been crept in during the classification.  If you
>>>>>> go back to say GCC 7 you shouldn't see value-ranges with
>>>>>> UNDEFINED/VARYING state in the lattice that have equivalences.
>>>>>>
>>>>>> It may not be easy to avoid with the new classy interface but we're
>>>>>> certainly not tacking on them "blindly".  At least we're not supposed
>>>>>> to.  As usual the intermediate state might be "broken" but
>>>>>> intermediateness is not sth the new class "likes".
>>>>>
>>>>> It looks like extract_range_from_stmt (by virtue of
>>>>> vrp_visit_assignment_or_call and then extract_range_from_ssa_name)
>>>>> returns one of these intermediate ranges.  It would seem to me that an
>>>>> outward looking API method like vr_values::extract_range_from_stmt
>>>>> shouldn't be returning inconsistent ranges.  Or are there no guarantees
>>>>> for value_ranges from within all of vr_values?
>>>> ISTM that if we have an implementation constraint that says a VR_VARYING
>>>> or VR_UNDEFINED range can't have equivalences, then we need to honor
>>>> that at the minimum for anything returned by an external API.  Returning
>>>> an inconsistent state is bad.  I'd even state that we should try damn
>>>> hard to avoid it in internal APIs as well.
>>>
>>> Agreed * 2.
>>>
>>>>
>>>>>
>>>>> Perhaps I should give a little background.  As part of your
>>>>> value_range_base re-factoring last year, you mentioned that you didn't
>>>>> split out intersect like you did union because of time or oversight.  I
>>>>> have code to implement intersect (attached), for which I've noticed that
>>>>> I must leave equivalences intact, even when transitioning to
>>>>> VR_UNDEFINED:
>>>>>
>>>>> [from the attached patch]
>>>>> +  /* If THIS is varying we want to pick up equivalences from OTHER.
>>>>> +     Just special-case this here rather than trying to fixup after the
>>>>> +     fact.  */
>>>>> +  if (this->varying_p ())
>>>>> +    this->deep_copy (other);
>>>>> +  else if (this->undefined_p ())
>>>>> +    /* ?? Leave any equivalences already present in an undefined.
>>>>> +       This is technically not allowed, but we may get an in-flight
>>>>> +       value_range in an intermediate state.  */
>>>> Where/when does this happen?
>>>
>>> The above snippet is not currently in mainline.  It's in the patch I'm
>>> proposing to clean up intersect.  It's just that while cleaning up
>>> intersect I noticed that if we keep to the value_range API, we end up
>>> clobbering an equivalence to a VR_UNDEFINED that we depend up further up
>>> the call chain.
>>>
>>> The reason it doesn't happen in mainline is because intersect_helper
>>> bails early on an undefined, thus leaving the problematic equivalence
>>> intact.
>>>
>>> You can see it in mainline though, with the following testcase:
>>>
>>> int f(int x)
>>> {
>>>   if (x != 0 && x != 1)
>>>     return -2;
>>>
>>>   return !x;
>>> }
>>>
>>> Break in evrp_range_analyzer::record_ranges_from_stmt() and see that the
>>> call to extract_range_from_stmt() returns a VR of undefined *WITH*
>>> equivalences:
>>>
>>>       vr_values->extract_range_from_stmt (stmt, &taken_edge, &output, &vr);
>>>
>>> This VR is later fed to update_value_range() and ultimately intersect(),
>>> which in mainline, leaves the equivalences alone, but IMO should respect
>>> that API and nuke them.
>> So I think this is coming from extract_range_from_ssa_name:
>>
>>> void
>>> vr_values::extract_range_from_ssa_name (value_range *vr, tree var)
>>> {
>>>   value_range *var_vr = get_value_range (var);
>>>
>>>   if (!var_vr->varying_p ())
>>>     vr->deep_copy (var_vr);
>>>   else
>>>     vr->set (var);
>>>
>>>   vr->equiv_add (var, get_value_range (var), &vrp_equiv_obstack);
>>> }
>>
>> Where we blindly add VAR to the equiv bitmap in the range.
>>
>> AFAICT gcc-7 has equivalent code, it's just not inside the class.
>>
>> I don't know what the fallout might be, but we could conditionalize the
>> call to add_equivalence to avoid the inconsistent state.
> 
> Well, the issue is that the equivalence _is_ there.  So above we
> know that we never end up with VARYING but the deep_copy
> can bring over UNDEFINED to us.  I guess we _could_ elide
> the equiv adding then.  OTOH the equivalence does look
> useful for predicate simplification which IIRC doesn't treat
> UNDEFINED != x in a useful way.  Which would mean allowing
> equivalences on UNDEFINED.  That somewhat makes sense
> since UNDEFINED is bottom-most in the lattice and one up
> (CONSTANT) we have equivalences while just on topmost
> (VARYING) we do not.
> 
> That said, I never liked equivalences - they are an odd way
> to represent ranges intersected from multiple ranges thus
> a way out of our too simplistic range representation.
> 
> So lets fix this in a way avoiding testsuite fallout.  But please
> not with special hacks in consumers.  Does guariding the
> above equiv_add with !vr->undefined_p () fix things?
I think we're in total agreement -- fix the inconsistencies, not the
consumers.

Jeff

Re: undefined behavior in value_range::equiv_add()?

[Aldy Hernandez]

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

On 5/31/19 5:00 AM, Richard Biener wrote:
> On Fri, May 31, 2019 at 2:27 AM Jeff Law <law@redhat.com> wrote:
>>
>> On 5/29/19 10:20 AM, Aldy Hernandez wrote:
>>> On 5/29/19 12:12 PM, Jeff Law wrote:
>>>> On 5/29/19 9:58 AM, Aldy Hernandez wrote:
>>>>> On 5/29/19 9:24 AM, Richard Biener wrote:
>>>>>> On Wed, May 29, 2019 at 2:18 PM Aldy Hernandez <aldyh@redhat.com>
>>>>>> wrote:
>>>>>>>
>>>>>>> As per the API, and the original documentation to value_range,
>>>>>>> VR_UNDEFINED and VR_VARYING should never have equivalences.  However,
>>>>>>> equiv_add is tacking on equivalences blindly, and there are various
>>>>>>> regressions that happen if I fix this oversight.
>>>>>>>
>>>>>>> void
>>>>>>> value_range::equiv_add (const_tree var,
>>>>>>>                            const value_range *var_vr,
>>>>>>>                            bitmap_obstack *obstack)
>>>>>>> {
>>>>>>>       if (!m_equiv)
>>>>>>>         m_equiv = BITMAP_ALLOC (obstack);
>>>>>>>       unsigned ver = SSA_NAME_VERSION (var);
>>>>>>>       bitmap_set_bit (m_equiv, ver);
>>>>>>>       if (var_vr && var_vr->m_equiv)
>>>>>>>         bitmap_ior_into (m_equiv, var_vr->m_equiv);
>>>>>>> }
>>>>>>>
>>>>>>> Is this a bug in the documentation / API, or is equiv_add incorrect
>>>>>>> and
>>>>>>> we should fix the fall-out elsewhere?
>>>>>>
>>>>>> I think this must have been crept in during the classification.  If you
>>>>>> go back to say GCC 7 you shouldn't see value-ranges with
>>>>>> UNDEFINED/VARYING state in the lattice that have equivalences.
>>>>>>
>>>>>> It may not be easy to avoid with the new classy interface but we're
>>>>>> certainly not tacking on them "blindly".  At least we're not supposed
>>>>>> to.  As usual the intermediate state might be "broken" but
>>>>>> intermediateness is not sth the new class "likes".
>>>>>
>>>>> It looks like extract_range_from_stmt (by virtue of
>>>>> vrp_visit_assignment_or_call and then extract_range_from_ssa_name)
>>>>> returns one of these intermediate ranges.  It would seem to me that an
>>>>> outward looking API method like vr_values::extract_range_from_stmt
>>>>> shouldn't be returning inconsistent ranges.  Or are there no guarantees
>>>>> for value_ranges from within all of vr_values?
>>>> ISTM that if we have an implementation constraint that says a VR_VARYING
>>>> or VR_UNDEFINED range can't have equivalences, then we need to honor
>>>> that at the minimum for anything returned by an external API.  Returning
>>>> an inconsistent state is bad.  I'd even state that we should try damn
>>>> hard to avoid it in internal APIs as well.
>>>
>>> Agreed * 2.
>>>
>>>>
>>>>>
>>>>> Perhaps I should give a little background.  As part of your
>>>>> value_range_base re-factoring last year, you mentioned that you didn't
>>>>> split out intersect like you did union because of time or oversight.  I
>>>>> have code to implement intersect (attached), for which I've noticed that
>>>>> I must leave equivalences intact, even when transitioning to
>>>>> VR_UNDEFINED:
>>>>>
>>>>> [from the attached patch]
>>>>> +  /* If THIS is varying we want to pick up equivalences from OTHER.
>>>>> +     Just special-case this here rather than trying to fixup after the
>>>>> +     fact.  */
>>>>> +  if (this->varying_p ())
>>>>> +    this->deep_copy (other);
>>>>> +  else if (this->undefined_p ())
>>>>> +    /* ?? Leave any equivalences already present in an undefined.
>>>>> +       This is technically not allowed, but we may get an in-flight
>>>>> +       value_range in an intermediate state.  */
>>>> Where/when does this happen?
>>>
>>> The above snippet is not currently in mainline.  It's in the patch I'm
>>> proposing to clean up intersect.  It's just that while cleaning up
>>> intersect I noticed that if we keep to the value_range API, we end up
>>> clobbering an equivalence to a VR_UNDEFINED that we depend up further up
>>> the call chain.
>>>
>>> The reason it doesn't happen in mainline is because intersect_helper
>>> bails early on an undefined, thus leaving the problematic equivalence
>>> intact.
>>>
>>> You can see it in mainline though, with the following testcase:
>>>
>>> int f(int x)
>>> {
>>>    if (x != 0 && x != 1)
>>>      return -2;
>>>
>>>    return !x;
>>> }
>>>
>>> Break in evrp_range_analyzer::record_ranges_from_stmt() and see that the
>>> call to extract_range_from_stmt() returns a VR of undefined *WITH*
>>> equivalences:
>>>
>>>        vr_values->extract_range_from_stmt (stmt, &taken_edge, &output, &vr);
>>>
>>> This VR is later fed to update_value_range() and ultimately intersect(),
>>> which in mainline, leaves the equivalences alone, but IMO should respect
>>> that API and nuke them.
>> So I think this is coming from extract_range_from_ssa_name:
>>
>>> void
>>> vr_values::extract_range_from_ssa_name (value_range *vr, tree var)
>>> {
>>>    value_range *var_vr = get_value_range (var);
>>>
>>>    if (!var_vr->varying_p ())
>>>      vr->deep_copy (var_vr);
>>>    else
>>>      vr->set (var);
>>>
>>>    vr->equiv_add (var, get_value_range (var), &vrp_equiv_obstack);
>>> }
>>
>> Where we blindly add VAR to the equiv bitmap in the range.
>>
>> AFAICT gcc-7 has equivalent code, it's just not inside the class.
>>
>> I don't know what the fallout might be, but we could conditionalize the
>> call to add_equivalence to avoid the inconsistent state.
> 
> Well, the issue is that the equivalence _is_ there.  So above we
> know that we never end up with VARYING but the deep_copy
> can bring over UNDEFINED to us.  I guess we _could_ elide
> the equiv adding then.  OTOH the equivalence does look
> useful for predicate simplification which IIRC doesn't treat
> UNDEFINED != x in a useful way.  Which would mean allowing
> equivalences on UNDEFINED.  That somewhat makes sense
> since UNDEFINED is bottom-most in the lattice and one up
> (CONSTANT) we have equivalences while just on topmost
> (VARYING) we do not.
> 
> That said, I never liked equivalences - they are an odd way
> to represent ranges intersected from multiple ranges thus
> a way out of our too simplistic range representation.
> 
> So lets fix this in a way avoiding testsuite fallout.  But please
> not with special hacks in consumers.  Does guariding the
> above equiv_add with !vr->undefined_p () fix things?

Agreed.  I never suggested we add special hacks to intersect.  The 
two-liner was only to explain why equivalences in varying/undefined 
currently matter in intersect.

Guarding the equiv_add causes regressions.  For example, for this simple 
testcase we incorrectly get rid of the final PHI:

int f(int x)
{
   if (x != 0 && x != 1)
     return -2;

   return !x;
}

In the evrp dump we now see:

Visiting PHI node: _3 = PHI <-2(3), _5(4)>
     Argument #0 (3 -> 5 executable)
         -2: int [-2, -2]
     Argument #1 (4 -> 5 executable)
         _5: UNDEFINED
Meeting
   int [-2, -2]
and
   UNDEFINED
to
   int [-2, -2]

whereas before the change, argument #1 was:

     Argument #1 (4 -> 5 executable)
         _5: int [_5, _5]

and the meeting result was VARYING.

I *think* this starts somewhere up the call chain in update_value_range, 
which as I've described earlier, will no longer make a difference 
between UNDEFINED and UNDEFINED + equivalence.  This causes that when 
transitioning from UNDEFINED to UNDEFINED + equivalence, we actually 
transition to VARYING:

  if (is_new)
     {
       if (old_vr->varying_p ())
	{
	  new_vr->set_varying ();
	  is_new = false;
	}
       else if (new_vr->undefined_p ())
	{
	  old_vr->set_varying ();
	  new_vr->set_varying ();
	  return true;
	}

Could someone better versed in this take a peek, please?  It's just a 
matter of applying the attached one-liner, and looking at "Visiting PHI" 
in the evrp dump.

Thanks.
Aldy

[-- Attachment #2: curr.patch --]
[-- Type: text/x-patch, Size: 513 bytes --]

diff --git a/gcc/vr-values.c b/gcc/vr-values.c
index b401516ae8e..86f9375c51f 100644
--- a/gcc/vr-values.c
+++ b/gcc/vr-values.c
@@ -719,7 +719,8 @@ vr_values::extract_range_from_ssa_name (value_range *vr, tree var)
   else
     vr->set (var);
 
-  vr->equiv_add (var, get_value_range (var), &vrp_equiv_obstack);
+  if (!vr->undefined_p () && !vr->varying_p ())
+    vr->equiv_add (var, get_value_range (var), &vrp_equiv_obstack);
 }
 
 /* Extract range information from a binary expression OP0 CODE OP1 based on

Re: undefined behavior in value_range::equiv_add()?

[Jeff Law]

On 6/3/19 7:13 AM, Aldy Hernandez wrote:
> On 5/31/19 5:00 AM, Richard Biener wrote:
>> On Fri, May 31, 2019 at 2:27 AM Jeff Law <law@redhat.com> wrote:
>>>
>>> On 5/29/19 10:20 AM, Aldy Hernandez wrote:
>>>> On 5/29/19 12:12 PM, Jeff Law wrote:
>>>>> On 5/29/19 9:58 AM, Aldy Hernandez wrote:
>>>>>> On 5/29/19 9:24 AM, Richard Biener wrote:
>>>>>>> On Wed, May 29, 2019 at 2:18 PM Aldy Hernandez <aldyh@redhat.com>
>>>>>>> wrote:
>>>>>>>>
>>>>>>>> As per the API, and the original documentation to value_range,
>>>>>>>> VR_UNDEFINED and VR_VARYING should never have equivalences. 
>>>>>>>> However,
>>>>>>>> equiv_add is tacking on equivalences blindly, and there are various
>>>>>>>> regressions that happen if I fix this oversight.
>>>>>>>>
>>>>>>>> void
>>>>>>>> value_range::equiv_add (const_tree var,
>>>>>>>>                            const value_range *var_vr,
>>>>>>>>                            bitmap_obstack *obstack)
>>>>>>>> {
>>>>>>>>       if (!m_equiv)
>>>>>>>>         m_equiv = BITMAP_ALLOC (obstack);
>>>>>>>>       unsigned ver = SSA_NAME_VERSION (var);
>>>>>>>>       bitmap_set_bit (m_equiv, ver);
>>>>>>>>       if (var_vr && var_vr->m_equiv)
>>>>>>>>         bitmap_ior_into (m_equiv, var_vr->m_equiv);
>>>>>>>> }
>>>>>>>>
>>>>>>>> Is this a bug in the documentation / API, or is equiv_add incorrect
>>>>>>>> and
>>>>>>>> we should fix the fall-out elsewhere?
>>>>>>>
>>>>>>> I think this must have been crept in during the classification. 
>>>>>>> If you
>>>>>>> go back to say GCC 7 you shouldn't see value-ranges with
>>>>>>> UNDEFINED/VARYING state in the lattice that have equivalences.
>>>>>>>
>>>>>>> It may not be easy to avoid with the new classy interface but we're
>>>>>>> certainly not tacking on them "blindly".  At least we're not
>>>>>>> supposed
>>>>>>> to.  As usual the intermediate state might be "broken" but
>>>>>>> intermediateness is not sth the new class "likes".
>>>>>>
>>>>>> It looks like extract_range_from_stmt (by virtue of
>>>>>> vrp_visit_assignment_or_call and then extract_range_from_ssa_name)
>>>>>> returns one of these intermediate ranges.  It would seem to me
>>>>>> that an
>>>>>> outward looking API method like vr_values::extract_range_from_stmt
>>>>>> shouldn't be returning inconsistent ranges.  Or are there no
>>>>>> guarantees
>>>>>> for value_ranges from within all of vr_values?
>>>>> ISTM that if we have an implementation constraint that says a
>>>>> VR_VARYING
>>>>> or VR_UNDEFINED range can't have equivalences, then we need to honor
>>>>> that at the minimum for anything returned by an external API. 
>>>>> Returning
>>>>> an inconsistent state is bad.  I'd even state that we should try damn
>>>>> hard to avoid it in internal APIs as well.
>>>>
>>>> Agreed * 2.
>>>>
>>>>>
>>>>>>
>>>>>> Perhaps I should give a little background.  As part of your
>>>>>> value_range_base re-factoring last year, you mentioned that you
>>>>>> didn't
>>>>>> split out intersect like you did union because of time or
>>>>>> oversight.  I
>>>>>> have code to implement intersect (attached), for which I've
>>>>>> noticed that
>>>>>> I must leave equivalences intact, even when transitioning to
>>>>>> VR_UNDEFINED:
>>>>>>
>>>>>> [from the attached patch]
>>>>>> +  /* If THIS is varying we want to pick up equivalences from OTHER.
>>>>>> +     Just special-case this here rather than trying to fixup
>>>>>> after the
>>>>>> +     fact.  */
>>>>>> +  if (this->varying_p ())
>>>>>> +    this->deep_copy (other);
>>>>>> +  else if (this->undefined_p ())
>>>>>> +    /* ?? Leave any equivalences already present in an undefined.
>>>>>> +       This is technically not allowed, but we may get an in-flight
>>>>>> +       value_range in an intermediate state.  */
>>>>> Where/when does this happen?
>>>>
>>>> The above snippet is not currently in mainline.  It's in the patch I'm
>>>> proposing to clean up intersect.  It's just that while cleaning up
>>>> intersect I noticed that if we keep to the value_range API, we end up
>>>> clobbering an equivalence to a VR_UNDEFINED that we depend up
>>>> further up
>>>> the call chain.
>>>>
>>>> The reason it doesn't happen in mainline is because intersect_helper
>>>> bails early on an undefined, thus leaving the problematic equivalence
>>>> intact.
>>>>
>>>> You can see it in mainline though, with the following testcase:
>>>>
>>>> int f(int x)
>>>> {
>>>>    if (x != 0 && x != 1)
>>>>      return -2;
>>>>
>>>>    return !x;
>>>> }
>>>>
>>>> Break in evrp_range_analyzer::record_ranges_from_stmt() and see that
>>>> the
>>>> call to extract_range_from_stmt() returns a VR of undefined *WITH*
>>>> equivalences:
>>>>
>>>>        vr_values->extract_range_from_stmt (stmt, &taken_edge,
>>>> &output, &vr);
>>>>
>>>> This VR is later fed to update_value_range() and ultimately
>>>> intersect(),
>>>> which in mainline, leaves the equivalences alone, but IMO should
>>>> respect
>>>> that API and nuke them.
>>> So I think this is coming from extract_range_from_ssa_name:
>>>
>>>> void
>>>> vr_values::extract_range_from_ssa_name (value_range *vr, tree var)
>>>> {
>>>>    value_range *var_vr = get_value_range (var);
>>>>
>>>>    if (!var_vr->varying_p ())
>>>>      vr->deep_copy (var_vr);
>>>>    else
>>>>      vr->set (var);
>>>>
>>>>    vr->equiv_add (var, get_value_range (var), &vrp_equiv_obstack);
>>>> }
>>>
>>> Where we blindly add VAR to the equiv bitmap in the range.
>>>
>>> AFAICT gcc-7 has equivalent code, it's just not inside the class.
>>>
>>> I don't know what the fallout might be, but we could conditionalize the
>>> call to add_equivalence to avoid the inconsistent state.
>>
>> Well, the issue is that the equivalence _is_ there.  So above we
>> know that we never end up with VARYING but the deep_copy
>> can bring over UNDEFINED to us.  I guess we _could_ elide
>> the equiv adding then.  OTOH the equivalence does look
>> useful for predicate simplification which IIRC doesn't treat
>> UNDEFINED != x in a useful way.  Which would mean allowing
>> equivalences on UNDEFINED.  That somewhat makes sense
>> since UNDEFINED is bottom-most in the lattice and one up
>> (CONSTANT) we have equivalences while just on topmost
>> (VARYING) we do not.
>>
>> That said, I never liked equivalences - they are an odd way
>> to represent ranges intersected from multiple ranges thus
>> a way out of our too simplistic range representation.
>>
>> So lets fix this in a way avoiding testsuite fallout.  But please
>> not with special hacks in consumers.  Does guariding the
>> above equiv_add with !vr->undefined_p () fix things?
> 
> Agreed.  I never suggested we add special hacks to intersect.  The
> two-liner was only to explain why equivalences in varying/undefined
> currently matter in intersect.
> 
> Guarding the equiv_add causes regressions.  For example, for this simple
> testcase we incorrectly get rid of the final PHI:
> 
> int f(int x)
> {
>   if (x != 0 && x != 1)
>     return -2;
> 
>   return !x;
> }
> 
> In the evrp dump we now see:
> 
> Visiting PHI node: _3 = PHI <-2(3), _5(4)>
>     Argument #0 (3 -> 5 executable)
>         -2: int [-2, -2]
>     Argument #1 (4 -> 5 executable)
>         _5: UNDEFINED
> Meeting
>   int [-2, -2]
> and
>   UNDEFINED
> to
>   int [-2, -2]
> 
> whereas before the change, argument #1 was:
> 
>     Argument #1 (4 -> 5 executable)
>         _5: int [_5, _5]
> 
> and the meeting result was VARYING.
> 
> I *think* this starts somewhere up the call chain in update_value_range,
> which as I've described earlier, will no longer make a difference
> between UNDEFINED and UNDEFINED + equivalence.  This causes that when
> transitioning from UNDEFINED to UNDEFINED + equivalence, we actually
> transition to VARYING:
> 
>  if (is_new)
>     {
>       if (old_vr->varying_p ())
>     {
>       new_vr->set_varying ();
>       is_new = false;
>     }
>       else if (new_vr->undefined_p ())
>     {
>       old_vr->set_varying ();
>       new_vr->set_varying ();
>       return true;
>     }
> 
> Could someone better versed in this take a peek, please?  It's just a
> matter of applying the attached one-liner, and looking at "Visiting PHI"
> in the evrp dump.
As I mentioned in IRC.  I know what's going on here and see a path to
fix it.  Hoping to get a patch into my tester overnight, but life seems
to be getting in the way.

jeff

Re: undefined behavior in value_range::equiv_add()?

[Richard Biener]

On Tue, Jun 4, 2019 at 12:30 AM Jeff Law <law@redhat.com> wrote:
>
> On 6/3/19 7:13 AM, Aldy Hernandez wrote:
> > On 5/31/19 5:00 AM, Richard Biener wrote:
> >> On Fri, May 31, 2019 at 2:27 AM Jeff Law <law@redhat.com> wrote:
> >>>
> >>> On 5/29/19 10:20 AM, Aldy Hernandez wrote:
> >>>> On 5/29/19 12:12 PM, Jeff Law wrote:
> >>>>> On 5/29/19 9:58 AM, Aldy Hernandez wrote:
> >>>>>> On 5/29/19 9:24 AM, Richard Biener wrote:
> >>>>>>> On Wed, May 29, 2019 at 2:18 PM Aldy Hernandez <aldyh@redhat.com>
> >>>>>>> wrote:
> >>>>>>>>
> >>>>>>>> As per the API, and the original documentation to value_range,
> >>>>>>>> VR_UNDEFINED and VR_VARYING should never have equivalences.
> >>>>>>>> However,
> >>>>>>>> equiv_add is tacking on equivalences blindly, and there are various
> >>>>>>>> regressions that happen if I fix this oversight.
> >>>>>>>>
> >>>>>>>> void
> >>>>>>>> value_range::equiv_add (const_tree var,
> >>>>>>>>                            const value_range *var_vr,
> >>>>>>>>                            bitmap_obstack *obstack)
> >>>>>>>> {
> >>>>>>>>       if (!m_equiv)
> >>>>>>>>         m_equiv = BITMAP_ALLOC (obstack);
> >>>>>>>>       unsigned ver = SSA_NAME_VERSION (var);
> >>>>>>>>       bitmap_set_bit (m_equiv, ver);
> >>>>>>>>       if (var_vr && var_vr->m_equiv)
> >>>>>>>>         bitmap_ior_into (m_equiv, var_vr->m_equiv);
> >>>>>>>> }
> >>>>>>>>
> >>>>>>>> Is this a bug in the documentation / API, or is equiv_add incorrect
> >>>>>>>> and
> >>>>>>>> we should fix the fall-out elsewhere?
> >>>>>>>
> >>>>>>> I think this must have been crept in during the classification.
> >>>>>>> If you
> >>>>>>> go back to say GCC 7 you shouldn't see value-ranges with
> >>>>>>> UNDEFINED/VARYING state in the lattice that have equivalences.
> >>>>>>>
> >>>>>>> It may not be easy to avoid with the new classy interface but we're
> >>>>>>> certainly not tacking on them "blindly".  At least we're not
> >>>>>>> supposed
> >>>>>>> to.  As usual the intermediate state might be "broken" but
> >>>>>>> intermediateness is not sth the new class "likes".
> >>>>>>
> >>>>>> It looks like extract_range_from_stmt (by virtue of
> >>>>>> vrp_visit_assignment_or_call and then extract_range_from_ssa_name)
> >>>>>> returns one of these intermediate ranges.  It would seem to me
> >>>>>> that an
> >>>>>> outward looking API method like vr_values::extract_range_from_stmt
> >>>>>> shouldn't be returning inconsistent ranges.  Or are there no
> >>>>>> guarantees
> >>>>>> for value_ranges from within all of vr_values?
> >>>>> ISTM that if we have an implementation constraint that says a
> >>>>> VR_VARYING
> >>>>> or VR_UNDEFINED range can't have equivalences, then we need to honor
> >>>>> that at the minimum for anything returned by an external API.
> >>>>> Returning
> >>>>> an inconsistent state is bad.  I'd even state that we should try damn
> >>>>> hard to avoid it in internal APIs as well.
> >>>>
> >>>> Agreed * 2.
> >>>>
> >>>>>
> >>>>>>
> >>>>>> Perhaps I should give a little background.  As part of your
> >>>>>> value_range_base re-factoring last year, you mentioned that you
> >>>>>> didn't
> >>>>>> split out intersect like you did union because of time or
> >>>>>> oversight.  I
> >>>>>> have code to implement intersect (attached), for which I've
> >>>>>> noticed that
> >>>>>> I must leave equivalences intact, even when transitioning to
> >>>>>> VR_UNDEFINED:
> >>>>>>
> >>>>>> [from the attached patch]
> >>>>>> +  /* If THIS is varying we want to pick up equivalences from OTHER.
> >>>>>> +     Just special-case this here rather than trying to fixup
> >>>>>> after the
> >>>>>> +     fact.  */
> >>>>>> +  if (this->varying_p ())
> >>>>>> +    this->deep_copy (other);
> >>>>>> +  else if (this->undefined_p ())
> >>>>>> +    /* ?? Leave any equivalences already present in an undefined.
> >>>>>> +       This is technically not allowed, but we may get an in-flight
> >>>>>> +       value_range in an intermediate state.  */
> >>>>> Where/when does this happen?
> >>>>
> >>>> The above snippet is not currently in mainline.  It's in the patch I'm
> >>>> proposing to clean up intersect.  It's just that while cleaning up
> >>>> intersect I noticed that if we keep to the value_range API, we end up
> >>>> clobbering an equivalence to a VR_UNDEFINED that we depend up
> >>>> further up
> >>>> the call chain.
> >>>>
> >>>> The reason it doesn't happen in mainline is because intersect_helper
> >>>> bails early on an undefined, thus leaving the problematic equivalence
> >>>> intact.
> >>>>
> >>>> You can see it in mainline though, with the following testcase:
> >>>>
> >>>> int f(int x)
> >>>> {
> >>>>    if (x != 0 && x != 1)
> >>>>      return -2;
> >>>>
> >>>>    return !x;
> >>>> }
> >>>>
> >>>> Break in evrp_range_analyzer::record_ranges_from_stmt() and see that
> >>>> the
> >>>> call to extract_range_from_stmt() returns a VR of undefined *WITH*
> >>>> equivalences:
> >>>>
> >>>>        vr_values->extract_range_from_stmt (stmt, &taken_edge,
> >>>> &output, &vr);
> >>>>
> >>>> This VR is later fed to update_value_range() and ultimately
> >>>> intersect(),
> >>>> which in mainline, leaves the equivalences alone, but IMO should
> >>>> respect
> >>>> that API and nuke them.
> >>> So I think this is coming from extract_range_from_ssa_name:
> >>>
> >>>> void
> >>>> vr_values::extract_range_from_ssa_name (value_range *vr, tree var)
> >>>> {
> >>>>    value_range *var_vr = get_value_range (var);
> >>>>
> >>>>    if (!var_vr->varying_p ())
> >>>>      vr->deep_copy (var_vr);
> >>>>    else
> >>>>      vr->set (var);
> >>>>
> >>>>    vr->equiv_add (var, get_value_range (var), &vrp_equiv_obstack);
> >>>> }
> >>>
> >>> Where we blindly add VAR to the equiv bitmap in the range.
> >>>
> >>> AFAICT gcc-7 has equivalent code, it's just not inside the class.
> >>>
> >>> I don't know what the fallout might be, but we could conditionalize the
> >>> call to add_equivalence to avoid the inconsistent state.
> >>
> >> Well, the issue is that the equivalence _is_ there.  So above we
> >> know that we never end up with VARYING but the deep_copy
> >> can bring over UNDEFINED to us.  I guess we _could_ elide
> >> the equiv adding then.  OTOH the equivalence does look
> >> useful for predicate simplification which IIRC doesn't treat
> >> UNDEFINED != x in a useful way.  Which would mean allowing
> >> equivalences on UNDEFINED.  That somewhat makes sense
> >> since UNDEFINED is bottom-most in the lattice and one up
> >> (CONSTANT) we have equivalences while just on topmost
> >> (VARYING) we do not.
> >>
> >> That said, I never liked equivalences - they are an odd way
> >> to represent ranges intersected from multiple ranges thus
> >> a way out of our too simplistic range representation.
> >>
> >> So lets fix this in a way avoiding testsuite fallout.  But please
> >> not with special hacks in consumers.  Does guariding the
> >> above equiv_add with !vr->undefined_p () fix things?
> >
> > Agreed.  I never suggested we add special hacks to intersect.  The
> > two-liner was only to explain why equivalences in varying/undefined
> > currently matter in intersect.
> >
> > Guarding the equiv_add causes regressions.  For example, for this simple
> > testcase we incorrectly get rid of the final PHI:
> >
> > int f(int x)
> > {
> >   if (x != 0 && x != 1)
> >     return -2;
> >
> >   return !x;
> > }
> >
> > In the evrp dump we now see:
> >
> > Visiting PHI node: _3 = PHI <-2(3), _5(4)>
> >     Argument #0 (3 -> 5 executable)
> >         -2: int [-2, -2]
> >     Argument #1 (4 -> 5 executable)
> >         _5: UNDEFINED
> > Meeting
> >   int [-2, -2]
> > and
> >   UNDEFINED
> > to
> >   int [-2, -2]
> >
> > whereas before the change, argument #1 was:
> >
> >     Argument #1 (4 -> 5 executable)
> >         _5: int [_5, _5]
> >
> > and the meeting result was VARYING.
> >
> > I *think* this starts somewhere up the call chain in update_value_range,
> > which as I've described earlier, will no longer make a difference
> > between UNDEFINED and UNDEFINED + equivalence.  This causes that when
> > transitioning from UNDEFINED to UNDEFINED + equivalence, we actually
> > transition to VARYING:
> >
> >  if (is_new)
> >     {
> >       if (old_vr->varying_p ())
> >     {
> >       new_vr->set_varying ();
> >       is_new = false;
> >     }
> >       else if (new_vr->undefined_p ())
> >     {
> >       old_vr->set_varying ();
> >       new_vr->set_varying ();
> >       return true;
> >     }
> >
> > Could someone better versed in this take a peek, please?  It's just a
> > matter of applying the attached one-liner, and looking at "Visiting PHI"
> > in the evrp dump.
> As I mentioned in IRC.  I know what's going on here and see a path to
> fix it.  Hoping to get a patch into my tester overnight, but life seems
> to be getting in the way.

It's of course a latent issue.  One I fixed in DOMs use of the EVRP machinery.
The following fixes it in a conservative way:

Index: gcc/gimple-ssa-evrp.c
===================================================================
--- gcc/gimple-ssa-evrp.c       (revision 271904)
+++ gcc/gimple-ssa-evrp.c       (working copy)
@@ -175,6 +175,8 @@ evrp_dom_walker::before_dom_children (ba

       /* Try folding stmts with the VR discovered.  */
       bool did_replace = evrp_folder.replace_uses_in (stmt);
+      gimple_stmt_iterator prev_gsi = gsi;
+      gsi_prev (&prev_gsi);
       if (fold_stmt (&gsi, follow_single_use_edges)
          || did_replace)
        {
@@ -191,6 +193,17 @@ evrp_dom_walker::before_dom_children (ba

       if (did_replace)
        {
+         /* If we wound up generating new stmts during folding
+            drop all their defs to VARYING.
+            ???  Properly process them.  */
+         if (gsi_end_p (prev_gsi))
+           prev_gsi = gsi_start_bb (bb);
+         while (gsi_stmt (prev_gsi) != gsi_stmt (gsi))
+           {
+             evrp_range_analyzer.get_vr_values ()
+               ->set_defs_to_varying (gsi_stmt (prev_gsi));
+             gsi_next (&prev_gsi);
+           }
          /* If we cleaned up EH information from the statement,
             remove EH edges.  */
          if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt))

the more "proper" fix requires keeping track of stmts already
processed (you don't want to re-process stmts, I ran into
"issues" when doing that for the same issue in DOM).  For
DOM I used the visited flag (see dom_opt_dom_walker::before_dom_children).

You might want to copy that handling.

Just give me a note if you want to work on that, otherwise I'll try to
queue it for somewhen this week.

Richard.

> jeff

Re: undefined behavior in value_range::equiv_add()?

[Jeff Law]

On 6/4/19 5:23 AM, Richard Biener wrote:
> On Tue, Jun 4, 2019 at 12:30 AM Jeff Law <law@redhat.com> wrote:
>>
>> On 6/3/19 7:13 AM, Aldy Hernandez wrote:
>>> On 5/31/19 5:00 AM, Richard Biener wrote:
>>>> On Fri, May 31, 2019 at 2:27 AM Jeff Law <law@redhat.com> wrote:
>>>>>
>>>>> On 5/29/19 10:20 AM, Aldy Hernandez wrote:
>>>>>> On 5/29/19 12:12 PM, Jeff Law wrote:
>>>>>>> On 5/29/19 9:58 AM, Aldy Hernandez wrote:
>>>>>>>> On 5/29/19 9:24 AM, Richard Biener wrote:
>>>>>>>>> On Wed, May 29, 2019 at 2:18 PM Aldy Hernandez <aldyh@redhat.com>
>>>>>>>>> wrote:
>>>>>>>>>>
>>>>>>>>>> As per the API, and the original documentation to value_range,
>>>>>>>>>> VR_UNDEFINED and VR_VARYING should never have equivalences.
>>>>>>>>>> However,
>>>>>>>>>> equiv_add is tacking on equivalences blindly, and there are various
>>>>>>>>>> regressions that happen if I fix this oversight.
>>>>>>>>>>
>>>>>>>>>> void
>>>>>>>>>> value_range::equiv_add (const_tree var,
>>>>>>>>>>                            const value_range *var_vr,
>>>>>>>>>>                            bitmap_obstack *obstack)
>>>>>>>>>> {
>>>>>>>>>>       if (!m_equiv)
>>>>>>>>>>         m_equiv = BITMAP_ALLOC (obstack);
>>>>>>>>>>       unsigned ver = SSA_NAME_VERSION (var);
>>>>>>>>>>       bitmap_set_bit (m_equiv, ver);
>>>>>>>>>>       if (var_vr && var_vr->m_equiv)
>>>>>>>>>>         bitmap_ior_into (m_equiv, var_vr->m_equiv);
>>>>>>>>>> }
>>>>>>>>>>
>>>>>>>>>> Is this a bug in the documentation / API, or is equiv_add incorrect
>>>>>>>>>> and
>>>>>>>>>> we should fix the fall-out elsewhere?
>>>>>>>>>
>>>>>>>>> I think this must have been crept in during the classification.
>>>>>>>>> If you
>>>>>>>>> go back to say GCC 7 you shouldn't see value-ranges with
>>>>>>>>> UNDEFINED/VARYING state in the lattice that have equivalences.
>>>>>>>>>
>>>>>>>>> It may not be easy to avoid with the new classy interface but we're
>>>>>>>>> certainly not tacking on them "blindly".  At least we're not
>>>>>>>>> supposed
>>>>>>>>> to.  As usual the intermediate state might be "broken" but
>>>>>>>>> intermediateness is not sth the new class "likes".
>>>>>>>>
>>>>>>>> It looks like extract_range_from_stmt (by virtue of
>>>>>>>> vrp_visit_assignment_or_call and then extract_range_from_ssa_name)
>>>>>>>> returns one of these intermediate ranges.  It would seem to me
>>>>>>>> that an
>>>>>>>> outward looking API method like vr_values::extract_range_from_stmt
>>>>>>>> shouldn't be returning inconsistent ranges.  Or are there no
>>>>>>>> guarantees
>>>>>>>> for value_ranges from within all of vr_values?
>>>>>>> ISTM that if we have an implementation constraint that says a
>>>>>>> VR_VARYING
>>>>>>> or VR_UNDEFINED range can't have equivalences, then we need to honor
>>>>>>> that at the minimum for anything returned by an external API.
>>>>>>> Returning
>>>>>>> an inconsistent state is bad.  I'd even state that we should try damn
>>>>>>> hard to avoid it in internal APIs as well.
>>>>>>
>>>>>> Agreed * 2.
>>>>>>
>>>>>>>
>>>>>>>>
>>>>>>>> Perhaps I should give a little background.  As part of your
>>>>>>>> value_range_base re-factoring last year, you mentioned that you
>>>>>>>> didn't
>>>>>>>> split out intersect like you did union because of time or
>>>>>>>> oversight.  I
>>>>>>>> have code to implement intersect (attached), for which I've
>>>>>>>> noticed that
>>>>>>>> I must leave equivalences intact, even when transitioning to
>>>>>>>> VR_UNDEFINED:
>>>>>>>>
>>>>>>>> [from the attached patch]
>>>>>>>> +  /* If THIS is varying we want to pick up equivalences from OTHER.
>>>>>>>> +     Just special-case this here rather than trying to fixup
>>>>>>>> after the
>>>>>>>> +     fact.  */
>>>>>>>> +  if (this->varying_p ())
>>>>>>>> +    this->deep_copy (other);
>>>>>>>> +  else if (this->undefined_p ())
>>>>>>>> +    /* ?? Leave any equivalences already present in an undefined.
>>>>>>>> +       This is technically not allowed, but we may get an in-flight
>>>>>>>> +       value_range in an intermediate state.  */
>>>>>>> Where/when does this happen?
>>>>>>
>>>>>> The above snippet is not currently in mainline.  It's in the patch I'm
>>>>>> proposing to clean up intersect.  It's just that while cleaning up
>>>>>> intersect I noticed that if we keep to the value_range API, we end up
>>>>>> clobbering an equivalence to a VR_UNDEFINED that we depend up
>>>>>> further up
>>>>>> the call chain.
>>>>>>
>>>>>> The reason it doesn't happen in mainline is because intersect_helper
>>>>>> bails early on an undefined, thus leaving the problematic equivalence
>>>>>> intact.
>>>>>>
>>>>>> You can see it in mainline though, with the following testcase:
>>>>>>
>>>>>> int f(int x)
>>>>>> {
>>>>>>    if (x != 0 && x != 1)
>>>>>>      return -2;
>>>>>>
>>>>>>    return !x;
>>>>>> }
>>>>>>
>>>>>> Break in evrp_range_analyzer::record_ranges_from_stmt() and see that
>>>>>> the
>>>>>> call to extract_range_from_stmt() returns a VR of undefined *WITH*
>>>>>> equivalences:
>>>>>>
>>>>>>        vr_values->extract_range_from_stmt (stmt, &taken_edge,
>>>>>> &output, &vr);
>>>>>>
>>>>>> This VR is later fed to update_value_range() and ultimately
>>>>>> intersect(),
>>>>>> which in mainline, leaves the equivalences alone, but IMO should
>>>>>> respect
>>>>>> that API and nuke them.
>>>>> So I think this is coming from extract_range_from_ssa_name:
>>>>>
>>>>>> void
>>>>>> vr_values::extract_range_from_ssa_name (value_range *vr, tree var)
>>>>>> {
>>>>>>    value_range *var_vr = get_value_range (var);
>>>>>>
>>>>>>    if (!var_vr->varying_p ())
>>>>>>      vr->deep_copy (var_vr);
>>>>>>    else
>>>>>>      vr->set (var);
>>>>>>
>>>>>>    vr->equiv_add (var, get_value_range (var), &vrp_equiv_obstack);
>>>>>> }
>>>>>
>>>>> Where we blindly add VAR to the equiv bitmap in the range.
>>>>>
>>>>> AFAICT gcc-7 has equivalent code, it's just not inside the class.
>>>>>
>>>>> I don't know what the fallout might be, but we could conditionalize the
>>>>> call to add_equivalence to avoid the inconsistent state.
>>>>
>>>> Well, the issue is that the equivalence _is_ there.  So above we
>>>> know that we never end up with VARYING but the deep_copy
>>>> can bring over UNDEFINED to us.  I guess we _could_ elide
>>>> the equiv adding then.  OTOH the equivalence does look
>>>> useful for predicate simplification which IIRC doesn't treat
>>>> UNDEFINED != x in a useful way.  Which would mean allowing
>>>> equivalences on UNDEFINED.  That somewhat makes sense
>>>> since UNDEFINED is bottom-most in the lattice and one up
>>>> (CONSTANT) we have equivalences while just on topmost
>>>> (VARYING) we do not.
>>>>
>>>> That said, I never liked equivalences - they are an odd way
>>>> to represent ranges intersected from multiple ranges thus
>>>> a way out of our too simplistic range representation.
>>>>
>>>> So lets fix this in a way avoiding testsuite fallout.  But please
>>>> not with special hacks in consumers.  Does guariding the
>>>> above equiv_add with !vr->undefined_p () fix things?
>>>
>>> Agreed.  I never suggested we add special hacks to intersect.  The
>>> two-liner was only to explain why equivalences in varying/undefined
>>> currently matter in intersect.
>>>
>>> Guarding the equiv_add causes regressions.  For example, for this simple
>>> testcase we incorrectly get rid of the final PHI:
>>>
>>> int f(int x)
>>> {
>>>   if (x != 0 && x != 1)
>>>     return -2;
>>>
>>>   return !x;
>>> }
>>>
>>> In the evrp dump we now see:
>>>
>>> Visiting PHI node: _3 = PHI <-2(3), _5(4)>
>>>     Argument #0 (3 -> 5 executable)
>>>         -2: int [-2, -2]
>>>     Argument #1 (4 -> 5 executable)
>>>         _5: UNDEFINED
>>> Meeting
>>>   int [-2, -2]
>>> and
>>>   UNDEFINED
>>> to
>>>   int [-2, -2]
>>>
>>> whereas before the change, argument #1 was:
>>>
>>>     Argument #1 (4 -> 5 executable)
>>>         _5: int [_5, _5]
>>>
>>> and the meeting result was VARYING.
>>>
>>> I *think* this starts somewhere up the call chain in update_value_range,
>>> which as I've described earlier, will no longer make a difference
>>> between UNDEFINED and UNDEFINED + equivalence.  This causes that when
>>> transitioning from UNDEFINED to UNDEFINED + equivalence, we actually
>>> transition to VARYING:
>>>
>>>  if (is_new)
>>>     {
>>>       if (old_vr->varying_p ())
>>>     {
>>>       new_vr->set_varying ();
>>>       is_new = false;
>>>     }
>>>       else if (new_vr->undefined_p ())
>>>     {
>>>       old_vr->set_varying ();
>>>       new_vr->set_varying ();
>>>       return true;
>>>     }
>>>
>>> Could someone better versed in this take a peek, please?  It's just a
>>> matter of applying the attached one-liner, and looking at "Visiting PHI"
>>> in the evrp dump.
>> As I mentioned in IRC.  I know what's going on here and see a path to
>> fix it.  Hoping to get a patch into my tester overnight, but life seems
>> to be getting in the way.
> 
> It's of course a latent issue.  One I fixed in DOMs use of the EVRP machinery.
> The following fixes it in a conservative way:
> 
> Index: gcc/gimple-ssa-evrp.c
> ===================================================================
> --- gcc/gimple-ssa-evrp.c       (revision 271904)
> +++ gcc/gimple-ssa-evrp.c       (working copy)
> @@ -175,6 +175,8 @@ evrp_dom_walker::before_dom_children (ba
> 
>        /* Try folding stmts with the VR discovered.  */
>        bool did_replace = evrp_folder.replace_uses_in (stmt);
> +      gimple_stmt_iterator prev_gsi = gsi;
> +      gsi_prev (&prev_gsi);
>        if (fold_stmt (&gsi, follow_single_use_edges)
>           || did_replace)
>         {
> @@ -191,6 +193,17 @@ evrp_dom_walker::before_dom_children (ba
> 
>        if (did_replace)
>         {
> +         /* If we wound up generating new stmts during folding
> +            drop all their defs to VARYING.
> +            ???  Properly process them.  */
> +         if (gsi_end_p (prev_gsi))
> +           prev_gsi = gsi_start_bb (bb);
> +         while (gsi_stmt (prev_gsi) != gsi_stmt (gsi))
> +           {
> +             evrp_range_analyzer.get_vr_values ()
> +               ->set_defs_to_varying (gsi_stmt (prev_gsi));
> +             gsi_next (&prev_gsi);
> +           }
>           /* If we cleaned up EH information from the statement,
>              remove EH edges.  */
>           if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt))
> 
> the more "proper" fix requires keeping track of stmts already
> processed (you don't want to re-process stmts, I ran into
> "issues" when doing that for the same issue in DOM).  For
> DOM I used the visited flag (see dom_opt_dom_walker::before_dom_children).
> 
> You might want to copy that handling.
> 
> Just give me a note if you want to work on that, otherwise I'll try to
> queue it for somewhen this week.Umm, I think you're working around a problem in the simplifier code
which creates SSA_NAMEs, leaving them in an VR_UNDEFINED state.

jeff

Re: undefined behavior in value_range::equiv_add()?

[Richard Biener]

On Tue, Jun 4, 2019 at 3:40 PM Jeff Law <law@redhat.com> wrote:
>
> On 6/4/19 5:23 AM, Richard Biener wrote:
> > On Tue, Jun 4, 2019 at 12:30 AM Jeff Law <law@redhat.com> wrote:
> >>
> >> On 6/3/19 7:13 AM, Aldy Hernandez wrote:
> >>> On 5/31/19 5:00 AM, Richard Biener wrote:
> >>>> On Fri, May 31, 2019 at 2:27 AM Jeff Law <law@redhat.com> wrote:
> >>>>>
> >>>>> On 5/29/19 10:20 AM, Aldy Hernandez wrote:
> >>>>>> On 5/29/19 12:12 PM, Jeff Law wrote:
> >>>>>>> On 5/29/19 9:58 AM, Aldy Hernandez wrote:
> >>>>>>>> On 5/29/19 9:24 AM, Richard Biener wrote:
> >>>>>>>>> On Wed, May 29, 2019 at 2:18 PM Aldy Hernandez <aldyh@redhat.com>
> >>>>>>>>> wrote:
> >>>>>>>>>>
> >>>>>>>>>> As per the API, and the original documentation to value_range,
> >>>>>>>>>> VR_UNDEFINED and VR_VARYING should never have equivalences.
> >>>>>>>>>> However,
> >>>>>>>>>> equiv_add is tacking on equivalences blindly, and there are various
> >>>>>>>>>> regressions that happen if I fix this oversight.
> >>>>>>>>>>
> >>>>>>>>>> void
> >>>>>>>>>> value_range::equiv_add (const_tree var,
> >>>>>>>>>>                            const value_range *var_vr,
> >>>>>>>>>>                            bitmap_obstack *obstack)
> >>>>>>>>>> {
> >>>>>>>>>>       if (!m_equiv)
> >>>>>>>>>>         m_equiv = BITMAP_ALLOC (obstack);
> >>>>>>>>>>       unsigned ver = SSA_NAME_VERSION (var);
> >>>>>>>>>>       bitmap_set_bit (m_equiv, ver);
> >>>>>>>>>>       if (var_vr && var_vr->m_equiv)
> >>>>>>>>>>         bitmap_ior_into (m_equiv, var_vr->m_equiv);
> >>>>>>>>>> }
> >>>>>>>>>>
> >>>>>>>>>> Is this a bug in the documentation / API, or is equiv_add incorrect
> >>>>>>>>>> and
> >>>>>>>>>> we should fix the fall-out elsewhere?
> >>>>>>>>>
> >>>>>>>>> I think this must have been crept in during the classification.
> >>>>>>>>> If you
> >>>>>>>>> go back to say GCC 7 you shouldn't see value-ranges with
> >>>>>>>>> UNDEFINED/VARYING state in the lattice that have equivalences.
> >>>>>>>>>
> >>>>>>>>> It may not be easy to avoid with the new classy interface but we're
> >>>>>>>>> certainly not tacking on them "blindly".  At least we're not
> >>>>>>>>> supposed
> >>>>>>>>> to.  As usual the intermediate state might be "broken" but
> >>>>>>>>> intermediateness is not sth the new class "likes".
> >>>>>>>>
> >>>>>>>> It looks like extract_range_from_stmt (by virtue of
> >>>>>>>> vrp_visit_assignment_or_call and then extract_range_from_ssa_name)
> >>>>>>>> returns one of these intermediate ranges.  It would seem to me
> >>>>>>>> that an
> >>>>>>>> outward looking API method like vr_values::extract_range_from_stmt
> >>>>>>>> shouldn't be returning inconsistent ranges.  Or are there no
> >>>>>>>> guarantees
> >>>>>>>> for value_ranges from within all of vr_values?
> >>>>>>> ISTM that if we have an implementation constraint that says a
> >>>>>>> VR_VARYING
> >>>>>>> or VR_UNDEFINED range can't have equivalences, then we need to honor
> >>>>>>> that at the minimum for anything returned by an external API.
> >>>>>>> Returning
> >>>>>>> an inconsistent state is bad.  I'd even state that we should try damn
> >>>>>>> hard to avoid it in internal APIs as well.
> >>>>>>
> >>>>>> Agreed * 2.
> >>>>>>
> >>>>>>>
> >>>>>>>>
> >>>>>>>> Perhaps I should give a little background.  As part of your
> >>>>>>>> value_range_base re-factoring last year, you mentioned that you
> >>>>>>>> didn't
> >>>>>>>> split out intersect like you did union because of time or
> >>>>>>>> oversight.  I
> >>>>>>>> have code to implement intersect (attached), for which I've
> >>>>>>>> noticed that
> >>>>>>>> I must leave equivalences intact, even when transitioning to
> >>>>>>>> VR_UNDEFINED:
> >>>>>>>>
> >>>>>>>> [from the attached patch]
> >>>>>>>> +  /* If THIS is varying we want to pick up equivalences from OTHER.
> >>>>>>>> +     Just special-case this here rather than trying to fixup
> >>>>>>>> after the
> >>>>>>>> +     fact.  */
> >>>>>>>> +  if (this->varying_p ())
> >>>>>>>> +    this->deep_copy (other);
> >>>>>>>> +  else if (this->undefined_p ())
> >>>>>>>> +    /* ?? Leave any equivalences already present in an undefined.
> >>>>>>>> +       This is technically not allowed, but we may get an in-flight
> >>>>>>>> +       value_range in an intermediate state.  */
> >>>>>>> Where/when does this happen?
> >>>>>>
> >>>>>> The above snippet is not currently in mainline.  It's in the patch I'm
> >>>>>> proposing to clean up intersect.  It's just that while cleaning up
> >>>>>> intersect I noticed that if we keep to the value_range API, we end up
> >>>>>> clobbering an equivalence to a VR_UNDEFINED that we depend up
> >>>>>> further up
> >>>>>> the call chain.
> >>>>>>
> >>>>>> The reason it doesn't happen in mainline is because intersect_helper
> >>>>>> bails early on an undefined, thus leaving the problematic equivalence
> >>>>>> intact.
> >>>>>>
> >>>>>> You can see it in mainline though, with the following testcase:
> >>>>>>
> >>>>>> int f(int x)
> >>>>>> {
> >>>>>>    if (x != 0 && x != 1)
> >>>>>>      return -2;
> >>>>>>
> >>>>>>    return !x;
> >>>>>> }
> >>>>>>
> >>>>>> Break in evrp_range_analyzer::record_ranges_from_stmt() and see that
> >>>>>> the
> >>>>>> call to extract_range_from_stmt() returns a VR of undefined *WITH*
> >>>>>> equivalences:
> >>>>>>
> >>>>>>        vr_values->extract_range_from_stmt (stmt, &taken_edge,
> >>>>>> &output, &vr);
> >>>>>>
> >>>>>> This VR is later fed to update_value_range() and ultimately
> >>>>>> intersect(),
> >>>>>> which in mainline, leaves the equivalences alone, but IMO should
> >>>>>> respect
> >>>>>> that API and nuke them.
> >>>>> So I think this is coming from extract_range_from_ssa_name:
> >>>>>
> >>>>>> void
> >>>>>> vr_values::extract_range_from_ssa_name (value_range *vr, tree var)
> >>>>>> {
> >>>>>>    value_range *var_vr = get_value_range (var);
> >>>>>>
> >>>>>>    if (!var_vr->varying_p ())
> >>>>>>      vr->deep_copy (var_vr);
> >>>>>>    else
> >>>>>>      vr->set (var);
> >>>>>>
> >>>>>>    vr->equiv_add (var, get_value_range (var), &vrp_equiv_obstack);
> >>>>>> }
> >>>>>
> >>>>> Where we blindly add VAR to the equiv bitmap in the range.
> >>>>>
> >>>>> AFAICT gcc-7 has equivalent code, it's just not inside the class.
> >>>>>
> >>>>> I don't know what the fallout might be, but we could conditionalize the
> >>>>> call to add_equivalence to avoid the inconsistent state.
> >>>>
> >>>> Well, the issue is that the equivalence _is_ there.  So above we
> >>>> know that we never end up with VARYING but the deep_copy
> >>>> can bring over UNDEFINED to us.  I guess we _could_ elide
> >>>> the equiv adding then.  OTOH the equivalence does look
> >>>> useful for predicate simplification which IIRC doesn't treat
> >>>> UNDEFINED != x in a useful way.  Which would mean allowing
> >>>> equivalences on UNDEFINED.  That somewhat makes sense
> >>>> since UNDEFINED is bottom-most in the lattice and one up
> >>>> (CONSTANT) we have equivalences while just on topmost
> >>>> (VARYING) we do not.
> >>>>
> >>>> That said, I never liked equivalences - they are an odd way
> >>>> to represent ranges intersected from multiple ranges thus
> >>>> a way out of our too simplistic range representation.
> >>>>
> >>>> So lets fix this in a way avoiding testsuite fallout.  But please
> >>>> not with special hacks in consumers.  Does guariding the
> >>>> above equiv_add with !vr->undefined_p () fix things?
> >>>
> >>> Agreed.  I never suggested we add special hacks to intersect.  The
> >>> two-liner was only to explain why equivalences in varying/undefined
> >>> currently matter in intersect.
> >>>
> >>> Guarding the equiv_add causes regressions.  For example, for this simple
> >>> testcase we incorrectly get rid of the final PHI:
> >>>
> >>> int f(int x)
> >>> {
> >>>   if (x != 0 && x != 1)
> >>>     return -2;
> >>>
> >>>   return !x;
> >>> }
> >>>
> >>> In the evrp dump we now see:
> >>>
> >>> Visiting PHI node: _3 = PHI <-2(3), _5(4)>
> >>>     Argument #0 (3 -> 5 executable)
> >>>         -2: int [-2, -2]
> >>>     Argument #1 (4 -> 5 executable)
> >>>         _5: UNDEFINED
> >>> Meeting
> >>>   int [-2, -2]
> >>> and
> >>>   UNDEFINED
> >>> to
> >>>   int [-2, -2]
> >>>
> >>> whereas before the change, argument #1 was:
> >>>
> >>>     Argument #1 (4 -> 5 executable)
> >>>         _5: int [_5, _5]
> >>>
> >>> and the meeting result was VARYING.
> >>>
> >>> I *think* this starts somewhere up the call chain in update_value_range,
> >>> which as I've described earlier, will no longer make a difference
> >>> between UNDEFINED and UNDEFINED + equivalence.  This causes that when
> >>> transitioning from UNDEFINED to UNDEFINED + equivalence, we actually
> >>> transition to VARYING:
> >>>
> >>>  if (is_new)
> >>>     {
> >>>       if (old_vr->varying_p ())
> >>>     {
> >>>       new_vr->set_varying ();
> >>>       is_new = false;
> >>>     }
> >>>       else if (new_vr->undefined_p ())
> >>>     {
> >>>       old_vr->set_varying ();
> >>>       new_vr->set_varying ();
> >>>       return true;
> >>>     }
> >>>
> >>> Could someone better versed in this take a peek, please?  It's just a
> >>> matter of applying the attached one-liner, and looking at "Visiting PHI"
> >>> in the evrp dump.
> >> As I mentioned in IRC.  I know what's going on here and see a path to
> >> fix it.  Hoping to get a patch into my tester overnight, but life seems
> >> to be getting in the way.
> >
> > It's of course a latent issue.  One I fixed in DOMs use of the EVRP machinery.
> > The following fixes it in a conservative way:
> >
> > Index: gcc/gimple-ssa-evrp.c
> > ===================================================================
> > --- gcc/gimple-ssa-evrp.c       (revision 271904)
> > +++ gcc/gimple-ssa-evrp.c       (working copy)
> > @@ -175,6 +175,8 @@ evrp_dom_walker::before_dom_children (ba
> >
> >        /* Try folding stmts with the VR discovered.  */
> >        bool did_replace = evrp_folder.replace_uses_in (stmt);
> > +      gimple_stmt_iterator prev_gsi = gsi;
> > +      gsi_prev (&prev_gsi);
> >        if (fold_stmt (&gsi, follow_single_use_edges)
> >           || did_replace)
> >         {
> > @@ -191,6 +193,17 @@ evrp_dom_walker::before_dom_children (ba
> >
> >        if (did_replace)
> >         {
> > +         /* If we wound up generating new stmts during folding
> > +            drop all their defs to VARYING.
> > +            ???  Properly process them.  */
> > +         if (gsi_end_p (prev_gsi))
> > +           prev_gsi = gsi_start_bb (bb);
> > +         while (gsi_stmt (prev_gsi) != gsi_stmt (gsi))
> > +           {
> > +             evrp_range_analyzer.get_vr_values ()
> > +               ->set_defs_to_varying (gsi_stmt (prev_gsi));
> > +             gsi_next (&prev_gsi);
> > +           }
> >           /* If we cleaned up EH information from the statement,
> >              remove EH edges.  */
> >           if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt))
> >
> > the more "proper" fix requires keeping track of stmts already
> > processed (you don't want to re-process stmts, I ran into
> > "issues" when doing that for the same issue in DOM).  For
> > DOM I used the visited flag (see dom_opt_dom_walker::before_dom_children).
> >
> > You might want to copy that handling.
> >
> > Just give me a note if you want to work on that, otherwise I'll try to
> > queue it for somewhen this week.Umm, I think you're working around a problem in the simplifier code
> which creates SSA_NAMEs, leaving them in an VR_UNDEFINED state.

But the simplifier is / can be just fold_stmt () - it doesn't know it
has to populate a
value-range lattice.  But yes, the VRP specific simplifier likely has
the same issue
in the EVRP context (in SSA VRP all "new" SSA names are beyond the
static allocated
array and get VARYING automatically).  So I think handling the "new
stmts" in the
propagator is correct?

Richard.

> jeff

Re: undefined behavior in value_range::equiv_add()?

[Jeff Law]

On 6/4/19 9:04 AM, Richard Biener wrote:
> On Tue, Jun 4, 2019 at 3:40 PM Jeff Law <law@redhat.com> wrote:
>> 
>> On 6/4/19 5:23 AM, Richard Biener wrote:
>>> On Tue, Jun 4, 2019 at 12:30 AM Jeff Law <law@redhat.com> wrote:
>>>> 
>>>> On 6/3/19 7:13 AM, Aldy Hernandez wrote:
>>>>> On 5/31/19 5:00 AM, Richard Biener wrote:
>>>>>> On Fri, May 31, 2019 at 2:27 AM Jeff Law <law@redhat.com>
>>>>>> wrote:
>>>>>>> 
>>>>>>> On 5/29/19 10:20 AM, Aldy Hernandez wrote:
>>>>>>>> On 5/29/19 12:12 PM, Jeff Law wrote:
>>>>>>>>> On 5/29/19 9:58 AM, Aldy Hernandez wrote:
>>>>>>>>>> On 5/29/19 9:24 AM, Richard Biener wrote:
>>>>>>>>>>> On Wed, May 29, 2019 at 2:18 PM Aldy Hernandez
>>>>>>>>>>> <aldyh@redhat.com> wrote:
>>>>>>>>>>>> 
>>>>>>>>>>>> As per the API, and the original documentation
>>>>>>>>>>>> to value_range, VR_UNDEFINED and VR_VARYING
>>>>>>>>>>>> should never have equivalences. However, 
>>>>>>>>>>>> equiv_add is tacking on equivalences blindly,
>>>>>>>>>>>> and there are various regressions that happen
>>>>>>>>>>>> if I fix this oversight.
>>>>>>>>>>>> 
>>>>>>>>>>>> void value_range::equiv_add (const_tree var, 
>>>>>>>>>>>> const value_range *var_vr, bitmap_obstack
>>>>>>>>>>>> *obstack) { if (!m_equiv) m_equiv =
>>>>>>>>>>>> BITMAP_ALLOC (obstack); unsigned ver =
>>>>>>>>>>>> SSA_NAME_VERSION (var); bitmap_set_bit
>>>>>>>>>>>> (m_equiv, ver); if (var_vr && var_vr->m_equiv) 
>>>>>>>>>>>> bitmap_ior_into (m_equiv, var_vr->m_equiv); }
>>>>>>>>>>>> 
>>>>>>>>>>>> Is this a bug in the documentation / API, or is
>>>>>>>>>>>> equiv_add incorrect and we should fix the
>>>>>>>>>>>> fall-out elsewhere?
>>>>>>>>>>> 
>>>>>>>>>>> I think this must have been crept in during the
>>>>>>>>>>> classification. If you go back to say GCC 7 you
>>>>>>>>>>> shouldn't see value-ranges with UNDEFINED/VARYING
>>>>>>>>>>> state in the lattice that have equivalences.
>>>>>>>>>>> 
>>>>>>>>>>> It may not be easy to avoid with the new classy
>>>>>>>>>>> interface but we're certainly not tacking on them
>>>>>>>>>>> "blindly".  At least we're not supposed to.  As
>>>>>>>>>>> usual the intermediate state might be "broken"
>>>>>>>>>>> but intermediateness is not sth the new class
>>>>>>>>>>> "likes".
>>>>>>>>>> 
>>>>>>>>>> It looks like extract_range_from_stmt (by virtue
>>>>>>>>>> of vrp_visit_assignment_or_call and then
>>>>>>>>>> extract_range_from_ssa_name) returns one of these
>>>>>>>>>> intermediate ranges.  It would seem to me that an 
>>>>>>>>>> outward looking API method like
>>>>>>>>>> vr_values::extract_range_from_stmt shouldn't be
>>>>>>>>>> returning inconsistent ranges.  Or are there no 
>>>>>>>>>> guarantees for value_ranges from within all of
>>>>>>>>>> vr_values?
>>>>>>>>> ISTM that if we have an implementation constraint
>>>>>>>>> that says a VR_VARYING or VR_UNDEFINED range can't
>>>>>>>>> have equivalences, then we need to honor that at the
>>>>>>>>> minimum for anything returned by an external API. 
>>>>>>>>> Returning an inconsistent state is bad.  I'd even
>>>>>>>>> state that we should try damn hard to avoid it in
>>>>>>>>> internal APIs as well.
>>>>>>>> 
>>>>>>>> Agreed * 2.
>>>>>>>> 
>>>>>>>>> 
>>>>>>>>>> 
>>>>>>>>>> Perhaps I should give a little background.  As part
>>>>>>>>>> of your value_range_base re-factoring last year,
>>>>>>>>>> you mentioned that you didn't split out intersect
>>>>>>>>>> like you did union because of time or oversight.
>>>>>>>>>> I have code to implement intersect (attached), for
>>>>>>>>>> which I've noticed that I must leave equivalences
>>>>>>>>>> intact, even when transitioning to VR_UNDEFINED:
>>>>>>>>>> 
>>>>>>>>>> [from the attached patch] +  /* If THIS is varying
>>>>>>>>>> we want to pick up equivalences from OTHER. +
>>>>>>>>>> Just special-case this here rather than trying to
>>>>>>>>>> fixup after the +     fact.  */ +  if
>>>>>>>>>> (this->varying_p ()) +    this->deep_copy (other); 
>>>>>>>>>> +  else if (this->undefined_p ()) +    /* ?? Leave
>>>>>>>>>> any equivalences already present in an undefined. +
>>>>>>>>>> This is technically not allowed, but we may get an
>>>>>>>>>> in-flight +       value_range in an intermediate
>>>>>>>>>> state.  */
>>>>>>>>> Where/when does this happen?
>>>>>>>> 
>>>>>>>> The above snippet is not currently in mainline.  It's
>>>>>>>> in the patch I'm proposing to clean up intersect.  It's
>>>>>>>> just that while cleaning up intersect I noticed that if
>>>>>>>> we keep to the value_range API, we end up clobbering an
>>>>>>>> equivalence to a VR_UNDEFINED that we depend up further
>>>>>>>> up the call chain.
>>>>>>>> 
>>>>>>>> The reason it doesn't happen in mainline is because
>>>>>>>> intersect_helper bails early on an undefined, thus
>>>>>>>> leaving the problematic equivalence intact.
>>>>>>>> 
>>>>>>>> You can see it in mainline though, with the following
>>>>>>>> testcase:
>>>>>>>> 
>>>>>>>> int f(int x) { if (x != 0 && x != 1) return -2;
>>>>>>>> 
>>>>>>>> return !x; }
>>>>>>>> 
>>>>>>>> Break in evrp_range_analyzer::record_ranges_from_stmt()
>>>>>>>> and see that the call to extract_range_from_stmt()
>>>>>>>> returns a VR of undefined *WITH* equivalences:
>>>>>>>> 
>>>>>>>> vr_values->extract_range_from_stmt (stmt, &taken_edge, 
>>>>>>>> &output, &vr);
>>>>>>>> 
>>>>>>>> This VR is later fed to update_value_range() and
>>>>>>>> ultimately intersect(), which in mainline, leaves the
>>>>>>>> equivalences alone, but IMO should respect that API and
>>>>>>>> nuke them.
>>>>>>> So I think this is coming from
>>>>>>> extract_range_from_ssa_name:
>>>>>>> 
>>>>>>>> void vr_values::extract_range_from_ssa_name
>>>>>>>> (value_range *vr, tree var) { value_range *var_vr =
>>>>>>>> get_value_range (var);
>>>>>>>> 
>>>>>>>> if (!var_vr->varying_p ()) vr->deep_copy (var_vr); 
>>>>>>>> else vr->set (var);
>>>>>>>> 
>>>>>>>> vr->equiv_add (var, get_value_range (var),
>>>>>>>> &vrp_equiv_obstack); }
>>>>>>> 
>>>>>>> Where we blindly add VAR to the equiv bitmap in the
>>>>>>> range.
>>>>>>> 
>>>>>>> AFAICT gcc-7 has equivalent code, it's just not inside
>>>>>>> the class.
>>>>>>> 
>>>>>>> I don't know what the fallout might be, but we could
>>>>>>> conditionalize the call to add_equivalence to avoid the
>>>>>>> inconsistent state.
>>>>>> 
>>>>>> Well, the issue is that the equivalence _is_ there.  So
>>>>>> above we know that we never end up with VARYING but the
>>>>>> deep_copy can bring over UNDEFINED to us.  I guess we
>>>>>> _could_ elide the equiv adding then.  OTOH the equivalence
>>>>>> does look useful for predicate simplification which IIRC
>>>>>> doesn't treat UNDEFINED != x in a useful way.  Which would
>>>>>> mean allowing equivalences on UNDEFINED.  That somewhat
>>>>>> makes sense since UNDEFINED is bottom-most in the lattice
>>>>>> and one up (CONSTANT) we have equivalences while just on
>>>>>> topmost (VARYING) we do not.
>>>>>> 
>>>>>> That said, I never liked equivalences - they are an odd
>>>>>> way to represent ranges intersected from multiple ranges
>>>>>> thus a way out of our too simplistic range representation.
>>>>>> 
>>>>>> So lets fix this in a way avoiding testsuite fallout.  But
>>>>>> please not with special hacks in consumers.  Does guariding
>>>>>> the above equiv_add with !vr->undefined_p () fix things?
>>>>> 
>>>>> Agreed.  I never suggested we add special hacks to intersect.
>>>>> The two-liner was only to explain why equivalences in
>>>>> varying/undefined currently matter in intersect.
>>>>> 
>>>>> Guarding the equiv_add causes regressions.  For example, for
>>>>> this simple testcase we incorrectly get rid of the final
>>>>> PHI:
>>>>> 
>>>>> int f(int x) { if (x != 0 && x != 1) return -2;
>>>>> 
>>>>> return !x; }
>>>>> 
>>>>> In the evrp dump we now see:
>>>>> 
>>>>> Visiting PHI node: _3 = PHI <-2(3), _5(4)> Argument #0 (3 ->
>>>>> 5 executable) -2: int [-2, -2] Argument #1 (4 -> 5
>>>>> executable) _5: UNDEFINED Meeting int [-2, -2] and UNDEFINED 
>>>>> to int [-2, -2]
>>>>> 
>>>>> whereas before the change, argument #1 was:
>>>>> 
>>>>> Argument #1 (4 -> 5 executable) _5: int [_5, _5]
>>>>> 
>>>>> and the meeting result was VARYING.
>>>>> 
>>>>> I *think* this starts somewhere up the call chain in
>>>>> update_value_range, which as I've described earlier, will no
>>>>> longer make a difference between UNDEFINED and UNDEFINED +
>>>>> equivalence.  This causes that when transitioning from
>>>>> UNDEFINED to UNDEFINED + equivalence, we actually transition
>>>>> to VARYING:
>>>>> 
>>>>> if (is_new) { if (old_vr->varying_p ()) { new_vr->set_varying
>>>>> (); is_new = false; } else if (new_vr->undefined_p ()) { 
>>>>> old_vr->set_varying (); new_vr->set_varying (); return true; 
>>>>> }
>>>>> 
>>>>> Could someone better versed in this take a peek, please?
>>>>> It's just a matter of applying the attached one-liner, and
>>>>> looking at "Visiting PHI" in the evrp dump.
>>>> As I mentioned in IRC.  I know what's going on here and see a
>>>> path to fix it.  Hoping to get a patch into my tester
>>>> overnight, but life seems to be getting in the way.
>>> 
>>> It's of course a latent issue.  One I fixed in DOMs use of the
>>> EVRP machinery. The following fixes it in a conservative way:
>>> 
>>> Index: gcc/gimple-ssa-evrp.c 
>>> ===================================================================
>>>
>>> 
--- gcc/gimple-ssa-evrp.c       (revision 271904)
>>> +++ gcc/gimple-ssa-evrp.c       (working copy) @@ -175,6 +175,8
>>> @@ evrp_dom_walker::before_dom_children (ba
>>> 
>>> /* Try folding stmts with the VR discovered.  */ bool did_replace
>>> = evrp_folder.replace_uses_in (stmt); +      gimple_stmt_iterator
>>> prev_gsi = gsi; +      gsi_prev (&prev_gsi); if (fold_stmt (&gsi,
>>> follow_single_use_edges) || did_replace) { @@ -191,6 +193,17 @@
>>> evrp_dom_walker::before_dom_children (ba
>>> 
>>> if (did_replace) { +         /* If we wound up generating new
>>> stmts during folding +            drop all their defs to
>>> VARYING. +            ???  Properly process them.  */ +
>>> if (gsi_end_p (prev_gsi)) +           prev_gsi = gsi_start_bb
>>> (bb); +         while (gsi_stmt (prev_gsi) != gsi_stmt (gsi)) +
>>> { +             evrp_range_analyzer.get_vr_values () +
>>> ->set_defs_to_varying (gsi_stmt (prev_gsi)); +
>>> gsi_next (&prev_gsi); +           } /* If we cleaned up EH
>>> information from the statement, remove EH edges.  */ if
>>> (maybe_clean_or_replace_eh_stmt (old_stmt, stmt))
>>> 
>>> the more "proper" fix requires keeping track of stmts already 
>>> processed (you don't want to re-process stmts, I ran into 
>>> "issues" when doing that for the same issue in DOM).  For DOM I
>>> used the visited flag (see
>>> dom_opt_dom_walker::before_dom_children).
>>> 
>>> You might want to copy that handling.
>>> 
>>> Just give me a note if you want to work on that, otherwise I'll
>>> try to queue it for somewhen this week.Umm, I think you're
>>> working around a problem in the simplifier code
>> which creates SSA_NAMEs, leaving them in an VR_UNDEFINED state.
> 
> But the simplifier is / can be just fold_stmt () - it doesn't know
> it has to populate a value-range lattice.  But yes, the VRP specific
> simplifier likely has the same issue in the EVRP context (in SSA VRP
> all "new" SSA names are beyond the static allocated array and get
> VARYING automatically).  So I think handling the "new stmts" in the 
> propagator is correct?
I didn't realize we had so many calls to make_ssa_name in gimple-fold.
I was primarily concerned with the ones in the evrp simplification
engine which are easy to fix in-place.  Looking at gimple-fold.c I agree
we do need to address the walking problem.

I'm not sure we can drop to varying though -- my first twiddle of this
did precisely that, but that'll likely regress vrp47 where we know the
resultant range after simplification is just [0,1].

Ideally we wouldn't have the simplifiers creating new names or we'd have
a more robust mechanism for identifying when we've created a new name
and doing the right thing.  I suspect whatever we do here right now is
going to be a bandaid and as long as we keep creating new names in the
simplifier we're likely going to be coming back and applying more bandaids.

jeff

Re: undefined behavior in value_range::equiv_add()?

[Richard Biener]

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

On Wed, Jun 5, 2019 at 11:12 PM Jeff Law <law@redhat.com> wrote:
>
> On 6/4/19 9:04 AM, Richard Biener wrote:
> > On Tue, Jun 4, 2019 at 3:40 PM Jeff Law <law@redhat.com> wrote:
> >>
> >> On 6/4/19 5:23 AM, Richard Biener wrote:
> >>> On Tue, Jun 4, 2019 at 12:30 AM Jeff Law <law@redhat.com> wrote:
> >>>>
> >>>> On 6/3/19 7:13 AM, Aldy Hernandez wrote:
> >>>>> On 5/31/19 5:00 AM, Richard Biener wrote:
> >>>>>> On Fri, May 31, 2019 at 2:27 AM Jeff Law <law@redhat.com>
> >>>>>> wrote:
> >>>>>>>
> >>>>>>> On 5/29/19 10:20 AM, Aldy Hernandez wrote:
> >>>>>>>> On 5/29/19 12:12 PM, Jeff Law wrote:
> >>>>>>>>> On 5/29/19 9:58 AM, Aldy Hernandez wrote:
> >>>>>>>>>> On 5/29/19 9:24 AM, Richard Biener wrote:
> >>>>>>>>>>> On Wed, May 29, 2019 at 2:18 PM Aldy Hernandez
> >>>>>>>>>>> <aldyh@redhat.com> wrote:
> >>>>>>>>>>>>
> >>>>>>>>>>>> As per the API, and the original documentation
> >>>>>>>>>>>> to value_range, VR_UNDEFINED and VR_VARYING
> >>>>>>>>>>>> should never have equivalences. However,
> >>>>>>>>>>>> equiv_add is tacking on equivalences blindly,
> >>>>>>>>>>>> and there are various regressions that happen
> >>>>>>>>>>>> if I fix this oversight.
> >>>>>>>>>>>>
> >>>>>>>>>>>> void value_range::equiv_add (const_tree var,
> >>>>>>>>>>>> const value_range *var_vr, bitmap_obstack
> >>>>>>>>>>>> *obstack) { if (!m_equiv) m_equiv =
> >>>>>>>>>>>> BITMAP_ALLOC (obstack); unsigned ver =
> >>>>>>>>>>>> SSA_NAME_VERSION (var); bitmap_set_bit
> >>>>>>>>>>>> (m_equiv, ver); if (var_vr && var_vr->m_equiv)
> >>>>>>>>>>>> bitmap_ior_into (m_equiv, var_vr->m_equiv); }
> >>>>>>>>>>>>
> >>>>>>>>>>>> Is this a bug in the documentation / API, or is
> >>>>>>>>>>>> equiv_add incorrect and we should fix the
> >>>>>>>>>>>> fall-out elsewhere?
> >>>>>>>>>>>
> >>>>>>>>>>> I think this must have been crept in during the
> >>>>>>>>>>> classification. If you go back to say GCC 7 you
> >>>>>>>>>>> shouldn't see value-ranges with UNDEFINED/VARYING
> >>>>>>>>>>> state in the lattice that have equivalences.
> >>>>>>>>>>>
> >>>>>>>>>>> It may not be easy to avoid with the new classy
> >>>>>>>>>>> interface but we're certainly not tacking on them
> >>>>>>>>>>> "blindly".  At least we're not supposed to.  As
> >>>>>>>>>>> usual the intermediate state might be "broken"
> >>>>>>>>>>> but intermediateness is not sth the new class
> >>>>>>>>>>> "likes".
> >>>>>>>>>>
> >>>>>>>>>> It looks like extract_range_from_stmt (by virtue
> >>>>>>>>>> of vrp_visit_assignment_or_call and then
> >>>>>>>>>> extract_range_from_ssa_name) returns one of these
> >>>>>>>>>> intermediate ranges.  It would seem to me that an
> >>>>>>>>>> outward looking API method like
> >>>>>>>>>> vr_values::extract_range_from_stmt shouldn't be
> >>>>>>>>>> returning inconsistent ranges.  Or are there no
> >>>>>>>>>> guarantees for value_ranges from within all of
> >>>>>>>>>> vr_values?
> >>>>>>>>> ISTM that if we have an implementation constraint
> >>>>>>>>> that says a VR_VARYING or VR_UNDEFINED range can't
> >>>>>>>>> have equivalences, then we need to honor that at the
> >>>>>>>>> minimum for anything returned by an external API.
> >>>>>>>>> Returning an inconsistent state is bad.  I'd even
> >>>>>>>>> state that we should try damn hard to avoid it in
> >>>>>>>>> internal APIs as well.
> >>>>>>>>
> >>>>>>>> Agreed * 2.
> >>>>>>>>
> >>>>>>>>>
> >>>>>>>>>>
> >>>>>>>>>> Perhaps I should give a little background.  As part
> >>>>>>>>>> of your value_range_base re-factoring last year,
> >>>>>>>>>> you mentioned that you didn't split out intersect
> >>>>>>>>>> like you did union because of time or oversight.
> >>>>>>>>>> I have code to implement intersect (attached), for
> >>>>>>>>>> which I've noticed that I must leave equivalences
> >>>>>>>>>> intact, even when transitioning to VR_UNDEFINED:
> >>>>>>>>>>
> >>>>>>>>>> [from the attached patch] +  /* If THIS is varying
> >>>>>>>>>> we want to pick up equivalences from OTHER. +
> >>>>>>>>>> Just special-case this here rather than trying to
> >>>>>>>>>> fixup after the +     fact.  */ +  if
> >>>>>>>>>> (this->varying_p ()) +    this->deep_copy (other);
> >>>>>>>>>> +  else if (this->undefined_p ()) +    /* ?? Leave
> >>>>>>>>>> any equivalences already present in an undefined. +
> >>>>>>>>>> This is technically not allowed, but we may get an
> >>>>>>>>>> in-flight +       value_range in an intermediate
> >>>>>>>>>> state.  */
> >>>>>>>>> Where/when does this happen?
> >>>>>>>>
> >>>>>>>> The above snippet is not currently in mainline.  It's
> >>>>>>>> in the patch I'm proposing to clean up intersect.  It's
> >>>>>>>> just that while cleaning up intersect I noticed that if
> >>>>>>>> we keep to the value_range API, we end up clobbering an
> >>>>>>>> equivalence to a VR_UNDEFINED that we depend up further
> >>>>>>>> up the call chain.
> >>>>>>>>
> >>>>>>>> The reason it doesn't happen in mainline is because
> >>>>>>>> intersect_helper bails early on an undefined, thus
> >>>>>>>> leaving the problematic equivalence intact.
> >>>>>>>>
> >>>>>>>> You can see it in mainline though, with the following
> >>>>>>>> testcase:
> >>>>>>>>
> >>>>>>>> int f(int x) { if (x != 0 && x != 1) return -2;
> >>>>>>>>
> >>>>>>>> return !x; }
> >>>>>>>>
> >>>>>>>> Break in evrp_range_analyzer::record_ranges_from_stmt()
> >>>>>>>> and see that the call to extract_range_from_stmt()
> >>>>>>>> returns a VR of undefined *WITH* equivalences:
> >>>>>>>>
> >>>>>>>> vr_values->extract_range_from_stmt (stmt, &taken_edge,
> >>>>>>>> &output, &vr);
> >>>>>>>>
> >>>>>>>> This VR is later fed to update_value_range() and
> >>>>>>>> ultimately intersect(), which in mainline, leaves the
> >>>>>>>> equivalences alone, but IMO should respect that API and
> >>>>>>>> nuke them.
> >>>>>>> So I think this is coming from
> >>>>>>> extract_range_from_ssa_name:
> >>>>>>>
> >>>>>>>> void vr_values::extract_range_from_ssa_name
> >>>>>>>> (value_range *vr, tree var) { value_range *var_vr =
> >>>>>>>> get_value_range (var);
> >>>>>>>>
> >>>>>>>> if (!var_vr->varying_p ()) vr->deep_copy (var_vr);
> >>>>>>>> else vr->set (var);
> >>>>>>>>
> >>>>>>>> vr->equiv_add (var, get_value_range (var),
> >>>>>>>> &vrp_equiv_obstack); }
> >>>>>>>
> >>>>>>> Where we blindly add VAR to the equiv bitmap in the
> >>>>>>> range.
> >>>>>>>
> >>>>>>> AFAICT gcc-7 has equivalent code, it's just not inside
> >>>>>>> the class.
> >>>>>>>
> >>>>>>> I don't know what the fallout might be, but we could
> >>>>>>> conditionalize the call to add_equivalence to avoid the
> >>>>>>> inconsistent state.
> >>>>>>
> >>>>>> Well, the issue is that the equivalence _is_ there.  So
> >>>>>> above we know that we never end up with VARYING but the
> >>>>>> deep_copy can bring over UNDEFINED to us.  I guess we
> >>>>>> _could_ elide the equiv adding then.  OTOH the equivalence
> >>>>>> does look useful for predicate simplification which IIRC
> >>>>>> doesn't treat UNDEFINED != x in a useful way.  Which would
> >>>>>> mean allowing equivalences on UNDEFINED.  That somewhat
> >>>>>> makes sense since UNDEFINED is bottom-most in the lattice
> >>>>>> and one up (CONSTANT) we have equivalences while just on
> >>>>>> topmost (VARYING) we do not.
> >>>>>>
> >>>>>> That said, I never liked equivalences - they are an odd
> >>>>>> way to represent ranges intersected from multiple ranges
> >>>>>> thus a way out of our too simplistic range representation.
> >>>>>>
> >>>>>> So lets fix this in a way avoiding testsuite fallout.  But
> >>>>>> please not with special hacks in consumers.  Does guariding
> >>>>>> the above equiv_add with !vr->undefined_p () fix things?
> >>>>>
> >>>>> Agreed.  I never suggested we add special hacks to intersect.
> >>>>> The two-liner was only to explain why equivalences in
> >>>>> varying/undefined currently matter in intersect.
> >>>>>
> >>>>> Guarding the equiv_add causes regressions.  For example, for
> >>>>> this simple testcase we incorrectly get rid of the final
> >>>>> PHI:
> >>>>>
> >>>>> int f(int x) { if (x != 0 && x != 1) return -2;
> >>>>>
> >>>>> return !x; }
> >>>>>
> >>>>> In the evrp dump we now see:
> >>>>>
> >>>>> Visiting PHI node: _3 = PHI <-2(3), _5(4)> Argument #0 (3 ->
> >>>>> 5 executable) -2: int [-2, -2] Argument #1 (4 -> 5
> >>>>> executable) _5: UNDEFINED Meeting int [-2, -2] and UNDEFINED
> >>>>> to int [-2, -2]
> >>>>>
> >>>>> whereas before the change, argument #1 was:
> >>>>>
> >>>>> Argument #1 (4 -> 5 executable) _5: int [_5, _5]
> >>>>>
> >>>>> and the meeting result was VARYING.
> >>>>>
> >>>>> I *think* this starts somewhere up the call chain in
> >>>>> update_value_range, which as I've described earlier, will no
> >>>>> longer make a difference between UNDEFINED and UNDEFINED +
> >>>>> equivalence.  This causes that when transitioning from
> >>>>> UNDEFINED to UNDEFINED + equivalence, we actually transition
> >>>>> to VARYING:
> >>>>>
> >>>>> if (is_new) { if (old_vr->varying_p ()) { new_vr->set_varying
> >>>>> (); is_new = false; } else if (new_vr->undefined_p ()) {
> >>>>> old_vr->set_varying (); new_vr->set_varying (); return true;
> >>>>> }
> >>>>>
> >>>>> Could someone better versed in this take a peek, please?
> >>>>> It's just a matter of applying the attached one-liner, and
> >>>>> looking at "Visiting PHI" in the evrp dump.
> >>>> As I mentioned in IRC.  I know what's going on here and see a
> >>>> path to fix it.  Hoping to get a patch into my tester
> >>>> overnight, but life seems to be getting in the way.
> >>>
> >>> It's of course a latent issue.  One I fixed in DOMs use of the
> >>> EVRP machinery. The following fixes it in a conservative way:
> >>>
> >>> Index: gcc/gimple-ssa-evrp.c
> >>> ===================================================================
> >>>
> >>>
> --- gcc/gimple-ssa-evrp.c       (revision 271904)
> >>> +++ gcc/gimple-ssa-evrp.c       (working copy) @@ -175,6 +175,8
> >>> @@ evrp_dom_walker::before_dom_children (ba
> >>>
> >>> /* Try folding stmts with the VR discovered.  */ bool did_replace
> >>> = evrp_folder.replace_uses_in (stmt); +      gimple_stmt_iterator
> >>> prev_gsi = gsi; +      gsi_prev (&prev_gsi); if (fold_stmt (&gsi,
> >>> follow_single_use_edges) || did_replace) { @@ -191,6 +193,17 @@
> >>> evrp_dom_walker::before_dom_children (ba
> >>>
> >>> if (did_replace) { +         /* If we wound up generating new
> >>> stmts during folding +            drop all their defs to
> >>> VARYING. +            ???  Properly process them.  */ +
> >>> if (gsi_end_p (prev_gsi)) +           prev_gsi = gsi_start_bb
> >>> (bb); +         while (gsi_stmt (prev_gsi) != gsi_stmt (gsi)) +
> >>> { +             evrp_range_analyzer.get_vr_values () +
> >>> ->set_defs_to_varying (gsi_stmt (prev_gsi)); +
> >>> gsi_next (&prev_gsi); +           } /* If we cleaned up EH
> >>> information from the statement, remove EH edges.  */ if
> >>> (maybe_clean_or_replace_eh_stmt (old_stmt, stmt))
> >>>
> >>> the more "proper" fix requires keeping track of stmts already
> >>> processed (you don't want to re-process stmts, I ran into
> >>> "issues" when doing that for the same issue in DOM).  For DOM I
> >>> used the visited flag (see
> >>> dom_opt_dom_walker::before_dom_children).
> >>>
> >>> You might want to copy that handling.
> >>>
> >>> Just give me a note if you want to work on that, otherwise I'll
> >>> try to queue it for somewhen this week.Umm, I think you're
> >>> working around a problem in the simplifier code
> >> which creates SSA_NAMEs, leaving them in an VR_UNDEFINED state.
> >
> > But the simplifier is / can be just fold_stmt () - it doesn't know
> > it has to populate a value-range lattice.  But yes, the VRP specific
> > simplifier likely has the same issue in the EVRP context (in SSA VRP
> > all "new" SSA names are beyond the static allocated array and get
> > VARYING automatically).  So I think handling the "new stmts" in the
> > propagator is correct?
> I didn't realize we had so many calls to make_ssa_name in gimple-fold.

It's not only those literally appearing but when match.pd simplifies
to an expression that requires a temporary we create one as well.

> I was primarily concerned with the ones in the evrp simplification
> engine which are easy to fix in-place.  Looking at gimple-fold.c I agree
> we do need to address the walking problem.
>
> I'm not sure we can drop to varying though -- my first twiddle of this
> did precisely that, but that'll likely regress vrp47 where we know the
> resultant range after simplification is just [0,1].

Of course we do not need to drop the original LHS to VARYING, only
the defs we didn't already visit.

> Ideally we wouldn't have the simplifiers creating new names or we'd have
> a more robust mechanism for identifying when we've created a new name
> and doing the right thing.  I suspect whatever we do here right now is
> going to be a bandaid and as long as we keep creating new names in the
> simplifier we're likely going to be coming back and applying more bandaids.

Re-visiting the stmts would be possible if we'd split registering ranges derived
from uses of a stmt from those of defs (IIRC I had incomplete patches to do that
when trying to derive X != 0 from Y / X because otherwise we miscompile stuff).

Meanwhile I have bootstrapped / tested the following which does the VARYING
thing.

Applied to trunk.  I think we need to backport this since this is a latent
wrong-code issue.  We can see to improve things on the trunk incrementally.

Richard.

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

        * vr-values.c (vr_values::extract_range_from_ssa_name): Do not
        put equivalences on UNDEFINED ranges.
        * gimple-ssa-evrp.c (evrp_dom_walker::before_dom_children):
        Make sure to drop defs of stmts added during simplification
        to VARYING.



> jeff
>
>

[-- Attachment #2: p2-2 --]
[-- Type: application/octet-stream, Size: 2060 bytes --]

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

	* vr-values.c (vr_values::extract_range_from_ssa_name): Do not
	put equivalences on UNDEFINED ranges.
	* gimple-ssa-evrp.c (evrp_dom_walker::before_dom_children):
	Make sure to drop defs of stmts added during simplification
	to VARYING.

Index: gcc/vr-values.c
===================================================================
--- gcc/vr-values.c	(revision 271951)
+++ gcc/vr-values.c	(working copy)
@@ -719,7 +719,8 @@ vr_values::extract_range_from_ssa_name (
   else
     vr->set (var);
 
-  vr->equiv_add (var, get_value_range (var), &vrp_equiv_obstack);
+  if (!vr->undefined_p ())
+    vr->equiv_add (var, get_value_range (var), &vrp_equiv_obstack);
 }
 
 /* Extract range information from a binary expression OP0 CODE OP1 based on
Index: gcc/gimple-ssa-evrp.c
===================================================================
--- gcc/gimple-ssa-evrp.c	(revision 271951)
+++ gcc/gimple-ssa-evrp.c	(working copy)
@@ -175,6 +175,8 @@ evrp_dom_walker::before_dom_children (ba
 
       /* Try folding stmts with the VR discovered.  */
       bool did_replace = evrp_folder.replace_uses_in (stmt);
+      gimple_stmt_iterator prev_gsi = gsi;
+      gsi_prev (&prev_gsi);
       if (fold_stmt (&gsi, follow_single_use_edges)
 	  || did_replace)
 	{
@@ -191,6 +193,21 @@ evrp_dom_walker::before_dom_children (ba
 
       if (did_replace)
 	{
+	  /* If we wound up generating new stmts during folding
+	     drop all their defs to VARYING.  We can't easily
+	     process them because we've already instantiated
+	     ranges on uses on STMT that only hold after it.  */
+	  if (gsi_end_p (prev_gsi))
+	    prev_gsi = gsi_start_bb (bb);
+	  else
+	    gsi_next (&prev_gsi);
+	  while (gsi_stmt (prev_gsi) != gsi_stmt (gsi))
+	    {
+	      evrp_range_analyzer.get_vr_values ()
+		->set_defs_to_varying (gsi_stmt (prev_gsi));
+	      gsi_next (&prev_gsi);
+	    }
+
 	  /* If we cleaned up EH information from the statement,
 	     remove EH edges.  */
 	  if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt))

Re: undefined behavior in value_range::equiv_add()?

[Jeff Law]

On 6/6/19 1:31 AM, Richard Biener wrote:
[ Big snip ]

> 
>> I was primarily concerned with the ones in the evrp simplification
>> engine which are easy to fix in-place.  Looking at gimple-fold.c I agree
>> we do need to address the walking problem.
>>
>> I'm not sure we can drop to varying though -- my first twiddle of this
>> did precisely that, but that'll likely regress vrp47 where we know the
>> resultant range after simplification is just [0,1].
> 
> Of course we do not need to drop the original LHS to VARYING, only
> the defs we didn't already visit.
I was referring to the newly created def.  There's a case (seen in vrp47
IIRC) where the new temporary has a known range [0,1] and we need to
know that for subsequent simplifications.  But if your change passes
regression testing, then we're still picking that up properly.


> 
>> Ideally we wouldn't have the simplifiers creating new names or we'd have
>> a more robust mechanism for identifying when we've created a new name
>> and doing the right thing.  I suspect whatever we do here right now is
>> going to be a bandaid and as long as we keep creating new names in the
>> simplifier we're likely going to be coming back and applying more bandaids.
> 
> Re-visiting the stmts would be possible if we'd split registering ranges derived
> from uses of a stmt from those of defs (IIRC I had incomplete patches to do that
> when trying to derive X != 0 from Y / X because otherwise we miscompile stuff).
> 
> Meanwhile I have bootstrapped / tested the following which does the VARYING
> thing.
> 
> Applied to trunk.  I think we need to backport this since this is a latent
> wrong-code issue.  We can see to improve things on the trunk incrementally.
Works for me.

jeff

Re: undefined behavior in value_range::equiv_add()?

[Aldy Hernandez]

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

> Meanwhile I have bootstrapped / tested the following which does the VARYING
> thing.
> 
> Applied to trunk.  I think we need to backport this since this is a latent
> wrong-code issue.  We can see to improve things on the trunk incrementally.

Folks, thanks so much for taking care of this.

After Richard's patch, my value_range_base::intersect patch no longer 
fails on vrp47, and no longer requires a special-case for undefined.

The attached patch splits out the intersect code into a value_range_base 
version, as we have for union_.

OK?

Aldy

[-- Attachment #2: curr.patch --]
[-- Type: text/x-patch, Size: 8171 bytes --]

gcc/

	* tree-vrp.h (value_range_base::intersect): New.
	(value_range::intersect_helper): Move from here...
	(value_range_base::intersect_helper): ...to here.
	* tree-vrp.c (value_range::intersect_helper): Rename to...
	(value_range_base::intersect_helper): ...this, and rewrite to
	return a value instead of modifying THIS in place.
	Also, move equivalence handling...
	(value_range::intersect): ...here, while calling intersect_helper.
	* gimple-fold.c (size_must_be_zero_p): Use value_range_base when
	calling intersect.
	* gimple-ssa-evrp-analyze.c (ecord_ranges_from_incoming_edge):
	Same.
	* vr-values.c (vrp_evaluate_conditional_warnv_with_ops): Same.

diff --git a/gcc/gimple-fold.c b/gcc/gimple-fold.c
index b3e931744f8..8b8331eb555 100644
--- a/gcc/gimple-fold.c
+++ b/gcc/gimple-fold.c
@@ -684,10 +684,10 @@ size_must_be_zero_p (tree size)
   /* Compute the value of SSIZE_MAX, the largest positive value that
      can be stored in ssize_t, the signed counterpart of size_t.  */
   wide_int ssize_max = wi::lshift (wi::one (prec), prec - 1) - 1;
-  value_range valid_range (VR_RANGE,
-			   build_int_cst (type, 0),
-			   wide_int_to_tree (type, ssize_max));
-  value_range vr;
+  value_range_base valid_range (VR_RANGE,
+				build_int_cst (type, 0),
+				wide_int_to_tree (type, ssize_max));
+  value_range_base vr;
   get_range_info (size, vr);
   vr.intersect (&valid_range);
   return vr.zero_p ();
diff --git a/gcc/gimple-ssa-evrp-analyze.c b/gcc/gimple-ssa-evrp-analyze.c
index bb4e2d6e798..4c68af847e1 100644
--- a/gcc/gimple-ssa-evrp-analyze.c
+++ b/gcc/gimple-ssa-evrp-analyze.c
@@ -210,9 +210,10 @@ evrp_range_analyzer::record_ranges_from_incoming_edge (basic_block bb)
 	         getting first [64, +INF] and then ~[0, 0] from
 		 conditions like (s & 0x3cc0) == 0).  */
 	      value_range *old_vr = get_value_range (vrs[i].first);
-	      value_range tem (old_vr->kind (), old_vr->min (), old_vr->max ());
+	      value_range_base tem (old_vr->kind (), old_vr->min (),
+				    old_vr->max ());
 	      tem.intersect (vrs[i].second);
-	      if (tem.equal_p (*old_vr, /*ignore_equivs=*/true))
+	      if (tem.equal_p (*old_vr))
 		continue;
 	      push_value_range (vrs[i].first, vrs[i].second);
 	      if (is_fallthru
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index fdda64c30d5..d94de2b22ee 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -6020,30 +6020,26 @@ intersect_ranges (enum value_range_kind *vr0type,
 }
 
 
-/* Intersect the two value-ranges *VR0 and *VR1 and store the result
-   in *VR0.  This may not be the smallest possible such range.  */
+/* Helper for the intersection operation for value ranges.  Given two
+   value ranges VR0 and VR1, return the intersection of the two
+   ranges.  This may not be the smallest possible such range.  */
 
-void
-value_range::intersect_helper (value_range *vr0, const value_range *vr1)
+value_range_base
+value_range_base::intersect_helper (const value_range_base *vr0,
+				    const value_range_base *vr1)
 {
   /* If either range is VR_VARYING the other one wins.  */
   if (vr1->varying_p ())
-    return;
+    return *vr0;
   if (vr0->varying_p ())
-    {
-      vr0->deep_copy (vr1);
-      return;
-    }
+    return *vr1;
 
   /* When either range is VR_UNDEFINED the resulting range is
      VR_UNDEFINED, too.  */
   if (vr0->undefined_p ())
-    return;
+    return *vr0;
   if (vr1->undefined_p ())
-    {
-      vr0->set_undefined ();
-      return;
-    }
+    return *vr1;
 
   value_range_kind vr0type = vr0->kind ();
   tree vr0min = vr0->min ();
@@ -6053,28 +6049,34 @@ value_range::intersect_helper (value_range *vr0, const value_range *vr1)
   /* Make sure to canonicalize the result though as the inversion of a
      VR_RANGE can still be a VR_RANGE.  Work on a temporary so we can
      fall back to vr0 when this turns things to varying.  */
-  value_range tem;
+  value_range_base tem;
   tem.set_and_canonicalize (vr0type, vr0min, vr0max);
   /* If that failed, use the saved original VR0.  */
   if (tem.varying_p ())
-    return;
-  vr0->update (tem.kind (), tem.min (), tem.max ());
+    return *vr0;
 
-  /* If the result is VR_UNDEFINED there is no need to mess with
-     the equivalencies.  */
-  if (vr0->undefined_p ())
-    return;
+  return tem;
+}
 
-  /* The resulting set of equivalences for range intersection is the union of
-     the two sets.  */
-  if (vr0->m_equiv && vr1->m_equiv && vr0->m_equiv != vr1->m_equiv)
-    bitmap_ior_into (vr0->m_equiv, vr1->m_equiv);
-  else if (vr1->m_equiv && !vr0->m_equiv)
+void
+value_range_base::intersect (const value_range_base *other)
+{
+  if (dump_file && (dump_flags & TDF_DETAILS))
     {
-      /* All equivalence bitmaps are allocated from the same obstack.  So
-	 we can use the obstack associated with VR to allocate vr0->equiv.  */
-      vr0->m_equiv = BITMAP_ALLOC (vr1->m_equiv->obstack);
-      bitmap_copy (m_equiv, vr1->m_equiv);
+      fprintf (dump_file, "Intersecting\n  ");
+      dump_value_range (dump_file, this);
+      fprintf (dump_file, "\nand\n  ");
+      dump_value_range (dump_file, other);
+      fprintf (dump_file, "\n");
+    }
+
+  *this = intersect_helper (this, other);
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "to\n  ");
+      dump_value_range (dump_file, this);
+      fprintf (dump_file, "\n");
     }
 }
 
@@ -6089,7 +6091,36 @@ value_range::intersect (const value_range *other)
       dump_value_range (dump_file, other);
       fprintf (dump_file, "\n");
     }
-  intersect_helper (this, other);
+
+  /* If THIS is varying we want to pick up equivalences from OTHER.
+     Just special-case this here rather than trying to fixup after the
+     fact.  */
+  if (this->varying_p ())
+    this->deep_copy (other);
+  else
+    {
+      value_range_base tem = intersect_helper (this, other);
+      this->update (tem.kind (), tem.min (), tem.max ());
+
+      /* If the result is VR_UNDEFINED there is no need to mess with
+	 equivalencies.  */
+      if (!undefined_p ())
+	{
+	  /* The resulting set of equivalences for range intersection
+	     is the union of the two sets.  */
+	  if (m_equiv && other->m_equiv && m_equiv != other->m_equiv)
+	    bitmap_ior_into (m_equiv, other->m_equiv);
+	  else if (other->m_equiv && !m_equiv)
+	    {
+	      /* All equivalence bitmaps are allocated from the same
+		 obstack.  So we can use the obstack associated with
+		 VR to allocate this->m_equiv.  */
+	      m_equiv = BITMAP_ALLOC (other->m_equiv->obstack);
+	      bitmap_copy (m_equiv, other->m_equiv);
+	    }
+	}
+    }
+
   if (dump_file && (dump_flags & TDF_DETAILS))
     {
       fprintf (dump_file, "to\n  ");
diff --git a/gcc/tree-vrp.h b/gcc/tree-vrp.h
index 435df4227f7..c0801ff8041 100644
--- a/gcc/tree-vrp.h
+++ b/gcc/tree-vrp.h
@@ -62,6 +62,7 @@ public:
   void set_undefined ();
 
   void union_ (const value_range_base *);
+  void intersect (const value_range_base *);
 
   bool operator== (const value_range_base &) const /* = delete */;
   bool operator!= (const value_range_base &) const /* = delete */;
@@ -80,6 +81,8 @@ protected:
   void check ();
   static value_range_base union_helper (const value_range_base *,
 					const value_range_base *);
+  static value_range_base intersect_helper (const value_range_base *,
+					    const value_range_base *);
 
   enum value_range_kind m_kind;
 
@@ -144,7 +147,6 @@ class GTY((user)) value_range : public value_range_base
   /* Deep-copies bitmap argument.  */
   void set_equiv (bitmap);
   void check ();
-  void intersect_helper (value_range *, const value_range *);
 
   /* Set of SSA names whose value ranges are equivalent to this one.
      This set is only valid when TYPE is VR_RANGE or VR_ANTI_RANGE.  */
diff --git a/gcc/vr-values.c b/gcc/vr-values.c
index 9e58cbf7b2a..d3653e80789 100644
--- a/gcc/vr-values.c
+++ b/gcc/vr-values.c
@@ -2357,7 +2357,7 @@ vr_values::vrp_evaluate_conditional_warnv_with_ops (enum tree_code code,
 	}
       else
 	{
-	  value_range vro, vri;
+	  value_range_base vro, vri;
 	  if (code == GT_EXPR || code == GE_EXPR)
 	    {
 	      vro.set (VR_ANTI_RANGE, TYPE_MIN_VALUE (TREE_TYPE (op0)), x);

Re: undefined behavior in value_range::equiv_add()?

[Jeff Law]

On 6/6/19 4:11 PM, Aldy Hernandez wrote:
>> Meanwhile I have bootstrapped / tested the following which does the VARYING
>>
>> thing.
>>
>> Applied to trunk.  I think we need to backport this since this is a latent
>>
>> wrong-code issue.  We can see to improve things on the trunk incrementally.
>>
> 
> Folks, thanks so much for taking care of this.
> 
> After Richard's patch, my value_range_base::intersect patch no longer
> fails on vrp47, and no longer requires a special-case for undefined.
> 
> The attached patch splits out the intersect code into a value_range_base
> version, as we have for union_.
> 
> OK?
> 
> Aldy
> 
> curr.patch
> 
> gcc/
> 
> 	* tree-vrp.h (value_range_base::intersect): New.
> 	(value_range::intersect_helper): Move from here...
> 	(value_range_base::intersect_helper): ...to here.
> 	* tree-vrp.c (value_range::intersect_helper): Rename to...
> 	(value_range_base::intersect_helper): ...this, and rewrite to
> 	return a value instead of modifying THIS in place.
> 	Also, move equivalence handling...
> 	(value_range::intersect): ...here, while calling intersect_helper.
> 	* gimple-fold.c (size_must_be_zero_p): Use value_range_base when
> 	calling intersect.
> 	* gimple-ssa-evrp-analyze.c (ecord_ranges_from_incoming_edge):
> 	Same.
> 	* vr-values.c (vrp_evaluate_conditional_warnv_with_ops): Same.
OK
jeff

Re: undefined behavior in value_range::equiv_add()?

[Jeff Law]

On 5/29/19 7:24 AM, Richard Biener wrote:
> On Wed, May 29, 2019 at 2:18 PM Aldy Hernandez <aldyh@redhat.com> wrote:
>>
>> As per the API, and the original documentation to value_range,
>> VR_UNDEFINED and VR_VARYING should never have equivalences.  However,
>> equiv_add is tacking on equivalences blindly, and there are various
>> regressions that happen if I fix this oversight.
>>
>> void
>> value_range::equiv_add (const_tree var,
>>                         const value_range *var_vr,
>>                         bitmap_obstack *obstack)
>> {
>>    if (!m_equiv)
>>      m_equiv = BITMAP_ALLOC (obstack);
>>    unsigned ver = SSA_NAME_VERSION (var);
>>    bitmap_set_bit (m_equiv, ver);
>>    if (var_vr && var_vr->m_equiv)
>>      bitmap_ior_into (m_equiv, var_vr->m_equiv);
>> }
>>
>> Is this a bug in the documentation / API, or is equiv_add incorrect and
>> we should fix the fall-out elsewhere?
> 
> I think this must have been crept in during the classification.  If you
> go back to say GCC 7 you shouldn't see value-ranges with
> UNDEFINED/VARYING state in the lattice that have equivalences.
> 
> It may not be easy to avoid with the new classy interface but we're
> certainly not tacking on them "blindly".  At least we're not supposed
> to.  As usual the intermediate state might be "broken" but
> intermediateness is not sth the new class "likes".
I don't remember changing anything (behavior-wise) in this space.  If I
did it certainly wasn't intentional.

Given the code in gcc-7 looks like this:


> static void
> add_equivalence (bitmap *equiv, const_tree var)
> {
>   unsigned ver = SSA_NAME_VERSION (var);
>   value_range *vr = get_value_range (var);
> 
>   if (*equiv == NULL)
>     *equiv = BITMAP_ALLOC (&vrp_equiv_obstack);
>   bitmap_set_bit (*equiv, ver);
>   if (vr && vr->equiv)
>     bitmap_ior_into (*equiv, vr->equiv);
> }

I suspect we need to look up the call chain.


Jeff