[SCEV] Strengthen variance condition in calculateLoopDisposition

[mkazantsev]

Summary

Given loops L1 and L2 with AddRecs AR1 and AR2 varying in them respectively.
When identifying loop disposition of AR2 w.r.t. L1, we only say that it is varying if
L1 contains L2. But there is also a possible situation where L1 and L2 are
consecutive sibling loops within the parent loop. In this case, AR2 is also varying
w.r.t. L1, but we don't correctly identify it.

It can lead, for exaple, to attempt of incorrect folding. Consider:

AR1 = {a,+,b}<L1>
AR2 = {c,+,d}<L2>
EXAR2 = sext(AR1)
MUL = mul AR1, EXAR2

If we incorrectly assume that EXAR2 is invariant w.r.t. L1, we can end up trying to
construct something like: {a * {c,+,d}<L2>,+,b * {c,+,d}<L2>}<L1>, which is incorrect
because AR2 is not available on entrance of L1.

Both situations "L1 contains L2" and "L1 preceeds sibling loop L2" can be handled
with one check: "header of L1 dominates header of L2". This patch replaces the old
insufficient check with this one.

[reames]

Max, I don't quite follow your discussion enough to know for sure, but I suspect there's something wrong with your framing here. A induction variable in one loop may be loop invariant with respect to sibling loop. That's normal. Is there maybe a subcase here? Or are you looking at flawed assumption in caller code?

int i;
for (i = 0; i < N; i++) { /* i is variant, j is undefined here */ }
for (int j = 0; j < M; j++) {/* i is invariant, j is varying. */ }

[mkazantsev]

In D39453#918719, @reames wrote:

Max, I don't quite follow your discussion enough to know for sure, but I suspect there's something wrong with your framing here. A induction variable in one loop may be loop invariant with respect to sibling loop. That's normal. Is there maybe a subcase here? Or are you looking at flawed assumption in caller code?

int i;
for (i = 0; i < N; i++) { /* i is variant, j is undefined here */ }
for (int j = 0; j < M; j++) {/* i is invariant, j is varying. */ }

We are speaking about case /* i is variant, j is undefined here */ . We attempt to get the disposition of j w.r.t. the first loop, and we falsely return Invariant in this case. We don't have Undefined stance, so I used Variant instead of it.

I agree that i is invariant w.r.t. loop 2, but this is not the case that we cover in this patch.

[mkazantsev]

lib/Analysis/ScalarEvolution.cpp

10852 ↗

(On Diff #120959)

Just to make it clear: what is meant here is "L and AR are consecutive in this order, i.e. L goes BEFORE the loop where AR is defined".

[mkazantsev]

@reames the problem here is that when we try to simplify sum of i and j in getSCEVAddRecExpr, we falsely assume that j is invariant for i's loop while it should be vice versa: i is invariant for j's loop.

[mkazantsev]

Updated comments in code to make it more clear what is going on.

[reames]

Max and I discussed and realized this comes down to simply needing a much simpler and straight-forward comment. :) If AR is not defined on entry to L, it can't be LoopInvariant with respect to L. The distinction between L being a parent of AR->loop vs a sibling vs a nephew, cousin, etc... really doesn't contribute anything here.

The fact we use LoopVariant to represent "not defined on entry" is slightly confusing, but the code already does that for other cases.

I asked Max to update the comment and add a nephew loop example to the test.

[mkazantsev]

Changed comments, added test with nephew loop.

[reames]

LGTM

llvm/trunk/lib/Analysis/ScalarEvolution.cpp

case scAddRecExpr: {
     // If L is the addrec's loop, it's computable.
     if (AR->getLoop() == L)
       return LoopComputable;
 
     // Add recurrences are never invariant in the function-body (null loop).
     if (!L)
       return LoopVariant;
 
-    // This recurrence is variant w.r.t. L if L contains AR's loop.
-    if (L->contains(AR->getLoop()))
+    // Everything that is not defined at loop entry is variant.
+    if (DT.dominates(L->getHeader(), AR->getLoop()->getHeader()))
       return LoopVariant;
+    assert(!L->contains(AR->getLoop()) && "Containing loop's header does not"
+           " dominate the contained loop's header?");
 
     // This recurrence is invariant w.r.t. L if AR's loop contains L.
     if (AR->getLoop()->contains(L))
       return LoopInvariant;
 
     // This recurrence is variant w.r.t. L if any of its operands
     // are variant.
     for (auto *Op : AR->operands())

llvm/trunk/test/Analysis/ScalarEvolution/different-loops-recs.ll

loop_2:
   %iv.2.2.next = add nsw i64 %iv.2.2, -1
   %tmp17 = icmp slt i64 %iv.2.3.next, %iv.1.1
   br i1 %tmp17, label %loop_2, label %exit
 
 exit:
   %tmp10 = add i32 %iv.1.2, 3
   ret void
 }
