On 6/4/19 9:04 AM, Richard Biener wrote:
> On Tue, Jun 4, 2019 at 3:40 PM Jeff Law <l...@redhat.com> wrote:
>>
>> On 6/4/19 5:23 AM, Richard Biener wrote:
>>> On Tue, Jun 4, 2019 at 12:30 AM Jeff Law <l...@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 <l...@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
>>>>>>>>>>> <al...@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
