Index: lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp =================================================================== --- lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp +++ lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp @@ -1481,6 +1481,13 @@ 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"); } @@ -1500,6 +1507,13 @@ 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"); } Index: test/Transforms/IRCE/bad_expander.ll =================================================================== --- /dev/null +++ test/Transforms/IRCE/bad_expander.ll @@ -0,0 +1,140 @@ +; 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}