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

[Andrew MacLeod <amacleod@redhat.com>]

On 10/12/22 06:15, Jakub Jelinek wrote:
>
>> 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.
>
I agree, I think it would be better to process once, and store the 
results some where. I could provide a routine which attempts the 
evaluation of the current function, and returns a "safe" range for each 
of the parameters.   By safe, I mean it would assume VARYING for every 
unknown value in the function, reduced by whatever the backward walk 
determined.  We can refine that later by wiring this call in after a 
full ranger walk of VRP for instance to get more precise values, but 
that is not necessary at the moment.

I can also make it so that we always try to look up values from the 
.ASSUME in fold_using_range, which means any VRP or other ranger client 
will pick up the results.  If there is nothing available, it would 
return VARYING as the default.   Any current range would be intersected 
with what the ASSUME query returns.

I presume you are looking to get this working for this release, making 
the priority high? :-)

>> 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).
Intersection I believe...?  I think the value from the assume's should 
add restrictions to the range..
>> 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.).

Single blocks for the first cut and POC.  easier.  then look at expansion


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


I figured as much, I was just wondering if there might be some way to 
"simplify" certain things by processing it and turning each parameter 
query into a smaller function returning the range we determined from the 
main one...   but perhaps that is more complicated.


Andrew