Index: lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp =================================================================== --- lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp +++ lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp @@ -176,6 +176,7 @@ Type *getType() const { return Begin->getType(); } const SCEV *getBegin() const { return Begin; } const SCEV *getEnd() const { return End; } + bool isEmpty() const { return Begin == End; } }; /// This is the value the condition of the branch needs to evaluate to for the @@ -1654,8 +1655,11 @@ IntersectRange(ScalarEvolution &SE, const Optional &R1, const InductiveRangeCheck::Range &R2) { - if (!R1.hasValue()) - return R2; + if (!R1.hasValue()) { + if (!R2.isEmpty()) + return R2; + return None; + } auto &R1Value = R1.getValue(); // TODO: we could widen the smaller range and have this work; but for now we @@ -1666,7 +1670,11 @@ const SCEV *NewBegin = SE.getSMaxExpr(R1Value.getBegin(), R2.getBegin()); const SCEV *NewEnd = SE.getSMinExpr(R1Value.getEnd(), R2.getEnd()); - return InductiveRangeCheck::Range(NewBegin, NewEnd); + // If the resulting range is empty, just return None. + auto Ret = InductiveRangeCheck::Range(NewBegin, NewEnd); + if (Ret.isEmpty()) + return None; + return Ret; } bool InductiveRangeCheckElimination::runOnLoop(Loop *L, LPPassManager &LPM) { @@ -1735,6 +1743,8 @@ auto MaybeSafeIterRange = IntersectRange(SE, SafeIterRange, Result.getValue()); if (MaybeSafeIterRange.hasValue()) { + assert(!MaybeSafeIterRange.getValue().isEmpty() && + "We should never return empty ranges!"); RangeChecksToEliminate.push_back(IRC); SafeIterRange = MaybeSafeIterRange.getValue(); } Index: test/Transforms/IRCE/correct-loop-info.ll =================================================================== --- test/Transforms/IRCE/correct-loop-info.ll +++ test/Transforms/IRCE/correct-loop-info.ll @@ -21,7 +21,7 @@ ; CHECK: innerheader.preloop.preheader: ; CHECK-NEXT: br label [[INNERHEADER_PRELOOP:%.*]] ; CHECK: mainloop: -; CHECK-NEXT: [[TMP0:%.*]] = icmp slt i32 [[INDVAR_END:%.*]], -1 +; CHECK-NEXT: [[TMP0:%.*]] = icmp slt i32 [[INDVAR_END:%.*]], 0 ; CHECK-NEXT: br i1 [[TMP0]], label [[INNERHEADER_PREHEADER:%.*]], label [[MAIN_PSEUDO_EXIT:%.*]] ; CHECK: innerheader.preheader: ; CHECK-NEXT: br label [[INNERHEADER:%.*]] @@ -31,11 +31,11 @@ ; CHECK-NEXT: to label [[BB5:%.*]] unwind label %outer_exiting.loopexit.split-lp.loopexit.split-lp ; CHECK: bb5: ; CHECK-NEXT: [[TMP6]] = add i32 [[TMP4]], 1 -; CHECK-NEXT: [[TMP7:%.*]] = icmp ult i32 [[TMP6]], 0 +; CHECK-NEXT: [[TMP7:%.*]] = icmp ult i32 [[TMP6]], 1 ; CHECK-NEXT: br i1 true, label [[BB8]], label [[EXIT3_LOOPEXIT5:%.*]] ; CHECK: bb8: ; CHECK-NEXT: [[TMP9:%.*]] = icmp slt i32 [[TMP6]], 84 -; CHECK-NEXT: [[TMP1:%.*]] = icmp slt i32 [[TMP6]], -1 +; CHECK-NEXT: [[TMP1:%.*]] = icmp slt i32 [[TMP6]], 0 ; CHECK-NEXT: br i1 [[TMP1]], label [[INNERHEADER]], label [[MAIN_EXIT_SELECTOR:%.*]] ; CHECK: main.exit.selector: ; CHECK-NEXT: [[TMP6_LCSSA:%.*]] = phi i32 [ [[TMP6]], [[BB8]] ] @@ -90,7 +90,7 @@ ; CHECK-NEXT: to label [[BB5_PRELOOP:%.*]] unwind label [[OUTER_EXITING_LOOPEXIT:%.*]] ; CHECK: bb5.preloop: ; CHECK-NEXT: [[TMP6_PRELOOP]] = add i32 [[TMP4_PRELOOP]], 1 -; CHECK-NEXT: [[TMP7_PRELOOP:%.*]] = icmp ult i32 [[TMP6_PRELOOP]], 0 +; CHECK-NEXT: [[TMP7_PRELOOP:%.*]] = icmp ult i32 [[TMP6_PRELOOP]], 1 ; CHECK-NEXT: br i1 [[TMP7_PRELOOP]], label [[BB8_PRELOOP]], label [[EXIT3_LOOPEXIT:%.*]] ; CHECK: bb8.preloop: ; CHECK-NEXT: [[TMP9_PRELOOP:%.*]] = icmp slt i32 [[TMP6_PRELOOP]], 84 @@ -112,7 +112,7 @@ ; CHECK-NEXT: to label [[BB5_POSTLOOP:%.*]] unwind label %outer_exiting.loopexit.split-lp.loopexit ; CHECK: bb5.postloop: ; CHECK-NEXT: [[TMP6_POSTLOOP]] = add i32 [[TMP4_POSTLOOP]], 1 -; CHECK-NEXT: [[TMP7_POSTLOOP:%.*]] = icmp ult i32 [[TMP6_POSTLOOP]], 0 +; CHECK-NEXT: [[TMP7_POSTLOOP:%.*]] = icmp ult i32 [[TMP6_POSTLOOP]], 1 ; CHECK-NEXT: br i1 [[TMP7_POSTLOOP]], label [[BB8_POSTLOOP]], label [[EXIT3_LOOPEXIT4:%.*]] ; CHECK: bb8.postloop: ; CHECK-NEXT: [[TMP9_POSTLOOP:%.*]] = icmp slt i32 [[TMP6_POSTLOOP]], 84 @@ -135,7 +135,7 @@ bb5: ; preds = %innerheader %tmp6 = add i32 %tmp4, 1 - %tmp7 = icmp ult i32 %tmp6, 0 + %tmp7 = icmp ult i32 %tmp6, 1 br i1 %tmp7, label %bb8, label %exit3 bb8: ; preds = %bb5 Index: test/Transforms/IRCE/single-access-no-preloop.ll =================================================================== --- test/Transforms/IRCE/single-access-no-preloop.ll +++ test/Transforms/IRCE/single-access-no-preloop.ll @@ -113,5 +113,71 @@ ; CHECK: %next.postloop = icmp slt i32 %idx.next.postloop, %n ; CHECK: br i1 %next.postloop, label %loop.postloop, label %exit.loopexit +; Make sure that we do not do IRCE if we know that the safe iteration range of +; the main loop is empty. + +define void @single_access_empty_range(i32 *%arr, i32 *%a_len_ptr, i32 %n) { + entry: + %len = load i32, i32* %a_len_ptr, !range !0 + %first.itr.check = icmp sgt i32 %n, 0 + br i1 %first.itr.check, label %loop, label %exit + + loop: + %idx = phi i32 [ 0, %entry ] , [ %idx.next, %in.bounds ] + %idx.next = add i32 %idx, 1 + %abc = icmp slt i32 %idx, 0 + br i1 %abc, label %in.bounds, label %out.of.bounds, !prof !1 + + in.bounds: + %addr = getelementptr i32, i32* %arr, i32 %idx + store i32 0, i32* %addr + %next = icmp slt i32 %idx.next, %n + br i1 %next, label %loop, label %exit + + out.of.bounds: + ret void + + exit: + ret void +} + +; CHECK-LABEL: @single_access_empty_range( +; CHECK-NOT: br i1 false +; CHECK-NOT: preloop +; CHECK-NOT: postloop + +define void @single_access_empty_range_2(i32 *%arr, i32 *%a_len_ptr, i32 %n) { + entry: + %len = load i32, i32* %a_len_ptr, !range !0 + %first.itr.check = icmp sgt i32 %n, 0 + br i1 %first.itr.check, label %loop, label %exit + + loop: + %idx = phi i32 [ 0, %entry ] , [ %idx.next, %in.bounds2 ] + %idx.next = add i32 %idx, 1 + %abc = icmp slt i32 %idx, 60 + br i1 %abc, label %in.bounds1, label %out.of.bounds, !prof !1 + + in.bounds1: + %def = icmp slt i32 %idx, 0 + br i1 %def, label %in.bounds2, label %out.of.bounds, !prof !1 + +in.bounds2: + %addr = getelementptr i32, i32* %arr, i32 %idx + store i32 0, i32* %addr + %next = icmp slt i32 %idx.next, %n + br i1 %next, label %loop, label %exit + + out.of.bounds: + ret void + + exit: + ret void +} + +; CHECK-LABEL: @single_access_empty_range_2( +; CHECK-NOT: br i1 false +; CHECK-NOT: preloop + !0 = !{i32 0, i32 2147483647} !1 = !{!"branch_weights", i32 64, i32 4}