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/ADT/SetVector.h" 27 #include "llvm/Analysis/LoopInfo.h" 28 #include "llvm/IR/ConstantRange.h" 29 #include "llvm/IR/Instructions.h" 30 #include "llvm/IR/Operator.h" 31 #include "llvm/IR/PassManager.h" 32 #include "llvm/IR/ValueHandle.h" 33 #include "llvm/IR/ValueMap.h" 34 #include "llvm/Pass.h" 35 #include "llvm/Support/Allocator.h" 36 #include "llvm/Support/DataTypes.h" 37 38 namespace llvm { 39 class APInt; 40 class AssumptionCache; 41 class Constant; 42 class ConstantInt; 43 class DominatorTree; 44 class Type; 45 class ScalarEvolution; 46 class DataLayout; 47 class TargetLibraryInfo; 48 class LLVMContext; 49 class Operator; 50 class SCEV; 51 class SCEVAddRecExpr; 52 class SCEVConstant; 53 class SCEVExpander; 54 class SCEVPredicate; 55 class SCEVUnknown; 56 class Function; 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 { 103 FlagAnyWrap = 0, // No guarantee. 104 FlagNW = (1 << 0), // No self-wrap. 105 FlagNUW = (1 << 1), // No unsigned wrap. 106 FlagNSW = (1 << 2), // No signed wrap. 107 NoWrapMask = (1 << 3) - 1 108 }; 109 110 explicit SCEV(const FoldingSetNodeIDRef ID, unsigned SCEVTy) 111 : FastID(ID), SCEVType(SCEVTy), SubclassData(0) {} 112 113 unsigned getSCEVType() const { return SCEVType; } 114 115 /// Return the LLVM type of this SCEV expression. 116 /// 117 Type *getType() const; 118 119 /// Return true if the expression is a constant zero. 120 /// 121 bool isZero() const; 122 123 /// Return true if the expression is a constant one. 124 /// 125 bool isOne() const; 126 127 /// Return true if the expression is a constant all-ones value. 128 /// 129 bool isAllOnesValue() const; 130 131 /// Return true if the specified scev is negated, but not a constant. 132 bool isNonConstantNegative() const; 133 134 /// Print out the internal representation of this scalar to the specified 135 /// stream. This should really only be used for debugging purposes. 136 void print(raw_ostream &OS) const; 137 138 /// This method is used for debugging. 139 /// 140 void dump() const; 141 }; 142 143 // Specialize FoldingSetTrait for SCEV to avoid needing to compute 144 // temporary FoldingSetNodeID values. 145 template <> struct FoldingSetTrait<SCEV> : DefaultFoldingSetTrait<SCEV> { 146 static void Profile(const SCEV &X, FoldingSetNodeID &ID) { ID = X.FastID; } 147 static bool Equals(const SCEV &X, const FoldingSetNodeID &ID, unsigned IDHash, 148 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 /// This class represents an assumption made using SCEV expressions which can 173 /// 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, P_Wrap }; 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 /// Returns the estimated complexity of this predicate. This is roughly 196 /// measured in the number of run-time checks required. 197 virtual unsigned getComplexity() const { return 1; } 198 199 /// 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 /// Returns true if this predicate implies \p N. 204 virtual bool implies(const SCEVPredicate *N) const = 0; 205 206 /// Prints a textual representation of this predicate with an indentation of 207 /// \p Depth. 208 virtual void print(raw_ostream &OS, unsigned Depth = 0) const = 0; 209 210 /// Returns the SCEV to which this predicate applies, or nullptr if this is 211 /// 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> : DefaultFoldingSetTrait<SCEVPredicate> { 224 225 static void Profile(const SCEVPredicate &X, FoldingSetNodeID &ID) { 226 ID = X.FastID; 227 } 228 229 static bool Equals(const SCEVPredicate &X, const FoldingSetNodeID &ID, 230 unsigned IDHash, FoldingSetNodeID &TempID) { 231 return ID == X.FastID; 232 } 233 static unsigned ComputeHash(const SCEVPredicate &X, 234 FoldingSetNodeID &TempID) { 235 return X.FastID.ComputeHash(); 236 } 237 }; 238 239 /// This class represents an assumption that two SCEV expressions are equal, 240 /// and this can be checked at run-time. We assume that the left hand side is 241 /// a SCEVUnknown and the right hand side a constant. 242 class SCEVEqualPredicate final : public SCEVPredicate { 243 /// We assume that LHS == RHS, where LHS is a SCEVUnknown and RHS a 244 /// constant. 245 const SCEVUnknown *LHS; 246 const SCEVConstant *RHS; 247 248 public: 249 SCEVEqualPredicate(const FoldingSetNodeIDRef ID, const SCEVUnknown *LHS, 250 const SCEVConstant *RHS); 251 252 /// Implementation of the SCEVPredicate interface 253 bool implies(const SCEVPredicate *N) const override; 254 void print(raw_ostream &OS, unsigned Depth = 0) const override; 255 bool isAlwaysTrue() const override; 256 const SCEV *getExpr() const override; 257 258 /// Returns the left hand side of the equality. 259 const SCEVUnknown *getLHS() const { return LHS; } 260 261 /// Returns the right hand side of the equality. 262 const SCEVConstant *getRHS() const { return RHS; } 263 264 /// Methods for support type inquiry through isa, cast, and dyn_cast: 265 static inline bool classof(const SCEVPredicate *P) { 266 return P->getKind() == P_Equal; 267 } 268 }; 269 270 /// This class represents an assumption made on an AddRec expression. Given an 271 /// affine AddRec expression {a,+,b}, we assume that it has the nssw or nusw 272 /// flags (defined below) in the first X iterations of the loop, where X is a 273 /// SCEV expression returned by getPredicatedBackedgeTakenCount). 274 /// 275 /// Note that this does not imply that X is equal to the backedge taken 276 /// count. This means that if we have a nusw predicate for i32 {0,+,1} with a 277 /// predicated backedge taken count of X, we only guarantee that {0,+,1} has 278 /// nusw in the first X iterations. {0,+,1} may still wrap in the loop if we 279 /// have more than X iterations. 280 class SCEVWrapPredicate final : public SCEVPredicate { 281 public: 282 /// Similar to SCEV::NoWrapFlags, but with slightly different semantics 283 /// for FlagNUSW. The increment is considered to be signed, and a + b 284 /// (where b is the increment) is considered to wrap if: 285 /// zext(a + b) != zext(a) + sext(b) 286 /// 287 /// If Signed is a function that takes an n-bit tuple and maps to the 288 /// integer domain as the tuples value interpreted as twos complement, 289 /// and Unsigned a function that takes an n-bit tuple and maps to the 290 /// integer domain as as the base two value of input tuple, then a + b 291 /// has IncrementNUSW iff: 292 /// 293 /// 0 <= Unsigned(a) + Signed(b) < 2^n 294 /// 295 /// The IncrementNSSW flag has identical semantics with SCEV::FlagNSW. 296 /// 297 /// Note that the IncrementNUSW flag is not commutative: if base + inc 298 /// has IncrementNUSW, then inc + base doesn't neccessarily have this 299 /// property. The reason for this is that this is used for sign/zero 300 /// extending affine AddRec SCEV expressions when a SCEVWrapPredicate is 301 /// assumed. A {base,+,inc} expression is already non-commutative with 302 /// regards to base and inc, since it is interpreted as: 303 /// (((base + inc) + inc) + inc) ... 304 enum IncrementWrapFlags { 305 IncrementAnyWrap = 0, // No guarantee. 306 IncrementNUSW = (1 << 0), // No unsigned with signed increment wrap. 307 IncrementNSSW = (1 << 1), // No signed with signed increment wrap 308 // (equivalent with SCEV::NSW) 309 IncrementNoWrapMask = (1 << 2) - 1 310 }; 311 312 /// Convenient IncrementWrapFlags manipulation methods. 313 LLVM_NODISCARD static SCEVWrapPredicate::IncrementWrapFlags 314 clearFlags(SCEVWrapPredicate::IncrementWrapFlags Flags, 315 SCEVWrapPredicate::IncrementWrapFlags OffFlags) { 316 assert((Flags & IncrementNoWrapMask) == Flags && "Invalid flags value!"); 317 assert((OffFlags & IncrementNoWrapMask) == OffFlags && 318 "Invalid flags value!"); 319 return (SCEVWrapPredicate::IncrementWrapFlags)(Flags & ~OffFlags); 320 } 321 322 LLVM_NODISCARD static SCEVWrapPredicate::IncrementWrapFlags 323 maskFlags(SCEVWrapPredicate::IncrementWrapFlags Flags, int Mask) { 324 assert((Flags & IncrementNoWrapMask) == Flags && "Invalid flags value!"); 325 assert((Mask & IncrementNoWrapMask) == Mask && "Invalid mask value!"); 326 327 return (SCEVWrapPredicate::IncrementWrapFlags)(Flags & Mask); 328 } 329 330 LLVM_NODISCARD static SCEVWrapPredicate::IncrementWrapFlags 331 setFlags(SCEVWrapPredicate::IncrementWrapFlags Flags, 332 SCEVWrapPredicate::IncrementWrapFlags OnFlags) { 333 assert((Flags & IncrementNoWrapMask) == Flags && "Invalid flags value!"); 334 assert((OnFlags & IncrementNoWrapMask) == OnFlags && 335 "Invalid flags value!"); 336 337 return (SCEVWrapPredicate::IncrementWrapFlags)(Flags | OnFlags); 338 } 339 340 /// Returns the set of SCEVWrapPredicate no wrap flags implied by a 341 /// SCEVAddRecExpr. 342 LLVM_NODISCARD static SCEVWrapPredicate::IncrementWrapFlags 343 getImpliedFlags(const SCEVAddRecExpr *AR, ScalarEvolution &SE); 344 345 private: 346 const SCEVAddRecExpr *AR; 347 IncrementWrapFlags Flags; 348 349 public: 350 explicit SCEVWrapPredicate(const FoldingSetNodeIDRef ID, 351 const SCEVAddRecExpr *AR, 352 IncrementWrapFlags Flags); 353 354 /// Returns the set assumed no overflow flags. 355 IncrementWrapFlags getFlags() const { return Flags; } 356 /// Implementation of the SCEVPredicate interface 357 const SCEV *getExpr() const override; 358 bool implies(const SCEVPredicate *N) const override; 359 void print(raw_ostream &OS, unsigned Depth = 0) const override; 360 bool isAlwaysTrue() const override; 361 362 /// Methods for support type inquiry through isa, cast, and dyn_cast: 363 static inline bool classof(const SCEVPredicate *P) { 364 return P->getKind() == P_Wrap; 365 } 366 }; 367 368 /// This class represents a composition of other SCEV predicates, and is the 369 /// class that most clients will interact with. This is equivalent to a 370 /// logical "AND" of all the predicates in the union. 371 /// 372 /// NB! Unlike other SCEVPredicate sub-classes this class does not live in the 373 /// ScalarEvolution::Preds folding set. This is why the \c add function is sound. 374 class SCEVUnionPredicate final : public SCEVPredicate { 375 private: 376 typedef DenseMap<const SCEV *, SmallVector<const SCEVPredicate *, 4>> 377 PredicateMap; 378 379 /// Vector with references to all predicates in this union. 380 SmallVector<const SCEVPredicate *, 16> Preds; 381 /// Maps SCEVs to predicates for quick look-ups. 382 PredicateMap SCEVToPreds; 383 384 public: 385 SCEVUnionPredicate(); 386 387 const SmallVectorImpl<const SCEVPredicate *> &getPredicates() const { 388 return Preds; 389 } 390 391 /// Adds a predicate to this union. 392 void add(const SCEVPredicate *N); 393 394 /// Returns a reference to a vector containing all predicates which apply to 395 /// \p Expr. 396 ArrayRef<const SCEVPredicate *> getPredicatesForExpr(const SCEV *Expr); 397 398 /// Implementation of the SCEVPredicate interface 399 bool isAlwaysTrue() const override; 400 bool implies(const SCEVPredicate *N) const override; 401 void print(raw_ostream &OS, unsigned Depth) const override; 402 const SCEV *getExpr() const override; 403 404 /// We estimate the complexity of a union predicate as the size number of 405 /// predicates in the union. 406 unsigned getComplexity() const override { return Preds.size(); } 407 408 /// Methods for support type inquiry through isa, cast, and dyn_cast: 409 static inline bool classof(const SCEVPredicate *P) { 410 return P->getKind() == P_Union; 411 } 412 }; 413 414 /// The main scalar evolution driver. Because client code (intentionally) 415 /// can't do much with the SCEV objects directly, they must ask this class 416 /// for services. 417 class ScalarEvolution { 418 public: 419 /// An enum describing the relationship between a SCEV and a loop. 420 enum LoopDisposition { 421 LoopVariant, ///< The SCEV is loop-variant (unknown). 422 LoopInvariant, ///< The SCEV is loop-invariant. 423 LoopComputable ///< The SCEV varies predictably with the loop. 424 }; 425 426 /// An enum describing the relationship between a SCEV and a basic block. 427 enum BlockDisposition { 428 DoesNotDominateBlock, ///< The SCEV does not dominate the block. 429 DominatesBlock, ///< The SCEV dominates the block. 430 ProperlyDominatesBlock ///< The SCEV properly dominates the block. 431 }; 432 433 /// Convenient NoWrapFlags manipulation that hides enum casts and is 434 /// visible in the ScalarEvolution name space. 435 LLVM_NODISCARD static SCEV::NoWrapFlags maskFlags(SCEV::NoWrapFlags Flags, 436 int Mask) { 437 return (SCEV::NoWrapFlags)(Flags & Mask); 438 } 439 LLVM_NODISCARD static SCEV::NoWrapFlags setFlags(SCEV::NoWrapFlags Flags, 440 SCEV::NoWrapFlags OnFlags) { 441 return (SCEV::NoWrapFlags)(Flags | OnFlags); 442 } 443 LLVM_NODISCARD static SCEV::NoWrapFlags 444 clearFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OffFlags) { 445 return (SCEV::NoWrapFlags)(Flags & ~OffFlags); 446 } 447 448 private: 449 /// A CallbackVH to arrange for ScalarEvolution to be notified whenever a 450 /// Value is deleted. 451 class SCEVCallbackVH final : public CallbackVH { 452 ScalarEvolution *SE; 453 void deleted() override; 454 void allUsesReplacedWith(Value *New) override; 455 456 public: 457 SCEVCallbackVH(Value *V, ScalarEvolution *SE = nullptr); 458 }; 459 460 friend class SCEVCallbackVH; 461 friend class SCEVExpander; 462 friend class SCEVUnknown; 463 464 /// The function we are analyzing. 465 /// 466 Function &F; 467 468 /// Does the module have any calls to the llvm.experimental.guard intrinsic 469 /// at all? If this is false, we avoid doing work that will only help if 470 /// thare are guards present in the IR. 471 /// 472 bool HasGuards; 473 474 /// The target library information for the target we are targeting. 475 /// 476 TargetLibraryInfo &TLI; 477 478 /// The tracker for @llvm.assume intrinsics in this function. 479 AssumptionCache &AC; 480 481 /// The dominator tree. 482 /// 483 DominatorTree &DT; 484 485 /// The loop information for the function we are currently analyzing. 486 /// 487 LoopInfo &LI; 488 489 /// This SCEV is used to represent unknown trip counts and things. 490 std::unique_ptr<SCEVCouldNotCompute> CouldNotCompute; 491 492 /// The typedef for HasRecMap. 493 /// 494 typedef DenseMap<const SCEV *, bool> HasRecMapType; 495 496 /// This is a cache to record whether a SCEV contains any scAddRecExpr. 497 HasRecMapType HasRecMap; 498 499 /// The typedef for ExprValueMap. 500 /// 501 typedef std::pair<Value *, ConstantInt *> ValueOffsetPair; 502 typedef DenseMap<const SCEV *, SetVector<ValueOffsetPair>> ExprValueMapType; 503 504 /// ExprValueMap -- This map records the original values from which 505 /// the SCEV expr is generated from. 506 /// 507 /// We want to represent the mapping as SCEV -> ValueOffsetPair instead 508 /// of SCEV -> Value: 509 /// Suppose we know S1 expands to V1, and 510 /// S1 = S2 + C_a 511 /// S3 = S2 + C_b 512 /// where C_a and C_b are different SCEVConstants. Then we'd like to 513 /// expand S3 as V1 - C_a + C_b instead of expanding S2 literally. 514 /// It is helpful when S2 is a complex SCEV expr. 515 /// 516 /// In order to do that, we represent ExprValueMap as a mapping from 517 /// SCEV to ValueOffsetPair. We will save both S1->{V1, 0} and 518 /// S2->{V1, C_a} into the map when we create SCEV for V1. When S3 519 /// is expanded, it will first expand S2 to V1 - C_a because of 520 /// S2->{V1, C_a} in the map, then expand S3 to V1 - C_a + C_b. 521 /// 522 /// Note: S->{V, Offset} in the ExprValueMap means S can be expanded 523 /// to V - Offset. 524 ExprValueMapType ExprValueMap; 525 526 /// The typedef for ValueExprMap. 527 /// 528 typedef DenseMap<SCEVCallbackVH, const SCEV *, DenseMapInfo<Value *>> 529 ValueExprMapType; 530 531 /// This is a cache of the values we have analyzed so far. 532 /// 533 ValueExprMapType ValueExprMap; 534 535 /// Mark predicate values currently being processed by isImpliedCond. 536 SmallPtrSet<Value *, 6> PendingLoopPredicates; 537 538 /// Set to true by isLoopBackedgeGuardedByCond when we're walking the set of 539 /// conditions dominating the backedge of a loop. 540 bool WalkingBEDominatingConds; 541 542 /// Set to true by isKnownPredicateViaSplitting when we're trying to prove a 543 /// predicate by splitting it into a set of independent predicates. 544 bool ProvingSplitPredicate; 545 546 /// Memoized values for the GetMinTrailingZeros 547 DenseMap<const SCEV *, uint32_t> MinTrailingZerosCache; 548 549 /// Private helper method for the GetMinTrailingZeros method 550 uint32_t GetMinTrailingZerosImpl(const SCEV *S); 551 552 /// Information about the number of loop iterations for which a loop exit's 553 /// branch condition evaluates to the not-taken path. This is a temporary 554 /// pair of exact and max expressions that are eventually summarized in 555 /// ExitNotTakenInfo and BackedgeTakenInfo. 556 struct ExitLimit { 557 const SCEV *ExactNotTaken; // The exit is not taken exactly this many times 558 const SCEV *MaxNotTaken; // The exit is not taken at most this many times 559 bool MaxOrZero; // Not taken either exactly MaxNotTaken or zero times 560 561 /// A set of predicate guards for this ExitLimit. The result is only valid 562 /// if all of the predicates in \c Predicates evaluate to 'true' at 563 /// run-time. 564 SmallPtrSet<const SCEVPredicate *, 4> Predicates; 565 566 void addPredicate(const SCEVPredicate *P) { 567 assert(!isa<SCEVUnionPredicate>(P) && "Only add leaf predicates here!"); 568 Predicates.insert(P); 569 } 570 571 /*implicit*/ ExitLimit(const SCEV *E) 572 : ExactNotTaken(E), MaxNotTaken(E), MaxOrZero(false) {} 573 574 ExitLimit( 575 const SCEV *E, const SCEV *M, bool MaxOrZero, 576 ArrayRef<const SmallPtrSetImpl<const SCEVPredicate *> *> PredSetList) 577 : ExactNotTaken(E), MaxNotTaken(M), MaxOrZero(MaxOrZero) { 578 assert((isa<SCEVCouldNotCompute>(ExactNotTaken) || 579 !isa<SCEVCouldNotCompute>(MaxNotTaken)) && 580 "Exact is not allowed to be less precise than Max"); 581 for (auto *PredSet : PredSetList) 582 for (auto *P : *PredSet) 583 addPredicate(P); 584 } 585 586 ExitLimit(const SCEV *E, const SCEV *M, bool MaxOrZero, 587 const SmallPtrSetImpl<const SCEVPredicate *> &PredSet) 588 : ExitLimit(E, M, MaxOrZero, {&PredSet}) {} 589 590 ExitLimit(const SCEV *E, const SCEV *M, bool MaxOrZero) 591 : ExitLimit(E, M, MaxOrZero, None) {} 592 593 /// Test whether this ExitLimit contains any computed information, or 594 /// whether it's all SCEVCouldNotCompute values. 595 bool hasAnyInfo() const { 596 return !isa<SCEVCouldNotCompute>(ExactNotTaken) || 597 !isa<SCEVCouldNotCompute>(MaxNotTaken); 598 } 599 600 /// Test whether this ExitLimit contains all information. 601 bool hasFullInfo() const { 602 return !isa<SCEVCouldNotCompute>(ExactNotTaken); 603 } 604 }; 605 606 /// Information about the number of times a particular loop exit may be 607 /// reached before exiting the loop. 608 struct ExitNotTakenInfo { 609 PoisoningVH<BasicBlock> ExitingBlock; 610 const SCEV *ExactNotTaken; 611 std::unique_ptr<SCEVUnionPredicate> Predicate; 612 bool hasAlwaysTruePredicate() const { 613 return !Predicate || Predicate->isAlwaysTrue(); 614 } 615 616 explicit ExitNotTakenInfo(PoisoningVH<BasicBlock> ExitingBlock, 617 const SCEV *ExactNotTaken, 618 std::unique_ptr<SCEVUnionPredicate> Predicate) 619 : ExitingBlock(ExitingBlock), ExactNotTaken(ExactNotTaken), 620 Predicate(std::move(Predicate)) {} 621 }; 622 623 /// Information about the backedge-taken count of a loop. This currently 624 /// includes an exact count and a maximum count. 625 /// 626 class BackedgeTakenInfo { 627 /// A list of computable exits and their not-taken counts. Loops almost 628 /// never have more than one computable exit. 629 SmallVector<ExitNotTakenInfo, 1> ExitNotTaken; 630 631 /// The pointer part of \c MaxAndComplete is an expression indicating the 632 /// least maximum backedge-taken count of the loop that is known, or a 633 /// SCEVCouldNotCompute. This expression is only valid if the predicates 634 /// associated with all loop exits are true. 635 /// 636 /// The integer part of \c MaxAndComplete is a boolean indicating if \c 637 /// ExitNotTaken has an element for every exiting block in the loop. 638 PointerIntPair<const SCEV *, 1> MaxAndComplete; 639 640 /// True iff the backedge is taken either exactly Max or zero times. 641 bool MaxOrZero; 642 643 /// \name Helper projection functions on \c MaxAndComplete. 644 /// @{ 645 bool isComplete() const { return MaxAndComplete.getInt(); } 646 const SCEV *getMax() const { return MaxAndComplete.getPointer(); } 647 /// @} 648 649 public: 650 BackedgeTakenInfo() : MaxAndComplete(nullptr, 0) {} 651 652 BackedgeTakenInfo(BackedgeTakenInfo &&) = default; 653 BackedgeTakenInfo &operator=(BackedgeTakenInfo &&) = default; 654 655 typedef std::pair<BasicBlock *, ExitLimit> EdgeExitInfo; 656 657 /// Initialize BackedgeTakenInfo from a list of exact exit counts. 658 BackedgeTakenInfo(SmallVectorImpl<EdgeExitInfo> &&ExitCounts, bool Complete, 659 const SCEV *MaxCount, bool MaxOrZero); 660 661 /// Test whether this BackedgeTakenInfo contains any computed information, 662 /// or whether it's all SCEVCouldNotCompute values. 663 bool hasAnyInfo() const { 664 return !ExitNotTaken.empty() || !isa<SCEVCouldNotCompute>(getMax()); 665 } 666 667 /// Test whether this BackedgeTakenInfo contains complete information. 668 bool hasFullInfo() const { return isComplete(); } 669 670 /// Return an expression indicating the exact backedge-taken count of the 671 /// loop if it is known or SCEVCouldNotCompute otherwise. This is the 672 /// number of times the loop header can be guaranteed to execute, minus 673 /// one. 674 /// 675 /// If the SCEV predicate associated with the answer can be different 676 /// from AlwaysTrue, we must add a (non null) Predicates argument. 677 /// The SCEV predicate associated with the answer will be added to 678 /// Predicates. A run-time check needs to be emitted for the SCEV 679 /// predicate in order for the answer to be valid. 680 /// 681 /// Note that we should always know if we need to pass a predicate 682 /// argument or not from the way the ExitCounts vector was computed. 683 /// If we allowed SCEV predicates to be generated when populating this 684 /// vector, this information can contain them and therefore a 685 /// SCEVPredicate argument should be added to getExact. 686 const SCEV *getExact(ScalarEvolution *SE, 687 SCEVUnionPredicate *Predicates = nullptr) const; 688 689 /// Return the number of times this loop exit may fall through to the back 690 /// edge, or SCEVCouldNotCompute. The loop is guaranteed not to exit via 691 /// this block before this number of iterations, but may exit via another 692 /// block. 693 const SCEV *getExact(BasicBlock *ExitingBlock, ScalarEvolution *SE) const; 694 695 /// Get the max backedge taken count for the loop. 696 const SCEV *getMax(ScalarEvolution *SE) const; 697 698 /// Return true if the number of times this backedge is taken is either the 699 /// value returned by getMax or zero. 700 bool isMaxOrZero(ScalarEvolution *SE) const; 701 702 /// Return true if any backedge taken count expressions refer to the given 703 /// subexpression. 704 bool hasOperand(const SCEV *S, ScalarEvolution *SE) const; 705 706 /// Invalidate this result and free associated memory. 707 void clear(); 708 }; 709 710 /// Cache the backedge-taken count of the loops for this function as they 711 /// are computed. 712 DenseMap<const Loop *, BackedgeTakenInfo> BackedgeTakenCounts; 713 714 /// Cache the predicated backedge-taken count of the loops for this 715 /// function as they are computed. 716 DenseMap<const Loop *, BackedgeTakenInfo> PredicatedBackedgeTakenCounts; 717 718 /// This map contains entries for all of the PHI instructions that we 719 /// attempt to compute constant evolutions for. This allows us to avoid 720 /// potentially expensive recomputation of these properties. An instruction 721 /// maps to null if we are unable to compute its exit value. 722 DenseMap<PHINode *, Constant *> ConstantEvolutionLoopExitValue; 723 724 /// This map contains entries for all the expressions that we attempt to 725 /// compute getSCEVAtScope information for, which can be expensive in 726 /// extreme cases. 727 DenseMap<const SCEV *, SmallVector<std::pair<const Loop *, const SCEV *>, 2>> 728 ValuesAtScopes; 729 730 /// Memoized computeLoopDisposition results. 731 DenseMap<const SCEV *, 732 SmallVector<PointerIntPair<const Loop *, 2, LoopDisposition>, 2>> 733 LoopDispositions; 734 735 struct LoopProperties { 736 /// Set to true if the loop contains no instruction that can have side 737 /// effects (i.e. via throwing an exception, volatile or atomic access). 738 bool HasNoAbnormalExits; 739 740 /// Set to true if the loop contains no instruction that can abnormally exit 741 /// the loop (i.e. via throwing an exception, by terminating the thread 742 /// cleanly or by infinite looping in a called function). Strictly 743 /// speaking, the last one is not leaving the loop, but is identical to 744 /// leaving the loop for reasoning about undefined behavior. 745 bool HasNoSideEffects; 746 }; 747 748 /// Cache for \c getLoopProperties. 749 DenseMap<const Loop *, LoopProperties> LoopPropertiesCache; 750 751 /// Return a \c LoopProperties instance for \p L, creating one if necessary. 752 LoopProperties getLoopProperties(const Loop *L); 753 754 bool loopHasNoSideEffects(const Loop *L) { 755 return getLoopProperties(L).HasNoSideEffects; 756 } 757 758 bool loopHasNoAbnormalExits(const Loop *L) { 759 return getLoopProperties(L).HasNoAbnormalExits; 760 } 761 762 /// Compute a LoopDisposition value. 763 LoopDisposition computeLoopDisposition(const SCEV *S, const Loop *L); 764 765 /// Memoized computeBlockDisposition results. 766 DenseMap< 767 const SCEV *, 768 SmallVector<PointerIntPair<const BasicBlock *, 2, BlockDisposition>, 2>> 769 BlockDispositions; 770 771 /// Compute a BlockDisposition value. 772 BlockDisposition computeBlockDisposition(const SCEV *S, const BasicBlock *BB); 773 774 /// Memoized results from getRange 775 DenseMap<const SCEV *, ConstantRange> UnsignedRanges; 776 777 /// Memoized results from getRange 778 DenseMap<const SCEV *, ConstantRange> SignedRanges; 779 780 /// Used to parameterize getRange 781 enum RangeSignHint { HINT_RANGE_UNSIGNED, HINT_RANGE_SIGNED }; 782 783 /// Set the memoized range for the given SCEV. 784 const ConstantRange &setRange(const SCEV *S, RangeSignHint Hint, 785 const ConstantRange &CR) { 786 DenseMap<const SCEV *, ConstantRange> &Cache = 787 Hint == HINT_RANGE_UNSIGNED ? UnsignedRanges : SignedRanges; 788 789 auto Pair = Cache.insert({S, CR}); 790 if (!Pair.second) 791 Pair.first->second = CR; 792 return Pair.first->second; 793 } 794 795 /// Determine the range for a particular SCEV. 796 ConstantRange getRange(const SCEV *S, RangeSignHint Hint); 797 798 /// Determines the range for the affine SCEVAddRecExpr {\p Start,+,\p Stop}. 799 /// Helper for \c getRange. 800 ConstantRange getRangeForAffineAR(const SCEV *Start, const SCEV *Stop, 801 const SCEV *MaxBECount, unsigned BitWidth); 802 803 /// Try to compute a range for the affine SCEVAddRecExpr {\p Start,+,\p 804 /// Stop} by "factoring out" a ternary expression from the add recurrence. 805 /// Helper called by \c getRange. 806 ConstantRange getRangeViaFactoring(const SCEV *Start, const SCEV *Stop, 807 const SCEV *MaxBECount, unsigned BitWidth); 808 809 /// We know that there is no SCEV for the specified value. Analyze the 810 /// expression. 811 const SCEV *createSCEV(Value *V); 812 813 /// Provide the special handling we need to analyze PHI SCEVs. 814 const SCEV *createNodeForPHI(PHINode *PN); 815 816 /// Helper function called from createNodeForPHI. 817 const SCEV *createAddRecFromPHI(PHINode *PN); 818 819 /// Helper function called from createNodeForPHI. 820 const SCEV *createNodeFromSelectLikePHI(PHINode *PN); 821 822 /// Provide special handling for a select-like instruction (currently this 823 /// is either a select instruction or a phi node). \p I is the instruction 824 /// being processed, and it is assumed equivalent to "Cond ? TrueVal : 825 /// FalseVal". 826 const SCEV *createNodeForSelectOrPHI(Instruction *I, Value *Cond, 827 Value *TrueVal, Value *FalseVal); 828 829 /// Provide the special handling we need to analyze GEP SCEVs. 830 const SCEV *createNodeForGEP(GEPOperator *GEP); 831 832 /// Implementation code for getSCEVAtScope; called at most once for each 833 /// SCEV+Loop pair. 834 /// 835 const SCEV *computeSCEVAtScope(const SCEV *S, const Loop *L); 836 837 /// This looks up computed SCEV values for all instructions that depend on 838 /// the given instruction and removes them from the ValueExprMap map if they 839 /// reference SymName. This is used during PHI resolution. 840 void forgetSymbolicName(Instruction *I, const SCEV *SymName); 841 842 /// Return the BackedgeTakenInfo for the given loop, lazily computing new 843 /// values if the loop hasn't been analyzed yet. The returned result is 844 /// guaranteed not to be predicated. 845 const BackedgeTakenInfo &getBackedgeTakenInfo(const Loop *L); 846 847 /// Similar to getBackedgeTakenInfo, but will add predicates as required 848 /// with the purpose of returning complete information. 849 const BackedgeTakenInfo &getPredicatedBackedgeTakenInfo(const Loop *L); 850 851 /// Compute the number of times the specified loop will iterate. 852 /// If AllowPredicates is set, we will create new SCEV predicates as 853 /// necessary in order to return an exact answer. 854 BackedgeTakenInfo computeBackedgeTakenCount(const Loop *L, 855 bool AllowPredicates = false); 856 857 /// Compute the number of times the backedge of the specified loop will 858 /// execute if it exits via the specified block. If AllowPredicates is set, 859 /// this call will try to use a minimal set of SCEV predicates in order to 860 /// return an exact answer. 861 ExitLimit computeExitLimit(const Loop *L, BasicBlock *ExitingBlock, 862 bool AllowPredicates = false); 863 864 /// Compute the number of times the backedge of the specified loop will 865 /// execute if its exit condition were a conditional branch of ExitCond, 866 /// TBB, and FBB. 867 /// 868 /// \p ControlsExit is true if ExitCond directly controls the exit 869 /// branch. In this case, we can assume that the loop exits only if the 870 /// condition is true and can infer that failing to meet the condition prior 871 /// to integer wraparound results in undefined behavior. 872 /// 873 /// If \p AllowPredicates is set, this call will try to use a minimal set of 874 /// SCEV predicates in order to return an exact answer. 875 ExitLimit computeExitLimitFromCond(const Loop *L, Value *ExitCond, 876 BasicBlock *TBB, BasicBlock *FBB, 877 bool ControlsExit, 878 bool AllowPredicates = false); 879 880 /// Compute the number of times the backedge of the specified loop will 881 /// execute if its exit condition were a conditional branch of the ICmpInst 882 /// ExitCond, TBB, and FBB. If AllowPredicates is set, this call will try 883 /// to use a minimal set of SCEV predicates in order to return an exact 884 /// answer. 885 ExitLimit computeExitLimitFromICmp(const Loop *L, ICmpInst *ExitCond, 886 BasicBlock *TBB, BasicBlock *FBB, 887 bool IsSubExpr, 888 bool AllowPredicates = false); 889 890 /// Compute the number of times the backedge of the specified loop will 891 /// execute if its exit condition were a switch with a single exiting case 892 /// to ExitingBB. 893 ExitLimit computeExitLimitFromSingleExitSwitch(const Loop *L, 894 SwitchInst *Switch, 895 BasicBlock *ExitingBB, 896 bool IsSubExpr); 897 898 /// Given an exit condition of 'icmp op load X, cst', try to see if we can 899 /// compute the backedge-taken count. 900 ExitLimit computeLoadConstantCompareExitLimit(LoadInst *LI, Constant *RHS, 901 const Loop *L, 902 ICmpInst::Predicate p); 903 904 /// Compute the exit limit of a loop that is controlled by a 905 /// "(IV >> 1) != 0" type comparison. We cannot compute the exact trip 906 /// count in these cases (since SCEV has no way of expressing them), but we 907 /// can still sometimes compute an upper bound. 908 /// 909 /// Return an ExitLimit for a loop whose backedge is guarded by `LHS Pred 910 /// RHS`. 911 ExitLimit computeShiftCompareExitLimit(Value *LHS, Value *RHS, const Loop *L, 912 ICmpInst::Predicate Pred); 913 914 /// If the loop is known to execute a constant number of times (the 915 /// condition evolves only from constants), try to evaluate a few iterations 916 /// of the loop until we get the exit condition gets a value of ExitWhen 917 /// (true or false). If we cannot evaluate the exit count of the loop, 918 /// return CouldNotCompute. 919 const SCEV *computeExitCountExhaustively(const Loop *L, Value *Cond, 920 bool ExitWhen); 921 922 /// Return the number of times an exit condition comparing the specified 923 /// value to zero will execute. If not computable, return CouldNotCompute. 924 /// If AllowPredicates is set, this call will try to use a minimal set of 925 /// SCEV predicates in order to return an exact answer. 926 ExitLimit howFarToZero(const SCEV *V, const Loop *L, bool IsSubExpr, 927 bool AllowPredicates = false); 928 929 /// Return the number of times an exit condition checking the specified 930 /// value for nonzero will execute. If not computable, return 931 /// CouldNotCompute. 932 ExitLimit howFarToNonZero(const SCEV *V, const Loop *L); 933 934 /// Return the number of times an exit condition containing the specified 935 /// less-than comparison will execute. If not computable, return 936 /// CouldNotCompute. 937 /// 938 /// \p isSigned specifies whether the less-than is signed. 939 /// 940 /// \p ControlsExit is true when the LHS < RHS condition directly controls 941 /// the branch (loops exits only if condition is true). In this case, we can 942 /// use NoWrapFlags to skip overflow checks. 943 /// 944 /// If \p AllowPredicates is set, this call will try to use a minimal set of 945 /// SCEV predicates in order to return an exact answer. 946 ExitLimit howManyLessThans(const SCEV *LHS, const SCEV *RHS, const Loop *L, 947 bool isSigned, bool ControlsExit, 948 bool AllowPredicates = false); 949 950 ExitLimit howManyGreaterThans(const SCEV *LHS, const SCEV *RHS, const Loop *L, 951 bool isSigned, bool IsSubExpr, 952 bool AllowPredicates = false); 953 954 /// Return a predecessor of BB (which may not be an immediate predecessor) 955 /// which has exactly one successor from which BB is reachable, or null if 956 /// no such block is found. 957 std::pair<BasicBlock *, BasicBlock *> 958 getPredecessorWithUniqueSuccessorForBB(BasicBlock *BB); 959 960 /// Test whether the condition described by Pred, LHS, and RHS is true 961 /// whenever the given FoundCondValue value evaluates to true. 962 bool isImpliedCond(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, 963 Value *FoundCondValue, bool Inverse); 964 965 /// Test whether the condition described by Pred, LHS, and RHS is true 966 /// whenever the condition described by FoundPred, FoundLHS, FoundRHS is 967 /// true. 968 bool isImpliedCond(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, 969 ICmpInst::Predicate FoundPred, const SCEV *FoundLHS, 970 const SCEV *FoundRHS); 971 972 /// Test whether the condition described by Pred, LHS, and RHS is true 973 /// whenever the condition described by Pred, FoundLHS, and FoundRHS is 974 /// true. 975 bool isImpliedCondOperands(ICmpInst::Predicate Pred, const SCEV *LHS, 976 const SCEV *RHS, const SCEV *FoundLHS, 977 const SCEV *FoundRHS); 978 979 /// Test whether the condition described by Pred, LHS, and RHS is true 980 /// whenever the condition described by Pred, FoundLHS, and FoundRHS is 981 /// true. Here LHS is an operation that includes FoundLHS as one of its 982 /// arguments. 983 bool isImpliedViaOperations(ICmpInst::Predicate Pred, 984 const SCEV *LHS, const SCEV *RHS, 985 const SCEV *FoundLHS, const SCEV *FoundRHS, 986 unsigned Depth = 0); 987 988 /// Test whether the condition described by Pred, LHS, and RHS is true. 989 /// Use only simple non-recursive types of checks, such as range analysis etc. 990 bool isKnownViaSimpleReasoning(ICmpInst::Predicate Pred, 991 const SCEV *LHS, const SCEV *RHS); 992 993 /// Test whether the condition described by Pred, LHS, and RHS is true 994 /// whenever the condition described by Pred, FoundLHS, and FoundRHS is 995 /// true. 996 bool isImpliedCondOperandsHelper(ICmpInst::Predicate Pred, const SCEV *LHS, 997 const SCEV *RHS, const SCEV *FoundLHS, 998 const SCEV *FoundRHS); 999 1000 /// Test whether the condition described by Pred, LHS, and RHS is true 1001 /// whenever the condition described by Pred, FoundLHS, and FoundRHS is 1002 /// true. Utility function used by isImpliedCondOperands. Tries to get 1003 /// cases like "X `sgt` 0 => X - 1 `sgt` -1". 1004 bool isImpliedCondOperandsViaRanges(ICmpInst::Predicate Pred, const SCEV *LHS, 1005 const SCEV *RHS, const SCEV *FoundLHS, 1006 const SCEV *FoundRHS); 1007 1008 /// Return true if the condition denoted by \p LHS \p Pred \p RHS is implied 1009 /// by a call to \c @llvm.experimental.guard in \p BB. 1010 bool isImpliedViaGuard(BasicBlock *BB, ICmpInst::Predicate Pred, 1011 const SCEV *LHS, const SCEV *RHS); 1012 1013 /// Test whether the condition described by Pred, LHS, and RHS is true 1014 /// whenever the condition described by Pred, FoundLHS, and FoundRHS is 1015 /// true. 1016 /// 1017 /// This routine tries to rule out certain kinds of integer overflow, and 1018 /// then tries to reason about arithmetic properties of the predicates. 1019 bool isImpliedCondOperandsViaNoOverflow(ICmpInst::Predicate Pred, 1020 const SCEV *LHS, const SCEV *RHS, 1021 const SCEV *FoundLHS, 1022 const SCEV *FoundRHS); 1023 1024 /// If we know that the specified Phi is in the header of its containing 1025 /// loop, we know the loop executes a constant number of times, and the PHI 1026 /// node is just a recurrence involving constants, fold it. 1027 Constant *getConstantEvolutionLoopExitValue(PHINode *PN, const APInt &BEs, 1028 const Loop *L); 1029 1030 /// Test if the given expression is known to satisfy the condition described 1031 /// by Pred and the known constant ranges of LHS and RHS. 1032 /// 1033 bool isKnownPredicateViaConstantRanges(ICmpInst::Predicate Pred, 1034 const SCEV *LHS, const SCEV *RHS); 1035 1036 /// Try to prove the condition described by "LHS Pred RHS" by ruling out 1037 /// integer overflow. 1038 /// 1039 /// For instance, this will return true for "A s< (A + C)<nsw>" if C is 1040 /// positive. 1041 bool isKnownPredicateViaNoOverflow(ICmpInst::Predicate Pred, const SCEV *LHS, 1042 const SCEV *RHS); 1043 1044 /// Try to split Pred LHS RHS into logical conjunctions (and's) and try to 1045 /// prove them individually. 1046 bool isKnownPredicateViaSplitting(ICmpInst::Predicate Pred, const SCEV *LHS, 1047 const SCEV *RHS); 1048 1049 /// Try to match the Expr as "(L + R)<Flags>". 1050 bool splitBinaryAdd(const SCEV *Expr, const SCEV *&L, const SCEV *&R, 1051 SCEV::NoWrapFlags &Flags); 1052 1053 /// Compute \p LHS - \p RHS and returns the result as an APInt if it is a 1054 /// constant, and None if it isn't. 1055 /// 1056 /// This is intended to be a cheaper version of getMinusSCEV. We can be 1057 /// frugal here since we just bail out of actually constructing and 1058 /// canonicalizing an expression in the cases where the result isn't going 1059 /// to be a constant. 1060 Optional<APInt> computeConstantDifference(const SCEV *LHS, const SCEV *RHS); 1061 1062 /// Drop memoized information computed for S. 1063 void forgetMemoizedResults(const SCEV *S); 1064 1065 /// Return an existing SCEV for V if there is one, otherwise return nullptr. 1066 const SCEV *getExistingSCEV(Value *V); 1067 1068 /// Return false iff given SCEV contains a SCEVUnknown with NULL value- 1069 /// pointer. 1070 bool checkValidity(const SCEV *S) const; 1071 1072 /// Return true if `ExtendOpTy`({`Start`,+,`Step`}) can be proved to be 1073 /// equal to {`ExtendOpTy`(`Start`),+,`ExtendOpTy`(`Step`)}. This is 1074 /// equivalent to proving no signed (resp. unsigned) wrap in 1075 /// {`Start`,+,`Step`} if `ExtendOpTy` is `SCEVSignExtendExpr` 1076 /// (resp. `SCEVZeroExtendExpr`). 1077 /// 1078 template <typename ExtendOpTy> 1079 bool proveNoWrapByVaryingStart(const SCEV *Start, const SCEV *Step, 1080 const Loop *L); 1081 1082 /// Try to prove NSW or NUW on \p AR relying on ConstantRange manipulation. 1083 SCEV::NoWrapFlags proveNoWrapViaConstantRanges(const SCEVAddRecExpr *AR); 1084 1085 bool isMonotonicPredicateImpl(const SCEVAddRecExpr *LHS, 1086 ICmpInst::Predicate Pred, bool &Increasing); 1087 1088 /// Return SCEV no-wrap flags that can be proven based on reasoning about 1089 /// how poison produced from no-wrap flags on this value (e.g. a nuw add) 1090 /// would trigger undefined behavior on overflow. 1091 SCEV::NoWrapFlags getNoWrapFlagsFromUB(const Value *V); 1092 1093 /// Return true if the SCEV corresponding to \p I is never poison. Proving 1094 /// this is more complex than proving that just \p I is never poison, since 1095 /// SCEV commons expressions across control flow, and you can have cases 1096 /// like: 1097 /// 1098 /// idx0 = a + b; 1099 /// ptr[idx0] = 100; 1100 /// if (<condition>) { 1101 /// idx1 = a +nsw b; 1102 /// ptr[idx1] = 200; 1103 /// } 1104 /// 1105 /// where the SCEV expression (+ a b) is guaranteed to not be poison (and 1106 /// hence not sign-overflow) only if "<condition>" is true. Since both 1107 /// `idx0` and `idx1` will be mapped to the same SCEV expression, (+ a b), 1108 /// it is not okay to annotate (+ a b) with <nsw> in the above example. 1109 bool isSCEVExprNeverPoison(const Instruction *I); 1110 1111 /// This is like \c isSCEVExprNeverPoison but it specifically works for 1112 /// instructions that will get mapped to SCEV add recurrences. Return true 1113 /// if \p I will never generate poison under the assumption that \p I is an 1114 /// add recurrence on the loop \p L. 1115 bool isAddRecNeverPoison(const Instruction *I, const Loop *L); 1116 1117 public: 1118 ScalarEvolution(Function &F, TargetLibraryInfo &TLI, AssumptionCache &AC, 1119 DominatorTree &DT, LoopInfo &LI); 1120 ~ScalarEvolution(); 1121 ScalarEvolution(ScalarEvolution &&Arg); 1122 1123 LLVMContext &getContext() const { return F.getContext(); } 1124 1125 /// Test if values of the given type are analyzable within the SCEV 1126 /// framework. This primarily includes integer types, and it can optionally 1127 /// include pointer types if the ScalarEvolution class has access to 1128 /// target-specific information. 1129 bool isSCEVable(Type *Ty) const; 1130 1131 /// Return the size in bits of the specified type, for which isSCEVable must 1132 /// return true. 1133 uint64_t getTypeSizeInBits(Type *Ty) const; 1134 1135 /// Return a type with the same bitwidth as the given type and which 1136 /// represents how SCEV will treat the given type, for which isSCEVable must 1137 /// return true. For pointer types, this is the pointer-sized integer type. 1138 Type *getEffectiveSCEVType(Type *Ty) const; 1139 1140 // Returns a wider type among {Ty1, Ty2}. 1141 Type *getWiderType(Type *Ty1, Type *Ty2) const; 1142 1143 /// Return true if the SCEV is a scAddRecExpr or it contains 1144 /// scAddRecExpr. The result will be cached in HasRecMap. 1145 /// 1146 bool containsAddRecurrence(const SCEV *S); 1147 1148 /// Return the Value set from which the SCEV expr is generated. 1149 SetVector<ValueOffsetPair> *getSCEVValues(const SCEV *S); 1150 1151 /// Erase Value from ValueExprMap and ExprValueMap. 1152 void eraseValueFromMap(Value *V); 1153 1154 /// Return a SCEV expression for the full generality of the specified 1155 /// expression. 1156 const SCEV *getSCEV(Value *V); 1157 1158 const SCEV *getConstant(ConstantInt *V); 1159 const SCEV *getConstant(const APInt &Val); 1160 const SCEV *getConstant(Type *Ty, uint64_t V, bool isSigned = false); 1161 const SCEV *getTruncateExpr(const SCEV *Op, Type *Ty); 1162 const SCEV *getZeroExtendExpr(const SCEV *Op, Type *Ty); 1163 const SCEV *getSignExtendExpr(const SCEV *Op, Type *Ty); 1164 const SCEV *getAnyExtendExpr(const SCEV *Op, Type *Ty); 1165 const SCEV *getAddExpr(SmallVectorImpl<const SCEV *> &Ops, 1166 SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap, 1167 unsigned Depth = 0); 1168 const SCEV *getAddExpr(const SCEV *LHS, const SCEV *RHS, 1169 SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap) { 1170 SmallVector<const SCEV *, 2> Ops = {LHS, RHS}; 1171 return getAddExpr(Ops, Flags); 1172 } 1173 const SCEV *getAddExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2, 1174 SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap) { 1175 SmallVector<const SCEV *, 3> Ops = {Op0, Op1, Op2}; 1176 return getAddExpr(Ops, Flags); 1177 } 1178 const SCEV *getMulExpr(SmallVectorImpl<const SCEV *> &Ops, 1179 SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap); 1180 const SCEV *getMulExpr(const SCEV *LHS, const SCEV *RHS, 1181 SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap) { 1182 SmallVector<const SCEV *, 2> Ops = {LHS, RHS}; 1183 return getMulExpr(Ops, Flags); 1184 } 1185 const SCEV *getMulExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2, 1186 SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap) { 1187 SmallVector<const SCEV *, 3> Ops = {Op0, Op1, Op2}; 1188 return getMulExpr(Ops, Flags); 1189 } 1190 const SCEV *getUDivExpr(const SCEV *LHS, const SCEV *RHS); 1191 const SCEV *getUDivExactExpr(const SCEV *LHS, const SCEV *RHS); 1192 const SCEV *getAddRecExpr(const SCEV *Start, const SCEV *Step, const Loop *L, 1193 SCEV::NoWrapFlags Flags); 1194 const SCEV *getAddRecExpr(SmallVectorImpl<const SCEV *> &Operands, 1195 const Loop *L, SCEV::NoWrapFlags Flags); 1196 const SCEV *getAddRecExpr(const SmallVectorImpl<const SCEV *> &Operands, 1197 const Loop *L, SCEV::NoWrapFlags Flags) { 1198 SmallVector<const SCEV *, 4> NewOp(Operands.begin(), Operands.end()); 1199 return getAddRecExpr(NewOp, L, Flags); 1200 } 1201 /// Returns an expression for a GEP 1202 /// 1203 /// \p GEP The GEP. The indices contained in the GEP itself are ignored, 1204 /// instead we use IndexExprs. 1205 /// \p IndexExprs The expressions for the indices. 1206 const SCEV *getGEPExpr(GEPOperator *GEP, 1207 const SmallVectorImpl<const SCEV *> &IndexExprs); 1208 const SCEV *getSMaxExpr(const SCEV *LHS, const SCEV *RHS); 1209 const SCEV *getSMaxExpr(SmallVectorImpl<const SCEV *> &Operands); 1210 const SCEV *getUMaxExpr(const SCEV *LHS, const SCEV *RHS); 1211 const SCEV *getUMaxExpr(SmallVectorImpl<const SCEV *> &Operands); 1212 const SCEV *getSMinExpr(const SCEV *LHS, const SCEV *RHS); 1213 const SCEV *getUMinExpr(const SCEV *LHS, const SCEV *RHS); 1214 const SCEV *getUnknown(Value *V); 1215 const SCEV *getCouldNotCompute(); 1216 1217 /// Return a SCEV for the constant 0 of a specific type. 1218 const SCEV *getZero(Type *Ty) { return getConstant(Ty, 0); } 1219 1220 /// Return a SCEV for the constant 1 of a specific type. 1221 const SCEV *getOne(Type *Ty) { return getConstant(Ty, 1); } 1222 1223 /// Return an expression for sizeof AllocTy that is type IntTy 1224 /// 1225 const SCEV *getSizeOfExpr(Type *IntTy, Type *AllocTy); 1226 1227 /// Return an expression for offsetof on the given field with type IntTy 1228 /// 1229 const SCEV *getOffsetOfExpr(Type *IntTy, StructType *STy, unsigned FieldNo); 1230 1231 /// Return the SCEV object corresponding to -V. 1232 /// 1233 const SCEV *getNegativeSCEV(const SCEV *V, 1234 SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap); 1235 1236 /// Return the SCEV object corresponding to ~V. 1237 /// 1238 const SCEV *getNotSCEV(const SCEV *V); 1239 1240 /// Return LHS-RHS. Minus is represented in SCEV as A+B*-1. 1241 const SCEV *getMinusSCEV(const SCEV *LHS, const SCEV *RHS, 1242 SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap); 1243 1244 /// Return a SCEV corresponding to a conversion of the input value to the 1245 /// specified type. If the type must be extended, it is zero extended. 1246 const SCEV *getTruncateOrZeroExtend(const SCEV *V, Type *Ty); 1247 1248 /// Return a SCEV corresponding to a conversion of the input value to the 1249 /// specified type. If the type must be extended, it is sign extended. 1250 const SCEV *getTruncateOrSignExtend(const SCEV *V, Type *Ty); 1251 1252 /// Return a SCEV corresponding to a conversion of the input value to the 1253 /// specified type. If the type must be extended, it is zero extended. The 1254 /// conversion must not be narrowing. 1255 const SCEV *getNoopOrZeroExtend(const SCEV *V, Type *Ty); 1256 1257 /// Return a SCEV corresponding to a conversion of the input value to the 1258 /// specified type. If the type must be extended, it is sign extended. The 1259 /// conversion must not be narrowing. 1260 const SCEV *getNoopOrSignExtend(const SCEV *V, Type *Ty); 1261 1262 /// Return a SCEV corresponding to a conversion of the input value to the 1263 /// specified type. If the type must be extended, it is extended with 1264 /// unspecified bits. The conversion must not be narrowing. 1265 const SCEV *getNoopOrAnyExtend(const SCEV *V, Type *Ty); 1266 1267 /// Return a SCEV corresponding to a conversion of the input value to the 1268 /// specified type. The conversion must not be widening. 1269 const SCEV *getTruncateOrNoop(const SCEV *V, Type *Ty); 1270 1271 /// Promote the operands to the wider of the types using zero-extension, and 1272 /// then perform a umax operation with them. 1273 const SCEV *getUMaxFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS); 1274 1275 /// Promote the operands to the wider of the types using zero-extension, and 1276 /// then perform a umin operation with them. 1277 const SCEV *getUMinFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS); 1278 1279 /// Transitively follow the chain of pointer-type operands until reaching a 1280 /// SCEV that does not have a single pointer operand. This returns a 1281 /// SCEVUnknown pointer for well-formed pointer-type expressions, but corner 1282 /// cases do exist. 1283 const SCEV *getPointerBase(const SCEV *V); 1284 1285 /// Return a SCEV expression for the specified value at the specified scope 1286 /// in the program. The L value specifies a loop nest to evaluate the 1287 /// expression at, where null is the top-level or a specified loop is 1288 /// immediately inside of the loop. 1289 /// 1290 /// This method can be used to compute the exit value for a variable defined 1291 /// in a loop by querying what the value will hold in the parent loop. 1292 /// 1293 /// In the case that a relevant loop exit value cannot be computed, the 1294 /// original value V is returned. 1295 const SCEV *getSCEVAtScope(const SCEV *S, const Loop *L); 1296 1297 /// This is a convenience function which does getSCEVAtScope(getSCEV(V), L). 1298 const SCEV *getSCEVAtScope(Value *V, const Loop *L); 1299 1300 /// Test whether entry to the loop is protected by a conditional between LHS 1301 /// and RHS. This is used to help avoid max expressions in loop trip 1302 /// counts, and to eliminate casts. 1303 bool isLoopEntryGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, 1304 const SCEV *LHS, const SCEV *RHS); 1305 1306 /// Test whether the backedge of the loop is protected by a conditional 1307 /// between LHS and RHS. This is used to to eliminate casts. 1308 bool isLoopBackedgeGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, 1309 const SCEV *LHS, const SCEV *RHS); 1310 1311 /// Returns the maximum trip count of the loop if it is a single-exit 1312 /// loop and we can compute a small maximum for that loop. 1313 /// 1314 /// Implemented in terms of the \c getSmallConstantTripCount overload with 1315 /// the single exiting block passed to it. See that routine for details. 1316 unsigned getSmallConstantTripCount(const Loop *L); 1317 1318 /// Returns the maximum trip count of this loop as a normal unsigned 1319 /// value. Returns 0 if the trip count is unknown or not constant. This 1320 /// "trip count" assumes that control exits via ExitingBlock. More 1321 /// precisely, it is the number of times that control may reach ExitingBlock 1322 /// before taking the branch. For loops with multiple exits, it may not be 1323 /// the number times that the loop header executes if the loop exits 1324 /// prematurely via another branch. 1325 unsigned getSmallConstantTripCount(const Loop *L, BasicBlock *ExitingBlock); 1326 1327 /// Returns the upper bound of the loop trip count as a normal unsigned 1328 /// value. 1329 /// Returns 0 if the trip count is unknown or not constant. 1330 unsigned getSmallConstantMaxTripCount(const Loop *L); 1331 1332 /// Returns the largest constant divisor of the trip count of the 1333 /// loop if it is a single-exit loop and we can compute a small maximum for 1334 /// that loop. 1335 /// 1336 /// Implemented in terms of the \c getSmallConstantTripMultiple overload with 1337 /// the single exiting block passed to it. See that routine for details. 1338 unsigned getSmallConstantTripMultiple(const Loop *L); 1339 1340 /// Returns the largest constant divisor of the trip count of this loop as a 1341 /// normal unsigned value, if possible. This means that the actual trip 1342 /// count is always a multiple of the returned value (don't forget the trip 1343 /// count could very well be zero as well!). As explained in the comments 1344 /// for getSmallConstantTripCount, this assumes that control exits the loop 1345 /// via ExitingBlock. 1346 unsigned getSmallConstantTripMultiple(const Loop *L, 1347 BasicBlock *ExitingBlock); 1348 1349 /// Get the expression for the number of loop iterations for which this loop 1350 /// is guaranteed not to exit via ExitingBlock. Otherwise return 1351 /// SCEVCouldNotCompute. 1352 const SCEV *getExitCount(const Loop *L, BasicBlock *ExitingBlock); 1353 1354 /// If the specified loop has a predictable backedge-taken count, return it, 1355 /// otherwise return a SCEVCouldNotCompute object. The backedge-taken count 1356 /// is the number of times the loop header will be branched to from within 1357 /// the loop. This is one less than the trip count of the loop, since it 1358 /// doesn't count the first iteration, when the header is branched to from 1359 /// outside the loop. 1360 /// 1361 /// Note that it is not valid to call this method on a loop without a 1362 /// loop-invariant backedge-taken count (see 1363 /// hasLoopInvariantBackedgeTakenCount). 1364 /// 1365 const SCEV *getBackedgeTakenCount(const Loop *L); 1366 1367 /// Similar to getBackedgeTakenCount, except it will add a set of 1368 /// SCEV predicates to Predicates that are required to be true in order for 1369 /// the answer to be correct. Predicates can be checked with run-time 1370 /// checks and can be used to perform loop versioning. 1371 const SCEV *getPredicatedBackedgeTakenCount(const Loop *L, 1372 SCEVUnionPredicate &Predicates); 1373 1374 /// Similar to getBackedgeTakenCount, except return the least SCEV value 1375 /// that is known never to be less than the actual backedge taken count. 1376 const SCEV *getMaxBackedgeTakenCount(const Loop *L); 1377 1378 /// Return true if the backedge taken count is either the value returned by 1379 /// getMaxBackedgeTakenCount or zero. 1380 bool isBackedgeTakenCountMaxOrZero(const Loop *L); 1381 1382 /// Return true if the specified loop has an analyzable loop-invariant 1383 /// backedge-taken count. 1384 bool hasLoopInvariantBackedgeTakenCount(const Loop *L); 1385 1386 /// This method should be called by the client when it has changed a loop in 1387 /// a way that may effect ScalarEvolution's ability to compute a trip count, 1388 /// or if the loop is deleted. This call is potentially expensive for large 1389 /// loop bodies. 1390 void forgetLoop(const Loop *L); 1391 1392 /// This method should be called by the client when it has changed a value 1393 /// in a way that may effect its value, or which may disconnect it from a 1394 /// def-use chain linking it to a loop. 1395 void forgetValue(Value *V); 1396 1397 /// Called when the client has changed the disposition of values in 1398 /// this loop. 1399 /// 1400 /// We don't have a way to invalidate per-loop dispositions. Clear and 1401 /// recompute is simpler. 1402 void forgetLoopDispositions(const Loop *L) { LoopDispositions.clear(); } 1403 1404 /// Determine the minimum number of zero bits that S is guaranteed to end in 1405 /// (at every loop iteration). It is, at the same time, the minimum number 1406 /// of times S is divisible by 2. For example, given {4,+,8} it returns 2. 1407 /// If S is guaranteed to be 0, it returns the bitwidth of S. 1408 uint32_t GetMinTrailingZeros(const SCEV *S); 1409 1410 /// Determine the unsigned range for a particular SCEV. 1411 /// 1412 ConstantRange getUnsignedRange(const SCEV *S) { 1413 return getRange(S, HINT_RANGE_UNSIGNED); 1414 } 1415 1416 /// Determine the signed range for a particular SCEV. 1417 /// 1418 ConstantRange getSignedRange(const SCEV *S) { 1419 return getRange(S, HINT_RANGE_SIGNED); 1420 } 1421 1422 /// Test if the given expression is known to be negative. 1423 /// 1424 bool isKnownNegative(const SCEV *S); 1425 1426 /// Test if the given expression is known to be positive. 1427 /// 1428 bool isKnownPositive(const SCEV *S); 1429 1430 /// Test if the given expression is known to be non-negative. 1431 /// 1432 bool isKnownNonNegative(const SCEV *S); 1433 1434 /// Test if the given expression is known to be non-positive. 1435 /// 1436 bool isKnownNonPositive(const SCEV *S); 1437 1438 /// Test if the given expression is known to be non-zero. 1439 /// 1440 bool isKnownNonZero(const SCEV *S); 1441 1442 /// Test if the given expression is known to satisfy the condition described 1443 /// by Pred, LHS, and RHS. 1444 /// 1445 bool isKnownPredicate(ICmpInst::Predicate Pred, const SCEV *LHS, 1446 const SCEV *RHS); 1447 1448 /// Return true if, for all loop invariant X, the predicate "LHS `Pred` X" 1449 /// is monotonically increasing or decreasing. In the former case set 1450 /// `Increasing` to true and in the latter case set `Increasing` to false. 1451 /// 1452 /// A predicate is said to be monotonically increasing if may go from being 1453 /// false to being true as the loop iterates, but never the other way 1454 /// around. A predicate is said to be monotonically decreasing if may go 1455 /// from being true to being false as the loop iterates, but never the other 1456 /// way around. 1457 bool isMonotonicPredicate(const SCEVAddRecExpr *LHS, ICmpInst::Predicate Pred, 1458 bool &Increasing); 1459 1460 /// Return true if the result of the predicate LHS `Pred` RHS is loop 1461 /// invariant with respect to L. Set InvariantPred, InvariantLHS and 1462 /// InvariantLHS so that InvariantLHS `InvariantPred` InvariantRHS is the 1463 /// loop invariant form of LHS `Pred` RHS. 1464 bool isLoopInvariantPredicate(ICmpInst::Predicate Pred, const SCEV *LHS, 1465 const SCEV *RHS, const Loop *L, 1466 ICmpInst::Predicate &InvariantPred, 1467 const SCEV *&InvariantLHS, 1468 const SCEV *&InvariantRHS); 1469 1470 /// Simplify LHS and RHS in a comparison with predicate Pred. Return true 1471 /// iff any changes were made. If the operands are provably equal or 1472 /// unequal, LHS and RHS are set to the same value and Pred is set to either 1473 /// ICMP_EQ or ICMP_NE. 1474 /// 1475 bool SimplifyICmpOperands(ICmpInst::Predicate &Pred, const SCEV *&LHS, 1476 const SCEV *&RHS, unsigned Depth = 0); 1477 1478 /// Return the "disposition" of the given SCEV with respect to the given 1479 /// loop. 1480 LoopDisposition getLoopDisposition(const SCEV *S, const Loop *L); 1481 1482 /// Return true if the value of the given SCEV is unchanging in the 1483 /// specified loop. 1484 bool isLoopInvariant(const SCEV *S, const Loop *L); 1485 1486 /// Return true if the given SCEV changes value in a known way in the 1487 /// specified loop. This property being true implies that the value is 1488 /// variant in the loop AND that we can emit an expression to compute the 1489 /// value of the expression at any particular loop iteration. 1490 bool hasComputableLoopEvolution(const SCEV *S, const Loop *L); 1491 1492 /// Return the "disposition" of the given SCEV with respect to the given 1493 /// block. 1494 BlockDisposition getBlockDisposition(const SCEV *S, const BasicBlock *BB); 1495 1496 /// Return true if elements that makes up the given SCEV dominate the 1497 /// specified basic block. 1498 bool dominates(const SCEV *S, const BasicBlock *BB); 1499 1500 /// Return true if elements that makes up the given SCEV properly dominate 1501 /// the specified basic block. 1502 bool properlyDominates(const SCEV *S, const BasicBlock *BB); 1503 1504 /// Test whether the given SCEV has Op as a direct or indirect operand. 1505 bool hasOperand(const SCEV *S, const SCEV *Op) const; 1506 1507 /// Return the size of an element read or written by Inst. 1508 const SCEV *getElementSize(Instruction *Inst); 1509 1510 /// Compute the array dimensions Sizes from the set of Terms extracted from 1511 /// the memory access function of this SCEVAddRecExpr (second step of 1512 /// delinearization). 1513 void findArrayDimensions(SmallVectorImpl<const SCEV *> &Terms, 1514 SmallVectorImpl<const SCEV *> &Sizes, 1515 const SCEV *ElementSize) const; 1516 1517 void print(raw_ostream &OS) const; 1518 void verify() const; 1519 bool invalidate(Function &F, const PreservedAnalyses &PA, 1520 FunctionAnalysisManager::Invalidator &Inv); 1521 1522 /// Collect parametric terms occurring in step expressions (first step of 1523 /// delinearization). 1524 void collectParametricTerms(const SCEV *Expr, 1525 SmallVectorImpl<const SCEV *> &Terms); 1526 1527 /// Return in Subscripts the access functions for each dimension in Sizes 1528 /// (third step of delinearization). 1529 void computeAccessFunctions(const SCEV *Expr, 1530 SmallVectorImpl<const SCEV *> &Subscripts, 1531 SmallVectorImpl<const SCEV *> &Sizes); 1532 1533 /// Split this SCEVAddRecExpr into two vectors of SCEVs representing the 1534 /// subscripts and sizes of an array access. 1535 /// 1536 /// The delinearization is a 3 step process: the first two steps compute the 1537 /// sizes of each subscript and the third step computes the access functions 1538 /// for the delinearized array: 1539 /// 1540 /// 1. Find the terms in the step functions 1541 /// 2. Compute the array size 1542 /// 3. Compute the access function: divide the SCEV by the array size 1543 /// starting with the innermost dimensions found in step 2. The Quotient 1544 /// is the SCEV to be divided in the next step of the recursion. The 1545 /// Remainder is the subscript of the innermost dimension. Loop over all 1546 /// array dimensions computed in step 2. 1547 /// 1548 /// To compute a uniform array size for several memory accesses to the same 1549 /// object, one can collect in step 1 all the step terms for all the memory 1550 /// accesses, and compute in step 2 a unique array shape. This guarantees 1551 /// that the array shape will be the same across all memory accesses. 1552 /// 1553 /// FIXME: We could derive the result of steps 1 and 2 from a description of 1554 /// the array shape given in metadata. 1555 /// 1556 /// Example: 1557 /// 1558 /// A[][n][m] 1559 /// 1560 /// for i 1561 /// for j 1562 /// for k 1563 /// A[j+k][2i][5i] = 1564 /// 1565 /// The initial SCEV: 1566 /// 1567 /// A[{{{0,+,2*m+5}_i, +, n*m}_j, +, n*m}_k] 1568 /// 1569 /// 1. Find the different terms in the step functions: 1570 /// -> [2*m, 5, n*m, n*m] 1571 /// 1572 /// 2. Compute the array size: sort and unique them 1573 /// -> [n*m, 2*m, 5] 1574 /// find the GCD of all the terms = 1 1575 /// divide by the GCD and erase constant terms 1576 /// -> [n*m, 2*m] 1577 /// GCD = m 1578 /// divide by GCD -> [n, 2] 1579 /// remove constant terms 1580 /// -> [n] 1581 /// size of the array is A[unknown][n][m] 1582 /// 1583 /// 3. Compute the access function 1584 /// a. Divide {{{0,+,2*m+5}_i, +, n*m}_j, +, n*m}_k by the innermost size m 1585 /// Quotient: {{{0,+,2}_i, +, n}_j, +, n}_k 1586 /// Remainder: {{{0,+,5}_i, +, 0}_j, +, 0}_k 1587 /// The remainder is the subscript of the innermost array dimension: [5i]. 1588 /// 1589 /// b. Divide Quotient: {{{0,+,2}_i, +, n}_j, +, n}_k by next outer size n 1590 /// Quotient: {{{0,+,0}_i, +, 1}_j, +, 1}_k 1591 /// Remainder: {{{0,+,2}_i, +, 0}_j, +, 0}_k 1592 /// The Remainder is the subscript of the next array dimension: [2i]. 1593 /// 1594 /// The subscript of the outermost dimension is the Quotient: [j+k]. 1595 /// 1596 /// Overall, we have: A[][n][m], and the access function: A[j+k][2i][5i]. 1597 void delinearize(const SCEV *Expr, SmallVectorImpl<const SCEV *> &Subscripts, 1598 SmallVectorImpl<const SCEV *> &Sizes, 1599 const SCEV *ElementSize); 1600 1601 /// Return the DataLayout associated with the module this SCEV instance is 1602 /// operating on. 1603 const DataLayout &getDataLayout() const { 1604 return F.getParent()->getDataLayout(); 1605 } 1606 1607 const SCEVPredicate *getEqualPredicate(const SCEVUnknown *LHS, 1608 const SCEVConstant *RHS); 1609 1610 const SCEVPredicate * 1611 getWrapPredicate(const SCEVAddRecExpr *AR, 1612 SCEVWrapPredicate::IncrementWrapFlags AddedFlags); 1613 1614 /// Re-writes the SCEV according to the Predicates in \p A. 1615 const SCEV *rewriteUsingPredicate(const SCEV *S, const Loop *L, 1616 SCEVUnionPredicate &A); 1617 /// Tries to convert the \p S expression to an AddRec expression, 1618 /// adding additional predicates to \p Preds as required. 1619 const SCEVAddRecExpr *convertSCEVToAddRecWithPredicates( 1620 const SCEV *S, const Loop *L, 1621 SmallPtrSetImpl<const SCEVPredicate *> &Preds); 1622 1623 private: 1624 /// Compute the backedge taken count knowing the interval difference, the 1625 /// stride and presence of the equality in the comparison. 1626 const SCEV *computeBECount(const SCEV *Delta, const SCEV *Stride, 1627 bool Equality); 1628 1629 /// Verify if an linear IV with positive stride can overflow when in a 1630 /// less-than comparison, knowing the invariant term of the comparison, 1631 /// the stride and the knowledge of NSW/NUW flags on the recurrence. 1632 bool doesIVOverflowOnLT(const SCEV *RHS, const SCEV *Stride, bool IsSigned, 1633 bool NoWrap); 1634 1635 /// Verify if an linear IV with negative stride can overflow when in a 1636 /// greater-than comparison, knowing the invariant term of the comparison, 1637 /// the stride and the knowledge of NSW/NUW flags on the recurrence. 1638 bool doesIVOverflowOnGT(const SCEV *RHS, const SCEV *Stride, bool IsSigned, 1639 bool NoWrap); 1640 1641 /// Get add expr already created or create a new one 1642 const SCEV *getOrCreateAddExpr(SmallVectorImpl<const SCEV *> &Ops, 1643 SCEV::NoWrapFlags Flags); 1644 1645 private: 1646 FoldingSet<SCEV> UniqueSCEVs; 1647 FoldingSet<SCEVPredicate> UniquePreds; 1648 BumpPtrAllocator SCEVAllocator; 1649 1650 /// The head of a linked list of all SCEVUnknown values that have been 1651 /// allocated. This is used by releaseMemory to locate them all and call 1652 /// their destructors. 1653 SCEVUnknown *FirstUnknown; 1654 }; 1655 1656 /// Analysis pass that exposes the \c ScalarEvolution for a function. 1657 class ScalarEvolutionAnalysis 1658 : public AnalysisInfoMixin<ScalarEvolutionAnalysis> { 1659 friend AnalysisInfoMixin<ScalarEvolutionAnalysis>; 1660 static AnalysisKey Key; 1661 1662 public: 1663 typedef ScalarEvolution Result; 1664 1665 ScalarEvolution run(Function &F, FunctionAnalysisManager &AM); 1666 }; 1667 1668 /// Printer pass for the \c ScalarEvolutionAnalysis results. 1669 class ScalarEvolutionPrinterPass 1670 : public PassInfoMixin<ScalarEvolutionPrinterPass> { 1671 raw_ostream &OS; 1672 1673 public: 1674 explicit ScalarEvolutionPrinterPass(raw_ostream &OS) : OS(OS) {} 1675 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 1676 }; 1677 1678 class ScalarEvolutionWrapperPass : public FunctionPass { 1679 std::unique_ptr<ScalarEvolution> SE; 1680 1681 public: 1682 static char ID; 1683 1684 ScalarEvolutionWrapperPass(); 1685 1686 ScalarEvolution &getSE() { return *SE; } 1687 const ScalarEvolution &getSE() const { return *SE; } 1688 1689 bool runOnFunction(Function &F) override; 1690 void releaseMemory() override; 1691 void getAnalysisUsage(AnalysisUsage &AU) const override; 1692 void print(raw_ostream &OS, const Module * = nullptr) const override; 1693 void verifyAnalysis() const override; 1694 }; 1695 1696 /// An interface layer with SCEV used to manage how we see SCEV expressions 1697 /// for values in the context of existing predicates. We can add new 1698 /// predicates, but we cannot remove them. 1699 /// 1700 /// This layer has multiple purposes: 1701 /// - provides a simple interface for SCEV versioning. 1702 /// - guarantees that the order of transformations applied on a SCEV 1703 /// expression for a single Value is consistent across two different 1704 /// getSCEV calls. This means that, for example, once we've obtained 1705 /// an AddRec expression for a certain value through expression 1706 /// rewriting, we will continue to get an AddRec expression for that 1707 /// Value. 1708 /// - lowers the number of expression rewrites. 1709 class PredicatedScalarEvolution { 1710 public: 1711 PredicatedScalarEvolution(ScalarEvolution &SE, Loop &L); 1712 const SCEVUnionPredicate &getUnionPredicate() const; 1713 1714 /// Returns the SCEV expression of V, in the context of the current SCEV 1715 /// predicate. The order of transformations applied on the expression of V 1716 /// returned by ScalarEvolution is guaranteed to be preserved, even when 1717 /// adding new predicates. 1718 const SCEV *getSCEV(Value *V); 1719 1720 /// Get the (predicated) backedge count for the analyzed loop. 1721 const SCEV *getBackedgeTakenCount(); 1722 1723 /// Adds a new predicate. 1724 void addPredicate(const SCEVPredicate &Pred); 1725 1726 /// Attempts to produce an AddRecExpr for V by adding additional SCEV 1727 /// predicates. If we can't transform the expression into an AddRecExpr we 1728 /// return nullptr and not add additional SCEV predicates to the current 1729 /// context. 1730 const SCEVAddRecExpr *getAsAddRec(Value *V); 1731 1732 /// Proves that V doesn't overflow by adding SCEV predicate. 1733 void setNoOverflow(Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags); 1734 1735 /// Returns true if we've proved that V doesn't wrap by means of a SCEV 1736 /// predicate. 1737 bool hasNoOverflow(Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags); 1738 1739 /// Returns the ScalarEvolution analysis used. 1740 ScalarEvolution *getSE() const { return &SE; } 1741 1742 /// We need to explicitly define the copy constructor because of FlagsMap. 1743 PredicatedScalarEvolution(const PredicatedScalarEvolution &); 1744 1745 /// Print the SCEV mappings done by the Predicated Scalar Evolution. 1746 /// The printed text is indented by \p Depth. 1747 void print(raw_ostream &OS, unsigned Depth) const; 1748 1749 private: 1750 /// Increments the version number of the predicate. This needs to be called 1751 /// every time the SCEV predicate changes. 1752 void updateGeneration(); 1753 1754 /// Holds a SCEV and the version number of the SCEV predicate used to 1755 /// perform the rewrite of the expression. 1756 typedef std::pair<unsigned, const SCEV *> RewriteEntry; 1757 1758 /// Maps a SCEV to the rewrite result of that SCEV at a certain version 1759 /// number. If this number doesn't match the current Generation, we will 1760 /// need to do a rewrite. To preserve the transformation order of previous 1761 /// rewrites, we will rewrite the previous result instead of the original 1762 /// SCEV. 1763 DenseMap<const SCEV *, RewriteEntry> RewriteMap; 1764 1765 /// Records what NoWrap flags we've added to a Value *. 1766 ValueMap<Value *, SCEVWrapPredicate::IncrementWrapFlags> FlagsMap; 1767 1768 /// The ScalarEvolution analysis. 1769 ScalarEvolution &SE; 1770 1771 /// The analyzed Loop. 1772 const Loop &L; 1773 1774 /// The SCEVPredicate that forms our context. We will rewrite all 1775 /// expressions assuming that this predicate true. 1776 SCEVUnionPredicate Preds; 1777 1778 /// Marks the version of the SCEV predicate used. When rewriting a SCEV 1779 /// expression we mark it with the version of the predicate. We use this to 1780 /// figure out if the predicate has changed from the last rewrite of the 1781 /// SCEV. If so, we need to perform a new rewrite. 1782 unsigned Generation; 1783 1784 /// The backedge taken count. 1785 const SCEV *BackedgeCount; 1786 }; 1787 } 1788 1789 #endif 1790