[IRCE] Do not process empty safe ranges

[mkazantsev]

Summary

IRCE should not apply when the safe iteration range is proved to be empty.
In this case we do unneeded job creating pre/post loops and then never
go to the main loop.

This patch makes IRCE not apply to empty safe ranges, adds test for this
situation and also modifies one of existing tests where it used to happen
slightly.

[anna]

LGTM!

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

public:
   public:
     Range(const SCEV *Begin, const SCEV *End) : Begin(Begin), End(End) {
       assert(Begin->getType() == End->getType() && "ill-typed range!");
     }
 
     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
   /// branch to take the hot successor (see (1) above).
   bool getPassingDirection() { return true; }
 
   /// Computes a range for the induction variable (IndVar) in which the range
   /// check is redundant and can be constant-folded away.  The induction
InductiveRangeCheck::computeSafeIterationSpace(
   const SCEV *End = SE.getMinusSCEV(UpperLimit, M);
   return InductiveRangeCheck::Range(Begin, End);
 }
 
 static Optional<InductiveRangeCheck::Range>
 IntersectRange(ScalarEvolution &SE,
                const Optional<InductiveRangeCheck::Range> &R1,
                const InductiveRangeCheck::Range &R2) {
-  if (!R1.hasValue())
+  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
   // bail out to keep things simple.
   if (R1Value.getType() != R2.getType())
     return None;
 
   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) {
   if (skipLoop(L))
     return false;
 
   if (L->getBlocks().size() >= LoopSizeCutoff) {
     DEBUG(dbgs() << "irce: giving up constraining loop, too large\n";);
bool InductiveRangeCheckElimination::runOnLoop(Loop *L, LPPassManager &LPM) {
 
   IRBuilder<> B(ExprInsertPt);
   for (InductiveRangeCheck &IRC : RangeChecks) {
     auto Result = IRC.computeSafeIterationSpace(SE, IndVar);
     if (Result.hasValue()) {
       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();
       }
     }
   }
 
   if (!SafeIterRange.hasValue())
     return false;

test/Transforms/IRCE/correct-loop-info.ll

 ; CHECK:       outerheader:
 ; CHECK-NEXT:    [[TMP:%.*]] = icmp slt i32 undef, 84
 ; CHECK-NEXT:    br i1 [[TMP]], label [[BB2:%.*]], label [[BB16:%.*]]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    br i1 false, label [[INNERHEADER_PRELOOP_PREHEADER:%.*]], label [[PRELOOP_PSEUDO_EXIT:%.*]]
 ; 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:%.*]]
 ; CHECK:       innerheader:
 ; CHECK-NEXT:    [[TMP4:%.*]] = phi i32 [ [[TMP6:%.*]], [[BB8:%.*]] ], [ [[TMP4_PRELOOP_COPY:%.*]], [[INNERHEADER_PREHEADER]] ]
 ; CHECK-NEXT:    invoke void @pluto()
 ; 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]] ]
 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp slt i32 [[TMP6_LCSSA]], 84
 ; CHECK-NEXT:    br i1 [[TMP2]], label [[MAIN_PSEUDO_EXIT]], label [[BB13:%.*]]
 ; CHECK:       main.pseudo.exit:
 ; CHECK-NEXT:    [[TMP4_COPY:%.*]] = phi i32 [ [[TMP4_PRELOOP_COPY]], [[MAINLOOP:%.*]] ], [ [[TMP6_LCSSA]], [[MAIN_EXIT_SELECTOR]] ]
 ; CHECK-NEXT:    [[INDVAR_END1:%.*]] = phi i32 [ [[INDVAR_END]], [[MAINLOOP]] ], [ [[TMP6_LCSSA]], [[MAIN_EXIT_SELECTOR]] ]

 ; CHECK:       exit2:
 ; CHECK-NEXT:    ret void
 ; CHECK:       innerheader.preloop:
 ; CHECK-NEXT:    [[TMP4_PRELOOP:%.*]] = phi i32 [ [[TMP6_PRELOOP:%.*]], [[BB8_PRELOOP:%.*]] ], [ undef, [[INNERHEADER_PRELOOP_PREHEADER]] ]
 ; CHECK-NEXT:    invoke void @pluto()
 ; 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
 ; CHECK-NEXT:    [[TMP3:%.*]] = icmp slt i32 [[TMP6_PRELOOP]], -1
 ; CHECK-NEXT:    br i1 [[TMP3]], label [[INNERHEADER_PRELOOP]], label [[PRELOOP_EXIT_SELECTOR:%.*]], !llvm.loop !0, !irce.loop.clone !5
 ; CHECK:       preloop.exit.selector:
 ; CHECK-NEXT:    [[TMP6_PRELOOP_LCSSA:%.*]] = phi i32 [ [[TMP6_PRELOOP]], [[BB8_PRELOOP]] ]
 ; CHECK-NEXT:    [[TMP4:%.*]] = icmp slt i32 [[TMP6_PRELOOP_LCSSA]], 84
 ; CHECK-NEXT:    br i1 [[TMP4]], label [[PRELOOP_PSEUDO_EXIT]], label [[BB13]]
 ; CHECK:       preloop.pseudo.exit:
 ; CHECK-NEXT:    [[TMP4_PRELOOP_COPY]] = phi i32 [ undef, [[BB2]] ], [ [[TMP6_PRELOOP_LCSSA]], [[PRELOOP_EXIT_SELECTOR]] ]
 ; CHECK-NEXT:    [[INDVAR_END]] = phi i32 [ undef, [[BB2]] ], [ [[TMP6_PRELOOP_LCSSA]], [[PRELOOP_EXIT_SELECTOR]] ]
 ; CHECK-NEXT:    br label [[MAINLOOP]]
 ; CHECK:       postloop:
 ; CHECK-NEXT:    br label [[INNERHEADER_POSTLOOP:%.*]]
 ; CHECK:       innerheader.postloop:
 ; CHECK-NEXT:    [[TMP4_POSTLOOP:%.*]] = phi i32 [ [[TMP6_POSTLOOP:%.*]], [[BB8_POSTLOOP:%.*]] ], [ [[TMP4_COPY]], [[POSTLOOP]] ]
 ; CHECK-NEXT:    invoke void @pluto()
 ; 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
 ; CHECK-NEXT:    br i1 [[TMP9_POSTLOOP]], label [[INNERHEADER_POSTLOOP]], label [[BB13_LOOPEXIT:%.*]], !llvm.loop !6, !irce.loop.clone !5
 ;
 bb:
   br label %outerheader
 
 outerheader:                                              ; preds = %bb14, %bb
   %tmp = icmp slt i32 undef, 84
   br i1 %tmp, label %bb2, label %bb16
 
 bb2:                                              ; preds = %outerheader
   br label %innerheader
 
 innerheader:                                              ; preds = %bb8, %bb2
   %tmp4 = phi i32 [ %tmp6, %bb8 ], [ undef, %bb2 ]
   invoke void @pluto()
   to label %bb5 unwind label %outer_exiting
 
 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
   %tmp9 = icmp slt i32 %tmp6, 84
   br i1 %tmp9, label %innerheader, label %bb13
 
 outer_exiting:                                             ; preds = %innerheader
   %tmp11 = landingpad { i8*, i32 }

test/Transforms/IRCE/single-access-no-preloop.ll

 
 ; CHECK: loop.postloop:
 ; CHECK: %idx.postloop = phi i32 [ %idx.next.postloop, %in.bounds.postloop ], [ %idx.copy, %postloop ]
 
 ; CHECK: in.bounds.postloop:
 ; 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}