congzhe cao via llvm-dev
2021-Feb-07 20:29 UTC
[llvm-dev] SCEV determines the inner loop induction variable to be loop-invariant at the scope of the outer loop
Hi Stefanos, Thanks a lot for providing the resources - they are definitely helpful. Best regards, Congzhe On Wed, Feb 3, 2021 at 4:54 PM Stefanos Baziotis < stefanos.baziotis at gmail.com> wrote:> Hi Congzhe, > > Could you clarify the first question? Whose correctness is in question? > backedgeTakenCount() is supposed to always be correct of course. That is > different from whether it can always compute the backedge taken count. > Maybe not and it'll tell you. > > For the second question: There's no special distinction about induction > variables. The same logic is for them or other variables and the basic > question is "Does your value change because of the loop?" > Now, if you want more resources on understanding the general concepts of > scalar evolution, then I recommend these two: > 1) > http://users.uoa.gr/~sdi1600105/compilers/introduction-to-scalar-evolution.html > 2) https://www.youtube.com/watch?v=AmjliNp0_00 > > Disclaimer: The first resource is an article of mine. The reason I > recommend it is because I created it because I think it is a very quick and > very intuitive introduction, that uses a different intuition than I usually > see in tutorials (although this intuition is the one it seems that almost > all experienced devs use in their minds). > That said, I would definitely recommend watching 2) either you read 1) or > not. > > Best, > Stefanos > > Στις Τετ, 3 Φεβ 2021 στις 10:16 μ.μ., ο/η congzhe cao via llvm-dev < > llvm-dev at lists.llvm.org> έγραψε: > >> Hi Michael, >> >> Thanks for the reply! As you've seen, my purpose is indeed to use >> getSCEVAtScope(V, L) with V being an instruction/value in the inner loop >> and L being the outer loop. >> >> - I can somewhat see that if V is the induction variable for the inner >> loop, then getSCEVAtScope(V, L) tries to derive the backedgeTakenCount of >> the inner loop. Is it always correct? >> >> - I'm also wondering if V is not the induction variable for the inner >> loop but some other value inside the inner loop (so this is a more general >> situation), what would be the expected behavior of getSCEVAtScope(V, L)? It >> would be ideal if you could let me know the logic in SCEV regarding this >> situation. >> >> Thanks again, >> Congzhe >> >> On Wed, Feb 3, 2021 at 12:54 PM Michael Kruse <llvmdev at meinersbur.de> >> wrote: >> >>> %j.018 is variant in the innermost loop (for.body4), but after >>> existing that loop, it will have the value before leaving the loop. If >>> you intent to use %j.018 in the innermost loop, you need to call >>> getSCEVAtScope() with the innermost loop as the scope. getSCEVAtScope >>> with a scope outside the loop (or NULL) will try to derive the exit >>> value. >>> >>> Michael >>> >>> >>> >>> Am Mi., 3. Feb. 2021 um 11:11 Uhr schrieb congzhe cao via llvm-dev >>> <llvm-dev at lists.llvm.org>: >>> > >>> > Dear all, >>> > >>> > >>> > >>> > For the following IR which is essentially a doubly nested loop, if we >>> get the SCEV expression for the inner loop induction variable, i.e., >>> %j.018, at the scope of the outer loop using getSCEVAtScope(), the result >>> is: 9. That is a constant, or loop-invariant. >>> > >>> > >>> > However, %j.018 does keep changing within the scope of the outer loop >>> since it is the induction variable of the inner loop, so it is not >>> straightforward to me why %j.018 is considered a loop-invariant. Something >>> like “{0,+,1}<nuw><nsw><%for.body4>” would make more sense to me. >>> > >>> > >>> > >>> > I’m wondering if I can get any comments on that? >>> > >>> > >>> > >>> > Best regards, >>> > >>> > Congzhe >>> > >>> > >>> > >>> > *************************************************************** >>> > >>> > define dso_local i32 @main() { >>> > >>> > entry: >>> > >>> > br label %for.cond1.preheader >>> > >>> > >>> > >>> > for.cond1.preheader: ; preds >>> %for.cond.cleanup3, %entry >>> > >>> > %i.020 = phi i32 [ 0, %entry ], [ %inc8, %for.cond.cleanup3 ] >>> > >>> > %x.019 = phi i32 [ 17, %entry ], [ %add, %for.cond.cleanup3 ] >>> > >>> > br label %for.body4 >>> > >>> > >>> > >>> > for.cond.cleanup: ; preds >>> %for.cond.cleanup3 >>> > >>> > ret i32 %add >>> > >>> > >>> > >>> > for.cond.cleanup3: ; preds = %for.body4 >>> > >>> > %inc8 = add nuw nsw i32 %i.020, 1 >>> > >>> > %exitcond21 = icmp eq i32 %inc8, 10 >>> > >>> > br i1 %exitcond21, label %for.cond.cleanup, label >>> %for.cond1.preheader >>> > >>> > >>> > >>> > for.body4: ; preds >>> %for.body4, %for.cond1.preheader >>> > >>> > %j.018 = phi i64 [ 0, %for.cond1.preheader ], [ %inc, %for.body4 ] >>> > >>> > %x.117 = phi i32 [ %x.019, %for.cond1.preheader ], [ %add, >>> %for.body4 ] >>> > >>> > %cmp5 = icmp eq i64 %j.018, 9 >>> > >>> > %conv = zext i1 %cmp5 to i32 >>> > >>> > %add = add nsw i32 %x.117, %conv >>> > >>> > call void @_Z3foov() >>> > >>> > %inc = add nuw nsw i64 %j.018, 1 >>> > >>> > %exitcond = icmp eq i64 %inc, 10 >>> > >>> > br i1 %exitcond, label %for.cond.cleanup3, label %for.body4 >>> > >>> > } >>> > >>> > >>> > >>> > declare dso_local void @_Z3foov() local_unnamed_addr #1 >>> > >>> > _______________________________________________ >>> > LLVM Developers mailing list >>> > llvm-dev at lists.llvm.org >>> > https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev >>> >> _______________________________________________ >> LLVM Developers mailing list >> llvm-dev at lists.llvm.org >> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev >> >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20210207/b21b9207/attachment.html>
Stefanos Baziotis via llvm-dev
2021-Feb-07 21:04 UTC
[llvm-dev] SCEV determines the inner loop induction variable to be loop-invariant at the scope of the outer loop
Hi Congzhe, Glad they helped! Feel free to ask any other questions either here or on Discord. Best, Stefanos Στις Κυρ, 7 Φεβ 2021 στις 10:30 μ.μ., ο/η congzhe cao <congzhecao at gmail.com> έγραψε:> Hi Stefanos, > > Thanks a lot for providing the resources - they are definitely helpful. > > Best regards, > Congzhe > > On Wed, Feb 3, 2021 at 4:54 PM Stefanos Baziotis < > stefanos.baziotis at gmail.com> wrote: > >> Hi Congzhe, >> >> Could you clarify the first question? Whose correctness is in question? >> backedgeTakenCount() is supposed to always be correct of course. That is >> different from whether it can always compute the backedge taken count. >> Maybe not and it'll tell you. >> >> For the second question: There's no special distinction about induction >> variables. The same logic is for them or other variables and the basic >> question is "Does your value change because of the loop?" >> Now, if you want more resources on understanding the general concepts of >> scalar evolution, then I recommend these two: >> 1) >> http://users.uoa.gr/~sdi1600105/compilers/introduction-to-scalar-evolution.html >> 2) https://www.youtube.com/watch?v=AmjliNp0_00 >> >> Disclaimer: The first resource is an article of mine. The reason I >> recommend it is because I created it because I think it is a very quick and >> very intuitive introduction, that uses a different intuition than I usually >> see in tutorials (although this intuition is the one it seems that almost >> all experienced devs use in their minds). >> That said, I would definitely recommend watching 2) either you read 1) or >> not. >> >> Best, >> Stefanos >> >> Στις Τετ, 3 Φεβ 2021 στις 10:16 μ.μ., ο/η congzhe cao via llvm-dev < >> llvm-dev at lists.llvm.org> έγραψε: >> >>> Hi Michael, >>> >>> Thanks for the reply! As you've seen, my purpose is indeed to use >>> getSCEVAtScope(V, L) with V being an instruction/value in the inner loop >>> and L being the outer loop. >>> >>> - I can somewhat see that if V is the induction variable for the inner >>> loop, then getSCEVAtScope(V, L) tries to derive the backedgeTakenCount of >>> the inner loop. Is it always correct? >>> >>> - I'm also wondering if V is not the induction variable for the inner >>> loop but some other value inside the inner loop (so this is a more general >>> situation), what would be the expected behavior of getSCEVAtScope(V, L)? It >>> would be ideal if you could let me know the logic in SCEV regarding this >>> situation. >>> >>> Thanks again, >>> Congzhe >>> >>> On Wed, Feb 3, 2021 at 12:54 PM Michael Kruse <llvmdev at meinersbur.de> >>> wrote: >>> >>>> %j.018 is variant in the innermost loop (for.body4), but after >>>> existing that loop, it will have the value before leaving the loop. If >>>> you intent to use %j.018 in the innermost loop, you need to call >>>> getSCEVAtScope() with the innermost loop as the scope. getSCEVAtScope >>>> with a scope outside the loop (or NULL) will try to derive the exit >>>> value. >>>> >>>> Michael >>>> >>>> >>>> >>>> Am Mi., 3. Feb. 2021 um 11:11 Uhr schrieb congzhe cao via llvm-dev >>>> <llvm-dev at lists.llvm.org>: >>>> > >>>> > Dear all, >>>> > >>>> > >>>> > >>>> > For the following IR which is essentially a doubly nested loop, if we >>>> get the SCEV expression for the inner loop induction variable, i.e., >>>> %j.018, at the scope of the outer loop using getSCEVAtScope(), the result >>>> is: 9. That is a constant, or loop-invariant. >>>> > >>>> > >>>> > However, %j.018 does keep changing within the scope of the outer loop >>>> since it is the induction variable of the inner loop, so it is not >>>> straightforward to me why %j.018 is considered a loop-invariant. Something >>>> like “{0,+,1}<nuw><nsw><%for.body4>” would make more sense to me. >>>> > >>>> > >>>> > >>>> > I’m wondering if I can get any comments on that? >>>> > >>>> > >>>> > >>>> > Best regards, >>>> > >>>> > Congzhe >>>> > >>>> > >>>> > >>>> > *************************************************************** >>>> > >>>> > define dso_local i32 @main() { >>>> > >>>> > entry: >>>> > >>>> > br label %for.cond1.preheader >>>> > >>>> > >>>> > >>>> > for.cond1.preheader: ; preds >>>> %for.cond.cleanup3, %entry >>>> > >>>> > %i.020 = phi i32 [ 0, %entry ], [ %inc8, %for.cond.cleanup3 ] >>>> > >>>> > %x.019 = phi i32 [ 17, %entry ], [ %add, %for.cond.cleanup3 ] >>>> > >>>> > br label %for.body4 >>>> > >>>> > >>>> > >>>> > for.cond.cleanup: ; preds >>>> %for.cond.cleanup3 >>>> > >>>> > ret i32 %add >>>> > >>>> > >>>> > >>>> > for.cond.cleanup3: ; preds = %for.body4 >>>> > >>>> > %inc8 = add nuw nsw i32 %i.020, 1 >>>> > >>>> > %exitcond21 = icmp eq i32 %inc8, 10 >>>> > >>>> > br i1 %exitcond21, label %for.cond.cleanup, label >>>> %for.cond1.preheader >>>> > >>>> > >>>> > >>>> > for.body4: ; preds >>>> %for.body4, %for.cond1.preheader >>>> > >>>> > %j.018 = phi i64 [ 0, %for.cond1.preheader ], [ %inc, %for.body4 ] >>>> > >>>> > %x.117 = phi i32 [ %x.019, %for.cond1.preheader ], [ %add, >>>> %for.body4 ] >>>> > >>>> > %cmp5 = icmp eq i64 %j.018, 9 >>>> > >>>> > %conv = zext i1 %cmp5 to i32 >>>> > >>>> > %add = add nsw i32 %x.117, %conv >>>> > >>>> > call void @_Z3foov() >>>> > >>>> > %inc = add nuw nsw i64 %j.018, 1 >>>> > >>>> > %exitcond = icmp eq i64 %inc, 10 >>>> > >>>> > br i1 %exitcond, label %for.cond.cleanup3, label %for.body4 >>>> > >>>> > } >>>> > >>>> > >>>> > >>>> > declare dso_local void @_Z3foov() local_unnamed_addr #1 >>>> > >>>> > _______________________________________________ >>>> > LLVM Developers mailing list >>>> > llvm-dev at lists.llvm.org >>>> > https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev >>>> >>> _______________________________________________ >>> LLVM Developers mailing list >>> llvm-dev at lists.llvm.org >>> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev >>> >>-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20210207/347fba5f/attachment.html>