[llvm-dev] SCEV determines the inner loop induction variable to be loop-invariant at the scope of the outer loop
Stefanos Baziotis via llvm-dev
llvm-dev at lists.llvm.org
Sun Feb 7 13:04:08 PST 2021
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>
More information about the llvm-dev
mailing list