llvm dev - Mar 2013 - [LLVMdev] llvm.meta (was Rotated loop identification)

----- Original Message -----
> From: "Andrew Trick" <atrick at apple.com>
> To: "Hal Finkel" <hfinkel at anl.gov>
> Cc: "llvmdev at cs.uiuc.edu List" <llvmdev at cs.uiuc.edu>,
"Michele Scandale" <michele.scandale at gmail.com>
> Sent: Friday, February 8, 2013 1:52:55 PM
> Subject: llvm.meta (was Rotated loop identification)
> 
> 
> 
> On Feb 7, 2013, at 10:58 PM, Hal Finkel < hfinkel at anl.gov > wrote:
> 
> 
> 
> 
> As long as this is brainstorming time, I actually like the idea of an
> llvm.invariant intrinsic that the optimizers know to ignore. I like
> it for other purposes, but would happen to work for you as a
> temporary workaround. It could take one or two IR values (as
> metadata operands) and a metadata language describing the invariant,
> such as a relational operator and optional constant. In your case,
> you want to know that the loop counter's starting value is less than
> its limit, so you could conveniently plop one of those in the loop
> preheader. The invariant would only go away if no one else used the
> value, which in your case would make sense (e.g. if the loop test
> were rewritten in terms of %b, you probably wouldn't need the
> invariant any more).
> 
>
http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20121210/158601.html
> 
> If you're in favor of this approach, can I pop out of the woodwork
> and say that it appears that we have a reasonably-large group of
> contributors in favor of an invariant intrinsic and we should move
> forward on that basis?
> 
> 
> A general llvm.invariant does seem like a convenient thing. I'm not
> pushing very hard because I don't need it for anything I'm working
> on yet, and wasn't aware that anyone else liked this particular
> idea. But I haven't heard any argument against it. I am aware that a
> lot of people want to attach new semantics to the IR that are not
> necessarily easy to preserve, so I don't want to oversell a
> solution.
> 
> 
> I don't have an opinion on whether each type of invariant should get
> its own intrinsic ID or we should have one and use the flexibility
> of metadata operands. The important thing is that the optimizer have
> a uniform approach to handling them, and that they truly cannot
> interfere with optimization other than as intended. For the sake of
> discussion, and to avoid confusion with the current, badly named
> llvm.invariant, I'll just call these llvm.meta intrinsics.
> 
> 
> I would only endorse a new llvm.meta approach if we're sure we can
> unify or replace most of the current meta-style intrinsics. But I
> first need to better understand the motivation for those approaches,
> which I have not personally worked with much (they're somewhat
> marginalized).
Thanks for writing this! As you point out there are already a number of
"pseudo-users" in LLVM, and we don't have a good general scheme
for handling them. Currently, special handling for llvm.dbg, expect, etc. are
coded into several (many) different places to make them appear free, and adding
more in a similar way might become unmanageable. Even worse, these intrinsics
break the "hasOneUser" check, and this interferes with optimization.
This may not be important for debug intrinsics, but certainly is for features
intended to help optimization.

Based on this, it seems that we need to differentiate two classes of users: real
users and, as Chandler called them, ephemeral users. We could update
hasOneUser() to be hasOneUser(bool countEphemerals = false), or something like
that, and the trick will be to support this without requiring additional
iteration over all users. Thoughts?

We should also use this new class of users to replace a lot of the special-case
code that currently exists for making some of these intrinsics free (and
removing them before CodeGen, etc.).

