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