[RFC/PATCH] updating global ranges and their effect on __builtin_unreachable code

[Andrew MacLeod]

On 6/7/21 3:25 AM, Richard Biener wrote:
> On Wed, Jun 2, 2021 at 2:53 PM Andrew MacLeod <amacleod@redhat.com> wrote:
>> On 6/2/21 7:52 AM, Richard Biener wrote:
>>> On Wed, Jun 2, 2021 at 12:34 PM Aldy Hernandez via Gcc-patches
>>> <gcc-patches@gcc.gnu.org> wrote:
>>>> We've been having "issues" in our branch when exporting to the global
>>>> space ranges that take into account previously known ranges
>>>> (SSA_NAME_RANGE_INFO, etc).  For the longest time we had the export
>>>> feature turned off because it had the potential of removing
>>>> __builtin_unreachable code early in the pipeline.  This was causing one
>>>> or two tests to fail.
>>>>
>>>> I finally got fed up, and investigated why.
>>>>
>>>> Take the following code:
>>>>
>>>>      i_4 = somerandom ();
>>>>      if (i_4 < 0)
>>>>        goto <bb 3>; [INV]
>>>>      else
>>>>        goto <bb 4>; [INV]
>>>>
>>>>      <bb 3> :
>>>>      __builtin_unreachable ();
>>>>
>>>>      <bb 4> :
>>>>
>>>> It turns out that both legacy evrp and VRP have code that notices the
>>>> above pattern and sets the *global* range for i_4 to [0,MAX].  That is,
>>>> the range for i_4 is set, not at BB4, but at the definition site.  See
>>>> uses of assert_unreachable_fallthru_edge_p() for details.
>>>>
>>>> This global range causes subsequent passes (VRP1 in the testcase below),
>>>> to remove the checks and the __builtin_unreachable code altogether.
>>>>
>>>> // pr80776-1.c
>>>> int somerandom (void);
>>>> void
>>>> Foo (void)
>>>> {
>>>>      int i = somerandom ();
>>>>      if (! (0 <= i))
>>>>        __builtin_unreachable ();
>>>>      if (! (0 <= i && i <= 999999))
>>>>        __builtin_unreachable ();
>>>>      sprintf (number, "%d", i);
>>>> }
>>>>
>>>> This means that by the time the -Wformat-overflow warning runs, the
>>>> above sprintf has been left unguarded, and a bogus warning is issued.
>>>>
>>>> Currently the above test does not warn, but that's because of an
>>>> oversight in export_global_ranges().  This function is disregarding
>>>> known global ranges (SSA_NAME_RANGE_INFO and SSA_NAME_PTR_INFO) and only
>>>> setting ranges the ranger knows about.
>>>>
>>>> For the above test the IL is:
>>>>
>>>>      <bb 2> :
>>>>      i_4 = somerandom ();
>>>>      if (i_4 < 0)
>>>>        goto <bb 3>; [INV]
>>>>      else
>>>>        goto <bb 4>; [INV]
>>>>
>>>>      <bb 3> :
>>>>      __builtin_unreachable ();
>>>>
>>>>      <bb 4> :
>>>>      i.0_1 = (unsigned int) i_4;
>>>>      if (i.0_1 > 999999)
>>>>        goto <bb 5>; [INV]
>>>>      else
>>>>        goto <bb 6>; [INV]
>>>>
>>>>      <bb 5> :
>>>>      __builtin_unreachable ();
>>>>
>>>>      <bb 6> :
>>>>      _7 = __builtin___sprintf_chk (&number, 1, 7, "%d", i_4);
>>>>
>>>>
>>>> Legacy evrp has determined that the range for i_4 is [0,MAX] per my
>>>> analysis above, but ranger has no known range for i_4 at the definition
>>>> site.  So at export_global_ranges time, ranger leaves the [0,MAX] alone.
>>>>
>>>> OTOH, evrp sets the global range at the definition for i.0_1 to
>>>> [0,999999] per the same unreachable feature.  However, ranger has
>>>> correctly determined that the range for i.0_1 at the definition is
>>>> [0,MAX], which it then proceeds to export.  Since the current
>>>> export_global_ranges (mistakenly) does not take into account previous
>>>> global ranges, the ranges in the global tables end up like this:
>>>>
>>>> i_4: [0, MAX]
>>>> i.0_1: [0, MAX]
>>>>
>>>> This causes the first unreachable block to be removed in VRP1, but the
>>>> second one to remain.  Later VRP can determine that i_4 in the sprintf
>>>> call is [0,999999], and no warning is issued.
>>>>
>>>> But... the missing bogus warning is due to current export_global_ranges
>>>> ignoring SSA_NAME_RANGE_INFO and friends, something which I'd like to
>>>> fix.  However, fixing this, gets us back to:
>>>>
>>>> i_4: [0, MAX]
>>>> i.0_1: [0, 999999]
>>>>
>>>> Which means, we'll be back to removing the unreachable blocks and
>>>> issuing a warning in pr80776-1.c (like we have been since the beginning
>>>> of time).
>>>>
>>>> The attached patch fixes export_global_ranges to the expected behavior,
>>>> and adds the previous XFAIL to pr80776-1.c, while documenting why this
>>>> warning is issued in the first place.
>>>>
>>>> Once legacy evrp is removed, this won't be an issue, as ranges in the IL
>>>> will tell the truth.  However, this will mean that we will no longer
>>>> remove the first __builtin_unreachable combo.  But ISTM, that would be
>>>> correct behavior ??.
>>>>
>>>> BTW, in addition to this patch we could explore removing the
>>>> assert_unreachable_fallthru_edge_p() use in the evrp_analyzer, since it
>>>> is no longer needed to get the warnings in the testcases in the original
>>>> PR correctly (gcc.dg/pr80776-[12].c).
>>> But the whole point of all this singing and dancing is not to make
>>> warnings but to be able to implement assert (); or assume (); that
>>> will result in no code but optimization based on the assumption.
>>>
>>> That means that all the checks guarding __builtin_unreachable ()
>>> should be removed at the GIMPLE level - just not too early
>>> to preserve range info on the variables participating in the
>>> guarding condition.
>>>
>>> So yes, it sounds fragile but instead it's carefully architected.  Heh.
>>>
>>> In particular it is designed so that early optimization leaves those
>>> unreachable () around (for later LTO consumption and inlining, etc.
>>> to be able to re-create the ranges) whilst VRP1 / DOM will end up
>>> eliminating them.  I think we have testcases that verify said behavior,
>>> namely optimize out range checks based on the assertions - maybe missed
>>> the case where this only happens after inlining (important for your friendly
>>> C++ abstraction hell), and the unreachable()s gone.
>>>
>>> Please make sure to not break that.
>> Let me see if I understand...  we want to leave builtin_unreachable
>> around until a certain point in compilation, and then remove them?
>>
>> It seems to me that either
>>
>>    A) a builtin_unreachable () provides useful information,( ie,
>> information that isn't otherwise obvious, and would therefore stay in
>> the IL and not be eliminated by the various optimizations until it is..
>> ). OR
>>
>>    B )its telling us something is we can already figure out, in which
>> case we will naturally eliminate the branches leading to it, and then it
>> goes away on its own.
>>
>> By that standard, any builtin_unreachable that makes it late into the
>> optimization cycle is useful... So can't we just leave those until
>> whatever point it is we decide the information they provide is no longer
>> needed, and then simply drop them?  Rewrite any branch to an unreachable
>> so that its truly unreachable, and then the next cfg cleanup makes them
>> all go away?  That could be part of a late/final VRP or a pass of its own.
>>
>> This whole checking to see if they are there seems fragile, because it
>> doesn't tell us whether they are useful or not..
> It's a combination of A and B.  It's A) until after IPA and after IPA the
> information is transitioned to range information on the SSA names
> which is then persistent (but it for example does not survive all
> IPA optimizations - definitely not LTO streaming for example).  So
> we're transitioning from a if (a) __builtin_unreachable () representation
> of the useful information to representing it by on-the-side info
> (SSA_NAME_RANGE_INFO)
> on 'a'.
>
> That should work fine with ranger as well I think - now, what was fragile
> was that the way the if (a) __builtin_unreachable () IL was preserved
> was simply that there's a single EVRP pass before IPA only and the
> way it is (was) structured makes sure that once we reflect the IL on
> the range info of 'a' it is not used (in the same EVRP pass) to elide
> the condition and nothing does (did) that before VRP1 either.
>
> Richard.

OK, lets see if I follow. The problem is that if we do eliminate the if 
and __builtin_unreachable too early, LTO streaming is likely to/might 
lose the information? and maybe some of the other IPA passes will not 
maintain the ssa_name_range_info data and thus also lose the info.

So once IPA is done, we'd be free to do eliminate at will when they 
aren't useful any morer?     And if I continue to follow that logic, 
then ranger shouldn't start with global information from the 
SSA_NAME_RANGE_INFO until post-IPA... then its free to pick up that info 
and eliminate anything it can.

At least until IPA and LTO are 100% range propagators :-)  so in theory, 
we could have a flag for post-ipa that allows us to pick better 
starting  global ranges when they are available.   we could wrap that up 
with the enable_ranger() call.. checks to see what pass we're in and if 
post-ipa enables global access?  or is there such a query already available?

Andrew

PS Ah, and now that I re-read, i think we're both saying the same thing? 
:-)  so it boils down to how do we check post-ipa.

Is there any movement to making LTO maintain any range info it currently 
loses?  Maybe this is an opportunity :-)  I know it maintains some, 
because it was part of the reason we dont use globals now