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

[Andrew Trick]

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