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