ScalarEvolution.h revision 1b342583f6fc42f548912632f6aa24fc6e11986a
1//===- llvm/Analysis/ScalarEvolution.h - Scalar Evolution -------*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// The ScalarEvolution class is an LLVM pass which can be used to analyze and 11// catagorize scalar expressions in loops. It specializes in recognizing 12// general induction variables, representing them with the abstract and opaque 13// SCEV class. Given this analysis, trip counts of loops and other important 14// properties can be obtained. 15// 16// This analysis is primarily useful for induction variable substitution and 17// strength reduction. 18// 19//===----------------------------------------------------------------------===// 20 21#ifndef LLVM_ANALYSIS_SCALAREVOLUTION_H 22#define LLVM_ANALYSIS_SCALAREVOLUTION_H 23 24#include "llvm/Pass.h" 25#include "llvm/Analysis/LoopInfo.h" 26#include "llvm/Support/DataTypes.h" 27#include "llvm/Support/ValueHandle.h" 28#include "llvm/Support/Allocator.h" 29#include "llvm/Support/ConstantRange.h" 30#include "llvm/ADT/FoldingSet.h" 31#include "llvm/ADT/DenseMap.h" 32#include <iosfwd> 33 34namespace llvm { 35 class APInt; 36 class ConstantInt; 37 class Type; 38 class ScalarEvolution; 39 class TargetData; 40 class LLVMContext; 41 42 /// SCEV - This class represents an analyzed expression in the program. These 43 /// are opaque objects that the client is not allowed to do much with 44 /// directly. 45 /// 46 class SCEV : public FoldingSetNode { 47 const unsigned SCEVType; // The SCEV baseclass this node corresponds to 48 49 SCEV(const SCEV &); // DO NOT IMPLEMENT 50 void operator=(const SCEV &); // DO NOT IMPLEMENT 51 protected: 52 virtual ~SCEV(); 53 public: 54 explicit SCEV(unsigned SCEVTy) : 55 SCEVType(SCEVTy) {} 56 57 virtual void Profile(FoldingSetNodeID &ID) const = 0; 58 59 unsigned getSCEVType() const { return SCEVType; } 60 61 /// isLoopInvariant - Return true if the value of this SCEV is unchanging in 62 /// the specified loop. 63 virtual bool isLoopInvariant(const Loop *L) const = 0; 64 65 /// hasComputableLoopEvolution - Return true if this SCEV changes value in a 66 /// known way in the specified loop. This property being true implies that 67 /// the value is variant in the loop AND that we can emit an expression to 68 /// compute the value of the expression at any particular loop iteration. 69 virtual bool hasComputableLoopEvolution(const Loop *L) const = 0; 70 71 /// getType - Return the LLVM type of this SCEV expression. 72 /// 73 virtual const Type *getType() const = 0; 74 75 /// isZero - Return true if the expression is a constant zero. 76 /// 77 bool isZero() const; 78 79 /// isOne - Return true if the expression is a constant one. 80 /// 81 bool isOne() const; 82 83 /// isAllOnesValue - Return true if the expression is a constant 84 /// all-ones value. 85 /// 86 bool isAllOnesValue() const; 87 88 /// replaceSymbolicValuesWithConcrete - If this SCEV internally references 89 /// the symbolic value "Sym", construct and return a new SCEV that produces 90 /// the same value, but which uses the concrete value Conc instead of the 91 /// symbolic value. If this SCEV does not use the symbolic value, it 92 /// returns itself. 93 virtual const SCEV * 94 replaceSymbolicValuesWithConcrete(const SCEV *Sym, 95 const SCEV *Conc, 96 ScalarEvolution &SE) const = 0; 97 98 /// dominates - Return true if elements that makes up this SCEV dominates 99 /// the specified basic block. 100 virtual bool dominates(BasicBlock *BB, DominatorTree *DT) const = 0; 101 102 /// print - Print out the internal representation of this scalar to the 103 /// specified stream. This should really only be used for debugging 104 /// purposes. 105 virtual void print(raw_ostream &OS) const = 0; 106 void print(std::ostream &OS) const; 107 void print(std::ostream *OS) const { if (OS) print(*OS); } 108 109 /// dump - This method is used for debugging. 110 /// 111 void dump() const; 112 }; 113 114 inline raw_ostream &operator<<(raw_ostream &OS, const SCEV &S) { 115 S.print(OS); 116 return OS; 117 } 118 119 inline std::ostream &operator<<(std::ostream &OS, const SCEV &S) { 120 S.print(OS); 121 return OS; 122 } 123 124 /// SCEVCouldNotCompute - An object of this class is returned by queries that 125 /// could not be answered. For example, if you ask for the number of 126 /// iterations of a linked-list traversal loop, you will get one of these. 127 /// None of the standard SCEV operations are valid on this class, it is just a 128 /// marker. 129 struct SCEVCouldNotCompute : public SCEV { 130 SCEVCouldNotCompute(); 131 132 // None of these methods are valid for this object. 133 virtual void Profile(FoldingSetNodeID &ID) const; 134 virtual bool isLoopInvariant(const Loop *L) const; 135 virtual const Type *getType() const; 136 virtual bool hasComputableLoopEvolution(const Loop *L) const; 137 virtual void print(raw_ostream &OS) const; 138 virtual const SCEV * 139 replaceSymbolicValuesWithConcrete(const SCEV *Sym, 140 const SCEV *Conc, 141 ScalarEvolution &SE) const; 142 143 virtual bool dominates(BasicBlock *BB, DominatorTree *DT) const { 144 return true; 145 } 146 147 /// Methods for support type inquiry through isa, cast, and dyn_cast: 148 static inline bool classof(const SCEVCouldNotCompute *S) { return true; } 149 static bool classof(const SCEV *S); 150 }; 151 152 /// ScalarEvolution - This class is the main scalar evolution driver. Because 153 /// client code (intentionally) can't do much with the SCEV objects directly, 154 /// they must ask this class for services. 155 /// 156 class ScalarEvolution : public FunctionPass { 157 /// SCEVCallbackVH - A CallbackVH to arrange for ScalarEvolution to be 158 /// notified whenever a Value is deleted. 159 class SCEVCallbackVH : public CallbackVH { 160 ScalarEvolution *SE; 161 virtual void deleted(); 162 virtual void allUsesReplacedWith(Value *New); 163 public: 164 SCEVCallbackVH(Value *V, ScalarEvolution *SE = 0); 165 }; 166 167 friend class SCEVCallbackVH; 168 friend class SCEVExpander; 169 170 /// F - The function we are analyzing. 171 /// 172 Function *F; 173 174 /// LI - The loop information for the function we are currently analyzing. 175 /// 176 LoopInfo *LI; 177 178 /// TD - The target data information for the target we are targetting. 179 /// 180 TargetData *TD; 181 182 /// CouldNotCompute - This SCEV is used to represent unknown trip 183 /// counts and things. 184 SCEVCouldNotCompute CouldNotCompute; 185 186 /// Scalars - This is a cache of the scalars we have analyzed so far. 187 /// 188 std::map<SCEVCallbackVH, const SCEV *> Scalars; 189 190 /// BackedgeTakenInfo - Information about the backedge-taken count 191 /// of a loop. This currently inclues an exact count and a maximum count. 192 /// 193 struct BackedgeTakenInfo { 194 /// Exact - An expression indicating the exact backedge-taken count of 195 /// the loop if it is known, or a SCEVCouldNotCompute otherwise. 196 const SCEV *Exact; 197 198 /// Max - An expression indicating the least maximum backedge-taken 199 /// count of the loop that is known, or a SCEVCouldNotCompute. 200 const SCEV *Max; 201 202 /*implicit*/ BackedgeTakenInfo(const SCEV *exact) : 203 Exact(exact), Max(exact) {} 204 205 BackedgeTakenInfo(const SCEV *exact, const SCEV *max) : 206 Exact(exact), Max(max) {} 207 208 /// hasAnyInfo - Test whether this BackedgeTakenInfo contains any 209 /// computed information, or whether it's all SCEVCouldNotCompute 210 /// values. 211 bool hasAnyInfo() const { 212 return !isa<SCEVCouldNotCompute>(Exact) || 213 !isa<SCEVCouldNotCompute>(Max); 214 } 215 }; 216 217 /// BackedgeTakenCounts - Cache the backedge-taken count of the loops for 218 /// this function as they are computed. 219 std::map<const Loop*, BackedgeTakenInfo> BackedgeTakenCounts; 220 221 /// ConstantEvolutionLoopExitValue - This map contains entries for all of 222 /// the PHI instructions that we attempt to compute constant evolutions for. 223 /// This allows us to avoid potentially expensive recomputation of these 224 /// properties. An instruction maps to null if we are unable to compute its 225 /// exit value. 226 std::map<PHINode*, Constant*> ConstantEvolutionLoopExitValue; 227 228 /// ValuesAtScopes - This map contains entries for all the instructions 229 /// that we attempt to compute getSCEVAtScope information for without 230 /// using SCEV techniques, which can be expensive. 231 std::map<Instruction *, std::map<const Loop *, Constant *> > ValuesAtScopes; 232 233 /// createSCEV - We know that there is no SCEV for the specified value. 234 /// Analyze the expression. 235 const SCEV *createSCEV(Value *V); 236 237 /// createNodeForPHI - Provide the special handling we need to analyze PHI 238 /// SCEVs. 239 const SCEV *createNodeForPHI(PHINode *PN); 240 241 /// createNodeForGEP - Provide the special handling we need to analyze GEP 242 /// SCEVs. 243 const SCEV *createNodeForGEP(User *GEP); 244 245 /// ReplaceSymbolicValueWithConcrete - This looks up the computed SCEV value 246 /// for the specified instruction and replaces any references to the 247 /// symbolic value SymName with the specified value. This is used during 248 /// PHI resolution. 249 void ReplaceSymbolicValueWithConcrete(Instruction *I, 250 const SCEV *SymName, 251 const SCEV *NewVal); 252 253 /// getBECount - Subtract the end and start values and divide by the step, 254 /// rounding up, to get the number of times the backedge is executed. Return 255 /// CouldNotCompute if an intermediate computation overflows. 256 const SCEV *getBECount(const SCEV *Start, 257 const SCEV *End, 258 const SCEV *Step); 259 260 /// getBackedgeTakenInfo - Return the BackedgeTakenInfo for the given 261 /// loop, lazily computing new values if the loop hasn't been analyzed 262 /// yet. 263 const BackedgeTakenInfo &getBackedgeTakenInfo(const Loop *L); 264 265 /// ComputeBackedgeTakenCount - Compute the number of times the specified 266 /// loop will iterate. 267 BackedgeTakenInfo ComputeBackedgeTakenCount(const Loop *L); 268 269 /// ComputeBackedgeTakenCountFromExit - Compute the number of times the 270 /// backedge of the specified loop will execute if it exits via the 271 /// specified block. 272 BackedgeTakenInfo ComputeBackedgeTakenCountFromExit(const Loop *L, 273 BasicBlock *ExitingBlock); 274 275 /// ComputeBackedgeTakenCountFromExitCond - Compute the number of times the 276 /// backedge of the specified loop will execute if its exit condition 277 /// were a conditional branch of ExitCond, TBB, and FBB. 278 BackedgeTakenInfo 279 ComputeBackedgeTakenCountFromExitCond(const Loop *L, 280 Value *ExitCond, 281 BasicBlock *TBB, 282 BasicBlock *FBB); 283 284 /// ComputeBackedgeTakenCountFromExitCondICmp - Compute the number of 285 /// times the backedge of the specified loop will execute if its exit 286 /// condition were a conditional branch of the ICmpInst ExitCond, TBB, 287 /// and FBB. 288 BackedgeTakenInfo 289 ComputeBackedgeTakenCountFromExitCondICmp(const Loop *L, 290 ICmpInst *ExitCond, 291 BasicBlock *TBB, 292 BasicBlock *FBB); 293 294 /// ComputeLoadConstantCompareBackedgeTakenCount - Given an exit condition 295 /// of 'icmp op load X, cst', try to see if we can compute the trip count. 296 const SCEV * 297 ComputeLoadConstantCompareBackedgeTakenCount(LoadInst *LI, 298 Constant *RHS, 299 const Loop *L, 300 ICmpInst::Predicate p); 301 302 /// ComputeBackedgeTakenCountExhaustively - If the trip is known to execute 303 /// a constant number of times (the condition evolves only from constants), 304 /// try to evaluate a few iterations of the loop until we get the exit 305 /// condition gets a value of ExitWhen (true or false). If we cannot 306 /// evaluate the trip count of the loop, return CouldNotCompute. 307 const SCEV *ComputeBackedgeTakenCountExhaustively(const Loop *L, 308 Value *Cond, 309 bool ExitWhen); 310 311 /// HowFarToZero - Return the number of times a backedge comparing the 312 /// specified value to zero will execute. If not computable, return 313 /// CouldNotCompute. 314 const SCEV *HowFarToZero(const SCEV *V, const Loop *L); 315 316 /// HowFarToNonZero - Return the number of times a backedge checking the 317 /// specified value for nonzero will execute. If not computable, return 318 /// CouldNotCompute. 319 const SCEV *HowFarToNonZero(const SCEV *V, const Loop *L); 320 321 /// HowManyLessThans - Return the number of times a backedge containing the 322 /// specified less-than comparison will execute. If not computable, return 323 /// CouldNotCompute. isSigned specifies whether the less-than is signed. 324 BackedgeTakenInfo HowManyLessThans(const SCEV *LHS, const SCEV *RHS, 325 const Loop *L, bool isSigned); 326 327 /// getLoopPredecessor - If the given loop's header has exactly one unique 328 /// predecessor outside the loop, return it. Otherwise return null. 329 BasicBlock *getLoopPredecessor(const Loop *L); 330 331 /// getPredecessorWithUniqueSuccessorForBB - Return a predecessor of BB 332 /// (which may not be an immediate predecessor) which has exactly one 333 /// successor from which BB is reachable, or null if no such block is 334 /// found. 335 BasicBlock* getPredecessorWithUniqueSuccessorForBB(BasicBlock *BB); 336 337 /// isNecessaryCond - Test whether the condition described by Pred, LHS, 338 /// and RHS is a necessary condition for the given Cond value to evaluate 339 /// to true. 340 bool isNecessaryCond(Value *Cond, ICmpInst::Predicate Pred, 341 const SCEV *LHS, const SCEV *RHS, 342 bool Inverse); 343 344 /// isNecessaryCondOperands - Test whether the condition described by Pred, 345 /// LHS, and RHS is a necessary condition for the condition described by 346 /// Pred, FoundLHS, and FoundRHS to evaluate to true. 347 bool isNecessaryCondOperands(ICmpInst::Predicate Pred, 348 const SCEV *LHS, const SCEV *RHS, 349 const SCEV *FoundLHS, const SCEV *FoundRHS); 350 351 /// getConstantEvolutionLoopExitValue - If we know that the specified Phi is 352 /// in the header of its containing loop, we know the loop executes a 353 /// constant number of times, and the PHI node is just a recurrence 354 /// involving constants, fold it. 355 Constant *getConstantEvolutionLoopExitValue(PHINode *PN, const APInt& BEs, 356 const Loop *L); 357 358 public: 359 static char ID; // Pass identification, replacement for typeid 360 ScalarEvolution(); 361 362 LLVMContext *getContext() const { return Context; } 363 364 /// isSCEVable - Test if values of the given type are analyzable within 365 /// the SCEV framework. This primarily includes integer types, and it 366 /// can optionally include pointer types if the ScalarEvolution class 367 /// has access to target-specific information. 368 bool isSCEVable(const Type *Ty) const; 369 370 /// getTypeSizeInBits - Return the size in bits of the specified type, 371 /// for which isSCEVable must return true. 372 uint64_t getTypeSizeInBits(const Type *Ty) const; 373 374 /// getEffectiveSCEVType - Return a type with the same bitwidth as 375 /// the given type and which represents how SCEV will treat the given 376 /// type, for which isSCEVable must return true. For pointer types, 377 /// this is the pointer-sized integer type. 378 const Type *getEffectiveSCEVType(const Type *Ty) const; 379 380 /// getSCEV - Return a SCEV expression handle for the full generality of the 381 /// specified expression. 382 const SCEV *getSCEV(Value *V); 383 384 const SCEV *getConstant(ConstantInt *V); 385 const SCEV *getConstant(const APInt& Val); 386 const SCEV *getConstant(const Type *Ty, uint64_t V, bool isSigned = false); 387 const SCEV *getTruncateExpr(const SCEV *Op, const Type *Ty); 388 const SCEV *getZeroExtendExpr(const SCEV *Op, const Type *Ty); 389 const SCEV *getSignExtendExpr(const SCEV *Op, const Type *Ty); 390 const SCEV *getAnyExtendExpr(const SCEV *Op, const Type *Ty); 391 const SCEV *getAddExpr(SmallVectorImpl<const SCEV *> &Ops); 392 const SCEV *getAddExpr(const SCEV *LHS, const SCEV *RHS) { 393 SmallVector<const SCEV *, 2> Ops; 394 Ops.push_back(LHS); 395 Ops.push_back(RHS); 396 return getAddExpr(Ops); 397 } 398 const SCEV *getAddExpr(const SCEV *Op0, const SCEV *Op1, 399 const SCEV *Op2) { 400 SmallVector<const SCEV *, 3> Ops; 401 Ops.push_back(Op0); 402 Ops.push_back(Op1); 403 Ops.push_back(Op2); 404 return getAddExpr(Ops); 405 } 406 const SCEV *getMulExpr(SmallVectorImpl<const SCEV *> &Ops); 407 const SCEV *getMulExpr(const SCEV *LHS, const SCEV *RHS) { 408 SmallVector<const SCEV *, 2> Ops; 409 Ops.push_back(LHS); 410 Ops.push_back(RHS); 411 return getMulExpr(Ops); 412 } 413 const SCEV *getUDivExpr(const SCEV *LHS, const SCEV *RHS); 414 const SCEV *getAddRecExpr(const SCEV *Start, const SCEV *Step, 415 const Loop *L); 416 const SCEV *getAddRecExpr(SmallVectorImpl<const SCEV *> &Operands, 417 const Loop *L); 418 const SCEV *getAddRecExpr(const SmallVectorImpl<const SCEV *> &Operands, 419 const Loop *L) { 420 SmallVector<const SCEV *, 4> NewOp(Operands.begin(), Operands.end()); 421 return getAddRecExpr(NewOp, L); 422 } 423 const SCEV *getSMaxExpr(const SCEV *LHS, const SCEV *RHS); 424 const SCEV *getSMaxExpr(SmallVectorImpl<const SCEV *> &Operands); 425 const SCEV *getUMaxExpr(const SCEV *LHS, const SCEV *RHS); 426 const SCEV *getUMaxExpr(SmallVectorImpl<const SCEV *> &Operands); 427 const SCEV *getSMinExpr(const SCEV *LHS, const SCEV *RHS); 428 const SCEV *getUMinExpr(const SCEV *LHS, const SCEV *RHS); 429 const SCEV *getUnknown(Value *V); 430 const SCEV *getCouldNotCompute(); 431 432 /// getNegativeSCEV - Return the SCEV object corresponding to -V. 433 /// 434 const SCEV *getNegativeSCEV(const SCEV *V); 435 436 /// getNotSCEV - Return the SCEV object corresponding to ~V. 437 /// 438 const SCEV *getNotSCEV(const SCEV *V); 439 440 /// getMinusSCEV - Return LHS-RHS. 441 /// 442 const SCEV *getMinusSCEV(const SCEV *LHS, 443 const SCEV *RHS); 444 445 /// getTruncateOrZeroExtend - Return a SCEV corresponding to a conversion 446 /// of the input value to the specified type. If the type must be 447 /// extended, it is zero extended. 448 const SCEV *getTruncateOrZeroExtend(const SCEV *V, const Type *Ty); 449 450 /// getTruncateOrSignExtend - Return a SCEV corresponding to a conversion 451 /// of the input value to the specified type. If the type must be 452 /// extended, it is sign extended. 453 const SCEV *getTruncateOrSignExtend(const SCEV *V, const Type *Ty); 454 455 /// getNoopOrZeroExtend - Return a SCEV corresponding to a conversion of 456 /// the input value to the specified type. If the type must be extended, 457 /// it is zero extended. The conversion must not be narrowing. 458 const SCEV *getNoopOrZeroExtend(const SCEV *V, const Type *Ty); 459 460 /// getNoopOrSignExtend - Return a SCEV corresponding to a conversion of 461 /// the input value to the specified type. If the type must be extended, 462 /// it is sign extended. The conversion must not be narrowing. 463 const SCEV *getNoopOrSignExtend(const SCEV *V, const Type *Ty); 464 465 /// getNoopOrAnyExtend - Return a SCEV corresponding to a conversion of 466 /// the input value to the specified type. If the type must be extended, 467 /// it is extended with unspecified bits. The conversion must not be 468 /// narrowing. 469 const SCEV *getNoopOrAnyExtend(const SCEV *V, const Type *Ty); 470 471 /// getTruncateOrNoop - Return a SCEV corresponding to a conversion of the 472 /// input value to the specified type. The conversion must not be 473 /// widening. 474 const SCEV *getTruncateOrNoop(const SCEV *V, const Type *Ty); 475 476 /// getIntegerSCEV - Given a SCEVable type, create a constant for the 477 /// specified signed integer value and return a SCEV for the constant. 478 const SCEV *getIntegerSCEV(int Val, const Type *Ty); 479 480 /// getUMaxFromMismatchedTypes - Promote the operands to the wider of 481 /// the types using zero-extension, and then perform a umax operation 482 /// with them. 483 const SCEV *getUMaxFromMismatchedTypes(const SCEV *LHS, 484 const SCEV *RHS); 485 486 /// getUMinFromMismatchedTypes - Promote the operands to the wider of 487 /// the types using zero-extension, and then perform a umin operation 488 /// with them. 489 const SCEV *getUMinFromMismatchedTypes(const SCEV *LHS, 490 const SCEV *RHS); 491 492 /// hasSCEV - Return true if the SCEV for this value has already been 493 /// computed. 494 bool hasSCEV(Value *V) const; 495 496 /// setSCEV - Insert the specified SCEV into the map of current SCEVs for 497 /// the specified value. 498 void setSCEV(Value *V, const SCEV *H); 499 500 /// getSCEVAtScope - Return a SCEV expression handle for the specified value 501 /// at the specified scope in the program. The L value specifies a loop 502 /// nest to evaluate the expression at, where null is the top-level or a 503 /// specified loop is immediately inside of the loop. 504 /// 505 /// This method can be used to compute the exit value for a variable defined 506 /// in a loop by querying what the value will hold in the parent loop. 507 /// 508 /// In the case that a relevant loop exit value cannot be computed, the 509 /// original value V is returned. 510 const SCEV *getSCEVAtScope(const SCEV *S, const Loop *L); 511 512 /// getSCEVAtScope - This is a convenience function which does 513 /// getSCEVAtScope(getSCEV(V), L). 514 const SCEV *getSCEVAtScope(Value *V, const Loop *L); 515 516 /// isLoopGuardedByCond - Test whether entry to the loop is protected by 517 /// a conditional between LHS and RHS. This is used to help avoid max 518 /// expressions in loop trip counts, and to eliminate casts. 519 bool isLoopGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, 520 const SCEV *LHS, const SCEV *RHS); 521 522 /// isLoopBackedgeGuardedByCond - Test whether the backedge of the loop is 523 /// protected by a conditional between LHS and RHS. This is used to 524 /// to eliminate casts. 525 bool isLoopBackedgeGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, 526 const SCEV *LHS, const SCEV *RHS); 527 528 /// getBackedgeTakenCount - If the specified loop has a predictable 529 /// backedge-taken count, return it, otherwise return a SCEVCouldNotCompute 530 /// object. The backedge-taken count is the number of times the loop header 531 /// will be branched to from within the loop. This is one less than the 532 /// trip count of the loop, since it doesn't count the first iteration, 533 /// when the header is branched to from outside the loop. 534 /// 535 /// Note that it is not valid to call this method on a loop without a 536 /// loop-invariant backedge-taken count (see 537 /// hasLoopInvariantBackedgeTakenCount). 538 /// 539 const SCEV *getBackedgeTakenCount(const Loop *L); 540 541 /// getMaxBackedgeTakenCount - Similar to getBackedgeTakenCount, except 542 /// return the least SCEV value that is known never to be less than the 543 /// actual backedge taken count. 544 const SCEV *getMaxBackedgeTakenCount(const Loop *L); 545 546 /// hasLoopInvariantBackedgeTakenCount - Return true if the specified loop 547 /// has an analyzable loop-invariant backedge-taken count. 548 bool hasLoopInvariantBackedgeTakenCount(const Loop *L); 549 550 /// forgetLoopBackedgeTakenCount - This method should be called by the 551 /// client when it has changed a loop in a way that may effect 552 /// ScalarEvolution's ability to compute a trip count, or if the loop 553 /// is deleted. 554 void forgetLoopBackedgeTakenCount(const Loop *L); 555 556 /// GetMinTrailingZeros - Determine the minimum number of zero bits that S 557 /// is guaranteed to end in (at every loop iteration). It is, at the same 558 /// time, the minimum number of times S is divisible by 2. For example, 559 /// given {4,+,8} it returns 2. If S is guaranteed to be 0, it returns the 560 /// bitwidth of S. 561 uint32_t GetMinTrailingZeros(const SCEV *S); 562 563 /// getUnsignedRange - Determine the unsigned range for a particular SCEV. 564 /// 565 ConstantRange getUnsignedRange(const SCEV *S); 566 567 /// getSignedRange - Determine the signed range for a particular SCEV. 568 /// 569 ConstantRange getSignedRange(const SCEV *S); 570 571 /// isKnownNegative - Test if the given expression is known to be negative. 572 /// 573 bool isKnownNegative(const SCEV *S); 574 575 /// isKnownPositive - Test if the given expression is known to be positive. 576 /// 577 bool isKnownPositive(const SCEV *S); 578 579 /// isKnownNonNegative - Test if the given expression is known to be 580 /// non-negative. 581 /// 582 bool isKnownNonNegative(const SCEV *S); 583 584 /// isKnownNonPositive - Test if the given expression is known to be 585 /// non-positive. 586 /// 587 bool isKnownNonPositive(const SCEV *S); 588 589 /// isKnownNonZero - Test if the given expression is known to be 590 /// non-zero. 591 /// 592 bool isKnownNonZero(const SCEV *S); 593 594 /// isKnownNonZero - Test if the given expression is known to satisfy 595 /// the condition described by Pred, LHS, and RHS. 596 /// 597 bool isKnownPredicate(ICmpInst::Predicate Pred, 598 const SCEV *LHS, const SCEV *RHS); 599 600 virtual bool runOnFunction(Function &F); 601 virtual void releaseMemory(); 602 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 603 void print(raw_ostream &OS, const Module* = 0) const; 604 virtual void print(std::ostream &OS, const Module* = 0) const; 605 void print(std::ostream *OS, const Module* M = 0) const { 606 if (OS) print(*OS, M); 607 } 608 609 private: 610 FoldingSet<SCEV> UniqueSCEVs; 611 BumpPtrAllocator SCEVAllocator; 612 }; 613} 614 615#endif 616