+ 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]->getZExtValue();
+ 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,
+ ICmpInst::Predicate predicate) {
+ 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) {
+ ConstantInt *ItCst =
+ ConstantInt::get(IdxExpr->getType(), 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::getICmp(predicate, Result, RHS);
+ if (!isa<ConstantInt>(Result)) break; // Couldn't decide for sure
+ if (cast<ConstantInt>(Result)->getZExtValue() == false) {
+#if 0
+ 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;