+
+define i64 @test_09(i32 %param) {
+
+; CHECK-LABEL: Classifying expressions for: @test_09
+; CHECK:       %iv1 = phi i64 [ %iv1.next, %guarded ], [ 0, %outer.loop ]
+; CHECK-NEXT:    -->  {0,+,1}<nuw><nsw><%loop1>
+; CHECK:       %iv1.trunc = trunc i64 %iv1 to i32
+; CHECK-NEXT:    -->  {0,+,1}<%loop1>
+; CHECK:       %iv1.next = add nuw nsw i64 %iv1, 1
+; CHECK-NEXT:    -->  {1,+,1}<nuw><nsw><%loop1>
+; CHECK:       %iv2 = phi i32 [ %iv2.next, %loop2 ], [ %param, %loop2.preheader ]
+; CHECK-NEXT:    -->  {%param,+,1}<%loop2>
+; CHECK:       %iv2.next = add i32 %iv2, 1
+; CHECK-NEXT:    -->  {(1 + %param),+,1}<%loop2>
+; CHECK:       %iv2.ext = sext i32 %iv2.next to i64
+; CHECK-NEXT:    -->  (sext i32 {(1 + %param),+,1}<%loop2> to i64)
+; CHECK:       %ret = mul i64 %iv1, %iv2.ext
+; CHECK-NEXT:    -->  ((sext i32 {(1 + %param),+,1}<%loop2> to i64) * {0,+,1}<nuw><nsw><%loop1>)
+
+entry:
+  br label %outer.loop
+
+outer.loop:                                 ; preds = %loop2.exit, %entry
+  br label %loop1
+
+loop1:                                           ; preds = %guarded, %outer.loop
+  %iv1 = phi i64 [ %iv1.next, %guarded ], [ 0, %outer.loop ]
+  %iv1.trunc = trunc i64 %iv1 to i32
+  %cond1 = icmp ult i64 %iv1, 100
+  br i1 %cond1, label %guarded, label %deopt
+
+guarded:                                          ; preds = %loop1
+  %iv1.next = add nuw nsw i64 %iv1, 1
+  %tmp16 = icmp slt i32 %iv1.trunc, 2
+  br i1 %tmp16, label %loop1, label %loop2.preheader
+
+deopt:                                            ; preds = %loop1
+  unreachable
+
+loop2.preheader:                                 ; preds = %guarded
+  br label %loop2
+
+loop2:                                           ; preds = %loop2, %loop2.preheader
+  %iv2 = phi i32 [ %iv2.next, %loop2 ], [ %param, %loop2.preheader ]
+  %iv2.next = add i32 %iv2, 1
+  %cond2 = icmp slt i32 %iv2, %iv1.trunc
+  br i1 %cond2, label %loop2, label %exit
+
+exit:                                          ; preds = %loop2.exit
+  %iv2.ext = sext i32 %iv2.next to i64
+  %ret = mul i64 %iv1, %iv2.ext
+  ret i64 %ret
+}
+
+define i64 @test_10(i32 %param) {
+
+; CHECK-LABEL: Classifying expressions for: @test_10
+; CHECK:       %uncle = phi i64 [ %uncle.outer.next, %uncle.loop.backedge ], [ 0, %outer.loop ]
+; CHECK-NEXT:  -->  {0,+,1}<%uncle.loop>
+; CHECK:       %iv1 = phi i64 [ %iv1.next, %guarded ], [ 0, %uncle.loop ]
+; CHECK-NEXT:  -->  {0,+,1}<nuw><nsw><%loop1>
+; CHECK:       %iv1.trunc = trunc i64 %iv1 to i32
+; CHECK-NEXT:  -->  {0,+,1}<%loop1>
+; CHECK:       %iv1.next = add nuw nsw i64 %iv1, 1
+; CHECK-NEXT:  -->  {1,+,1}<nuw><nsw><%loop1>
+; CHECK:       %uncle.outer.next = add i64 %uncle, 1
+; CHECK-NEXT:  -->  {1,+,1}<%uncle.loop>
+; CHECK:       %iv2 = phi i32 [ %iv2.next, %loop2 ], [ %param, %loop2.preheader ]
+; CHECK-NEXT:  -->  {%param,+,1}<%loop2>
+; CHECK:       %iv2.next = add i32 %iv2, 1
+; CHECK-NEXT:  -->  {(1 + %param),+,1}<%loop2>
+; CHECK:       %iv2.ext = sext i32 %iv2.next to i64
+; CHECK-NEXT:  -->  (sext i32 {(1 + %param),+,1}<%loop2> to i64)
+; CHECK:       %ret = mul i64 %iv1, %iv2.ext
+; CHECK-NEXT:  -->  ((sext i32 {(1 + %param),+,1}<%loop2> to i64) * {0,+,1}<nuw><nsw><%loop1>)
+
+entry:
+  br label %outer.loop
+
+outer.loop:                                       ; preds = %entry
+  br label %uncle.loop
+
+uncle.loop:                                       ; preds = %uncle.loop.backedge, %outer.loop
+  %uncle = phi i64 [ %uncle.outer.next, %uncle.loop.backedge ], [ 0, %outer.loop ]
+  br label %loop1
+
+loop1:                                            ; preds = %guarded, %uncle.loop
+  %iv1 = phi i64 [ %iv1.next, %guarded ], [ 0, %uncle.loop ]
+  %iv1.trunc = trunc i64 %iv1 to i32
+  %cond1 = icmp ult i64 %iv1, 100
+  br i1 %cond1, label %guarded, label %deopt
+
+guarded:                                          ; preds = %loop1
+  %iv1.next = add nuw nsw i64 %iv1, 1
+  %tmp16 = icmp slt i32 %iv1.trunc, 2
+  br i1 %tmp16, label %loop1, label %uncle.loop.backedge
+
+uncle.loop.backedge:                              ; preds = %guarded
+  %uncle.outer.next = add i64 %uncle, 1
+  %cond.uncle = icmp ult i64 %uncle, 120
+  br i1 %cond.uncle, label %loop2.preheader, label %uncle.loop
+
+deopt:                                            ; preds = %loop1
+  unreachable
+
+loop2.preheader:                                  ; preds = %uncle.loop.backedge
+  br label %loop2
+
+loop2:                                            ; preds = %loop2, %loop2.preheader
+  %iv2 = phi i32 [ %iv2.next, %loop2 ], [ %param, %loop2.preheader ]
+  %iv2.next = add i32 %iv2, 1
+  %cond2 = icmp slt i32 %iv2, %iv1.trunc
+  br i1 %cond2, label %loop2, label %exit
+
+exit:                                             ; preds = %loop2
+  %iv2.ext = sext i32 %iv2.next to i64
+  %ret = mul i64 %iv1, %iv2.ext
+  ret i64 %ret
+}