Specifically regarding invariants; I think that dbg and lifetime (and
annotation?) would need to remain separate intrinsics. The invariant could have
both a 'required' and 'expected' mode, and we could merge expect
into it. Value ranges should fit naturally into the semantics of an invariant.
> 
> 
> - llvm.dbg
> 
> 
> Are there any problems with our current approach?
> 
> 
> - llvm.lifetime and llvm.invariant (for pointers)
> 
> 
> Why are they real value users? We probably don't care about extra
> users of an object base, but are we confident they won't affect
> optimization except as intended? I'd like to see an experiment where
> we emit these gratuitously, suppress optimizations that use them,
> strip them after -O3, and verify no effect on bitcode.
> 
> 
> - llvm.annotation
> 
> 
> Does anyone use these? Supposedly the optimizer "ignores" them.
But
> the optimizer certainly doesn't ignore additional uses of a value.
As I recall, the optimizer does not currently consider these free everywhere
that it should (by inspection); nevertheless, I've never seem them used
anywhere. Why were they introduced?
> 
> 
> - llvm.expect
> 
> 
> This is injected in the def-use chain. Accidentally running the
> optimizer with these intrinsics present would be disasterous. It's
> really the same problem as representing an invariant, just different
> semantics.
> 
> 
> - load range metadata
> 
> 
> We should be able to express general value ranges, independent of
> loads.
> We should be able to express the invariant conditionally, independent
> of the value's definition.
> The load's should be gvn-able without losing the invariants.
Agreed.

 -Hal
> 
> 
> Future uses:
> 
> 
> - Relating value to other values (not just a constant range).
> 
> 
> - Pointer alignment.
> 
> 
> - Pointers to immutable memory (when dominated by intrinsic).
> 
> 
> You mentioned a number of other things you'd like to use invariants
> for in a previous post, I won't try to repeat them.
> 
> 
> -Andy

On Feb 22, 2013, at 6:28 AM, Hal Finkel <hfinkel at anl.gov> wrote:
> ----- Original Message -----
>> From: "Andrew Trick" <atrick at apple.com>
>> To: "Hal Finkel" <hfinkel at anl.gov>
>> Cc: "llvmdev at cs.uiuc.edu List" <llvmdev at
cs.uiuc.edu>, "Michele Scandale" <michele.scandale at
gmail.com>
>> Sent: Friday, February 8, 2013 1:52:55 PM
>> Subject: llvm.meta (was Rotated loop identification)
>> 
>> 
>> 
>> On Feb 7, 2013, at 10:58 PM, Hal Finkel < hfinkel at anl.gov >
wrote:
>> 
>> 
>> 
>> 
>> As long as this is brainstorming time, I actually like the idea of an
>> llvm.invariant intrinsic that the optimizers know to ignore. I like
>> it for other purposes, but would happen to work for you as a
>> temporary workaround. It could take one or two IR values (as
>> metadata operands) and a metadata language describing the invariant,
>> such as a relational operator and optional constant. In your case,
>> you want to know that the loop counter's starting value is less
than
>> its limit, so you could conveniently plop one of those in the loop
>> preheader. The invariant would only go away if no one else used the
>> value, which in your case would make sense (e.g. if the loop test
>> were rewritten in terms of %b, you probably wouldn't need the
>> invariant any more).
>> 
>>
http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20121210/158601.html
>> 
>> If you're in favor of this approach, can I pop out of the woodwork
>> and say that it appears that we have a reasonably-large group of
>> contributors in favor of an invariant intrinsic and we should move
>> forward on that basis?
>> 
>> 
>> A general llvm.invariant does seem like a convenient thing. I'm not
>> pushing very hard because I don't need it for anything I'm
working
>> on yet, and wasn't aware that anyone else liked this particular
>> idea. But I haven't heard any argument against it. I am aware that
a
>> lot of people want to attach new semantics to the IR that are not
>> necessarily easy to preserve, so I don't want to oversell a
>> solution.
>> 
>> 
>> I don't have an opinion on whether each type of invariant should
get
>> its own intrinsic ID or we should have one and use the flexibility
>> of metadata operands. The important thing is that the optimizer have
>> a uniform approach to handling them, and that they truly cannot
>> interfere with optimization other than as intended. For the sake of
>> discussion, and to avoid confusion with the current, badly named
>> llvm.invariant, I'll just call these llvm.meta intrinsics.
>> 
>> 
>> I would only endorse a new llvm.meta approach if we're sure we can
>> unify or replace most of the current meta-style intrinsics. But I
>> first need to better understand the motivation for those approaches,
>> which I have not personally worked with much (they're somewhat
>> marginalized).
> 
> Thanks for writing this! As you point out there are already a number of
"pseudo-users" in LLVM, and we don't have a good general scheme
for handling them. Currently, special handling for llvm.dbg, expect, etc. are
coded into several (many) different places to make them appear free, and adding
more in a similar way might become unmanageable. Even worse, these intrinsics
break the "hasOneUser" check, and this interferes with optimization.
This may not be important for debug intrinsics, but certainly is for features
intended to help optimization.
> 
> Based on this, it seems that we need to differentiate two classes of users:
real users and, as Chandler called them, ephemeral users. We could update
hasOneUser() to be hasOneUser(bool countEphemerals = false), or something like
that, and the trick will be to support this without requiring additional
iteration over all users. Thoughts?
Redefining hasOneUser() would be the most efficient approach, and definitely
possible. But it would add complexity to a fundamental property of the IR and
potentially cause bugs when developers forget to check the meta users.

