On Wed, Sep 19, 2012 at 6:30 PM, Andrew Trick <atrick at apple.com> wrote:> > On Sep 19, 2012, at 2:18 PM, Preston Briggs <preston.briggs at gmail.com> > wrote: > > On Tue, Sep 18, 2012 at 10:59 PM, Andrew Trick <atrick at apple.com> wrote: > >> >> On Sep 18, 2012, at 8:21 PM, Preston Briggs <preston.briggs at gmail.com> >> wrote: >> >> Given the following SCEV, >> >> *(sext i32 {2,+,1}<nw><%for.body> to i64)* >> >> >> from the following C source, >> >> *void strong3(int *A, int *B, int n) {* >> * for (int i = 0; i < n; i++) {* >> * A[i + 2] = i;* >> * ...* >> * }* >> *}* >> >> >> Since the No-Wrap flag is set on the addrec, can't I safely rewrite it as >> >> *{2,+,1}<nw><%for.body>* >> >> >> If I can, why isn't the SCEV package simplifying things for me? >> >> >> The short answer is that SCEV is terrible at preserving NSW flags. I >> personally don't believe they belong in SCEV but the merits of making any >> design change here are dubious. >> >> To understand one example of SCEV dropping NSW, see createSCEV for >> Instruction::Add. Synopsis: your add is not a "basic induction variable" so >> its NSW flag does not bound the number of loop iterations. We only know >> that the add's original IR users expect NSW. There could be other IR adds >> with the same expression, but without the NSW flag. SCEV doesn't know >> anything about acyclic control flow or IR users, so it must drop the flags. >> >> I would try hard not to rely on NSW flags on arbitrary SCEVs. I would >> first find the phi or basic induction variable before checking the >> recurrence's NSW flag. Or, better yet, only rely on SCEVAddRec's NW (no >> self-wrap flag) rather than NSW. Notice that the NW is preserved in your >> add's recurrence! >> >> -Andy >> >> > OK. I think... > Basically, I'm trying to understand how two subscripts relate to one > another. When I find sign and zero extensions, life gets confusing. In an > effort to keep life simple, I begin by walking though the expressions, > trying to eliminate extensions where it won't change the answer. For > example, I think > > *(sext i32 {2,+,1}<nw><%for.body> to i64) > * > > is the same as > > *{2,+,1}<nw><%for.body>* > > right? > > Mechanically, when I see an sext over an addrec and the addrec has the NW > flag, then I can rewrite is as an addrec<nw> with the base and step > extended. In this case, the base and step are constants, which are > particularly easy. > > On the other hand, if the addrec is missing the NW flag, I'd be making a > mistake. > > In a similar vein, it seems plausible that I can rewrite a sign-extend > over an add (or multiply), as long as the add (multiply) has the NSW flag, > right? Same for zero-extend, over add with NUW flag. > > > Sorry, I probably led you astray. No-self-wrap is useful for determining > trip count, but does not mean that sign/zero extension can be hoisted. > > But if you run your analysis after -indvars, the sign-extension should be > removed if possible. The algorithm walks the derived induction variables > specifically looking for add nsw/nuw and replacing only those IR users with > a wide induction variable. See GetExtendedOperandRecurrence. > > If you have a situation where the sign extends cannot removed, then you > may need your own IR-level analysis to determine whether you can ignore > them. Otherwise, you may run into trouble operating on SCEVs that contain > sext/zext/truncs. Are all your array indices uniformly sign-extended? I > don't know if this is a good idea, but why can't you consider the sext > operand the array index rather than the gep operand? If you prove that the > narrow indices are disjoint, then the extended indices must be disjoint. > SCEV operations should work fine on the narrow indices which shouldn't have > any impure type casting operations. > > This can all be avoided by limiting your optimization to code that uses > pointer-size loop counters! > > -Andy >The array indices are out of my control; depends on the code people write. If they'd use long ints for everything, life would be good; but ints happen. I'll play with -indvars. Thanks, Preston -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20120919/af4ca8d7/attachment.html>
On Wed, Sep 19, 2012 at 9:29 PM, Preston Briggs <preston.briggs at gmail.com>wrote:> On Wed, Sep 19, 2012 at 6:30 PM, Andrew Trick <atrick at apple.com> wrote: > >> >> On Sep 19, 2012, at 2:18 PM, Preston Briggs <preston.briggs at gmail.com> >> wrote: >> >> On Tue, Sep 18, 2012 at 10:59 PM, Andrew Trick <atrick at apple.com> wrote: >> >>> >>> On Sep 18, 2012, at 8:21 PM, Preston Briggs <preston.briggs at gmail.com> >>> wrote: >>> >>> Given the following SCEV, >>> >>> *(sext i32 {2,+,1}<nw><%for.body> to i64)* >>> >>> >>> from the following C source, >>> >>> *void strong3(int *A, int *B, int n) {* >>> * for (int i = 0; i < n; i++) {* >>> * A[i + 2] = i;* >>> * ...* >>> * }* >>> *}* >>> >>> >>> Since the No-Wrap flag is set on the addrec, can't I safely rewrite it as >>> >>> *{2,+,1}<nw><%for.body>* >>> >>> >>> If I can, why isn't the SCEV package simplifying things for me? >>> >>> >>> The short answer is that SCEV is terrible at preserving NSW flags. I >>> personally don't believe they belong in SCEV but the merits of making any >>> design change here are dubious. >>> >>> To understand one example of SCEV dropping NSW, see createSCEV for >>> Instruction::Add. Synopsis: your add is not a "basic induction variable" so >>> its NSW flag does not bound the number of loop iterations. We only know >>> that the add's original IR users expect NSW. There could be other IR adds >>> with the same expression, but without the NSW flag. SCEV doesn't know >>> anything about acyclic control flow or IR users, so it must drop the flags. >>> >>> I would try hard not to rely on NSW flags on arbitrary SCEVs. I would >>> first find the phi or basic induction variable before checking the >>> recurrence's NSW flag. Or, better yet, only rely on SCEVAddRec's NW (no >>> self-wrap flag) rather than NSW. Notice that the NW is preserved in your >>> add's recurrence! >>> >>> -Andy >>> >>> >> OK. I think... >> Basically, I'm trying to understand how two subscripts relate to one >> another. When I find sign and zero extensions, life gets confusing. In an >> effort to keep life simple, I begin by walking though the expressions, >> trying to eliminate extensions where it won't change the answer. For >> example, I think >> >> *(sext i32 {2,+,1}<nw><%for.body> to i64) >> * >> >> is the same as >> >> *{2,+,1}<nw><%for.body>* >> >> right? >> >> Mechanically, when I see an sext over an addrec and the addrec has the NW >> flag, then I can rewrite is as an addrec<nw> with the base and step >> extended. In this case, the base and step are constants, which are >> particularly easy. >> >> On the other hand, if the addrec is missing the NW flag, I'd be making a >> mistake. >> >> In a similar vein, it seems plausible that I can rewrite a sign-extend >> over an add (or multiply), as long as the add (multiply) has the NSW flag, >> right? Same for zero-extend, over add with NUW flag. >> >> >> Sorry, I probably led you astray. No-self-wrap is useful for determining >> trip count, but does not mean that sign/zero extension can be hoisted. >> >> But if you run your analysis after -indvars, the sign-extension should be >> removed if possible. The algorithm walks the derived induction variables >> specifically looking for add nsw/nuw and replacing only those IR users with >> a wide induction variable. See GetExtendedOperandRecurrence. >> >> If you have a situation where the sign extends cannot removed, then you >> may need your own IR-level analysis to determine whether you can ignore >> them. Otherwise, you may run into trouble operating on SCEVs that contain >> sext/zext/truncs. Are all your array indices uniformly sign-extended? I >> don't know if this is a good idea, but why can't you consider the sext >> operand the array index rather than the gep operand? If you prove that the >> narrow indices are disjoint, then the extended indices must be disjoint. >> SCEV operations should work fine on the narrow indices which shouldn't have >> any impure type casting operations. >> >> This can all be avoided by limiting your optimization to code that uses >> pointer-size loop counters! >> >> -Andy >> > > The array indices are out of my control; depends on the code people > write. If they'd use long ints for everything, life would be good; but ints > happen. > > I'll play with -indvars. > > Thanks, > Preston >Ah, -indvars works a treat. -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20120919/7be6108c/attachment.html>
Hi,> Sorry, I probably led you astray. No-self-wrap is useful for determining > trip count, but does not mean that sign/zero extension can be hoisted. > > But if you run your analysis after -indvars, the sign-extension should be > removed if possible. The algorithm walks the derived induction variables > specifically looking for add nsw/nuw and replacing only those IR users with > a wide induction variable. See GetExtendedOperandRecurrence. > > If you have a situation where the sign extends cannot removed, then you may > need your own IR-level analysis to determine whether you can ignore them. > Otherwise, you may run into trouble operating on SCEVs that contain > sext/zext/truncs. Are all your array indices uniformly sign-extended? I > don't know if this is a good idea, but why can't you consider the sext > operand the array index rather than the gep operand? If you prove that the > narrow indices are disjoint, then the extended indices must be disjoint. > SCEV operations should work fine on the narrow indices which shouldn't have > any impure type casting operations. > > This can all be avoided by limiting your optimization to code that uses > pointer-size loop counters! > > -Andy > > > The array indices are out of my control; depends on the code people write. If > they'd use long ints for everything, life would be good; but ints happen.I thought array indices were promoted to a larger size when possible... This came up with Ada where loops with i8 counters are quite common. Dan added logic to boost the size of the loop counters, but perhaps it doesn't promote them beyond i32, or doesn't apply here for some reason? Ciao, Duncan.> > I'll play with -indvars. > > Thanks, > Preston > > > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >
On Sep 20, 2012, at 1:28 AM, Duncan Sands <baldrick at free.fr> wrote:> Hi, > >> Sorry, I probably led you astray. No-self-wrap is useful for determining >> trip count, but does not mean that sign/zero extension can be hoisted. >> >> But if you run your analysis after -indvars, the sign-extension should be >> removed if possible. The algorithm walks the derived induction variables >> specifically looking for add nsw/nuw and replacing only those IR users with >> a wide induction variable. See GetExtendedOperandRecurrence. >> >> If you have a situation where the sign extends cannot removed, then you may >> need your own IR-level analysis to determine whether you can ignore them. >> Otherwise, you may run into trouble operating on SCEVs that contain >> sext/zext/truncs. Are all your array indices uniformly sign-extended? I >> don't know if this is a good idea, but why can't you consider the sext >> operand the array index rather than the gep operand? If you prove that the >> narrow indices are disjoint, then the extended indices must be disjoint. >> SCEV operations should work fine on the narrow indices which shouldn't have >> any impure type casting operations. >> >> This can all be avoided by limiting your optimization to code that uses >> pointer-size loop counters! >> >> -Andy >> >> >> The array indices are out of my control; depends on the code people write. If >> they'd use long ints for everything, life would be good; but ints happen.Random aside: I realize that as a practical engineer, there is value in being able to just accept certain obstacles as facts of life. However, valuable engineering insights sometimes depend on recognizing the source of obstacles, rather than just the ability to cleverly work around them, so there is value in keeping in mind the fact that this whole situation is caused by a quirk of C in common usage.> I thought array indices were promoted to a larger size when possible... This > came up with Ada where loops with i8 counters are quite common. Dan added > logic to boost the size of the loop counters, but perhaps it doesn't promote > them beyond i32, or doesn't apply here for some reason?The pass that does this is -indvars, and it does promote beyond i32 as appropriate in many common cases, and it sounds like it's working here, from subsequent messages.> > Ciao, Duncan. > >> >> I'll play with -indvars.Dan