LLVM API Documentation
00001 //===- ScalarEvolution.cpp - Scalar Evolution Analysis ----------*- C++ -*-===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file contains the implementation of the scalar evolution analysis 00011 // engine, which is used primarily to analyze expressions involving induction 00012 // variables in loops. 00013 // 00014 // There are several aspects to this library. First is the representation of 00015 // scalar expressions, which are represented as subclasses of the SCEV class. 00016 // These classes are used to represent certain types of subexpressions that we 00017 // can handle. We only create one SCEV of a particular shape, so 00018 // pointer-comparisons for equality are legal. 00019 // 00020 // One important aspect of the SCEV objects is that they are never cyclic, even 00021 // if there is a cycle in the dataflow for an expression (ie, a PHI node). If 00022 // the PHI node is one of the idioms that we can represent (e.g., a polynomial 00023 // recurrence) then we represent it directly as a recurrence node, otherwise we 00024 // represent it as a SCEVUnknown node. 00025 // 00026 // In addition to being able to represent expressions of various types, we also 00027 // have folders that are used to build the *canonical* representation for a 00028 // particular expression. These folders are capable of using a variety of 00029 // rewrite rules to simplify the expressions. 00030 // 00031 // Once the folders are defined, we can implement the more interesting 00032 // higher-level code, such as the code that recognizes PHI nodes of various 00033 // types, computes the execution count of a loop, etc. 00034 // 00035 // TODO: We should use these routines and value representations to implement 00036 // dependence analysis! 00037 // 00038 //===----------------------------------------------------------------------===// 00039 // 00040 // There are several good references for the techniques used in this analysis. 00041 // 00042 // Chains of recurrences -- a method to expedite the evaluation 00043 // of closed-form functions 00044 // Olaf Bachmann, Paul S. Wang, Eugene V. Zima 00045 // 00046 // On computational properties of chains of recurrences 00047 // Eugene V. Zima 00048 // 00049 // Symbolic Evaluation of Chains of Recurrences for Loop Optimization 00050 // Robert A. van Engelen 00051 // 00052 // Efficient Symbolic Analysis for Optimizing Compilers 00053 // Robert A. van Engelen 00054 // 00055 // Using the chains of recurrences algebra for data dependence testing and 00056 // induction variable substitution 00057 // MS Thesis, Johnie Birch 00058 // 00059 //===----------------------------------------------------------------------===// 00060 00061 #define DEBUG_TYPE "scalar-evolution" 00062 #include "llvm/Analysis/ScalarEvolutionExpressions.h" 00063 #include "llvm/Constants.h" 00064 #include "llvm/DerivedTypes.h" 00065 #include "llvm/GlobalVariable.h" 00066 #include "llvm/Instructions.h" 00067 #include "llvm/LLVMContext.h" 00068 #include "llvm/Operator.h" 00069 #include "llvm/Analysis/ConstantFolding.h" 00070 #include "llvm/Analysis/Dominators.h" 00071 #include "llvm/Analysis/LoopInfo.h" 00072 #include "llvm/Analysis/ValueTracking.h" 00073 #include "llvm/Assembly/Writer.h" 00074 #include "llvm/Target/TargetData.h" 00075 #include "llvm/Support/CommandLine.h" 00076 #include "llvm/Support/Compiler.h" 00077 #include "llvm/Support/ConstantRange.h" 00078 #include "llvm/Support/ErrorHandling.h" 00079 #include "llvm/Support/GetElementPtrTypeIterator.h" 00080 #include "llvm/Support/InstIterator.h" 00081 #include "llvm/Support/MathExtras.h" 00082 #include "llvm/Support/raw_ostream.h" 00083 #include "llvm/ADT/Statistic.h" 00084 #include "llvm/ADT/STLExtras.h" 00085 #include "llvm/ADT/SmallPtrSet.h" 00086 #include <algorithm> 00087 using namespace llvm; 00088 00089 STATISTIC(NumArrayLenItCounts, 00090 "Number of trip counts computed with array length"); 00091 STATISTIC(NumTripCountsComputed, 00092 "Number of loops with predictable loop counts"); 00093 STATISTIC(NumTripCountsNotComputed, 00094 "Number of loops without predictable loop counts"); 00095 STATISTIC(NumBruteForceTripCountsComputed, 00096 "Number of loops with trip counts computed by force"); 00097 00098 static cl::opt<unsigned> 00099 MaxBruteForceIterations("scalar-evolution-max-iterations", cl::ReallyHidden, 00100 cl::desc("Maximum number of iterations SCEV will " 00101 "symbolically execute a constant " 00102 "derived loop"), 00103 cl::init(100)); 00104 00105 static RegisterPass<ScalarEvolution> 00106 R("scalar-evolution", "Scalar Evolution Analysis", false, true); 00107 char ScalarEvolution::ID = 0; 00108 00109 //===----------------------------------------------------------------------===// 00110 // SCEV class definitions 00111 //===----------------------------------------------------------------------===// 00112 00113 //===----------------------------------------------------------------------===// 00114 // Implementation of the SCEV class. 00115 // 00116 00117 SCEV::~SCEV() {} 00118 00119 void SCEV::dump() const { 00120 print(errs()); 00121 errs() << '\n'; 00122 } 00123 00124 void SCEV::print(std::ostream &o) const { 00125 raw_os_ostream OS(o); 00126 print(OS); 00127 } 00128 00129 bool SCEV::isZero() const { 00130 if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(this)) 00131 return SC->getValue()->isZero(); 00132 return false; 00133 } 00134 00135 bool SCEV::isOne() const { 00136 if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(this)) 00137 return SC->getValue()->isOne(); 00138 return false; 00139 } 00140 00141 bool SCEV::isAllOnesValue() const { 00142 if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(this)) 00143 return SC->getValue()->isAllOnesValue(); 00144 return false; 00145 } 00146 00147 SCEVCouldNotCompute::SCEVCouldNotCompute() : 00148 SCEV(FoldingSetNodeID(), scCouldNotCompute) {} 00149 00150 bool SCEVCouldNotCompute::isLoopInvariant(const Loop *L) const { 00151 llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!"); 00152 return false; 00153 } 00154 00155 const Type *SCEVCouldNotCompute::getType() const { 00156 llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!"); 00157 return 0; 00158 } 00159 00160 bool SCEVCouldNotCompute::hasComputableLoopEvolution(const Loop *L) const { 00161 llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!"); 00162 return false; 00163 } 00164 00165 bool SCEVCouldNotCompute::hasOperand(const SCEV *) const { 00166 llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!"); 00167 return false; 00168 } 00169 00170 void SCEVCouldNotCompute::print(raw_ostream &OS) const { 00171 OS << "***COULDNOTCOMPUTE***"; 00172 } 00173 00174 bool SCEVCouldNotCompute::classof(const SCEV *S) { 00175 return S->getSCEVType() == scCouldNotCompute; 00176 } 00177 00178 const SCEV *ScalarEvolution::getConstant(ConstantInt *V) { 00179 FoldingSetNodeID ID; 00180 ID.AddInteger(scConstant); 00181 ID.AddPointer(V); 00182 void *IP = 0; 00183 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; 00184 SCEV *S = SCEVAllocator.Allocate<SCEVConstant>(); 00185 new (S) SCEVConstant(ID, V); 00186 UniqueSCEVs.InsertNode(S, IP); 00187 return S; 00188 } 00189 00190 const SCEV *ScalarEvolution::getConstant(const APInt& Val) { 00191 return getConstant(ConstantInt::get(getContext(), Val)); 00192 } 00193 00194 const SCEV * 00195 ScalarEvolution::getConstant(const Type *Ty, uint64_t V, bool isSigned) { 00196 return getConstant( 00197 ConstantInt::get(cast<IntegerType>(Ty), V, isSigned)); 00198 } 00199 00200 const Type *SCEVConstant::getType() const { return V->getType(); } 00201 00202 void SCEVConstant::print(raw_ostream &OS) const { 00203 WriteAsOperand(OS, V, false); 00204 } 00205 00206 SCEVCastExpr::SCEVCastExpr(const FoldingSetNodeID &ID, 00207 unsigned SCEVTy, const SCEV *op, const Type *ty) 00208 : SCEV(ID, SCEVTy), Op(op), Ty(ty) {} 00209 00210 bool SCEVCastExpr::dominates(BasicBlock *BB, DominatorTree *DT) const { 00211 return Op->dominates(BB, DT); 00212 } 00213 00214 SCEVTruncateExpr::SCEVTruncateExpr(const FoldingSetNodeID &ID, 00215 const SCEV *op, const Type *ty) 00216 : SCEVCastExpr(ID, scTruncate, op, ty) { 00217 assert((Op->getType()->isInteger() || isa<PointerType>(Op->getType())) && 00218 (Ty->isInteger() || isa<PointerType>(Ty)) && 00219 "Cannot truncate non-integer value!"); 00220 } 00221 00222 void SCEVTruncateExpr::print(raw_ostream &OS) const { 00223 OS << "(trunc " << *Op->getType() << " " << *Op << " to " << *Ty << ")"; 00224 } 00225 00226 SCEVZeroExtendExpr::SCEVZeroExtendExpr(const FoldingSetNodeID &ID, 00227 const SCEV *op, const Type *ty) 00228 : SCEVCastExpr(ID, scZeroExtend, op, ty) { 00229 assert((Op->getType()->isInteger() || isa<PointerType>(Op->getType())) && 00230 (Ty->isInteger() || isa<PointerType>(Ty)) && 00231 "Cannot zero extend non-integer value!"); 00232 } 00233 00234 void SCEVZeroExtendExpr::print(raw_ostream &OS) const { 00235 OS << "(zext " << *Op->getType() << " " << *Op << " to " << *Ty << ")"; 00236 } 00237 00238 SCEVSignExtendExpr::SCEVSignExtendExpr(const FoldingSetNodeID &ID, 00239 const SCEV *op, const Type *ty) 00240 : SCEVCastExpr(ID, scSignExtend, op, ty) { 00241 assert((Op->getType()->isInteger() || isa<PointerType>(Op->getType())) && 00242 (Ty->isInteger() || isa<PointerType>(Ty)) && 00243 "Cannot sign extend non-integer value!"); 00244 } 00245 00246 void SCEVSignExtendExpr::print(raw_ostream &OS) const { 00247 OS << "(sext " << *Op->getType() << " " << *Op << " to " << *Ty << ")"; 00248 } 00249 00250 void SCEVCommutativeExpr::print(raw_ostream &OS) const { 00251 assert(Operands.size() > 1 && "This plus expr shouldn't exist!"); 00252 const char *OpStr = getOperationStr(); 00253 OS << "(" << *Operands[0]; 00254 for (unsigned i = 1, e = Operands.size(); i != e; ++i) 00255 OS << OpStr << *Operands[i]; 00256 OS << ")"; 00257 } 00258 00259 bool SCEVNAryExpr::dominates(BasicBlock *BB, DominatorTree *DT) const { 00260 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) { 00261 if (!getOperand(i)->dominates(BB, DT)) 00262 return false; 00263 } 00264 return true; 00265 } 00266 00267 bool SCEVUDivExpr::dominates(BasicBlock *BB, DominatorTree *DT) const { 00268 return LHS->dominates(BB, DT) && RHS->dominates(BB, DT); 00269 } 00270 00271 void SCEVUDivExpr::print(raw_ostream &OS) const { 00272 OS << "(" << *LHS << " /u " << *RHS << ")"; 00273 } 00274 00275 const Type *SCEVUDivExpr::getType() const { 00276 // In most cases the types of LHS and RHS will be the same, but in some 00277 // crazy cases one or the other may be a pointer. ScalarEvolution doesn't 00278 // depend on the type for correctness, but handling types carefully can 00279 // avoid extra casts in the SCEVExpander. The LHS is more likely to be 00280 // a pointer type than the RHS, so use the RHS' type here. 00281 return RHS->getType(); 00282 } 00283 00284 bool SCEVAddRecExpr::isLoopInvariant(const Loop *QueryLoop) const { 00285 // Add recurrences are never invariant in the function-body (null loop). 00286 if (!QueryLoop) 00287 return false; 00288 00289 // This recurrence is variant w.r.t. QueryLoop if QueryLoop contains L. 00290 if (QueryLoop->contains(L->getHeader())) 00291 return false; 00292 00293 // This recurrence is variant w.r.t. QueryLoop if any of its operands 00294 // are variant. 00295 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) 00296 if (!getOperand(i)->isLoopInvariant(QueryLoop)) 00297 return false; 00298 00299 // Otherwise it's loop-invariant. 00300 return true; 00301 } 00302 00303 void SCEVAddRecExpr::print(raw_ostream &OS) const { 00304 OS << "{" << *Operands[0]; 00305 for (unsigned i = 1, e = Operands.size(); i != e; ++i) 00306 OS << ",+," << *Operands[i]; 00307 OS << "}<" << L->getHeader()->getName() + ">"; 00308 } 00309 00310 void SCEVFieldOffsetExpr::print(raw_ostream &OS) const { 00311 // LLVM struct fields don't have names, so just print the field number. 00312 OS << "offsetof(" << *STy << ", " << FieldNo << ")"; 00313 } 00314 00315 void SCEVAllocSizeExpr::print(raw_ostream &OS) const { 00316 OS << "sizeof(" << *AllocTy << ")"; 00317 } 00318 00319 bool SCEVUnknown::isLoopInvariant(const Loop *L) const { 00320 // All non-instruction values are loop invariant. All instructions are loop 00321 // invariant if they are not contained in the specified loop. 00322 // Instructions are never considered invariant in the function body 00323 // (null loop) because they are defined within the "loop". 00324 if (Instruction *I = dyn_cast<Instruction>(V)) 00325 return L && !L->contains(I->getParent()); 00326 return true; 00327 } 00328 00329 bool SCEVUnknown::dominates(BasicBlock *BB, DominatorTree *DT) const { 00330 if (Instruction *I = dyn_cast<Instruction>(getValue())) 00331 return DT->dominates(I->getParent(), BB); 00332 return true; 00333 } 00334 00335 const Type *SCEVUnknown::getType() const { 00336 return V->getType(); 00337 } 00338 00339 void SCEVUnknown::print(raw_ostream &OS) const { 00340 WriteAsOperand(OS, V, false); 00341 } 00342 00343 //===----------------------------------------------------------------------===// 00344 // SCEV Utilities 00345 //===----------------------------------------------------------------------===// 00346 00347 static bool CompareTypes(const Type *A, const Type *B) { 00348 if (A->getTypeID() != B->getTypeID()) 00349 return A->getTypeID() < B->getTypeID(); 00350 if (const IntegerType *AI = dyn_cast<IntegerType>(A)) { 00351 const IntegerType *BI = cast<IntegerType>(B); 00352 return AI->getBitWidth() < BI->getBitWidth(); 00353 } 00354 if (const PointerType *AI = dyn_cast<PointerType>(A)) { 00355 const PointerType *BI = cast<PointerType>(B); 00356 return CompareTypes(AI->getElementType(), BI->getElementType()); 00357 } 00358 if (const ArrayType *AI = dyn_cast<ArrayType>(A)) { 00359 const ArrayType *BI = cast<ArrayType>(B); 00360 if (AI->getNumElements() != BI->getNumElements()) 00361 return AI->getNumElements() < BI->getNumElements(); 00362 return CompareTypes(AI->getElementType(), BI->getElementType()); 00363 } 00364 if (const VectorType *AI = dyn_cast<VectorType>(A)) { 00365 const VectorType *BI = cast<VectorType>(B); 00366 if (AI->getNumElements() != BI->getNumElements()) 00367 return AI->getNumElements() < BI->getNumElements(); 00368 return CompareTypes(AI->getElementType(), BI->getElementType()); 00369 } 00370 if (const StructType *AI = dyn_cast<StructType>(A)) { 00371 const StructType *BI = cast<StructType>(B); 00372 if (AI->getNumElements() != BI->getNumElements()) 00373 return AI->getNumElements() < BI->getNumElements(); 00374 for (unsigned i = 0, e = AI->getNumElements(); i != e; ++i) 00375 if (CompareTypes(AI->getElementType(i), BI->getElementType(i)) || 00376 CompareTypes(BI->getElementType(i), AI->getElementType(i))) 00377 return CompareTypes(AI->getElementType(i), BI->getElementType(i)); 00378 } 00379 return false; 00380 } 00381 00382 namespace { 00383 /// SCEVComplexityCompare - Return true if the complexity of the LHS is less 00384 /// than the complexity of the RHS. This comparator is used to canonicalize 00385 /// expressions. 00386 class VISIBILITY_HIDDEN SCEVComplexityCompare { 00387 LoopInfo *LI; 00388 public: 00389 explicit SCEVComplexityCompare(LoopInfo *li) : LI(li) {} 00390 00391 bool operator()(const SCEV *LHS, const SCEV *RHS) const { 00392 // Primarily, sort the SCEVs by their getSCEVType(). 00393 if (LHS->getSCEVType() != RHS->getSCEVType()) 00394 return LHS->getSCEVType() < RHS->getSCEVType(); 00395 00396 // Aside from the getSCEVType() ordering, the particular ordering 00397 // isn't very important except that it's beneficial to be consistent, 00398 // so that (a + b) and (b + a) don't end up as different expressions. 00399 00400 // Sort SCEVUnknown values with some loose heuristics. TODO: This is 00401 // not as complete as it could be. 00402 if (const SCEVUnknown *LU = dyn_cast<SCEVUnknown>(LHS)) { 00403 const SCEVUnknown *RU = cast<SCEVUnknown>(RHS); 00404 00405 // Order pointer values after integer values. This helps SCEVExpander 00406 // form GEPs. 00407 if (isa<PointerType>(LU->getType()) && !isa<PointerType>(RU->getType())) 00408 return false; 00409 if (isa<PointerType>(RU->getType()) && !isa<PointerType>(LU->getType())) 00410 return true; 00411 00412 // Compare getValueID values. 00413 if (LU->getValue()->getValueID() != RU->getValue()->getValueID()) 00414 return LU->getValue()->getValueID() < RU->getValue()->getValueID(); 00415 00416 // Sort arguments by their position. 00417 if (const Argument *LA = dyn_cast<Argument>(LU->getValue())) { 00418 const Argument *RA = cast<Argument>(RU->getValue()); 00419 return LA->getArgNo() < RA->getArgNo(); 00420 } 00421 00422 // For instructions, compare their loop depth, and their opcode. 00423 // This is pretty loose. 00424 if (Instruction *LV = dyn_cast<Instruction>(LU->getValue())) { 00425 Instruction *RV = cast<Instruction>(RU->getValue()); 00426 00427 // Compare loop depths. 00428 if (LI->getLoopDepth(LV->getParent()) != 00429 LI->getLoopDepth(RV->getParent())) 00430 return LI->getLoopDepth(LV->getParent()) < 00431 LI->getLoopDepth(RV->getParent()); 00432 00433 // Compare opcodes. 00434 if (LV->getOpcode() != RV->getOpcode()) 00435 return LV->getOpcode() < RV->getOpcode(); 00436 00437 // Compare the number of operands. 00438 if (LV->getNumOperands() != RV->getNumOperands()) 00439 return LV->getNumOperands() < RV->getNumOperands(); 00440 } 00441 00442 return false; 00443 } 00444 00445 // Compare constant values. 00446 if (const SCEVConstant *LC = dyn_cast<SCEVConstant>(LHS)) { 00447 const SCEVConstant *RC = cast<SCEVConstant>(RHS); 00448 if (LC->getValue()->getBitWidth() != RC->getValue()->getBitWidth()) 00449 return LC->getValue()->getBitWidth() < RC->getValue()->getBitWidth(); 00450 return LC->getValue()->getValue().ult(RC->getValue()->getValue()); 00451 } 00452 00453 // Compare addrec loop depths. 00454 if (const SCEVAddRecExpr *LA = dyn_cast<SCEVAddRecExpr>(LHS)) { 00455 const SCEVAddRecExpr *RA = cast<SCEVAddRecExpr>(RHS); 00456 if (LA->getLoop()->getLoopDepth() != RA->getLoop()->getLoopDepth()) 00457 return LA->getLoop()->getLoopDepth() < RA->getLoop()->getLoopDepth(); 00458 } 00459 00460 // Lexicographically compare n-ary expressions. 00461 if (const SCEVNAryExpr *LC = dyn_cast<SCEVNAryExpr>(LHS)) { 00462 const SCEVNAryExpr *RC = cast<SCEVNAryExpr>(RHS); 00463 for (unsigned i = 0, e = LC->getNumOperands(); i != e; ++i) { 00464 if (i >= RC->getNumOperands()) 00465 return false; 00466 if (operator()(LC->getOperand(i), RC->getOperand(i))) 00467 return true; 00468 if (operator()(RC->getOperand(i), LC->getOperand(i))) 00469 return false; 00470 } 00471 return LC->getNumOperands() < RC->getNumOperands(); 00472 } 00473 00474 // Lexicographically compare udiv expressions. 00475 if (const SCEVUDivExpr *LC = dyn_cast<SCEVUDivExpr>(LHS)) { 00476 const SCEVUDivExpr *RC = cast<SCEVUDivExpr>(RHS); 00477 if (operator()(LC->getLHS(), RC->getLHS())) 00478 return true; 00479 if (operator()(RC->getLHS(), LC->getLHS())) 00480 return false; 00481 if (operator()(LC->getRHS(), RC->getRHS())) 00482 return true; 00483 if (operator()(RC->getRHS(), LC->getRHS())) 00484 return false; 00485 return false; 00486 } 00487 00488 // Compare cast expressions by operand. 00489 if (const SCEVCastExpr *LC = dyn_cast<SCEVCastExpr>(LHS)) { 00490 const SCEVCastExpr *RC = cast<SCEVCastExpr>(RHS); 00491 return operator()(LC->getOperand(), RC->getOperand()); 00492 } 00493 00494 // Compare offsetof expressions. 00495 if (const SCEVFieldOffsetExpr *LA = dyn_cast<SCEVFieldOffsetExpr>(LHS)) { 00496 const SCEVFieldOffsetExpr *RA = cast<SCEVFieldOffsetExpr>(RHS); 00497 if (CompareTypes(LA->getStructType(), RA->getStructType()) || 00498 CompareTypes(RA->getStructType(), LA->getStructType())) 00499 return CompareTypes(LA->getStructType(), RA->getStructType()); 00500 return LA->getFieldNo() < RA->getFieldNo(); 00501 } 00502 00503 // Compare sizeof expressions by the allocation type. 00504 if (const SCEVAllocSizeExpr *LA = dyn_cast<SCEVAllocSizeExpr>(LHS)) { 00505 const SCEVAllocSizeExpr *RA = cast<SCEVAllocSizeExpr>(RHS); 00506 return CompareTypes(LA->getAllocType(), RA->getAllocType()); 00507 } 00508 00509 llvm_unreachable("Unknown SCEV kind!"); 00510 return false; 00511 } 00512 }; 00513 } 00514 00515 /// GroupByComplexity - Given a list of SCEV objects, order them by their 00516 /// complexity, and group objects of the same complexity together by value. 00517 /// When this routine is finished, we know that any duplicates in the vector are 00518 /// consecutive and that complexity is monotonically increasing. 00519 /// 00520 /// Note that we go take special precautions to ensure that we get determinstic 00521 /// results from this routine. In other words, we don't want the results of 00522 /// this to depend on where the addresses of various SCEV objects happened to 00523 /// land in memory. 00524 /// 00525 static void GroupByComplexity(SmallVectorImpl<const SCEV *> &Ops, 00526 LoopInfo *LI) { 00527 if (Ops.size() < 2) return; // Noop 00528 if (Ops.size() == 2) { 00529 // This is the common case, which also happens to be trivially simple. 00530 // Special case it. 00531 if (SCEVComplexityCompare(LI)(Ops[1], Ops[0])) 00532 std::swap(Ops[0], Ops[1]); 00533 return; 00534 } 00535 00536 // Do the rough sort by complexity. 00537 std::stable_sort(Ops.begin(), Ops.end(), SCEVComplexityCompare(LI)); 00538 00539 // Now that we are sorted by complexity, group elements of the same 00540 // complexity. Note that this is, at worst, N^2, but the vector is likely to 00541 // be extremely short in practice. Note that we take this approach because we 00542 // do not want to depend on the addresses of the objects we are grouping. 00543 for (unsigned i = 0, e = Ops.size(); i != e-2; ++i) { 00544 const SCEV *S = Ops[i]; 00545 unsigned Complexity = S->getSCEVType(); 00546 00547 // If there are any objects of the same complexity and same value as this 00548 // one, group them. 00549 for (unsigned j = i+1; j != e && Ops[j]->getSCEVType() == Complexity; ++j) { 00550 if (Ops[j] == S) { // Found a duplicate. 00551 // Move it to immediately after i'th element. 00552 std::swap(Ops[i+1], Ops[j]); 00553 ++i; // no need to rescan it. 00554 if (i == e-2) return; // Done! 00555 } 00556 } 00557 } 00558 } 00559 00560 00561 00562 //===----------------------------------------------------------------------===// 00563 // Simple SCEV method implementations 00564 //===----------------------------------------------------------------------===// 00565 00566 /// BinomialCoefficient - Compute BC(It, K). The result has width W. 00567 /// Assume, K > 0. 00568 static const SCEV *BinomialCoefficient(const SCEV *It, unsigned K, 00569 ScalarEvolution &SE, 00570 const Type* ResultTy) { 00571 // Handle the simplest case efficiently. 00572 if (K == 1) 00573 return SE.getTruncateOrZeroExtend(It, ResultTy); 00574 00575 // We are using the following formula for BC(It, K): 00576 // 00577 // BC(It, K) = (It * (It - 1) * ... * (It - K + 1)) / K! 00578 // 00579 // Suppose, W is the bitwidth of the return value. We must be prepared for 00580 // overflow. Hence, we must assure that the result of our computation is 00581 // equal to the accurate one modulo 2^W. Unfortunately, division isn't 00582 // safe in modular arithmetic. 00583 // 00584 // However, this code doesn't use exactly that formula; the formula it uses 00585 // is something like the following, where T is the number of factors of 2 in 00586 // K! (i.e. trailing zeros in the binary representation of K!), and ^ is 00587 // exponentiation: 00588 // 00589 // BC(It, K) = (It * (It - 1) * ... * (It - K + 1)) / 2^T / (K! / 2^T) 00590 // 00591 // This formula is trivially equivalent to the previous formula. However, 00592 // this formula can be implemented much more efficiently. The trick is that 00593 // K! / 2^T is odd, and exact division by an odd number *is* safe in modular 00594 // arithmetic. To do exact division in modular arithmetic, all we have 00595 // to do is multiply by the inverse. Therefore, this step can be done at 00596 // width W. 00597 // 00598 // The next issue is how to safely do the division by 2^T. The way this 00599 // is done is by doing the multiplication step at a width of at least W + T 00600 // bits. This way, the bottom W+T bits of the product are accurate. Then, 00601 // when we perform the division by 2^T (which is equivalent to a right shift 00602 // by T), the bottom W bits are accurate. Extra bits are okay; they'll get 00603 // truncated out after the division by 2^T. 00604 // 00605 // In comparison to just directly using the first formula, this technique 00606 // is much more efficient; using the first formula requires W * K bits, 00607 // but this formula less than W + K bits. Also, the first formula requires 00608 // a division step, whereas this formula only requires multiplies and shifts. 00609 // 00610 // It doesn't matter whether the subtraction step is done in the calculation 00611 // width or the input iteration count's width; if the subtraction overflows, 00612 // the result must be zero anyway. We prefer here to do it in the width of 00613 // the induction variable because it helps a lot for certain cases; CodeGen 00614 // isn't smart enough to ignore the overflow, which leads to much less 00615 // efficient code if the width of the subtraction is wider than the native 00616 // register width. 00617 // 00618 // (It's possible to not widen at all by pulling out factors of 2 before 00619 // the multiplication; for example, K=2 can be calculated as 00620 // It/2*(It+(It*INT_MIN/INT_MIN)+-1). However, it requires 00621 // extra arithmetic, so it's not an obvious win, and it gets 00622 // much more complicated for K > 3.) 00623 00624 // Protection from insane SCEVs; this bound is conservative, 00625 // but it probably doesn't matter. 00626 if (K > 1000) 00627 return SE.getCouldNotCompute(); 00628 00629 unsigned W = SE.getTypeSizeInBits(ResultTy); 00630 00631 // Calculate K! / 2^T and T; we divide out the factors of two before 00632 // multiplying for calculating K! / 2^T to avoid overflow. 00633 // Other overflow doesn't matter because we only care about the bottom 00634 // W bits of the result. 00635 APInt OddFactorial(W, 1); 00636 unsigned T = 1; 00637 for (unsigned i = 3; i <= K; ++i) { 00638 APInt Mult(W, i); 00639 unsigned TwoFactors = Mult.countTrailingZeros(); 00640 T += TwoFactors; 00641 Mult = Mult.lshr(TwoFactors); 00642 OddFactorial *= Mult; 00643 } 00644 00645 // We need at least W + T bits for the multiplication step 00646 unsigned CalculationBits = W + T; 00647 00648 // Calcuate 2^T, at width T+W. 00649 APInt DivFactor = APInt(CalculationBits, 1).shl(T); 00650 00651 // Calculate the multiplicative inverse of K! / 2^T; 00652 // this multiplication factor will perform the exact division by 00653 // K! / 2^T. 00654 APInt Mod = APInt::getSignedMinValue(W+1); 00655 APInt MultiplyFactor = OddFactorial.zext(W+1); 00656 MultiplyFactor = MultiplyFactor.multiplicativeInverse(Mod); 00657 MultiplyFactor = MultiplyFactor.trunc(W); 00658 00659 // Calculate the product, at width T+W 00660 const IntegerType *CalculationTy = IntegerType::get(SE.getContext(), 00661 CalculationBits); 00662 const SCEV *Dividend = SE.getTruncateOrZeroExtend(It, CalculationTy); 00663 for (unsigned i = 1; i != K; ++i) { 00664 const SCEV *S = SE.getMinusSCEV(It, SE.getIntegerSCEV(i, It->getType())); 00665 Dividend = SE.getMulExpr(Dividend, 00666 SE.getTruncateOrZeroExtend(S, CalculationTy)); 00667 } 00668 00669 // Divide by 2^T 00670 const SCEV *DivResult = SE.getUDivExpr(Dividend, SE.getConstant(DivFactor)); 00671 00672 // Truncate the result, and divide by K! / 2^T. 00673 00674 return SE.getMulExpr(SE.getConstant(MultiplyFactor), 00675 SE.getTruncateOrZeroExtend(DivResult, ResultTy)); 00676 } 00677 00678 /// evaluateAtIteration - Return the value of this chain of recurrences at 00679 /// the specified iteration number. We can evaluate this recurrence by 00680 /// multiplying each element in the chain by the binomial coefficient 00681 /// corresponding to it. In other words, we can evaluate {A,+,B,+,C,+,D} as: 00682 /// 00683 /// A*BC(It, 0) + B*BC(It, 1) + C*BC(It, 2) + D*BC(It, 3) 00684 /// 00685 /// where BC(It, k) stands for binomial coefficient. 00686 /// 00687 const SCEV *SCEVAddRecExpr::evaluateAtIteration(const SCEV *It, 00688 ScalarEvolution &SE) const { 00689 const SCEV *Result = getStart(); 00690 for (unsigned i = 1, e = getNumOperands(); i != e; ++i) { 00691 // The computation is correct in the face of overflow provided that the 00692 // multiplication is performed _after_ the evaluation of the binomial 00693 // coefficient. 00694 const SCEV *Coeff = BinomialCoefficient(It, i, SE, getType()); 00695 if (isa<SCEVCouldNotCompute>(Coeff)) 00696 return Coeff; 00697 00698 Result = SE.getAddExpr(Result, SE.getMulExpr(getOperand(i), Coeff)); 00699 } 00700 return Result; 00701 } 00702 00703 //===----------------------------------------------------------------------===// 00704 // SCEV Expression folder implementations 00705 //===----------------------------------------------------------------------===// 00706 00707 const SCEV *ScalarEvolution::getTruncateExpr(const SCEV *Op, 00708 const Type *Ty) { 00709 assert(getTypeSizeInBits(Op->getType()) > getTypeSizeInBits(Ty) && 00710 "This is not a truncating conversion!"); 00711 assert(isSCEVable(Ty) && 00712 "This is not a conversion to a SCEVable type!"); 00713 Ty = getEffectiveSCEVType(Ty); 00714 00715 FoldingSetNodeID ID; 00716 ID.AddInteger(scTruncate); 00717 ID.AddPointer(Op); 00718 ID.AddPointer(Ty); 00719 void *IP = 0; 00720 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; 00721 00722 // Fold if the operand is constant. 00723 if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Op)) 00724 return getConstant( 00725 cast<ConstantInt>(ConstantExpr::getTrunc(SC->getValue(), Ty))); 00726 00727 // trunc(trunc(x)) --> trunc(x) 00728 if (const SCEVTruncateExpr *ST = dyn_cast<SCEVTruncateExpr>(Op)) 00729 return getTruncateExpr(ST->getOperand(), Ty); 00730 00731 // trunc(sext(x)) --> sext(x) if widening or trunc(x) if narrowing 00732 if (const SCEVSignExtendExpr *SS = dyn_cast<SCEVSignExtendExpr>(Op)) 00733 return getTruncateOrSignExtend(SS->getOperand(), Ty); 00734 00735 // trunc(zext(x)) --> zext(x) if widening or trunc(x) if narrowing 00736 if (const SCEVZeroExtendExpr *SZ = dyn_cast<SCEVZeroExtendExpr>(Op)) 00737 return getTruncateOrZeroExtend(SZ->getOperand(), Ty); 00738 00739 // If the input value is a chrec scev, truncate the chrec's operands. 00740 if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Op)) { 00741 SmallVector<const SCEV *, 4> Operands; 00742 for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i) 00743 Operands.push_back(getTruncateExpr(AddRec->getOperand(i), Ty)); 00744 return getAddRecExpr(Operands, AddRec->getLoop()); 00745 } 00746 00747 // The cast wasn't folded; create an explicit cast node. 00748 // Recompute the insert position, as it may have been invalidated. 00749 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; 00750 SCEV *S = SCEVAllocator.Allocate<SCEVTruncateExpr>(); 00751 new (S) SCEVTruncateExpr(ID, Op, Ty); 00752 UniqueSCEVs.InsertNode(S, IP); 00753 return S; 00754 } 00755 00756 const SCEV *ScalarEvolution::getZeroExtendExpr(const SCEV *Op, 00757 const Type *Ty) { 00758 assert(getTypeSizeInBits(Op->getType()) < getTypeSizeInBits(Ty) && 00759 "This is not an extending conversion!"); 00760 assert(isSCEVable(Ty) && 00761 "This is not a conversion to a SCEVable type!"); 00762 Ty = getEffectiveSCEVType(Ty); 00763 00764 // Fold if the operand is constant. 00765 if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Op)) { 00766 const Type *IntTy = getEffectiveSCEVType(Ty); 00767 Constant *C = ConstantExpr::getZExt(SC->getValue(), IntTy); 00768 if (IntTy != Ty) C = ConstantExpr::getIntToPtr(C, Ty); 00769 return getConstant(cast<ConstantInt>(C)); 00770 } 00771 00772 // zext(zext(x)) --> zext(x) 00773 if (const SCEVZeroExtendExpr *SZ = dyn_cast<SCEVZeroExtendExpr>(Op)) 00774 return getZeroExtendExpr(SZ->getOperand(), Ty); 00775 00776 // Before doing any expensive analysis, check to see if we've already 00777 // computed a SCEV for this Op and Ty. 00778 FoldingSetNodeID ID; 00779 ID.AddInteger(scZeroExtend); 00780 ID.AddPointer(Op); 00781 ID.AddPointer(Ty); 00782 void *IP = 0; 00783 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; 00784 00785 // If the input value is a chrec scev, and we can prove that the value 00786 // did not overflow the old, smaller, value, we can zero extend all of the 00787 // operands (often constants). This allows analysis of something like 00788 // this: for (unsigned char X = 0; X < 100; ++X) { int Y = X; } 00789 if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Op)) 00790 if (AR->isAffine()) { 00791 const SCEV *Start = AR->getStart(); 00792 const SCEV *Step = AR->getStepRecurrence(*this); 00793 unsigned BitWidth = getTypeSizeInBits(AR->getType()); 00794 const Loop *L = AR->getLoop(); 00795 00796 // If we have special knowledge that this addrec won't overflow, 00797 // we don't need to do any further analysis. 00798 if (AR->hasNoUnsignedWrap()) 00799 return getAddRecExpr(getZeroExtendExpr(Start, Ty), 00800 getZeroExtendExpr(Step, Ty), 00801 L); 00802 00803 // Check whether the backedge-taken count is SCEVCouldNotCompute. 00804 // Note that this serves two purposes: It filters out loops that are 00805 // simply not analyzable, and it covers the case where this code is 00806 // being called from within backedge-taken count analysis, such that 00807 // attempting to ask for the backedge-taken count would likely result 00808 // in infinite recursion. In the later case, the analysis code will 00809 // cope with a conservative value, and it will take care to purge 00810 // that value once it has finished. 00811 const SCEV *MaxBECount = getMaxBackedgeTakenCount(L); 00812 if (!isa<SCEVCouldNotCompute>(MaxBECount)) { 00813 // Manually compute the final value for AR, checking for 00814 // overflow. 00815 00816 // Check whether the backedge-taken count can be losslessly casted to 00817 // the addrec's type. The count is always unsigned. 00818 const SCEV *CastedMaxBECount = 00819 getTruncateOrZeroExtend(MaxBECount, Start->getType()); 00820 const SCEV *RecastedMaxBECount = 00821 getTruncateOrZeroExtend(CastedMaxBECount, MaxBECount->getType()); 00822 if (MaxBECount == RecastedMaxBECount) { 00823 const Type *WideTy = IntegerType::get(getContext(), BitWidth * 2); 00824 // Check whether Start+Step*MaxBECount has no unsigned overflow. 00825 const SCEV *ZMul = 00826 getMulExpr(CastedMaxBECount, 00827 getTruncateOrZeroExtend(Step, Start->getType())); 00828 const SCEV *Add = getAddExpr(Start, ZMul); 00829 const SCEV *OperandExtendedAdd = 00830 getAddExpr(getZeroExtendExpr(Start, WideTy), 00831 getMulExpr(getZeroExtendExpr(CastedMaxBECount, WideTy), 00832 getZeroExtendExpr(Step, WideTy))); 00833 if (getZeroExtendExpr(Add, WideTy) == OperandExtendedAdd) 00834 // Return the expression with the addrec on the outside. 00835 return getAddRecExpr(getZeroExtendExpr(Start, Ty), 00836 getZeroExtendExpr(Step, Ty), 00837 L); 00838 00839 // Similar to above, only this time treat the step value as signed. 00840 // This covers loops that count down. 00841 const SCEV *SMul = 00842 getMulExpr(CastedMaxBECount, 00843 getTruncateOrSignExtend(Step, Start->getType())); 00844 Add = getAddExpr(Start, SMul); 00845 OperandExtendedAdd = 00846 getAddExpr(getZeroExtendExpr(Start, WideTy), 00847 getMulExpr(getZeroExtendExpr(CastedMaxBECount, WideTy), 00848 getSignExtendExpr(Step, WideTy))); 00849 if (getZeroExtendExpr(Add, WideTy) == OperandExtendedAdd) 00850 // Return the expression with the addrec on the outside. 00851 return getAddRecExpr(getZeroExtendExpr(Start, Ty), 00852 getSignExtendExpr(Step, Ty), 00853 L); 00854 } 00855 00856 // If the backedge is guarded by a comparison with the pre-inc value 00857 // the addrec is safe. Also, if the entry is guarded by a comparison 00858 // with the start value and the backedge is guarded by a comparison 00859 // with the post-inc value, the addrec is safe. 00860 if (isKnownPositive(Step)) { 00861 const SCEV *N = getConstant(APInt::getMinValue(BitWidth) - 00862 getUnsignedRange(Step).getUnsignedMax()); 00863 if (isLoopBackedgeGuardedByCond(L, ICmpInst::ICMP_ULT, AR, N) || 00864 (isLoopGuardedByCond(L, ICmpInst::ICMP_ULT, Start, N) && 00865 isLoopBackedgeGuardedByCond(L, ICmpInst::ICMP_ULT, 00866 AR->getPostIncExpr(*this), N))) 00867 // Return the expression with the addrec on the outside. 00868 return getAddRecExpr(getZeroExtendExpr(Start, Ty), 00869 getZeroExtendExpr(Step, Ty), 00870 L); 00871 } else if (isKnownNegative(Step)) { 00872 const SCEV *N = getConstant(APInt::getMaxValue(BitWidth) - 00873 getSignedRange(Step).getSignedMin()); 00874 if (isLoopBackedgeGuardedByCond(L, ICmpInst::ICMP_UGT, AR, N) && 00875 (isLoopGuardedByCond(L, ICmpInst::ICMP_UGT, Start, N) || 00876 isLoopBackedgeGuardedByCond(L, ICmpInst::ICMP_UGT, 00877 AR->getPostIncExpr(*this), N))) 00878 // Return the expression with the addrec on the outside. 00879 return getAddRecExpr(getZeroExtendExpr(Start, Ty), 00880 getSignExtendExpr(Step, Ty), 00881 L); 00882 } 00883 } 00884 } 00885 00886 // The cast wasn't folded; create an explicit cast node. 00887 // Recompute the insert position, as it may have been invalidated. 00888 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; 00889 SCEV *S = SCEVAllocator.Allocate<SCEVZeroExtendExpr>(); 00890 new (S) SCEVZeroExtendExpr(ID, Op, Ty); 00891 UniqueSCEVs.InsertNode(S, IP); 00892 return S; 00893 } 00894 00895 const SCEV *ScalarEvolution::getSignExtendExpr(const SCEV *Op, 00896 const Type *Ty) { 00897 assert(getTypeSizeInBits(Op->getType()) < getTypeSizeInBits(Ty) && 00898 "This is not an extending conversion!"); 00899 assert(isSCEVable(Ty) && 00900 "This is not a conversion to a SCEVable type!"); 00901 Ty = getEffectiveSCEVType(Ty); 00902 00903 // Fold if the operand is constant. 00904 if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Op)) { 00905 const Type *IntTy = getEffectiveSCEVType(Ty); 00906 Constant *C = ConstantExpr::getSExt(SC->getValue(), IntTy); 00907 if (IntTy != Ty) C = ConstantExpr::getIntToPtr(C, Ty); 00908 return getConstant(cast<ConstantInt>(C)); 00909 } 00910 00911 // sext(sext(x)) --> sext(x) 00912 if (const SCEVSignExtendExpr *SS = dyn_cast<SCEVSignExtendExpr>(Op)) 00913 return getSignExtendExpr(SS->getOperand(), Ty); 00914 00915 // Before doing any expensive analysis, check to see if we've already 00916 // computed a SCEV for this Op and Ty. 00917 FoldingSetNodeID ID; 00918 ID.AddInteger(scSignExtend); 00919 ID.AddPointer(Op); 00920 ID.AddPointer(Ty); 00921 void *IP = 0; 00922 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; 00923 00924 // If the input value is a chrec scev, and we can prove that the value 00925 // did not overflow the old, smaller, value, we can sign extend all of the 00926 // operands (often constants). This allows analysis of something like 00927 // this: for (signed char X = 0; X < 100; ++X) { int Y = X; } 00928 if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Op)) 00929 if (AR->isAffine()) { 00930 const SCEV *Start = AR->getStart(); 00931 const SCEV *Step = AR->getStepRecurrence(*this); 00932 unsigned BitWidth = getTypeSizeInBits(AR->getType()); 00933 const Loop *L = AR->getLoop(); 00934 00935 // If we have special knowledge that this addrec won't overflow, 00936 // we don't need to do any further analysis. 00937 if (AR->hasNoSignedWrap()) 00938 return getAddRecExpr(getSignExtendExpr(Start, Ty), 00939 getSignExtendExpr(Step, Ty), 00940 L); 00941 00942 // Check whether the backedge-taken count is SCEVCouldNotCompute. 00943 // Note that this serves two purposes: It filters out loops that are 00944 // simply not analyzable, and it covers the case where this code is 00945 // being called from within backedge-taken count analysis, such that 00946 // attempting to ask for the backedge-taken count would likely result 00947 // in infinite recursion. In the later case, the analysis code will 00948 // cope with a conservative value, and it will take care to purge 00949 // that value once it has finished. 00950 const SCEV *MaxBECount = getMaxBackedgeTakenCount(L); 00951 if (!isa<SCEVCouldNotCompute>(MaxBECount)) { 00952 // Manually compute the final value for AR, checking for 00953 // overflow. 00954 00955 // Check whether the backedge-taken count can be losslessly casted to 00956 // the addrec's type. The count is always unsigned. 00957 const SCEV *CastedMaxBECount = 00958 getTruncateOrZeroExtend(MaxBECount, Start->getType()); 00959 const SCEV *RecastedMaxBECount = 00960 getTruncateOrZeroExtend(CastedMaxBECount, MaxBECount->getType()); 00961 if (MaxBECount == RecastedMaxBECount) { 00962 const Type *WideTy = IntegerType::get(getContext(), BitWidth * 2); 00963 // Check whether Start+Step*MaxBECount has no signed overflow. 00964 const SCEV *SMul = 00965 getMulExpr(CastedMaxBECount, 00966 getTruncateOrSignExtend(Step, Start->getType())); 00967 const SCEV *Add = getAddExpr(Start, SMul); 00968 const SCEV *OperandExtendedAdd = 00969 getAddExpr(getSignExtendExpr(Start, WideTy), 00970 getMulExpr(getZeroExtendExpr(CastedMaxBECount, WideTy), 00971 getSignExtendExpr(Step, WideTy))); 00972 if (getSignExtendExpr(Add, WideTy) == OperandExtendedAdd) 00973 // Return the expression with the addrec on the outside. 00974 return getAddRecExpr(getSignExtendExpr(Start, Ty), 00975 getSignExtendExpr(Step, Ty), 00976 L); 00977 00978 // Similar to above, only this time treat the step value as unsigned. 00979 // This covers loops that count up with an unsigned step. 00980 const SCEV *UMul = 00981 getMulExpr(CastedMaxBECount, 00982 getTruncateOrZeroExtend(Step, Start->getType())); 00983 Add = getAddExpr(Start, UMul); 00984 OperandExtendedAdd = 00985 getAddExpr(getSignExtendExpr(Start, WideTy), 00986 getMulExpr(getZeroExtendExpr(CastedMaxBECount, WideTy), 00987 getZeroExtendExpr(Step, WideTy))); 00988 if (getSignExtendExpr(Add, WideTy) == OperandExtendedAdd) 00989 // Return the expression with the addrec on the outside. 00990 return getAddRecExpr(getSignExtendExpr(Start, Ty), 00991 getZeroExtendExpr(Step, Ty), 00992 L); 00993 } 00994 00995 // If the backedge is guarded by a comparison with the pre-inc value 00996 // the addrec is safe. Also, if the entry is guarded by a comparison 00997 // with the start value and the backedge is guarded by a comparison 00998 // with the post-inc value, the addrec is safe. 00999 if (isKnownPositive(Step)) { 01000 const SCEV *N = getConstant(APInt::getSignedMinValue(BitWidth) - 01001 getSignedRange(Step).getSignedMax()); 01002 if (isLoopBackedgeGuardedByCond(L, ICmpInst::ICMP_SLT, AR, N) || 01003 (isLoopGuardedByCond(L, ICmpInst::ICMP_SLT, Start, N) && 01004 isLoopBackedgeGuardedByCond(L, ICmpInst::ICMP_SLT, 01005 AR->getPostIncExpr(*this), N))) 01006 // Return the expression with the addrec on the outside. 01007 return getAddRecExpr(getSignExtendExpr(Start, Ty), 01008 getSignExtendExpr(Step, Ty), 01009 L); 01010 } else if (isKnownNegative(Step)) { 01011 const SCEV *N = getConstant(APInt::getSignedMaxValue(BitWidth) - 01012 getSignedRange(Step).getSignedMin()); 01013 if (isLoopBackedgeGuardedByCond(L, ICmpInst::ICMP_SGT, AR, N) || 01014 (isLoopGuardedByCond(L, ICmpInst::ICMP_SGT, Start, N) && 01015 isLoopBackedgeGuardedByCond(L, ICmpInst::ICMP_SGT, 01016 AR->getPostIncExpr(*this), N))) 01017 // Return the expression with the addrec on the outside. 01018 return getAddRecExpr(getSignExtendExpr(Start, Ty), 01019 getSignExtendExpr(Step, Ty), 01020 L); 01021 } 01022 } 01023 } 01024 01025 // The cast wasn't folded; create an explicit cast node. 01026 // Recompute the insert position, as it may have been invalidated. 01027 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; 01028 SCEV *S = SCEVAllocator.Allocate<SCEVSignExtendExpr>(); 01029 new (S) SCEVSignExtendExpr(ID, Op, Ty); 01030 UniqueSCEVs.InsertNode(S, IP); 01031 return S; 01032 } 01033 01034 /// getAnyExtendExpr - Return a SCEV for the given operand extended with 01035 /// unspecified bits out to the given type. 01036 /// 01037 const SCEV *ScalarEvolution::getAnyExtendExpr(const SCEV *Op, 01038 const Type *Ty) { 01039 assert(getTypeSizeInBits(Op->getType()) < getTypeSizeInBits(Ty) && 01040 "This is not an extending conversion!"); 01041 assert(isSCEVable(Ty) && 01042 "This is not a conversion to a SCEVable type!"); 01043 Ty = getEffectiveSCEVType(Ty); 01044 01045 // Sign-extend negative constants. 01046 if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Op)) 01047 if (SC->getValue()->getValue().isNegative()) 01048 return getSignExtendExpr(Op, Ty); 01049 01050 // Peel off a truncate cast. 01051 if (const SCEVTruncateExpr *T = dyn_cast<SCEVTruncateExpr>(Op)) { 01052 const SCEV *NewOp = T->getOperand(); 01053 if (getTypeSizeInBits(NewOp->getType()) < getTypeSizeInBits(Ty)) 01054 return getAnyExtendExpr(NewOp, Ty); 01055 return getTruncateOrNoop(NewOp, Ty); 01056 } 01057 01058 // Next try a zext cast. If the cast is folded, use it. 01059 const SCEV *ZExt = getZeroExtendExpr(Op, Ty); 01060 if (!isa<SCEVZeroExtendExpr>(ZExt)) 01061 return ZExt; 01062 01063 // Next try a sext cast. If the cast is folded, use it. 01064 const SCEV *SExt = getSignExtendExpr(Op, Ty); 01065 if (!isa<SCEVSignExtendExpr>(SExt)) 01066 return SExt; 01067 01068 // If the expression is obviously signed, use the sext cast value. 01069 if (isa<SCEVSMaxExpr>(Op)) 01070 return SExt; 01071 01072 // Absent any other information, use the zext cast value. 01073 return ZExt; 01074 } 01075 01076 /// CollectAddOperandsWithScales - Process the given Ops list, which is 01077 /// a list of operands to be added under the given scale, update the given 01078 /// map. This is a helper function for getAddRecExpr. As an example of 01079 /// what it does, given a sequence of operands that would form an add 01080 /// expression like this: 01081 /// 01082 /// m + n + 13 + (A * (o + p + (B * q + m + 29))) + r + (-1 * r) 01083 /// 01084 /// where A and B are constants, update the map with these values: 01085 /// 01086 /// (m, 1+A*B), (n, 1), (o, A), (p, A), (q, A*B), (r, 0) 01087 /// 01088 /// and add 13 + A*B*29 to AccumulatedConstant. 01089 /// This will allow getAddRecExpr to produce this: 01090 /// 01091 /// 13+A*B*29 + n + (m * (1+A*B)) + ((o + p) * A) + (q * A*B) 01092 /// 01093 /// This form often exposes folding opportunities that are hidden in 01094 /// the original operand list. 01095 /// 01096 /// Return true iff it appears that any interesting folding opportunities 01097 /// may be exposed. This helps getAddRecExpr short-circuit extra work in 01098 /// the common case where no interesting opportunities are present, and 01099 /// is also used as a check to avoid infinite recursion. 01100 /// 01101 static bool 01102 CollectAddOperandsWithScales(DenseMap<const SCEV *, APInt> &M, 01103 SmallVector<const SCEV *, 8> &NewOps, 01104 APInt &AccumulatedConstant, 01105 const SmallVectorImpl<const SCEV *> &Ops, 01106 const APInt &Scale, 01107 ScalarEvolution &SE) { 01108 bool Interesting = false; 01109 01110 // Iterate over the add operands. 01111 for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 01112 const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(Ops[i]); 01113 if (Mul && isa<SCEVConstant>(Mul->getOperand(0))) { 01114 APInt NewScale = 01115 Scale * cast<SCEVConstant>(Mul->getOperand(0))->getValue()->getValue(); 01116 if (Mul->getNumOperands() == 2 && isa<SCEVAddExpr>(Mul->getOperand(1))) { 01117 // A multiplication of a constant with another add; recurse. 01118 Interesting |= 01119 CollectAddOperandsWithScales(M, NewOps, AccumulatedConstant, 01120 cast<SCEVAddExpr>(Mul->getOperand(1)) 01121 ->getOperands(), 01122 NewScale, SE); 01123 } else { 01124 // A multiplication of a constant with some other value. Update 01125 // the map. 01126 SmallVector<const SCEV *, 4> MulOps(Mul->op_begin()+1, Mul->op_end()); 01127 const SCEV *Key = SE.getMulExpr(MulOps); 01128 std::pair<DenseMap<const SCEV *, APInt>::iterator, bool> Pair = 01129 M.insert(std::make_pair(Key, NewScale)); 01130 if (Pair.second) { 01131 NewOps.push_back(Pair.first->first); 01132 } else { 01133 Pair.first->second += NewScale; 01134 // The map already had an entry for this value, which may indicate 01135 // a folding opportunity. 01136 Interesting = true; 01137 } 01138 } 01139 } else if (const SCEVConstant *C = dyn_cast<SCEVConstant>(Ops[i])) { 01140 // Pull a buried constant out to the outside. 01141 if (Scale != 1 || AccumulatedConstant != 0 || C->isZero()) 01142 Interesting = true; 01143 AccumulatedConstant += Scale * C->getValue()->getValue(); 01144 } else { 01145 // An ordinary operand. Update the map. 01146 std::pair<DenseMap<const SCEV *, APInt>::iterator, bool> Pair = 01147 M.insert(std::make_pair(Ops[i], Scale)); 01148 if (Pair.second) { 01149 NewOps.push_back(Pair.first->first); 01150 } else { 01151 Pair.first->second += Scale; 01152 // The map already had an entry for this value, which may indicate 01153 // a folding opportunity. 01154 Interesting = true; 01155 } 01156 } 01157 } 01158 01159 return Interesting; 01160 } 01161 01162 namespace { 01163 struct APIntCompare { 01164 bool operator()(const APInt &LHS, const APInt &RHS) const { 01165 return LHS.ult(RHS); 01166 } 01167 }; 01168 } 01169 01170 /// getAddExpr - Get a canonical add expression, or something simpler if 01171 /// possible. 01172 const SCEV *ScalarEvolution::getAddExpr(SmallVectorImpl<const SCEV *> &Ops) { 01173 assert(!Ops.empty() && "Cannot get empty add!"); 01174 if (Ops.size() == 1) return Ops[0]; 01175 #ifndef NDEBUG 01176 for (unsigned i = 1, e = Ops.size(); i != e; ++i) 01177 assert(getEffectiveSCEVType(Ops[i]->getType()) == 01178 getEffectiveSCEVType(Ops[0]->getType()) && 01179 "SCEVAddExpr operand types don't match!"); 01180 #endif 01181 01182 // Sort by complexity, this groups all similar expression types together. 01183 GroupByComplexity(Ops, LI); 01184 01185 // If there are any constants, fold them together. 01186 unsigned Idx = 0; 01187 if (const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) { 01188 ++Idx; 01189 assert(Idx < Ops.size()); 01190 while (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) { 01191 // We found two constants, fold them together! 01192 Ops[0] = getConstant(LHSC->getValue()->getValue() + 01193 RHSC->getValue()->getValue()); 01194 if (Ops.size() == 2) return Ops[0]; 01195 Ops.erase(Ops.begin()+1); // Erase the folded element 01196 LHSC = cast<SCEVConstant>(Ops[0]); 01197 } 01198 01199 // If we are left with a constant zero being added, strip it off. 01200 if (cast<SCEVConstant>(Ops[0])->getValue()->isZero()) { 01201 Ops.erase(Ops.begin()); 01202 --Idx; 01203 } 01204 } 01205 01206 if (Ops.size() == 1) return Ops[0]; 01207 01208 // Okay, check to see if the same value occurs in the operand list twice. If 01209 // so, merge them together into an multiply expression. Since we sorted the 01210 // list, these values are required to be adjacent. 01211 const Type *Ty = Ops[0]->getType(); 01212 for (unsigned i = 0, e = Ops.size()-1; i != e; ++i) 01213 if (Ops[i] == Ops[i+1]) { // X + Y + Y --> X + Y*2 01214 // Found a match, merge the two values into a multiply, and add any 01215 // remaining values to the result. 01216 const SCEV *Two = getIntegerSCEV(2, Ty); 01217 const SCEV *Mul = getMulExpr(Ops[i], Two); 01218 if (Ops.size() == 2) 01219 return Mul; 01220 Ops.erase(Ops.begin()+i, Ops.begin()+i+2); 01221 Ops.push_back(Mul); 01222 return getAddExpr(Ops); 01223 } 01224 01225 // Check for truncates. If all the operands are truncated from the same 01226 // type, see if factoring out the truncate would permit the result to be 01227 // folded. eg., trunc(x) + m*trunc(n) --> trunc(x + trunc(m)*n) 01228 // if the contents of the resulting outer trunc fold to something simple. 01229 for (; Idx < Ops.size() && isa<SCEVTruncateExpr>(Ops[Idx]); ++Idx) { 01230 const SCEVTruncateExpr *Trunc = cast<SCEVTruncateExpr>(Ops[Idx]); 01231 const Type *DstType = Trunc->getType(); 01232 const Type *SrcType = Trunc->getOperand()->getType(); 01233 SmallVector<const SCEV *, 8> LargeOps; 01234 bool Ok = true; 01235 // Check all the operands to see if they can be represented in the 01236 // source type of the truncate. 01237 for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 01238 if (const SCEVTruncateExpr *T = dyn_cast<SCEVTruncateExpr>(Ops[i])) { 01239 if (T->getOperand()->getType() != SrcType) { 01240 Ok = false; 01241 break; 01242 } 01243 LargeOps.push_back(T->getOperand()); 01244 } else if (const SCEVConstant *C = dyn_cast<SCEVConstant>(Ops[i])) { 01245 // This could be either sign or zero extension, but sign extension 01246 // is much more likely to be foldable here. 01247 LargeOps.push_back(getSignExtendExpr(C, SrcType)); 01248 } else if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(Ops[i])) { 01249 SmallVector<const SCEV *, 8> LargeMulOps; 01250 for (unsigned j = 0, f = M->getNumOperands(); j != f && Ok; ++j) { 01251 if (const SCEVTruncateExpr *T = 01252 dyn_cast<SCEVTruncateExpr>(M->getOperand(j))) { 01253 if (T->getOperand()->getType() != SrcType) { 01254 Ok = false; 01255 break; 01256 } 01257 LargeMulOps.push_back(T->getOperand()); 01258 } else if (const SCEVConstant *C = 01259 dyn_cast<SCEVConstant>(M->getOperand(j))) { 01260 // This could be either sign or zero extension, but sign extension 01261 // is much more likely to be foldable here. 01262 LargeMulOps.push_back(getSignExtendExpr(C, SrcType)); 01263 } else { 01264 Ok = false; 01265 break; 01266 } 01267 } 01268 if (Ok) 01269 LargeOps.push_back(getMulExpr(LargeMulOps)); 01270 } else { 01271 Ok = false; 01272 break; 01273 } 01274 } 01275 if (Ok) { 01276 // Evaluate the expression in the larger type. 01277 const SCEV *Fold = getAddExpr(LargeOps); 01278 // If it folds to something simple, use it. Otherwise, don't. 01279 if (isa<SCEVConstant>(Fold) || isa<SCEVUnknown>(Fold)) 01280 return getTruncateExpr(Fold, DstType); 01281 } 01282 } 01283 01284 // Skip past any other cast SCEVs. 01285 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scAddExpr) 01286 ++Idx; 01287 01288 // If there are add operands they would be next. 01289 if (Idx < Ops.size()) { 01290 bool DeletedAdd = false; 01291 while (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Ops[Idx])) { 01292 // If we have an add, expand the add operands onto the end of the operands 01293 // list. 01294 Ops.insert(Ops.end(), Add->op_begin(), Add->op_end()); 01295 Ops.erase(Ops.begin()+Idx); 01296 DeletedAdd = true; 01297 } 01298 01299 // If we deleted at least one add, we added operands to the end of the list, 01300 // and they are not necessarily sorted. Recurse to resort and resimplify 01301 // any operands we just aquired. 01302 if (DeletedAdd) 01303 return getAddExpr(Ops); 01304 } 01305 01306 // Skip over the add expression until we get to a multiply. 01307 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scMulExpr) 01308 ++Idx; 01309 01310 // Check to see if there are any folding opportunities present with 01311 // operands multiplied by constant values. 01312 if (Idx < Ops.size() && isa<SCEVMulExpr>(Ops[Idx])) { 01313 uint64_t BitWidth = getTypeSizeInBits(Ty); 01314 DenseMap<const SCEV *, APInt> M; 01315 SmallVector<const SCEV *, 8> NewOps; 01316 APInt AccumulatedConstant(BitWidth, 0); 01317 if (CollectAddOperandsWithScales(M, NewOps, AccumulatedConstant, 01318 Ops, APInt(BitWidth, 1), *this)) { 01319 // Some interesting folding opportunity is present, so its worthwhile to 01320 // re-generate the operands list. Group the operands by constant scale, 01321 // to avoid multiplying by the same constant scale multiple times. 01322 std::map<APInt, SmallVector<const SCEV *, 4>, APIntCompare> MulOpLists; 01323 for (SmallVector<const SCEV *, 8>::iterator I = NewOps.begin(), 01324 E = NewOps.end(); I != E; ++I) 01325 MulOpLists[M.find(*I)->second].push_back(*I); 01326 // Re-generate the operands list. 01327 Ops.clear(); 01328 if (AccumulatedConstant != 0) 01329 Ops.push_back(getConstant(AccumulatedConstant)); 01330 for (std::map<APInt, SmallVector<const SCEV *, 4>, APIntCompare>::iterator 01331 I = MulOpLists.begin(), E = MulOpLists.end(); I != E; ++I) 01332 if (I->first != 0) 01333 Ops.push_back(getMulExpr(getConstant(I->first), 01334 getAddExpr(I->second))); 01335 if (Ops.empty()) 01336 return getIntegerSCEV(0, Ty); 01337 if (Ops.size() == 1) 01338 return Ops[0]; 01339 return getAddExpr(Ops); 01340 } 01341 } 01342 01343 // If we are adding something to a multiply expression, make sure the 01344 // something is not already an operand of the multiply. If so, merge it into 01345 // the multiply. 01346 for (; Idx < Ops.size() && isa<SCEVMulExpr>(Ops[Idx]); ++Idx) { 01347 const SCEVMulExpr *Mul = cast<SCEVMulExpr>(Ops[Idx]); 01348 for (unsigned MulOp = 0, e = Mul->getNumOperands(); MulOp != e; ++MulOp) { 01349 const SCEV *MulOpSCEV = Mul->getOperand(MulOp); 01350 for (unsigned AddOp = 0, e = Ops.size(); AddOp != e; ++AddOp) 01351 if (MulOpSCEV == Ops[AddOp] && !isa<SCEVConstant>(Ops[AddOp])) { 01352 // Fold W + X + (X * Y * Z) --> W + (X * ((Y*Z)+1)) 01353 const SCEV *InnerMul = Mul->getOperand(MulOp == 0); 01354 if (Mul->getNumOperands() != 2) { 01355 // If the multiply has more than two operands, we must get the 01356 // Y*Z term. 01357 SmallVector<const SCEV *, 4> MulOps(Mul->op_begin(), Mul->op_end()); 01358 MulOps.erase(MulOps.begin()+MulOp); 01359 InnerMul = getMulExpr(MulOps); 01360 } 01361 const SCEV *One = getIntegerSCEV(1, Ty); 01362 const SCEV *AddOne = getAddExpr(InnerMul, One); 01363 const SCEV *OuterMul = getMulExpr(AddOne, Ops[AddOp]); 01364 if (Ops.size() == 2) return OuterMul; 01365 if (AddOp < Idx) { 01366 Ops.erase(Ops.begin()+AddOp); 01367 Ops.erase(Ops.begin()+Idx-1); 01368 } else { 01369 Ops.erase(Ops.begin()+Idx); 01370 Ops.erase(Ops.begin()+AddOp-1); 01371 } 01372 Ops.push_back(OuterMul); 01373 return getAddExpr(Ops); 01374 } 01375 01376 // Check this multiply against other multiplies being added together. 01377 for (unsigned OtherMulIdx = Idx+1; 01378 OtherMulIdx < Ops.size() && isa<SCEVMulExpr>(Ops[OtherMulIdx]); 01379 ++OtherMulIdx) { 01380 const SCEVMulExpr *OtherMul = cast<SCEVMulExpr>(Ops[OtherMulIdx]); 01381 // If MulOp occurs in OtherMul, we can fold the two multiplies 01382 // together. 01383 for (unsigned OMulOp = 0, e = OtherMul->getNumOperands(); 01384 OMulOp != e; ++OMulOp) 01385 if (OtherMul->getOperand(OMulOp) == MulOpSCEV) { 01386 // Fold X + (A*B*C) + (A*D*E) --> X + (A*(B*C+D*E)) 01387 const SCEV *InnerMul1 = Mul->getOperand(MulOp == 0); 01388 if (Mul->getNumOperands() != 2) { 01389 SmallVector<const SCEV *, 4> MulOps(Mul->op_begin(), 01390 Mul->op_end()); 01391 MulOps.erase(MulOps.begin()+MulOp); 01392 InnerMul1 = getMulExpr(MulOps); 01393 } 01394 const SCEV *InnerMul2 = OtherMul->getOperand(OMulOp == 0); 01395 if (OtherMul->getNumOperands() != 2) { 01396 SmallVector<const SCEV *, 4> MulOps(OtherMul->op_begin(), 01397 OtherMul->op_end()); 01398 MulOps.erase(MulOps.begin()+OMulOp); 01399 InnerMul2 = getMulExpr(MulOps); 01400 } 01401 const SCEV *InnerMulSum = getAddExpr(InnerMul1,InnerMul2); 01402 const SCEV *OuterMul = getMulExpr(MulOpSCEV, InnerMulSum); 01403 if (Ops.size() == 2) return OuterMul; 01404 Ops.erase(Ops.begin()+Idx); 01405 Ops.erase(Ops.begin()+OtherMulIdx-1); 01406 Ops.push_back(OuterMul); 01407 return getAddExpr(Ops); 01408 } 01409 } 01410 } 01411 } 01412 01413 // If there are any add recurrences in the operands list, see if any other 01414 // added values are loop invariant. If so, we can fold them into the 01415 // recurrence. 01416 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scAddRecExpr) 01417 ++Idx; 01418 01419 // Scan over all recurrences, trying to fold loop invariants into them. 01420 for (; Idx < Ops.size() && isa<SCEVAddRecExpr>(Ops[Idx]); ++Idx) { 01421 // Scan all of the other operands to this add and add them to the vector if 01422 // they are loop invariant w.r.t. the recurrence. 01423 SmallVector<const SCEV *, 8> LIOps; 01424 const SCEVAddRecExpr *AddRec = cast<SCEVAddRecExpr>(Ops[Idx]); 01425 for (unsigned i = 0, e = Ops.size(); i != e; ++i) 01426 if (Ops[i]->isLoopInvariant(AddRec->getLoop())) { 01427 LIOps.push_back(Ops[i]); 01428 Ops.erase(Ops.begin()+i); 01429 --i; --e; 01430 } 01431 01432 // If we found some loop invariants, fold them into the recurrence. 01433 if (!LIOps.empty()) { 01434 // NLI + LI + {Start,+,Step} --> NLI + {LI+Start,+,Step} 01435 LIOps.push_back(AddRec->getStart()); 01436 01437 SmallVector<const SCEV *, 4> AddRecOps(AddRec->op_begin(), 01438 AddRec->op_end()); 01439 AddRecOps[0] = getAddExpr(LIOps); 01440 01441 const SCEV *NewRec = getAddRecExpr(AddRecOps, AddRec->getLoop()); 01442 // If all of the other operands were loop invariant, we are done. 01443 if (Ops.size() == 1) return NewRec; 01444 01445 // Otherwise, add the folded AddRec by the non-liv parts. 01446 for (unsigned i = 0;; ++i) 01447 if (Ops[i] == AddRec) { 01448 Ops[i] = NewRec; 01449 break; 01450 } 01451 return getAddExpr(Ops); 01452 } 01453 01454 // Okay, if there weren't any loop invariants to be folded, check to see if 01455 // there are multiple AddRec's with the same loop induction variable being 01456 // added together. If so, we can fold them. 01457 for (unsigned OtherIdx = Idx+1; 01458 OtherIdx < Ops.size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]);++OtherIdx) 01459 if (OtherIdx != Idx) { 01460 const SCEVAddRecExpr *OtherAddRec = cast<SCEVAddRecExpr>(Ops[OtherIdx]); 01461 if (AddRec->getLoop() == OtherAddRec->getLoop()) { 01462 // Other + {A,+,B} + {C,+,D} --> Other + {A+C,+,B+D} 01463 SmallVector<const SCEV *, 4> NewOps(AddRec->op_begin(), 01464 AddRec->op_end()); 01465 for (unsigned i = 0, e = OtherAddRec->getNumOperands(); i != e; ++i) { 01466 if (i >= NewOps.size()) { 01467 NewOps.insert(NewOps.end(), OtherAddRec->op_begin()+i, 01468 OtherAddRec->op_end()); 01469 break; 01470 } 01471 NewOps[i] = getAddExpr(NewOps[i], OtherAddRec->getOperand(i)); 01472 } 01473 const SCEV *NewAddRec = getAddRecExpr(NewOps, AddRec->getLoop()); 01474 01475 if (Ops.size() == 2) return NewAddRec; 01476 01477 Ops.erase(Ops.begin()+Idx); 01478 Ops.erase(Ops.begin()+OtherIdx-1); 01479 Ops.push_back(NewAddRec); 01480 return getAddExpr(Ops); 01481 } 01482 } 01483 01484 // Otherwise couldn't fold anything into this recurrence. Move onto the 01485 // next one. 01486 } 01487 01488 // Okay, it looks like we really DO need an add expr. Check to see if we 01489 // already have one, otherwise create a new one. 01490 FoldingSetNodeID ID; 01491 ID.AddInteger(scAddExpr); 01492 ID.AddInteger(Ops.size()); 01493 for (unsigned i = 0, e = Ops.size(); i != e; ++i) 01494 ID.AddPointer(Ops[i]); 01495 void *IP = 0; 01496 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; 01497 SCEV *S = SCEVAllocator.Allocate<SCEVAddExpr>(); 01498 new (S) SCEVAddExpr(ID, Ops); 01499 UniqueSCEVs.InsertNode(S, IP); 01500 return S; 01501 } 01502 01503 01504 /// getMulExpr - Get a canonical multiply expression, or something simpler if 01505 /// possible. 01506 const SCEV *ScalarEvolution::getMulExpr(SmallVectorImpl<const SCEV *> &Ops) { 01507 assert(!Ops.empty() && "Cannot get empty mul!"); 01508 #ifndef NDEBUG 01509 for (unsigned i = 1, e = Ops.size(); i != e; ++i) 01510 assert(getEffectiveSCEVType(Ops[i]->getType()) == 01511 getEffectiveSCEVType(Ops[0]->getType()) && 01512 "SCEVMulExpr operand types don't match!"); 01513 #endif 01514 01515 // Sort by complexity, this groups all similar expression types together. 01516 GroupByComplexity(Ops, LI); 01517 01518 // If there are any constants, fold them together. 01519 unsigned Idx = 0; 01520 if (const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) { 01521 01522 // C1*(C2+V) -> C1*C2 + C1*V 01523 if (Ops.size() == 2) 01524 if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Ops[1])) 01525 if (Add->getNumOperands() == 2 && 01526 isa<SCEVConstant>(Add->getOperand(0))) 01527 return getAddExpr(getMulExpr(LHSC, Add->getOperand(0)), 01528 getMulExpr(LHSC, Add->getOperand(1))); 01529 01530 01531 ++Idx; 01532 while (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) { 01533 // We found two constants, fold them together! 01534 ConstantInt *Fold = ConstantInt::get(getContext(), 01535 LHSC->getValue()->getValue() * 01536 RHSC->getValue()->getValue()); 01537 Ops[0] = getConstant(Fold); 01538 Ops.erase(Ops.begin()+1); // Erase the folded element 01539 if (Ops.size() == 1) return Ops[0]; 01540 LHSC = cast<SCEVConstant>(Ops[0]); 01541 } 01542 01543 // If we are left with a constant one being multiplied, strip it off. 01544 if (cast<SCEVConstant>(Ops[0])->getValue()->equalsInt(1)) { 01545 Ops.erase(Ops.begin()); 01546 --Idx; 01547 } else if (cast<SCEVConstant>(Ops[0])->getValue()->isZero()) { 01548 // If we have a multiply of zero, it will always be zero. 01549 return Ops[0]; 01550 } 01551 } 01552 01553 // Skip over the add expression until we get to a multiply. 01554 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scMulExpr) 01555 ++Idx; 01556 01557 if (Ops.size() == 1) 01558 return Ops[0]; 01559 01560 // If there are mul operands inline them all into this expression. 01561 if (Idx < Ops.size()) { 01562 bool DeletedMul = false; 01563 while (const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(Ops[Idx])) { 01564 // If we have an mul, expand the mul operands onto the end of the operands 01565 // list. 01566 Ops.insert(Ops.end(), Mul->op_begin(), Mul->op_end()); 01567 Ops.erase(Ops.begin()+Idx); 01568 DeletedMul = true; 01569 } 01570 01571 // If we deleted at least one mul, we added operands to the end of the list, 01572 // and they are not necessarily sorted. Recurse to resort and resimplify 01573 // any operands we just aquired. 01574 if (DeletedMul) 01575 return getMulExpr(Ops); 01576 } 01577 01578 // If there are any add recurrences in the operands list, see if any other 01579 // added values are loop invariant. If so, we can fold them into the 01580 // recurrence. 01581 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scAddRecExpr) 01582 ++Idx; 01583 01584 // Scan over all recurrences, trying to fold loop invariants into them. 01585 for (; Idx < Ops.size() && isa<SCEVAddRecExpr>(Ops[Idx]); ++Idx) { 01586 // Scan all of the other operands to this mul and add them to the vector if 01587 // they are loop invariant w.r.t. the recurrence. 01588 SmallVector<const SCEV *, 8> LIOps; 01589 const SCEVAddRecExpr *AddRec = cast<SCEVAddRecExpr>(Ops[Idx]); 01590 for (unsigned i = 0, e = Ops.size(); i != e; ++i) 01591 if (Ops[i]->isLoopInvariant(AddRec->getLoop())) { 01592 LIOps.push_back(Ops[i]); 01593 Ops.erase(Ops.begin()+i); 01594 --i; --e; 01595 } 01596 01597 // If we found some loop invariants, fold them into the recurrence. 01598 if (!LIOps.empty()) { 01599 // NLI * LI * {Start,+,Step} --> NLI * {LI*Start,+,LI*Step} 01600 SmallVector<const SCEV *, 4> NewOps; 01601 NewOps.reserve(AddRec->getNumOperands()); 01602 if (LIOps.size() == 1) { 01603 const SCEV *Scale = LIOps[0]; 01604 for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i) 01605 NewOps.push_back(getMulExpr(Scale, AddRec->getOperand(i))); 01606 } else { 01607 for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i) { 01608 SmallVector<const SCEV *, 4> MulOps(LIOps.begin(), LIOps.end()); 01609 MulOps.push_back(AddRec->getOperand(i)); 01610 NewOps.push_back(getMulExpr(MulOps)); 01611 } 01612 } 01613 01614 const SCEV *NewRec = getAddRecExpr(NewOps, AddRec->getLoop()); 01615 01616 // If all of the other operands were loop invariant, we are done. 01617 if (Ops.size() == 1) return NewRec; 01618 01619 // Otherwise, multiply the folded AddRec by the non-liv parts. 01620 for (unsigned i = 0;; ++i) 01621 if (Ops[i] == AddRec) { 01622 Ops[i] = NewRec; 01623 break; 01624 } 01625 return getMulExpr(Ops); 01626 } 01627 01628 // Okay, if there weren't any loop invariants to be folded, check to see if 01629 // there are multiple AddRec's with the same loop induction variable being 01630 // multiplied together. If so, we can fold them. 01631 for (unsigned OtherIdx = Idx+1; 01632 OtherIdx < Ops.size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]);++OtherIdx) 01633 if (OtherIdx != Idx) { 01634 const SCEVAddRecExpr *OtherAddRec = cast<SCEVAddRecExpr>(Ops[OtherIdx]); 01635 if (AddRec->getLoop() == OtherAddRec->getLoop()) { 01636 // F * G --> {A,+,B} * {C,+,D} --> {A*C,+,F*D + G*B + B*D} 01637 const SCEVAddRecExpr *F = AddRec, *G = OtherAddRec; 01638 const SCEV *NewStart = getMulExpr(F->getStart(), 01639 G->getStart()); 01640 const SCEV *B = F->getStepRecurrence(*this); 01641 const SCEV *D = G->getStepRecurrence(*this); 01642 const SCEV *NewStep = getAddExpr(getMulExpr(F, D), 01643 getMulExpr(G, B), 01644 getMulExpr(B, D)); 01645 const SCEV *NewAddRec = getAddRecExpr(NewStart, NewStep, 01646 F->getLoop()); 01647 if (Ops.size() == 2) return NewAddRec; 01648 01649 Ops.erase(Ops.begin()+Idx); 01650 Ops.erase(Ops.begin()+OtherIdx-1); 01651 Ops.push_back(NewAddRec); 01652 return getMulExpr(Ops); 01653 } 01654 } 01655 01656 // Otherwise couldn't fold anything into this recurrence. Move onto the 01657 // next one. 01658 } 01659 01660 // Okay, it looks like we really DO need an mul expr. Check to see if we 01661 // already have one, otherwise create a new one. 01662 FoldingSetNodeID ID; 01663 ID.AddInteger(scMulExpr); 01664 ID.AddInteger(Ops.size()); 01665 for (unsigned i = 0, e = Ops.size(); i != e; ++i) 01666 ID.AddPointer(Ops[i]); 01667 void *IP = 0; 01668 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; 01669 SCEV *S = SCEVAllocator.Allocate<SCEVMulExpr>(); 01670 new (S) SCEVMulExpr(ID, Ops); 01671 UniqueSCEVs.InsertNode(S, IP); 01672 return S; 01673 } 01674 01675 /// getUDivExpr - Get a canonical unsigned division expression, or something 01676 /// simpler if possible. 01677 const SCEV *ScalarEvolution::getUDivExpr(const SCEV *LHS, 01678 const SCEV *RHS) { 01679 assert(getEffectiveSCEVType(LHS->getType()) == 01680 getEffectiveSCEVType(RHS->getType()) && 01681 "SCEVUDivExpr operand types don't match!"); 01682 01683 if (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS)) { 01684 if (RHSC->getValue()->equalsInt(1)) 01685 return LHS; // X udiv 1 --> x 01686 if (RHSC->isZero()) 01687 return getIntegerSCEV(0, LHS->getType()); // value is undefined 01688 01689 // Determine if the division can be folded into the operands of 01690 // its operands. 01691 // TODO: Generalize this to non-constants by using known-bits information. 01692 const Type *Ty = LHS->getType(); 01693 unsigned LZ = RHSC->getValue()->getValue().countLeadingZeros(); 01694 unsigned MaxShiftAmt = getTypeSizeInBits(Ty) - LZ; 01695 // For non-power-of-two values, effectively round the value up to the 01696 // nearest power of two. 01697 if (!RHSC->getValue()->getValue().isPowerOf2()) 01698 ++MaxShiftAmt; 01699 const IntegerType *ExtTy = 01700 IntegerType::get(getContext(), getTypeSizeInBits(Ty) + MaxShiftAmt); 01701 // {X,+,N}/C --> {X/C,+,N/C} if safe and N/C can be folded. 01702 if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(LHS)) 01703 if (const SCEVConstant *Step = 01704 dyn_cast<SCEVConstant>(AR->getStepRecurrence(*this))) 01705 if (!Step->getValue()->getValue() 01706 .urem(RHSC->getValue()->getValue()) && 01707 getZeroExtendExpr(AR, ExtTy) == 01708 getAddRecExpr(getZeroExtendExpr(AR->getStart(), ExtTy), 01709 getZeroExtendExpr(Step, ExtTy), 01710 AR->getLoop())) { 01711 SmallVector<const SCEV *, 4> Operands; 01712 for (unsigned i = 0, e = AR->getNumOperands(); i != e; ++i) 01713 Operands.push_back(getUDivExpr(AR->getOperand(i), RHS)); 01714 return getAddRecExpr(Operands, AR->getLoop()); 01715 } 01716 // (A*B)/C --> A*(B/C) if safe and B/C can be folded. 01717 if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(LHS)) { 01718 SmallVector<const SCEV *, 4> Operands; 01719 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) 01720 Operands.push_back(getZeroExtendExpr(M->getOperand(i), ExtTy)); 01721 if (getZeroExtendExpr(M, ExtTy) == getMulExpr(Operands)) 01722 // Find an operand that's safely divisible. 01723 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) { 01724 const SCEV *Op = M->getOperand(i); 01725 const SCEV *Div = getUDivExpr(Op, RHSC); 01726 if (!isa<SCEVUDivExpr>(Div) && getMulExpr(Div, RHSC) == Op) { 01727 const SmallVectorImpl<const SCEV *> &MOperands = M->getOperands(); 01728 Operands = SmallVector<const SCEV *, 4>(MOperands.begin(), 01729 MOperands.end()); 01730 Operands[i] = Div; 01731 return getMulExpr(Operands); 01732 } 01733 } 01734 } 01735 // (A+B)/C --> (A/C + B/C) if safe and A/C and B/C can be folded. 01736 if (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(LHS)) { 01737 SmallVector<const SCEV *, 4> Operands; 01738 for (unsigned i = 0, e = A->getNumOperands(); i != e; ++i) 01739 Operands.push_back(getZeroExtendExpr(A->getOperand(i), ExtTy)); 01740 if (getZeroExtendExpr(A, ExtTy) == getAddExpr(Operands)) { 01741 Operands.clear(); 01742 for (unsigned i = 0, e = A->getNumOperands(); i != e; ++i) { 01743 const SCEV *Op = getUDivExpr(A->getOperand(i), RHS); 01744 if (isa<SCEVUDivExpr>(Op) || getMulExpr(Op, RHS) != A->getOperand(i)) 01745 break; 01746 Operands.push_back(Op); 01747 } 01748 if (Operands.size() == A->getNumOperands()) 01749 return getAddExpr(Operands); 01750 } 01751 } 01752 01753 // Fold if both operands are constant. 01754 if (const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(LHS)) { 01755 Constant *LHSCV = LHSC->getValue(); 01756 Constant *RHSCV = RHSC->getValue(); 01757 return getConstant(cast<ConstantInt>(ConstantExpr::getUDiv(LHSCV, 01758 RHSCV))); 01759 } 01760 } 01761 01762 FoldingSetNodeID ID; 01763 ID.AddInteger(scUDivExpr); 01764 ID.AddPointer(LHS); 01765 ID.AddPointer(RHS); 01766 void *IP = 0; 01767 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; 01768 SCEV *S = SCEVAllocator.Allocate<SCEVUDivExpr>(); 01769 new (S) SCEVUDivExpr(ID, LHS, RHS); 01770 UniqueSCEVs.InsertNode(S, IP); 01771 return S; 01772 } 01773 01774 01775 /// getAddRecExpr - Get an add recurrence expression for the specified loop. 01776 /// Simplify the expression as much as possible. 01777 const SCEV *ScalarEvolution::getAddRecExpr(const SCEV *Start, 01778 const SCEV *Step, const Loop *L) { 01779 SmallVector<const SCEV *, 4> Operands; 01780 Operands.push_back(Start); 01781 if (const SCEVAddRecExpr *StepChrec = dyn_cast<SCEVAddRecExpr>(Step)) 01782 if (StepChrec->getLoop() == L) { 01783 Operands.insert(Operands.end(), StepChrec->op_begin(), 01784 StepChrec->op_end()); 01785 return getAddRecExpr(Operands, L); 01786 } 01787 01788 Operands.push_back(Step); 01789 return getAddRecExpr(Operands, L); 01790 } 01791 01792 /// getAddRecExpr - Get an add recurrence expression for the specified loop. 01793 /// Simplify the expression as much as possible. 01794 const SCEV * 01795 ScalarEvolution::getAddRecExpr(SmallVectorImpl<const SCEV *> &Operands, 01796 const Loop *L) { 01797 if (Operands.size() == 1) return Operands[0]; 01798 #ifndef NDEBUG 01799 for (unsigned i = 1, e = Operands.size(); i != e; ++i) 01800 assert(getEffectiveSCEVType(Operands[i]->getType()) == 01801 getEffectiveSCEVType(Operands[0]->getType()) && 01802 "SCEVAddRecExpr operand types don't match!"); 01803 #endif 01804 01805 if (Operands.back()->isZero()) { 01806 Operands.pop_back(); 01807 return getAddRecExpr(Operands, L); // {X,+,0} --> X 01808 } 01809 01810 // Canonicalize nested AddRecs in by nesting them in order of loop depth. 01811 if (const SCEVAddRecExpr *NestedAR = dyn_cast<SCEVAddRecExpr>(Operands[0])) { 01812 const Loop* NestedLoop = NestedAR->getLoop(); 01813 if (L->getLoopDepth() < NestedLoop->getLoopDepth()) { 01814 SmallVector<const SCEV *, 4> NestedOperands(NestedAR->op_begin(), 01815 NestedAR->op_end()); 01816 Operands[0] = NestedAR->getStart(); 01817 // AddRecs require their operands be loop-invariant with respect to their 01818 // loops. Don't perform this transformation if it would break this 01819 // requirement. 01820 bool AllInvariant = true; 01821 for (unsigned i = 0, e = Operands.size(); i != e; ++i) 01822 if (!Operands[i]->isLoopInvariant(L)) { 01823 AllInvariant = false; 01824 break; 01825 } 01826 if (AllInvariant) { 01827 NestedOperands[0] = getAddRecExpr(Operands, L); 01828 AllInvariant = true; 01829 for (unsigned i = 0, e = NestedOperands.size(); i != e; ++i) 01830 if (!NestedOperands[i]->isLoopInvariant(NestedLoop)) { 01831 AllInvariant = false; 01832 break; 01833 } 01834 if (AllInvariant) 01835 // Ok, both add recurrences are valid after the transformation. 01836 return getAddRecExpr(NestedOperands, NestedLoop); 01837 } 01838 // Reset Operands to its original state. 01839 Operands[0] = NestedAR; 01840 } 01841 } 01842 01843 FoldingSetNodeID ID; 01844 ID.AddInteger(scAddRecExpr); 01845 ID.AddInteger(Operands.size()); 01846 for (unsigned i = 0, e = Operands.size(); i != e; ++i) 01847 ID.AddPointer(Operands[i]); 01848 ID.AddPointer(L); 01849 void *IP = 0; 01850 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; 01851 SCEV *S = SCEVAllocator.Allocate<SCEVAddRecExpr>(); 01852 new (S) SCEVAddRecExpr(ID, Operands, L); 01853 UniqueSCEVs.InsertNode(S, IP); 01854 return S; 01855 } 01856 01857 const SCEV *ScalarEvolution::getSMaxExpr(const SCEV *LHS, 01858 const SCEV *RHS) { 01859 SmallVector<const SCEV *, 2> Ops; 01860 Ops.push_back(LHS); 01861 Ops.push_back(RHS); 01862 return getSMaxExpr(Ops); 01863 } 01864 01865 const SCEV * 01866 ScalarEvolution::getSMaxExpr(SmallVectorImpl<const SCEV *> &Ops) { 01867 assert(!Ops.empty() && "Cannot get empty smax!"); 01868 if (Ops.size() == 1) return Ops[0]; 01869 #ifndef NDEBUG 01870 for (unsigned i = 1, e = Ops.size(); i != e; ++i) 01871 assert(getEffectiveSCEVType(Ops[i]->getType()) == 01872 getEffectiveSCEVType(Ops[0]->getType()) && 01873 "SCEVSMaxExpr operand types don't match!"); 01874 #endif 01875 01876 // Sort by complexity, this groups all similar expression types together. 01877 GroupByComplexity(Ops, LI); 01878 01879 // If there are any constants, fold them together. 01880 unsigned Idx = 0; 01881 if (const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) { 01882 ++Idx; 01883 assert(Idx < Ops.size()); 01884 while (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) { 01885 // We found two constants, fold them together! 01886 ConstantInt *Fold = ConstantInt::get(getContext(), 01887 APIntOps::smax(LHSC->getValue()->getValue(), 01888 RHSC->getValue()->getValue())); 01889 Ops[0] = getConstant(Fold); 01890 Ops.erase(Ops.begin()+1); // Erase the folded element 01891 if (Ops.size() == 1) return Ops[0]; 01892 LHSC = cast<SCEVConstant>(Ops[0]); 01893 } 01894 01895 // If we are left with a constant minimum-int, strip it off. 01896 if (cast<SCEVConstant>(Ops[0])->getValue()->isMinValue(true)) { 01897 Ops.erase(Ops.begin()); 01898 --Idx; 01899 } else if (cast<SCEVConstant>(Ops[0])->getValue()->isMaxValue(true)) { 01900 // If we have an smax with a constant maximum-int, it will always be 01901 // maximum-int. 01902 return Ops[0]; 01903 } 01904 } 01905 01906 if (Ops.size() == 1) return Ops[0]; 01907 01908 // Find the first SMax 01909 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scSMaxExpr) 01910 ++Idx; 01911 01912 // Check to see if one of the operands is an SMax. If so, expand its operands 01913 // onto our operand list, and recurse to simplify. 01914 if (Idx < Ops.size()) { 01915 bool DeletedSMax = false; 01916 while (const SCEVSMaxExpr *SMax = dyn_cast<SCEVSMaxExpr>(Ops[Idx])) { 01917 Ops.insert(Ops.end(), SMax->op_begin(), SMax->op_end()); 01918 Ops.erase(Ops.begin()+Idx); 01919 DeletedSMax = true; 01920 } 01921 01922 if (DeletedSMax) 01923 return getSMaxExpr(Ops); 01924 } 01925 01926 // Okay, check to see if the same value occurs in the operand list twice. If 01927 // so, delete one. Since we sorted the list, these values are required to 01928 // be adjacent. 01929 for (unsigned i = 0, e = Ops.size()-1; i != e; ++i) 01930 if (Ops[i] == Ops[i+1]) { // X smax Y smax Y --> X smax Y 01931 Ops.erase(Ops.begin()+i, Ops.begin()+i+1); 01932 --i; --e; 01933 } 01934 01935 if (Ops.size() == 1) return Ops[0]; 01936 01937 assert(!Ops.empty() && "Reduced smax down to nothing!"); 01938 01939 // Okay, it looks like we really DO need an smax expr. Check to see if we 01940 // already have one, otherwise create a new one. 01941 FoldingSetNodeID ID; 01942 ID.AddInteger(scSMaxExpr); 01943 ID.AddInteger(Ops.size()); 01944 for (unsigned i = 0, e = Ops.size(); i != e; ++i) 01945 ID.AddPointer(Ops[i]); 01946 void *IP = 0; 01947 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; 01948 SCEV *S = SCEVAllocator.Allocate<SCEVSMaxExpr>(); 01949 new (S) SCEVSMaxExpr(ID, Ops); 01950 UniqueSCEVs.InsertNode(S, IP); 01951 return S; 01952 } 01953 01954 const SCEV *ScalarEvolution::getUMaxExpr(const SCEV *LHS, 01955 const SCEV *RHS) { 01956 SmallVector<const SCEV *, 2> Ops; 01957 Ops.push_back(LHS); 01958 Ops.push_back(RHS); 01959 return getUMaxExpr(Ops); 01960 } 01961 01962 const SCEV * 01963 ScalarEvolution::getUMaxExpr(SmallVectorImpl<const SCEV *> &Ops) { 01964 assert(!Ops.empty() && "Cannot get empty umax!"); 01965 if (Ops.size() == 1) return Ops[0]; 01966 #ifndef NDEBUG 01967 for (unsigned i = 1, e = Ops.size(); i != e; ++i) 01968 assert(getEffectiveSCEVType(Ops[i]->getType()) == 01969 getEffectiveSCEVType(Ops[0]->getType()) && 01970 "SCEVUMaxExpr operand types don't match!"); 01971 #endif 01972 01973 // Sort by complexity, this groups all similar expression types together. 01974 GroupByComplexity(Ops, LI); 01975 01976 // If there are any constants, fold them together. 01977 unsigned Idx = 0; 01978 if (const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) { 01979 ++Idx; 01980 assert(Idx < Ops.size()); 01981 while (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) { 01982 // We found two constants, fold them together! 01983 ConstantInt *Fold = ConstantInt::get(getContext(), 01984 APIntOps::umax(LHSC->getValue()->getValue(), 01985 RHSC->getValue()->getValue())); 01986 Ops[0] = getConstant(Fold); 01987 Ops.erase(Ops.begin()+1); // Erase the folded element 01988 if (Ops.size() == 1) return Ops[0]; 01989 LHSC = cast<SCEVConstant>(Ops[0]); 01990 } 01991 01992 // If we are left with a constant minimum-int, strip it off. 01993 if (cast<SCEVConstant>(Ops[0])->getValue()->isMinValue(false)) { 01994 Ops.erase(Ops.begin()); 01995 --Idx; 01996 } else if (cast<SCEVConstant>(Ops[0])->getValue()->isMaxValue(false)) { 01997 // If we have an umax with a constant maximum-int, it will always be 01998 // maximum-int. 01999 return Ops[0]; 02000 } 02001 } 02002 02003 if (Ops.size() == 1) return Ops[0]; 02004 02005 // Find the first UMax 02006 while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scUMaxExpr) 02007 ++Idx; 02008 02009 // Check to see if one of the operands is a UMax. If so, expand its operands 02010 // onto our operand list, and recurse to simplify. 02011 if (Idx < Ops.size()) { 02012 bool DeletedUMax = false; 02013 while (const SCEVUMaxExpr *UMax = dyn_cast<SCEVUMaxExpr>(Ops[Idx])) { 02014 Ops.insert(Ops.end(), UMax->op_begin(), UMax->op_end()); 02015 Ops.erase(Ops.begin()+Idx); 02016 DeletedUMax = true; 02017 } 02018 02019 if (DeletedUMax) 02020 return getUMaxExpr(Ops); 02021 } 02022 02023 // Okay, check to see if the same value occurs in the operand list twice. If 02024 // so, delete one. Since we sorted the list, these values are required to 02025 // be adjacent. 02026 for (unsigned i = 0, e = Ops.size()-1; i != e; ++i) 02027 if (Ops[i] == Ops[i+1]) { // X umax Y umax Y --> X umax Y 02028 Ops.erase(Ops.begin()+i, Ops.begin()+i+1); 02029 --i; --e; 02030 } 02031 02032 if (Ops.size() == 1) return Ops[0]; 02033 02034 assert(!Ops.empty() && "Reduced umax down to nothing!"); 02035 02036 // Okay, it looks like we really DO need a umax expr. Check to see if we 02037 // already have one, otherwise create a new one. 02038 FoldingSetNodeID ID; 02039 ID.AddInteger(scUMaxExpr); 02040 ID.AddInteger(Ops.size()); 02041 for (unsigned i = 0, e = Ops.size(); i != e; ++i) 02042 ID.AddPointer(Ops[i]); 02043 void *IP = 0; 02044 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; 02045 SCEV *S = SCEVAllocator.Allocate<SCEVUMaxExpr>(); 02046 new (S) SCEVUMaxExpr(ID, Ops); 02047 UniqueSCEVs.InsertNode(S, IP); 02048 return S; 02049 } 02050 02051 const SCEV *ScalarEvolution::getSMinExpr(const SCEV *LHS, 02052 const SCEV *RHS) { 02053 // ~smax(~x, ~y) == smin(x, y). 02054 return getNotSCEV(getSMaxExpr(getNotSCEV(LHS), getNotSCEV(RHS))); 02055 } 02056 02057 const SCEV *ScalarEvolution::getUMinExpr(const SCEV *LHS, 02058 const SCEV *RHS) { 02059 // ~umax(~x, ~y) == umin(x, y) 02060 return getNotSCEV(getUMaxExpr(getNotSCEV(LHS), getNotSCEV(RHS))); 02061 } 02062 02063 const SCEV *ScalarEvolution::getFieldOffsetExpr(const StructType *STy, 02064 unsigned FieldNo) { 02065 // If we have TargetData we can determine the constant offset. 02066 if (TD) { 02067 const Type *IntPtrTy = TD->getIntPtrType(getContext()); 02068 const StructLayout &SL = *TD->getStructLayout(STy); 02069 uint64_t Offset = SL.getElementOffset(FieldNo); 02070 return getIntegerSCEV(Offset, IntPtrTy); 02071 } 02072 02073 // Field 0 is always at offset 0. 02074 if (FieldNo == 0) { 02075 const Type *Ty = getEffectiveSCEVType(PointerType::getUnqual(STy)); 02076 return getIntegerSCEV(0, Ty); 02077 } 02078 02079 // Okay, it looks like we really DO need an offsetof expr. Check to see if we 02080 // already have one, otherwise create a new one. 02081 FoldingSetNodeID ID; 02082 ID.AddInteger(scFieldOffset); 02083 ID.AddPointer(STy); 02084 ID.AddInteger(FieldNo); 02085 void *IP = 0; 02086 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; 02087 SCEV *S = SCEVAllocator.Allocate<SCEVFieldOffsetExpr>(); 02088 const Type *Ty = getEffectiveSCEVType(PointerType::getUnqual(STy)); 02089 new (S) SCEVFieldOffsetExpr(ID, Ty, STy, FieldNo); 02090 UniqueSCEVs.InsertNode(S, IP); 02091 return S; 02092 } 02093 02094 const SCEV *ScalarEvolution::getAllocSizeExpr(const Type *AllocTy) { 02095 // If we have TargetData we can determine the constant size. 02096 if (TD && AllocTy->isSized()) { 02097 const Type *IntPtrTy = TD->getIntPtrType(getContext()); 02098 return getIntegerSCEV(TD->getTypeAllocSize(AllocTy), IntPtrTy); 02099 } 02100 02101 // Expand an array size into the element size times the number 02102 // of elements. 02103 if (const ArrayType *ATy = dyn_cast<ArrayType>(AllocTy)) { 02104 const SCEV *E = getAllocSizeExpr(ATy->getElementType()); 02105 return getMulExpr( 02106 E, getConstant(ConstantInt::get(cast<IntegerType>(E->getType()), 02107 ATy->getNumElements()))); 02108 } 02109 02110 // Expand a vector size into the element size times the number 02111 // of elements. 02112 if (const VectorType *VTy = dyn_cast<VectorType>(AllocTy)) { 02113 const SCEV *E = getAllocSizeExpr(VTy->getElementType()); 02114 return getMulExpr( 02115 E, getConstant(ConstantInt::get(cast<IntegerType>(E->getType()), 02116 VTy->getNumElements()))); 02117 } 02118 02119 // Okay, it looks like we really DO need a sizeof expr. Check to see if we 02120 // already have one, otherwise create a new one. 02121 FoldingSetNodeID ID; 02122 ID.AddInteger(scAllocSize); 02123 ID.AddPointer(AllocTy); 02124 void *IP = 0; 02125 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; 02126 SCEV *S = SCEVAllocator.Allocate<SCEVAllocSizeExpr>(); 02127 const Type *Ty = getEffectiveSCEVType(PointerType::getUnqual(AllocTy)); 02128 new (S) SCEVAllocSizeExpr(ID, Ty, AllocTy); 02129 UniqueSCEVs.InsertNode(S, IP); 02130 return S; 02131 } 02132 02133 const SCEV *ScalarEvolution::getUnknown(Value *V) { 02134 // Don't attempt to do anything other than create a SCEVUnknown object 02135 // here. createSCEV only calls getUnknown after checking for all other 02136 // interesting possibilities, and any other code that calls getUnknown 02137 // is doing so in order to hide a value from SCEV canonicalization. 02138 02139 FoldingSetNodeID ID; 02140 ID.AddInteger(scUnknown); 02141 ID.AddPointer(V); 02142 void *IP = 0; 02143 if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; 02144 SCEV *S = SCEVAllocator.Allocate<SCEVUnknown>(); 02145 new (S) SCEVUnknown(ID, V); 02146 UniqueSCEVs.InsertNode(S, IP); 02147 return S; 02148 } 02149 02150 //===----------------------------------------------------------------------===// 02151 // Basic SCEV Analysis and PHI Idiom Recognition Code 02152 // 02153 02154 /// isSCEVable - Test if values of the given type are analyzable within 02155 /// the SCEV framework. This primarily includes integer types, and it 02156 /// can optionally include pointer types if the ScalarEvolution class 02157 /// has access to target-specific information. 02158 bool ScalarEvolution::isSCEVable(const Type *Ty) const { 02159 // Integers and pointers are always SCEVable. 02160 return Ty->isInteger() || isa<PointerType>(Ty); 02161 } 02162 02163 /// getTypeSizeInBits - Return the size in bits of the specified type, 02164 /// for which isSCEVable must return true. 02165 uint64_t ScalarEvolution::getTypeSizeInBits(const Type *Ty) const { 02166 assert(isSCEVable(Ty) && "Type is not SCEVable!"); 02167 02168 // If we have a TargetData, use it! 02169 if (TD) 02170 return TD->getTypeSizeInBits(Ty); 02171 02172 // Integer types have fixed sizes. 02173 if (Ty->isInteger()) 02174 return Ty->getPrimitiveSizeInBits(); 02175 02176 // The only other support type is pointer. Without TargetData, conservatively 02177 // assume pointers are 64-bit. 02178 assert(isa<PointerType>(Ty) && "isSCEVable permitted a non-SCEVable type!"); 02179 return 64; 02180 } 02181 02182 /// getEffectiveSCEVType - Return a type with the same bitwidth as 02183 /// the given type and which represents how SCEV will treat the given 02184 /// type, for which isSCEVable must return true. For pointer types, 02185 /// this is the pointer-sized integer type. 02186 const Type *ScalarEvolution::getEffectiveSCEVType(const Type *Ty) const { 02187 assert(isSCEVable(Ty) && "Type is not SCEVable!"); 02188 02189 if (Ty->isInteger()) 02190 return Ty; 02191 02192 // The only other support type is pointer. 02193 assert(isa<PointerType>(Ty) && "Unexpected non-pointer non-integer type!"); 02194 if (TD) return TD->getIntPtrType(getContext()); 02195 02196 // Without TargetData, conservatively assume pointers are 64-bit. 02197 return Type::getInt64Ty(getContext()); 02198 } 02199 02200 const SCEV *ScalarEvolution::getCouldNotCompute() { 02201 return &CouldNotCompute; 02202 } 02203 02204 /// getSCEV - Return an existing SCEV if it exists, otherwise analyze the 02205 /// expression and create a new one. 02206 const SCEV *ScalarEvolution::getSCEV(Value *V) { 02207 assert(isSCEVable(V->getType()) && "Value is not SCEVable!"); 02208 02209 std::map<SCEVCallbackVH, const SCEV *>::iterator I = Scalars.find(V); 02210 if (I != Scalars.end()) return I->second; 02211 const SCEV *S = createSCEV(V); 02212 Scalars.insert(std::make_pair(SCEVCallbackVH(V, this), S)); 02213 return S; 02214 } 02215 02216 /// getIntegerSCEV - Given a SCEVable type, create a constant for the 02217 /// specified signed integer value and return a SCEV for the constant. 02218 const SCEV *ScalarEvolution::getIntegerSCEV(int Val, const Type *Ty) { 02219 const IntegerType *ITy = cast<IntegerType>(getEffectiveSCEVType(Ty)); 02220 return getConstant(ConstantInt::get(ITy, Val)); 02221 } 02222 02223 /// getNegativeSCEV - Return a SCEV corresponding to -V = -1*V 02224 /// 02225 const SCEV *ScalarEvolution::getNegativeSCEV(const SCEV *V) { 02226 if (const SCEVConstant *VC = dyn_cast<SCEVConstant>(V)) 02227 return getConstant( 02228 cast<ConstantInt>(ConstantExpr::getNeg(VC->getValue()))); 02229 02230 const Type *Ty = V->getType(); 02231 Ty = getEffectiveSCEVType(Ty); 02232 return getMulExpr(V, 02233 getConstant(cast<ConstantInt>(Constant::getAllOnesValue(Ty)))); 02234 } 02235 02236 /// getNotSCEV - Return a SCEV corresponding to ~V = -1-V 02237 const SCEV *ScalarEvolution::getNotSCEV(const SCEV *V) { 02238 if (const SCEVConstant *VC = dyn_cast<SCEVConstant>(V)) 02239 return getConstant( 02240 cast<ConstantInt>(ConstantExpr::getNot(VC->getValue()))); 02241 02242 const Type *Ty = V->getType(); 02243 Ty = getEffectiveSCEVType(Ty); 02244 const SCEV *AllOnes = 02245 getConstant(cast<ConstantInt>(Constant::getAllOnesValue(Ty))); 02246 return getMinusSCEV(AllOnes, V); 02247 } 02248 02249 /// getMinusSCEV - Return a SCEV corresponding to LHS - RHS. 02250 /// 02251 const SCEV *ScalarEvolution::getMinusSCEV(const SCEV *LHS, 02252 const SCEV *RHS) { 02253 // X - Y --> X + -Y 02254 return getAddExpr(LHS, getNegativeSCEV(RHS)); 02255 } 02256 02257 /// getTruncateOrZeroExtend - Return a SCEV corresponding to a conversion of the 02258 /// input value to the specified type. If the type must be extended, it is zero 02259 /// extended. 02260 const SCEV * 02261 ScalarEvolution::getTruncateOrZeroExtend(const SCEV *V, 02262 const Type *Ty) { 02263 const Type *SrcTy = V->getType(); 02264 assert((SrcTy->isInteger() || isa<PointerType>(SrcTy)) && 02265 (Ty->isInteger() || isa<PointerType>(Ty)) && 02266 "Cannot truncate or zero extend with non-integer arguments!"); 02267 if (getTypeSizeInBits(SrcTy) == getTypeSizeInBits(Ty)) 02268 return V; // No conversion 02269 if (getTypeSizeInBits(SrcTy) > getTypeSizeInBits(Ty)) 02270 return getTruncateExpr(V, Ty); 02271 return getZeroExtendExpr(V, Ty); 02272 } 02273 02274 /// getTruncateOrSignExtend - Return a SCEV corresponding to a conversion of the 02275 /// input value to the specified type. If the type must be extended, it is sign 02276 /// extended. 02277 const SCEV * 02278 ScalarEvolution::getTruncateOrSignExtend(const SCEV *V, 02279 const Type *Ty) { 02280 const Type *SrcTy = V->getType(); 02281 assert((SrcTy->isInteger() || isa<PointerType>(SrcTy)) && 02282 (Ty->isInteger() || isa<PointerType>(Ty)) && 02283 "Cannot truncate or zero extend with non-integer arguments!"); 02284 if (getTypeSizeInBits(SrcTy) == getTypeSizeInBits(Ty)) 02285 return V; // No conversion 02286 if (getTypeSizeInBits(SrcTy) > getTypeSizeInBits(Ty)) 02287 return getTruncateExpr(V, Ty); 02288 return getSignExtendExpr(V, Ty); 02289 } 02290 02291 /// getNoopOrZeroExtend - Return a SCEV corresponding to a conversion of the 02292 /// input value to the specified type. If the type must be extended, it is zero 02293 /// extended. The conversion must not be narrowing. 02294 const SCEV * 02295 ScalarEvolution::getNoopOrZeroExtend(const SCEV *V, const Type *Ty) { 02296 const Type *SrcTy = V->getType(); 02297 assert((SrcTy->isInteger() || isa<PointerType>(SrcTy)) && 02298 (Ty->isInteger() || isa<PointerType>(Ty)) && 02299 "Cannot noop or zero extend with non-integer arguments!"); 02300 assert(getTypeSizeInBits(SrcTy) <= getTypeSizeInBits(Ty) && 02301 "getNoopOrZeroExtend cannot truncate!"); 02302 if (getTypeSizeInBits(SrcTy) == getTypeSizeInBits(Ty)) 02303 return V; // No conversion 02304 return getZeroExtendExpr(V, Ty); 02305 } 02306 02307 /// getNoopOrSignExtend - Return a SCEV corresponding to a conversion of the 02308 /// input value to the specified type. If the type must be extended, it is sign 02309 /// extended. The conversion must not be narrowing. 02310 const SCEV * 02311 ScalarEvolution::getNoopOrSignExtend(const SCEV *V, const Type *Ty) { 02312 const Type *SrcTy = V->getType(); 02313 assert((SrcTy->isInteger() || isa<PointerType>(SrcTy)) && 02314 (Ty->isInteger() || isa<PointerType>(Ty)) && 02315 "Cannot noop or sign extend with non-integer arguments!"); 02316 assert(getTypeSizeInBits(SrcTy) <= getTypeSizeInBits(Ty) && 02317 "getNoopOrSignExtend cannot truncate!"); 02318 if (getTypeSizeInBits(SrcTy) == getTypeSizeInBits(Ty)) 02319 return V; // No conversion 02320 return getSignExtendExpr(V, Ty); 02321 } 02322 02323 /// getNoopOrAnyExtend - Return a SCEV corresponding to a conversion of 02324 /// the input value to the specified type. If the type must be extended, 02325 /// it is extended with unspecified bits. The conversion must not be 02326 /// narrowing. 02327 const SCEV * 02328 ScalarEvolution::getNoopOrAnyExtend(const SCEV *V, const Type *Ty) { 02329 const Type *SrcTy = V->getType(); 02330 assert((SrcTy->isInteger() || isa<PointerType>(SrcTy)) && 02331 (Ty->isInteger() || isa<PointerType>(Ty)) && 02332 "Cannot noop or any extend with non-integer arguments!"); 02333 assert(getTypeSizeInBits(SrcTy) <= getTypeSizeInBits(Ty) && 02334 "getNoopOrAnyExtend cannot truncate!"); 02335 if (getTypeSizeInBits(SrcTy) == getTypeSizeInBits(Ty)) 02336 return V; // No conversion 02337 return getAnyExtendExpr(V, Ty); 02338 } 02339 02340 /// getTruncateOrNoop - Return a SCEV corresponding to a conversion of the 02341 /// input value to the specified type. The conversion must not be widening. 02342 const SCEV * 02343 ScalarEvolution::getTruncateOrNoop(const SCEV *V, const Type *Ty) { 02344 const Type *SrcTy = V->getType(); 02345 assert((SrcTy->isInteger() || isa<PointerType>(SrcTy)) && 02346 (Ty->isInteger() || isa<PointerType>(Ty)) && 02347 "Cannot truncate or noop with non-integer arguments!"); 02348 assert(getTypeSizeInBits(SrcTy) >= getTypeSizeInBits(Ty) && 02349 "getTruncateOrNoop cannot extend!"); 02350 if (getTypeSizeInBits(SrcTy) == getTypeSizeInBits(Ty)) 02351 return V; // No conversion 02352 return getTruncateExpr(V, Ty); 02353 } 02354 02355 /// getUMaxFromMismatchedTypes - Promote the operands to the wider of 02356 /// the types using zero-extension, and then perform a umax operation 02357 /// with them. 02358 const SCEV *ScalarEvolution::getUMaxFromMismatchedTypes(const SCEV *LHS, 02359 const SCEV *RHS) { 02360 const SCEV *PromotedLHS = LHS; 02361 const SCEV *PromotedRHS = RHS; 02362 02363 if (getTypeSizeInBits(LHS->getType()) > getTypeSizeInBits(RHS->getType())) 02364 PromotedRHS = getZeroExtendExpr(RHS, LHS->getType()); 02365 else 02366 PromotedLHS = getNoopOrZeroExtend(LHS, RHS->getType()); 02367 02368 return getUMaxExpr(PromotedLHS, PromotedRHS); 02369 } 02370 02371 /// getUMinFromMismatchedTypes - Promote the operands to the wider of 02372 /// the types using zero-extension, and then perform a umin operation 02373 /// with them. 02374 const SCEV *ScalarEvolution::getUMinFromMismatchedTypes(const SCEV *LHS, 02375 const SCEV *RHS) { 02376 const SCEV *PromotedLHS = LHS; 02377 const SCEV *PromotedRHS = RHS; 02378 02379 if (getTypeSizeInBits(LHS->getType()) > getTypeSizeInBits(RHS->getType())) 02380 PromotedRHS = getZeroExtendExpr(RHS, LHS->getType()); 02381 else 02382 PromotedLHS = getNoopOrZeroExtend(LHS, RHS->getType()); 02383 02384 return getUMinExpr(PromotedLHS, PromotedRHS); 02385 } 02386 02387 /// PushDefUseChildren - Push users of the given Instruction 02388 /// onto the given Worklist. 02389 static void 02390 PushDefUseChildren(Instruction *I, 02391 SmallVectorImpl<Instruction *> &Worklist) { 02392 // Push the def-use children onto the Worklist stack. 02393 for (Value::use_iterator UI = I->use_begin(), UE = I->use_end(); 02394 UI != UE; ++UI) 02395 Worklist.push_back(cast<Instruction>(UI)); 02396 } 02397 02398 /// ForgetSymbolicValue - This looks up computed SCEV values for all 02399 /// instructions that depend on the given instruction and removes them from 02400 /// the Scalars map if they reference SymName. This is used during PHI 02401 /// resolution. 02402 void 02403 ScalarEvolution::ForgetSymbolicName(Instruction *I, const SCEV *SymName) { 02404 SmallVector<Instruction *, 16> Worklist; 02405 PushDefUseChildren(I, Worklist); 02406 02407 SmallPtrSet<Instruction *, 8> Visited; 02408 Visited.insert(I); 02409 while (!Worklist.empty()) { 02410 Instruction *I = Worklist.pop_back_val(); 02411 if (!Visited.insert(I)) continue; 02412 02413 std::map<SCEVCallbackVH, const SCEV*>::iterator It = 02414 Scalars.find(static_cast<Value *>(I)); 02415 if (It != Scalars.end()) { 02416 // Short-circuit the def-use traversal if the symbolic name 02417 // ceases to appear in expressions. 02418 if (!It->second->hasOperand(SymName)) 02419 continue; 02420 02421 // SCEVUnknown for a PHI either means that it has an unrecognized 02422 // structure, or it's a PHI that's in the progress of being computed 02423 // by createNodeForPHI. In the former case, additional loop trip 02424 // count information isn't going to change anything. In the later 02425 // case, createNodeForPHI will perform the necessary updates on its 02426 // own when it gets to that point. 02427 if (!isa<PHINode>(I) || !isa<SCEVUnknown>(It->second)) 02428 Scalars.erase(It); 02429 ValuesAtScopes.erase(I); 02430 } 02431 02432 PushDefUseChildren(I, Worklist); 02433 } 02434 } 02435 02436 /// createNodeForPHI - PHI nodes have two cases. Either the PHI node exists in 02437 /// a loop header, making it a potential recurrence, or it doesn't. 02438 /// 02439 const SCEV *ScalarEvolution::createNodeForPHI(PHINode *PN) { 02440 if (PN->getNumIncomingValues() == 2) // The loops have been canonicalized. 02441 if (const Loop *L = LI->getLoopFor(PN->getParent())) 02442 if (L->getHeader() == PN->getParent()) { 02443 // If it lives in the loop header, it has two incoming values, one 02444 // from outside the loop, and one from inside. 02445 unsigned IncomingEdge = L->contains(PN->getIncomingBlock(0)); 02446 unsigned BackEdge = IncomingEdge^1; 02447 02448 // While we are analyzing this PHI node, handle its value symbolically. 02449 const SCEV *SymbolicName = getUnknown(PN); 02450 assert(Scalars.find(PN) == Scalars.end() && 02451 "PHI node already processed?"); 02452 Scalars.insert(std::make_pair(SCEVCallbackVH(PN, this), SymbolicName)); 02453 02454 // Using this symbolic name for the PHI, analyze the value coming around 02455 // the back-edge. 02456 Value *BEValueV = PN->getIncomingValue(BackEdge); 02457 const SCEV *BEValue = getSCEV(BEValueV); 02458 02459 // NOTE: If BEValue is loop invariant, we know that the PHI node just 02460 // has a special value for the first iteration of the loop. 02461 02462 // If the value coming around the backedge is an add with the symbolic 02463 // value we just inserted, then we found a simple induction variable! 02464 if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(BEValue)) { 02465 // If there is a single occurrence of the symbolic value, replace it 02466 // with a recurrence. 02467 unsigned FoundIndex = Add->getNumOperands(); 02468 for (unsigned i = 0, e = Add->getNumOperands(); i != e; ++i) 02469 if (Add->getOperand(i) == SymbolicName) 02470 if (FoundIndex == e) { 02471 FoundIndex = i; 02472 break; 02473 } 02474 02475 if (FoundIndex != Add->getNumOperands()) { 02476 // Create an add with everything but the specified operand. 02477 SmallVector<const SCEV *, 8> Ops; 02478 for (unsigned i = 0, e = Add->getNumOperands(); i != e; ++i) 02479 if (i != FoundIndex) 02480 Ops.push_back(Add->getOperand(i)); 02481 const SCEV *Accum = getAddExpr(Ops); 02482 02483 // This is not a valid addrec if the step amount is varying each 02484 // loop iteration, but is not itself an addrec in this loop. 02485 if (Accum->isLoopInvariant(L) || 02486 (isa<SCEVAddRecExpr>(Accum) && 02487 cast<SCEVAddRecExpr>(Accum)->getLoop() == L)) { 02488 const SCEV *StartVal = 02489 getSCEV(PN->getIncomingValue(IncomingEdge)); 02490 const SCEVAddRecExpr *PHISCEV = 02491 cast<SCEVAddRecExpr>(getAddRecExpr(StartVal, Accum, L)); 02492 02493 // If the increment doesn't overflow, then neither the addrec nor the 02494 // post-increment will overflow. 02495 if (const AddOperator *OBO = dyn_cast<AddOperator>(BEValueV)) 02496 if (OBO->getOperand(0) == PN && 02497 getSCEV(OBO->getOperand(1)) == 02498 PHISCEV->getStepRecurrence(*this)) { 02499 const SCEVAddRecExpr *PostInc = PHISCEV->getPostIncExpr(*this); 02500 if (OBO->hasNoUnsignedWrap()) { 02501 const_cast<SCEVAddRecExpr *>(PHISCEV) 02502 ->setHasNoUnsignedWrap(true); 02503 const_cast<SCEVAddRecExpr *>(PostInc) 02504 ->setHasNoUnsignedWrap(true); 02505 } 02506 if (OBO->hasNoSignedWrap()) { 02507 const_cast<SCEVAddRecExpr *>(PHISCEV) 02508 ->setHasNoSignedWrap(true); 02509 const_cast<SCEVAddRecExpr *>(PostInc) 02510 ->setHasNoSignedWrap(true); 02511 } 02512 } 02513 02514 // Okay, for the entire analysis of this edge we assumed the PHI 02515 // to be symbolic. We now need to go back and purge all of the 02516 // entries for the scalars that use the symbolic expression. 02517 ForgetSymbolicName(PN, SymbolicName); 02518 Scalars[SCEVCallbackVH(PN, this)] = PHISCEV; 02519 return PHISCEV; 02520 } 02521 } 02522 } else if (const SCEVAddRecExpr *AddRec = 02523 dyn_cast<SCEVAddRecExpr>(BEValue)) { 02524 // Otherwise, this could be a loop like this: 02525 // i = 0; for (j = 1; ..; ++j) { .... i = j; } 02526 // In this case, j = {1,+,1} and BEValue is j. 02527 // Because the other in-value of i (0) fits the evolution of BEValue 02528 // i really is an addrec evolution. 02529 if (AddRec->getLoop() == L && AddRec->isAffine()) { 02530 const SCEV *StartVal = getSCEV(PN->getIncomingValue(IncomingEdge)); 02531 02532 // If StartVal = j.start - j.stride, we can use StartVal as the 02533 // initial step of the addrec evolution. 02534 if (StartVal == getMinusSCEV(AddRec->getOperand(0), 02535 AddRec->getOperand(1))) { 02536 const SCEV *PHISCEV = 02537 getAddRecExpr(StartVal, AddRec->getOperand(1), L); 02538 02539 // Okay, for the entire analysis of this edge we assumed the PHI 02540 // to be symbolic. We now need to go back and purge all of the 02541 // entries for the scalars that use the symbolic expression. 02542 ForgetSymbolicName(PN, SymbolicName); 02543 Scalars[SCEVCallbackVH(PN, this)] = PHISCEV; 02544 return PHISCEV; 02545 } 02546 } 02547 } 02548 02549 return SymbolicName; 02550 } 02551 02552 // It's tempting to recognize PHIs with a unique incoming value, however 02553 // this leads passes like indvars to break LCSSA form. Fortunately, such 02554 // PHIs are rare, as instcombine zaps them. 02555 02556 // If it's not a loop phi, we can't handle it yet. 02557 return getUnknown(PN); 02558 } 02559 02560 /// createNodeForGEP - Expand GEP instructions into add and multiply 02561 /// operations. This allows them to be analyzed by regular SCEV code. 02562 /// 02563 const SCEV *ScalarEvolution::createNodeForGEP(Operator *GEP) { 02564 02565 const Type *IntPtrTy = getEffectiveSCEVType(GEP->getType()); 02566 Value *Base = GEP->getOperand(0); 02567 // Don't attempt to analyze GEPs over unsized objects. 02568 if (!cast<PointerType>(Base->getType())->getElementType()->isSized()) 02569 return getUnknown(GEP); 02570 const SCEV *TotalOffset = getIntegerSCEV(0, IntPtrTy); 02571 gep_type_iterator GTI = gep_type_begin(GEP); 02572 for (GetElementPtrInst::op_iterator I = next(GEP->op_begin()), 02573 E = GEP->op_end(); 02574 I != E; ++I) { 02575 Value *Index = *I; 02576 // Compute the (potentially symbolic) offset in bytes for this index. 02577 if (const StructType *STy = dyn_cast<StructType>(*GTI++)) { 02578 // For a struct, add the member offset. 02579 unsigned FieldNo = cast<ConstantInt>(Index)->getZExtValue(); 02580 TotalOffset = getAddExpr(TotalOffset, 02581 getFieldOffsetExpr(STy, FieldNo)); 02582 } else { 02583 // For an array, add the element offset, explicitly scaled. 02584 const SCEV *LocalOffset = getSCEV(Index); 02585 if (!isa<PointerType>(LocalOffset->getType())) 02586 // Getelementptr indicies are signed. 02587 LocalOffset = getTruncateOrSignExtend(LocalOffset, IntPtrTy); 02588 LocalOffset = getMulExpr(LocalOffset, getAllocSizeExpr(*GTI)); 02589 TotalOffset = getAddExpr(TotalOffset, LocalOffset); 02590 } 02591 } 02592 return getAddExpr(getSCEV(Base), TotalOffset); 02593 } 02594 02595 /// GetMinTrailingZeros - Determine the minimum number of zero bits that S is 02596 /// guaranteed to end in (at every loop iteration). It is, at the same time, 02597 /// the minimum number of times S is divisible by 2. For example, given {4,+,8} 02598 /// it returns 2. If S is guaranteed to be 0, it returns the bitwidth of S. 02599 uint32_t 02600 ScalarEvolution::GetMinTrailingZeros(const SCEV *S) { 02601 if (const SCEVConstant *C = dyn_cast<SCEVConstant>(S)) 02602 return C->getValue()->getValue().countTrailingZeros(); 02603 02604 if (const SCEVTruncateExpr *T = dyn_cast<SCEVTruncateExpr>(S)) 02605 return std::min(GetMinTrailingZeros(T->getOperand()), 02606 (uint32_t)getTypeSizeInBits(T->getType())); 02607 02608 if (const SCEVZeroExtendExpr *E = dyn_cast<SCEVZeroExtendExpr>(S)) { 02609 uint32_t OpRes = GetMinTrailingZeros(E->getOperand()); 02610 return OpRes == getTypeSizeInBits(E->getOperand()->getType()) ? 02611 getTypeSizeInBits(E->getType()) : OpRes; 02612 } 02613 02614 if (const SCEVSignExtendExpr *E = dyn_cast<SCEVSignExtendExpr>(S)) { 02615 uint32_t OpRes = GetMinTrailingZeros(E->getOperand()); 02616 return OpRes == getTypeSizeInBits(E->getOperand()->getType()) ? 02617 getTypeSizeInBits(E->getType()) : OpRes; 02618 } 02619 02620 if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(S)) { 02621 // The result is the min of all operands results. 02622 uint32_t MinOpRes = GetMinTrailingZeros(A->getOperand(0)); 02623 for (unsigned i = 1, e = A->getNumOperands(); MinOpRes && i != e; ++i) 02624 MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(A->getOperand(i))); 02625 return MinOpRes; 02626 } 02627 02628 if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(S)) { 02629 // The result is the sum of all operands results. 02630 uint32_t SumOpRes = GetMinTrailingZeros(M->getOperand(0)); 02631 uint32_t BitWidth = getTypeSizeInBits(M->getType()); 02632 for (unsigned i = 1, e = M->getNumOperands(); 02633 SumOpRes != BitWidth && i != e; ++i) 02634 SumOpRes = std::min(SumOpRes + GetMinTrailingZeros(M->getOperand(i)), 02635 BitWidth); 02636 return SumOpRes; 02637 } 02638 02639 if (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(S)) { 02640 // The result is the min of all operands results. 02641 uint32_t MinOpRes = GetMinTrailingZeros(A->getOperand(0)); 02642 for (unsigned i = 1, e = A->getNumOperands(); MinOpRes && i != e; ++i) 02643 MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(A->getOperand(i))); 02644 return MinOpRes; 02645 } 02646 02647 if (const SCEVSMaxExpr *M = dyn_cast<SCEVSMaxExpr>(S)) { 02648 // The result is the min of all operands results. 02649 uint32_t MinOpRes = GetMinTrailingZeros(M->getOperand(0)); 02650 for (unsigned i = 1, e = M->getNumOperands(); MinOpRes && i != e; ++i) 02651 MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(M->getOperand(i))); 02652 return MinOpRes; 02653 } 02654 02655 if (const SCEVUMaxExpr *M = dyn_cast<SCEVUMaxExpr>(S)) { 02656 // The result is the min of all operands results. 02657 uint32_t MinOpRes = GetMinTrailingZeros(M->getOperand(0)); 02658 for (unsigned i = 1, e = M->getNumOperands(); MinOpRes && i != e; ++i) 02659 MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(M->getOperand(i))); 02660 return MinOpRes; 02661 } 02662 02663 if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) { 02664 // For a SCEVUnknown, ask ValueTracking. 02665 unsigned BitWidth = getTypeSizeInBits(U->getType()); 02666 APInt Mask = APInt::getAllOnesValue(BitWidth); 02667 APInt Zeros(BitWidth, 0), Ones(BitWidth, 0); 02668 ComputeMaskedBits(U->getValue(), Mask, Zeros, Ones); 02669 return Zeros.countTrailingOnes(); 02670 } 02671 02672 // SCEVUDivExpr 02673 return 0; 02674 } 02675 02676 /// getUnsignedRange - Determine the unsigned range for a particular SCEV. 02677 /// 02678 ConstantRange 02679 ScalarEvolution::getUnsignedRange(const SCEV *S) { 02680 02681 if (const SCEVConstant *C = dyn_cast<SCEVConstant>(S)) 02682 return ConstantRange(C->getValue()->getValue()); 02683 02684 if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) { 02685 ConstantRange X = getUnsignedRange(Add->getOperand(0)); 02686 for (unsigned i = 1, e = Add->getNumOperands(); i != e; ++i) 02687 X = X.add(getUnsignedRange(Add->getOperand(i))); 02688 return X; 02689 } 02690 02691 if (const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(S)) { 02692 ConstantRange X = getUnsignedRange(Mul->getOperand(0)); 02693 for (unsigned i = 1, e = Mul->getNumOperands(); i != e; ++i) 02694 X = X.multiply(getUnsignedRange(Mul->getOperand(i))); 02695 return X; 02696 } 02697 02698 if (const SCEVSMaxExpr *SMax = dyn_cast<SCEVSMaxExpr>(S)) { 02699 ConstantRange X = getUnsignedRange(SMax->getOperand(0)); 02700 for (unsigned i = 1, e = SMax->getNumOperands(); i != e; ++i) 02701 X = X.smax(getUnsignedRange(SMax->getOperand(i))); 02702 return X; 02703 } 02704 02705 if (const SCEVUMaxExpr *UMax = dyn_cast<SCEVUMaxExpr>(S)) { 02706 ConstantRange X = getUnsignedRange(UMax->getOperand(0)); 02707 for (unsigned i = 1, e = UMax->getNumOperands(); i != e; ++i) 02708 X = X.umax(getUnsignedRange(UMax->getOperand(i))); 02709 return X; 02710 } 02711 02712 if (const SCEVUDivExpr *UDiv = dyn_cast<SCEVUDivExpr>(S)) { 02713 ConstantRange X = getUnsignedRange(UDiv->getLHS()); 02714 ConstantRange Y = getUnsignedRange(UDiv->getRHS()); 02715 return X.udiv(Y); 02716 } 02717 02718 if (const SCEVZeroExtendExpr *ZExt = dyn_cast<SCEVZeroExtendExpr>(S)) { 02719 ConstantRange X = getUnsignedRange(ZExt->getOperand()); 02720 return X.zeroExtend(cast<IntegerType>(ZExt->getType())->getBitWidth()); 02721 } 02722 02723 if (const SCEVSignExtendExpr *SExt = dyn_cast<SCEVSignExtendExpr>(S)) { 02724 ConstantRange X = getUnsignedRange(SExt->getOperand()); 02725 return X.signExtend(cast<IntegerType>(SExt->getType())->getBitWidth()); 02726 } 02727 02728 if (const SCEVTruncateExpr *Trunc = dyn_cast<SCEVTruncateExpr>(S)) { 02729 ConstantRange X = getUnsignedRange(Trunc->getOperand()); 02730 return X.truncate(cast<IntegerType>(Trunc->getType())->getBitWidth()); 02731 } 02732 02733 ConstantRange FullSet(getTypeSizeInBits(S->getType()), true); 02734 02735 if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(S)) { 02736 const SCEV *T = getBackedgeTakenCount(AddRec->getLoop()); 02737 const SCEVConstant *Trip = dyn_cast<SCEVConstant>(T); 02738 if (!Trip) return FullSet; 02739 02740 // TODO: non-affine addrec 02741 if (AddRec->isAffine()) { 02742 const Type *Ty = AddRec->getType(); 02743 const SCEV *MaxBECount = getMaxBackedgeTakenCount(AddRec->getLoop()); 02744 if (getTypeSizeInBits(MaxBECount->getType()) <= getTypeSizeInBits(Ty)) { 02745 MaxBECount = getNoopOrZeroExtend(MaxBECount, Ty); 02746 02747 const SCEV *Start = AddRec->getStart(); 02748 const SCEV *Step = AddRec->getStepRecurrence(*this); 02749 const SCEV *End = AddRec->evaluateAtIteration(MaxBECount, *this); 02750 02751 // Check for overflow. 02752 // TODO: This is very conservative. 02753 if (!(Step->isOne() && 02754 isKnownPredicate(ICmpInst::ICMP_ULT, Start, End)) && 02755 !(Step->isAllOnesValue() && 02756 isKnownPredicate(ICmpInst::ICMP_UGT, Start, End))) 02757 return FullSet; 02758 02759 ConstantRange StartRange = getUnsignedRange(Start); 02760 ConstantRange EndRange = getUnsignedRange(End); 02761 APInt Min = APIntOps::umin(StartRange.getUnsignedMin(), 02762 EndRange.getUnsignedMin()); 02763 APInt Max = APIntOps::umax(StartRange.getUnsignedMax(), 02764 EndRange.getUnsignedMax()); 02765 if (Min.isMinValue() && Max.isMaxValue()) 02766 return FullSet; 02767 return ConstantRange(Min, Max+1); 02768 } 02769 } 02770 } 02771 02772 if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) { 02773 // For a SCEVUnknown, ask ValueTracking. 02774 unsigned BitWidth = getTypeSizeInBits(U->getType()); 02775 APInt Mask = APInt::getAllOnesValue(BitWidth); 02776 APInt Zeros(BitWidth, 0), Ones(BitWidth, 0); 02777 ComputeMaskedBits(U->getValue(), Mask, Zeros, Ones, TD); 02778 if (Ones == ~Zeros + 1) 02779 return FullSet; 02780 return ConstantRange(Ones, ~Zeros + 1); 02781 } 02782 02783 return FullSet; 02784 } 02785 02786 /// getSignedRange - Determine the signed range for a particular SCEV. 02787 /// 02788 ConstantRange 02789 ScalarEvolution::getSignedRange(const SCEV *S) { 02790 02791 if (const SCEVConstant *C = dyn_cast<SCEVConstant>(S)) 02792 return ConstantRange(C->getValue()->getValue()); 02793 02794 if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) { 02795 ConstantRange X = getSignedRange(Add->getOperand(0)); 02796 for (unsigned i = 1, e = Add->getNumOperands(); i != e; ++i) 02797 X = X.add(getSignedRange(Add->getOperand(i))); 02798 return X; 02799 } 02800 02801 if (const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(S)) { 02802 ConstantRange X = getSignedRange(Mul->getOperand(0)); 02803 for (unsigned i = 1, e = Mul->getNumOperands(); i != e; ++i) 02804 X = X.multiply(getSignedRange(Mul->getOperand(i))); 02805 return X; 02806 } 02807 02808 if (const SCEVSMaxExpr *SMax = dyn_cast<SCEVSMaxExpr>(S)) { 02809 ConstantRange X = getSignedRange(SMax->getOperand(0)); 02810 for (unsigned i = 1, e = SMax->getNumOperands(); i != e; ++i) 02811 X = X.smax(getSignedRange(SMax->getOperand(i))); 02812 return X; 02813 } 02814 02815 if (const SCEVUMaxExpr *UMax = dyn_cast<SCEVUMaxExpr>(S)) { 02816 ConstantRange X = getSignedRange(UMax->getOperand(0)); 02817 for (unsigned i = 1, e = UMax->getNumOperands(); i != e; ++i) 02818 X = X.umax(getSignedRange(UMax->getOperand(i))); 02819 return X; 02820 } 02821 02822 if (const SCEVUDivExpr *UDiv = dyn_cast<SCEVUDivExpr>(S)) { 02823 ConstantRange X = getSignedRange(UDiv->getLHS()); 02824 ConstantRange Y = getSignedRange(UDiv->getRHS()); 02825 return X.udiv(Y); 02826 } 02827 02828 if (const SCEVZeroExtendExpr *ZExt = dyn_cast<SCEVZeroExtendExpr>(S)) { 02829 ConstantRange X = getSignedRange(ZExt->getOperand()); 02830 return X.zeroExtend(cast<IntegerType>(ZExt->getType())->getBitWidth()); 02831 } 02832 02833 if (const SCEVSignExtendExpr *SExt = dyn_cast<SCEVSignExtendExpr>(S)) { 02834 ConstantRange X = getSignedRange(SExt->getOperand()); 02835 return X.signExtend(cast<IntegerType>(SExt->getType())->getBitWidth()); 02836 } 02837 02838 if (const SCEVTruncateExpr *Trunc = dyn_cast<SCEVTruncateExpr>(S)) { 02839 ConstantRange X = getSignedRange(Trunc->getOperand()); 02840 return X.truncate(cast<IntegerType>(Trunc->getType())->getBitWidth()); 02841 } 02842 02843 ConstantRange FullSet(getTypeSizeInBits(S->getType()), true); 02844 02845 if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(S)) { 02846 const SCEV *T = getBackedgeTakenCount(AddRec->getLoop()); 02847 const SCEVConstant *Trip = dyn_cast<SCEVConstant>(T); 02848 if (!Trip) return FullSet; 02849 02850 // TODO: non-affine addrec 02851 if (AddRec->isAffine()) { 02852 const Type *Ty = AddRec->getType(); 02853 const SCEV *MaxBECount = getMaxBackedgeTakenCount(AddRec->getLoop()); 02854 if (getTypeSizeInBits(MaxBECount->getType()) <= getTypeSizeInBits(Ty)) { 02855 MaxBECount = getNoopOrZeroExtend(MaxBECount, Ty); 02856 02857 const SCEV *Start = AddRec->getStart(); 02858 const SCEV *Step = AddRec->getStepRecurrence(*this); 02859 const SCEV *End = AddRec->evaluateAtIteration(MaxBECount, *this); 02860 02861 // Check for overflow. 02862 // TODO: This is very conservative. 02863 if (!(Step->isOne() && 02864 isKnownPredicate(ICmpInst::ICMP_SLT, Start, End)) && 02865 !(Step->isAllOnesValue() && 02866 isKnownPredicate(ICmpInst::ICMP_SGT, Start, End))) 02867 return FullSet; 02868 02869 ConstantRange StartRange = getSignedRange(Start); 02870 ConstantRange EndRange = getSignedRange(End); 02871 APInt Min = APIntOps::smin(StartRange.getSignedMin(), 02872 EndRange.getSignedMin()); 02873 APInt Max = APIntOps::smax(StartRange.getSignedMax(), 02874 EndRange.getSignedMax()); 02875 if (Min.isMinSignedValue() && Max.isMaxSignedValue()) 02876 return FullSet; 02877 return ConstantRange(Min, Max+1); 02878 } 02879 } 02880 } 02881 02882 if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) { 02883 // For a SCEVUnknown, ask ValueTracking. 02884 unsigned BitWidth = getTypeSizeInBits(U->getType()); 02885 unsigned NS = ComputeNumSignBits(U->getValue(), TD); 02886 if (NS == 1) 02887 return FullSet; 02888 return 02889 ConstantRange(APInt::getSignedMinValue(BitWidth).ashr(NS - 1), 02890 APInt::getSignedMaxValue(BitWidth).ashr(NS - 1)+1); 02891 } 02892 02893 return FullSet; 02894 } 02895 02896 /// createSCEV - We know that there is no SCEV for the specified value. 02897 /// Analyze the expression. 02898 /// 02899 const SCEV *ScalarEvolution::createSCEV(Value *V) { 02900 if (!isSCEVable(V->getType())) 02901 return getUnknown(V); 02902 02903 unsigned Opcode = Instruction::UserOp1; 02904 if (Instruction *I = dyn_cast<Instruction>(V)) 02905 Opcode = I->getOpcode(); 02906 else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) 02907 Opcode = CE->getOpcode(); 02908 else if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) 02909 return getConstant(CI); 02910 else if (isa<ConstantPointerNull>(V)) 02911 return getIntegerSCEV(0, V->getType()); 02912 else if (isa<UndefValue>(V)) 02913 return getIntegerSCEV(0, V->getType()); 02914 else 02915 return getUnknown(V); 02916 02917 Operator *U = cast<Operator>(V); 02918 switch (Opcode) { 02919 case Instruction::Add: 02920 return getAddExpr(getSCEV(U->getOperand(0)), 02921 getSCEV(U->getOperand(1))); 02922 case Instruction::Mul: 02923 return getMulExpr(getSCEV(U->getOperand(0)), 02924 getSCEV(U->getOperand(1))); 02925 case Instruction::UDiv: 02926 return getUDivExpr(getSCEV(U->getOperand(0)), 02927 getSCEV(U->getOperand(1))); 02928 case Instruction::Sub: 02929 return getMinusSCEV(getSCEV(U->getOperand(0)), 02930 getSCEV(U->getOperand(1))); 02931 case Instruction::And: 02932 // For an expression like x&255 that merely masks off the high bits, 02933 // use zext(trunc(x)) as the SCEV expression. 02934 if (ConstantInt *CI = dyn_cast<ConstantInt>(U->getOperand(1))) { 02935 if (CI->isNullValue()) 02936 return getSCEV(U->getOperand(1)); 02937 if (CI->isAllOnesValue()) 02938 return getSCEV(U->getOperand(0)); 02939 const APInt &A = CI->getValue(); 02940 02941 // Instcombine's ShrinkDemandedConstant may strip bits out of 02942 // constants, obscuring what would otherwise be a low-bits mask. 02943 // Use ComputeMaskedBits to compute what ShrinkDemandedConstant 02944 // knew about to reconstruct a low-bits mask value. 02945 unsigned LZ = A.countLeadingZeros(); 02946 unsigned BitWidth = A.getBitWidth(); 02947 APInt AllOnes = APInt::getAllOnesValue(BitWidth); 02948 APInt KnownZero(BitWidth, 0), KnownOne(BitWidth, 0); 02949 ComputeMaskedBits(U->getOperand(0), AllOnes, KnownZero, KnownOne, TD); 02950 02951 APInt EffectiveMask = APInt::getLowBitsSet(BitWidth, BitWidth - LZ); 02952 02953 if (LZ != 0 && !((~A & ~KnownZero) & EffectiveMask)) 02954 return 02955 getZeroExtendExpr(getTruncateExpr(getSCEV(U->getOperand(0)), 02956 IntegerType::get(getContext(), BitWidth - LZ)), 02957 U->getType()); 02958 } 02959 break; 02960 02961 case Instruction::Or: 02962 // If the RHS of the Or is a constant, we may have something like: 02963 // X*4+1 which got turned into X*4|1. Handle this as an Add so loop 02964 // optimizations will transparently handle this case. 02965 // 02966 // In order for this transformation to be safe, the LHS must be of the 02967 // form X*(2^n) and the Or constant must be less than 2^n. 02968 if (ConstantInt *CI = dyn_cast<ConstantInt>(U->getOperand(1))) { 02969 const SCEV *LHS = getSCEV(U->getOperand(0)); 02970 const APInt &CIVal = CI->getValue(); 02971 if (GetMinTrailingZeros(LHS) >= 02972 (CIVal.getBitWidth() - CIVal.countLeadingZeros())) 02973 return getAddExpr(LHS, getSCEV(U->getOperand(1))); 02974 } 02975 break; 02976 case Instruction::Xor: 02977 if (ConstantInt *CI = dyn_cast<ConstantInt>(U->getOperand(1))) { 02978 // If the RHS of the xor is a signbit, then this is just an add. 02979 // Instcombine turns add of signbit into xor as a strength reduction step. 02980 if (CI->getValue().isSignBit()) 02981 return getAddExpr(getSCEV(U->getOperand(0)), 02982 getSCEV(U->getOperand(1))); 02983 02984 // If the RHS of xor is -1, then this is a not operation. 02985 if (CI->isAllOnesValue()) 02986 return getNotSCEV(getSCEV(U->getOperand(0))); 02987 02988 // Model xor(and(x, C), C) as and(~x, C), if C is a low-bits mask. 02989 // This is a variant of the check for xor with -1, and it handles 02990 // the case where instcombine has trimmed non-demanded bits out 02991 // of an xor with -1. 02992 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(U->getOperand(0))) 02993 if (ConstantInt *LCI = dyn_cast<ConstantInt>(BO->getOperand(1))) 02994 if (BO->getOpcode() == Instruction::And && 02995 LCI->getValue() == CI->getValue()) 02996 if (const SCEVZeroExtendExpr *Z = 02997 dyn_cast<SCEVZeroExtendExpr>(getSCEV(U->getOperand(0)))) { 02998 const Type *UTy = U->getType(); 02999 const SCEV *Z0 = Z->getOperand(); 03000 const Type *Z0Ty = Z0->getType(); 03001 unsigned Z0TySize = getTypeSizeInBits(Z0Ty); 03002 03003 // If C is a low-bits mask, the zero extend is zerving to 03004 // mask off the high bits. Complement the operand and 03005 // re-apply the zext. 03006 if (APIntOps::isMask(Z0TySize, CI->getValue())) 03007 return getZeroExtendExpr(getNotSCEV(Z0), UTy); 03008 03009 // If C is a single bit, it may be in the sign-bit position 03010 // before the zero-extend. In this case, represent the xor 03011 // using an add, which is equivalent, and re-apply the zext. 03012 APInt Trunc = APInt(CI->getValue()).trunc(Z0TySize); 03013 if (APInt(Trunc).zext(getTypeSizeInBits(UTy)) == CI->getValue() && 03014 Trunc.isSignBit()) 03015 return getZeroExtendExpr(getAddExpr(Z0, getConstant(Trunc)), 03016 UTy); 03017 } 03018 } 03019 break; 03020 03021 case Instruction::Shl: 03022 // Turn shift left of a constant amount into a multiply. 03023 if (ConstantInt *SA = dyn_cast<ConstantInt>(U->getOperand(1))) { 03024 uint32_t BitWidth = cast<IntegerType>(V->getType())->getBitWidth(); 03025 Constant *X = ConstantInt::get(getContext(), 03026 APInt(BitWidth, 1).shl(SA->getLimitedValue(BitWidth))); 03027 return getMulExpr(getSCEV(U->getOperand(0)), getSCEV(X)); 03028 } 03029 break; 03030 03031 case Instruction::LShr: 03032 // Turn logical shift right of a constant into a unsigned divide. 03033 if (ConstantInt *SA = dyn_cast<ConstantInt>(U->getOperand(1))) { 03034 uint32_t BitWidth = cast<IntegerType>(V->getType())->getBitWidth(); 03035 Constant *X = ConstantInt::get(getContext(), 03036 APInt(BitWidth, 1).shl(SA->getLimitedValue(BitWidth))); 03037 return getUDivExpr(getSCEV(U->getOperand(0)), getSCEV(X)); 03038 } 03039 break; 03040 03041 case Instruction::AShr: 03042 // For a two-shift sext-inreg, use sext(trunc(x)) as the SCEV expression. 03043 if (ConstantInt *CI = dyn_cast<ConstantInt>(U->getOperand(1))) 03044 if (Instruction *L = dyn_cast<Instruction>(U->getOperand(0))) 03045 if (L->getOpcode() == Instruction::Shl && 03046 L->getOperand(1) == U->getOperand(1)) { 03047 unsigned BitWidth = getTypeSizeInBits(U->getType()); 03048 uint64_t Amt = BitWidth - CI->getZExtValue(); 03049 if (Amt == BitWidth) 03050 return getSCEV(L->getOperand(0)); // shift by zero --> noop 03051 if (Amt > BitWidth) 03052 return getIntegerSCEV(0, U->getType()); // value is undefined 03053 return 03054 getSignExtendExpr(getTruncateExpr(getSCEV(L->getOperand(0)), 03055 IntegerType::get(getContext(), Amt)), 03056 U->getType()); 03057 } 03058 break; 03059 03060 case Instruction::Trunc: 03061 return getTruncateExpr(getSCEV(U->getOperand(0)), U->getType()); 03062 03063 case Instruction::ZExt: 03064 return getZeroExtendExpr(getSCEV(U->getOperand(0)), U->getType()); 03065 03066 case Instruction::SExt: 03067 return getSignExtendExpr(getSCEV(U->getOperand(0)), U->getType()); 03068 03069 case Instruction::BitCast: 03070 // BitCasts are no-op casts so we just eliminate the cast. 03071 if (isSCEVable(U->getType()) && isSCEVable(U->getOperand(0)->getType())) 03072 return getSCEV(U->getOperand(0)); 03073 break; 03074 03075 // It's tempting to handle inttoptr and ptrtoint, however this can 03076 // lead to pointer expressions which cannot be expanded to GEPs 03077 // (because they may overflow). For now, the only pointer-typed 03078 // expressions we handle are GEPs and address literals. 03079 03080 case Instruction::GetElementPtr: 03081 return createNodeForGEP(U); 03082 03083 case Instruction::PHI: 03084 return createNodeForPHI(cast<PHINode>(U)); 03085 03086 case Instruction::Select: 03087 // This could be a smax or umax that was lowered earlier. 03088 // Try to recover it. 03089 if (ICmpInst *ICI = dyn_cast<ICmpInst>(U->getOperand(0))) { 03090 Value *LHS = ICI->getOperand(0); 03091 Value *RHS = ICI->getOperand(1); 03092 switch (ICI->getPredicate()) { 03093 case ICmpInst::ICMP_SLT: 03094 case ICmpInst::ICMP_SLE: 03095 std::swap(LHS, RHS); 03096 // fall through 03097 case ICmpInst::ICMP_SGT: 03098 case ICmpInst::ICMP_SGE: 03099 if (LHS == U->getOperand(1) && RHS == U->getOperand(2)) 03100 return getSMaxExpr(getSCEV(LHS), getSCEV(RHS)); 03101 else if (LHS == U->getOperand(2) && RHS == U->getOperand(1)) 03102 return getSMinExpr(getSCEV(LHS), getSCEV(RHS)); 03103 break; 03104 case ICmpInst::ICMP_ULT: 03105 case ICmpInst::ICMP_ULE: 03106 std::swap(LHS, RHS); 03107 // fall through 03108 case ICmpInst::ICMP_UGT: 03109 case ICmpInst::ICMP_UGE: 03110 if (LHS == U->getOperand(1) && RHS == U->getOperand(2)) 03111 return getUMaxExpr(getSCEV(LHS), getSCEV(RHS)); 03112 else if (LHS == U->getOperand(2) && RHS == U->getOperand(1)) 03113 return getUMinExpr(getSCEV(LHS), getSCEV(RHS)); 03114 break; 03115 case ICmpInst::ICMP_NE: 03116 // n != 0 ? n : 1 -> umax(n, 1) 03117 if (LHS == U->getOperand(1) && 03118 isa<ConstantInt>(U->getOperand(2)) && 03119 cast<ConstantInt>(U->getOperand(2))->isOne() && 03120 isa<ConstantInt>(RHS) && 03121 cast<ConstantInt>(RHS)->isZero()) 03122 return getUMaxExpr(getSCEV(LHS), getSCEV(U->getOperand(2))); 03123 break; 03124 case ICmpInst::ICMP_EQ: 03125 // n == 0 ? 1 : n -> umax(n, 1) 03126 if (LHS == U->getOperand(2) && 03127 isa<ConstantInt>(U->getOperand(1)) && 03128 cast<ConstantInt>(U->getOperand(1))->isOne() && 03129 isa<ConstantInt>(RHS) && 03130 cast<ConstantInt>(RHS)->isZero()) 03131 return getUMaxExpr(getSCEV(LHS), getSCEV(U->getOperand(1))); 03132 break; 03133 default: 03134 break; 03135 } 03136 } 03137 03138 default: // We cannot analyze this expression. 03139 break; 03140 } 03141 03142 return getUnknown(V); 03143 } 03144 03145 03146 03147 //===----------------------------------------------------------------------===// 03148 // Iteration Count Computation Code 03149 // 03150 03151 /// getBackedgeTakenCount - If the specified loop has a predictable 03152 /// backedge-taken count, return it, otherwise return a SCEVCouldNotCompute 03153 /// object. The backedge-taken count is the number of times the loop header 03154 /// will be branched to from within the loop. This is one less than the 03155 /// trip count of the loop, since it doesn't count the first iteration, 03156 /// when the header is branched to from outside the loop. 03157 /// 03158 /// Note that it is not valid to call this method on a loop without a 03159 /// loop-invariant backedge-taken count (see 03160 /// hasLoopInvariantBackedgeTakenCount). 03161 /// 03162 const SCEV *ScalarEvolution::getBackedgeTakenCount(const Loop *L) { 03163 return getBackedgeTakenInfo(L).Exact; 03164 } 03165 03166 /// getMaxBackedgeTakenCount - Similar to getBackedgeTakenCount, except 03167 /// return the least SCEV value that is known never to be less than the 03168 /// actual backedge taken count. 03169 const SCEV *ScalarEvolution::getMaxBackedgeTakenCount(const Loop *L) { 03170 return getBackedgeTakenInfo(L).Max; 03171 } 03172 03173 /// PushLoopPHIs - Push PHI nodes in the header of the given loop 03174 /// onto the given Worklist. 03175 static void 03176 PushLoopPHIs(const Loop *L, SmallVectorImpl<Instruction *> &Worklist) { 03177 BasicBlock *Header = L->getHeader(); 03178 03179 // Push all Loop-header PHIs onto the Worklist stack. 03180 for (BasicBlock::iterator I = Header->begin(); 03181 PHINode *PN = dyn_cast<PHINode>(I); ++I) 03182 Worklist.push_back(PN); 03183 } 03184 03185 const ScalarEvolution::BackedgeTakenInfo & 03186 ScalarEvolution::getBackedgeTakenInfo(const Loop *L) { 03187 // Initially insert a CouldNotCompute for this loop. If the insertion 03188 // succeeds, procede to actually compute a backedge-taken count and 03189 // update the value. The temporary CouldNotCompute value tells SCEV 03190 // code elsewhere that it shouldn't attempt to request a new 03191 // backedge-taken count, which could result in infinite recursion. 03192 std::pair<std::map<const Loop*, BackedgeTakenInfo>::iterator, bool> Pair = 03193 BackedgeTakenCounts.insert(std::make_pair(L, getCouldNotCompute())); 03194 if (Pair.second) { 03195 BackedgeTakenInfo ItCount = ComputeBackedgeTakenCount(L); 03196 if (ItCount.Exact != getCouldNotCompute()) { 03197 assert(ItCount.Exact->isLoopInvariant(L) && 03198 ItCount.Max->isLoopInvariant(L) && 03199 "Computed trip count isn't loop invariant for loop!"); 03200 ++NumTripCountsComputed; 03201 03202 // Update the value in the map. 03203 Pair.first->second = ItCount; 03204 } else { 03205 if (ItCount.Max != getCouldNotCompute()) 03206 // Update the value in the map. 03207 Pair.first->second = ItCount; 03208 if (isa<PHINode>(L->getHeader()->begin())) 03209 // Only count loops that have phi nodes as not being computable. 03210 ++NumTripCountsNotComputed; 03211 } 03212 03213 // Now that we know more about the trip count for this loop, forget any 03214 // existing SCEV values for PHI nodes in this loop since they are only 03215 // conservative estimates made without the benefit of trip count 03216 // information. This is similar to the code in 03217 // forgetLoopBackedgeTakenCount, except that it handles SCEVUnknown PHI 03218 // nodes specially. 03219 if (ItCount.hasAnyInfo()) { 03220 SmallVector<Instruction *, 16> Worklist; 03221 PushLoopPHIs(L, Worklist); 03222 03223 SmallPtrSet<Instruction *, 8> Visited; 03224 while (!Worklist.empty()) { 03225 Instruction *I = Worklist.pop_back_val(); 03226 if (!Visited.insert(I)) continue; 03227 03228 std::map<SCEVCallbackVH, const SCEV*>::iterator It = 03229 Scalars.find(static_cast<Value *>(I)); 03230 if (It != Scalars.end()) { 03231 // SCEVUnknown for a PHI either means that it has an unrecognized 03232 // structure, or it's a PHI that's in the progress of being computed 03233 // by createNodeForPHI. In the former case, additional loop trip 03234 // count information isn't going to change anything. In the later 03235 // case, createNodeForPHI will perform the necessary updates on its 03236 // own when it gets to that point. 03237 if (!isa<PHINode>(I) || !isa<SCEVUnknown>(It->second)) 03238 Scalars.erase(It); 03239 ValuesAtScopes.erase(I); 03240 if (PHINode *PN = dyn_cast<PHINode>(I)) 03241 ConstantEvolutionLoopExitValue.erase(PN); 03242 } 03243 03244 PushDefUseChildren(I, Worklist); 03245 } 03246 } 03247 } 03248 return Pair.first->second; 03249 } 03250 03251 /// forgetLoopBackedgeTakenCount - This method should be called by the 03252 /// client when it has changed a loop in a way that may effect 03253 /// ScalarEvolution's ability to compute a trip count, or if the loop 03254 /// is deleted. 03255 void ScalarEvolution::forgetLoopBackedgeTakenCount(const Loop *L) { 03256 BackedgeTakenCounts.erase(L); 03257 03258 SmallVector<Instruction *, 16> Worklist; 03259 PushLoopPHIs(L, Worklist); 03260 03261 SmallPtrSet<Instruction *, 8> Visited; 03262 while (!Worklist.empty()) { 03263 Instruction *I = Worklist.pop_back_val(); 03264 if (!Visited.insert(I)) continue; 03265 03266 std::map<SCEVCallbackVH, const SCEV*>::iterator It = 03267 Scalars.find(static_cast<Value *>(I)); 03268 if (It != Scalars.end()) { 03269 Scalars.erase(It); 03270 ValuesAtScopes.erase(I); 03271 if (PHINode *PN = dyn_cast<PHINode>(I)) 03272 ConstantEvolutionLoopExitValue.erase(PN); 03273 } 03274 03275 PushDefUseChildren(I, Worklist); 03276 } 03277 } 03278 03279 /// ComputeBackedgeTakenCount - Compute the number of times the backedge 03280 /// of the specified loop will execute. 03281 ScalarEvolution::BackedgeTakenInfo 03282 ScalarEvolution::ComputeBackedgeTakenCount(const Loop *L) { 03283 SmallVector<BasicBlock*, 8> ExitingBlocks; 03284 L->getExitingBlocks(ExitingBlocks); 03285 03286 // Examine all exits and pick the most conservative values. 03287 const SCEV *BECount = getCouldNotCompute(); 03288 const SCEV *MaxBECount = getCouldNotCompute(); 03289 bool CouldNotComputeBECount = false; 03290 for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) { 03291 BackedgeTakenInfo NewBTI = 03292 ComputeBackedgeTakenCountFromExit(L, ExitingBlocks[i]); 03293 03294 if (NewBTI.Exact == getCouldNotCompute()) { 03295 // We couldn't compute an exact value for this exit, so 03296 // we won't be able to compute an exact value for the loop. 03297 CouldNotComputeBECount = true; 03298 BECount = getCouldNotCompute(); 03299 } else if (!CouldNotComputeBECount) { 03300 if (BECount == getCouldNotCompute()) 03301 BECount = NewBTI.Exact; 03302 else 03303 BECount = getUMinFromMismatchedTypes(BECount, NewBTI.Exact); 03304 } 03305 if (MaxBECount == getCouldNotCompute()) 03306 MaxBECount = NewBTI.Max; 03307 else if (NewBTI.Max != getCouldNotCompute()) 03308 MaxBECount = getUMinFromMismatchedTypes(MaxBECount, NewBTI.Max); 03309 } 03310 03311 return BackedgeTakenInfo(BECount, MaxBECount); 03312 } 03313 03314 /// ComputeBackedgeTakenCountFromExit - Compute the number of times the backedge 03315 /// of the specified loop will execute if it exits via the specified block. 03316 ScalarEvolution::BackedgeTakenInfo 03317 ScalarEvolution::ComputeBackedgeTakenCountFromExit(const Loop *L, 03318 BasicBlock *ExitingBlock) { 03319 03320 // Okay, we've chosen an exiting block. See what condition causes us to 03321 // exit at this block. 03322 // 03323 // FIXME: we should be able to handle switch instructions (with a single exit) 03324 BranchInst *ExitBr = dyn_cast<BranchInst>(ExitingBlock->getTerminator()); 03325 if (ExitBr == 0) return getCouldNotCompute(); 03326 assert(ExitBr->isConditional() && "If unconditional, it can't be in loop!"); 03327 03328 // At this point, we know we have a conditional branch that determines whether 03329 // the loop is exited. However, we don't know if the branch is executed each 03330 // time through the loop. If not, then the execution count of the branch will 03331 // not be equal to the trip count of the loop. 03332 // 03333 // Currently we check for this by checking to see if the Exit branch goes to 03334 // the loop header. If so, we know it will always execute the same number of 03335 // times as the loop. We also handle the case where the exit block *is* the 03336 // loop header. This is common for un-rotated loops. 03337 // 03338 // If both of those tests fail, walk up the unique predecessor chain to the 03339 // header, stopping if there is an edge that doesn't exit the loop. If the 03340 // header is reached, the execution count of the branch will be equal to the 03341 // trip count of the loop. 03342 // 03343 // More extensive analysis could be done to handle more cases here. 03344 // 03345 if (ExitBr->getSuccessor(0) != L->getHeader() && 03346 ExitBr->getSuccessor(1) != L->getHeader() && 03347 ExitBr->getParent() != L->getHeader()) { 03348 // The simple checks failed, try climbing the unique predecessor chain 03349 // up to the header. 03350 bool Ok = false; 03351 for (BasicBlock *BB = ExitBr->getParent(); BB; ) { 03352 BasicBlock *Pred = BB->getUniquePredecessor(); 03353 if (!Pred) 03354 return getCouldNotCompute(); 03355 TerminatorInst *PredTerm = Pred->getTerminator(); 03356 for (unsigned i = 0, e = PredTerm->getNumSuccessors(); i != e; ++i) { 03357 BasicBlock *PredSucc = PredTerm->getSuccessor(i); 03358 if (PredSucc == BB) 03359 continue; 03360 // If the predecessor has a successor that isn't BB and isn't 03361 // outside the loop, assume the worst. 03362 if (L->contains(PredSucc)) 03363 return getCouldNotCompute(); 03364 } 03365 if (Pred == L->getHeader()) { 03366 Ok = true; 03367 break; 03368 } 03369 BB = Pred; 03370 } 03371 if (!Ok) 03372 return getCouldNotCompute(); 03373 } 03374 03375 // Procede to the next level to examine the exit condition expression. 03376 return ComputeBackedgeTakenCountFromExitCond(L, ExitBr->getCondition(), 03377 ExitBr->getSuccessor(0), 03378 ExitBr->getSuccessor(1)); 03379 } 03380 03381 /// ComputeBackedgeTakenCountFromExitCond - Compute the number of times the 03382 /// backedge of the specified loop will execute if its exit condition 03383 /// were a conditional branch of ExitCond, TBB, and FBB. 03384 ScalarEvolution::BackedgeTakenInfo 03385 ScalarEvolution::ComputeBackedgeTakenCountFromExitCond(const Loop *L, 03386 Value *ExitCond, 03387 BasicBlock *TBB, 03388 BasicBlock *FBB) { 03389 // Check if the controlling expression for this loop is an And or Or. 03390 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(ExitCond)) { 03391 if (BO->getOpcode() == Instruction::And) { 03392 // Recurse on the operands of the and. 03393 BackedgeTakenInfo BTI0 = 03394 ComputeBackedgeTakenCountFromExitCond(L, BO->getOperand(0), TBB, FBB); 03395 BackedgeTakenInfo BTI1 = 03396 ComputeBackedgeTakenCountFromExitCond(L, BO->getOperand(1), TBB, FBB); 03397 const SCEV *BECount = getCouldNotCompute(); 03398 const SCEV *MaxBECount = getCouldNotCompute(); 03399 if (L->contains(TBB)) { 03400 // Both conditions must be true for the loop to continue executing. 03401 // Choose the less conservative count. 03402 if (BTI0.Exact == getCouldNotCompute() || 03403 BTI1.Exact == getCouldNotCompute()) 03404 BECount = getCouldNotCompute(); 03405 else 03406 BECount = getUMinFromMismatchedTypes(BTI0.Exact, BTI1.Exact); 03407 if (BTI0.Max == getCouldNotCompute()) 03408 MaxBECount = BTI1.Max; 03409 else if (BTI1.Max == getCouldNotCompute()) 03410 MaxBECount = BTI0.Max; 03411 else 03412 MaxBECount = getUMinFromMismatchedTypes(BTI0.Max, BTI1.Max); 03413 } else { 03414 // Both conditions must be true for the loop to exit. 03415 assert(L->contains(FBB) && "Loop block has no successor in loop!"); 03416 if (BTI0.Exact != getCouldNotCompute() && 03417 BTI1.Exact != getCouldNotCompute()) 03418 BECount = getUMaxFromMismatchedTypes(BTI0.Exact, BTI1.Exact); 03419 if (BTI0.Max != getCouldNotCompute() && 03420 BTI1.Max != getCouldNotCompute()) 03421 MaxBECount = getUMaxFromMismatchedTypes(BTI0.Max, BTI1.Max); 03422 } 03423 03424 return BackedgeTakenInfo(BECount, MaxBECount); 03425 } 03426 if (BO->getOpcode() == Instruction::Or) { 03427 // Recurse on the operands of the or. 03428 BackedgeTakenInfo BTI0 = 03429 ComputeBackedgeTakenCountFromExitCond(L, BO->getOperand(0), TBB, FBB); 03430 BackedgeTakenInfo BTI1 = 03431 ComputeBackedgeTakenCountFromExitCond(L, BO->getOperand(1), TBB, FBB); 03432 const SCEV *BECount = getCouldNotCompute(); 03433 const SCEV *MaxBECount = getCouldNotCompute(); 03434 if (L->contains(FBB)) { 03435 // Both conditions must be false for the loop to continue executing. 03436 // Choose the less conservative count. 03437 if (BTI0.Exact == getCouldNotCompute() || 03438 BTI1.Exact == getCouldNotCompute()) 03439 BECount = getCouldNotCompute(); 03440 else 03441 BECount = getUMinFromMismatchedTypes(BTI0.Exact, BTI1.Exact); 03442 if (BTI0.Max == getCouldNotCompute()) 03443 MaxBECount = BTI1.Max; 03444 else if (BTI1.Max == getCouldNotCompute()) 03445 MaxBECount = BTI0.Max; 03446 else 03447 MaxBECount = getUMinFromMismatchedTypes(BTI0.Max, BTI1.Max); 03448 } else { 03449 // Both conditions must be false for the loop to exit. 03450 assert(L->contains(TBB) && "Loop block has no successor in loop!"); 03451 if (BTI0.Exact != getCouldNotCompute() && 03452 BTI1.Exact != getCouldNotCompute()) 03453 BECount = getUMaxFromMismatchedTypes(BTI0.Exact, BTI1.Exact); 03454 if (BTI0.Max != getCouldNotCompute() && 03455 BTI1.Max != getCouldNotCompute()) 03456 MaxBECount = getUMaxFromMismatchedTypes(BTI0.Max, BTI1.Max); 03457 } 03458 03459 return BackedgeTakenInfo(BECount, MaxBECount); 03460 } 03461 } 03462 03463 // With an icmp, it may be feasible to compute an exact backedge-taken count. 03464 // Procede to the next level to examine the icmp. 03465 if (ICmpInst *ExitCondICmp = dyn_cast<ICmpInst>(ExitCond)) 03466 return ComputeBackedgeTakenCountFromExitCondICmp(L, ExitCondICmp, TBB, FBB); 03467 03468 // If it's not an integer or pointer comparison then compute it the hard way. 03469 return ComputeBackedgeTakenCountExhaustively(L, ExitCond, !L->contains(TBB)); 03470 } 03471 03472 /// ComputeBackedgeTakenCountFromExitCondICmp - Compute the number of times the 03473 /// backedge of the specified loop will execute if its exit condition 03474 /// were a conditional branch of the ICmpInst ExitCond, TBB, and FBB. 03475 ScalarEvolution::BackedgeTakenInfo 03476 ScalarEvolution::ComputeBackedgeTakenCountFromExitCondICmp(const Loop *L, 03477 ICmpInst *ExitCond, 03478 BasicBlock *TBB, 03479 BasicBlock *FBB) { 03480 03481 // If the condition was exit on true, convert the condition to exit on false 03482 ICmpInst::Predicate Cond; 03483 if (!L->contains(FBB)) 03484 Cond = ExitCond->getPredicate(); 03485 else 03486 Cond = ExitCond->getInversePredicate(); 03487 03488 // Handle common loops like: for (X = "string"; *X; ++X) 03489 if (LoadInst *LI = dyn_cast<LoadInst>(ExitCond->getOperand(0))) 03490 if (Constant *RHS = dyn_cast<Constant>(ExitCond->getOperand(1))) { 03491 const SCEV *ItCnt = 03492 ComputeLoadConstantCompareBackedgeTakenCount(LI, RHS, L, Cond); 03493 if (!isa<SCEVCouldNotCompute>(ItCnt)) { 03494 unsigned BitWidth = getTypeSizeInBits(ItCnt->getType()); 03495 return BackedgeTakenInfo(ItCnt, 03496 isa<SCEVConstant>(ItCnt) ? ItCnt : 03497 getConstant(APInt::getMaxValue(BitWidth)-1)); 03498 } 03499 } 03500 03501 const SCEV *LHS = getSCEV(ExitCond->getOperand(0)); 03502 const SCEV *RHS = getSCEV(ExitCond->getOperand(1)); 03503 03504 // Try to evaluate any dependencies out of the loop. 03505 LHS = getSCEVAtScope(LHS, L); 03506 RHS = getSCEVAtScope(RHS, L); 03507 03508 // At this point, we would like to compute how many iterations of the 03509 // loop the predicate will return true for these inputs. 03510 if (LHS->isLoopInvariant(L) && !RHS->isLoopInvariant(L)) { 03511 // If there is a loop-invariant, force it into the RHS. 03512 std::swap(LHS, RHS); 03513 Cond = ICmpInst::getSwappedPredicate(Cond); 03514 } 03515 03516 // If we have a comparison of a chrec against a constant, try to use value 03517 // ranges to answer this query. 03518 if (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS)) 03519 if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(LHS)) 03520 if (AddRec->getLoop() == L) { 03521 // Form the constant range. 03522 ConstantRange CompRange( 03523 ICmpInst::makeConstantRange(Cond, RHSC->getValue()->getValue())); 03524 03525 const SCEV *Ret = AddRec->getNumIterationsInRange(CompRange, *this); 03526 if (!isa<SCEVCouldNotCompute>(Ret)) return Ret; 03527 } 03528 03529 switch (Cond) { 03530 case ICmpInst::ICMP_NE: { // while (X != Y) 03531 // Convert to: while (X-Y != 0) 03532 const SCEV *TC = HowFarToZero(getMinusSCEV(LHS, RHS), L); 03533 if (!isa<SCEVCouldNotCompute>(TC)) return TC; 03534 break; 03535 } 03536 case ICmpInst::ICMP_EQ: { // while (X == Y) 03537 // Convert to: while (X-Y == 0) 03538 const SCEV *TC = HowFarToNonZero(getMinusSCEV(LHS, RHS), L); 03539 if (!isa<SCEVCouldNotCompute>(TC)) return TC; 03540 break; 03541 } 03542 case ICmpInst::ICMP_SLT: { 03543 BackedgeTakenInfo BTI = HowManyLessThans(LHS, RHS, L, true); 03544 if (BTI.hasAnyInfo()) return BTI; 03545 break; 03546 } 03547 case ICmpInst::ICMP_SGT: { 03548 BackedgeTakenInfo BTI = HowManyLessThans(getNotSCEV(LHS), 03549 getNotSCEV(RHS), L, true); 03550 if (BTI.hasAnyInfo()) return BTI; 03551 break; 03552 } 03553 case ICmpInst::ICMP_ULT: { 03554 BackedgeTakenInfo BTI = HowManyLessThans(LHS, RHS, L, false); 03555 if (BTI.hasAnyInfo()) return BTI; 03556 break; 03557 } 03558 case ICmpInst::ICMP_UGT: { 03559 BackedgeTakenInfo BTI = HowManyLessThans(getNotSCEV(LHS), 03560 getNotSCEV(RHS), L, false); 03561 if (BTI.hasAnyInfo()) return BTI; 03562 break; 03563 } 03564 default: 03565 #if 0 03566 errs() << "ComputeBackedgeTakenCount "; 03567 if (ExitCond->getOperand(0)->getType()->isUnsigned()) 03568 errs() << "[unsigned] "; 03569 errs() << *LHS << " " 03570 << Instruction::getOpcodeName(Instruction::ICmp) 03571 << " " << *RHS << "\n"; 03572 #endif 03573 break; 03574 } 03575 return 03576 ComputeBackedgeTakenCountExhaustively(L, ExitCond, !L->contains(TBB)); 03577 } 03578 03579 static ConstantInt * 03580 EvaluateConstantChrecAtConstant(const SCEVAddRecExpr *AddRec, ConstantInt *C, 03581 ScalarEvolution &SE) { 03582 const SCEV *InVal = SE.getConstant(C); 03583 const SCEV *Val = AddRec->evaluateAtIteration(InVal, SE); 03584 assert(isa<SCEVConstant>(Val) && 03585 "Evaluation of SCEV at constant didn't fold correctly?"); 03586 return cast<SCEVConstant>(Val)->getValue(); 03587 } 03588 03589 /// GetAddressedElementFromGlobal - Given a global variable with an initializer 03590 /// and a GEP expression (missing the pointer index) indexing into it, return 03591 /// the addressed element of the initializer or null if the index expression is 03592 /// invalid. 03593 static Constant * 03594 GetAddressedElementFromGlobal(LLVMContext &Context, GlobalVariable *GV, 03595 const std::vector<ConstantInt*> &Indices) { 03596 Constant *Init = GV->getInitializer(); 03597 for (unsigned i = 0, e = Indices.size(); i != e; ++i) { 03598 uint64_t Idx = Indices[i]->getZExtValue(); 03599 if (ConstantStruct *CS = dyn_cast<ConstantStruct>(Init)) { 03600 assert(Idx < CS->getNumOperands() && "Bad struct index!"); 03601 Init = cast<Constant>(CS->getOperand(Idx)); 03602 } else if (ConstantArray *CA = dyn_cast<ConstantArray>(Init)) { 03603 if (Idx >= CA->getNumOperands()) return 0; // Bogus program 03604 Init = cast<Constant>(CA->getOperand(Idx)); 03605 } else if (isa<ConstantAggregateZero>(Init)) { 03606 if (const StructType *STy = dyn_cast<StructType>(Init->getType())) { 03607 assert(Idx < STy->getNumElements() && "Bad struct index!"); 03608 Init = Constant::getNullValue(STy->getElementType(Idx)); 03609 } else if (const ArrayType *ATy = dyn_cast<ArrayType>(Init->getType())) { 03610 if (Idx >= ATy->getNumElements()) return 0; // Bogus program 03611 Init = Constant::getNullValue(ATy->getElementType()); 03612 } else { 03613 llvm_unreachable("Unknown constant aggregate type!"); 03614 } 03615 return 0; 03616 } else { 03617 return 0; // Unknown initializer type 03618 } 03619 } 03620 return Init; 03621 } 03622 03623 /// ComputeLoadConstantCompareBackedgeTakenCount - Given an exit condition of 03624 /// 'icmp op load X, cst', try to see if we can compute the backedge 03625 /// execution count. 03626 const SCEV * 03627 ScalarEvolution::ComputeLoadConstantCompareBackedgeTakenCount( 03628 LoadInst *LI, 03629 Constant *RHS, 03630 const Loop *L, 03631 ICmpInst::Predicate predicate) { 03632 if (LI->isVolatile()) return getCouldNotCompute(); 03633 03634 // Check to see if the loaded pointer is a getelementptr of a global. 03635 GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(LI->getOperand(0)); 03636 if (!GEP) return getCouldNotCompute(); 03637 03638 // Make sure that it is really a constant global we are gepping, with an 03639 // initializer, and make sure the first IDX is really 0. 03640 GlobalVariable *GV = dyn_cast<GlobalVariable>(GEP->getOperand(0)); 03641 if (!GV || !GV->isConstant() || !GV->hasDefinitiveInitializer() || 03642 GEP->getNumOperands() < 3 || !isa<Constant>(GEP->getOperand(1)) || 03643 !cast<Constant>(GEP->getOperand(1))->isNullValue()) 03644 return getCouldNotCompute(); 03645 03646 // Okay, we allow one non-constant index into the GEP instruction. 03647 Value *VarIdx = 0; 03648 std::vector<ConstantInt*> Indexes; 03649 unsigned VarIdxNum = 0; 03650 for (unsigned i = 2, e = GEP->getNumOperands(); i != e; ++i) 03651 if (ConstantInt *CI = dyn_cast<ConstantInt>(GEP->getOperand(i))) { 03652 Indexes.push_back(CI); 03653 } else if (!isa<ConstantInt>(GEP->getOperand(i))) { 03654 if (VarIdx) return getCouldNotCompute(); // Multiple non-constant idx's. 03655 VarIdx = GEP->getOperand(i); 03656 VarIdxNum = i-2; 03657 Indexes.push_back(0); 03658 } 03659 03660 // Okay, we know we have a (load (gep GV, 0, X)) comparison with a constant. 03661 // Check to see if X is a loop variant variable value now. 03662 const SCEV *Idx = getSCEV(VarIdx); 03663 Idx = getSCEVAtScope(Idx, L); 03664 03665 // We can only recognize very limited forms of loop index expressions, in 03666 // particular, only affine AddRec's like {C1,+,C2}. 03667 const SCEVAddRecExpr *IdxExpr = dyn_cast<SCEVAddRecExpr>(Idx); 03668 if (!IdxExpr || !IdxExpr->isAffine() || IdxExpr->isLoopInvariant(L) || 03669 !isa<SCEVConstant>(IdxExpr->getOperand(0)) || 03670 !isa<SCEVConstant>(IdxExpr->getOperand(1))) 03671 return getCouldNotCompute(); 03672 03673 unsigned MaxSteps = MaxBruteForceIterations; 03674 for (unsigned IterationNum = 0; IterationNum != MaxSteps; ++IterationNum) { 03675 ConstantInt *ItCst = ConstantInt::get( 03676 cast<IntegerType>(IdxExpr->getType()), IterationNum); 03677 ConstantInt *Val = EvaluateConstantChrecAtConstant(IdxExpr, ItCst, *this); 03678 03679 // Form the GEP offset. 03680 Indexes[VarIdxNum] = Val; 03681 03682 Constant *Result = GetAddressedElementFromGlobal(getContext(), GV, Indexes); 03683 if (Result == 0) break; // Cannot compute! 03684 03685 // Evaluate the condition for this iteration. 03686 Result = ConstantExpr::getICmp(predicate, Result, RHS); 03687 if (!isa<ConstantInt>(Result)) break; // Couldn't decide for sure 03688 if (cast<ConstantInt>(Result)->getValue().isMinValue()) { 03689 #if 0 03690 errs() << "\n***\n*** Computed loop count " << *ItCst 03691 << "\n*** From global " << *GV << "*** BB: " << *L->getHeader() 03692 << "***\n"; 03693 #endif 03694 ++NumArrayLenItCounts; 03695 return getConstant(ItCst); // Found terminating iteration! 03696 } 03697 } 03698 return getCouldNotCompute(); 03699 } 03700 03701 03702 /// CanConstantFold - Return true if we can constant fold an instruction of the 03703 /// specified type, assuming that all operands were constants. 03704 static bool CanConstantFold(const Instruction *I) { 03705 if (isa<BinaryOperator>(I) || isa<CmpInst>(I) || 03706 isa<SelectInst>(I) || isa<CastInst>(I) || isa<GetElementPtrInst>(I)) 03707 return true; 03708 03709 if (const CallInst *CI = dyn_cast<CallInst>(I)) 03710 if (const Function *F = CI->getCalledFunction()) 03711 return canConstantFoldCallTo(F); 03712 return false; 03713 } 03714 03715 /// getConstantEvolvingPHI - Given an LLVM value and a loop, return a PHI node 03716 /// in the loop that V is derived from. We allow arbitrary operations along the 03717 /// way, but the operands of an operation must either be constants or a value 03718 /// derived from a constant PHI. If this expression does not fit with these 03719 /// constraints, return null. 03720 static PHINode *getConstantEvolvingPHI(Value *V, const Loop *L) { 03721 // If this is not an instruction, or if this is an instruction outside of the 03722 // loop, it can't be derived from a loop PHI. 03723 Instruction *I = dyn_cast<Instruction>(V); 03724 if (I == 0 || !L->contains(I->getParent())) return 0; 03725 03726 if (PHINode *PN = dyn_cast<PHINode>(I)) { 03727 if (L->getHeader() == I->getParent()) 03728 return PN; 03729 else 03730 // We don't currently keep track of the control flow needed to evaluate 03731 // PHIs, so we cannot handle PHIs inside of loops. 03732 return 0; 03733 } 03734 03735 // If we won't be able to constant fold this expression even if the operands 03736 // are constants, return early. 03737 if (!CanConstantFold(I)) return 0; 03738 03739 // Otherwise, we can evaluate this instruction if all of its operands are 03740 // constant or derived from a PHI node themselves. 03741 PHINode *PHI = 0; 03742 for (unsigned Op = 0, e = I->getNumOperands(); Op != e; ++Op) 03743 if (!(isa<Constant>(I->getOperand(Op)) || 03744 isa<GlobalValue>(I->getOperand(Op)))) { 03745 PHINode *P = getConstantEvolvingPHI(I->getOperand(Op), L); 03746 if (P == 0) return 0; // Not evolving from PHI 03747 if (PHI == 0) 03748 PHI = P; 03749 else if (PHI != P) 03750 return 0; // Evolving from multiple different PHIs. 03751 } 03752 03753 // This is a expression evolving from a constant PHI! 03754 return PHI; 03755 } 03756 03757 /// EvaluateExpression - Given an expression that passes the 03758 /// getConstantEvolvingPHI predicate, evaluate its value assuming the PHI node 03759 /// in the loop has the value PHIVal. If we can't fold this expression for some 03760 /// reason, return null. 03761 static Constant *EvaluateExpression(Value *V, Constant *PHIVal) { 03762 if (isa<PHINode>(V)) return PHIVal; 03763 if (Constant *C = dyn_cast<Constant>(V)) return C; 03764 if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) return GV; 03765 Instruction *I = cast<Instruction>(V); 03766 LLVMContext &Context = I->getParent()->getContext(); 03767 03768 std::vector<Constant*> Operands; 03769 Operands.resize(I->getNumOperands()); 03770 03771 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 03772 Operands[i] = EvaluateExpression(I->getOperand(i), PHIVal); 03773 if (Operands[i] == 0) return 0; 03774 } 03775 03776 if (const CmpInst *CI = dyn_cast<CmpInst>(I)) 03777 return ConstantFoldCompareInstOperands(CI->getPredicate(), 03778 &Operands[0], Operands.size(), 03779 Context); 03780 else 03781 return ConstantFoldInstOperands(I->getOpcode(), I->getType(), 03782 &Operands[0], Operands.size(), 03783 Context); 03784 } 03785 03786 /// getConstantEvolutionLoopExitValue - If we know that the specified Phi is 03787 /// in the header of its containing loop, we know the loop executes a 03788 /// constant number of times, and the PHI node is just a recurrence 03789 /// involving constants, fold it. 03790 Constant * 03791 ScalarEvolution::getConstantEvolutionLoopExitValue(PHINode *PN, 03792 const APInt& BEs, 03793 const Loop *L) { 03794 std::map<PHINode*, Constant*>::iterator I = 03795 ConstantEvolutionLoopExitValue.find(PN); 03796 if (I != ConstantEvolutionLoopExitValue.end()) 03797 return I->second; 03798 03799 if (BEs.ugt(APInt(BEs.getBitWidth(),MaxBruteForceIterations))) 03800 return ConstantEvolutionLoopExitValue[PN] = 0; // Not going to evaluate it. 03801 03802 Constant *&RetVal = ConstantEvolutionLoopExitValue[PN]; 03803 03804 // Since the loop is canonicalized, the PHI node must have two entries. One 03805 // entry must be a constant (coming in from outside of the loop), and the 03806 // second must be derived from the same PHI. 03807 bool SecondIsBackedge = L->contains(PN->getIncomingBlock(1)); 03808 Constant *StartCST = 03809 dyn_cast<Constant>(PN->getIncomingValue(!SecondIsBackedge)); 03810 if (StartCST == 0) 03811 return RetVal = 0; // Must be a constant. 03812 03813 Value *BEValue = PN->getIncomingValue(SecondIsBackedge); 03814 PHINode *PN2 = getConstantEvolvingPHI(BEValue, L); 03815 if (PN2 != PN) 03816 return RetVal = 0; // Not derived from same PHI. 03817 03818 // Execute the loop symbolically to determine the exit value. 03819 if (BEs.getActiveBits() >= 32) 03820 return RetVal = 0; // More than 2^32-1 iterations?? Not doing it! 03821 03822 unsigned NumIterations = BEs.getZExtValue(); // must be in range 03823 unsigned IterationNum = 0; 03824 for (Constant *PHIVal = StartCST; ; ++IterationNum) { 03825 if (IterationNum == NumIterations) 03826 return RetVal = PHIVal; // Got exit value! 03827 03828 // Compute the value of the PHI node for the next iteration. 03829 Constant *NextPHI = EvaluateExpression(BEValue, PHIVal); 03830 if (NextPHI == PHIVal) 03831 return RetVal = NextPHI; // Stopped evolving! 03832 if (NextPHI == 0) 03833 return 0; // Couldn't evaluate! 03834 PHIVal = NextPHI; 03835 } 03836 } 03837 03838 /// ComputeBackedgeTakenCountExhaustively - If the loop is known to execute a 03839 /// constant number of times (the condition evolves only from constants), 03840 /// try to evaluate a few iterations of the loop until we get the exit 03841 /// condition gets a value of ExitWhen (true or false). If we cannot 03842 /// evaluate the trip count of the loop, return getCouldNotCompute(). 03843 const SCEV * 03844 ScalarEvolution::ComputeBackedgeTakenCountExhaustively(const Loop *L, 03845 Value *Cond, 03846 bool ExitWhen) { 03847 PHINode *PN = getConstantEvolvingPHI(Cond, L); 03848 if (PN == 0) return getCouldNotCompute(); 03849 03850 // Since the loop is canonicalized, the PHI node must have two entries. One 03851 // entry must be a constant (coming in from outside of the loop), and the 03852 // second must be derived from the same PHI. 03853 bool SecondIsBackedge = L->contains(PN->getIncomingBlock(1)); 03854 Constant *StartCST = 03855 dyn_cast<Constant>(PN->getIncomingValue(!SecondIsBackedge)); 03856 if (StartCST == 0) return getCouldNotCompute(); // Must be a constant. 03857 03858 Value *BEValue = PN->getIncomingValue(SecondIsBackedge); 03859 PHINode *PN2 = getConstantEvolvingPHI(BEValue, L); 03860 if (PN2 != PN) return getCouldNotCompute(); // Not derived from same PHI. 03861 03862 // Okay, we find a PHI node that defines the trip count of this loop. Execute 03863 // the loop symbolically to determine when the condition gets a value of 03864 // "ExitWhen". 03865 unsigned IterationNum = 0; 03866 unsigned MaxIterations = MaxBruteForceIterations; // Limit analysis. 03867 for (Constant *PHIVal = StartCST; 03868 IterationNum != MaxIterations; ++IterationNum) { 03869 ConstantInt *CondVal = 03870 dyn_cast_or_null<ConstantInt>(EvaluateExpression(Cond, PHIVal)); 03871 03872 // Couldn't symbolically evaluate. 03873 if (!CondVal) return getCouldNotCompute(); 03874 03875 if (CondVal->getValue() == uint64_t(ExitWhen)) { 03876 ++NumBruteForceTripCountsComputed; 03877 return getConstant(Type::getInt32Ty(getContext()), IterationNum); 03878 } 03879 03880 // Compute the value of the PHI node for the next iteration. 03881 Constant *NextPHI = EvaluateExpression(BEValue, PHIVal); 03882 if (NextPHI == 0 || NextPHI == PHIVal) 03883 return getCouldNotCompute();// Couldn't evaluate or not making progress... 03884 PHIVal = NextPHI; 03885 } 03886 03887 // Too many iterations were needed to evaluate. 03888 return getCouldNotCompute(); 03889 } 03890 03891 /// getSCEVAtScope - Return a SCEV expression handle for the specified value 03892 /// at the specified scope in the program. The L value specifies a loop 03893 /// nest to evaluate the expression at, where null is the top-level or a 03894 /// specified loop is immediately inside of the loop. 03895 /// 03896 /// This method can be used to compute the exit value for a variable defined 03897 /// in a loop by querying what the value will hold in the parent loop. 03898 /// 03899 /// In the case that a relevant loop exit value cannot be computed, the 03900 /// original value V is returned. 03901 const SCEV *ScalarEvolution::getSCEVAtScope(const SCEV *V, const Loop *L) { 03902 // FIXME: this should be turned into a virtual method on SCEV! 03903 03904 if (isa<SCEVConstant>(V)) return V; 03905 03906 // If this instruction is evolved from a constant-evolving PHI, compute the 03907 // exit value from the loop without using SCEVs. 03908 if (const SCEVUnknown *SU = dyn_cast<SCEVUnknown>(V)) { 03909 if (Instruction *I = dyn_cast<Instruction>(SU->getValue())) { 03910 const Loop *LI = (*this->LI)[I->getParent()]; 03911 if (LI && LI->getParentLoop() == L) // Looking for loop exit value. 03912 if (PHINode *PN = dyn_cast<PHINode>(I)) 03913 if (PN->getParent() == LI->getHeader()) { 03914 // Okay, there is no closed form solution for the PHI node. Check 03915 // to see if the loop that contains it has a known backedge-taken 03916 // count. If so, we may be able to force computation of the exit 03917 // value. 03918 const SCEV *BackedgeTakenCount = getBackedgeTakenCount(LI); 03919 if (const SCEVConstant *BTCC = 03920 dyn_cast<SCEVConstant>(BackedgeTakenCount)) { 03921 // Okay, we know how many times the containing loop executes. If 03922 // this is a constant evolving PHI node, get the final value at 03923 // the specified iteration number. 03924 Constant *RV = getConstantEvolutionLoopExitValue(PN, 03925 BTCC->getValue()->getValue(), 03926 LI); 03927 if (RV) return getSCEV(RV); 03928 } 03929 } 03930 03931 // Okay, this is an expression that we cannot symbolically evaluate 03932 // into a SCEV. Check to see if it's possible to symbolically evaluate 03933 // the arguments into constants, and if so, try to constant propagate the 03934 // result. This is particularly useful for computing loop exit values. 03935 if (CanConstantFold(I)) { 03936 // Check to see if we've folded this instruction at this loop before. 03937 std::map<const Loop *, Constant *> &Values = ValuesAtScopes[I]; 03938 std::pair<std::map<const Loop *, Constant *>::iterator, bool> Pair = 03939 Values.insert(std::make_pair(L, static_cast<Constant *>(0))); 03940 if (!Pair.second) 03941 return Pair.first->second ? &*getSCEV(Pair.first->second) : V; 03942 03943 std::vector<Constant*> Operands; 03944 Operands.reserve(I->getNumOperands()); 03945 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 03946 Value *Op = I->getOperand(i); 03947 if (Constant *C = dyn_cast<Constant>(Op)) { 03948 Operands.push_back(C); 03949 } else { 03950 // If any of the operands is non-constant and if they are 03951 // non-integer and non-pointer, don't even try to analyze them 03952 // with scev techniques. 03953 if (!isSCEVable(Op->getType())) 03954 return V; 03955 03956 const SCEV* OpV = getSCEVAtScope(Op, L); 03957 if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(OpV)) { 03958 Constant *C = SC->getValue(); 03959 if (C->getType() != Op->getType()) 03960 C = ConstantExpr::getCast(CastInst::getCastOpcode(C, false, 03961 Op->getType(), 03962 false), 03963 C, Op->getType()); 03964 Operands.push_back(C); 03965 } else if (const SCEVUnknown *SU = dyn_cast<SCEVUnknown>(OpV)) { 03966 if (Constant *C = dyn_cast<Constant>(SU->getValue())) { 03967 if (C->getType() != Op->getType()) 03968 C = 03969 ConstantExpr::getCast(CastInst::getCastOpcode(C, false, 03970 Op->getType(), 03971 false), 03972 C, Op->getType()); 03973 Operands.push_back(C); 03974 } else 03975 return V; 03976 } else { 03977 return V; 03978 } 03979 } 03980 } 03981 03982 Constant *C; 03983 if (const CmpInst *CI = dyn_cast<CmpInst>(I)) 03984 C = ConstantFoldCompareInstOperands(CI->getPredicate(), 03985 &Operands[0], Operands.size(), 03986 getContext()); 03987 else 03988 C = ConstantFoldInstOperands(I->getOpcode(), I->getType(), 03989 &Operands[0], Operands.size(), 03990 getContext()); 03991 Pair.first->second = C; 03992 return getSCEV(C); 03993 } 03994 } 03995 03996 // This is some other type of SCEVUnknown, just return it. 03997 return V; 03998 } 03999 04000 if (const SCEVCommutativeExpr *Comm = dyn_cast<SCEVCommutativeExpr>(V)) { 04001 // Avoid performing the look-up in the common case where the specified 04002 // expression has no loop-variant portions. 04003 for (unsigned i = 0, e = Comm->getNumOperands(); i != e; ++i) { 04004 const SCEV *OpAtScope = getSCEVAtScope(Comm->getOperand(i), L); 04005 if (OpAtScope != Comm->getOperand(i)) { 04006 // Okay, at least one of these operands is loop variant but might be 04007 // foldable. Build a new instance of the folded commutative expression. 04008 SmallVector<const SCEV *, 8> NewOps(Comm->op_begin(), 04009 Comm->op_begin()+i); 04010 NewOps.push_back(OpAtScope); 04011 04012 for (++i; i != e; ++i) { 04013 OpAtScope = getSCEVAtScope(Comm->getOperand(i), L); 04014 NewOps.push_back(OpAtScope); 04015 } 04016 if (isa<SCEVAddExpr>(Comm)) 04017 return getAddExpr(NewOps); 04018 if (isa<SCEVMulExpr>(Comm)) 04019 return getMulExpr(NewOps); 04020 if (isa<SCEVSMaxExpr>(Comm)) 04021 return getSMaxExpr(NewOps); 04022 if (isa<SCEVUMaxExpr>(Comm)) 04023 return getUMaxExpr(NewOps); 04024 llvm_unreachable("Unknown commutative SCEV type!"); 04025 } 04026 } 04027 // If we got here, all operands are loop invariant. 04028 return Comm; 04029 } 04030 04031 if (const SCEVUDivExpr *Div = dyn_cast<SCEVUDivExpr>(V)) { 04032 const SCEV *LHS = getSCEVAtScope(Div->getLHS(), L); 04033 const SCEV *RHS = getSCEVAtScope(Div->getRHS(), L); 04034 if (LHS == Div->getLHS() && RHS == Div->getRHS()) 04035 return Div; // must be loop invariant 04036 return getUDivExpr(LHS, RHS); 04037 } 04038 04039 // If this is a loop recurrence for a loop that does not contain L, then we 04040 // are dealing with the final value computed by the loop. 04041 if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(V)) { 04042 if (!L || !AddRec->getLoop()->contains(L->getHeader())) { 04043 // To evaluate this recurrence, we need to know how many times the AddRec 04044 // loop iterates. Compute this now. 04045 const SCEV *BackedgeTakenCount = getBackedgeTakenCount(AddRec->getLoop()); 04046 if (BackedgeTakenCount == getCouldNotCompute()) return AddRec; 04047 04048 // Then, evaluate the AddRec. 04049 return AddRec->evaluateAtIteration(BackedgeTakenCount, *this); 04050 } 04051 return AddRec; 04052 } 04053 04054 if (const SCEVZeroExtendExpr *Cast = dyn_cast<SCEVZeroExtendExpr>(V)) { 04055 const SCEV *Op = getSCEVAtScope(Cast->getOperand(), L); 04056 if (Op == Cast->getOperand()) 04057 return Cast; // must be loop invariant 04058 return getZeroExtendExpr(Op, Cast->getType()); 04059 } 04060 04061 if (const SCEVSignExtendExpr *Cast = dyn_cast<SCEVSignExtendExpr>(V)) { 04062 const SCEV *Op = getSCEVAtScope(Cast->getOperand(), L); 04063 if (Op == Cast->getOperand()) 04064 return Cast; // must be loop invariant 04065 return getSignExtendExpr(Op, Cast->getType()); 04066 } 04067 04068 if (const SCEVTruncateExpr *Cast = dyn_cast<SCEVTruncateExpr>(V)) { 04069 const SCEV *Op = getSCEVAtScope(Cast->getOperand(), L); 04070 if (Op == Cast->getOperand()) 04071 return Cast; // must be loop invariant 04072 return getTruncateExpr(Op, Cast->getType()); 04073 } 04074 04075 if (isa<SCEVTargetDataConstant>(V)) 04076 return V; 04077 04078 llvm_unreachable("Unknown SCEV type!"); 04079 return 0; 04080 } 04081 04082 /// getSCEVAtScope - This is a convenience function which does 04083 /// getSCEVAtScope(getSCEV(V), L). 04084 const SCEV *ScalarEvolution::getSCEVAtScope(Value *V, const Loop *L) { 04085 return getSCEVAtScope(getSCEV(V), L); 04086 } 04087 04088 /// SolveLinEquationWithOverflow - Finds the minimum unsigned root of the 04089 /// following equation: 04090 /// 04091 /// A * X = B (mod N) 04092 /// 04093 /// where N = 2^BW and BW is the common bit width of A and B. The signedness of 04094 /// A and B isn't important. 04095 /// 04096 /// If the equation does not have a solution, SCEVCouldNotCompute is returned. 04097 static const SCEV *SolveLinEquationWithOverflow(const APInt &A, const APInt &B, 04098 ScalarEvolution &SE) { 04099 uint32_t BW = A.getBitWidth(); 04100 assert(BW == B.getBitWidth() && "Bit widths must be the same."); 04101 assert(A != 0 && "A must be non-zero."); 04102 04103 // 1. D = gcd(A, N) 04104 // 04105 // The gcd of A and N may have only one prime factor: 2. The number of 04106 // trailing zeros in A is its multiplicity 04107 uint32_t Mult2 = A.countTrailingZeros(); 04108 // D = 2^Mult2 04109 04110 // 2. Check if B is divisible by D. 04111 // 04112 // B is divisible by D if and only if the multiplicity of prime factor 2 for B 04113 // is not less than multiplicity of this prime factor for D. 04114 if (B.countTrailingZeros() < Mult2) 04115 return SE.getCouldNotCompute(); 04116 04117 // 3. Compute I: the multiplicative inverse of (A / D) in arithmetic 04118 // modulo (N / D). 04119 // 04120 // (N / D) may need BW+1 bits in its representation. Hence, we'll use this 04121 // bit width during computations. 04122 APInt AD = A.lshr(Mult2).zext(BW + 1); // AD = A / D 04123 APInt Mod(BW + 1, 0); 04124 Mod.set(BW - Mult2); // Mod = N / D 04125 APInt I = AD.multiplicativeInverse(Mod); 04126 04127 // 4. Compute the minimum unsigned root of the equation: 04128 // I * (B / D) mod (N / D) 04129 APInt Result = (I * B.lshr(Mult2).zext(BW + 1)).urem(Mod); 04130 04131 // The result is guaranteed to be less than 2^BW so we may truncate it to BW 04132 // bits. 04133 return SE.getConstant(Result.trunc(BW)); 04134 } 04135 04136 /// SolveQuadraticEquation - Find the roots of the quadratic equation for the 04137 /// given quadratic chrec {L,+,M,+,N}. This returns either the two roots (which 04138 /// might be the same) or two SCEVCouldNotCompute objects. 04139 /// 04140 static std::pair<const SCEV *,const SCEV *> 04141 SolveQuadraticEquation(const SCEVAddRecExpr *AddRec, ScalarEvolution &SE) { 04142 assert(AddRec->getNumOperands() == 3 && "This is not a quadratic chrec!"); 04143 const SCEVConstant *LC = dyn_cast<SCEVConstant>(AddRec->getOperand(0)); 04144 const SCEVConstant *MC = dyn_cast<SCEVConstant>(AddRec->getOperand(1)); 04145 const SCEVConstant *NC = dyn_cast<SCEVConstant>(AddRec->getOperand(2)); 04146 04147 // We currently can only solve this if the coefficients are constants. 04148 if (!LC || !MC || !NC) { 04149 const SCEV *CNC = SE.getCouldNotCompute(); 04150 return std::make_pair(CNC, CNC); 04151 } 04152 04153 uint32_t BitWidth = LC->getValue()->getValue().getBitWidth(); 04154 const APInt &L = LC->getValue()->getValue(); 04155 const APInt &M = MC->getValue()->getValue(); 04156 const APInt &N = NC->getValue()->getValue(); 04157 APInt Two(BitWidth, 2); 04158 APInt Four(BitWidth, 4); 04159 04160 { 04161 using namespace APIntOps; 04162 const APInt& C = L; 04163 // Convert from chrec coefficients to polynomial coefficients AX^2+BX+C 04164 // The B coefficient is M-N/2 04165 APInt B(M); 04166 B -= sdiv(N,Two); 04167 04168 // The A coefficient is N/2 04169 APInt A(N.sdiv(Two)); 04170 04171 // Compute the B^2-4ac term. 04172 APInt SqrtTerm(B); 04173 SqrtTerm *= B; 04174 SqrtTerm -= Four * (A * C); 04175 04176 // Compute sqrt(B^2-4ac). This is guaranteed to be the nearest 04177 // integer value or else APInt::sqrt() will assert. 04178 APInt SqrtVal(SqrtTerm.sqrt()); 04179 04180 // Compute the two solutions for the quadratic formula. 04181 // The divisions must be performed as signed divisions. 04182 APInt NegB(-B); 04183 APInt TwoA( A << 1 ); 04184 if (TwoA.isMinValue()) { 04185 const SCEV *CNC = SE.getCouldNotCompute(); 04186 return std::make_pair(CNC, CNC); 04187 } 04188 04189 LLVMContext &Context = SE.getContext(); 04190 04191 ConstantInt *Solution1 = 04192 ConstantInt::get(Context, (NegB + SqrtVal).sdiv(TwoA)); 04193 ConstantInt *Solution2 = 04194 ConstantInt::get(Context, (NegB - SqrtVal).sdiv(TwoA)); 04195 04196 return std::make_pair(SE.getConstant(Solution1), 04197 SE.getConstant(Solution2)); 04198 } // end APIntOps namespace 04199 } 04200 04201 /// HowFarToZero - Return the number of times a backedge comparing the specified 04202 /// value to zero will execute. If not computable, return CouldNotCompute. 04203 const SCEV *ScalarEvolution::HowFarToZero(const SCEV *V, const Loop *L) { 04204 // If the value is a constant 04205 if (const SCEVConstant *C = dyn_cast<SCEVConstant>(V)) { 04206 // If the value is already zero, the branch will execute zero times. 04207 if (C->getValue()->isZero()) return C; 04208 return getCouldNotCompute(); // Otherwise it will loop infinitely. 04209 } 04210 04211 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(V); 04212 if (!AddRec || AddRec->getLoop() != L) 04213 return getCouldNotCompute(); 04214 04215 if (AddRec->isAffine()) { 04216 // If this is an affine expression, the execution count of this branch is 04217 // the minimum unsigned root of the following equation: 04218 // 04219 // Start + Step*N = 0 (mod 2^BW) 04220 // 04221 // equivalent to: 04222 // 04223 // Step*N = -Start (mod 2^BW) 04224 // 04225 // where BW is the common bit width of Start and Step. 04226 04227 // Get the initial value for the loop. 04228 const SCEV *Start = getSCEVAtScope(AddRec->getStart(), 04229 L->getParentLoop()); 04230 const SCEV *Step = getSCEVAtScope(AddRec->getOperand(1), 04231 L->getParentLoop()); 04232 04233 if (const SCEVConstant *StepC = dyn_cast<SCEVConstant>(Step)) { 04234 // For now we handle only constant steps. 04235 04236 // First, handle unitary steps. 04237 if (StepC->getValue()->equalsInt(1)) // 1*N = -Start (mod 2^BW), so: 04238 return getNegativeSCEV(Start); // N = -Start (as unsigned) 04239 if (StepC->getValue()->isAllOnesValue()) // -1*N = -Start (mod 2^BW), so: 04240 return Start; // N = Start (as unsigned) 04241 04242 // Then, try to solve the above equation provided that Start is constant. 04243 if (const SCEVConstant *StartC = dyn_cast<SCEVConstant>(Start)) 04244 return SolveLinEquationWithOverflow(StepC->getValue()->getValue(), 04245 -StartC->getValue()->getValue(), 04246 *this); 04247 } 04248 } else if (AddRec->isQuadratic() && AddRec->getType()->isInteger()) { 04249 // If this is a quadratic (3-term) AddRec {L,+,M,+,N}, find the roots of 04250 // the quadratic equation to solve it. 04251 std::pair<const SCEV *,const SCEV *> Roots = SolveQuadraticEquation(AddRec, 04252 *this); 04253 const SCEVConstant *R1 = dyn_cast<SCEVConstant>(Roots.first); 04254 const SCEVConstant *R2 = dyn_cast<SCEVConstant>(Roots.second); 04255 if (R1) { 04256 #if 0 04257 errs() << "HFTZ: " << *V << " - sol#1: " << *R1 04258 << " sol#2: " << *R2 << "\n"; 04259 #endif 04260 // Pick the smallest positive root value. 04261 if (ConstantInt *CB = 04262 dyn_cast<ConstantInt>(ConstantExpr::getICmp(ICmpInst::ICMP_ULT, 04263 R1->getValue(), R2->getValue()))) { 04264 if (CB->getZExtValue() == false) 04265 std::swap(R1, R2); // R1 is the minimum root now. 04266 04267 // We can only use this value if the chrec ends up with an exact zero 04268 // value at this index. When solving for "X*X != 5", for example, we 04269 // should not accept a root of 2. 04270 const SCEV *Val = AddRec->evaluateAtIteration(R1, *this); 04271 if (Val->isZero()) 04272 return R1; // We found a quadratic root! 04273 } 04274 } 04275 } 04276 04277 return getCouldNotCompute(); 04278 } 04279 04280 /// HowFarToNonZero - Return the number of times a backedge checking the 04281 /// specified value for nonzero will execute. If not computable, return 04282 /// CouldNotCompute 04283 const SCEV *ScalarEvolution::HowFarToNonZero(const SCEV *V, const Loop *L) { 04284 // Loops that look like: while (X == 0) are very strange indeed. We don't 04285 // handle them yet except for the trivial case. This could be expanded in the 04286 // future as needed. 04287 04288 // If the value is a constant, check to see if it is known to be non-zero 04289 // already. If so, the backedge will execute zero times. 04290 if (const SCEVConstant *C = dyn_cast<SCEVConstant>(V)) { 04291 if (!C->getValue()->isNullValue()) 04292 return getIntegerSCEV(0, C->getType()); 04293 return getCouldNotCompute(); // Otherwise it will loop infinitely. 04294 } 04295 04296 // We could implement others, but I really doubt anyone writes loops like 04297 // this, and if they did, they would already be constant folded. 04298 return getCouldNotCompute(); 04299 } 04300 04301 /// getLoopPredecessor - If the given loop's header has exactly one unique 04302 /// predecessor outside the loop, return it. Otherwise return null. 04303 /// 04304 BasicBlock *ScalarEvolution::getLoopPredecessor(const Loop *L) { 04305 BasicBlock *Header = L->getHeader(); 04306 BasicBlock *Pred = 0; 04307 for (pred_iterator PI = pred_begin(Header), E = pred_end(Header); 04308 PI != E; ++PI) 04309 if (!L->contains(*PI)) { 04310 if (Pred && Pred != *PI) return 0; // Multiple predecessors. 04311 Pred = *PI; 04312 } 04313 return Pred; 04314 } 04315 04316 /// getPredecessorWithUniqueSuccessorForBB - Return a predecessor of BB 04317 /// (which may not be an immediate predecessor) which has exactly one 04318 /// successor from which BB is reachable, or null if no such block is 04319 /// found. 04320 /// 04321 BasicBlock * 04322 ScalarEvolution::getPredecessorWithUniqueSuccessorForBB(BasicBlock *BB) { 04323 // If the block has a unique predecessor, then there is no path from the 04324 // predecessor to the block that does not go through the direct edge 04325 // from the predecessor to the block. 04326 if (BasicBlock *Pred = BB->getSinglePredecessor()) 04327 return Pred; 04328 04329 // A loop's header is defined to be a block that dominates the loop. 04330 // If the header has a unique predecessor outside the loop, it must be 04331 // a block that has exactly one successor that can reach the loop. 04332 if (Loop *L = LI->getLoopFor(BB)) 04333 return getLoopPredecessor(L); 04334 04335 return 0; 04336 } 04337 04338 /// HasSameValue - SCEV structural equivalence is usually sufficient for 04339 /// testing whether two expressions are equal, however for the purposes of 04340 /// looking for a condition guarding a loop, it can be useful to be a little 04341 /// more general, since a front-end may have replicated the controlling 04342 /// expression. 04343 /// 04344 static bool HasSameValue(const SCEV *A, const SCEV *B) { 04345 // Quick check to see if they are the same SCEV. 04346 if (A == B) return true; 04347 04348 // Otherwise, if they're both SCEVUnknown, it's possible that they hold 04349 // two different instructions with the same value. Check for this case. 04350 if (const SCEVUnknown *AU = dyn_cast<SCEVUnknown>(A)) 04351 if (const SCEVUnknown *BU = dyn_cast<SCEVUnknown>(B)) 04352 if (const Instruction *AI = dyn_cast<Instruction>(AU->getValue())) 04353 if (const Instruction *BI = dyn_cast<Instruction>(BU->getValue())) 04354 if (AI->isIdenticalTo(BI)) 04355 return true; 04356 04357 // Otherwise assume they may have a different value. 04358 return false; 04359 } 04360 04361 bool ScalarEvolution::isKnownNegative(const SCEV *S) { 04362 return getSignedRange(S).getSignedMax().isNegative(); 04363 } 04364 04365 bool ScalarEvolution::isKnownPositive(const SCEV *S) { 04366 return getSignedRange(S).getSignedMin().isStrictlyPositive(); 04367 } 04368 04369 bool ScalarEvolution::isKnownNonNegative(const SCEV *S) { 04370 return !getSignedRange(S).getSignedMin().isNegative(); 04371 } 04372 04373 bool ScalarEvolution::isKnownNonPositive(const SCEV *S) { 04374 return !getSignedRange(S).getSignedMax().isStrictlyPositive(); 04375 } 04376 04377 bool ScalarEvolution::isKnownNonZero(const SCEV *S) { 04378 return isKnownNegative(S) || isKnownPositive(S); 04379 } 04380 04381 bool ScalarEvolution::isKnownPredicate(ICmpInst::Predicate Pred, 04382 const SCEV *LHS, const SCEV *RHS) { 04383 04384 if (HasSameValue(LHS, RHS)) 04385 return ICmpInst::isTrueWhenEqual(Pred); 04386 04387 switch (Pred) { 04388 default: 04389 llvm_unreachable("Unexpected ICmpInst::Predicate value!"); 04390 break; 04391 case ICmpInst::ICMP_SGT: 04392 Pred = ICmpInst::ICMP_SLT; 04393 std::swap(LHS, RHS); 04394 case ICmpInst::ICMP_SLT: { 04395 ConstantRange LHSRange = getSignedRange(LHS); 04396 ConstantRange RHSRange = getSignedRange(RHS); 04397 if (LHSRange.getSignedMax().slt(RHSRange.getSignedMin())) 04398 return true; 04399 if (LHSRange.getSignedMin().sge(RHSRange.getSignedMax())) 04400 return false; 04401 break; 04402 } 04403 case ICmpInst::ICMP_SGE: 04404 Pred = ICmpInst::ICMP_SLE; 04405 std::swap(LHS, RHS); 04406 case ICmpInst::ICMP_SLE: { 04407 ConstantRange LHSRange = getSignedRange(LHS); 04408 ConstantRange RHSRange = getSignedRange(RHS); 04409 if (LHSRange.getSignedMax().sle(RHSRange.getSignedMin())) 04410 return true; 04411 if (LHSRange.getSignedMin().sgt(RHSRange.getSignedMax())) 04412 return false; 04413 break; 04414 } 04415 case ICmpInst::ICMP_UGT: 04416 Pred = ICmpInst::ICMP_ULT; 04417 std::swap(LHS, RHS); 04418 case ICmpInst::ICMP_ULT: { 04419 ConstantRange LHSRange = getUnsignedRange(LHS); 04420 ConstantRange RHSRange = getUnsignedRange(RHS); 04421 if (LHSRange.getUnsignedMax().ult(RHSRange.getUnsignedMin())) 04422 return true; 04423 if (LHSRange.getUnsignedMin().uge(RHSRange.getUnsignedMax())) 04424 return false; 04425 break; 04426 } 04427 case ICmpInst::ICMP_UGE: 04428 Pred = ICmpInst::ICMP_ULE; 04429 std::swap(LHS, RHS); 04430 case ICmpInst::ICMP_ULE: { 04431 ConstantRange LHSRange = getUnsignedRange(LHS); 04432 ConstantRange RHSRange = getUnsignedRange(RHS); 04433 if (LHSRange.getUnsignedMax().ule(RHSRange.getUnsignedMin())) 04434 return true; 04435 if (LHSRange.getUnsignedMin().ugt(RHSRange.getUnsignedMax())) 04436 return false; 04437 break; 04438 } 04439 case ICmpInst::ICMP_NE: { 04440 if (getUnsignedRange(LHS).intersectWith(getUnsignedRange(RHS)).isEmptySet()) 04441 return true; 04442 if (getSignedRange(LHS).intersectWith(getSignedRange(RHS)).isEmptySet()) 04443 return true; 04444 04445 const SCEV *Diff = getMinusSCEV(LHS, RHS); 04446 if (isKnownNonZero(Diff)) 04447 return true; 04448 break; 04449 } 04450 case ICmpInst::ICMP_EQ: 04451 // The check at the top of the function catches the case where 04452 // the values are known to be equal. 04453 break; 04454 } 04455 return false; 04456 } 04457 04458 /// isLoopBackedgeGuardedByCond - Test whether the backedge of the loop is 04459 /// protected by a conditional between LHS and RHS. This is used to 04460 /// to eliminate casts. 04461 bool 04462 ScalarEvolution::isLoopBackedgeGuardedByCond(const Loop *L, 04463 ICmpInst::Predicate Pred, 04464 const SCEV *LHS, const SCEV *RHS) { 04465 // Interpret a null as meaning no loop, where there is obviously no guard 04466 // (interprocedural conditions notwithstanding). 04467 if (!L) return true; 04468 04469 BasicBlock *Latch = L->getLoopLatch(); 04470 if (!Latch) 04471 return false; 04472 04473 BranchInst *LoopContinuePredicate = 04474 dyn_cast<BranchInst>(Latch->getTerminator()); 04475 if (!LoopContinuePredicate || 04476 LoopContinuePredicate->isUnconditional()) 04477 return false; 04478 04479 return isImpliedCond(LoopContinuePredicate->getCondition(), Pred, LHS, RHS, 04480 LoopContinuePredicate->getSuccessor(0) != L->getHeader()); 04481 } 04482 04483 /// isLoopGuardedByCond - Test whether entry to the loop is protected 04484 /// by a conditional between LHS and RHS. This is used to help avoid max 04485 /// expressions in loop trip counts, and to eliminate casts. 04486 bool 04487 ScalarEvolution::isLoopGuardedByCond(const Loop *L, 04488 ICmpInst::Predicate Pred, 04489 const SCEV *LHS, const SCEV *RHS) { 04490 // Interpret a null as meaning no loop, where there is obviously no guard 04491 // (interprocedural conditions notwithstanding). 04492 if (!L) return false; 04493 04494 BasicBlock *Predecessor = getLoopPredecessor(L); 04495 BasicBlock *PredecessorDest = L->getHeader(); 04496 04497 // Starting at the loop predecessor, climb up the predecessor chain, as long 04498 // as there are predecessors that can be found that have unique successors 04499 // leading to the original header. 04500 for (; Predecessor; 04501 PredecessorDest = Predecessor, 04502 Predecessor = getPredecessorWithUniqueSuccessorForBB(Predecessor)) { 04503 04504 BranchInst *LoopEntryPredicate = 04505 dyn_cast<BranchInst>(Predecessor->getTerminator()); 04506 if (!LoopEntryPredicate || 04507 LoopEntryPredicate->isUnconditional()) 04508 continue; 04509 04510 if (isImpliedCond(LoopEntryPredicate->getCondition(), Pred, LHS, RHS, 04511 LoopEntryPredicate->getSuccessor(0) != PredecessorDest)) 04512 return true; 04513 } 04514 04515 return false; 04516 } 04517 04518 /// isImpliedCond - Test whether the condition described by Pred, LHS, 04519 /// and RHS is true whenever the given Cond value evaluates to true. 04520 bool ScalarEvolution::isImpliedCond(Value *CondValue, 04521 ICmpInst::Predicate Pred, 04522 const SCEV *LHS, const SCEV *RHS, 04523 bool Inverse) { 04524 // Recursivly handle And and Or conditions. 04525 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(CondValue)) { 04526 if (BO->getOpcode() == Instruction::And) { 04527 if (!Inverse) 04528 return isImpliedCond(BO->getOperand(0), Pred, LHS, RHS, Inverse) || 04529 isImpliedCond(BO->getOperand(1), Pred, LHS, RHS, Inverse); 04530 } else if (BO->getOpcode() == Instruction::Or) { 04531 if (Inverse) 04532 return isImpliedCond(BO->getOperand(0), Pred, LHS, RHS, Inverse) || 04533 isImpliedCond(BO->getOperand(1), Pred, LHS, RHS, Inverse); 04534 } 04535 } 04536 04537 ICmpInst *ICI = dyn_cast<ICmpInst>(CondValue); 04538 if (!ICI) return false; 04539 04540 // Bail if the ICmp's operands' types are wider than the needed type 04541 // before attempting to call getSCEV on them. This avoids infinite 04542 // recursion, since the analysis of widening casts can require loop 04543 // exit condition information for overflow checking, which would 04544 // lead back here. 04545 if (getTypeSizeInBits(LHS->getType()) < 04546 getTypeSizeInBits(ICI->getOperand(0)->getType())) 04547 return false; 04548 04549 // Now that we found a conditional branch that dominates the loop, check to 04550 // see if it is the comparison we are looking for. 04551 ICmpInst::Predicate FoundPred; 04552 if (Inverse) 04553 FoundPred = ICI->getInversePredicate(); 04554 else 04555 FoundPred = ICI->getPredicate(); 04556 04557 const SCEV *FoundLHS = getSCEV(ICI->getOperand(0)); 04558 const SCEV *FoundRHS = getSCEV(ICI->getOperand(1)); 04559 04560 // Balance the types. The case where FoundLHS' type is wider than 04561 // LHS' type is checked for above. 04562 if (getTypeSizeInBits(LHS->getType()) > 04563 getTypeSizeInBits(FoundLHS->getType())) { 04564 if (CmpInst::isSigned(Pred)) { 04565 FoundLHS = getSignExtendExpr(FoundLHS, LHS->getType()); 04566 FoundRHS = getSignExtendExpr(FoundRHS, LHS->getType()); 04567 } else { 04568 FoundLHS = getZeroExtendExpr(FoundLHS, LHS->getType()); 04569 FoundRHS = getZeroExtendExpr(FoundRHS, LHS->getType()); 04570 } 04571 } 04572 04573 // Canonicalize the query to match the way instcombine will have 04574 // canonicalized the comparison. 04575 // First, put a constant operand on the right. 04576 if (isa<SCEVConstant>(LHS)) { 04577 std::swap(LHS, RHS); 04578 Pred = ICmpInst::getSwappedPredicate(Pred); 04579 } 04580 // Then, canonicalize comparisons with boundary cases. 04581 if (const SCEVConstant *RC = dyn_cast<SCEVConstant>(RHS)) { 04582 const APInt &RA = RC->getValue()->getValue(); 04583 switch (Pred) { 04584 default: llvm_unreachable("Unexpected ICmpInst::Predicate value!"); 04585 case ICmpInst::ICMP_EQ: 04586 case ICmpInst::ICMP_NE: 04587 break; 04588 case ICmpInst::ICMP_UGE: 04589 if ((RA - 1).isMinValue()) { 04590 Pred = ICmpInst::ICMP_NE; 04591 RHS = getConstant(RA - 1); 04592 break; 04593 } 04594 if (RA.isMaxValue()) { 04595 Pred = ICmpInst::ICMP_EQ; 04596 break; 04597 } 04598 if (RA.isMinValue()) return true; 04599 break; 04600 case ICmpInst::ICMP_ULE: 04601 if ((RA + 1).isMaxValue()) { 04602 Pred = ICmpInst::ICMP_NE; 04603 RHS = getConstant(RA + 1); 04604 break; 04605 } 04606 if (RA.isMinValue()) { 04607 Pred = ICmpInst::ICMP_EQ; 04608 break; 04609 } 04610 if (RA.isMaxValue()) return true; 04611 break; 04612 case ICmpInst::ICMP_SGE: 04613 if ((RA - 1).isMinSignedValue()) { 04614 Pred = ICmpInst::ICMP_NE; 04615 RHS = getConstant(RA - 1); 04616 break; 04617 } 04618 if (RA.isMaxSignedValue()) { 04619 Pred = ICmpInst::ICMP_EQ; 04620 break; 04621 } 04622 if (RA.isMinSignedValue()) return true; 04623 break; 04624 case ICmpInst::ICMP_SLE: 04625 if ((RA + 1).isMaxSignedValue()) { 04626 Pred = ICmpInst::ICMP_NE; 04627 RHS = getConstant(RA + 1); 04628 break; 04629 } 04630 if (RA.isMinSignedValue()) { 04631 Pred = ICmpInst::ICMP_EQ; 04632 break; 04633 } 04634 if (RA.isMaxSignedValue()) return true; 04635 break; 04636 case ICmpInst::ICMP_UGT: 04637 if (RA.isMinValue()) { 04638 Pred = ICmpInst::ICMP_NE; 04639 break; 04640 } 04641 if ((RA + 1).isMaxValue()) { 04642 Pred = ICmpInst::ICMP_EQ; 04643 RHS = getConstant(RA + 1); 04644 break; 04645 } 04646 if (RA.isMaxValue()) return false; 04647 break; 04648 case ICmpInst::ICMP_ULT: 04649 if (RA.isMaxValue()) { 04650 Pred = ICmpInst::ICMP_NE; 04651 break; 04652 } 04653 if ((RA - 1).isMinValue()) { 04654 Pred = ICmpInst::ICMP_EQ; 04655 RHS = getConstant(RA - 1); 04656 break; 04657 } 04658 if (RA.isMinValue()) return false; 04659 break; 04660 case ICmpInst::ICMP_SGT: 04661 if (RA.isMinSignedValue()) { 04662 Pred = ICmpInst::ICMP_NE; 04663 break; 04664 } 04665 if ((RA + 1).isMaxSignedValue()) { 04666 Pred = ICmpInst::ICMP_EQ; 04667 RHS = getConstant(RA + 1); 04668 break; 04669 } 04670 if (RA.isMaxSignedValue()) return false; 04671 break; 04672 case ICmpInst::ICMP_SLT: 04673 if (RA.isMaxSignedValue()) { 04674 Pred = ICmpInst::ICMP_NE; 04675 break; 04676 } 04677 if ((RA - 1).isMinSignedValue()) { 04678 Pred = ICmpInst::ICMP_EQ; 04679 RHS = getConstant(RA - 1); 04680 break; 04681 } 04682 if (RA.isMinSignedValue()) return false; 04683 break; 04684 } 04685 } 04686 04687 // Check to see if we can make the LHS or RHS match. 04688 if (LHS == FoundRHS || RHS == FoundLHS) { 04689 if (isa<SCEVConstant>(RHS)) { 04690 std::swap(FoundLHS, FoundRHS); 04691 FoundPred = ICmpInst::getSwappedPredicate(FoundPred); 04692 } else { 04693 std::swap(LHS, RHS); 04694 Pred = ICmpInst::getSwappedPredicate(Pred); 04695 } 04696 } 04697 04698 // Check whether the found predicate is the same as the desired predicate. 04699 if (FoundPred == Pred) 04700 return isImpliedCondOperands(Pred, LHS, RHS, FoundLHS, FoundRHS); 04701 04702 // Check whether swapping the found predicate makes it the same as the 04703 // desired predicate. 04704 if (ICmpInst::getSwappedPredicate(FoundPred) == Pred) { 04705 if (isa<SCEVConstant>(RHS)) 04706 return isImpliedCondOperands(Pred, LHS, RHS, FoundRHS, FoundLHS); 04707 else 04708 return isImpliedCondOperands(ICmpInst::getSwappedPredicate(Pred), 04709 RHS, LHS, FoundLHS, FoundRHS); 04710 } 04711 04712 // Check whether the actual condition is beyond sufficient. 04713 if (FoundPred == ICmpInst::ICMP_EQ) 04714 if (ICmpInst::isTrueWhenEqual(Pred)) 04715 if (isImpliedCondOperands(Pred, LHS, RHS, FoundLHS, FoundRHS)) 04716 return true; 04717 if (Pred == ICmpInst::ICMP_NE) 04718 if (!ICmpInst::isTrueWhenEqual(FoundPred)) 04719 if (isImpliedCondOperands(FoundPred, LHS, RHS, FoundLHS, FoundRHS)) 04720 return true; 04721 04722 // Otherwise assume the worst. 04723 return false; 04724 } 04725 04726 /// isImpliedCondOperands - Test whether the condition described by Pred, 04727 /// LHS, and RHS is true whenever the condition desribed by Pred, FoundLHS, 04728 /// and FoundRHS is true. 04729 bool ScalarEvolution::isImpliedCondOperands(ICmpInst::Predicate Pred, 04730 const SCEV *LHS, const SCEV *RHS, 04731 const SCEV *FoundLHS, 04732 const SCEV *FoundRHS) { 04733 return isImpliedCondOperandsHelper(Pred, LHS, RHS, 04734 FoundLHS, FoundRHS) || 04735 // ~x < ~y --> x > y 04736 isImpliedCondOperandsHelper(Pred, LHS, RHS, 04737 getNotSCEV(FoundRHS), 04738 getNotSCEV(FoundLHS)); 04739 } 04740 04741 /// isImpliedCondOperandsHelper - Test whether the condition described by 04742 /// Pred, LHS, and RHS is true whenever the condition desribed by Pred, 04743 /// FoundLHS, and FoundRHS is true. 04744 bool 04745 ScalarEvolution::isImpliedCondOperandsHelper(ICmpInst::Predicate Pred, 04746 const SCEV *LHS, const SCEV *RHS, 04747 const SCEV *FoundLHS, 04748 const SCEV *FoundRHS) { 04749 switch (Pred) { 04750 default: llvm_unreachable("Unexpected ICmpInst::Predicate value!"); 04751 case ICmpInst::ICMP_EQ: 04752 case ICmpInst::ICMP_NE: 04753 if (HasSameValue(LHS, FoundLHS) && HasSameValue(RHS, FoundRHS)) 04754 return true; 04755 break; 04756 case ICmpInst::ICMP_SLT: 04757 case ICmpInst::ICMP_SLE: 04758 if (isKnownPredicate(ICmpInst::ICMP_SLE, LHS, FoundLHS) && 04759 isKnownPredicate(ICmpInst::ICMP_SGE, RHS, FoundRHS)) 04760 return true; 04761 break; 04762 case ICmpInst::ICMP_SGT: 04763 case ICmpInst::ICMP_SGE: 04764 if (isKnownPredicate(ICmpInst::ICMP_SGE, LHS, FoundLHS) && 04765 isKnownPredicate(ICmpInst::ICMP_SLE, RHS, FoundRHS)) 04766 return true; 04767 break; 04768 case ICmpInst::ICMP_ULT: 04769 case ICmpInst::ICMP_ULE: 04770 if (isKnownPredicate(ICmpInst::ICMP_ULE, LHS, FoundLHS) && 04771 isKnownPredicate(ICmpInst::ICMP_UGE, RHS, FoundRHS)) 04772 return true; 04773 break; 04774 case ICmpInst::ICMP_UGT: 04775 case ICmpInst::ICMP_UGE: 04776 if (isKnownPredicate(ICmpInst::ICMP_UGE, LHS, FoundLHS) && 04777 isKnownPredicate(ICmpInst::ICMP_ULE, RHS, FoundRHS)) 04778 return true; 04779 break; 04780 } 04781 04782 return false; 04783 } 04784 04785 /// getBECount - Subtract the end and start values and divide by the step, 04786 /// rounding up, to get the number of times the backedge is executed. Return 04787 /// CouldNotCompute if an intermediate computation overflows. 04788 const SCEV *ScalarEvolution::getBECount(const SCEV *Start, 04789 const SCEV *End, 04790 const SCEV *Step) { 04791 const Type *Ty = Start->getType(); 04792 const SCEV *NegOne = getIntegerSCEV(-1, Ty); 04793 const SCEV *Diff = getMinusSCEV(End, Start); 04794 const SCEV *RoundUp = getAddExpr(Step, NegOne); 04795 04796 // Add an adjustment to the difference between End and Start so that 04797 // the division will effectively round up. 04798 const SCEV *Add = getAddExpr(Diff, RoundUp); 04799 04800 // Check Add for unsigned overflow. 04801 // TODO: More sophisticated things could be done here. 04802 const Type *WideTy = IntegerType::get(getContext(), 04803 getTypeSizeInBits(Ty) + 1); 04804 const SCEV *EDiff = getZeroExtendExpr(Diff, WideTy); 04805 const SCEV *ERoundUp = getZeroExtendExpr(RoundUp, WideTy); 04806 const SCEV *OperandExtendedAdd = getAddExpr(EDiff, ERoundUp); 04807 if (getZeroExtendExpr(Add, WideTy) != OperandExtendedAdd) 04808 return getCouldNotCompute(); 04809 04810 return getUDivExpr(Add, Step); 04811 } 04812 04813 /// HowManyLessThans - Return the number of times a backedge containing the 04814 /// specified less-than comparison will execute. If not computable, return 04815 /// CouldNotCompute. 04816 ScalarEvolution::BackedgeTakenInfo 04817 ScalarEvolution::HowManyLessThans(const SCEV *LHS, const SCEV *RHS, 04818 const Loop *L, bool isSigned) { 04819 // Only handle: "ADDREC < LoopInvariant". 04820 if (!RHS->isLoopInvariant(L)) return getCouldNotCompute(); 04821 04822 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(LHS); 04823 if (!AddRec || AddRec->getLoop() != L) 04824 return getCouldNotCompute(); 04825 04826 if (AddRec->isAffine()) { 04827 // FORNOW: We only support unit strides. 04828 unsigned BitWidth = getTypeSizeInBits(AddRec->getType()); 04829 const SCEV *Step = AddRec->getStepRecurrence(*this); 04830 04831 // TODO: handle non-constant strides. 04832 const SCEVConstant *CStep = dyn_cast<SCEVConstant>(Step); 04833 if (!CStep || CStep->isZero()) 04834 return getCouldNotCompute(); 04835 if (CStep->isOne()) { 04836 // With unit stride, the iteration never steps past the limit value. 04837 } else if (CStep->getValue()->getValue().isStrictlyPositive()) { 04838 if (const SCEVConstant *CLimit = dyn_cast<SCEVConstant>(RHS)) { 04839 // Test whether a positive iteration iteration can step past the limit 04840 // value and past the maximum value for its type in a single step. 04841 if (isSigned) { 04842 APInt Max = APInt::getSignedMaxValue(BitWidth); 04843 if ((Max - CStep->getValue()->getValue()) 04844 .slt(CLimit->getValue()->getValue())) 04845 return getCouldNotCompute(); 04846 } else { 04847 APInt Max = APInt::getMaxValue(BitWidth); 04848 if ((Max - CStep->getValue()->getValue()) 04849 .ult(CLimit->getValue()->getValue())) 04850 return getCouldNotCompute(); 04851 } 04852 } else 04853 // TODO: handle non-constant limit values below. 04854 return getCouldNotCompute(); 04855 } else 04856 // TODO: handle negative strides below. 04857 return getCouldNotCompute(); 04858 04859 // We know the LHS is of the form {n,+,s} and the RHS is some loop-invariant 04860 // m. So, we count the number of iterations in which {n,+,s} < m is true. 04861 // Note that we cannot simply return max(m-n,0)/s because it's not safe to 04862 // treat m-n as signed nor unsigned due to overflow possibility. 04863 04864 // First, we get the value of the LHS in the first iteration: n 04865 const SCEV *Start = AddRec->getOperand(0); 04866 04867 // Determine the minimum constant start value. 04868 const SCEV *MinStart = getConstant(isSigned ? 04869 getSignedRange(Start).getSignedMin() : 04870 getUnsignedRange(Start).getUnsignedMin()); 04871 04872 // If we know that the condition is true in order to enter the loop, 04873 // then we know that it will run exactly (m-n)/s times. Otherwise, we 04874 // only know that it will execute (max(m,n)-n)/s times. In both cases, 04875 // the division must round up. 04876 const SCEV *End = RHS; 04877 if (!isLoopGuardedByCond(L, 04878 isSigned ? ICmpInst::ICMP_SLT : 04879 ICmpInst::ICMP_ULT, 04880 getMinusSCEV(Start, Step), RHS)) 04881 End = isSigned ? getSMaxExpr(RHS, Start) 04882 : getUMaxExpr(RHS, Start); 04883 04884 // Determine the maximum constant end value. 04885 const SCEV *MaxEnd = getConstant(isSigned ? 04886 getSignedRange(End).getSignedMax() : 04887 getUnsignedRange(End).getUnsignedMax()); 04888 04889 // Finally, we subtract these two values and divide, rounding up, to get 04890 // the number of times the backedge is executed. 04891 const SCEV *BECount = getBECount(Start, End, Step); 04892 04893 // The maximum backedge count is similar, except using the minimum start 04894 // value and the maximum end value. 04895 const SCEV *MaxBECount = getBECount(MinStart, MaxEnd, Step); 04896 04897 return BackedgeTakenInfo(BECount, MaxBECount); 04898 } 04899 04900 return getCouldNotCompute(); 04901 } 04902 04903 /// getNumIterationsInRange - Return the number of iterations of this loop that 04904 /// produce values in the specified constant range. Another way of looking at 04905 /// this is that it returns the first iteration number where the value is not in 04906 /// the condition, thus computing the exit count. If the iteration count can't 04907 /// be computed, an instance of SCEVCouldNotCompute is returned. 04908 const SCEV *SCEVAddRecExpr::getNumIterationsInRange(ConstantRange Range, 04909 ScalarEvolution &SE) const { 04910 if (Range.isFullSet()) // Infinite loop. 04911 return SE.getCouldNotCompute(); 04912 04913 // If the start is a non-zero constant, shift the range to simplify things. 04914 if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(getStart())) 04915 if (!SC->getValue()->isZero()) { 04916 SmallVector<const SCEV *, 4> Operands(op_begin(), op_end()); 04917 Operands[0] = SE.getIntegerSCEV(0, SC->getType()); 04918 const SCEV *Shifted = SE.getAddRecExpr(Operands, getLoop()); 04919 if (const SCEVAddRecExpr *ShiftedAddRec = 04920 dyn_cast<SCEVAddRecExpr>(Shifted)) 04921 return ShiftedAddRec->getNumIterationsInRange( 04922 Range.subtract(SC->getValue()->getValue()), SE); 04923 // This is strange and shouldn't happen. 04924 return SE.getCouldNotCompute(); 04925 } 04926 04927 // The only time we can solve this is when we have all constant indices. 04928 // Otherwise, we cannot determine the overflow conditions. 04929 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) 04930 if (!isa<SCEVConstant>(getOperand(i))) 04931 return SE.getCouldNotCompute(); 04932 04933 04934 // Okay at this point we know that all elements of the chrec are constants and 04935 // that the start element is zero. 04936 04937 // First check to see if the range contains zero. If not, the first 04938 // iteration exits. 04939 unsigned BitWidth = SE.getTypeSizeInBits(getType()); 04940 if (!Range.contains(APInt(BitWidth, 0))) 04941 return SE.getIntegerSCEV(0, getType()); 04942 04943 if (isAffine()) { 04944 // If this is an affine expression then we have this situation: 04945 // Solve {0,+,A} in Range === Ax in Range 04946 04947 // We know that zero is in the range. If A is positive then we know that 04948 // the upper value of the range must be the first possible exit value. 04949 // If A is negative then the lower of the range is the last possible loop 04950 // value. Also note that we already checked for a full range. 04951 APInt One(BitWidth,1); 04952 APInt A = cast<SCEVConstant>(getOperand(1))->getValue()->getValue(); 04953 APInt End = A.sge(One) ? (Range.getUpper() - One) : Range.getLower(); 04954 04955 // The exit value should be (End+A)/A. 04956 APInt ExitVal = (End + A).udiv(A); 04957 ConstantInt *ExitValue = ConstantInt::get(SE.getContext(), ExitVal); 04958 04959 // Evaluate at the exit value. If we really did fall out of the valid 04960 // range, then we computed our trip count, otherwise wrap around or other 04961 // things must have happened. 04962 ConstantInt *Val = EvaluateConstantChrecAtConstant(this, ExitValue, SE); 04963 if (Range.contains(Val->getValue())) 04964 return SE.getCouldNotCompute(); // Something strange happened 04965 04966 // Ensure that the previous value is in the range. This is a sanity check. 04967 assert(Range.contains( 04968 EvaluateConstantChrecAtConstant(this, 04969 ConstantInt::get(SE.getContext(), ExitVal - One), SE)->getValue()) && 04970 "Linear scev computation is off in a bad way!"); 04971 return SE.getConstant(ExitValue); 04972 } else if (isQuadratic()) { 04973 // If this is a quadratic (3-term) AddRec {L,+,M,+,N}, find the roots of the 04974 // quadratic equation to solve it. To do this, we must frame our problem in 04975 // terms of figuring out when zero is crossed, instead of when 04976 // Range.getUpper() is crossed. 04977 SmallVector<const SCEV *, 4> NewOps(op_begin(), op_end()); 04978 NewOps[0] = SE.getNegativeSCEV(SE.getConstant(Range.getUpper())); 04979 const SCEV *NewAddRec = SE.getAddRecExpr(NewOps, getLoop()); 04980 04981 // Next, solve the constructed addrec 04982 std::pair<const SCEV *,const SCEV *> Roots = 04983 SolveQuadraticEquation(cast<SCEVAddRecExpr>(NewAddRec), SE); 04984 const SCEVConstant *R1 = dyn_cast<SCEVConstant>(Roots.first); 04985 const SCEVConstant *R2 = dyn_cast<SCEVConstant>(Roots.second); 04986 if (R1) { 04987 // Pick the smallest positive root value. 04988 if (ConstantInt *CB = 04989 dyn_cast<ConstantInt>(ConstantExpr::getICmp(ICmpInst::ICMP_ULT, 04990 R1->getValue(), R2->getValue()))) { 04991 if (CB->getZExtValue() == false) 04992 std::swap(R1, R2); // R1 is the minimum root now. 04993 04994 // Make sure the root is not off by one. The returned iteration should 04995 // not be in the range, but the previous one should be. When solving 04996 // for "X*X < 5", for example, we should not return a root of 2. 04997 ConstantInt *R1Val = EvaluateConstantChrecAtConstant(this, 04998 R1->getValue(), 04999 SE); 05000 if (Range.contains(R1Val->getValue())) { 05001 // The next iteration must be out of the range... 05002 ConstantInt *NextVal = 05003 ConstantInt::get(SE.getContext(), R1->getValue()->getValue()+1); 05004 05005 R1Val = EvaluateConstantChrecAtConstant(this, NextVal, SE); 05006 if (!Range.contains(R1Val->getValue())) 05007 return SE.getConstant(NextVal); 05008 return SE.getCouldNotCompute(); // Something strange happened 05009 } 05010 05011 // If R1 was not in the range, then it is a good return value. Make 05012 // sure that R1-1 WAS in the range though, just in case. 05013 ConstantInt *NextVal = 05014 ConstantInt::get(SE.getContext(), R1->getValue()->getValue()-1); 05015 R1Val = EvaluateConstantChrecAtConstant(this, NextVal, SE); 05016 if (Range.contains(R1Val->getValue())) 05017 return R1; 05018 return SE.getCouldNotCompute(); // Something strange happened 05019 } 05020 } 05021 } 05022 05023 return SE.getCouldNotCompute(); 05024 } 05025 05026 05027 05028 //===----------------------------------------------------------------------===// 05029 // SCEVCallbackVH Class Implementation 05030 //===----------------------------------------------------------------------===// 05031 05032 void ScalarEvolution::SCEVCallbackVH::deleted() { 05033 assert(SE && "SCEVCallbackVH called with a null ScalarEvolution!"); 05034 if (PHINode *PN = dyn_cast<PHINode>(getValPtr())) 05035 SE->ConstantEvolutionLoopExitValue.erase(PN); 05036 if (Instruction *I = dyn_cast<Instruction>(getValPtr())) 05037 SE->ValuesAtScopes.erase(I); 05038 SE->Scalars.erase(getValPtr()); 05039 // this now dangles! 05040 } 05041 05042 void ScalarEvolution::SCEVCallbackVH::allUsesReplacedWith(Value *) { 05043 assert(SE && "SCEVCallbackVH called with a null ScalarEvolution!"); 05044 05045 // Forget all the expressions associated with users of the old value, 05046 // so that future queries will recompute the expressions using the new 05047 // value. 05048 SmallVector<User *, 16> Worklist; 05049 SmallPtrSet<User *, 8> Visited; 05050 Value *Old = getValPtr(); 05051 bool DeleteOld = false; 05052 for (Value::use_iterator UI = Old->use_begin(), UE = Old->use_end(); 05053 UI != UE; ++UI) 05054 Worklist.push_back(*UI); 05055 while (!Worklist.empty()) { 05056 User *U = Worklist.pop_back_val(); 05057 // Deleting the Old value will cause this to dangle. Postpone 05058 // that until everything else is done. 05059 if (U == Old) { 05060 DeleteOld = true; 05061 continue; 05062 } 05063 if (!Visited.insert(U)) 05064 continue; 05065 if (PHINode *PN = dyn_cast<PHINode>(U)) 05066 SE->ConstantEvolutionLoopExitValue.erase(PN); 05067 if (Instruction *I = dyn_cast<Instruction>(U)) 05068 SE->ValuesAtScopes.erase(I); 05069 SE->Scalars.erase(U); 05070 for (Value::use_iterator UI = U->use_begin(), UE = U->use_end(); 05071 UI != UE; ++UI) 05072 Worklist.push_back(*UI); 05073 } 05074 // Delete the Old value if it (indirectly) references itself. 05075 if (DeleteOld) { 05076 if (PHINode *PN = dyn_cast<PHINode>(Old)) 05077 SE->ConstantEvolutionLoopExitValue.erase(PN); 05078 if (Instruction *I = dyn_cast<Instruction>(Old)) 05079 SE->ValuesAtScopes.erase(I); 05080 SE->Scalars.erase(Old); 05081 // this now dangles! 05082 } 05083 // this may dangle! 05084 } 05085 05086 ScalarEvolution::SCEVCallbackVH::SCEVCallbackVH(Value *V, ScalarEvolution *se) 05087 : CallbackVH(V), SE(se) {} 05088 05089 //===----------------------------------------------------------------------===// 05090 // ScalarEvolution Class Implementation 05091 //===----------------------------------------------------------------------===// 05092 05093 ScalarEvolution::ScalarEvolution() 05094 : FunctionPass(&ID) { 05095 } 05096 05097 bool ScalarEvolution::runOnFunction(Function &F) { 05098 this->F = &F; 05099 LI = &getAnalysis<LoopInfo>(); 05100 TD = getAnalysisIfAvailable<TargetData>(); 05101 return false; 05102 } 05103 05104 void ScalarEvolution::releaseMemory() { 05105 Scalars.clear(); 05106 BackedgeTakenCounts.clear(); 05107 ConstantEvolutionLoopExitValue.clear(); 05108 ValuesAtScopes.clear(); 05109 UniqueSCEVs.clear(); 05110 SCEVAllocator.Reset(); 05111 } 05112 05113 void ScalarEvolution::getAnalysisUsage(AnalysisUsage &AU) const { 05114 AU.setPreservesAll(); 05115 AU.addRequiredTransitive<LoopInfo>(); 05116 } 05117 05118 bool ScalarEvolution::hasLoopInvariantBackedgeTakenCount(const Loop *L) { 05119 return !isa<SCEVCouldNotCompute>(getBackedgeTakenCount(L)); 05120 } 05121 05122 static void PrintLoopInfo(raw_ostream &OS, ScalarEvolution *SE, 05123 const Loop *L) { 05124 // Print all inner loops first 05125 for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I) 05126 PrintLoopInfo(OS, SE, *I); 05127 05128 OS << "Loop " << L->getHeader()->getName() << ": "; 05129 05130 SmallVector<BasicBlock*, 8> ExitBlocks; 05131 L->getExitBlocks(ExitBlocks); 05132 if (ExitBlocks.size() != 1) 05133 OS << "<multiple exits> "; 05134 05135 if (SE->hasLoopInvariantBackedgeTakenCount(L)) { 05136 OS << "backedge-taken count is " << *SE->getBackedgeTakenCount(L); 05137 } else { 05138 OS << "Unpredictable backedge-taken count. "; 05139 } 05140 05141 OS << "\n"; 05142 OS << "Loop " << L->getHeader()->getName() << ": "; 05143 05144 if (!isa<SCEVCouldNotCompute>(SE->getMaxBackedgeTakenCount(L))) { 05145 OS << "max backedge-taken count is " << *SE->getMaxBackedgeTakenCount(L); 05146 } else { 05147 OS << "Unpredictable max backedge-taken count. "; 05148 } 05149 05150 OS << "\n"; 05151 } 05152 05153 void ScalarEvolution::print(raw_ostream &OS, const Module* ) const { 05154 // ScalarEvolution's implementaiton of the print method is to print 05155 // out SCEV values of all instructions that are interesting. Doing 05156 // this potentially causes it to create new SCEV objects though, 05157 // which technically conflicts with the const qualifier. This isn't 05158 // observable from outside the class though, so casting away the 05159 // const isn't dangerous. 05160 ScalarEvolution &SE = *const_cast<ScalarEvolution*>(this); 05161 05162 OS << "Classifying expressions for: " << F->getName() << "\n"; 05163 for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) 05164 if (isSCEVable(I->getType())) { 05165 OS << *I << '\n'; 05166 OS << " --> "; 05167 const SCEV *SV = SE.getSCEV(&*I); 05168 SV->print(OS); 05169 05170 const Loop *L = LI->getLoopFor((*I).getParent()); 05171 05172 const SCEV *AtUse = SE.getSCEVAtScope(SV, L); 05173 if (AtUse != SV) { 05174 OS << " --> "; 05175 AtUse->print(OS); 05176 } 05177 05178 if (L) { 05179 OS << "\t\t" "Exits: "; 05180 const SCEV *ExitValue = SE.getSCEVAtScope(SV, L->getParentLoop()); 05181 if (!ExitValue->isLoopInvariant(L)) { 05182 OS << "<<Unknown>>"; 05183 } else { 05184 OS << *ExitValue; 05185 } 05186 } 05187 05188 OS << "\n"; 05189 } 05190 05191 OS << "Determining loop execution counts for: " << F->getName() << "\n"; 05192 for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I) 05193 PrintLoopInfo(OS, &SE, *I); 05194 } 05195 05196 void ScalarEvolution::print(std::ostream &o, const Module *M) const { 05197 raw_os_ostream OS(o); 05198 print(OS, M); 05199 }