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

[Hal Finkel]

----- Original Message -----
> 
> 
> 
> On Sep 7, 2013, at 7:41 AM, Hal Finkel < hfinkel at anl.gov > wrote:
> 
> 
> 
> 
> 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.
> 
> 
> Metadata is a better approach because it doesn’t interfere with
> optimizations that are free to ignore it.
> 
> 
> Yes, if the invariant expression requires IR values and real uses,
> then that defeats the purpose. I prefer a meta-data language to the
> alternative of ephemeral expressions. I could be convinced either
> way. I just think it will be confusing to mix ephemeral expressions
> with program logic and impractical to make it transparent to
> optimizations. Not the end of the world though, and I’ll listen to
> any strong arguments to the contrary.
> 
> When you say "metadata language", what do you have in mind? I can
> think of two general schemes:
> 
> 1. A language in which each expression in the language is a metadata
> node; maybe something like:
> !invariant1 = !{ !"eq", !{ !"urem", i32 %value, i32 48 }, i32 0 }
> 
> 2. A language encoded in a string with some syntax for substitution
> values; maybe something like:
> !invariant1 = !{ !"(eq (urem #1, 48), 0)", i32 %value}
> 
> 
> 
> 
> I was thinking of the first approach, but not as a pseudo-IR with
> expression syntax, just as a way to express the few invariants that
> we support.
> 
> 
> Either: @llvm.invariant(i8* %adr, metadata !invariant)
> 
> 
> Or: @llvm.invariant(metadata !{i32* %adr}, metadata !invariant)
> 
> 
> With: !invariant1 = !{ !"align", i32 48, i32 0 }
> 
> 
> Or just skip the meta-data altogether:
> @llvm.align(i8*,i32, i32)
> 
> 
> I don't know if it's better to use strings or enums. I'm not a
> meta-data designer.
> 
> 
> If we only try to solve your immediate problem of
> builtin_assume_aligned, isn't that good enough for now?

The thing that most concerns me about __builtin_assume_aligned and this scheme is the control dependencies. In gcc, it is the return value of the intrinsic that carries the alignment guarantee, and I think that this makes a lot of sense. Consider something like this:

void foo(double *x) {
  if (check_if_x_is_special(&global_state)) {
    y = __builtin_assume_aligned(x, 16);
    do_something(y);
  } else
    do_something_else(x);
}

with this scheme, there is never a danger that the alignment assumption can be lifted and incorrectly applied to x in an inlined do_something_else(x). If we simply have the intrinsic not return a value and apply its invariant back on its arguments, then I don't see how to guarantee correctness.

I would like general invariants, but can I make general invariants return a value in the same way? Alternatively, maybe the invariant could take a pointer and only apply to values in a specific memory location at some particular point? Maybe then AA will keep everything safe?

As Chandler pointed in response to my original patch on this topic, making the intrinsic return a value means that everyone else needs to look through it. On the other hand, it would make it conservatively correct ;) (as I'm writing this, I'm leaning toward trying the pointer thing).

Thoughts?

Thanks again,
Hal

> Are you
> concerned about generalizing this to builtin_assume?
> 
> 
> 
> 
> 
> 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)
> 
> 
> 
> I think this concept is sound except for the problem of enforcing SSA
> properties. Do meta-data operands need to dominate? If so, we need
> to fix SSA updater to deal with this. Preserving the meta-data after
> code duplication would effectively require a meta-phi. We don’t want
> a real phi because we don’t want a real use. Admittedly this would
> be annoying, but we could always drop the metadata users instead.
> You could get by initially without solving this problem, as we’ve
> done with dbg.value.
> 
> 
> I’m a bit less enthusiastic about meta-intrinsics after realizing
> that the only current example, dbg.value, is a poor use of the
> concept. It should have been meta-data attached directly to the
> value with source line info instead.
> 
> What if we say that they don't need to dominate? The dependency graph
> can certainly be well defined without the vector of IR instructions
> being a topological ordering of that graph. I understand that we
> like it this way for a number of reasons, but it is not clear to me
> that any of those reasons apply in this case. If the metadata
> intrinsic does not return a value, we can't introduce unwanted
> cycles. If they do return a value and could introduce a cycle, then
> we do decide how we would handle that.
> 
> 
> 
> Right, meta-intrinsics should never return a value. It’s a bit nasty
> to have to guess what to do when the value is RAUW’d though.
> 
> 
> 
> 
> 
> 
> 
> 
> 
> If we could demonstrate the advantage of converting lifetime
> intrinsics to meta-instrinsics (not real uses), then I’d be all for
> it.
> 
> 
> 
> 
> but then the problem becomes making sure that these things stick
> around long enough to help the interesting inlining cases. Thoughts?
> 
> 
> 
> Ensuring meta-data sticks around seems like the dual of the problem
> of ensuring ephemeral values and uses don’t interfere with
> optimization. I’d rather have the first problem? Is it really
> harder?
> 
> 
> 
> So, you have two problems:
> 
> 
> 1) Expressing the invariants. A meta-data language could be invented
> for this initially. Or simply constant operands to an alignment
> intrinsic as in your example.
> 
> 
> 2) Associating the invariants with IR values. Options are, in order
> from the easiest to implement and sell to the public to the most
> complicated but robust:
> 
> 
> 2a) Attach meta-data to the value. This only works when constraint
> dominates all uses. Inlining would need to check before propagating.
> 
> 
> 2b) Add a real use to a special intrinsic: tail call void
> @llvm.assume.aligned(i32* %ptr, i32 16)
> 
> 
> 2c) Add a meta-use to an intrinsic (pure meta-intrinsic): tail call
> void @llvm.assume.aligned(metadata !{i32* %ptr}, i32 16)
> 
> 
> I think it’s a question of whether the simpler approaches work well
> enough for you.
> 
> 
> 
> Is it obvious which of these will be easier to deal with in
> InstCombine? SROA? -- I think that adding a real use will kill a lot
> of optimizations that InstCombine might do. On the other hand,
> updating InstCombine to propagate the invariants might also be quite
> complicated (this is the benefit of adding a real use... we get the
> "updating" of the invariants for free, and optimizations are blocked
> only when they'd kill the invariant (or, at least that's the
> theory)).
> 
> 
> 
> That was also my intuition, and I didn't like the idea of meta-data
> interfering with optimization. However, I’m no longer as interested
> in taking a giant step toward pervasive meta-intrinsics. I would go
> down the path of real uses first until we have compelling data or
> hit more concrete problems. e.g. What happens if you add an
> invariant instrinsic to every load?
> 
> 
> The meta-data use is a potential back-up solution if we hit problems.
> 
> 
> -Andy
> 
> 
> 
> 
> 
> Thanks again,
> Hal
> 
> 
> 
> 
> 
> -Andy
> 
> 
> 
> 
> 
> 
> 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
> 
> 
> --
> Hal Finkel
> Assistant Computational Scientist
> Leadership Computing Facility
> Argonne National Laboratory
> 

-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory