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

Wed Feb 17 09:08:54 PST 2021

An cmp instruction where both arguments are loop-invariant would
normally be hoisted before the loop by the LICM or GVN pass.

Support for scCMP might be useful, although I don't expect many
compare boolean exit values (that are not already hoisted by LICM)
from loops to be constant. However, support for a conditional SCEV
expression (if /select) would be nice.However, extending
ScalarEvolution can be a lot of work.

FileCheck tests are messy to update, no way around that unfortunately.

Michael

Am Di., 16. Feb. 2021 um 22:17 Uhr schrieb congzhe cao <congzhecao at gmail.com>:
>
> Hi there,
>
> Can I have one further question please? Currently SCEV uses `computeLoopDisposition(SCEV *S, Loop *L)` to check if a SCEV expression is a loop invariant. The concern here is that it does not handle cmp instructions very well, because cmp instructions are not recognized as a SCEV type - it is merely an "scUnknown" type. For  scUnknown, `  computeLoopDisposition()` only checks if L contains the underlying instruction from S and if that is the case, it determines S is not a loop invariant, which may not be very accurate.
>
> However for a cmp instruction, I suspect it is okay to say if both operands are loop-invariants, then this cmp instruction can be determined to be a loop invariant. I added some code in `computeLoopDisposition()` under the case of scUnknown that executes that logic -  if both operands are loop-invariants then this cmp instruction is a loop invariant. This way we can determine some cmp instructions to be loop invariants (whereas previously they were not determined to be loop invariants), and may expose opportunities for optimization. It unfortunately causes a number of regression test failures and benchmark compilation failures. The failures are from induction variable simplification, ScalarEvolution and ScalarEvolutionExpander. I am able to add fixes here and there to avoid those failures, but my concern is that it seems messy (different fixes in a number of places that address problems caused by loop-invariance of cmp instructions).
>
> Would it be preferred to add full support for cmp instructions in SCEV, like adding and supporting an "scCMP" type in `SCEVTypes`?
>
> Thanks,
> Congzhe
>
> On Sun, Feb 7, 2021 at 4:04 PM Stefanos Baziotis <stefanos.baziotis at gmail.com> wrote:
>>
>> 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