[IRCE] Ensure that expanded exit values are available in loop's preheader

[mkazantsev]

Summary

This patch adds a check that SCEV of main and preloop exit conditions are available in
predecessor where they are expanded. In theory, this may be broken if these values
depend on SCEVUnknown which cannot be expanded to preheader. In practice, such
cases get rejected earlier, but this may change in future.

[reames]

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

1468

To avoid confusion, call this something like MainL or OriginalL.

1485–1486

Put these in the other order so that we don't run isSafeToExpandAt if the value is not available. I don't know that it currently does, but isSafeToExpandAt could reasonable have a precondition that the location is available. :)

1512–1513

Same.

test/Transforms/IRCE/bad_expander.ll

169

What is this trying to test? The potentially faulting load doesn't contribute to any latch or range check, so how would it show up in the split value?

200

Same problem.

[mkazantsev]

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

1485–1486

We invoke isSafeToExpandAt for loop's preheader. From within this function, we don't have any information about the fact that our insertion point is connected to some loop, and whether it is important for us or not. The loop in this particular case is important because we know that we are going to use the expanded value as the entry value of some loop's Phi; in general case, we don't always do so so shouldn't always care about loops in expander.

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

bool NeedsPreLoop =
       Increasing ? SR.LowLimit.hasValue() : SR.HighLimit.hasValue();
   bool NeedsPostLoop =
       Increasing ? SR.HighLimit.hasValue() : SR.LowLimit.hasValue();
 
   Value *ExitPreLoopAt = nullptr;
   Value *ExitMainLoopAt = nullptr;
   const SCEVConstant *MinusOneS =
       cast<SCEVConstant>(SE.getConstant(IVTy, -1, true /* isSigned */));