I was proposing to use meta-data operands in the intrinsic instead. They add no
visible users. They can be left dangling and cleaned up lazily. WeakVH are
expensive, but I'm not worried about cost yet. The added complexity in this
case happens at SSA update, which does need to visit meta users explicitly. I
believe this is currently broken for dbg.value and works by luck for simple
cases. So we need to fix this one way or another.

I contrived a test case for this and submitted PR15501.

-Andy
> We should also use this new class of users to replace a lot of the
special-case code that currently exists for making some of these intrinsics free
(and removing them before CodeGen, etc.).
> 
> Specifically regarding invariants; I think that dbg and lifetime (and
annotation?) would need to remain separate intrinsics. The invariant could have
both a 'required' and 'expected' mode, and we could merge expect
into it. Value ranges should fit naturally into the semantics of an invariant.
> 
>> 
>> 
>> - llvm.dbg
>> 
>> 
>> Are there any problems with our current approach?
>> 
>> 
>> - llvm.lifetime and llvm.invariant (for pointers)
>> 
>> 
>> Why are they real value users? We probably don't care about extra
>> users of an object base, but are we confident they won't affect
>> optimization except as intended? I'd like to see an experiment
where
>> we emit these gratuitously, suppress optimizations that use them,
>> strip them after -O3, and verify no effect on bitcode.
>> 
>> 
>> - llvm.annotation
>> 
>> 
>> Does anyone use these? Supposedly the optimizer "ignores"
them. But
>> the optimizer certainly doesn't ignore additional uses of a value.
> 
> As I recall, the optimizer does not currently consider these free
everywhere that it should (by inspection); nevertheless, I've never seem
them used anywhere. Why were they introduced?
> 
>> 
>> 
>> - llvm.expect
>> 
>> 
>> This is injected in the def-use chain. Accidentally running the
>> optimizer with these intrinsics present would be disasterous. It's
>> really the same problem as representing an invariant, just different
>> semantics.
>> 
>> 
>> - load range metadata
>> 
>> 
>> We should be able to express general value ranges, independent of
>> loads.
>> We should be able to express the invariant conditionally, independent
>> of the value's definition.
>> The load's should be gvn-able without losing the invariants.
> 
> Agreed.
> 
> -Hal
> 
>> 
>> 
>> Future uses:
>> 
>> 
>> - Relating value to other values (not just a constant range).
>> 
>> 
>> - Pointer alignment.
>> 
>> 
>> - Pointers to immutable memory (when dominated by intrinsic).
>> 
>> 
>> You mentioned a number of other things you'd like to use invariants
>> for in a previous post, I won't try to repeat them.
>> 
>> 
>> -Andy

