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

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"

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.

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.

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


Thanks,
  Johannes
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 228 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20191218/a64687c7/attachment.sig>

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>

On 12/18, John McCall wrote:
> 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.
Perfect! I'll go ahead and prototype something then so we can collect
data and experience.

> > > > > - 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”.
That's right and I don't know what the perfect solution looks like,
maybe always outlining is not so bad after all. I guess we all agree
that we have to minimize the llvm.assume impact while keeping
information available and correct, e.g., wrt. control dependences.

A crazy idea we could try further down the road:
  Once we have control dependences [0] we can start "moving" the
assume
  calls, e.g., towards function entries. We can hoist it over
  conditionals when we can keep track of the control dependences and we
  know it would have been reached, e.g., the original position is in the
  "must-be-executed-context" of the new position [1].

[0] https://reviews.llvm.org/D71578
[1] https://reviews.llvm.org/D65186
> > 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.
FWIW. A few people do actively work towards that goal by actually
implementing interprocedural analyses and optimizations.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 228 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20191218/d2cc8012/attachment.sig>