[SCEV] Compute max backedge count for loops with "shift ivs"

This teaches SCEV to compute //max// backedge taken counts for loops
like

    for (int i = k; i != 0; i >>>= 1)
      whatever();

SCEV yet cannot represent the exact backedge count for these loops, and
this patch does not change that.  This is really geared towards teaching
SCEV that loops like the above are *not* infinite.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@251558 91177308-0d34-0410-b5e6-96231b3b80d8

diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h
index 14091af7349899e905a80efe29a138213f823d3e..fa2a0555920ffa778aea5d1558e4715ed66307b8 100644 (file)
--- a/include/llvm/Analysis/ScalarEvolution.h
+++ b/include/llvm/Analysis/ScalarEvolution.h
@@ -482,6 +482,17 @@ namespace llvm {
                                                   const Loop *L,
                                                   ICmpInst::Predicate p);
 
+    /// Compute the exit limit of a loop that is controlled by a
+    /// "(IV >> 1) != 0" type comparison.  We cannot compute the exact trip
+    /// count in these cases (since SCEV has no way of expressing them), but we
+    /// can still sometimes compute an upper bound.
+    ///
+    /// Return an ExitLimit for a loop whose backedge is guarded by `LHS Pred
+    /// RHS`.
+    ExitLimit computeShiftCompareExitLimit(Value *LHS, Value *RHS,
+                                           const Loop *L,
+                                           ICmpInst::Predicate Pred);
+
     /// If the loop is known to execute a constant number of times (the
     /// condition evolves only from constants), try to evaluate a few iterations
     /// of the loop until we get the exit condition gets a value of ExitWhen

diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp
index 9df31ed9e3a45b0f93982f1dfbeaa325e991a25f..e0658c210506f42bad811b53a5c003d8c47046a5 100644 (file)
--- a/lib/Analysis/ScalarEvolution.cpp
+++ b/lib/Analysis/ScalarEvolution.cpp
@@ -83,6 +83,7 @@
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Metadata.h"
 #include "llvm/IR/Operator.h"
+#include "llvm/IR/PatternMatch.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
@@ -5398,6 +5399,11 @@ ScalarEvolution::computeExitLimitFromICmp(const Loop *L,
         return ItCnt;
     }
 
+  ExitLimit ShiftEL = computeShiftCompareExitLimit(
+      ExitCond->getOperand(0), ExitCond->getOperand(1), L, Cond);
+  if (ShiftEL.hasAnyInfo())
+    return ShiftEL;
+
   const SCEV *LHS = getSCEV(ExitCond->getOperand(0));
   const SCEV *RHS = getSCEV(ExitCond->getOperand(1));
 
@@ -5576,6 +5582,149 @@ ScalarEvolution::computeLoadConstantCompareExitLimit(
   return getCouldNotCompute();
 }
 