----- Original Message -----
> 
> On Feb 22, 2013, at 6:28 AM, Hal Finkel <hfinkel at anl.gov> wrote:
> 
> > ----- Original Message -----
> >> From: "Andrew Trick" <atrick at apple.com>
> >> To: "Hal Finkel" <hfinkel at anl.gov>
> >> Cc: "llvmdev at cs.uiuc.edu List" <llvmdev at
cs.uiuc.edu>, "Michele
> >> Scandale" <michele.scandale at gmail.com>
> >> Sent: Friday, February 8, 2013 1:52:55 PM
> >> Subject: llvm.meta (was Rotated loop identification)
> >> 
> >> 
> >> 
> >> On Feb 7, 2013, at 10:58 PM, Hal Finkel < hfinkel at anl.gov
> wrote:
> >> 
> >> 
> >> 
> >> 
> >> As long as this is brainstorming time, I actually like the idea of
> >> an
> >> llvm.invariant intrinsic that the optimizers know to ignore. I
> >> like
> >> it for other purposes, but would happen to work for you as a
> >> temporary workaround. It could take one or two IR values (as
> >> metadata operands) and a metadata language describing the
> >> invariant,
> >> such as a relational operator and optional constant. In your case,
> >> you want to know that the loop counter's starting value is
less
> >> than
> >> its limit, so you could conveniently plop one of those in the loop
> >> preheader. The invariant would only go away if no one else used
> >> the
> >> value, which in your case would make sense (e.g. if the loop test
> >> were rewritten in terms of %b, you probably wouldn't need the
> >> invariant any more).
> >> 
> >>
http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20121210/158601.html
> >> 
> >> If you're in favor of this approach, can I pop out of the
woodwork
> >> and say that it appears that we have a reasonably-large group of
> >> contributors in favor of an invariant intrinsic and we should move
> >> forward on that basis?
> >> 
> >> 
> >> A general llvm.invariant does seem like a convenient thing.
I'm
> >> not
> >> pushing very hard because I don't need it for anything I'm
working
> >> on yet, and wasn't aware that anyone else liked this
particular
> >> idea. But I haven't heard any argument against it. I am aware
that
> >> a
> >> lot of people want to attach new semantics to the IR that are not
> >> necessarily easy to preserve, so I don't want to oversell a
> >> solution.
> >> 
> >> 
> >> I don't have an opinion on whether each type of invariant
should
> >> get
> >> its own intrinsic ID or we should have one and use the flexibility
> >> of metadata operands. The important thing is that the optimizer
> >> have
> >> a uniform approach to handling them, and that they truly cannot
> >> interfere with optimization other than as intended. For the sake
> >> of
> >> discussion, and to avoid confusion with the current, badly named
> >> llvm.invariant, I'll just call these llvm.meta intrinsics.
> >> 
> >> 
> >> I would only endorse a new llvm.meta approach if we're sure we
can
> >> unify or replace most of the current meta-style intrinsics. But I
> >> first need to better understand the motivation for those
> >> approaches,
> >> which I have not personally worked with much (they're somewhat
> >> marginalized).
> > 
> > Thanks for writing this! As you point out there are already a
> > number of "pseudo-users" in LLVM, and we don't have a
good general
> > scheme for handling them. Currently, special handling for
> > llvm.dbg, expect, etc. are coded into several (many) different
> > places to make them appear free, and adding more in a similar way
> > might become unmanageable. Even worse, these intrinsics break the
> > "hasOneUser" check, and this interferes with optimization.
This
> > may not be important for debug intrinsics, but certainly is for
> > features intended to help optimization.
> > 
> > Based on this, it seems that we need to differentiate two classes
> > of users: real users and, as Chandler called them, ephemeral
> > users. We could update hasOneUser() to be hasOneUser(bool
> > countEphemerals = false), or something like that, and the trick
> > will be to support this without requiring additional iteration
> > over all users. Thoughts?
> 
> Redefining hasOneUser() would be the most efficient approach, and
> definitely possible. But it would add complexity to a fundamental
> property of the IR and potentially cause bugs when developers forget
> to check the meta users.
> 
> I was proposing to use meta-data operands in the intrinsic instead.
> They add no visible users. They can be left dangling and cleaned up
> lazily. WeakVH are expensive, but I'm not worried about cost yet.
> The added complexity in this case happens at SSA update, which does
> need to visit meta users explicitly. I believe this is currently
> broken for dbg.value and works by luck for simple cases. So we need
> to fix this one way or another.
I'd still like to be able to chart a way forward on this. Regarding defining
invariants, I don't understand how using metadata intrinsics really helps
because, while a metadata operand could be used to tie the invariant to a value
being constrained, the invariant expression itself would add additional uses to
the values used in its subexpressions. When I had discussed this with Chandler
(many months ago now), we had developed a working assumption that if the
invariant is worth having, then it is worth carrying as a dependency of the
values it constrains. This may not be true, but I think is a viewpoint worth
evaluating.

