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 // categorize 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/ADT/DenseSet.h" 25 #include "llvm/ADT/FoldingSet.h" 26 #include "llvm/IR/ConstantRange.h" 27 #include "llvm/IR/Function.h" 28 #include "llvm/IR/Instructions.h" 29 #include "llvm/IR/Operator.h" 30 #include "llvm/IR/PassManager.h" 31 #include "llvm/IR/ValueHandle.h" 32 #include "llvm/Pass.h" 33 #include "llvm/Support/Allocator.h" 34 #include "llvm/Support/DataTypes.h" 35 #include <map> 36 37 namespace llvm { 38 class APInt; 39 class AssumptionCache; 40 class Constant; 41 class ConstantInt; 42 class DominatorTree; 43 class Type; 44 class ScalarEvolution; 45 class DataLayout; 46 class TargetLibraryInfo; 47 class LLVMContext; 48 class Loop; 49 class LoopInfo; 50 class Operator; 51 class SCEV; 52 class SCEVAddRecExpr; 53 class SCEVConstant; 54 class SCEVExpander; 55 class SCEVPredicate; 56 class SCEVUnknown; 57 58 template <> struct FoldingSetTrait<SCEV>; 59 template <> struct FoldingSetTrait<SCEVPredicate>; 60 61 /// This class represents an analyzed expression in the program. These are 62 /// opaque objects that the client is not allowed to do much with directly. 63 /// 64 class SCEV : public FoldingSetNode { 65 friend struct FoldingSetTrait<SCEV>; 66 67 /// A reference to an Interned FoldingSetNodeID for this node. The 68 /// ScalarEvolution's BumpPtrAllocator holds the data. 69 FoldingSetNodeIDRef FastID; 70 71 // The SCEV baseclass this node corresponds to 72 const unsigned short SCEVType; 73 74 protected: 75 /// This field is initialized to zero and may be used in subclasses to store 76 /// miscellaneous information. 77 unsigned short SubclassData; 78 79 private: 80 SCEV(const SCEV &) = delete; 81 void operator=(const SCEV &) = delete; 82 83 public: 84 /// NoWrapFlags are bitfield indices into SubclassData. 85 /// 86 /// Add and Mul expressions may have no-unsigned-wrap <NUW> or 87 /// no-signed-wrap <NSW> properties, which are derived from the IR 88 /// operator. NSW is a misnomer that we use to mean no signed overflow or 89 /// underflow. 90 /// 91 /// AddRec expressions may have a no-self-wraparound <NW> property if, in 92 /// the integer domain, abs(step) * max-iteration(loop) <= 93 /// unsigned-max(bitwidth). This means that the recurrence will never reach 94 /// its start value if the step is non-zero. Computing the same value on 95 /// each iteration is not considered wrapping, and recurrences with step = 0 96 /// are trivially <NW>. <NW> is independent of the sign of step and the 97 /// value the add recurrence starts with. 98 /// 99 /// Note that NUW and NSW are also valid properties of a recurrence, and 100 /// either implies NW. For convenience, NW will be set for a recurrence 101 /// whenever either NUW or NSW are set. 102 enum NoWrapFlags { FlagAnyWrap = 0, // No guarantee. 103 FlagNW = (1 << 0), // No self-wrap. 104 FlagNUW = (1 << 1), // No unsigned wrap. 105 FlagNSW = (1 << 2), // No signed wrap. 106 NoWrapMask = (1 << 3) -1 }; 107 108 explicit SCEV(const FoldingSetNodeIDRef ID, unsigned SCEVTy) : 109 FastID(ID), SCEVType(SCEVTy), SubclassData(0) {} 110 111 unsigned getSCEVType() const { return SCEVType; } 112 113 /// Return the LLVM type of this SCEV expression. 114 /// 115 Type *getType() const; 116 117 /// Return true if the expression is a constant zero. 118 /// 119 bool isZero() const; 120 121 /// Return true if the expression is a constant one. 122 /// 123 bool isOne() const; 124 125 /// Return true if the expression is a constant all-ones value. 126 /// 127 bool isAllOnesValue() const; 128 129 /// Return true if the specified scev is negated, but not a constant. 130 bool isNonConstantNegative() const; 131 132 /// Print out the internal representation of this scalar to the specified 133 /// stream. This should really only be used for debugging purposes. 134 void print(raw_ostream &OS) const; 135 136 /// This method is used for debugging. 137 /// 138 void dump() const; 139 }; 140 141 // Specialize FoldingSetTrait for SCEV to avoid needing to compute 142 // temporary FoldingSetNodeID values. 143 template<> struct FoldingSetTrait<SCEV> : DefaultFoldingSetTrait<SCEV> { 144 static void Profile(const SCEV &X, FoldingSetNodeID& ID) { 145 ID = X.FastID; 146 } 147 static bool Equals(const SCEV &X, const FoldingSetNodeID &ID, 148 unsigned IDHash, FoldingSetNodeID &TempID) { 149 return ID == X.FastID; 150 } 151 static unsigned ComputeHash(const SCEV &X, FoldingSetNodeID &TempID) { 152 return X.FastID.ComputeHash(); 153 } 154 }; 155 156 inline raw_ostream &operator<<(raw_ostream &OS, const SCEV &S) { 157 S.print(OS); 158 return OS; 159 } 160 161 /// An object of this class is returned by queries that could not be answered. 162 /// For example, if you ask for the number of iterations of a linked-list 163 /// traversal loop, you will get one of these. None of the standard SCEV 164 /// operations are valid on this class, it is just a marker. 165 struct SCEVCouldNotCompute : public SCEV { 166 SCEVCouldNotCompute(); 167 168 /// Methods for support type inquiry through isa, cast, and dyn_cast: 169 static bool classof(const SCEV *S); 170 }; 171 172 /// SCEVPredicate - This class represents an assumption made using SCEV 173 /// expressions which can be checked at run-time. 174 class SCEVPredicate : public FoldingSetNode { 175 friend struct FoldingSetTrait<SCEVPredicate>; 176 177 /// A reference to an Interned FoldingSetNodeID for this node. The 178 /// ScalarEvolution's BumpPtrAllocator holds the data. 179 FoldingSetNodeIDRef FastID; 180 181 public: 182 enum SCEVPredicateKind { P_Union, P_Equal }; 183 184 protected: 185 SCEVPredicateKind Kind; 186 ~SCEVPredicate() = default; 187 SCEVPredicate(const SCEVPredicate&) = default; 188 SCEVPredicate &operator=(const SCEVPredicate&) = default; 189 190 public: 191 SCEVPredicate(const FoldingSetNodeIDRef ID, SCEVPredicateKind Kind); 192 193 SCEVPredicateKind getKind() const { return Kind; } 194 195 /// \brief Returns the estimated complexity of this predicate. 196 /// This is roughly measured in the number of run-time checks required. 197 virtual unsigned getComplexity() const { return 1; } 198 199 /// \brief Returns true if the predicate is always true. This means that no 200 /// assumptions were made and nothing needs to be checked at run-time. 201 virtual bool isAlwaysTrue() const = 0; 202 203 /// \brief Returns true if this predicate implies \p N. 204 virtual bool implies(const SCEVPredicate *N) const = 0; 205 206 /// \brief Prints a textual representation of this predicate with an 207 /// indentation of \p Depth. 208 virtual void print(raw_ostream &OS, unsigned Depth = 0) const = 0; 209 210 /// \brief Returns the SCEV to which this predicate applies, or nullptr 211 /// if this is a SCEVUnionPredicate. 212 virtual const SCEV *getExpr() const = 0; 213 }; 214 215 inline raw_ostream &operator<<(raw_ostream &OS, const SCEVPredicate &P) { 216 P.print(OS); 217 return OS; 218 } 219 220 // Specialize FoldingSetTrait for SCEVPredicate to avoid needing to compute 221 // temporary FoldingSetNodeID values. 222 template <> 223 struct FoldingSetTrait<SCEVPredicate> 224 : DefaultFoldingSetTrait<SCEVPredicate> { 225 226 static void Profile(const SCEVPredicate &X, FoldingSetNodeID &ID) { 227 ID = X.FastID; 228 } 229 230 static bool Equals(const SCEVPredicate &X, const FoldingSetNodeID &ID, 231 unsigned IDHash, FoldingSetNodeID &TempID) { 232 return ID == X.FastID; 233 } 234 static unsigned ComputeHash(const SCEVPredicate &X, 235 FoldingSetNodeID &TempID) { 236 return X.FastID.ComputeHash(); 237 } 238 }; 239 240 /// SCEVEqualPredicate - This class represents an assumption that two SCEV 241 /// expressions are equal, and this can be checked at run-time. We assume 242 /// that the left hand side is a SCEVUnknown and the right hand side a 243 /// constant. 244 class SCEVEqualPredicate final : public SCEVPredicate { 245 /// We assume that LHS == RHS, where LHS is a SCEVUnknown and RHS a 246 /// constant. 247 const SCEVUnknown *LHS; 248 const SCEVConstant *RHS; 249 250 public: 251 SCEVEqualPredicate(const FoldingSetNodeIDRef ID, const SCEVUnknown *LHS, 252 const SCEVConstant *RHS); 253 254 /// Implementation of the SCEVPredicate interface 255 bool implies(const SCEVPredicate *N) const override; 256 void print(raw_ostream &OS, unsigned Depth = 0) const override; 257 bool isAlwaysTrue() const override; 258 const SCEV *getExpr() const override; 259 260 /// \brief Returns the left hand side of the equality. 261 const SCEVUnknown *getLHS() const { return LHS; } 262 263 /// \brief Returns the right hand side of the equality. 264 const SCEVConstant *getRHS() const { return RHS; } 265 266 /// Methods for support type inquiry through isa, cast, and dyn_cast: 267 static inline bool classof(const SCEVPredicate *P) { 268 return P->getKind() == P_Equal; 269 } 270 }; 271 272 /// SCEVUnionPredicate - This class represents a composition of other 273 /// SCEV predicates, and is the class that most clients will interact with. 274 /// This is equivalent to a logical "AND" of all the predicates in the union. 275 class SCEVUnionPredicate final : public SCEVPredicate { 276 private: 277 typedef DenseMap<const SCEV *, SmallVector<const SCEVPredicate *, 4>> 278 PredicateMap; 279 280 /// Vector with references to all predicates in this union. 281 SmallVector<const SCEVPredicate *, 16> Preds; 282 /// Maps SCEVs to predicates for quick look-ups. 283 PredicateMap SCEVToPreds; 284 285 public: 286 SCEVUnionPredicate(); 287 288 const SmallVectorImpl<const SCEVPredicate *> &getPredicates() const { 289 return Preds; 290 } 291 292 /// \brief Adds a predicate to this union. 293 void add(const SCEVPredicate *N); 294 295 /// \brief Returns a reference to a vector containing all predicates 296 /// which apply to \p Expr. 297 ArrayRef<const SCEVPredicate *> getPredicatesForExpr(const SCEV *Expr); 298 299 /// Implementation of the SCEVPredicate interface 300 bool isAlwaysTrue() const override; 301 bool implies(const SCEVPredicate *N) const override; 302 void print(raw_ostream &OS, unsigned Depth) const override; 303 const SCEV *getExpr() const override; 304 305 /// \brief We estimate the complexity of a union predicate as the size 306 /// number of predicates in the union. 307 unsigned getComplexity() const override { return Preds.size(); } 308 309 /// Methods for support type inquiry through isa, cast, and dyn_cast: 310 static inline bool classof(const SCEVPredicate *P) { 311 return P->getKind() == P_Union; 312 } 313 }; 314 315 /// The main scalar evolution driver. Because client code (intentionally) 316 /// can't do much with the SCEV objects directly, they must ask this class 317 /// for services. 318 class ScalarEvolution { 319 public: 320 /// An enum describing the relationship between a SCEV and a loop. 321 enum LoopDisposition { 322 LoopVariant, ///< The SCEV is loop-variant (unknown). 323 LoopInvariant, ///< The SCEV is loop-invariant. 324 LoopComputable ///< The SCEV varies predictably with the loop. 325 }; 326 327 /// An enum describing the relationship between a SCEV and a basic block. 328 enum BlockDisposition { 329 DoesNotDominateBlock, ///< The SCEV does not dominate the block. 330 DominatesBlock, ///< The SCEV dominates the block. 331 ProperlyDominatesBlock ///< The SCEV properly dominates the block. 332 }; 333 334 /// Convenient NoWrapFlags manipulation that hides enum casts and is 335 /// visible in the ScalarEvolution name space. 336 static SCEV::NoWrapFlags LLVM_ATTRIBUTE_UNUSED_RESULT 337 maskFlags(SCEV::NoWrapFlags Flags, int Mask) { 338 return (SCEV::NoWrapFlags)(Flags & Mask); 339 } 340 static SCEV::NoWrapFlags LLVM_ATTRIBUTE_UNUSED_RESULT 341 setFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OnFlags) { 342 return (SCEV::NoWrapFlags)(Flags | OnFlags); 343 } 344 static SCEV::NoWrapFlags LLVM_ATTRIBUTE_UNUSED_RESULT 345 clearFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OffFlags) { 346 return (SCEV::NoWrapFlags)(Flags & ~OffFlags); 347 } 348 349 private: 350 /// A CallbackVH to arrange for ScalarEvolution to be notified whenever a 351 /// Value is deleted. 352 class SCEVCallbackVH final : public CallbackVH { 353 ScalarEvolution *SE; 354 void deleted() override; 355 void allUsesReplacedWith(Value *New) override; 356 public: 357 SCEVCallbackVH(Value *V, ScalarEvolution *SE = nullptr); 358 }; 359 360 friend class SCEVCallbackVH; 361 friend class SCEVExpander; 362 friend class SCEVUnknown; 363 364 /// The function we are analyzing. 365 /// 366 Function &F; 367 368 /// The target library information for the target we are targeting. 369 /// 370 TargetLibraryInfo &TLI; 371 372 /// The tracker for @llvm.assume intrinsics in this function. 373 AssumptionCache &AC; 374 375 /// The dominator tree. 376 /// 377 DominatorTree &DT; 378 379 /// The loop information for the function we are currently analyzing. 380 /// 381 LoopInfo &LI; 382 383 /// This SCEV is used to represent unknown trip counts and things. 384 std::unique_ptr<SCEVCouldNotCompute> CouldNotCompute; 385 386 /// The typedef for ValueExprMap. 387 /// 388 typedef DenseMap<SCEVCallbackVH, const SCEV *, DenseMapInfo<Value *> > 389 ValueExprMapType; 390 391 /// This is a cache of the values we have analyzed so far. 392 /// 393 ValueExprMapType ValueExprMap; 394 395 /// Mark predicate values currently being processed by isImpliedCond. 396 DenseSet<Value*> PendingLoopPredicates; 397 398 /// Set to true by isLoopBackedgeGuardedByCond when we're walking the set of 399 /// conditions dominating the backedge of a loop. 400 bool WalkingBEDominatingConds; 401 402 /// Set to true by isKnownPredicateViaSplitting when we're trying to prove a 403 /// predicate by splitting it into a set of independent predicates. 404 bool ProvingSplitPredicate; 405 406 /// Information about the number of loop iterations for which a loop exit's 407 /// branch condition evaluates to the not-taken path. This is a temporary 408 /// pair of exact and max expressions that are eventually summarized in 409 /// ExitNotTakenInfo and BackedgeTakenInfo. 410 struct ExitLimit { 411 const SCEV *Exact; 412 const SCEV *Max; 413 414 /*implicit*/ ExitLimit(const SCEV *E) : Exact(E), Max(E) {} 415 416 ExitLimit(const SCEV *E, const SCEV *M) : Exact(E), Max(M) {} 417 418 /// Test whether this ExitLimit contains any computed information, or 419 /// whether it's all SCEVCouldNotCompute values. 420 bool hasAnyInfo() const { 421 return !isa<SCEVCouldNotCompute>(Exact) || 422 !isa<SCEVCouldNotCompute>(Max); 423 } 424 }; 425 426 /// Information about the number of times a particular loop exit may be 427 /// reached before exiting the loop. 428 struct ExitNotTakenInfo { 429 AssertingVH<BasicBlock> ExitingBlock; 430 const SCEV *ExactNotTaken; 431 PointerIntPair<ExitNotTakenInfo*, 1> NextExit; 432 433 ExitNotTakenInfo() : ExitingBlock(nullptr), ExactNotTaken(nullptr) {} 434 435 /// Return true if all loop exits are computable. 436 bool isCompleteList() const { 437 return NextExit.getInt() == 0; 438 } 439 440 void setIncomplete() { NextExit.setInt(1); } 441 442 /// Return a pointer to the next exit's not-taken info. 443 ExitNotTakenInfo *getNextExit() const { 444 return NextExit.getPointer(); 445 } 446 447 void setNextExit(ExitNotTakenInfo *ENT) { NextExit.setPointer(ENT); } 448 }; 449 450 /// Information about the backedge-taken count of a loop. This currently 451 /// includes an exact count and a maximum count. 452 /// 453 class BackedgeTakenInfo { 454 /// A list of computable exits and their not-taken counts. Loops almost 455 /// never have more than one computable exit. 456 ExitNotTakenInfo ExitNotTaken; 457 458 /// An expression indicating the least maximum backedge-taken count of the 459 /// loop that is known, or a SCEVCouldNotCompute. 460 const SCEV *Max; 461 462 public: 463 BackedgeTakenInfo() : Max(nullptr) {} 464 465 /// Initialize BackedgeTakenInfo from a list of exact exit counts. 466 BackedgeTakenInfo( 467 SmallVectorImpl< std::pair<BasicBlock *, const SCEV *> > &ExitCounts, 468 bool Complete, const SCEV *MaxCount); 469 470 /// Test whether this BackedgeTakenInfo contains any computed information, 471 /// or whether it's all SCEVCouldNotCompute values. 472 bool hasAnyInfo() const { 473 return ExitNotTaken.ExitingBlock || !isa<SCEVCouldNotCompute>(Max); 474 } 475 476 /// Return an expression indicating the exact backedge-taken count of the 477 /// loop if it is known, or SCEVCouldNotCompute otherwise. This is the 478 /// number of times the loop header can be guaranteed to execute, minus 479 /// one. 480 const SCEV *getExact(ScalarEvolution *SE) const; 481 482 /// Return the number of times this loop exit may fall through to the back 483 /// edge, or SCEVCouldNotCompute. The loop is guaranteed not to exit via 484 /// this block before this number of iterations, but may exit via another 485 /// block. 486 const SCEV *getExact(BasicBlock *ExitingBlock, ScalarEvolution *SE) const; 487 488 /// Get the max backedge taken count for the loop. 489 const SCEV *getMax(ScalarEvolution *SE) const; 490 491 /// Return true if any backedge taken count expressions refer to the given 492 /// subexpression. 493 bool hasOperand(const SCEV *S, ScalarEvolution *SE) const; 494 495 /// Invalidate this result and free associated memory. 496 void clear(); 497 }; 498 499 /// Cache the backedge-taken count of the loops for this function as they 500 /// are computed. 501 DenseMap<const Loop*, BackedgeTakenInfo> BackedgeTakenCounts; 502 503 /// This map contains entries for all of the PHI instructions that we 504 /// attempt to compute constant evolutions for. This allows us to avoid 505 /// potentially expensive recomputation of these properties. An instruction 506 /// maps to null if we are unable to compute its exit value. 507 DenseMap<PHINode*, Constant*> ConstantEvolutionLoopExitValue; 508 509 /// This map contains entries for all the expressions that we attempt to 510 /// compute getSCEVAtScope information for, which can be expensive in 511 /// extreme cases. 512 DenseMap<const SCEV *, 513 SmallVector<std::pair<const Loop *, const SCEV *>, 2> > ValuesAtScopes; 514 515 /// Memoized computeLoopDisposition results. 516 DenseMap<const SCEV *, 517 SmallVector<PointerIntPair<const Loop *, 2, LoopDisposition>, 2>> 518 LoopDispositions; 519 520 /// Compute a LoopDisposition value. 521 LoopDisposition computeLoopDisposition(const SCEV *S, const Loop *L); 522 523 /// Memoized computeBlockDisposition results. 524 DenseMap< 525 const SCEV *, 526 SmallVector<PointerIntPair<const BasicBlock *, 2, BlockDisposition>, 2>> 527 BlockDispositions; 528 529 /// Compute a BlockDisposition value. 530 BlockDisposition computeBlockDisposition(const SCEV *S, const BasicBlock *BB); 531 532 /// Memoized results from getRange 533 DenseMap<const SCEV *, ConstantRange> UnsignedRanges; 534 535 /// Memoized results from getRange 536 DenseMap<const SCEV *, ConstantRange> SignedRanges; 537 538 /// Used to parameterize getRange 539 enum RangeSignHint { HINT_RANGE_UNSIGNED, HINT_RANGE_SIGNED }; 540 541 /// Set the memoized range for the given SCEV. 542 const ConstantRange &setRange(const SCEV *S, RangeSignHint Hint, 543 const ConstantRange &CR) { 544 DenseMap<const SCEV *, ConstantRange> &Cache = 545 Hint == HINT_RANGE_UNSIGNED ? UnsignedRanges : SignedRanges; 546 547 std::pair<DenseMap<const SCEV *, ConstantRange>::iterator, bool> Pair = 548 Cache.insert(std::make_pair(S, CR)); 549 if (!Pair.second) 550 Pair.first->second = CR; 551 return Pair.first->second; 552 } 553 554 /// Determine the range for a particular SCEV. 555 ConstantRange getRange(const SCEV *S, RangeSignHint Hint); 556 557 /// We know that there is no SCEV for the specified value. Analyze the 558 /// expression. 559 const SCEV *createSCEV(Value *V); 560 561 /// Provide the special handling we need to analyze PHI SCEVs. 562 const SCEV *createNodeForPHI(PHINode *PN); 563 564 /// Helper function called from createNodeForPHI. 565 const SCEV *createAddRecFromPHI(PHINode *PN); 566 567 /// Helper function called from createNodeForPHI. 568 const SCEV *createNodeFromSelectLikePHI(PHINode *PN); 569 570 /// Provide special handling for a select-like instruction (currently this 571 /// is either a select instruction or a phi node). \p I is the instruction 572 /// being processed, and it is assumed equivalent to "Cond ? TrueVal : 573 /// FalseVal". 574 const SCEV *createNodeForSelectOrPHI(Instruction *I, Value *Cond, 575 Value *TrueVal, Value *FalseVal); 576 577 /// Provide the special handling we need to analyze GEP SCEVs. 578 const SCEV *createNodeForGEP(GEPOperator *GEP); 579 580 /// Implementation code for getSCEVAtScope; called at most once for each 581 /// SCEV+Loop pair. 582 /// 583 const SCEV *computeSCEVAtScope(const SCEV *S, const Loop *L); 584 585 /// This looks up computed SCEV values for all instructions that depend on 586 /// the given instruction and removes them from the ValueExprMap map if they 587 /// reference SymName. This is used during PHI resolution. 588 void ForgetSymbolicName(Instruction *I, const SCEV *SymName); 589 590 /// Return the BackedgeTakenInfo for the given loop, lazily computing new 591 /// values if the loop hasn't been analyzed yet. 592 const BackedgeTakenInfo &getBackedgeTakenInfo(const Loop *L); 593 594 /// Compute the number of times the specified loop will iterate. 595 BackedgeTakenInfo computeBackedgeTakenCount(const Loop *L); 596 597 /// Compute the number of times the backedge of the specified loop will 598 /// execute if it exits via the specified block. 599 ExitLimit computeExitLimit(const Loop *L, BasicBlock *ExitingBlock); 600 601 /// Compute the number of times the backedge of the specified loop will 602 /// execute if its exit condition were a conditional branch of ExitCond, 603 /// TBB, and FBB. 604 ExitLimit computeExitLimitFromCond(const Loop *L, 605 Value *ExitCond, 606 BasicBlock *TBB, 607 BasicBlock *FBB, 608 bool IsSubExpr); 609 610 /// Compute the number of times the backedge of the specified loop will 611 /// execute if its exit condition were a conditional branch of the ICmpInst 612 /// ExitCond, TBB, and FBB. 613 ExitLimit computeExitLimitFromICmp(const Loop *L, 614 ICmpInst *ExitCond, 615 BasicBlock *TBB, 616 BasicBlock *FBB, 617 bool IsSubExpr); 618 619 /// Compute the number of times the backedge of the specified loop will 620 /// execute if its exit condition were a switch with a single exiting case 621 /// to ExitingBB. 622 ExitLimit 623 computeExitLimitFromSingleExitSwitch(const Loop *L, SwitchInst *Switch, 624 BasicBlock *ExitingBB, bool IsSubExpr); 625 626 /// Given an exit condition of 'icmp op load X, cst', try to see if we can 627 /// compute the backedge-taken count. 628 ExitLimit computeLoadConstantCompareExitLimit(LoadInst *LI, 629 Constant *RHS, 630 const Loop *L, 631 ICmpInst::Predicate p); 632 633 /// Compute the exit limit of a loop that is controlled by a 634 /// "(IV >> 1) != 0" type comparison. We cannot compute the exact trip 635 /// count in these cases (since SCEV has no way of expressing them), but we 636 /// can still sometimes compute an upper bound. 637 /// 638 /// Return an ExitLimit for a loop whose backedge is guarded by `LHS Pred 639 /// RHS`. 640 ExitLimit computeShiftCompareExitLimit(Value *LHS, Value *RHS, 641 const Loop *L, 642 ICmpInst::Predicate Pred); 643 644 /// If the loop is known to execute a constant number of times (the 645 /// condition evolves only from constants), try to evaluate a few iterations 646 /// of the loop until we get the exit condition gets a value of ExitWhen 647 /// (true or false). If we cannot evaluate the exit count of the loop, 648 /// return CouldNotCompute. 649 const SCEV *computeExitCountExhaustively(const Loop *L, 650 Value *Cond, 651 bool ExitWhen); 652 653 /// Return the number of times an exit condition comparing the specified 654 /// value to zero will execute. If not computable, return CouldNotCompute. 655 ExitLimit HowFarToZero(const SCEV *V, const Loop *L, bool IsSubExpr); 656 657 /// Return the number of times an exit condition checking the specified 658 /// value for nonzero will execute. If not computable, return 659 /// CouldNotCompute. 660 ExitLimit HowFarToNonZero(const SCEV *V, const Loop *L); 661 662 /// Return the number of times an exit condition containing the specified 663 /// less-than comparison will execute. If not computable, return 664 /// CouldNotCompute. isSigned specifies whether the less-than is signed. 665 ExitLimit HowManyLessThans(const SCEV *LHS, const SCEV *RHS, 666 const Loop *L, bool isSigned, bool IsSubExpr); 667 ExitLimit HowManyGreaterThans(const SCEV *LHS, const SCEV *RHS, 668 const Loop *L, bool isSigned, bool IsSubExpr); 669 670 /// Return a predecessor of BB (which may not be an immediate predecessor) 671 /// which has exactly one successor from which BB is reachable, or null if 672 /// no such block is found. 673 std::pair<BasicBlock *, BasicBlock *> 674 getPredecessorWithUniqueSuccessorForBB(BasicBlock *BB); 675 676 /// Test whether the condition described by Pred, LHS, and RHS is true 677 /// whenever the given FoundCondValue value evaluates to true. 678 bool isImpliedCond(ICmpInst::Predicate Pred, 679 const SCEV *LHS, const SCEV *RHS, 680 Value *FoundCondValue, 681 bool Inverse); 682 683 /// Test whether the condition described by Pred, LHS, and RHS is true 684 /// whenever the condition described by FoundPred, FoundLHS, FoundRHS is 685 /// true. 686 bool isImpliedCond(ICmpInst::Predicate Pred, const SCEV *LHS, 687 const SCEV *RHS, ICmpInst::Predicate FoundPred, 688 const SCEV *FoundLHS, const SCEV *FoundRHS); 689 690 /// Test whether the condition described by Pred, LHS, and RHS is true 691 /// whenever the condition described by Pred, FoundLHS, and FoundRHS is 692 /// true. 693 bool isImpliedCondOperands(ICmpInst::Predicate Pred, 694 const SCEV *LHS, const SCEV *RHS, 695 const SCEV *FoundLHS, const SCEV *FoundRHS); 696 697 /// Test whether the condition described by Pred, LHS, and RHS is true 698 /// whenever the condition described by Pred, FoundLHS, and FoundRHS is 699 /// true. 700 bool isImpliedCondOperandsHelper(ICmpInst::Predicate Pred, 701 const SCEV *LHS, const SCEV *RHS, 702 const SCEV *FoundLHS, 703 const SCEV *FoundRHS); 704 705 /// Test whether the condition described by Pred, LHS, and RHS is true 706 /// whenever the condition described by Pred, FoundLHS, and FoundRHS is 707 /// true. Utility function used by isImpliedCondOperands. 708 bool isImpliedCondOperandsViaRanges(ICmpInst::Predicate Pred, 709 const SCEV *LHS, const SCEV *RHS, 710 const SCEV *FoundLHS, 711 const SCEV *FoundRHS); 712 713 /// Test whether the condition described by Pred, LHS, and RHS is true 714 /// whenever the condition described by Pred, FoundLHS, and FoundRHS is 715 /// true. 716 /// 717 /// This routine tries to rule out certain kinds of integer overflow, and 718 /// then tries to reason about arithmetic properties of the predicates. 719 bool isImpliedCondOperandsViaNoOverflow(ICmpInst::Predicate Pred, 720 const SCEV *LHS, const SCEV *RHS, 721 const SCEV *FoundLHS, 722 const SCEV *FoundRHS); 723 724 /// If we know that the specified Phi is in the header of its containing 725 /// loop, we know the loop executes a constant number of times, and the PHI 726 /// node is just a recurrence involving constants, fold it. 727 Constant *getConstantEvolutionLoopExitValue(PHINode *PN, const APInt& BEs, 728 const Loop *L); 729 730 /// Test if the given expression is known to satisfy the condition described 731 /// by Pred and the known constant ranges of LHS and RHS. 732 /// 733 bool isKnownPredicateWithRanges(ICmpInst::Predicate Pred, 734 const SCEV *LHS, const SCEV *RHS); 735 736 /// Try to prove the condition described by "LHS Pred RHS" by ruling out 737 /// integer overflow. 738 /// 739 /// For instance, this will return true for "A s< (A + C)<nsw>" if C is 740 /// positive. 741 bool isKnownPredicateViaNoOverflow(ICmpInst::Predicate Pred, 742 const SCEV *LHS, const SCEV *RHS); 743 744 /// Try to split Pred LHS RHS into logical conjunctions (and's) and try to 745 /// prove them individually. 746 bool isKnownPredicateViaSplitting(ICmpInst::Predicate Pred, const SCEV *LHS, 747 const SCEV *RHS); 748 749 /// Try to match the Expr as "(L + R)<Flags>". 750 bool splitBinaryAdd(const SCEV *Expr, const SCEV *&L, const SCEV *&R, 751 SCEV::NoWrapFlags &Flags); 752 753 /// Return true if More == (Less + C), where C is a constant. This is 754 /// intended to be used as a cheaper substitute for full SCEV subtraction. 755 bool computeConstantDifference(const SCEV *Less, const SCEV *More, 756 APInt &C); 757 758 /// Drop memoized information computed for S. 759 void forgetMemoizedResults(const SCEV *S); 760 761 /// Return an existing SCEV for V if there is one, otherwise return nullptr. 762 const SCEV *getExistingSCEV(Value *V); 763 764 /// Return false iff given SCEV contains a SCEVUnknown with NULL value- 765 /// pointer. 766 bool checkValidity(const SCEV *S) const; 767 768 /// Return true if `ExtendOpTy`({`Start`,+,`Step`}) can be proved to be 769 /// equal to {`ExtendOpTy`(`Start`),+,`ExtendOpTy`(`Step`)}. This is 770 /// equivalent to proving no signed (resp. unsigned) wrap in 771 /// {`Start`,+,`Step`} if `ExtendOpTy` is `SCEVSignExtendExpr` 772 /// (resp. `SCEVZeroExtendExpr`). 773 /// 774 template<typename ExtendOpTy> 775 bool proveNoWrapByVaryingStart(const SCEV *Start, const SCEV *Step, 776 const Loop *L); 777 778 bool isMonotonicPredicateImpl(const SCEVAddRecExpr *LHS, 779 ICmpInst::Predicate Pred, bool &Increasing); 780 781 /// Return true if, for all loop invariant X, the predicate "LHS `Pred` X" 782 /// is monotonically increasing or decreasing. In the former case set 783 /// `Increasing` to true and in the latter case set `Increasing` to false. 784 /// 785 /// A predicate is said to be monotonically increasing if may go from being 786 /// false to being true as the loop iterates, but never the other way 787 /// around. A predicate is said to be monotonically decreasing if may go 788 /// from being true to being false as the loop iterates, but never the other 789 /// way around. 790 bool isMonotonicPredicate(const SCEVAddRecExpr *LHS, 791 ICmpInst::Predicate Pred, bool &Increasing); 792 793 // Return SCEV no-wrap flags that can be proven based on reasoning 794 // about how poison produced from no-wrap flags on this value 795 // (e.g. a nuw add) would trigger undefined behavior on overflow. 796 SCEV::NoWrapFlags getNoWrapFlagsFromUB(const Value *V); 797 798 public: 799 ScalarEvolution(Function &F, TargetLibraryInfo &TLI, AssumptionCache &AC, 800 DominatorTree &DT, LoopInfo &LI); 801 ~ScalarEvolution(); 802 ScalarEvolution(ScalarEvolution &&Arg); 803 804 LLVMContext &getContext() const { return F.getContext(); } 805 806 /// Test if values of the given type are analyzable within the SCEV 807 /// framework. This primarily includes integer types, and it can optionally 808 /// include pointer types if the ScalarEvolution class has access to 809 /// target-specific information. 810 bool isSCEVable(Type *Ty) const; 811 812 /// Return the size in bits of the specified type, for which isSCEVable must 813 /// return true. 814 uint64_t getTypeSizeInBits(Type *Ty) const; 815 816 /// Return a type with the same bitwidth as the given type and which 817 /// represents how SCEV will treat the given type, for which isSCEVable must 818 /// return true. For pointer types, this is the pointer-sized integer type. 819 Type *getEffectiveSCEVType(Type *Ty) const; 820 821 /// Return a SCEV expression for the full generality of the specified 822 /// expression. 823 const SCEV *getSCEV(Value *V); 824 825 const SCEV *getConstant(ConstantInt *V); 826 const SCEV *getConstant(const APInt& Val); 827 const SCEV *getConstant(Type *Ty, uint64_t V, bool isSigned = false); 828 const SCEV *getTruncateExpr(const SCEV *Op, Type *Ty); 829 const SCEV *getZeroExtendExpr(const SCEV *Op, Type *Ty); 830 const SCEV *getSignExtendExpr(const SCEV *Op, Type *Ty); 831 const SCEV *getAnyExtendExpr(const SCEV *Op, Type *Ty); 832 const SCEV *getAddExpr(SmallVectorImpl<const SCEV *> &Ops, 833 SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap); 834 const SCEV *getAddExpr(const SCEV *LHS, const SCEV *RHS, 835 SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap) { 836 SmallVector<const SCEV *, 2> Ops = {LHS, RHS}; 837 return getAddExpr(Ops, Flags); 838 } 839 const SCEV *getAddExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2, 840 SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap) { 841 SmallVector<const SCEV *, 3> Ops = {Op0, Op1, Op2}; 842 return getAddExpr(Ops, Flags); 843 } 844 const SCEV *getMulExpr(SmallVectorImpl<const SCEV *> &Ops, 845 SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap); 846 const SCEV *getMulExpr(const SCEV *LHS, const SCEV *RHS, 847 SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap) { 848 SmallVector<const SCEV *, 2> Ops = {LHS, RHS}; 849 return getMulExpr(Ops, Flags); 850 } 851 const SCEV *getMulExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2, 852 SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap) { 853 SmallVector<const SCEV *, 3> Ops = {Op0, Op1, Op2}; 854 return getMulExpr(Ops, Flags); 855 } 856 const SCEV *getUDivExpr(const SCEV *LHS, const SCEV *RHS); 857 const SCEV *getUDivExactExpr(const SCEV *LHS, const SCEV *RHS); 858 const SCEV *getAddRecExpr(const SCEV *Start, const SCEV *Step, 859 const Loop *L, SCEV::NoWrapFlags Flags); 860 const SCEV *getAddRecExpr(SmallVectorImpl<const SCEV *> &Operands, 861 const Loop *L, SCEV::NoWrapFlags Flags); 862 const SCEV *getAddRecExpr(const SmallVectorImpl<const SCEV *> &Operands, 863 const Loop *L, SCEV::NoWrapFlags Flags) { 864 SmallVector<const SCEV *, 4> NewOp(Operands.begin(), Operands.end()); 865 return getAddRecExpr(NewOp, L, Flags); 866 } 867 /// \brief Returns an expression for a GEP 868 /// 869 /// \p PointeeType The type used as the basis for the pointer arithmetics 870 /// \p BaseExpr The expression for the pointer operand. 871 /// \p IndexExprs The expressions for the indices. 872 /// \p InBounds Whether the GEP is in bounds. 873 const SCEV *getGEPExpr(Type *PointeeType, const SCEV *BaseExpr, 874 const SmallVectorImpl<const SCEV *> &IndexExprs, 875 bool InBounds = false); 876 const SCEV *getSMaxExpr(const SCEV *LHS, const SCEV *RHS); 877 const SCEV *getSMaxExpr(SmallVectorImpl<const SCEV *> &Operands); 878 const SCEV *getUMaxExpr(const SCEV *LHS, const SCEV *RHS); 879 const SCEV *getUMaxExpr(SmallVectorImpl<const SCEV *> &Operands); 880 const SCEV *getSMinExpr(const SCEV *LHS, const SCEV *RHS); 881 const SCEV *getUMinExpr(const SCEV *LHS, const SCEV *RHS); 882 const SCEV *getUnknown(Value *V); 883 const SCEV *getCouldNotCompute(); 884 885 /// \brief Return a SCEV for the constant 0 of a specific type. 886 const SCEV *getZero(Type *Ty) { return getConstant(Ty, 0); } 887 888 /// \brief Return a SCEV for the constant 1 of a specific type. 889 const SCEV *getOne(Type *Ty) { return getConstant(Ty, 1); } 890 891 /// Return an expression for sizeof AllocTy that is type IntTy 892 /// 893 const SCEV *getSizeOfExpr(Type *IntTy, Type *AllocTy); 894 895 /// Return an expression for offsetof on the given field with type IntTy 896 /// 897 const SCEV *getOffsetOfExpr(Type *IntTy, StructType *STy, unsigned FieldNo); 898 899 /// Return the SCEV object corresponding to -V. 900 /// 901 const SCEV *getNegativeSCEV(const SCEV *V, 902 SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap); 903 904 /// Return the SCEV object corresponding to ~V. 905 /// 906 const SCEV *getNotSCEV(const SCEV *V); 907 908 /// Return LHS-RHS. Minus is represented in SCEV as A+B*-1. 909 const SCEV *getMinusSCEV(const SCEV *LHS, const SCEV *RHS, 910 SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap); 911 912 /// Return a SCEV corresponding to a conversion of the input value to the 913 /// specified type. If the type must be extended, it is zero extended. 914 const SCEV *getTruncateOrZeroExtend(const SCEV *V, Type *Ty); 915 916 /// Return a SCEV corresponding to a conversion of the input value to the 917 /// specified type. If the type must be extended, it is sign extended. 918 const SCEV *getTruncateOrSignExtend(const SCEV *V, Type *Ty); 919 920 /// Return a SCEV corresponding to a conversion of the input value to the 921 /// specified type. If the type must be extended, it is zero extended. The 922 /// conversion must not be narrowing. 923 const SCEV *getNoopOrZeroExtend(const SCEV *V, Type *Ty); 924 925 /// Return a SCEV corresponding to a conversion of the input value to the 926 /// specified type. If the type must be extended, it is sign extended. The 927 /// conversion must not be narrowing. 928 const SCEV *getNoopOrSignExtend(const SCEV *V, Type *Ty); 929 930 /// Return a SCEV corresponding to a conversion of the input value to the 931 /// specified type. If the type must be extended, it is extended with 932 /// unspecified bits. The conversion must not be narrowing. 933 const SCEV *getNoopOrAnyExtend(const SCEV *V, Type *Ty); 934 935 /// Return a SCEV corresponding to a conversion of the input value to the 936 /// specified type. The conversion must not be widening. 937 const SCEV *getTruncateOrNoop(const SCEV *V, Type *Ty); 938 939 /// Promote the operands to the wider of the types using zero-extension, and 940 /// then perform a umax operation with them. 941 const SCEV *getUMaxFromMismatchedTypes(const SCEV *LHS, 942 const SCEV *RHS); 943 944 /// Promote the operands to the wider of the types using zero-extension, and 945 /// then perform a umin operation with them. 946 const SCEV *getUMinFromMismatchedTypes(const SCEV *LHS, 947 const SCEV *RHS); 948 949 /// Transitively follow the chain of pointer-type operands until reaching a 950 /// SCEV that does not have a single pointer operand. This returns a 951 /// SCEVUnknown pointer for well-formed pointer-type expressions, but corner 952 /// cases do exist. 953 const SCEV *getPointerBase(const SCEV *V); 954 955 /// Return a SCEV expression for the specified value at the specified scope 956 /// in the program. The L value specifies a loop nest to evaluate the 957 /// expression at, where null is the top-level or a specified loop is 958 /// immediately inside of the loop. 959 /// 960 /// This method can be used to compute the exit value for a variable defined 961 /// in a loop by querying what the value will hold in the parent loop. 962 /// 963 /// In the case that a relevant loop exit value cannot be computed, the 964 /// original value V is returned. 965 const SCEV *getSCEVAtScope(const SCEV *S, const Loop *L); 966 967 /// This is a convenience function which does getSCEVAtScope(getSCEV(V), L). 968 const SCEV *getSCEVAtScope(Value *V, const Loop *L); 969 970 /// Test whether entry to the loop is protected by a conditional between LHS 971 /// and RHS. This is used to help avoid max expressions in loop trip 972 /// counts, and to eliminate casts. 973 bool isLoopEntryGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, 974 const SCEV *LHS, const SCEV *RHS); 975 976 /// Test whether the backedge of the loop is protected by a conditional 977 /// between LHS and RHS. This is used to to eliminate casts. 978 bool isLoopBackedgeGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, 979 const SCEV *LHS, const SCEV *RHS); 980 981 /// \brief Returns the maximum trip count of the loop if it is a single-exit 982 /// loop and we can compute a small maximum for that loop. 983 /// 984 /// Implemented in terms of the \c getSmallConstantTripCount overload with 985 /// the single exiting block passed to it. See that routine for details. 986 unsigned getSmallConstantTripCount(Loop *L); 987 988 /// Returns the maximum trip count of this loop as a normal unsigned 989 /// value. Returns 0 if the trip count is unknown or not constant. This 990 /// "trip count" assumes that control exits via ExitingBlock. More 991 /// precisely, it is the number of times that control may reach ExitingBlock 992 /// before taking the branch. For loops with multiple exits, it may not be 993 /// the number times that the loop header executes if the loop exits 994 /// prematurely via another branch. 995 unsigned getSmallConstantTripCount(Loop *L, BasicBlock *ExitingBlock); 996 997 /// \brief Returns the largest constant divisor of the trip count of the 998 /// loop if it is a single-exit loop and we can compute a small maximum for 999 /// that loop. 1000 /// 1001 /// Implemented in terms of the \c getSmallConstantTripMultiple overload with 1002 /// the single exiting block passed to it. See that routine for details. 1003 unsigned getSmallConstantTripMultiple(Loop *L); 1004 1005 /// Returns the largest constant divisor of the trip count of this loop as a 1006 /// normal unsigned value, if possible. This means that the actual trip 1007 /// count is always a multiple of the returned value (don't forget the trip 1008 /// count could very well be zero as well!). As explained in the comments 1009 /// for getSmallConstantTripCount, this assumes that control exits the loop 1010 /// via ExitingBlock. 1011 unsigned getSmallConstantTripMultiple(Loop *L, BasicBlock *ExitingBlock); 1012 1013 /// Get the expression for the number of loop iterations for which this loop 1014 /// is guaranteed not to exit via ExitingBlock. Otherwise return 1015 /// SCEVCouldNotCompute. 1016 const SCEV *getExitCount(Loop *L, BasicBlock *ExitingBlock); 1017 1018 /// If the specified loop has a predictable backedge-taken count, return it, 1019 /// otherwise return a SCEVCouldNotCompute object. The backedge-taken count 1020 /// is the number of times the loop header will be branched to from within 1021 /// the loop. This is one less than the trip count of the loop, since it 1022 /// doesn't count the first iteration, when the header is branched to from 1023 /// outside the loop. 1024 /// 1025 /// Note that it is not valid to call this method on a loop without a 1026 /// loop-invariant backedge-taken count (see 1027 /// hasLoopInvariantBackedgeTakenCount). 1028 /// 1029 const SCEV *getBackedgeTakenCount(const Loop *L); 1030 1031 /// Similar to getBackedgeTakenCount, except return the least SCEV value 1032 /// that is known never to be less than the actual backedge taken count. 1033 const SCEV *getMaxBackedgeTakenCount(const Loop *L); 1034 1035 /// Return true if the specified loop has an analyzable loop-invariant 1036 /// backedge-taken count. 1037 bool hasLoopInvariantBackedgeTakenCount(const Loop *L); 1038 1039 /// This method should be called by the client when it has changed a loop in 1040 /// a way that may effect ScalarEvolution's ability to compute a trip count, 1041 /// or if the loop is deleted. This call is potentially expensive for large 1042 /// loop bodies. 1043 void forgetLoop(const Loop *L); 1044 1045 /// This method should be called by the client when it has changed a value 1046 /// in a way that may effect its value, or which may disconnect it from a 1047 /// def-use chain linking it to a loop. 1048 void forgetValue(Value *V); 1049 1050 /// \brief Called when the client has changed the disposition of values in 1051 /// this loop. 1052 /// 1053 /// We don't have a way to invalidate per-loop dispositions. Clear and 1054 /// recompute is simpler. 1055 void forgetLoopDispositions(const Loop *L) { LoopDispositions.clear(); } 1056 1057 /// Determine the minimum number of zero bits that S is guaranteed to end in 1058 /// (at every loop iteration). It is, at the same time, the minimum number 1059 /// of times S is divisible by 2. For example, given {4,+,8} it returns 2. 1060 /// If S is guaranteed to be 0, it returns the bitwidth of S. 1061 uint32_t GetMinTrailingZeros(const SCEV *S); 1062 1063 /// Determine the unsigned range for a particular SCEV. 1064 /// 1065 ConstantRange getUnsignedRange(const SCEV *S) { 1066 return getRange(S, HINT_RANGE_UNSIGNED); 1067 } 1068 1069 /// Determine the signed range for a particular SCEV. 1070 /// 1071 ConstantRange getSignedRange(const SCEV *S) { 1072 return getRange(S, HINT_RANGE_SIGNED); 1073 } 1074 1075 /// Test if the given expression is known to be negative. 1076 /// 1077 bool isKnownNegative(const SCEV *S); 1078 1079 /// Test if the given expression is known to be positive. 1080 /// 1081 bool isKnownPositive(const SCEV *S); 1082 1083 /// Test if the given expression is known to be non-negative. 1084 /// 1085 bool isKnownNonNegative(const SCEV *S); 1086 1087 /// Test if the given expression is known to be non-positive. 1088 /// 1089 bool isKnownNonPositive(const SCEV *S); 1090 1091 /// Test if the given expression is known to be non-zero. 1092 /// 1093 bool isKnownNonZero(const SCEV *S); 1094 1095 /// Test if the given expression is known to satisfy the condition described 1096 /// by Pred, LHS, and RHS. 1097 /// 1098 bool isKnownPredicate(ICmpInst::Predicate Pred, 1099 const SCEV *LHS, const SCEV *RHS); 1100 1101 /// Return true if the result of the predicate LHS `Pred` RHS is loop 1102 /// invariant with respect to L. Set InvariantPred, InvariantLHS and 1103 /// InvariantLHS so that InvariantLHS `InvariantPred` InvariantRHS is the 1104 /// loop invariant form of LHS `Pred` RHS. 1105 bool isLoopInvariantPredicate(ICmpInst::Predicate Pred, const SCEV *LHS, 1106 const SCEV *RHS, const Loop *L, 1107 ICmpInst::Predicate &InvariantPred, 1108 const SCEV *&InvariantLHS, 1109 const SCEV *&InvariantRHS); 1110 1111 /// Simplify LHS and RHS in a comparison with predicate Pred. Return true 1112 /// iff any changes were made. If the operands are provably equal or 1113 /// unequal, LHS and RHS are set to the same value and Pred is set to either 1114 /// ICMP_EQ or ICMP_NE. 1115 /// 1116 bool SimplifyICmpOperands(ICmpInst::Predicate &Pred, 1117 const SCEV *&LHS, 1118 const SCEV *&RHS, 1119 unsigned Depth = 0); 1120 1121 /// Return the "disposition" of the given SCEV with respect to the given 1122 /// loop. 1123 LoopDisposition getLoopDisposition(const SCEV *S, const Loop *L); 1124 1125 /// Return true if the value of the given SCEV is unchanging in the 1126 /// specified loop. 1127 bool isLoopInvariant(const SCEV *S, const Loop *L); 1128 1129 /// Return true if the given SCEV changes value in a known way in the 1130 /// specified loop. This property being true implies that the value is 1131 /// variant in the loop AND that we can emit an expression to compute the 1132 /// value of the expression at any particular loop iteration. 1133 bool hasComputableLoopEvolution(const SCEV *S, const Loop *L); 1134 1135 /// Return the "disposition" of the given SCEV with respect to the given 1136 /// block. 1137 BlockDisposition getBlockDisposition(const SCEV *S, const BasicBlock *BB); 1138 1139 /// Return true if elements that makes up the given SCEV dominate the 1140 /// specified basic block. 1141 bool dominates(const SCEV *S, const BasicBlock *BB); 1142 1143 /// Return true if elements that makes up the given SCEV properly dominate 1144 /// the specified basic block. 1145 bool properlyDominates(const SCEV *S, const BasicBlock *BB); 1146 1147 /// Test whether the given SCEV has Op as a direct or indirect operand. 1148 bool hasOperand(const SCEV *S, const SCEV *Op) const; 1149 1150 /// Return the size of an element read or written by Inst. 1151 const SCEV *getElementSize(Instruction *Inst); 1152 1153 /// Compute the array dimensions Sizes from the set of Terms extracted from 1154 /// the memory access function of this SCEVAddRecExpr. 1155 void findArrayDimensions(SmallVectorImpl<const SCEV *> &Terms, 1156 SmallVectorImpl<const SCEV *> &Sizes, 1157 const SCEV *ElementSize) const; 1158 1159 void print(raw_ostream &OS) const; 1160 void verify() const; 1161 1162 /// Collect parametric terms occurring in step expressions. 1163 void collectParametricTerms(const SCEV *Expr, 1164 SmallVectorImpl<const SCEV *> &Terms); 1165 1166 1167 1168 /// Return in Subscripts the access functions for each dimension in Sizes. 1169 void computeAccessFunctions(const SCEV *Expr, 1170 SmallVectorImpl<const SCEV *> &Subscripts, 1171 SmallVectorImpl<const SCEV *> &Sizes); 1172 1173 /// Split this SCEVAddRecExpr into two vectors of SCEVs representing the 1174 /// subscripts and sizes of an array access. 1175 /// 1176 /// The delinearization is a 3 step process: the first two steps compute the 1177 /// sizes of each subscript and the third step computes the access functions 1178 /// for the delinearized array: 1179 /// 1180 /// 1. Find the terms in the step functions 1181 /// 2. Compute the array size 1182 /// 3. Compute the access function: divide the SCEV by the array size 1183 /// starting with the innermost dimensions found in step 2. The Quotient 1184 /// is the SCEV to be divided in the next step of the recursion. The 1185 /// Remainder is the subscript of the innermost dimension. Loop over all 1186 /// array dimensions computed in step 2. 1187 /// 1188 /// To compute a uniform array size for several memory accesses to the same 1189 /// object, one can collect in step 1 all the step terms for all the memory 1190 /// accesses, and compute in step 2 a unique array shape. This guarantees 1191 /// that the array shape will be the same across all memory accesses. 1192 /// 1193 /// FIXME: We could derive the result of steps 1 and 2 from a description of 1194 /// the array shape given in metadata. 1195 /// 1196 /// Example: 1197 /// 1198 /// A[][n][m] 1199 /// 1200 /// for i 1201 /// for j 1202 /// for k 1203 /// A[j+k][2i][5i] = 1204 /// 1205 /// The initial SCEV: 1206 /// 1207 /// A[{{{0,+,2*m+5}_i, +, n*m}_j, +, n*m}_k] 1208 /// 1209 /// 1. Find the different terms in the step functions: 1210 /// -> [2*m, 5, n*m, n*m] 1211 /// 1212 /// 2. Compute the array size: sort and unique them 1213 /// -> [n*m, 2*m, 5] 1214 /// find the GCD of all the terms = 1 1215 /// divide by the GCD and erase constant terms 1216 /// -> [n*m, 2*m] 1217 /// GCD = m 1218 /// divide by GCD -> [n, 2] 1219 /// remove constant terms 1220 /// -> [n] 1221 /// size of the array is A[unknown][n][m] 1222 /// 1223 /// 3. Compute the access function 1224 /// a. Divide {{{0,+,2*m+5}_i, +, n*m}_j, +, n*m}_k by the innermost size m 1225 /// Quotient: {{{0,+,2}_i, +, n}_j, +, n}_k 1226 /// Remainder: {{{0,+,5}_i, +, 0}_j, +, 0}_k 1227 /// The remainder is the subscript of the innermost array dimension: [5i]. 1228 /// 1229 /// b. Divide Quotient: {{{0,+,2}_i, +, n}_j, +, n}_k by next outer size n 1230 /// Quotient: {{{0,+,0}_i, +, 1}_j, +, 1}_k 1231 /// Remainder: {{{0,+,2}_i, +, 0}_j, +, 0}_k 1232 /// The Remainder is the subscript of the next array dimension: [2i]. 1233 /// 1234 /// The subscript of the outermost dimension is the Quotient: [j+k]. 1235 /// 1236 /// Overall, we have: A[][n][m], and the access function: A[j+k][2i][5i]. 1237 void delinearize(const SCEV *Expr, 1238 SmallVectorImpl<const SCEV *> &Subscripts, 1239 SmallVectorImpl<const SCEV *> &Sizes, 1240 const SCEV *ElementSize); 1241 1242 /// Return the DataLayout associated with the module this SCEV instance is 1243 /// operating on. 1244 const DataLayout &getDataLayout() const { 1245 return F.getParent()->getDataLayout(); 1246 } 1247 1248 const SCEVPredicate *getEqualPredicate(const SCEVUnknown *LHS, 1249 const SCEVConstant *RHS); 1250 1251 /// Re-writes the SCEV according to the Predicates in \p Preds. 1252 const SCEV *rewriteUsingPredicate(const SCEV *Scev, SCEVUnionPredicate &A); 1253 1254 private: 1255 /// Compute the backedge taken count knowing the interval difference, the 1256 /// stride and presence of the equality in the comparison. 1257 const SCEV *computeBECount(const SCEV *Delta, const SCEV *Stride, 1258 bool Equality); 1259 1260 /// Verify if an linear IV with positive stride can overflow when in a 1261 /// less-than comparison, knowing the invariant term of the comparison, 1262 /// the stride and the knowledge of NSW/NUW flags on the recurrence. 1263 bool doesIVOverflowOnLT(const SCEV *RHS, const SCEV *Stride, 1264 bool IsSigned, bool NoWrap); 1265 1266 /// Verify if an linear IV with negative stride can overflow when in a 1267 /// greater-than comparison, knowing the invariant term of the comparison, 1268 /// the stride and the knowledge of NSW/NUW flags on the recurrence. 1269 bool doesIVOverflowOnGT(const SCEV *RHS, const SCEV *Stride, 1270 bool IsSigned, bool NoWrap); 1271 1272 private: 1273 FoldingSet<SCEV> UniqueSCEVs; 1274 FoldingSet<SCEVPredicate> UniquePreds; 1275 BumpPtrAllocator SCEVAllocator; 1276 1277 /// The head of a linked list of all SCEVUnknown values that have been 1278 /// allocated. This is used by releaseMemory to locate them all and call 1279 /// their destructors. 1280 SCEVUnknown *FirstUnknown; 1281 }; 1282 1283 /// \brief Analysis pass that exposes the \c ScalarEvolution for a function. 1284 class ScalarEvolutionAnalysis { 1285 static char PassID; 1286 1287 public: 1288 typedef ScalarEvolution Result; 1289 1290 /// \brief Opaque, unique identifier for this analysis pass. 1291 static void *ID() { return (void *)&PassID; } 1292 1293 /// \brief Provide a name for the analysis for debugging and logging. 1294 static StringRef name() { return "ScalarEvolutionAnalysis"; } 1295 1296 ScalarEvolution run(Function &F, AnalysisManager<Function> *AM); 1297 }; 1298 1299 /// \brief Printer pass for the \c ScalarEvolutionAnalysis results. 1300 class ScalarEvolutionPrinterPass { 1301 raw_ostream &OS; 1302 1303 public: 1304 explicit ScalarEvolutionPrinterPass(raw_ostream &OS) : OS(OS) {} 1305 PreservedAnalyses run(Function &F, AnalysisManager<Function> *AM); 1306 1307 static StringRef name() { return "ScalarEvolutionPrinterPass"; } 1308 }; 1309 1310 class ScalarEvolutionWrapperPass : public FunctionPass { 1311 std::unique_ptr<ScalarEvolution> SE; 1312 1313 public: 1314 static char ID; 1315 1316 ScalarEvolutionWrapperPass(); 1317 1318 ScalarEvolution &getSE() { return *SE; } 1319 const ScalarEvolution &getSE() const { return *SE; } 1320 1321 bool runOnFunction(Function &F) override; 1322 void releaseMemory() override; 1323 void getAnalysisUsage(AnalysisUsage &AU) const override; 1324 void print(raw_ostream &OS, const Module * = nullptr) const override; 1325 void verifyAnalysis() const override; 1326 }; 1327 1328 /// An interface layer with SCEV used to manage how we see SCEV expressions 1329 /// for values in the context of existing predicates. We can add new 1330 /// predicates, but we cannot remove them. 1331 /// 1332 /// This layer has multiple purposes: 1333 /// - provides a simple interface for SCEV versioning. 1334 /// - guarantees that the order of transformations applied on a SCEV 1335 /// expression for a single Value is consistent across two different 1336 /// getSCEV calls. This means that, for example, once we've obtained 1337 /// an AddRec expression for a certain value through expression 1338 /// rewriting, we will continue to get an AddRec expression for that 1339 /// Value. 1340 /// - lowers the number of expression rewrites. 1341 class PredicatedScalarEvolution { 1342 public: 1343 PredicatedScalarEvolution(ScalarEvolution &SE); 1344 const SCEVUnionPredicate &getUnionPredicate() const; 1345 /// \brief Returns the SCEV expression of V, in the context of the current 1346 /// SCEV predicate. 1347 /// The order of transformations applied on the expression of V returned 1348 /// by ScalarEvolution is guaranteed to be preserved, even when adding new 1349 /// predicates. 1350 const SCEV *getSCEV(Value *V); 1351 /// \brief Adds a new predicate. 1352 void addPredicate(const SCEVPredicate &Pred); 1353 /// \brief Returns the ScalarEvolution analysis used. 1354 ScalarEvolution *getSE() const { return &SE; } 1355 1356 private: 1357 /// \brief Increments the version number of the predicate. 1358 /// This needs to be called every time the SCEV predicate changes. 1359 void updateGeneration(); 1360 /// Holds a SCEV and the version number of the SCEV predicate used to 1361 /// perform the rewrite of the expression. 1362 typedef std::pair<unsigned, const SCEV *> RewriteEntry; 1363 /// Maps a SCEV to the rewrite result of that SCEV at a certain version 1364 /// number. If this number doesn't match the current Generation, we will 1365 /// need to do a rewrite. To preserve the transformation order of previous 1366 /// rewrites, we will rewrite the previous result instead of the original 1367 /// SCEV. 1368 DenseMap<const SCEV *, RewriteEntry> RewriteMap; 1369 /// The ScalarEvolution analysis. 1370 ScalarEvolution &SE; 1371 /// The SCEVPredicate that forms our context. We will rewrite all 1372 /// expressions assuming that this predicate true. 1373 SCEVUnionPredicate Preds; 1374 /// Marks the version of the SCEV predicate used. When rewriting a SCEV 1375 /// expression we mark it with the version of the predicate. We use this to 1376 /// figure out if the predicate has changed from the last rewrite of the 1377 /// SCEV. If so, we need to perform a new rewrite. 1378 unsigned Generation; 1379 }; 1380 } 1381 1382 #endif 1383
