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