Re: [PATCH] middle-end IFN_ASSUME support [PR106654]

[Andrew MacLeod <amacleod@redhat.com>]

On 10/10/22 04:54, Jakub Jelinek via Gcc-patches wrote:
> Hi!
>
> My earlier patches gimplify the simplest non-side-effects assumptions
> into if (cond) ; else __builtin_unreachable (); and throw the rest
> on the floor.
> The following patch attempts to do something with the rest too.
> For -O0, it actually throws even the simplest assumptions on the floor,
> we don't expect optimizations and the assumptions are there to allow
> optimizations.  Otherwise, it keeps the handling of the simplest
> assumptions as is, and otherwise arranges for the assumptions to be
> visible in the IL as
>    .ASSUME (_Z2f4i._assume.0, i_1(D));
> call where there is an artificial function like:
> bool _Z2f4i._assume.0 (int i)
> {
>    bool _2;
>
>    <bb 2> [local count: 1073741824]:
>    _2 = i_1(D) == 43;
>    return _2;
>
> }
> with the semantics that there is UB unless the assumption function
> would return true.
>
> Aldy, could ranger handle this?  If it sees .ASSUME call,
> walk the body of such function from the edge(s) to exit with the
> assumption that the function returns true, so above set _2 [true, true]
> and from there derive that i_1(D) [43, 43] and then map the argument
> in the assumption function to argument passed to IFN_ASSUME (note,
> args there are shifted by 1)?


Ranger GORI component could assume the return value is [1,1] and work 
backwards from there. Single basic blocks would be trivial. The problem 
becomes when there are multiple blocks.   The gori engine has no real 
restriction other than it works from within a basic block only

I see no reason we couldn't wire something up that continues propagating 
values out the top of the block evaluating things for more complicated 
cases.  you would end up with a set of ranges for names which are the 
"maximal" possible range based on the restriction that the return value 
is [1,1].


> During gimplification it actually gimplifies it into
>    D.2591 = .ASSUME ();
>    if (D.2591 != 0) goto <D.2593>; else goto <D.2592>;
>    <D.2593>:
>    {
>      i = i + 1;
>      D.2591 = i == 44;
>    }
>    <D.2592>:
>    .ASSUME (D.2591);
> with the condition wrapped into a GIMPLE_BIND (I admit the above isn't
> extra clean but it is just something to hold it from gimplifier until
> gimple low pass; it reassembles if (condition_never_true) { cond; };


What we really care about is what the SSA form looks like.. thats what 
ranger will deal with.

Is this function inlined?  If it isn't then you'd need LTO/IPA to 
propagate the ranges we calculated above for the function. Or some 
special pass that reads assumes, does the processing you mention above 
and applies it?  Is that what you are thinking?

Looking at assume7.C, I see:

int bar (int x)
{
   <bb 2> [local count: 1073741824]:
   .ASSUME (_Z3bari._assume.0, x_1(D));
   return x_1(D);

And:

bool _Z3bari._assume.0 (int x)
{
   bool _2;

   <bb 2> [local count: 1073741824]:
   _2 = x_1(D) == 42;
   return _2;


Using the above approach, GORI could tell you that if _2 is [1,1] that 
x_1 must be [42,42].

If you are parsing that ASSUME, you could presumably match things pu and 
we could make x_1 have a range of [42,42] in bar() at that call.

this would require a bit of processing in fold_using_range for handling 
function calls, checking for this case and so on, but quite doable.

looking at the more complicated case for

bool _Z3bazi._assume.0 (int x)

it seems that the answer is determines without processing most of the 
function. ie:, work from the bottom up:

   <bb 5> [local count: 670631318]:
   _8 = x_3 == 43;                       x_3 = [43,43]

   <bb 6> [local count: 1073741824]:
   # _1 = PHI <0(2), _8(5)>              _8 = [1,1]  2->6 cant happen
   return _1;                            _1 = [1,1]

you only care about x, so as soon as you find a result that that, you'd 
actually be done.   However, I can imagine cases where you do need to go 
all the way back to the top of the assume function.. and combine values. Ie

bool assume (int x, int y)
{
   if (y > 10)
     return x == 2;
   return x > 20;
}

   <bb 2> [local count: 1073741824]:
   if (y_2(D) > 10)
     goto <bb 3>; [34.00%]
   else
     goto <bb 4>; [66.00%]

   <bb 3> [local count: 365072224]:
   _5 = x_3(D) == 2;                    x_3 = [2,2]
   goto <bb 5>; [100.00%]

   <bb 4> [local count: 708669601]:
   _4 = x_3(D) > 20;                    x_3 = [21, +INF]

   <bb 5> [local count: 1073741824]:
   # _1 = PHI <_5(3), _4(4)>          _5 = [1,1], _4 = [1,1]

   return _1;

And we'd have a range of [2,2][21, +INF]
if you wanted to be able to plug values of Y in, things would get more 
complicated, but the framework would all be there.


OK, enough pontificating,   it wouldn't be ranger, but yes, you could 
wire GORI into a pass which evaluates what we think the range of a set 
of inputs would be if we return 1.  I don't think It would be very 
difficult, just a bit of work to work the IL in reverse.  And then you 
should be able to wire in a range update for those parameters in 
fold_using_range (or wherever else I suppose) with a little more work.

It seems to me that if you were to "optimize" the function via this new 
pass,  assuming 1 was returned,  you could probably eliminate a lot of 
the extraneous code..   for what thats worth.

Can the assume function produce more than one assumption you care about?

Andrew