[LLVMdev] llvm.meta (was Rotated loop identification)

[Hal Finkel]

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