----- Original Message -----> From: "Andrew Trick" <atrick at apple.com> > To: "Michele Scandale" <michele.scandale at gmail.com> > Cc: "llvmdev at cs.uiuc.edu List" <llvmdev at cs.uiuc.edu> > Sent: Thursday, February 7, 2013 11:56:42 PM > Subject: Re: [LLVMdev] Rotated loop identification > > > On Feb 7, 2013, at 10:53 AM, Michele Scandale > <michele.scandale at gmail.com> wrote: > > >> Thanks for the details. Please add them to a bug report. > > > > I will do this. > > Thanks. > > >> InstCombine is certainly interfering with our ability to analyze > >> the loop. I think the problem is that ScalarEvolution cannot > >> reason about signed division. This is a general problem > >> independent of your target. At the moment I'm not sure if we can > >> teach ScalarEvolution to reason about this, or if we can defer > >> certain InstCombine's until after loop passes run, including > >> target-specific loop passes (it's hard for me to say whether this > >> InstCombine really a necessary canonicalization before other > >> passes). A bug report would be appropriate. > > > > It sounds to me that the same capabilities of InstCombine should be > > implemented > > also in the ScalarEvolution. > > It's doable, just not pretty. We could special-case SCEV's > isImpliedCond to look for an sdiv opcode and recognize the inverse > of InstCombine's trick. I doubt it makes sense to add an SDIV > operator to SCEV since SCEV would want to assume modulus division, > and the IR sdiv is a truncating divide. > > >> Absent a fix for the above problem, it is certainly possible for > >> you to add target-specific intrinsics. I can't guarantee that it > >> won't interfere with optimization. It might also be possible to > >> add metadata to the loop exit branch when it is cloned by > >> LoopRotate, indicating that the loop is guarded by the same > >> condition. I don't think we want something like this on trunk > >> though since it is a heavy-handed workaround that could be hard > >> to maintain. > > > > Following also the proposal 'Parallel Loop Metadata' it seems to me > > that > > basically there's the same problem. Maybe I've not fully understood > > the things > > but, assuming to have the ability to map metadata to BasicBlocks > > then such > > informations could be registered directly to the loop header or > > latch, without > > custom intrinsics and hopefully without interfering with the > > optimizer. > > > > What do you think about this? > > There's been talk of adding metata do the branch that terminates the > loop latch block. What llvm calls the "latch" is just a unique > backward branch to the loop header and not necessarilly even a loop > exit. > > I'm not sure how you would interpret that metadata, since the branch > exit may be rewritten (just like the loop guard). For example, the > indvars pass may convert it into a != test. > > 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.htmlIf 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? Thanks again, Hal> > But really, the only thing likely to make it onto trunk for this bug > is the SCEV fix mentioned above. More details can be discussed in > PR15205. > > -Andy > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >
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). - 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. - 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. 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 -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130208/b5df288b/attachment.html>
Eric Christopher
2013-Feb-08 20:09 UTC
[LLVMdev] llvm.meta (was Rotated loop identification)
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). > > - llvm.dbg > > Are there any problems with our current approach? > >Haven't been following the current discussion, but in general there aren't any problems with having llvm.dbg as a class of intrinsic. -eric -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130208/bd0fcf9d/attachment.html>
----- 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