+ScalarEvolution::ExitLimit ScalarEvolution::computeShiftCompareExitLimit(
+    Value *LHS, Value *RHSV, const Loop *L, ICmpInst::Predicate Pred) {
+  ConstantInt *RHS = dyn_cast<ConstantInt>(RHSV);
+  if (!RHS)
+    return getCouldNotCompute();
+
+  const BasicBlock *Latch = L->getLoopLatch();
+  if (!Latch)
+    return getCouldNotCompute();
+
+  const BasicBlock *Predecessor = L->getLoopPredecessor();
+  if (!Predecessor)
+    return getCouldNotCompute();
+
+  // Return true if V is of the form "LHS `shift_op` <positive constant>".
+  // Return LHS in OutLHS and shift_opt in OutOpCode.
+  auto MatchPositiveShift =
+      [](Value *V, Value *&OutLHS, Instruction::BinaryOps &OutOpCode) {
+
+    using namespace PatternMatch;
+
+    ConstantInt *ShiftAmt;
+    if (match(V, m_LShr(m_Value(OutLHS), m_ConstantInt(ShiftAmt))))
+      OutOpCode = Instruction::LShr;
+    else if (match(V, m_AShr(m_Value(OutLHS), m_ConstantInt(ShiftAmt))))
+      OutOpCode = Instruction::AShr;
+    else if (match(V, m_Shl(m_Value(OutLHS), m_ConstantInt(ShiftAmt))))
+      OutOpCode = Instruction::Shl;
+    else
+      return false;
+
+    return ShiftAmt->getValue().isStrictlyPositive();
+  };
+
+  // Recognize a "shift recurrence" either of the form %iv or of %iv.shifted in
+  //
+  // loop:
+  //   %iv = phi i32 [ %iv.shifted, %loop ], [ %val, %preheader ]
+  //   %iv.shifted = lshr i32 %iv, <positive constant>
+  //
+  // Return true on a succesful match.  Return the corresponding PHI node (%iv
+  // above) in PNOut and the opcode of the shift operation in OpCodeOut.
+  auto MatchShiftRecurrence =
+      [&](Value *V, PHINode *&PNOut, Instruction::BinaryOps &OpCodeOut) {
+    Optional<Instruction::BinaryOps> PostShiftOpCode;
+
+    {
+      Instruction::BinaryOps OpC;
+      Value *V;
+
+      // If we encounter a shift instruction, "peel off" the shift operation,
+      // and remember that we did so.  Later when we inspect %iv's backedge
+      // value, we will make sure that the backedge value uses the same
+      // operation.
+      //
+      // Note: the peeled shift operation does not have to be the same
+      // instruction as the one feeding into the PHI's backedge value.  We only
+      // really care about it being the same *kind* of shift instruction --
+      // that's all that is required for our later inferences to hold.
+      if (MatchPositiveShift(LHS, V, OpC)) {
+        PostShiftOpCode = OpC;
+        LHS = V;
+      }
+    }
+
+    PNOut = dyn_cast<PHINode>(LHS);
+    if (!PNOut || PNOut->getParent() != L->getHeader())
+      return false;
+
+    Value *BEValue = PNOut->getIncomingValueForBlock(Latch);
+    Value *OpLHS;
+
+    return
+        // The backedge value for the PHI node must be a shift by a positive
+        // amount
+        MatchPositiveShift(BEValue, OpLHS, OpCodeOut) &&
+
+        // of the PHI node itself
+        OpLHS == PNOut &&
+
+        // and the kind of shift should be match the kind of shift we peeled
+        // off, if any.
+        (!PostShiftOpCode.hasValue() || *PostShiftOpCode == OpCodeOut);
+  };
+
+  PHINode *PN;
+  Instruction::BinaryOps OpCode;
+  if (!MatchShiftRecurrence(LHS, PN, OpCode))
+    return getCouldNotCompute();
+
+  const DataLayout &DL = getDataLayout();
+
+  // The key rationale for this optimization is that for some kinds of shift
+  // recurrences, the value of the recurrence "stabilizes" to either 0 or -1
+  // within a finite number of iterations.  If the condition guarding the
+  // backedge (in the sense that the backedge is taken if the condition is true)
+  // is false for the value the shift recurrence stabilizes to, then we know
+  // that the backedge is taken only a finite number of times.
+
+  ConstantInt *StableValue = nullptr;
+  switch (OpCode) {
+  default:
+    llvm_unreachable("Impossible case!");
+
+  case Instruction::AShr: {
+    // {K,ashr,<positive-constant>} stabilizes to signum(K) in at most
+    // bitwidth(K) iterations.
+    Value *FirstValue = PN->getIncomingValueForBlock(Predecessor);
+    bool KnownZero, KnownOne;
+    ComputeSignBit(FirstValue, KnownZero, KnownOne, DL, 0, nullptr,
+                   Predecessor->getTerminator(), &DT);
+    auto *Ty = cast<IntegerType>(RHS->getType());
+    if (KnownZero)
+      StableValue = ConstantInt::get(Ty, 0);
+    else if (KnownOne)
+      StableValue = ConstantInt::get(Ty, -1, true);
+    else
+      return getCouldNotCompute();
+
+    break;
+  }
+  case Instruction::LShr:
+  case Instruction::Shl:
+    // Both {K,lshr,<positive-constant>} and {K,shl,<positive-constant>}
+    // stabilize to 0 in at most bitwidth(K) iterations.
+    StableValue = ConstantInt::get(cast<IntegerType>(RHS->getType()), 0);
+    break;
+  }
+
+  auto *Result =
+      ConstantFoldCompareInstOperands(Pred, StableValue, RHS, DL, &TLI);
+  assert(Result->getType()->isIntegerTy(1) &&
+         "Otherwise cannot be an operand to a branch instruction");
+
+  if (Result->isZeroValue()) {
+    unsigned BitWidth = getTypeSizeInBits(RHS->getType());
+    const SCEV *UpperBound =
+        getConstant(getEffectiveSCEVType(RHS->getType()), BitWidth);
+    return ExitLimit(getCouldNotCompute(), UpperBound);
+  }
+
+  return getCouldNotCompute();
+}
 
 /// CanConstantFold - Return true if we can constant fold an instruction of the
 /// specified type, assuming that all operands were constants.

