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