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