[llvm-dev] SCEV determines the inner loop induction variable to be loop-invariant at the scope of the outer loop

[congzhe cao via llvm-dev]

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>