[IRCE] Fix SCEVExpander's usage in IRCE

[mkazantsev]

Summary

When expanding exit conditions for pre- and postloops, we may end up expanding a
recurrency from the loop to in its loop's preheader. This produces incorrect IR.

This patch ensures that IRCE uses SCEVExpander correctly and only expands code which
is safe to expand in this particular location.

[mkazantsev]

Planning to add some more tests.

[mkazantsev]

Fixed typos in debug output message, added more tests for division.

[mkazantsev]

Ping

[reames]

LGTM once dependent changes land.

[mkazantsev]

Merged as https://reviews.llvm.org/rL318381

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

else {
         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)) {
+      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");
   }
 
   if (NeedsPostLoop) {
     const SCEV *ExitMainLoopAtSCEV = nullptr;
 
     if (Increasing)
       ExitMainLoopAtSCEV = *SR.HighLimit;
     else {
       if (CanBeMin(SE, *SR.LowLimit, IsSignedPredicate)) {
         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)) {
+      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");
   }
 
   // We clone these ahead of time so that we don't have to deal with changing
   // and temporarily invalid IR as we transform the loops.
   if (NeedsPreLoop)
     cloneLoop(PreLoop, "preloop");

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
+
+define void @test_01() {
+
+; CHECK-NOT:   irce: in function test_01: constrained Loop
+
+; CHECK-LABEL: test_01
+; 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 [ 380, %entry ], [ %limit, %guarded ]
+  %bad_phi = phi i32 [ 3, %entry ], [ %bad_phi.next, %guarded ]
+  %bad_phi.next = add nuw nsw i32 %bad_phi, 1
+  %iv.next = add nuw nsw i64 %iv, 1
+  %rc = icmp slt i64 %iv.next, 5
+  br i1 %rc, label %guarded, label %exit
+
+guarded:
+  %limit = add nsw i64 %iv, -1
+  %tmp5 = add nuw nsw i32 %bad_phi, 8
+  %tmp6 = zext i32 %tmp5 to i64
+  %tmp7 = icmp eq i64 %limit, %tmp6
+  br i1 %tmp7, label %exit, label %loop
+}
+
+; This test should fail because we are unable to prove that the division is
+; safe to expand it to preheader: if we exit by maybe_exit condition, it is
+; unsafe to execute it there.
+
+define void @test_02(i64* %p1, i64* %p2, i1 %maybe_exit) {
+
+; CHECK-LABEL: test_02
+; 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 !0
+  %denom = load i64, i64* %p2, align 4, !range !0
+  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:
+  %div_result = udiv i64 %num, %denom
+  %rc = icmp slt i64 %iv.next, %div_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_03(i64* %p1, i64* %p2, i1 %maybe_exit) {
+
+; Show that IRCE would hit test_02 if the division was safe (denom not zero).
+
+; CHECK-LABEL: test_03
+; CHECK:       entry:
+; CHECK-NEXT:    %num = load i64, i64* %p1, align 4
+; CHECK-NEXT:    %denom = load i64, i64* %p2, align 4
+; CHECK-NEXT:    [[DIV:%[^ ]+]] = udiv i64 %num, %denom
+; CHECK-NEXT:    [[DIV_MINUS_1:%[^ ]+]] = add i64 [[DIV]], -1
+; CHECK-NEXT:    [[COMP1:%[^ ]+]] = icmp sgt i64 [[DIV_MINUS_1]], 0
+; CHECK-NEXT:    %exit.mainloop.at = select i1 [[COMP1]], i64 [[DIV_MINUS_1]], i64 0
+; CHECK-NEXT:    [[COMP2:%[^ ]+]] = icmp slt i64 0, %exit.mainloop.at
+; CHECK-NEXT:    br i1 [[COMP2]], label %loop.preheader, label %main.pseudo.exit
+; CHECK-NOT:     preloop
+; CHECK:       loop:
+; CHECK-NEXT:    %iv = phi i64 [ %iv.next, %guarded ], [ 0, %loop.preheader ]
+; CHECK-NEXT:    %iv.next = add nuw nsw i64 %iv, 1
+; CHECK-NEXT:    br i1 %maybe_exit, label %range_check, label %exit.loopexit1
+; CHECK:       range_check:
+; CHECK-NEXT:    %div_result = udiv i64 %num, %denom
+; CHECK-NEXT:    %rc = icmp slt i64 %iv.next, %div_result
+; CHECK-NEXT:    br i1 true, label %guarded, label %exit.loopexit1
+; CHECK:       guarded:
+; CHECK-NEXT:    %gep = getelementptr i64, i64* %p1, i64 %iv.next
+; CHECK-NEXT:    %loaded = load i64, i64* %gep, align 4
+; CHECK-NEXT:    %tmp7 = icmp slt i64 %iv.next, 1000
+; CHECK-NEXT:    [[EXIT_MAIN_LOOP:%[^ ]+]] = icmp slt i64 %iv.next, %exit.mainloop.at
+; CHECK-NEXT:    br i1 [[EXIT_MAIN_LOOP]], label %loop, label %main.exit.selector
+; CHECK:       postloop
+
+entry:
+  %num = load i64, i64* %p1, align 4, !range !0
+  %denom = load i64, i64* %p2, align 4, !range !1
+  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:
+  %div_result = udiv i64 %num, %denom
+  %rc = icmp slt i64 %iv.next, %div_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}