<html><head><meta http-equiv="Content-Type" content="text/html charset=windows-1252"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;"><br><div><div>On Sep 7, 2013, at 7:41 AM, Hal Finkel <<a href="mailto:hfinkel@anl.gov">hfinkel@anl.gov</a>> wrote:</div><blockquote type="cite"><div style="font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><blockquote type="cite">On Feb 7, 2013, at 10:58 PM, Hal Finkel < <a href="mailto:hfinkel@anl.gov">hfinkel@anl.gov</a> > wrote:<br><br><br><br><br>As long as this is brainstorming time, I actually like the idea of<br>an<br>llvm.invariant intrinsic that the optimizers know to ignore. I<br>like<br>it for other purposes, but would happen to work for you as a<br>temporary workaround. It could take one or two IR values (as<br>metadata operands) and a metadata language describing the<br>invariant,<br>such as a relational operator and optional constant. In your case,<br>you want to know that the loop counter's starting value is less<br>than<br>its limit, so you could conveniently plop one of those in the loop<br>preheader. The invariant would only go away if no one else used<br>the<br>value, which in your case would make sense (e.g. if the loop test<br>were rewritten in terms of %b, you probably wouldn't need the<br>invariant any more).<br><br><a href="http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20121210/158601.html">http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20121210/158601.html</a><br><br>If you're in favor of this approach, can I pop out of the woodwork<br>and say that it appears that we have a reasonably-large group of<br>contributors in favor of an invariant intrinsic and we should move<br>forward on that basis?<br><br><br>A general llvm.invariant does seem like a convenient thing. I'm<br>not<br>pushing very hard because I don't need it for anything I'm working<br>on yet, and wasn't aware that anyone else liked this particular<br>idea. But I haven't heard any argument against it. I am aware that<br>a<br>lot of people want to attach new semantics to the IR that are not<br>necessarily easy to preserve, so I don't want to oversell a<br>solution.<br><br><br>I don't have an opinion on whether each type of invariant should<br>get<br>its own intrinsic ID or we should have one and use the flexibility<br>of metadata operands. The important thing is that the optimizer<br>have<br>a uniform approach to handling them, and that they truly cannot<br>interfere with optimization other than as intended. For the sake<br>of<br>discussion, and to avoid confusion with the current, badly named<br>llvm.invariant, I'll just call these llvm.meta intrinsics.<br><br><br>I would only endorse a new llvm.meta approach if we're sure we can<br>unify or replace most of the current meta-style intrinsics. But I<br>first need to better understand the motivation for those<br>approaches,<br>which I have not personally worked with much (they're somewhat<br>marginalized).<br><br>Thanks for writing this! As you point out there are already a<br>number of "pseudo-users" in LLVM, and we don't have a good general<br>scheme for handling them. Currently, special handling for<br>llvm.dbg, expect, etc. are coded into several (many) different<br>places to make them appear free, and adding more in a similar way<br>might become unmanageable. Even worse, these intrinsics break the<br>"hasOneUser" check, and this interferes with optimization. This<br>may not be important for debug intrinsics, but certainly is for<br>features intended to help optimization.<br><br>Based on this, it seems that we need to differentiate two classes<br>of users: real users and, as Chandler called them, ephemeral<br>users. We could update hasOneUser() to be hasOneUser(bool<br>countEphemerals = false), or something like that, and the trick<br>will be to support this without requiring additional iteration<br>over all users. Thoughts?<br><br>Redefining hasOneUser() would be the most efficient approach, and<br>definitely possible. But it would add complexity to a fundamental<br>property of the IR and potentially cause bugs when developers forget<br>to check the meta users.<br><br>I was proposing to use meta-data operands in the intrinsic instead.<br>They add no visible users. They can be left dangling and cleaned up<br>lazily. WeakVH are expensive, but I'm not worried about cost yet.<br>The added complexity in this case happens at SSA update, which does<br>need to visit meta users explicitly. I believe this is currently<br>broken for dbg.value and works by luck for simple cases. So we need<br>to fix this one way or another.<br><br>I'd still like to be able to chart a way forward on this. Regarding<br>defining invariants, I don't understand how using metadata<br>intrinsics really helps because, while a metadata operand could be<br>used to tie the invariant to a value being constrained, the<br>invariant expression itself would add additional uses to the values<br>used in its subexpressions. When I had discussed this with Chandler<br>(many months ago now), we had developed a working assumption that if<br>the invariant is worth having, then it is worth carrying as a<br>dependency of the values it constrains. This may not be true, but I<br>think is a viewpoint worth evaluating.<br><br><br>Metadata is a better approach because it doesn’t interfere with<br>optimizations that are free to ignore it.<br><br><br>Yes, if the invariant expression requires IR values and real uses,<br>then that defeats the purpose. I prefer a meta-data language to the<br>alternative of ephemeral expressions. I could be convinced either<br>way. I just think it will be confusing to mix ephemeral expressions<br>with program logic and impractical to make it transparent to<br>optimizations. Not the end of the world though, and I’ll listen to<br>any strong arguments to the contrary.<br></blockquote><br>When you say "metadata language", what do you have in mind? I can think of two general schemes:<br><br>1. A language in which each expression in the language is a metadata node; maybe something like:<br> !invariant1 = !{ !"eq", !{ !"urem", i32 %value, i32 48 }, i32 0 }<br><br>2. A language encoded in a string with some syntax for substitution values; maybe something like:<br> !invariant1 = !{ !"(eq (urem #1, 48), 0)", i32 %value}<br></div></blockquote><div><br></div><div><div>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.</div><div><br></div><div>Either: @llvm.invariant(i8* %adr, metadata !invariant)</div><div><br></div><div> Or: @llvm.invariant(metadata !{i32* %adr}, metadata !invariant)</div><div><br></div><div> With: !invariant1 = !{ !"align", i32 48, i32 0 }</div><div><br></div><div>Or just skip the meta-data altogether:</div><div> @llvm.align(i8*,i32, i32)</div><div><br></div><div>I don't know if it's better to use strings or enums. I'm not a meta-data designer.</div><div><br></div><div>If we only try to solve your immediate problem of builtin_assume_aligned, isn't that good enough for now? Are you concerned about generalizing this to builtin_assume?</div></div><br><blockquote type="cite"><div style="font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><blockquote type="cite">On the other hand, when I started down this road I was motivated by a<br>desire to implement support for __builtin_assume_aligned. I would<br>still like to do this, or something like this to get equivalent<br>functionality. The idea of metadata references seems like it might<br>work well for alignment assumptions, as a restricted special case.<br>Maybe something like this:<br><br>tail call void @llvm.assume.aligned(metadata !{i32* %ptr}, i32 16)<br><br><br><br>I think this concept is sound except for the problem of enforcing SSA<br>properties. Do meta-data operands need to dominate? If so, we need<br>to fix SSA updater to deal with this. Preserving the meta-data after<br>code duplication would effectively require a meta-phi. We don’t want<br>a real phi because we don’t want a real use. Admittedly this would<br>be annoying, but we could always drop the metadata users instead.<br>You could get by initially without solving this problem, as we’ve<br>done with dbg.value.<br><br><br>I’m a bit less enthusiastic about meta-intrinsics after realizing<br>that the only current example, dbg.value, is a poor use of the<br>concept. It should have been meta-data attached directly to the<br>value with source line info instead.<br></blockquote><br>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.<br></div></blockquote><div><br></div><div>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.</div><div><br></div><blockquote type="cite"><div style="font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><br><blockquote type="cite"><br><br>If we could demonstrate the advantage of converting lifetime<br>intrinsics to meta-instrinsics (not real uses), then I’d be all for<br>it.<br><br><br><br><br>but then the problem becomes making sure that these things stick<br>around long enough to help the interesting inlining cases. Thoughts?<br><br><br><br>Ensuring meta-data sticks around seems like the dual of the problem<br>of ensuring ephemeral values and uses don’t interfere with<br>optimization. I’d rather have the first problem? Is it really<br>harder?<br><br><br><br>So, you have two problems:<br><br><br>1) Expressing the invariants. A meta-data language could be invented<br>for this initially. Or simply constant operands to an alignment<br>intrinsic as in your example.<br><br><br>2) Associating the invariants with IR values. Options are, in order<br>from the easiest to implement and sell to the public to the most<br>complicated but robust:<br><br><br>2a) Attach meta-data to the value. This only works when constraint<br>dominates all uses. Inlining would need to check before propagating.<br><br><br>2b) Add a real use to a special intrinsic: tail call void<br>@llvm.assume.aligned(i32* %ptr, i32 16)<br><br><br>2c) Add a meta-use to an intrinsic (pure meta-intrinsic): tail call<br>void @llvm.assume.aligned(metadata !{i32* %ptr}, i32 16)<br><br><br>I think it’s a question of whether the simpler approaches work well<br>enough for you.<br><br><br></blockquote><br>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)).<br></div></blockquote><div><br></div><div>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?</div><div><br></div><div>The meta-data use is a potential back-up solution if we hit problems.</div><div><br></div><div>-Andy</div><div><br></div><blockquote type="cite"><div style="font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><br>Thanks again,<br>Hal<br><br><blockquote type="cite"><br><br>-Andy<br><br><br><br><br><br><br>I contrived a test case for this and submitted PR15501.<br><br>Interesting.<br><br>Thanks again,<br>Hal<br><br><br><br><br>-Andy<br><br><br><br>We should also use this new class of users to replace a lot of the<br>special-case code that currently exists for making some of these<br>intrinsics free (and removing them before CodeGen, etc.).<br><br>Specifically regarding invariants; I think that dbg and lifetime<br>(and annotation?) would need to remain separate intrinsics. The<br>invariant could have both a 'required' and 'expected' mode, and we<br>could merge expect into it. Value ranges should fit naturally into<br>the semantics of an invariant.<br><br><br><br><br><br>- llvm.dbg<br><br><br>Are there any problems with our current approach?<br><br><br>- llvm.lifetime and llvm.invariant (for pointers)<br><br><br>Why are they real value users? We probably don't care about extra<br>users of an object base, but are we confident they won't affect<br>optimization except as intended? I'd like to see an experiment<br>where<br>we emit these gratuitously, suppress optimizations that use them,<br>strip them after -O3, and verify no effect on bitcode.<br><br><br>- llvm.annotation<br><br><br>Does anyone use these? Supposedly the optimizer "ignores" them.<br>But<br>the optimizer certainly doesn't ignore additional uses of a value.<br><br>As I recall, the optimizer does not currently consider these free<br>everywhere that it should (by inspection); nevertheless, I've<br>never seem them used anywhere. Why were they introduced?<br><br><br><br><br><br>- llvm.expect<br><br><br>This is injected in the def-use chain. Accidentally running the<br>optimizer with these intrinsics present would be disasterous. It's<br>really the same problem as representing an invariant, just<br>different<br>semantics.<br><br><br>- load range metadata<br><br><br>We should be able to express general value ranges, independent of<br>loads.<br>We should be able to express the invariant conditionally,<br>independent<br>of the value's definition.<br>The load's should be gvn-able without losing the invariants.<br><br>Agreed.<br><br>-Hal<br><br><br><br><br><br>Future uses:<br><br><br>- Relating value to other values (not just a constant range).<br><br><br>- Pointer alignment.<br><br><br>- Pointers to immutable memory (when dominated by intrinsic).<br><br><br>You mentioned a number of other things you'd like to use<br>invariants<br>for in a previous post, I won't try to repeat them.<br><br><br>-Andy<br><br><br><br>--<br>Hal Finkel<br>Assistant Computational Scientist<br>Leadership Computing Facility<br>Argonne National Laboratory<br><br></blockquote><br>--<span class="Apple-converted-space"> </span><br>Hal Finkel<br>Assistant Computational Scientist<br>Leadership Computing Facility<br>Argonne National Laboratory</div></blockquote></div><br></body></html>