This nutty patch has been in my tree since before 1.3 went out, and it needs

to go in.  This patch allows us to compute the trip count of loops controlled
by values loaded from constant arrays.  The cannonnical example of this is
strlen when passed a constant argument:

for (int i = 0; "constantstring"[i]; ++i) ;
return i;

In this case, it will compute that the loop executes 14 times, which means
that the exit value of i is 14.  Because of this, the loop gets DCE'd and
we are happy.  This also applies to anything that does similar things, e.g.
loops like this:

  const float Array[] = { 0.1, 2.1, 3.2, 23.21 };
  for (int i = 0; Array[i] < 20; ++i)

and is actually fairly general.

The problem with this is that it almost never triggers.  The reason is that
we run indvars and the loop optimizer only at compile time, which is before
things like strlen and strcpy have been inlined into the program from libc.
Because of this, it almost never is used (it triggers twice in specint2k).

I'm committing it because it DOES work, may be useful in the future, and
doesn't slow us down at all.  If/when we start running the loop optimizer
at link-time (-O4?) this will be very nice indeed :)

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

diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp
index 31c85172f8a864d77086a152f95b5025e59a691b..fdfda32ee419a0c312d71f896fb81105e2909db8 100644 (file)
--- a/lib/Analysis/ScalarEvolution.cpp
+++ b/lib/Analysis/ScalarEvolution.cpp
@@ -62,9 +62,8 @@
 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
 #include "llvm/Constants.h"
 #include "llvm/DerivedTypes.h"
+#include "llvm/GlobalVariable.h"
 #include "llvm/Instructions.h"
-#include "llvm/Type.h"
-#include "llvm/Value.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Assembly/Writer.h"
 #include "llvm/Transforms/Scalar.h"
@@ -84,7 +83,11 @@ namespace {
 
   Statistic<>
   NumBruteForceEvaluations("scalar-evolution",
-                           "Number of brute force evaluations needed to calculate high-order polynomial exit values");
+                           "Number of brute force evaluations needed to "
+                           "calculate high-order polynomial exit values");
+  Statistic<>
+  NumArrayLenItCounts("scalar-evolution",
+                      "Number of trip counts computed with array length");
   Statistic<>
   NumTripCountsComputed("scalar-evolution",
                         "Number of loops with predictable loop counts");
