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

[John McCall via llvm-dev]

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.

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

John.

> We can easily teach the Attributor to follow these "pseudo-calls"
> in order to derive information from them.
>
> Thanks,
>   Johannes
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20191218/e2c64c18/attachment.html>