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