> Thanks for the details. Please add them to a bug report.I will do this.> 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.> 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? Thanks again. Best regards, Michele Scandale
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.html 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
----- 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 02/08/2013 06:56 AM, Andrew Trick wrote:> 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.html >I read the post you suggested. If I understood correctly the idea I like it very much. Just to better understand, when you say <<< It would be generally useful to model an intrinsic that is free and not a strong use but does have control dependence. That's what I call a meta-intrinsic. >>> you mean that this class of intrinsics cannot be removed because they have no uses and the can't be moved freely, e.g. hoisted from a loop? Indeed, if they handle a value (they are users), that value would never be eliminated if the only user is the meta-intrinsic itself? Maybe this kind of behaviour must be a parameter respect to the semantic you need to implement (At the end, if the intrinsic is the only user and during lowering is simply eliminated all the values used can be checked to be dead and deleted in that case). IMHO this is like a property that an intrinsic can have or not and the proposed llvm.invariant intrinsic is a particular intrinsic that has this property and whose semantic is to describe invariant facts (the metadata language you mentioned). Thanks again. Best regards, Michele Scandale