[llvm-dev] [RFC] How to manifest information in LLVM-IR, or, revisiting llvm.assume

[John McCall via llvm-dev]

On 18 Dec 2019, at 14:18, Doerfert, Johannes wrote:
> Hi John,
>
> Is it correct to assume that you are in favor of
>   - changing llvm.assume to be more expressive
>   - operand bundle uses, especially w/o outlining
>   - outlining, if we can show it plays well with transformations, e.g.
>     the binding to the code is "weak"

Yes, this is all correct.  I’m excited that we’re looking into 
making this
less useless.

> I inlined more comments below.
>
> On 12/18, John McCall wrote:
>> On 18 Dec 2019, at 11:28, Doerfert, Johannes wrote:
>>
>>> On 12/18, John McCall wrote:
>>>> On 16 Dec 2019, at 18:16, Doerfert, Johannes via llvm-dev wrote:
>>>>> Abstract:
>>>>>
>>>>> It is often hard or impossible to encode complex, e.g., 
>>>>> non-boolean,
>>>>> information in an `llvm.assume(i1)`. This RFC describes various 
>>>>> problems
>>>>> we have right now and provides alternative design ideas.
>>>>>
>>>>>
>>>>>
>>>>> Some Existing Problems:
>>>>>
>>>>> A) The boolean requirement.
>>>>>   The current `llvm.assume(i1)` expects a boolean that is known to 
>>>>> hold
>>>>>   true at runtime (once the `llvm.assume` call is reached). 
>>>>> However,
>>>>>   forming this boolean for "arbitrary" information is hard or even
>>>>>   impossible. Alignment, which is an easy case, already requires 3 
>>>>> extra
>>>>>   instructions, one of which is a `ptrtoint` and therefore not 
>>>>> really
>>>>>   optimizer friendly. Dereferenceability, is even scarier. Thus, 
>>>>> we are
>>>>>   currently limited to (almost) boolean information when we want 
>>>>> to
>>>>>   manifest information in the IR (which happens due to inlining or 
>>>>> code
>>>>>   motion, see https://reviews.llvm.org/D69477 for an example).
>>>>>
>>>>> B) The one-use checks.
>>>>>   Various pattern matching passes check the number of uses of a 
>>>>> value.
>>>>>   However, while `llvm.assume` is eventually eliminated by the 
>>>>> backend
>>>>>   it will still increase the use count of the operand. I doubt we 
>>>>> are
>>>>>   able to not increase the use count at all (and keep everything 
>>>>> else
>>>>>   working), but what we can do is make sure the uses in 
>>>>> "assumptions"
>>>>>   are easy to spot, thus filter. This is not the case right now 
>>>>> because
>>>>>   of the additional instructions we need to make the values 
>>>>> boolean.
>>>>>   Even if you have `__builtin_assume(ptr);` the `ptr` use will not 
>>>>> be
>>>>>   the `llvm.assume` call but a `icmp`.
>>>>>
>>>>> C) The side-effect avoidance.
>>>>>   `__assume`, `__builtin_assume`, `__builtin_assume_aligned`, and 
>>>>> OpenMP
>>>>>   `omp assume` are all defined to not evaluate their argument, 
>>>>> thus to
>>>>>   not cause the side effects that the evaluation of the argument 
>>>>> would
>>>>>   otherwise imply. The way we implement this restriction is by not
>>>>>   emitting the argument expression in IR if it might cause a side
>>>>>   effect. We warn the user if that happens. While this is 
>>>>> generally
>>>>>   speaking fine, it would be interesting to lift the 
>>>>> *implementation*
>>>>>   restriction. One benefit would be that we could implement 
>>>>> `assert`
>>>>>   through `__builtin_assume` properly.
>>>>>
>>>>> D) The singleton ranges.
>>>>>   An `llvm.assume` will only provide information for a single 
>>>>> program
>>>>>   point not a range. Even if the beginning and the end of a range 
>>>>> have
>>>>>   an `llvm.assume`, there are cases where the information will not 
>>>>> be
>>>>>   as good as a proper range assumption. OpenMP 5.1 introduces such
>>>>>   range assumptions but other situations would benefit from them 
>>>>> as
>>>>>   well. Take for example function attributes and inlining. Since 
>>>>> we know
>>>>>   they hold for the entire function and not only when it is 
>>>>> entered we
>>>>>   could encode the information over the entire range of the 
>>>>> inlined
>>>>>   code.
>>>>>
>>>>>
>>>>> Some Site Notes:
>>>>>
>>>>> - It seems of little use that we interleave the code for the 
>>>>> assumed
>>>>>   expression with the user code. Having the `llvm.assume` allows 
>>>>> us to
>>>>>   tie information to a program point, beyond that we just clutter 
>>>>> the
>>>>>   function with instructions that we later remove anyway.
>>>>>
>>>>> - Reconstructing information from the pattern of instructions that 
>>>>> feed
>>>>>   into the `llvm.assume` is also not optimal, especially since we 
>>>>> do
>>>>>   not need to "optimize" these instructions anyway.
>>>>>
>>>>> - The current (=arbitrary) side-effects of `llvm.assume` are too 
>>>>> strong.
>>>>>   We have `inaccessiblemem_or_argmemonly` and we might be able to 
>>>>> come
>>>>>   up with something even more specialized for this, e.g.,
>>>>>   `control_dependences_only` to indicate that there are only 
>>>>> control
>>>>>   dependences.
>>>>
>>>> This is all well put; I think you’ve covered the major 
>>>> weaknesses.
>>>>
>>>>
>>>>> Some Design Ideas:
>>>>>
>>>>> 1) Use named operand bundles to encode information.
>>>>>    If we want to encode property XYZ for a value %V holds at a 
>>>>> certain
>>>>>    program point and the property is dependent on %N we could 
>>>>> encode
>>>>>    that as:
>>>>>      `llvm.assume() ["XYZ"(%V, %N)]`
>>>>>    There are various benefits, including:
>>>>>      - It is freely extensible.
>>>>>      - The property is directly tied to the value. Thus, no need 
>>>>> for
>>>>>        encoding patterns that introduce extra instructions and 
>>>>> uses and
>>>>>        which we need to preserve and decode later.
>>>>>      - Allows dynamic properties even when corresponding 
>>>>> attributes do
>>>>>        not, e.g., `llvm.assume() ["align"(%arg_ptr, %N)]` is fine 
>>>>> and
>>>>>        once `%N` becomes a constant, or we determine a lower 
>>>>> bound, we
>>>>>        can introduce the `align(C)` attribute for `%arg_ptr`.
>>>>>
>>>>> 2) Outline assumption expression code (with side-effects).
>>>>>   If we potentially have side-effects, or we simply have a 
>>>>> non-trivial
>>>>>   expression that requires to be lowered into instructions, we can
>>>>>   outline the assumption expression code and tie it to the
>>>>>   `llvm.assume` via another operand bundle property. It could look
>>>>>   something like this:
>>>>>     `__builtin_assume(foo(i) == bar(j));`
>>>>>   will cause us to generate
>>>>>     ```
>>>>>     /// Must return true!
>>>>>     static bool llvm.assume.expression_#27(int i, int j) {
>>>>>       return foo(i) == bar(j);
>>>>>     }
>>>>>     ```
>>>>>   and a `llvm.assume` call like this:
>>>>>     `llvm.assume() ["assume_fn"(@llvm.assume.expression_#27, %i, 
>>>>> %j))]
>>>>>   So we generate the expression in a new function which we (only) 
>>>>> tie to
>>>>>   the `llvm.assume()` through the "assume_fn" operand bundle. This 
>>>>> will
>>>>>   make sure we do not accidentally evaluate the code, or assume it 
>>>>> is
>>>>>   evaluated and produced side-effects. We can still optimize the 
>>>>> code
>>>>>   and use the information that we learn from it at the 
>>>>> `llvm.assume`
>>>>>   site though.
>>>>
>>>> I think outlining is abstractly very promising, but I’m worried 
>>>> about
>>>> it impacting existing optimizations:
>>>>
>>>> - It’s won’t be obvious at all from the IR that the predicate 
>>>> function
>>>>   is dead code.  It would be a shame if we ended up emitting the 
>>>> predicate
>>>>   function, or some global only it references, because we didn’t 
>>>> delete
>>>>   all the llvm.assume calls early enough to recognize that it was 
>>>> dead.
>>>
>>> So, we already "delete" llvm.assume and its operands in the 
>>> backends.
>>> Having a dedicated middle-end pass to do that which also deletes the
>>> associated "assume_fn" doesn't seem hard or complicated to set up.
>>>
>>> Worst case (which I really don't think would ever happen), we emit 
>>> the
>>> functions which are internal and never referenced. The linker should
>>> strip them.
>>>
>>>
>>>
>>>> - Anything passed to the predicate function will by default look 
>>>> like it
>>>>   escapes.  This is particularly true if the predicate takes local
>>>>   variables by references, which is the easiest and most 
>>>> straightforwardly
>>>>   correct way for frontends to emit these predicates.  So this will 
>>>> block
>>>>   basic memory analyses (including mem2reg!) unless they’re 
>>>> taught to
>>>>   remove or rewrite assumptions.
>>>
>>> Partially true and we already have that problem though.
>>>
>>> Mem2reg, and others, might need to know about llvm.assume uses but I
>>> fail to see why they need to rewrite much (in the short therm). The
>>> frontend generated code would naturally look like this:
>>>
>>> %ptr.addr = alloca i32*
>>> store %ptr, %ptr.addr
>>> ...
>>> %ptr.val = load %ptr.addr
>>> llvm.assume() ["align"(%ptr.val)]
>>
>> I disagree; the natural way to generate this code in frontends will
>> actually be to take the variable by reference.  We can, of course, 
>> make
>> frontends smart enough to take the variable by value if it’s
>> obviously only loaded from in the expressions, but if the optimizers
>> still aren’t generally aware of the intrinsic, that will just mean
>> that assumptions pessimize slightly more abstracted code.
>>
>> For example, if I had this:
>>
>> ```
>>   Clang::QualType type = …;
>>   __builtin_assume(!type.hasLocalQualifiers());
>> ```
>>
>> At a high level, I want to be able to apply mem2reg to the value of
>> this `QualType`; but at a low level, this method call takes `type`
>> by reference, and so the predicate function will take it by reference
>> as well.
>
> At some point we need to realize code is only used in an assumption in
> order to actually outline. There is no question about that. Where it
> happens is a good question though. I could write a pass to do that in
> the IR, in order to test the idea.

You mean for things like loads that are just passed to the intrinsic?
I agree, although I think other people who’ve worked with 
`llvm.assume`
have noticed that the presence of the load can change optimization in
ways that are hard to eliminate, e.g. if a load gets hoisted because
it’s “done twice”.

> Since we don't have this code I won't speculate about it now. What I
> will say instead is that we have code to modify the IR in order to 
> pass
> an argument by reference instead of by value. I am more than happy to
> make it aware of llvm.assume operand bundle uses and I am very much
> certain the amount of code needed to transform these from pass by
> reference to pass by value is negligible.

Okay.

>>> Mem2reg should kick in just fine even if %ptr now has a "unknown" 
>>> use.
>>> But that "unknown" use is much less problematic than what we have 
>>> now
>>> because the user is the `llvm.assume` call and not some `ptrtoint` 
>>> which
>>> is used two steps later in an `llvm.assume.
>>>
>>> If you feel I missed a problem here, please let me know.
>>>
>>>
>>>
>>>> Unfortunately, I don’t have a great counter-proposal that isn’t 
>>>> a
>>>> major project.
>>>>
>>>> (The major project is to make the predicates sub-functions within
>>>> the caller.  This doesn’t fix all the problems, and sub-functions
>>>> introduce a host of new issues, but they do have the benefit of
>>>> making the analysis much more obviously intra-procedural.)
>>>
>>> I don't think inter-procedural reasoning is a problem or bad. 
>>> Especially
>>> here with internal functions that have a single use, it is really 
>>> not
>>> hard to make the connection.
>>
>> It’s certainly not a problem *in theory*.  *In theory* every
>> intraprocedural analysis can be taught to go interprocedural
>> into a predicate.
>
> We might have different expectations how assumes are used or where our
> analyses/transformation are heading. Not every pass needs to look at
> assumes at the end of the day. Most information that we use can 
> already,
> or should be described through an attribute and we have a working way 
> to
> deduce those interprocedurally. The future, I hope, is dominated by
> interprocedural analysis and optimization. Given how far we have come
> this summer alone, and what was said on the IPO panel at LLVM'dev, I 
> am
> confident we'll get there.

I suspect this will always be a practical point of tension, and I
did not come away from that panel feeling like there was anything
other than a fairly hand-wavey hope that somehow we’d get there.

John.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20191218/2e7e4a93/attachment.html>