+  auto *L = LI.getLoopFor(MainLoopStructure.Header);
 
   if (NeedsPreLoop) {
     const SCEV *ExitPreLoopAtSCEV = nullptr;
 
     if (Increasing)
       ExitPreLoopAtSCEV = *SR.LowLimit;
     else {
       if (CanBeMin(SE, *SR.HighLimit, IsSignedPredicate)) {
         DEBUG(dbgs() << "irce: could not prove no-overflow when computing "
                      << "preloop exit limit.  HighLimit = " << *(*SR.HighLimit)
                      << "\n");
         return false;
       }
       ExitPreLoopAtSCEV = SE.getAddExpr(*SR.HighLimit, MinusOneS);
     }
 
-    if (!isSafeToExpandAt(ExitPreLoopAtSCEV, InsertPt, SE)) {
+    if (!isSafeToExpandAt(ExitPreLoopAtSCEV, InsertPt, SE) ||
+        !SE.isAvailableAtLoopEntry(ExitPreLoopAtSCEV, L)) {
       DEBUG(dbgs() << "irce: could not prove that it is safe to expand the"
                    << " preloop exit limit " << *ExitPreLoopAtSCEV
                    << " at block " << InsertPt->getParent()->getName() << "\n");
       return false;
     }
 
     ExitPreLoopAt = Expander.expandCodeFor(ExitPreLoopAtSCEV, IVTy, InsertPt);
     ExitPreLoopAt->setName("exit.preloop.at");
else {
         DEBUG(dbgs() << "irce: could not prove no-overflow when computing "
                      << "mainloop exit limit.  LowLimit = " << *(*SR.LowLimit)
                      << "\n");
         return false;
       }
       ExitMainLoopAtSCEV = SE.getAddExpr(*SR.LowLimit, MinusOneS);
     }
 
-    if (!isSafeToExpandAt(ExitMainLoopAtSCEV, InsertPt, SE)) {
+    if (!isSafeToExpandAt(ExitMainLoopAtSCEV, InsertPt, SE) ||
+        !SE.isAvailableAtLoopEntry(ExitMainLoopAtSCEV, L)) {
       DEBUG(dbgs() << "irce: could not prove that it is safe to expand the"
                    << " main loop exit limit " << *ExitMainLoopAtSCEV
                    << " at block " << InsertPt->getParent()->getName() << "\n");
       return false;
     }
 
     ExitMainLoopAt = Expander.expandCodeFor(ExitMainLoopAtSCEV, IVTy, InsertPt);
     ExitMainLoopAt->setName("exit.mainloop.at");

test/Transforms/IRCE/bad_expander.ll

 ; RUN: opt -verify-loop-info -irce-print-changed-loops -irce -S < %s 2>&1 | FileCheck %s
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128-ni:1"
 target triple = "x86_64-unknown-linux-gnu"
 
 ; IRCE should fail here because the preheader's exiting value is a phi from the
 ; loop, and this value cannot be expanded at loop's preheader.
 
 ; CHECK-NOT:   irce: in function test_01: constrained Loop
 ; CHECK-NOT:   irce: in function test_02: constrained Loop
 ; CHECK-LABEL: irce: in function test_03: constrained Loop
+; CHECK-NOT:   irce: in function test_04: constrained Loop
+; CHECK-NOT:   irce: in function test_05: constrained Loop
 
 define void @test_01() {
 
 ; CHECK-NOT:   irce: in function test_01: constrained Loop
 
 ; CHECK-LABEL: test_01
 ; CHECK-NOT:   preloop
 ; CHECK-NOT:   postloop

 
 guarded:
   %gep = getelementptr i64, i64* %p1, i64 %iv.next
   %loaded = load i64, i64* %gep, align 4
   %tmp7 = icmp slt i64 %iv.next, 1000
   br i1 %tmp7, label %loop, label %exit
 }
 
+define void @test_04(i64* %p1, i64* %p2, i1 %maybe_exit) {
+
+; CHECK-LABEL: test_04
+; CHECK-NOT:   preloop
+; CHECK-NOT:   postloop
+; CHECK-NOT:   br i1 false
+; CHECK-NOT:   br i1 true
+
+entry:
+  %num = load i64, i64* %p1, align 4, !range !2
+  %denom = load i64, i64* %p2, align 4, !range !2
+  br label %loop
+
+exit:                                       ; preds = %guarded, %loop
+  ret void
+
+loop:                                      ; preds = %guarded, %entry
+  %iv = phi i64 [ 0, %entry ], [ %iv.next, %guarded ]
+  %iv.next = add nuw nsw i64 %iv, 1
+  br i1 %maybe_exit, label %range_check, label %exit
+
+range_check:
+  %rem_result = srem i64 %num, %denom
+  %rc = icmp slt i64 %iv.next, %rem_result
+  br i1 %rc, label %guarded, label %exit
+
+guarded:
+  %gep = getelementptr i64, i64* %p1, i64 %iv.next
+  %loaded = load i64, i64* %gep, align 4
+  %tmp7 = icmp slt i64 %iv.next, 1000
+  br i1 %tmp7, label %loop, label %exit
+}
+
+define void @test_05(i64* %p1, i1 %maybe_exit) {
+
+; CHECK-LABEL: test_05
+; CHECK-NOT:   preloop
+; CHECK-NOT:   postloop
+; CHECK-NOT:   br i1 false
+; CHECK-NOT:   br i1 true
+
+entry:
+  br label %loop
+
+exit:                                       ; preds = %guarded, %loop
+  ret void
+
+loop:                                      ; preds = %guarded, %entry
+  %iv = phi i64 [ 0, %entry ], [ %iv.next, %guarded ]
+  %iv.next = add nuw nsw i64 %iv, 1
+  br i1 %maybe_exit, label %range_check, label %exit
+
+range_check:
+  %load_result = load i64, i64* %p1, align 4, !range !1
+  %rc = icmp slt i64 %iv.next, %load_result
+  br i1 %rc, label %guarded, label %exit
+
+guarded:
+  %gep = getelementptr i64, i64* %p1, i64 %iv.next
+  %loaded = load i64, i64* %gep, align 4
+  %tmp7 = icmp slt i64 %iv.next, 1000
+  br i1 %tmp7, label %loop, label %exit
+}
+
 !0 = !{i64 0, i64 100}
 !1 = !{i64 1, i64 100}
+!2 = !{i64 -100, i64 100}