LLVM API Documentation
00001 //===- llvm/Analysis/ScalarEvolution.h - Scalar Evolution -------*- 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 // The ScalarEvolution class is an LLVM pass which can be used to analyze and 00011 // catagorize scalar expressions in loops. It specializes in recognizing 00012 // general induction variables, representing them with the abstract and opaque 00013 // SCEV class. Given this analysis, trip counts of loops and other important 00014 // properties can be obtained. 00015 // 00016 // This analysis is primarily useful for induction variable substitution and 00017 // strength reduction. 00018 // 00019 //===----------------------------------------------------------------------===// 00020 00021 #ifndef LLVM_ANALYSIS_SCALAREVOLUTION_H 00022 #define LLVM_ANALYSIS_SCALAREVOLUTION_H 00023 00024 #include "llvm/Pass.h" 00025 #include "llvm/Instructions.h" 00026 #include "llvm/Function.h" 00027 #include "llvm/Support/DataTypes.h" 00028 #include "llvm/Support/ValueHandle.h" 00029 #include "llvm/Support/Allocator.h" 00030 #include "llvm/Support/ConstantRange.h" 00031 #include "llvm/ADT/FoldingSet.h" 00032 #include "llvm/ADT/DenseMap.h" 00033 #include <iosfwd> 00034 #include <map> 00035 00036 namespace llvm { 00037 class APInt; 00038 class Constant; 00039 class ConstantInt; 00040 class DominatorTree; 00041 class Type; 00042 class ScalarEvolution; 00043 class TargetData; 00044 class LLVMContext; 00045 class Loop; 00046 class LoopInfo; 00047 class Operator; 00048 00049 /// SCEV - This class represents an analyzed expression in the program. These 00050 /// are opaque objects that the client is not allowed to do much with 00051 /// directly. 00052 /// 00053 class SCEV : public FastFoldingSetNode { 00054 // The SCEV baseclass this node corresponds to 00055 const unsigned short SCEVType; 00056 00057 protected: 00058 /// SubclassData - This field is initialized to zero and may be used in 00059 /// subclasses to store miscelaneous information. 00060 unsigned short SubclassData; 00061 00062 private: 00063 SCEV(const SCEV &); // DO NOT IMPLEMENT 00064 void operator=(const SCEV &); // DO NOT IMPLEMENT 00065 protected: 00066 virtual ~SCEV(); 00067 public: 00068 explicit SCEV(const FoldingSetNodeID &ID, unsigned SCEVTy) : 00069 FastFoldingSetNode(ID), SCEVType(SCEVTy), SubclassData(0) {} 00070 00071 unsigned getSCEVType() const { return SCEVType; } 00072 00073 /// isLoopInvariant - Return true if the value of this SCEV is unchanging in 00074 /// the specified loop. 00075 virtual bool isLoopInvariant(const Loop *L) const = 0; 00076 00077 /// hasComputableLoopEvolution - Return true if this SCEV changes value in a 00078 /// known way in the specified loop. This property being true implies that 00079 /// the value is variant in the loop AND that we can emit an expression to 00080 /// compute the value of the expression at any particular loop iteration. 00081 virtual bool hasComputableLoopEvolution(const Loop *L) const = 0; 00082 00083 /// getType - Return the LLVM type of this SCEV expression. 00084 /// 00085 virtual const Type *getType() const = 0; 00086 00087 /// isZero - Return true if the expression is a constant zero. 00088 /// 00089 bool isZero() const; 00090 00091 /// isOne - Return true if the expression is a constant one. 00092 /// 00093 bool isOne() const; 00094 00095 /// isAllOnesValue - Return true if the expression is a constant 00096 /// all-ones value. 00097 /// 00098 bool isAllOnesValue() const; 00099 00100 /// hasOperand - Test whether this SCEV has Op as a direct or 00101 /// indirect operand. 00102 virtual bool hasOperand(const SCEV *Op) const = 0; 00103 00104 /// dominates - Return true if elements that makes up this SCEV dominates 00105 /// the specified basic block. 00106 virtual bool dominates(BasicBlock *BB, DominatorTree *DT) const = 0; 00107 00108 /// print - Print out the internal representation of this scalar to the 00109 /// specified stream. This should really only be used for debugging 00110 /// purposes. 00111 virtual void print(raw_ostream &OS) const = 0; 00112 void print(std::ostream &OS) const; 00113 void print(std::ostream *OS) const { if (OS) print(*OS); } 00114 00115 /// dump - This method is used for debugging. 00116 /// 00117 void dump() const; 00118 }; 00119 00120 inline raw_ostream &operator<<(raw_ostream &OS, const SCEV &S) { 00121 S.print(OS); 00122 return OS; 00123 } 00124 00125 inline std::ostream &operator<<(std::ostream &OS, const SCEV &S) { 00126 S.print(OS); 00127 return OS; 00128 } 00129 00130 /// SCEVCouldNotCompute - An object of this class is returned by queries that 00131 /// could not be answered. For example, if you ask for the number of 00132 /// iterations of a linked-list traversal loop, you will get one of these. 00133 /// None of the standard SCEV operations are valid on this class, it is just a 00134 /// marker. 00135 struct SCEVCouldNotCompute : public SCEV { 00136 SCEVCouldNotCompute(); 00137 00138 // None of these methods are valid for this object. 00139 virtual bool isLoopInvariant(const Loop *L) const; 00140 virtual const Type *getType() const; 00141 virtual bool hasComputableLoopEvolution(const Loop *L) const; 00142 virtual void print(raw_ostream &OS) const; 00143 virtual bool hasOperand(const SCEV *Op) const; 00144 00145 virtual bool dominates(BasicBlock *BB, DominatorTree *DT) const { 00146 return true; 00147 } 00148 00149 /// Methods for support type inquiry through isa, cast, and dyn_cast: 00150 static inline bool classof(const SCEVCouldNotCompute *S) { return true; } 00151 static bool classof(const SCEV *S); 00152 }; 00153 00154 /// ScalarEvolution - This class is the main scalar evolution driver. Because 00155 /// client code (intentionally) can't do much with the SCEV objects directly, 00156 /// they must ask this class for services. 00157 /// 00158 class ScalarEvolution : public FunctionPass { 00159 /// SCEVCallbackVH - A CallbackVH to arrange for ScalarEvolution to be 00160 /// notified whenever a Value is deleted. 00161 class SCEVCallbackVH : public CallbackVH { 00162 ScalarEvolution *SE; 00163 virtual void deleted(); 00164 virtual void allUsesReplacedWith(Value *New); 00165 public: 00166 SCEVCallbackVH(Value *V, ScalarEvolution *SE = 0); 00167 }; 00168 00169 friend class SCEVCallbackVH; 00170 friend struct SCEVExpander; 00171 00172 /// F - The function we are analyzing. 00173 /// 00174 Function *F; 00175 00176 /// LI - The loop information for the function we are currently analyzing. 00177 /// 00178 LoopInfo *LI; 00179 00180 /// TD - The target data information for the target we are targetting. 00181 /// 00182 TargetData *TD; 00183 00184 /// CouldNotCompute - This SCEV is used to represent unknown trip 00185 /// counts and things. 00186 SCEVCouldNotCompute CouldNotCompute; 00187 00188 /// Scalars - This is a cache of the scalars we have analyzed so far. 00189 /// 00190 std::map<SCEVCallbackVH, const SCEV *> Scalars; 00191 00192 /// BackedgeTakenInfo - Information about the backedge-taken count 00193 /// of a loop. This currently inclues an exact count and a maximum count. 00194 /// 00195 struct BackedgeTakenInfo { 00196 /// Exact - An expression indicating the exact backedge-taken count of 00197 /// the loop if it is known, or a SCEVCouldNotCompute otherwise. 00198 const SCEV *Exact; 00199 00200 /// Max - An expression indicating the least maximum backedge-taken 00201 /// count of the loop that is known, or a SCEVCouldNotCompute. 00202 const SCEV *Max; 00203 00204 /*implicit*/ BackedgeTakenInfo(const SCEV *exact) : 00205 Exact(exact), Max(exact) {} 00206 00207 BackedgeTakenInfo(const SCEV *exact, const SCEV *max) : 00208 Exact(exact), Max(max) {} 00209 00210 /// hasAnyInfo - Test whether this BackedgeTakenInfo contains any 00211 /// computed information, or whether it's all SCEVCouldNotCompute 00212 /// values. 00213 bool hasAnyInfo() const { 00214 return !isa<SCEVCouldNotCompute>(Exact) || 00215 !isa<SCEVCouldNotCompute>(Max); 00216 } 00217 }; 00218 00219 /// BackedgeTakenCounts - Cache the backedge-taken count of the loops for 00220 /// this function as they are computed. 00221 std::map<const Loop*, BackedgeTakenInfo> BackedgeTakenCounts; 00222 00223 /// ConstantEvolutionLoopExitValue - This map contains entries for all of 00224 /// the PHI instructions that we attempt to compute constant evolutions for. 00225 /// This allows us to avoid potentially expensive recomputation of these 00226 /// properties. An instruction maps to null if we are unable to compute its 00227 /// exit value. 00228 std::map<PHINode*, Constant*> ConstantEvolutionLoopExitValue; 00229 00230 /// ValuesAtScopes - This map contains entries for all the instructions 00231 /// that we attempt to compute getSCEVAtScope information for without 00232 /// using SCEV techniques, which can be expensive. 00233 std::map<Instruction *, std::map<const Loop *, Constant *> > ValuesAtScopes; 00234 00235 /// createSCEV - We know that there is no SCEV for the specified value. 00236 /// Analyze the expression. 00237 const SCEV *createSCEV(Value *V); 00238 00239 /// createNodeForPHI - Provide the special handling we need to analyze PHI 00240 /// SCEVs. 00241 const SCEV *createNodeForPHI(PHINode *PN); 00242 00243 /// createNodeForGEP - Provide the special handling we need to analyze GEP 00244 /// SCEVs. 00245 const SCEV *createNodeForGEP(Operator *GEP); 00246 00247 /// ForgetSymbolicValue - This looks up computed SCEV values for all 00248 /// instructions that depend on the given instruction and removes them from 00249 /// the Scalars map if they reference SymName. This is used during PHI 00250 /// resolution. 00251 void ForgetSymbolicName(Instruction *I, const SCEV *SymName); 00252 00253 /// getBECount - Subtract the end and start values and divide by the step, 00254 /// rounding up, to get the number of times the backedge is executed. Return 00255 /// CouldNotCompute if an intermediate computation overflows. 00256 const SCEV *getBECount(const SCEV *Start, 00257 const SCEV *End, 00258 const SCEV *Step); 00259 00260 /// getBackedgeTakenInfo - Return the BackedgeTakenInfo for the given 00261 /// loop, lazily computing new values if the loop hasn't been analyzed 00262 /// yet. 00263 const BackedgeTakenInfo &getBackedgeTakenInfo(const Loop *L); 00264 00265 /// ComputeBackedgeTakenCount - Compute the number of times the specified 00266 /// loop will iterate. 00267 BackedgeTakenInfo ComputeBackedgeTakenCount(const Loop *L); 00268 00269 /// ComputeBackedgeTakenCountFromExit - Compute the number of times the 00270 /// backedge of the specified loop will execute if it exits via the 00271 /// specified block. 00272 BackedgeTakenInfo ComputeBackedgeTakenCountFromExit(const Loop *L, 00273 BasicBlock *ExitingBlock); 00274 00275 /// ComputeBackedgeTakenCountFromExitCond - Compute the number of times the 00276 /// backedge of the specified loop will execute if its exit condition 00277 /// were a conditional branch of ExitCond, TBB, and FBB. 00278 BackedgeTakenInfo 00279 ComputeBackedgeTakenCountFromExitCond(const Loop *L, 00280 Value *ExitCond, 00281 BasicBlock *TBB, 00282 BasicBlock *FBB); 00283 00284 /// ComputeBackedgeTakenCountFromExitCondICmp - Compute the number of 00285 /// times the backedge of the specified loop will execute if its exit 00286 /// condition were a conditional branch of the ICmpInst ExitCond, TBB, 00287 /// and FBB. 00288 BackedgeTakenInfo 00289 ComputeBackedgeTakenCountFromExitCondICmp(const Loop *L, 00290 ICmpInst *ExitCond, 00291 BasicBlock *TBB, 00292 BasicBlock *FBB); 00293 00294 /// ComputeLoadConstantCompareBackedgeTakenCount - Given an exit condition 00295 /// of 'icmp op load X, cst', try to see if we can compute the 00296 /// backedge-taken count. 00297 const SCEV * 00298 ComputeLoadConstantCompareBackedgeTakenCount(LoadInst *LI, 00299 Constant *RHS, 00300 const Loop *L, 00301 ICmpInst::Predicate p); 00302 00303 /// ComputeBackedgeTakenCountExhaustively - If the loop is known to execute 00304 /// a constant number of times (the condition evolves only from constants), 00305 /// try to evaluate a few iterations of the loop until we get the exit 00306 /// condition gets a value of ExitWhen (true or false). If we cannot 00307 /// evaluate the backedge-taken count of the loop, return CouldNotCompute. 00308 const SCEV *ComputeBackedgeTakenCountExhaustively(const Loop *L, 00309 Value *Cond, 00310 bool ExitWhen); 00311 00312 /// HowFarToZero - Return the number of times a backedge comparing the 00313 /// specified value to zero will execute. If not computable, return 00314 /// CouldNotCompute. 00315 const SCEV *HowFarToZero(const SCEV *V, const Loop *L); 00316 00317 /// HowFarToNonZero - Return the number of times a backedge checking the 00318 /// specified value for nonzero will execute. If not computable, return 00319 /// CouldNotCompute. 00320 const SCEV *HowFarToNonZero(const SCEV *V, const Loop *L); 00321 00322 /// HowManyLessThans - Return the number of times a backedge containing the 00323 /// specified less-than comparison will execute. If not computable, return 00324 /// CouldNotCompute. isSigned specifies whether the less-than is signed. 00325 BackedgeTakenInfo HowManyLessThans(const SCEV *LHS, const SCEV *RHS, 00326 const Loop *L, bool isSigned); 00327 00328 /// getLoopPredecessor - If the given loop's header has exactly one unique 00329 /// predecessor outside the loop, return it. Otherwise return null. 00330 BasicBlock *getLoopPredecessor(const Loop *L); 00331 00332 /// getPredecessorWithUniqueSuccessorForBB - Return a predecessor of BB 00333 /// (which may not be an immediate predecessor) which has exactly one 00334 /// successor from which BB is reachable, or null if no such block is 00335 /// found. 00336 BasicBlock* getPredecessorWithUniqueSuccessorForBB(BasicBlock *BB); 00337 00338 /// isImpliedCond - Test whether the condition described by Pred, LHS, 00339 /// and RHS is true whenever the given Cond value evaluates to true. 00340 bool isImpliedCond(Value *Cond, ICmpInst::Predicate Pred, 00341 const SCEV *LHS, const SCEV *RHS, 00342 bool Inverse); 00343 00344 /// isImpliedCondOperands - Test whether the condition described by Pred, 00345 /// LHS, and RHS is true whenever the condition desribed by Pred, FoundLHS, 00346 /// and FoundRHS is true. 00347 bool isImpliedCondOperands(ICmpInst::Predicate Pred, 00348 const SCEV *LHS, const SCEV *RHS, 00349 const SCEV *FoundLHS, const SCEV *FoundRHS); 00350 00351 /// isImpliedCondOperandsHelper - Test whether the condition described by 00352 /// Pred, LHS, and RHS is true whenever the condition desribed by Pred, 00353 /// FoundLHS, and FoundRHS is true. 00354 bool isImpliedCondOperandsHelper(ICmpInst::Predicate Pred, 00355 const SCEV *LHS, const SCEV *RHS, 00356 const SCEV *FoundLHS, const SCEV *FoundRHS); 00357 00358 /// getConstantEvolutionLoopExitValue - If we know that the specified Phi is 00359 /// in the header of its containing loop, we know the loop executes a 00360 /// constant number of times, and the PHI node is just a recurrence 00361 /// involving constants, fold it. 00362 Constant *getConstantEvolutionLoopExitValue(PHINode *PN, const APInt& BEs, 00363 const Loop *L); 00364 00365 public: 00366 static char ID; // Pass identification, replacement for typeid 00367 ScalarEvolution(); 00368 00369 LLVMContext &getContext() const { return F->getContext(); } 00370 00371 /// isSCEVable - Test if values of the given type are analyzable within 00372 /// the SCEV framework. This primarily includes integer types, and it 00373 /// can optionally include pointer types if the ScalarEvolution class 00374 /// has access to target-specific information. 00375 bool isSCEVable(const Type *Ty) const; 00376 00377 /// getTypeSizeInBits - Return the size in bits of the specified type, 00378 /// for which isSCEVable must return true. 00379 uint64_t getTypeSizeInBits(const Type *Ty) const; 00380 00381 /// getEffectiveSCEVType - Return a type with the same bitwidth as 00382 /// the given type and which represents how SCEV will treat the given 00383 /// type, for which isSCEVable must return true. For pointer types, 00384 /// this is the pointer-sized integer type. 00385 const Type *getEffectiveSCEVType(const Type *Ty) const; 00386 00387 /// getSCEV - Return a SCEV expression handle for the full generality of the 00388 /// specified expression. 00389 const SCEV *getSCEV(Value *V); 00390 00391 const SCEV *getConstant(ConstantInt *V); 00392 const SCEV *getConstant(const APInt& Val); 00393 const SCEV *getConstant(const Type *Ty, uint64_t V, bool isSigned = false); 00394 const SCEV *getTruncateExpr(const SCEV *Op, const Type *Ty); 00395 const SCEV *getZeroExtendExpr(const SCEV *Op, const Type *Ty); 00396 const SCEV *getSignExtendExpr(const SCEV *Op, const Type *Ty); 00397 const SCEV *getAnyExtendExpr(const SCEV *Op, const Type *Ty); 00398 const SCEV *getAddExpr(SmallVectorImpl<const SCEV *> &Ops); 00399 const SCEV *getAddExpr(const SCEV *LHS, const SCEV *RHS) { 00400 SmallVector<const SCEV *, 2> Ops; 00401 Ops.push_back(LHS); 00402 Ops.push_back(RHS); 00403 return getAddExpr(Ops); 00404 } 00405 const SCEV *getAddExpr(const SCEV *Op0, const SCEV *Op1, 00406 const SCEV *Op2) { 00407 SmallVector<const SCEV *, 3> Ops; 00408 Ops.push_back(Op0); 00409 Ops.push_back(Op1); 00410 Ops.push_back(Op2); 00411 return getAddExpr(Ops); 00412 } 00413 const SCEV *getMulExpr(SmallVectorImpl<const SCEV *> &Ops); 00414 const SCEV *getMulExpr(const SCEV *LHS, const SCEV *RHS) { 00415 SmallVector<const SCEV *, 2> Ops; 00416 Ops.push_back(LHS); 00417 Ops.push_back(RHS); 00418 return getMulExpr(Ops); 00419 } 00420 const SCEV *getUDivExpr(const SCEV *LHS, const SCEV *RHS); 00421 const SCEV *getAddRecExpr(const SCEV *Start, const SCEV *Step, 00422 const Loop *L); 00423 const SCEV *getAddRecExpr(SmallVectorImpl<const SCEV *> &Operands, 00424 const Loop *L); 00425 const SCEV *getAddRecExpr(const SmallVectorImpl<const SCEV *> &Operands, 00426 const Loop *L) { 00427 SmallVector<const SCEV *, 4> NewOp(Operands.begin(), Operands.end()); 00428 return getAddRecExpr(NewOp, L); 00429 } 00430 const SCEV *getSMaxExpr(const SCEV *LHS, const SCEV *RHS); 00431 const SCEV *getSMaxExpr(SmallVectorImpl<const SCEV *> &Operands); 00432 const SCEV *getUMaxExpr(const SCEV *LHS, const SCEV *RHS); 00433 const SCEV *getUMaxExpr(SmallVectorImpl<const SCEV *> &Operands); 00434 const SCEV *getSMinExpr(const SCEV *LHS, const SCEV *RHS); 00435 const SCEV *getUMinExpr(const SCEV *LHS, const SCEV *RHS); 00436 const SCEV *getFieldOffsetExpr(const StructType *STy, unsigned FieldNo); 00437 const SCEV *getAllocSizeExpr(const Type *AllocTy); 00438 const SCEV *getUnknown(Value *V); 00439 const SCEV *getCouldNotCompute(); 00440 00441 /// getNegativeSCEV - Return the SCEV object corresponding to -V. 00442 /// 00443 const SCEV *getNegativeSCEV(const SCEV *V); 00444 00445 /// getNotSCEV - Return the SCEV object corresponding to ~V. 00446 /// 00447 const SCEV *getNotSCEV(const SCEV *V); 00448 00449 /// getMinusSCEV - Return LHS-RHS. 00450 /// 00451 const SCEV *getMinusSCEV(const SCEV *LHS, 00452 const SCEV *RHS); 00453 00454 /// getTruncateOrZeroExtend - Return a SCEV corresponding to a conversion 00455 /// of the input value to the specified type. If the type must be 00456 /// extended, it is zero extended. 00457 const SCEV *getTruncateOrZeroExtend(const SCEV *V, const Type *Ty); 00458 00459 /// getTruncateOrSignExtend - Return a SCEV corresponding to a conversion 00460 /// of the input value to the specified type. If the type must be 00461 /// extended, it is sign extended. 00462 const SCEV *getTruncateOrSignExtend(const SCEV *V, const Type *Ty); 00463 00464 /// getNoopOrZeroExtend - Return a SCEV corresponding to a conversion of 00465 /// the input value to the specified type. If the type must be extended, 00466 /// it is zero extended. The conversion must not be narrowing. 00467 const SCEV *getNoopOrZeroExtend(const SCEV *V, const Type *Ty); 00468 00469 /// getNoopOrSignExtend - Return a SCEV corresponding to a conversion of 00470 /// the input value to the specified type. If the type must be extended, 00471 /// it is sign extended. The conversion must not be narrowing. 00472 const SCEV *getNoopOrSignExtend(const SCEV *V, const Type *Ty); 00473 00474 /// getNoopOrAnyExtend - Return a SCEV corresponding to a conversion of 00475 /// the input value to the specified type. If the type must be extended, 00476 /// it is extended with unspecified bits. The conversion must not be 00477 /// narrowing. 00478 const SCEV *getNoopOrAnyExtend(const SCEV *V, const Type *Ty); 00479 00480 /// getTruncateOrNoop - Return a SCEV corresponding to a conversion of the 00481 /// input value to the specified type. The conversion must not be 00482 /// widening. 00483 const SCEV *getTruncateOrNoop(const SCEV *V, const Type *Ty); 00484 00485 /// getIntegerSCEV - Given a SCEVable type, create a constant for the 00486 /// specified signed integer value and return a SCEV for the constant. 00487 const SCEV *getIntegerSCEV(int Val, const Type *Ty); 00488 00489 /// getUMaxFromMismatchedTypes - Promote the operands to the wider of 00490 /// the types using zero-extension, and then perform a umax operation 00491 /// with them. 00492 const SCEV *getUMaxFromMismatchedTypes(const SCEV *LHS, 00493 const SCEV *RHS); 00494 00495 /// getUMinFromMismatchedTypes - Promote the operands to the wider of 00496 /// the types using zero-extension, and then perform a umin operation 00497 /// with them. 00498 const SCEV *getUMinFromMismatchedTypes(const SCEV *LHS, 00499 const SCEV *RHS); 00500 00501 /// getSCEVAtScope - Return a SCEV expression handle for the specified value 00502 /// at the specified scope in the program. The L value specifies a loop 00503 /// nest to evaluate the expression at, where null is the top-level or a 00504 /// specified loop is immediately inside of the loop. 00505 /// 00506 /// This method can be used to compute the exit value for a variable defined 00507 /// in a loop by querying what the value will hold in the parent loop. 00508 /// 00509 /// In the case that a relevant loop exit value cannot be computed, the 00510 /// original value V is returned. 00511 const SCEV *getSCEVAtScope(const SCEV *S, const Loop *L); 00512 00513 /// getSCEVAtScope - This is a convenience function which does 00514 /// getSCEVAtScope(getSCEV(V), L). 00515 const SCEV *getSCEVAtScope(Value *V, const Loop *L); 00516 00517 /// isLoopGuardedByCond - Test whether entry to the loop is protected by 00518 /// a conditional between LHS and RHS. This is used to help avoid max 00519 /// expressions in loop trip counts, and to eliminate casts. 00520 bool isLoopGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, 00521 const SCEV *LHS, const SCEV *RHS); 00522 00523 /// isLoopBackedgeGuardedByCond - Test whether the backedge of the loop is 00524 /// protected by a conditional between LHS and RHS. This is used to 00525 /// to eliminate casts. 00526 bool isLoopBackedgeGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, 00527 const SCEV *LHS, const SCEV *RHS); 00528 00529 /// getBackedgeTakenCount - If the specified loop has a predictable 00530 /// backedge-taken count, return it, otherwise return a SCEVCouldNotCompute 00531 /// object. The backedge-taken count is the number of times the loop header 00532 /// will be branched to from within the loop. This is one less than the 00533 /// trip count of the loop, since it doesn't count the first iteration, 00534 /// when the header is branched to from outside the loop. 00535 /// 00536 /// Note that it is not valid to call this method on a loop without a 00537 /// loop-invariant backedge-taken count (see 00538 /// hasLoopInvariantBackedgeTakenCount). 00539 /// 00540 const SCEV *getBackedgeTakenCount(const Loop *L); 00541 00542 /// getMaxBackedgeTakenCount - Similar to getBackedgeTakenCount, except 00543 /// return the least SCEV value that is known never to be less than the 00544 /// actual backedge taken count. 00545 const SCEV *getMaxBackedgeTakenCount(const Loop *L); 00546 00547 /// hasLoopInvariantBackedgeTakenCount - Return true if the specified loop 00548 /// has an analyzable loop-invariant backedge-taken count. 00549 bool hasLoopInvariantBackedgeTakenCount(const Loop *L); 00550 00551 /// forgetLoopBackedgeTakenCount - This method should be called by the 00552 /// client when it has changed a loop in a way that may effect 00553 /// ScalarEvolution's ability to compute a trip count, or if the loop 00554 /// is deleted. 00555 void forgetLoopBackedgeTakenCount(const Loop *L); 00556 00557 /// GetMinTrailingZeros - Determine the minimum number of zero bits that S 00558 /// is guaranteed to end in (at every loop iteration). It is, at the same 00559 /// time, the minimum number of times S is divisible by 2. For example, 00560 /// given {4,+,8} it returns 2. If S is guaranteed to be 0, it returns the 00561 /// bitwidth of S. 00562 uint32_t GetMinTrailingZeros(const SCEV *S); 00563 00564 /// getUnsignedRange - Determine the unsigned range for a particular SCEV. 00565 /// 00566 ConstantRange getUnsignedRange(const SCEV *S); 00567 00568 /// getSignedRange - Determine the signed range for a particular SCEV. 00569 /// 00570 ConstantRange getSignedRange(const SCEV *S); 00571 00572 /// isKnownNegative - Test if the given expression is known to be negative. 00573 /// 00574 bool isKnownNegative(const SCEV *S); 00575 00576 /// isKnownPositive - Test if the given expression is known to be positive. 00577 /// 00578 bool isKnownPositive(const SCEV *S); 00579 00580 /// isKnownNonNegative - Test if the given expression is known to be 00581 /// non-negative. 00582 /// 00583 bool isKnownNonNegative(const SCEV *S); 00584 00585 /// isKnownNonPositive - Test if the given expression is known to be 00586 /// non-positive. 00587 /// 00588 bool isKnownNonPositive(const SCEV *S); 00589 00590 /// isKnownNonZero - Test if the given expression is known to be 00591 /// non-zero. 00592 /// 00593 bool isKnownNonZero(const SCEV *S); 00594 00595 /// isKnownNonZero - Test if the given expression is known to satisfy 00596 /// the condition described by Pred, LHS, and RHS. 00597 /// 00598 bool isKnownPredicate(ICmpInst::Predicate Pred, 00599 const SCEV *LHS, const SCEV *RHS); 00600 00601 virtual bool runOnFunction(Function &F); 00602 virtual void releaseMemory(); 00603 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 00604 void print(raw_ostream &OS, const Module* = 0) const; 00605 virtual void print(std::ostream &OS, const Module* = 0) const; 00606 void print(std::ostream *OS, const Module* M = 0) const { 00607 if (OS) print(*OS, M); 00608 } 00609 00610 private: 00611 FoldingSet<SCEV> UniqueSCEVs; 00612 BumpPtrAllocator SCEVAllocator; 00613 }; 00614 } 00615 00616 #endif