@@ -1090,6 +1093,13 @@ namespace {
     /// will iterate.
     SCEVHandle ComputeIterationCount(const Loop *L);
 
+    /// ComputeLoadConstantCompareIterationCount - Given an exit condition of
+    /// 'setcc load X, cst', try to se if we can compute the trip count.
+    SCEVHandle ComputeLoadConstantCompareIterationCount(LoadInst *LI,
+                                                        Constant *RHS,
+                                                        const Loop *L,
+                                                        unsigned SetCCOpcode);
+
     /// ComputeIterationCountExhaustively - If the trip 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
@@ -1387,6 +1397,21 @@ SCEVHandle ScalarEvolutionsImpl::ComputeIterationCount(const Loop *L) {
     return ComputeIterationCountExhaustively(L, ExitBr->getCondition(),
                                           ExitBr->getSuccessor(0) == ExitBlock);
 
+  // If the condition was exit on true, convert the condition to exit on false.
+  Instruction::BinaryOps Cond;
+  if (ExitBr->getSuccessor(1) == ExitBlock)
+    Cond = ExitCond->getOpcode();
+  else
+    Cond = ExitCond->getInverseCondition();
+
+  // Handle common loops like: for (X = "string"; *X; ++X)
+  if (LoadInst *LI = dyn_cast<LoadInst>(ExitCond->getOperand(0)))
+    if (Constant *RHS = dyn_cast<Constant>(ExitCond->getOperand(1))) {
+      SCEVHandle ItCnt =
+        ComputeLoadConstantCompareIterationCount(LI, RHS, L, Cond);
+      if (!isa<SCEVCouldNotCompute>(ItCnt)) return ItCnt;
+    }
+
   SCEVHandle LHS = getSCEV(ExitCond->getOperand(0));
   SCEVHandle RHS = getSCEV(ExitCond->getOperand(1));
 
@@ -1396,13 +1421,6 @@ SCEVHandle ScalarEvolutionsImpl::ComputeIterationCount(const Loop *L) {
   Tmp = getSCEVAtScope(RHS, L);
   if (!isa<SCEVCouldNotCompute>(Tmp)) RHS = Tmp;
 
-  // If the condition was exit on true, convert the condition to exit on false.
-  Instruction::BinaryOps Cond;
-  if (ExitBr->getSuccessor(1) == ExitBlock)
-    Cond = ExitCond->getOpcode();
-  else
-    Cond = ExitCond->getInverseCondition();
-
   // At this point, we would like to compute how many iterations of the loop the
   // predicate will return true for these inputs.
   if (isa<SCEVConstant>(LHS) && !isa<SCEVConstant>(RHS)) {
@@ -1473,6 +1491,125 @@ SCEVHandle ScalarEvolutionsImpl::ComputeIterationCount(const Loop *L) {
                                          ExitBr->getSuccessor(0) == ExitBlock);
 }
 
+static ConstantInt *
+EvaluateConstantChrecAtConstant(const SCEVAddRecExpr *AddRec, Constant *C) {
+  SCEVHandle InVal = SCEVConstant::get(cast<ConstantInt>(C));
+  SCEVHandle Val = AddRec->evaluateAtIteration(InVal);
+  assert(isa<SCEVConstant>(Val) &&
+         "Evaluation of SCEV at constant didn't fold correctly?");
+  return cast<SCEVConstant>(Val)->getValue();
+}
+
+/// GetAddressedElementFromGlobal - Given a global variable with an initializer
+/// and a GEP expression (missing the pointer index) indexing into it, return
+/// the addressed element of the initializer or null if the index expression is
+/// invalid.
+static Constant *
+GetAddressedElementFromGlobal(GlobalVariable *GV, 
+                              const std::vector<ConstantInt*> &Indices) {
+  Constant *Init = GV->getInitializer();
+  for (unsigned i = 0, e = Indices.size(); i != e; ++i) {
+    uint64_t Idx = Indices[i]->getRawValue();
+    if (ConstantStruct *CS = dyn_cast<ConstantStruct>(Init)) {
+      assert(Idx < CS->getNumOperands() && "Bad struct index!");
+      Init = cast<Constant>(CS->getOperand(Idx));
+    } else if (ConstantArray *CA = dyn_cast<ConstantArray>(Init)) {
+      if (Idx >= CA->getNumOperands()) return 0;  // Bogus program
+      Init = cast<Constant>(CA->getOperand(Idx));
+    } else if (isa<ConstantAggregateZero>(Init)) {
+      if (const StructType *STy = dyn_cast<StructType>(Init->getType())) {
+        assert(Idx < STy->getNumElements() && "Bad struct index!");
+        Init = Constant::getNullValue(STy->getElementType(Idx));
+      } else if (const ArrayType *ATy = dyn_cast<ArrayType>(Init->getType())) {
+        if (Idx >= ATy->getNumElements()) return 0;  // Bogus program
+        Init = Constant::getNullValue(ATy->getElementType());
+      } else {
+        assert(0 && "Unknown constant aggregate type!");
+      }
+      return 0;
+    } else {
+      return 0; // Unknown initializer type
+    }
+  }
+  return Init;
+}
+
+/// ComputeLoadConstantCompareIterationCount - Given an exit condition of
+/// 'setcc load X, cst', try to se if we can compute the trip count.
+SCEVHandle ScalarEvolutionsImpl::
+ComputeLoadConstantCompareIterationCount(LoadInst *LI, Constant *RHS, 
+                                         const Loop *L, unsigned SetCCOpcode) {
+  if (LI->isVolatile()) return UnknownValue;
+
+  // Check to see if the loaded pointer is a getelementptr of a global.
+  GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(LI->getOperand(0));
+  if (!GEP) return UnknownValue;
+
+  // Make sure that it is really a constant global we are gepping, with an
+  // initializer, and make sure the first IDX is really 0.
+  GlobalVariable *GV = dyn_cast<GlobalVariable>(GEP->getOperand(0));
+  if (!GV || !GV->isConstant() || !GV->hasInitializer() ||
+      GEP->getNumOperands() < 3 || !isa<Constant>(GEP->getOperand(1)) ||
+      !cast<Constant>(GEP->getOperand(1))->isNullValue())
+    return UnknownValue;
+
+  // Okay, we allow one non-constant index into the GEP instruction.
+  Value *VarIdx = 0;
+  std::vector<ConstantInt*> Indexes;
+  unsigned VarIdxNum = 0;
+  for (unsigned i = 2, e = GEP->getNumOperands(); i != e; ++i)
+    if (ConstantInt *CI = dyn_cast<ConstantInt>(GEP->getOperand(i))) {
+      Indexes.push_back(CI);
+    } else if (!isa<ConstantInt>(GEP->getOperand(i))) {
+      if (VarIdx) return UnknownValue;  // Multiple non-constant idx's.
+      VarIdx = GEP->getOperand(i);
+      VarIdxNum = i-2;
+      Indexes.push_back(0);
+    }
+
+  // Okay, we know we have a (load (gep GV, 0, X)) comparison with a constant.
+  // Check to see if X is a loop variant variable value now.
+  SCEVHandle Idx = getSCEV(VarIdx);
+  SCEVHandle Tmp = getSCEVAtScope(Idx, L);
+  if (!isa<SCEVCouldNotCompute>(Tmp)) Idx = Tmp;
+
+  // We can only recognize very limited forms of loop index expressions, in
+  // particular, only affine AddRec's like {C1,+,C2}.
+  SCEVAddRecExpr *IdxExpr = dyn_cast<SCEVAddRecExpr>(Idx);
+  if (!IdxExpr || !IdxExpr->isAffine() || IdxExpr->isLoopInvariant(L) ||
+      !isa<SCEVConstant>(IdxExpr->getOperand(0)) ||
+      !isa<SCEVConstant>(IdxExpr->getOperand(1)))
+    return UnknownValue;
+
+  unsigned MaxSteps = MaxBruteForceIterations;
+  for (unsigned IterationNum = 0; IterationNum != MaxSteps; ++IterationNum) {
+    ConstantUInt *ItCst =
+      ConstantUInt::get(IdxExpr->getType()->getUnsignedVersion(), IterationNum);
+    ConstantInt *Val = EvaluateConstantChrecAtConstant(IdxExpr, ItCst);
+
+    // Form the GEP offset.
+    Indexes[VarIdxNum] = Val;
+
+    Constant *Result = GetAddressedElementFromGlobal(GV, Indexes);
+    if (Result == 0) break;  // Cannot compute!
+
+    // Evaluate the condition for this iteration.
+    Result = ConstantExpr::get(SetCCOpcode, Result, RHS);
+    if (!isa<ConstantBool>(Result)) break;  // Couldn't decide for sure
+    if (Result == ConstantBool::False) {
+#if 0
+      std::cerr << "\n***\n*** Computed loop count " << *ItCst
+                << "\n*** From global " << *GV << "*** BB: " << *L->getHeader()
+                << "***\n";
+#endif
+      ++NumArrayLenItCounts;
+      return SCEVConstant::get(ItCst);   // Found terminating iteration!
+    }
+  }
+  return UnknownValue;
+}
+
+
 /// CanConstantFold - Return true if we can constant fold an instruction of the
 /// specified type, assuming that all operands were constants.
 static bool CanConstantFold(const Instruction *I) {
@@ -1978,16 +2115,6 @@ SCEVHandle ScalarEvolutionsImpl::HowFarToNonZero(SCEV *V, const Loop *L) {
   return UnknownValue;
 }
 
-static ConstantInt *
-EvaluateConstantChrecAtConstant(const SCEVAddRecExpr *AddRec, Constant *C) {
-  SCEVHandle InVal = SCEVConstant::get(cast<ConstantInt>(C));
-  SCEVHandle Val = AddRec->evaluateAtIteration(InVal);
-  assert(isa<SCEVConstant>(Val) &&
-         "Evaluation of SCEV at constant didn't fold correctly?");
-  return cast<SCEVConstant>(Val)->getValue();
-}
-
-
 /// getNumIterationsInRange - Return the number of iterations of this loop that
 /// produce values in the specified constant range.  Another way of looking at
 /// this is that it returns the first iteration number where the value is not in