On the other hand, when I started down this road I was motivated by a desire to
implement support for __builtin_assume_aligned. I would still like to do this,
or something like this to get equivalent functionality. The idea of metadata
references seems like it might work well for alignment assumptions, as a
restricted special case. Maybe something like this:

tail call void @llvm.assume.aligned(metadata !{i32* %ptr}, i32 16)

but then the problem becomes making sure that these things stick around long
enough to help the interesting inlining cases. Thoughts?
> 
> I contrived a test case for this and submitted PR15501.
Interesting.

Thanks again,
Hal
> 
> -Andy
> 
> > We should also use this new class of users to replace a lot of the
> > special-case code that currently exists for making some of these
> > intrinsics free (and removing them before CodeGen, etc.).
> > 
> > Specifically regarding invariants; I think that dbg and lifetime
> > (and annotation?) would need to remain separate intrinsics. The
> > invariant could have both a 'required' and 'expected'
mode, and we
> > could merge expect into it. Value ranges should fit naturally into
> > the semantics of an invariant.
> > 
> >> 
> >> 
> >> - llvm.dbg
> >> 
> >> 
> >> Are there any problems with our current approach?
> >> 
> >> 
> >> - llvm.lifetime and llvm.invariant (for pointers)
> >> 
> >> 
> >> Why are they real value users? We probably don't care about
extra
> >> users of an object base, but are we confident they won't
affect
> >> optimization except as intended? I'd like to see an experiment
> >> where
> >> we emit these gratuitously, suppress optimizations that use them,
> >> strip them after -O3, and verify no effect on bitcode.
> >> 
> >> 
> >> - llvm.annotation
> >> 
> >> 
> >> Does anyone use these? Supposedly the optimizer
"ignores" them.
> >> But
> >> the optimizer certainly doesn't ignore additional uses of a
value.
> > 
> > As I recall, the optimizer does not currently consider these free
> > everywhere that it should (by inspection); nevertheless, I've
> > never seem them used anywhere. Why were they introduced?
> > 
> >> 
> >> 
> >> - llvm.expect
> >> 
> >> 
> >> This is injected in the def-use chain. Accidentally running the
> >> optimizer with these intrinsics present would be disasterous.
It's
> >> really the same problem as representing an invariant, just
> >> different
> >> semantics.
> >> 
> >> 
> >> - load range metadata
> >> 
> >> 
> >> We should be able to express general value ranges, independent of
> >> loads.
> >> We should be able to express the invariant conditionally,
> >> independent
> >> of the value's definition.
> >> The load's should be gvn-able without losing the invariants.
> > 
> > Agreed.
> > 
> > -Hal
> > 
> >> 
> >> 
> >> Future uses:
> >> 
> >> 
> >> - Relating value to other values (not just a constant range).
> >> 
> >> 
> >> - Pointer alignment.
> >> 
> >> 
> >> - Pointers to immutable memory (when dominated by intrinsic).
> >> 
> >> 
> >> You mentioned a number of other things you'd like to use
> >> invariants
> >> for in a previous post, I won't try to repeat them.
> >> 
> >> 
> >> -Andy
> 
> 
-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory