From 541d77cf0d2bd08fbc51ca6221f8833e44dae99c Mon Sep 17 00:00:00 2001
From: Sanjoy Das <sanjoy@playingwithpointers.com>
Date: Tue, 7 Feb 2017 23:59:07 +0000
Subject: [PATCH] [IRCE] Add a missing invariant check

Currently IRCE relies on the loops it transforms to be (semantically) of
the form:

  for (i = START; i < END; i++)
    ...

or

  for (i = START; i > END; i--)
    ...

However, we were not verifying the presence of the START < END entry
check (i.e. check before the first iteration).  We were only verifying
that the backedge was guarded by (i + 1) < END.

Usually this would work "fine" since (especially in Java) most loops do
actually have the START < END check, but of course that is not
guaranteed.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@294375 91177308-0d34-0410-b5e6-96231b3b80d8
---
 .../Scalar/InductiveRangeCheckElimination.cpp | 44 +++++++++++++++---
 test/Transforms/IRCE/bad-loop-structure.ll    | 45 +++++++++++++++++++
 2 files changed, 84 insertions(+), 5 deletions(-)
 create mode 100644 test/Transforms/IRCE/bad-loop-structure.ll

diff --git a/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp b/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp
index 8e81541c233..85db6e5e110 100644
--- a/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp
+++ b/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp
@@ -446,6 +446,15 @@ struct LoopStructure {
   BasicBlock *LatchExit;
   unsigned LatchBrExitIdx;
 
+  // The loop represented by this instance of LoopStructure is semantically
+  // equivalent to:
+  //
+  // intN_ty inc = IndVarIncreasing ? 1 : -1;
+  // pred_ty predicate = IndVarIncreasing ? ICMP_SLT : ICMP_SGT;
+  //
+  // for (intN_ty iv = IndVarStart; predicate(iv, LoopExitAt); iv = IndVarNext)
+  //   ... body ...
+
   Value *IndVarNext;
   Value *IndVarStart;
   Value *LoopExitAt;
@@ -789,6 +798,10 @@ LoopStructure::parseLoopStructure(ScalarEvolution &SE, BranchProbabilityInfo &BP
     return None;
   }
 
+  const SCEV *StartNext = IndVarNext->getStart();
+  const SCEV *Addend = SE.getNegativeSCEV(IndVarNext->getStepRecurrence(SE));
+  const SCEV *IndVarStart = SE.getAddExpr(StartNext, Addend);
+
   ConstantInt *One = ConstantInt::get(IndVarTy, 1);
   // TODO: generalize the predicates here to also match their unsigned variants.
   if (IsIncreasing) {
@@ -809,10 +822,22 @@ LoopStructure::parseLoopStructure(ScalarEvolution &SE, BranchProbabilityInfo &BP
         return None;
       }
 
+      if (!SE.isLoopEntryGuardedByCond(
+              &L, CmpInst::ICMP_SLT, IndVarStart,
+              SE.getAddExpr(RightSCEV, SE.getOne(RightSCEV->getType())))) {
+        FailureReason = "Induction variable start not bounded by upper limit";
+        return None;
+      }
+
       IRBuilder<> B(Preheader->getTerminator());
       RightValue = B.CreateAdd(RightValue, One);
+    } else {
+      if (!SE.isLoopEntryGuardedByCond(&L, CmpInst::ICMP_SLT, IndVarStart,
+                                       RightSCEV)) {
+        FailureReason = "Induction variable start not bounded by upper limit";
+        return None;
+      }
     }
-
   } else {
     bool FoundExpectedPred =
         (Pred == ICmpInst::ICMP_SGT && LatchBrExitIdx == 1) ||
@@ -831,15 +856,24 @@ LoopStructure::parseLoopStructure(ScalarEvolution &SE, BranchProbabilityInfo &BP
         return None;
       }
 
+      if (!SE.isLoopEntryGuardedByCond(
+              &L, CmpInst::ICMP_SGT, IndVarStart,
+              SE.getMinusSCEV(RightSCEV, SE.getOne(RightSCEV->getType())))) {
+        FailureReason = "Induction variable start not bounded by lower limit";
+        return None;
+      }
+
       IRBuilder<> B(Preheader->getTerminator());
       RightValue = B.CreateSub(RightValue, One);
+    } else {
+      if (!SE.isLoopEntryGuardedByCond(&L, CmpInst::ICMP_SGT, IndVarStart,
+                                       RightSCEV)) {
+        FailureReason = "Induction variable start not bounded by lower limit";
+        return None;
+      }
     }
   }
 
-  const SCEV *StartNext = IndVarNext->getStart();
-  const SCEV *Addend = SE.getNegativeSCEV(IndVarNext->getStepRecurrence(SE));
-  const SCEV *IndVarStart = SE.getAddExpr(StartNext, Addend);
-
   BasicBlock *LatchExit = LatchBr->getSuccessor(LatchBrExitIdx);
 
   assert(SE.getLoopDisposition(LatchCount, &L) ==
diff --git a/test/Transforms/IRCE/bad-loop-structure.ll b/test/Transforms/IRCE/bad-loop-structure.ll
new file mode 100644
index 00000000000..9c2e4251423
--- /dev/null
+++ b/test/Transforms/IRCE/bad-loop-structure.ll
@@ -0,0 +1,45 @@
+; RUN: opt -S -irce -irce-print-changed-loops=true < %s | FileCheck %s
+
+; CHECK-NOT: irce
+
+define void @bad_loop_structure_increasing(i64 %iv.start) {
+entry:
+  br label %for.body
+
+for.body:
+  %indvars.iv = phi i64 [ %iv.start, %entry ], [ %indvars.iv.next, %for.inc ]
+  %cmp = icmp ult i64 %indvars.iv, 100
+  br i1 %cmp, label %switch.lookup, label %for.inc
+
+switch.lookup:
+  br label %for.inc
+
+for.inc:
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %cmp55 = icmp slt i64 %indvars.iv.next, 11
+  br i1 %cmp55, label %for.body, label %for.end
+
+for.end:
+  ret void
+}
+
+define void @bad_loop_structure_decreasing(i64 %iv.start) {
+entry:
+  br label %for.body
+
+for.body:
+  %indvars.iv = phi i64 [ %iv.start, %entry ], [ %indvars.iv.next, %for.inc ]
+  %cmp = icmp ult i64 %indvars.iv, 100
+  br i1 %cmp, label %switch.lookup, label %for.inc
+
+switch.lookup:
+  br label %for.inc
+
+for.inc:
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, -1
+  %cmp55 = icmp sgt i64 %indvars.iv.next, 11
+  br i1 %cmp55, label %for.body, label %for.end
+
+for.end:
+  ret void
+}
-- 
2.50.1