diff --git a/test/Analysis/ScalarEvolution/shift-op.ll b/test/Analysis/ScalarEvolution/shift-op.ll
new file mode 100644 (file)
index 0000000..fe832d5
--- /dev/null
+++ b/test/Analysis/ScalarEvolution/shift-op.ll
@@ -0,0 +1,164 @@
+; RUN: opt -analyze -scalar-evolution < %s | FileCheck %s
+
+define void @test0(i32 %init) {
+; CHECK-LABEL: Classifying expressions for: @test0
+; CHECK: Loop %loop: max backedge-taken count is 32
+ entry:
+  br label %loop
+
+ loop:
+  %iv = phi i32 [ %init, %entry ], [ %iv.shift, %loop ]
+  %iv.shift = lshr i32 %iv, 1
+  %exit.cond = icmp eq i32 %iv, 0
+  br i1 %exit.cond, label %leave, label %loop
+
+ leave:
+  ret void
+}
+
+define void @test1(i32 %init) {
+; CHECK-LABEL: Classifying expressions for: @test1
+; CHECK: Loop %loop: max backedge-taken count is 32
+ entry:
+  br label %loop
+
+ loop:
+  %iv = phi i32 [ %init, %entry ], [ %iv.shift, %loop ]
+  %iv.shift = shl i32 %iv, 1
+  %exit.cond = icmp eq i32 %iv, 0
+  br i1 %exit.cond, label %leave, label %loop
+
+ leave:
+  ret void
+}
+
+define void @test2(i32 %init) {
+; CHECK-LABEL: Determining loop execution counts for: @test2
+; CHECK: Loop %loop: Unpredictable max backedge-taken count.
+
+; Unpredictable because %iv could "stabilize" to either -1 or 0,
+; depending on %init.
+ entry:
+  br label %loop
+
+ loop:
+  %iv = phi i32 [ %init, %entry ], [ %iv.shift, %loop ]
+  %iv.shift = ashr i32 %iv, 1
+  %exit.cond = icmp eq i32 %iv, 0
+  br i1 %exit.cond, label %leave, label %loop
+
+ leave:
+  ret void
+}
+
+define void @test3(i32* %init.ptr) {
+; CHECK-LABEL: Determining loop execution counts for: @test3
+; CHECK: Loop %loop: max backedge-taken count is 32
+ entry:
+  %init = load i32, i32* %init.ptr, !range !0
+  br label %loop
+
+ loop:
+  %iv = phi i32 [ %init, %entry ], [ %iv.shift, %loop ]
+  %iv.shift = ashr i32 %iv, 1
+  %exit.cond = icmp eq i32 %iv, 0
+  br i1 %exit.cond, label %leave, label %loop
+
+ leave:
+  ret void
+}
+
+define void @test4(i32* %init.ptr) {
+; CHECK-LABEL: Classifying expressions for: @test4
+; CHECK-LABEL: Loop %loop: max backedge-taken count is 32
+ entry:
+  %init = load i32, i32* %init.ptr, !range !1
+  br label %loop
+
+ loop:
+  %iv = phi i32 [ %init, %entry ], [ %iv.shift, %loop ]
+  %iv.shift = ashr i32 %iv, 1
+  %exit.cond = icmp eq i32 %iv, -1
+  br i1 %exit.cond, label %leave, label %loop
+
+ leave:
+  ret void
+}
+
+define void @test5(i32* %init.ptr) {
+; CHECK-LABEL: Determining loop execution counts for: @test5
+; CHECK: Loop %loop: Unpredictable max backedge-taken count.
+
+; %iv will "stabilize" to -1, so this is an infinite loop
+ entry:
+  %init = load i32, i32* %init.ptr, !range !1
+  br label %loop
+
+ loop:
+  %iv = phi i32 [ %init, %entry ], [ %iv.shift, %loop ]
+  %iv.shift = ashr i32 %iv, 1
+  %exit.cond = icmp eq i32 %iv, 0
+  br i1 %exit.cond, label %leave, label %loop
+
+ leave:
+  ret void
+}
+
+define void @test6(i32 %init, i32 %shift.amt) {
+; CHECK-LABEL: Determining loop execution counts for: @test6
+; CHECK: Loop %loop: Unpredictable max backedge-taken count.
+
+; Potentially infinite loop, since %shift.amt could be 0
+ entry:
+  br label %loop
+
+ loop:
+  %iv = phi i32 [ %init, %entry ], [ %iv.shift, %loop ]
+  %iv.shift = lshr i32 %iv, %shift.amt
+  %exit.cond = icmp eq i32 %iv, 0
+  br i1 %exit.cond, label %leave, label %loop
+
+ leave:
+  ret void
+}
+
+define void @test7(i32 %init) {
+; CHECK-LABEL: Classifying expressions for: @test7
+; CHECK: Loop %loop: max backedge-taken count is 32
+
+ entry:
+  br label %loop
+
+ loop:
+  %iv = phi i32 [ %init, %entry ], [ %iv.shift, %loop ]
+  %iv.shift = lshr i32 %iv, 1
+  %exit.cond = icmp eq i32 %iv.shift, 0
+  br i1 %exit.cond, label %leave, label %loop
+
+ leave:
+  ret void
+}
+
+define void @test8(i32 %init) {
+; CHECK-LABEL: Classifying expressions for: @test8
+; CHECK: Loop %loop: Unpredictable max backedge-taken count.
+
+; In this test case, %iv.test stabilizes to 127, not -1, so the loop
+; is infinite.
+
+ entry:
+  br label %loop
+
+ loop:
+  %iv = phi i32 [ %init, %entry ], [ %iv.shift, %loop ]
+  %iv.shift = ashr i32 %iv, 1
+  %iv.test = lshr i32 %iv, 1
+  %exit.cond = icmp eq i32 %iv.test, -1
+  br i1 %exit.cond, label %leave, label %loop
+
+ leave:
+  ret void
+}
+
+!0 = !{i32 0, i32 50000}
+!1 = !{i32 -5000, i32 -1}