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