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