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