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

[Jakub Jelinek <jakub@redhat.com>]

On Tue, Oct 11, 2022 at 02:05:52PM -0400, Andrew MacLeod wrote:
> > 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.

Sure.

> Is this function inlined?  If it isn't then you'd need LTO/IPA to propagate

Never (the code is not supposed to be actually executed at runtime ever,
it is purely as if, if this function would be executed, then it would return
true, otherwise it would be UB).  But the goal is of course to inline stuff
into it and optimize the function even post IPA.

> 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?

The options would be to evaluate it each time ranger processes .ASSUME,
or to perform this backwards range propagation somewhere late during post
IPA optimizations of the cfun->assume_function and remember it somewhere
(e.g. in SSA_NAME_RANGE_INFO of the default defs of the params) and then
when visiting .ASSUME just look those up.  I think the latter is better,
we'd do it only once - the assumption that the function returns true after
the assume function itself is optimized will always be the same.
It could be a separate pass (gated on fun->assume_function, so done only
for them) somewhere shortly before expansion to RTL (which is what isn't
done and nothing later for those), or could be done say in VRP2 or some
other existing late pass.

> 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.

If we cache the range info for the assume_function arguments the above way
on SSA_NAME_RANGE_INFO, then you'd just see .ASSUME call and for (n+1)th
argument find nth argument of the 1st argument FUNCTION_DECL's
DECL_ARGUMENTS, ssa_default_def (DECL_STRUCT_FUNCTION (assume_fndecl), parm)
and just union the current range of (n+1)th argument with
SSA_NAME_RANGE_INFO of the ssa_default_def (if non-NULL).
> 
> 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.

Yeah.  Note, it is fine to handle say single block assume functions (after
optimizations) first and improve incrementally later, the goal is that
people actually see useful optimizations with simpler (but not simplest)
assume conditions, so they don't say they aren't completely useless, and if
they come up with something more complex that we don't handle yet, they
can file enhancement requests.  Of course, trying to walk all the bbs
backwards would be nicer, though even then it is important to be primarily
correct and so punting on anything we can't handle is fine (e.g. if there
are loops etc.).

> 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?

The assume function can have many arguments (one is created for each
automatic var referenced or set by the condition), so it would be nice to
track all of them rather than just hardcoding the first.  And, the argument
doesn't necessarily have to be a scalar, so perhaps later on we could derive
ranges even for structure members etc. if needed.  Or just handle
assume_function in IPA-SRA somehow at least.

The C++23 paper mentions
[[assume(size > 0)]];
[[assume(size % 32 == 0)]];
[[assume(std::isfinite(data[i]))]];
[[assume(*pn >= 1)]];
[[assume(i == 42)]];
[[assume(++i == 43)]];
[[assume((std::cin >> i, i == 42))]];
[[assume(++almost_last == last)]];
among other things, the first and fifth are already handled the
if (!cond) __builtin_unreachable (); way and so work even without this
patch, the (std::cin >> i, i == 42) case is not worth bothering for now
and the rest would be single block assumptions that can be handled easily
(except the last one which would have record type arguments and so we'd need
SRA).

	Jakub