1//===- llvm/Analysis/ScalarEvolution.h - Scalar Evolution -------*- C++ -*-===// 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 7//===----------------------------------------------------------------------===// 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. 15// This analysis is primarily useful for induction variable substitution and 18//===----------------------------------------------------------------------===// 20#ifndef LLVM_ANALYSIS_SCALAREVOLUTION_H 21#define LLVM_ANALYSIS_SCALAREVOLUTION_H 46classOverflowingBinaryOperator;
62classTargetLibraryInfo;
68/// This class represents an analyzed expression in the program. These are 69/// opaque objects that the client is not allowed to do much with directly. 74 /// A reference to an Interned FoldingSetNodeID for this node. The 75 /// ScalarEvolution's BumpPtrAllocator holds the data. 78// The SCEV baseclass this node corresponds to 82// Estimated complexity of this node's expression tree size. 85 /// This field is initialized to zero and may be used in subclasses to store 86 /// miscellaneous information. 90 /// NoWrapFlags are bitfield indices into SubclassData. 92 /// Add and Mul expressions may have no-unsigned-wrap <NUW> or 93 /// no-signed-wrap <NSW> properties, which are derived from the IR 94 /// operator. NSW is a misnomer that we use to mean no signed overflow or 97 /// AddRec expressions may have a no-self-wraparound <NW> property if, in 98 /// the integer domain, abs(step) * max-iteration(loop) <= 99 /// unsigned-max(bitwidth). This means that the recurrence will never reach 100 /// its start value if the step is non-zero. Computing the same value on 101 /// each iteration is not considered wrapping, and recurrences with step = 0 102 /// are trivially <NW>. <NW> is independent of the sign of step and the 103 /// value the add recurrence starts with. 105 /// Note that NUW and NSW are also valid properties of a recurrence, and 106 /// either implies NW. For convenience, NW will be set for a recurrence 107 /// whenever either NUW or NSW are set. 109 /// We require that the flag on a SCEV apply to the entire scope in which 110 /// that SCEV is defined. A SCEV's scope is set of locations dominated by 111 /// a defining location, which is in turn described by the following rules: 112 /// * A SCEVUnknown is at the point of definition of the Value. 113 /// * A SCEVConstant is defined at all points. 114 /// * A SCEVAddRec is defined starting with the header of the associated 116 /// * All other SCEVs are defined at the earlest point all operands are 119 /// The above rules describe a maximally hoisted form (without regards to 120 /// potential control dependence). A SCEV is defined anywhere a 121 /// corresponding instruction could be defined in said maximally hoisted 122 /// form. Note that SCEVUDivExpr (currently the only expression type which 123 /// can trap) can be defined per these rules in regions where it would trap 124 /// at runtime. A SCEV being defined does not require the existence of any 125 /// instruction within the defined scope. 142 /// Return the LLVM type of this SCEV expression. 145 /// Return operands of this SCEV expression. 148 /// Return true if the expression is a constant zero. 151 /// Return true if the expression is a constant one. 154 /// Return true if the expression is a constant all-ones value. 157 /// Return true if the specified scev is negated, but not a constant. 160// Returns estimated size of the mathematical expression represented by this 161// SCEV. The rules of its calculation are following: 162// 1) Size of a SCEV without operands (like constants and SCEVUnknown) is 1; 163// 2) Size SCEV with operands Op1, Op2, ..., OpN is calculated by formula: 164// (1 + Size(Op1) + ... + Size(OpN)). 165// This value gives us an estimation of time we need to traverse through this 166// SCEV and all its operands recursively. We may use it to avoid performing 167// heavy transformations on SCEVs of excessive size for sake of saving the 173 /// Print out the internal representation of this scalar to the specified 174 /// stream. This should really only be used for debugging purposes. 177 /// This method is used for debugging. 181// Specialize FoldingSetTrait for SCEV to avoid needing to compute 182// temporary FoldingSetNodeID values. 192returnX.FastID.ComputeHash();
201/// An object of this class is returned by queries that could not be answered. 202/// For example, if you ask for the number of iterations of a linked-list 203/// traversal loop, you will get one of these. None of the standard SCEV 204/// operations are valid on this class, it is just a marker. 208 /// Methods for support type inquiry through isa, cast, and dyn_cast: 212/// This class represents an assumption made using SCEV expressions which can 213/// be checked at run-time. 217 /// A reference to an Interned FoldingSetNodeID for this node. The 218 /// ScalarEvolution's BumpPtrAllocator holds the data. 235 /// Returns the estimated complexity of this predicate. This is roughly 236 /// measured in the number of run-time checks required. 239 /// Returns true if the predicate is always true. This means that no 240 /// assumptions were made and nothing needs to be checked at run-time. 243 /// Returns true if this predicate implies \p N. 246 /// Prints a textual representation of this predicate with an indentation of 256// Specialize FoldingSetTrait for SCEVPredicate to avoid needing to compute 257// temporary FoldingSetNodeID values. 271returnX.FastID.ComputeHash();
275/// This class represents an assumption that the expression LHS Pred RHS 276/// evaluates to true, and this can be checked at run-time. 278 /// We assume that LHS Pred RHS is true. 288 /// Implementation of the SCEVPredicate interface 295 /// Returns the left hand side of the predicate. 298 /// Returns the right hand side of the predicate. 301 /// Methods for support type inquiry through isa, cast, and dyn_cast: 307/// This class represents an assumption made on an AddRec expression. Given an 308/// affine AddRec expression {a,+,b}, we assume that it has the nssw or nusw 309/// flags (defined below) in the first X iterations of the loop, where X is a 310/// SCEV expression returned by getPredicatedBackedgeTakenCount). 312/// Note that this does not imply that X is equal to the backedge taken 313/// count. This means that if we have a nusw predicate for i32 {0,+,1} with a 314/// predicated backedge taken count of X, we only guarantee that {0,+,1} has 315/// nusw in the first X iterations. {0,+,1} may still wrap in the loop if we 316/// have more than X iterations. 319 /// Similar to SCEV::NoWrapFlags, but with slightly different semantics 320 /// for FlagNUSW. The increment is considered to be signed, and a + b 321 /// (where b is the increment) is considered to wrap if: 322 /// zext(a + b) != zext(a) + sext(b) 324 /// If Signed is a function that takes an n-bit tuple and maps to the 325 /// integer domain as the tuples value interpreted as twos complement, 326 /// and Unsigned a function that takes an n-bit tuple and maps to the 327 /// integer domain as the base two value of input tuple, then a + b 328 /// has IncrementNUSW iff: 330 /// 0 <= Unsigned(a) + Signed(b) < 2^n 332 /// The IncrementNSSW flag has identical semantics with SCEV::FlagNSW. 334 /// Note that the IncrementNUSW flag is not commutative: if base + inc 335 /// has IncrementNUSW, then inc + base doesn't neccessarily have this 336 /// property. The reason for this is that this is used for sign/zero 337 /// extending affine AddRec SCEV expressions when a SCEVWrapPredicate is 338 /// assumed. A {base,+,inc} expression is already non-commutative with 339 /// regards to base and inc, since it is interpreted as: 340 /// (((base + inc) + inc) + inc) ... 345// (equivalent with SCEV::NSW) 349 /// Convenient IncrementWrapFlags manipulation methods. 355"Invalid flags value!");
372"Invalid flags value!");
377 /// Returns the set of SCEVWrapPredicate no wrap flags implied by a 391 /// Returns the set assumed no overflow flags. 394 /// Implementation of the SCEVPredicate interface 400 /// Methods for support type inquiry through isa, cast, and dyn_cast: 406/// This class represents a composition of other SCEV predicates, and is the 407/// class that most clients will interact with. This is equivalent to a 408/// logical "AND" of all the predicates in the union. 410/// NB! Unlike other SCEVPredicate sub-classes this class does not live in the 411/// ScalarEvolution::Preds folding set. This is why the \c add function is sound. 417 /// Vector with references to all predicates in this union. 420 /// Adds a predicate to this union. 429 /// Implementation of the SCEVPredicate interface 434 /// We estimate the complexity of a union predicate as the size number of 435 /// predicates in the union. 438 /// Methods for support type inquiry through isa, cast, and dyn_cast: 444/// The main scalar evolution driver. Because client code (intentionally) 445/// can't do much with the SCEV objects directly, they must ask this class 451 /// An enum describing the relationship between a SCEV and a loop. 458 /// An enum describing the relationship between a SCEV and a basic block. 465 /// Convenient NoWrapFlags manipulation that hides enum casts and is 466 /// visible in the ScalarEvolution name space. 481return TestFlags ==
maskFlags(Flags, TestFlags);
491 /// Test if values of the given type are analyzable within the SCEV 492 /// framework. This primarily includes integer types, and it can optionally 493 /// include pointer types if the ScalarEvolution class has access to 494 /// target-specific information. 497 /// Return the size in bits of the specified type, for which isSCEVable must 501 /// Return a type with the same bitwidth as the given type and which 502 /// represents how SCEV will treat the given type, for which isSCEVable must 503 /// return true. For pointer types, this is the pointer-sized integer type. 506// Returns a wider type among {Ty1, Ty2}. 509 /// Return true if there exists a point in the program at which both 510 /// A and B could be operands to the same instruction. 511 /// SCEV expressions are generally assumed to correspond to instructions 512 /// which could exists in IR. In general, this requires that there exists 513 /// a use point in the program where all operands dominate the use. 518 /// loop { v1 = load @global1; } 520 /// loop { v2 = load @global2; } 522 /// No SCEV with operand V1, and v2 can exist in this program. 525 /// Return true if the SCEV is a scAddRecExpr or it contains 526 /// scAddRecExpr. The result will be cached in HasRecMap. 529 /// Is operation \p BinOp between \p LHS and \p RHS provably does not have 530 /// a signed/unsigned overflow (\p Signed)? If \p CtxI is specified, the 531 /// no-overflow fact should be true in the context of this instruction. 536 /// Parse NSW/NUW flags from add/sub/mul IR binary operation \p Op into 537 /// SCEV no-wrap flags, and deduce flag[s] that aren't known yet. 538 /// Does not mutate the original instruction. Returns std::nullopt if it could 539 /// not deduce more precise flags than the instruction already has, otherwise 540 /// returns proven flags. 541 std::optional<SCEV::NoWrapFlags>
544 /// Notify this ScalarEvolution that \p User directly uses SCEVs in \p Ops. 547 /// Return true if the SCEV expression contains an undef value. 550 /// Return true if the SCEV expression contains a Value that has been 551 /// optimised out and is now a nullptr. 554 /// Return a SCEV expression for the full generality of the specified 558 /// Return an existing SCEV for V if there is one, otherwise return nullptr. 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>>>
627 /// Returns an expression for a GEP 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. 646bool Sequential =
false);
648bool Sequential =
false);
652 /// Return a SCEV for the constant 0 of a specific type. 655 /// Return a SCEV for the constant 1 of a specific type. 658 /// Return a SCEV for the constant \p Power of two. 664 /// Return a SCEV for the constant -1 of a specific type. 669 /// Return an expression for a TypeSize. 672 /// Return an expression for the alloc size of AllocTy that is type IntTy 675 /// Return an expression for the store size of StoreTy that is type IntTy 678 /// Return an expression for offsetof on the given field with type IntTy 681 /// Return the SCEV object corresponding to -V. 685 /// Return the SCEV object corresponding to ~V. 688 /// Return LHS-RHS. Minus is represented in SCEV as A+B*-1. 690 /// If the LHS and RHS are pointers which don't share a common base 691 /// (according to getPointerBase()), this returns a SCEVCouldNotCompute. 692 /// To compute the difference between two unrelated pointers, you can 693 /// explicitly convert the arguments using getPtrToIntExpr(), for pointer 694 /// types that support it. 699 /// Compute ceil(N / D). N and D are treated as unsigned values. 701 /// Since SCEV doesn't have native ceiling division, this generates a 702 /// SCEV expression of the following form: 704 /// umin(N, 1) + floor((N - umin(N, 1)) / D) 706 /// A denominator of zero or poison is handled the same way as getUDivExpr(). 709 /// Return a SCEV corresponding to a conversion of the input value to the 710 /// specified type. If the type must be extended, it is zero extended. 714 /// Return a SCEV corresponding to a conversion of the input value to the 715 /// specified type. If the type must be extended, it is sign extended. 719 /// Return a SCEV corresponding to a conversion of the input value to the 720 /// specified type. If the type must be extended, it is zero extended. The 721 /// conversion must not be narrowing. 724 /// Return a SCEV corresponding to a conversion of the input value to the 725 /// specified type. If the type must be extended, it is sign extended. The 726 /// conversion must not be narrowing. 729 /// Return a SCEV corresponding to a conversion of the input value to the 730 /// specified type. If the type must be extended, it is extended with 731 /// unspecified bits. The conversion must not be narrowing. 734 /// Return a SCEV corresponding to a conversion of the input value to the 735 /// specified type. The conversion must not be widening. 738 /// Promote the operands to the wider of the types using zero-extension, and 739 /// then perform a umax operation with them. 742 /// Promote the operands to the wider of the types using zero-extension, and 743 /// then perform a umin operation with them. 745bool Sequential =
false);
747 /// Promote the operands to the wider of the types using zero-extension, and 748 /// then perform a umin operation with them. N-ary function. 750bool Sequential =
false);
752 /// Transitively follow the chain of pointer-type operands until reaching a 753 /// SCEV that does not have a single pointer operand. This returns a 754 /// SCEVUnknown pointer for well-formed pointer-type expressions, but corner 758 /// Compute an expression equivalent to S - getPointerBase(S). 761 /// Return a SCEV expression for the specified value at the specified scope 762 /// in the program. The L value specifies a loop nest to evaluate the 763 /// expression at, where null is the top-level or a specified loop is 764 /// immediately inside of the loop. 766 /// This method can be used to compute the exit value for a variable defined 767 /// in a loop by querying what the value will hold in the parent loop. 769 /// In the case that a relevant loop exit value cannot be computed, the 770 /// original value V is returned. 773 /// This is a convenience function which does getSCEVAtScope(getSCEV(V), L). 776 /// Test whether entry to the loop is protected by a conditional between LHS 777 /// and RHS. This is used to help avoid max expressions in loop trip 778 /// counts, and to eliminate casts. 782 /// Test whether entry to the basic block is protected by a conditional 783 /// between LHS and RHS. 787 /// Test whether the backedge of the loop is protected by a conditional 788 /// between LHS and RHS. This is used to eliminate casts. 792 /// A version of getTripCountFromExitCount below which always picks an 793 /// evaluation type which can not result in overflow. 796 /// Convert from an "exit count" (i.e. "backedge taken count") to a "trip 797 /// count". A "trip count" is the number of times the header of the loop 798 /// will execute if an exit is taken after the specified number of backedges 799 /// have been taken. (e.g. TripCount = ExitCount + 1). Note that the 800 /// expression can overflow if ExitCount = UINT_MAX. If EvalTy is not wide 801 /// enough to hold the result without overflow, result unsigned wraps with 802 /// 2s-complement semantics. ex: EC = 255 (i8), TC = 0 (i8) 806 /// Returns the exact trip count of the loop if we can compute it, and 807 /// the result is a small constant. '0' is used to represent an unknown 808 /// or non-constant trip count. Note that a trip count is simply one more 809 /// than the backedge taken count for the loop. 812 /// Return the exact trip count for this loop if we exit through ExitingBlock. 813 /// '0' is used to represent an unknown or non-constant trip count. Note 814 /// that a trip count is simply one more than the backedge taken count for 816 /// This "trip count" assumes that control exits via ExitingBlock. More 817 /// precisely, it is the number of times that control will reach ExitingBlock 818 /// before taking the branch. For loops with multiple exits, it may not be 819 /// the number times that the loop header executes if the loop exits 820 /// prematurely via another branch. 824 /// Returns the upper bound of the loop trip count as a normal unsigned 826 /// Returns 0 if the trip count is unknown, not constant or requires 827 /// SCEV predicates and \p Predicates is nullptr. 832 /// Returns the largest constant divisor of the trip count as a normal 833 /// unsigned value, if possible. This means that the actual trip count is 834 /// always a multiple of the returned value. Returns 1 if the trip count is 835 /// unknown or not guaranteed to be the multiple of a constant., Will also 836 /// return 1 if the trip count is very large (>= 2^32). 837 /// Note that the argument is an exit count for loop L, NOT a trip count. 839constSCEV *ExitCount);
841 /// Returns the largest constant divisor of the trip count of the 842 /// loop. Will return 1 if no trip count could be computed, or if a 843 /// divisor could not be found. 846 /// Returns the largest constant divisor of the trip count of this loop as a 847 /// normal unsigned value, if possible. This means that the actual trip 848 /// count is always a multiple of the returned value (don't forget the trip 849 /// count could very well be zero as well!). As explained in the comments 850 /// for getSmallConstantTripCount, this assumes that control exits the loop 851 /// via ExitingBlock. 855 /// The terms "backedge taken count" and "exit count" are used 856 /// interchangeably to refer to the number of times the backedge of a loop 857 /// has executed before the loop is exited. 859 /// An expression exactly describing the number of times the backedge has 860 /// executed when a loop is exited. 862 /// A constant which provides an upper bound on the exact trip count. 864 /// An expression which provides an upper bound on the exact trip count. 868 /// Return the number of times the backedge executes before the given exit 869 /// would be taken; if not exactly computable, return SCEVCouldNotCompute. 870 /// For a single exit loop, this value is equivelent to the result of 871 /// getBackedgeTakenCount. The loop is guaranteed to exit (via *some* exit) 872 /// before the backedge is executed (ExitCount + 1) times. Note that there 873 /// is no guarantee about *which* exit is taken on the exiting iteration. 877 /// Same as above except this uses the predicated backedge taken info and 878 /// may require predicates. 884 /// If the specified loop has a predictable backedge-taken count, return it, 885 /// otherwise return a SCEVCouldNotCompute object. The backedge-taken count is 886 /// the number of times the loop header will be branched to from within the 887 /// loop, assuming there are no abnormal exists like exception throws. This is 888 /// one less than the trip count of the loop, since it doesn't count the first 889 /// iteration, when the header is branched to from outside the loop. 891 /// Note that it is not valid to call this method on a loop without a 892 /// loop-invariant backedge-taken count (see 893 /// hasLoopInvariantBackedgeTakenCount). 896 /// Similar to getBackedgeTakenCount, except it will add a set of 897 /// SCEV predicates to Predicates that are required to be true in order for 898 /// the answer to be correct. Predicates can be checked with run-time 899 /// checks and can be used to perform loop versioning. 903 /// When successful, this returns a SCEVConstant that is greater than or equal 904 /// to (i.e. a "conservative over-approximation") of the value returend by 905 /// getBackedgeTakenCount. If such a value cannot be computed, it returns the 906 /// SCEVCouldNotCompute object. 911 /// Similar to getConstantMaxBackedgeTakenCount, except it will add a set of 912 /// SCEV predicates to Predicates that are required to be true in order for 913 /// the answer to be correct. Predicates can be checked with run-time 914 /// checks and can be used to perform loop versioning. 918 /// When successful, this returns a SCEV that is greater than or equal 919 /// to (i.e. a "conservative over-approximation") of the value returend by 920 /// getBackedgeTakenCount. If such a value cannot be computed, it returns the 921 /// SCEVCouldNotCompute object. 926 /// Similar to getSymbolicMaxBackedgeTakenCount, except it will add a set of 927 /// SCEV predicates to Predicates that are required to be true in order for 928 /// the answer to be correct. Predicates can be checked with run-time 929 /// checks and can be used to perform loop versioning. 933 /// Return true if the backedge taken count is either the value returned by 934 /// getConstantMaxBackedgeTakenCount or zero. 937 /// Return true if the specified loop has an analyzable loop-invariant 938 /// backedge-taken count. 941// This method should be called by the client when it made any change that 942// would invalidate SCEV's answers, and the client wants to remove all loop 943// information held internally by ScalarEvolution. This is intended to be used 944// when the alternative to forget a loop is too expensive (i.e. large loop 948 /// This method should be called by the client when it has changed a loop in 949 /// a way that may effect ScalarEvolution's ability to compute a trip count, 950 /// or if the loop is deleted. This call is potentially expensive for large 954// This method invokes forgetLoop for the outermost loop of the given loop 955// \p L, making ScalarEvolution forget about all this subtree. This needs to 956// be done whenever we make a transform that may affect the parameters of the 957// outer loop, such as exit counts for branches. 960 /// This method should be called by the client when it has changed a value 961 /// in a way that may effect its value, or which may disconnect it from a 962 /// def-use chain linking it to a loop. 965 /// Forget LCSSA phi node V of loop L to which a new predecessor was added, 966 /// such that it may no longer be trivial. 969 /// Called when the client has changed the disposition of values in 972 /// We don't have a way to invalidate per-loop dispositions. Clear and 973 /// recompute is simpler. 976 /// Called when the client has changed the disposition of values in 979 /// We don't have a way to invalidate per-loop/per-block dispositions. Clear 980 /// and recompute is simpler. 983 /// Determine the minimum number of zero bits that S is guaranteed to end in 984 /// (at every loop iteration). It is, at the same time, the minimum number 985 /// of times S is divisible by 2. For example, given {4,+,8} it returns 2. 986 /// If S is guaranteed to be 0, it returns the bitwidth of S. 989 /// Returns the max constant multiple of S. 992// Returns the max constant multiple of S. If S is exactly 0, return 1. 995 /// Determine the unsigned range for a particular SCEV. 996 /// NOTE: This returns a copy of the reference returned by getRangeRef. 998return getRangeRef(S, HINT_RANGE_UNSIGNED);
1001 /// Determine the min of the unsigned range for a particular SCEV. 1006 /// Determine the max of the unsigned range for a particular SCEV. 1011 /// Determine the signed range for a particular SCEV. 1012 /// NOTE: This returns a copy of the reference returned by getRangeRef. 1014return getRangeRef(S, HINT_RANGE_SIGNED);
1017 /// Determine the min of the signed range for a particular SCEV. 1019return getRangeRef(S, HINT_RANGE_SIGNED).
getSignedMin();
1022 /// Determine the max of the signed range for a particular SCEV. 1024return getRangeRef(S, HINT_RANGE_SIGNED).
getSignedMax();
1027 /// Test if the given expression is known to be negative. 1030 /// Test if the given expression is known to be positive. 1033 /// Test if the given expression is known to be non-negative. 1036 /// Test if the given expression is known to be non-positive. 1039 /// Test if the given expression is known to be non-zero. 1042 /// Test if the given expression is known to be a power of 2. OrNegative 1043 /// allows matching negative power of 2s, and OrZero allows matching 0. 1045bool OrNegative =
false);
1047 /// Splits SCEV expression \p S into two SCEVs. One of them is obtained from 1048 /// \p S by substitution of all AddRec sub-expression related to loop \p L 1049 /// with initial value of that SCEV. The second is obtained from \p S by 1050 /// substitution of all AddRec sub-expressions related to loop \p L with post 1051 /// increment of this AddRec in the loop \p L. In both cases all other AddRec 1052 /// sub-expressions (not related to \p L) remain the same. 1053 /// If the \p S contains non-invariant unknown SCEV the function returns 1054 /// CouldNotCompute SCEV in both values of std::pair. 1055 /// For example, for SCEV S={0, +, 1}<L1> + {0, +, 1}<L2> and loop L=L1 1056 /// the function returns pair: 1057 /// first = {0, +, 1}<L2> 1058 /// second = {1, +, 1}<L1> + {0, +, 1}<L2> 1059 /// We can see that for the first AddRec sub-expression it was replaced with 1060 /// 0 (initial value) for the first element and to {1, +, 1}<L1> (post 1061 /// increment value) for the second one. In both cases AddRec expression 1062 /// related to L2 remains the same. 1066 /// We'd like to check the predicate on every iteration of the most dominated 1067 /// loop between loops used in LHS and RHS. 1068 /// To do this we use the following list of steps: 1069 /// 1. Collect set S all loops on which either LHS or RHS depend. 1070 /// 2. If S is non-empty 1071 /// a. Let PD be the element of S which is dominated by all other elements. 1072 /// b. Let E(LHS) be value of LHS on entry of PD. 1073 /// To get E(LHS), we should just take LHS and replace all AddRecs that are 1074 /// attached to PD on with their entry values. 1075 /// Define E(RHS) in the same way. 1076 /// c. Let B(LHS) be value of L on backedge of PD. 1077 /// To get B(LHS), we should just take LHS and replace all AddRecs that are 1078 /// attached to PD on with their backedge values. 1079 /// Define B(RHS) in the same way. 1080 /// d. Note that E(LHS) and E(RHS) are automatically available on entry of PD, 1081 /// so we can assert on that. 1082 /// e. Return true if isLoopEntryGuardedByCond(Pred, E(LHS), E(RHS)) && 1083 /// isLoopBackedgeGuardedByCond(Pred, B(LHS), B(RHS)) 1086 /// Test if the given expression is known to satisfy the condition described 1087 /// by Pred, LHS, and RHS. 1090 /// Check whether the condition described by Pred, LHS, and RHS is true or 1091 /// false. If we know it, return the evaluation of this condition. If neither 1092 /// is proved, return std::nullopt. 1096 /// Test if the given expression is known to satisfy the condition described 1097 /// by Pred, LHS, and RHS in the given Context. 1101 /// Check whether the condition described by Pred, LHS, and RHS is true or 1102 /// false in the given \p Context. If we know it, return the evaluation of 1103 /// this condition. If neither is proved, return std::nullopt. 1108 /// Test if the condition described by Pred, LHS, RHS is known to be true on 1109 /// every iteration of the loop of the recurrency LHS. 1113 /// Information about the number of loop iterations for which a loop exit's 1114 /// branch condition evaluates to the not-taken path. This is a temporary 1115 /// pair of exact and max expressions that are eventually summarized in 1116 /// ExitNotTakenInfo and BackedgeTakenInfo. 1123// Not taken either exactly ConstantMaxNotTaken or zero times 1126 /// A vector of predicate guards for this ExitLimit. The result is only 1127 /// valid if all of the predicates in \c Predicates evaluate to 'true' at 1131 /// Construct either an exact exit limit from a constant, or an unknown 1132 /// one from a SCEVCouldNotCompute. No other types of SCEVs are allowed 1133 /// as arguments and asserts enforce that internally. 1144 /// Test whether this ExitLimit contains any computed information, or 1145 /// whether it's all SCEVCouldNotCompute values. 1151 /// Test whether this ExitLimit contains all information. 1157 /// Compute the number of times the backedge of the specified loop will 1158 /// execute if its exit condition were a conditional branch of ExitCond. 1160 /// \p ControlsOnlyExit is true if ExitCond directly controls the only exit 1161 /// branch. In this case, we can assume that the loop exits only if the 1162 /// condition is true and can infer that failing to meet the condition prior 1163 /// to integer wraparound results in undefined behavior. 1165 /// If \p AllowPredicates is set, this call will try to use a minimal set of 1166 /// SCEV predicates in order to return an exact answer. 1168bool ExitIfTrue,
bool ControlsOnlyExit,
1169bool AllowPredicates =
false);
1171 /// A predicate is said to be monotonically increasing if may go from being 1172 /// false to being true as the loop iterates, but never the other way 1173 /// around. A predicate is said to be monotonically decreasing if may go 1174 /// from being true to being false as the loop iterates, but never the other 1181 /// If, for all loop invariant X, the predicate "LHS `Pred` X" is 1182 /// monotonically increasing or decreasing, returns 1183 /// Some(MonotonicallyIncreasing) and Some(MonotonicallyDecreasing) 1184 /// respectively. If we could not prove either of these facts, returns 1186 std::optional<MonotonicPredicateType>
1199 /// If the result of the predicate LHS `Pred` RHS is loop invariant with 1200 /// respect to L, return a LoopInvariantPredicate with LHS and RHS being 1201 /// invariants, available at L's entry. Otherwise, return std::nullopt. 1202 std::optional<LoopInvariantPredicate>
1207 /// If the result of the predicate LHS `Pred` RHS is loop invariant with 1208 /// respect to L at given Context during at least first MaxIter iterations, 1209 /// return a LoopInvariantPredicate with LHS and RHS being invariants, 1210 /// available at L's entry. Otherwise, return std::nullopt. The predicate 1211 /// should be the loop's exit condition. 1212 std::optional<LoopInvariantPredicate>
1219 std::optional<LoopInvariantPredicate>
1224 /// Simplify LHS and RHS in a comparison with predicate Pred. Return true 1225 /// iff any changes were made. If the operands are provably equal or 1226 /// unequal, LHS and RHS are set to the same value and Pred is set to either 1227 /// ICMP_EQ or ICMP_NE. 1231 /// Return the "disposition" of the given SCEV with respect to the given 1235 /// Return true if the value of the given SCEV is unchanging in the 1239 /// Determine if the SCEV can be evaluated at loop's entry. It is true if it 1240 /// doesn't depend on a SCEVUnknown of an instruction which is dominated by 1241 /// the header of loop L. 1244 /// Return true if the given SCEV changes value in a known way in the 1245 /// specified loop. This property being true implies that the value is 1246 /// variant in the loop AND that we can emit an expression to compute the 1247 /// value of the expression at any particular loop iteration. 1250 /// Return the "disposition" of the given SCEV with respect to the given 1254 /// Return true if elements that makes up the given SCEV dominate the 1255 /// specified basic block. 1258 /// Return true if elements that makes up the given SCEV properly dominate 1259 /// the specified basic block. 1262 /// Test whether the given SCEV has Op as a direct or indirect operand. 1265 /// Return the size of an element read or written by Inst. 1273 /// Return the DataLayout associated with the module this SCEV instance is 1285 /// Re-writes the SCEV according to the Predicates in \p A. 1288 /// Tries to convert the \p S expression to an AddRec expression, 1289 /// adding additional predicates to \p Preds as required. 1294 /// Compute \p LHS - \p RHS and returns the result as an APInt if it is a 1295 /// constant, and std::nullopt if it isn't. 1297 /// This is intended to be a cheaper version of getMinusSCEV. We can be 1298 /// frugal here since we just bail out of actually constructing and 1299 /// canonicalizing an expression in the cases where the result isn't going 1300 /// to be a constant. 1304 /// Update no-wrap flags of an AddRec. This may drop the cached info about 1305 /// this AddRec (such as range info) in case if new flags may potentially 1311bool PreserveNUW =
false;
1312bool PreserveNSW =
false;
1317 /// Recursively collect loop guards in \p Guards, starting from 1318 /// block \p Block with predecessor \p Pred. The intended starting point 1319 /// is to collect from a loop header and its predecessor. 1326 /// Collect loop guards in \p Guards, starting from PHINode \p 1327 /// Phi, by calling \p collectFromBlock on the incoming blocks of 1328 /// \Phi and trying to merge the found constraints into a single 1329 /// combined one for \p Phi. 1330staticvoid collectFromPHI(
1337 /// Collect rewrite map for loop guards for loop \p L, together with flags 1338 /// indicating if NUW and NSW can be preserved during rewriting. 1341 /// Try to apply the collected loop guards to \p Expr. 1345 /// Try to apply information from loop guards for \p L to \p Expr. 1349 /// Return true if the loop has no abnormal exits. That is, if the loop 1350 /// is not infinite, it must exit through an explicit edge in the CFG. 1351 /// (As opposed to either a) throwing out of the function or b) entering a 1352 /// well defined infinite loop in some callee.) 1354return getLoopProperties(L).HasNoAbnormalExits;
1357 /// Return true if this loop is finite by assumption. That is, 1358 /// to be infinite, it must also be undefined. 1361 /// Return the set of Values that, if poison, will definitively result in S 1362 /// being poison as well. The returned set may be incomplete, i.e. there can 1363 /// be additional Values that also result in S being poison. 1367 /// Check whether it is poison-safe to represent the expression S using the 1368 /// instruction I. If such a replacement is performed, the poison flags of 1369 /// instructions in DropPoisonGeneratingInsts must be dropped. 1376constType *Ty =
nullptr;
1390reinterpret_cast<uintptr_t
>(Ty)));
1394return std::tie(
Op, Ty, C) == std::tie(
RHS.Op,
RHS.Ty,
RHS.C);
1399 /// A CallbackVH to arrange for ScalarEvolution to be notified whenever a 1400 /// Value is deleted. 1404void deleted()
override;
1405void allUsesReplacedWith(
Value *New)
override;
1415 /// The function we are analyzing. 1418 /// Data layout of the module. 1421 /// Does the module have any calls to the llvm.experimental.guard intrinsic 1422 /// at all? If this is false, we avoid doing work that will only help if 1423 /// thare are guards present in the IR. 1426 /// The target library information for the target we are targeting. 1429 /// The tracker for \@llvm.assume intrinsics in this function. 1432 /// The dominator tree. 1435 /// The loop information for the function we are currently analyzing. 1438 /// This SCEV is used to represent unknown trip counts and things. 1439 std::unique_ptr<SCEVCouldNotCompute> CouldNotCompute;
1441 /// The type for HasRecMap. 1444 /// This is a cache to record whether a SCEV contains any scAddRecExpr. 1447 /// The type for ExprValueMap. 1451 /// ExprValueMap -- This map records the original values from which 1452 /// the SCEV expr is generated from. 1455 /// The type for ValueExprMap. 1459 /// This is a cache of the values we have analyzed so far. 1462 /// This is a cache for expressions that got folded to a different existing 1467 /// Mark predicate values currently being processed by isImpliedCond. 1470 /// Mark SCEVUnknown Phis currently being processed by getRangeRef. 1473 /// Mark SCEVUnknown Phis currently being processed by getRangeRefIter. 1476// Mark SCEVUnknown Phis currently being processed by isImpliedViaMerge. 1479 /// Set to true by isLoopBackedgeGuardedByCond when we're walking the set of 1480 /// conditions dominating the backedge of a loop. 1481bool WalkingBEDominatingConds =
false;
1483 /// Set to true by isKnownPredicateViaSplitting when we're trying to prove a 1484 /// predicate by splitting it into a set of independent predicates. 1485bool ProvingSplitPredicate =
false;
1487 /// Memoized values for the getConstantMultiple 1490 /// Return the Value set from which the SCEV expr is generated. 1493 /// Private helper method for the getConstantMultiple method. 1494APInt getConstantMultipleImpl(
constSCEV *S);
1496 /// Information about the number of times a particular loop exit may be 1497 /// reached before exiting the loop. 1498structExitNotTakenInfo {
1500constSCEV *ExactNotTaken;
1501constSCEV *ConstantMaxNotTaken;
1502constSCEV *SymbolicMaxNotTaken;
1506constSCEV *ExactNotTaken,
1507constSCEV *ConstantMaxNotTaken,
1508constSCEV *SymbolicMaxNotTaken,
1510 : ExitingBlock(ExitingBlock), ExactNotTaken(ExactNotTaken),
1511 ConstantMaxNotTaken(ConstantMaxNotTaken),
1512 SymbolicMaxNotTaken(SymbolicMaxNotTaken), Predicates(Predicates) {}
1514bool hasAlwaysTruePredicate()
const{
1515return Predicates.
empty();
1519 /// Information about the backedge-taken count of a loop. This currently 1520 /// includes an exact count and a maximum count. 1522classBackedgeTakenInfo {
1523friendclassScalarEvolution;
1525 /// A list of computable exits and their not-taken counts. Loops almost 1526 /// never have more than one computable exit. 1527 SmallVector<ExitNotTakenInfo, 1> ExitNotTaken;
1529 /// Expression indicating the least constant maximum backedge-taken count of 1530 /// the loop that is known, or a SCEVCouldNotCompute. This expression is 1531 /// only valid if the predicates associated with all loop exits are true. 1532const SCEV *ConstantMax =
nullptr;
1534 /// Indicating if \c ExitNotTaken has an element for every exiting block in 1536bool IsComplete =
false;
1538 /// Expression indicating the least maximum backedge-taken count of the loop 1539 /// that is known, or a SCEVCouldNotCompute. Lazily computed on first query. 1540const SCEV *SymbolicMax =
nullptr;
1542 /// True iff the backedge is taken either exactly Max or zero times. 1543bool MaxOrZero =
false;
1545bool isComplete()
const{
return IsComplete; }
1546const SCEV *getConstantMax()
const{
return ConstantMax; }
1548const ExitNotTakenInfo *getExitNotTaken(
1549const BasicBlock *ExitingBlock,
1550 SmallVectorImpl<const SCEVPredicate *> *Predicates =
nullptr)
const;
1553 BackedgeTakenInfo() =
default;
1554 BackedgeTakenInfo(BackedgeTakenInfo &&) =
default;
1555 BackedgeTakenInfo &operator=(BackedgeTakenInfo &&) =
default;
1557usingEdgeExitInfo = std::pair<BasicBlock *, ExitLimit>;
1559 /// Initialize BackedgeTakenInfo from a list of exact exit counts. 1560 BackedgeTakenInfo(ArrayRef<EdgeExitInfo> ExitCounts,
bool IsComplete,
1561const SCEV *ConstantMax,
bool MaxOrZero);
1563 /// Test whether this BackedgeTakenInfo contains any computed information, 1564 /// or whether it's all SCEVCouldNotCompute values. 1565bool hasAnyInfo()
const{
1566return !ExitNotTaken.empty() ||
1567 !isa<SCEVCouldNotCompute>(getConstantMax());
1570 /// Test whether this BackedgeTakenInfo contains complete information. 1571bool hasFullInfo()
const{
return isComplete(); }
1573 /// Return an expression indicating the exact *backedge-taken* 1574 /// count of the loop if it is known or SCEVCouldNotCompute 1575 /// otherwise. If execution makes it to the backedge on every 1576 /// iteration (i.e. there are no abnormal exists like exception 1577 /// throws and thread exits) then this is the number of times the 1578 /// loop header will execute minus one. 1580 /// If the SCEV predicate associated with the answer can be different 1581 /// from AlwaysTrue, we must add a (non null) Predicates argument. 1582 /// The SCEV predicate associated with the answer will be added to 1583 /// Predicates. A run-time check needs to be emitted for the SCEV 1584 /// predicate in order for the answer to be valid. 1586 /// Note that we should always know if we need to pass a predicate 1587 /// argument or not from the way the ExitCounts vector was computed. 1588 /// If we allowed SCEV predicates to be generated when populating this 1589 /// vector, this information can contain them and therefore a 1590 /// SCEVPredicate argument should be added to getExact. 1591const SCEV *getExact(
1592const Loop *L, ScalarEvolution *SE,
1593 SmallVectorImpl<const SCEVPredicate *> *Predicates =
nullptr)
const;
1595 /// Return the number of times this loop exit may fall through to the back 1596 /// edge, or SCEVCouldNotCompute. The loop is guaranteed not to exit via 1597 /// this block before this number of iterations, but may exit via another 1598 /// block. If \p Predicates is null the function returns CouldNotCompute if 1599 /// predicates are required, otherwise it fills in the required predicates. 1600const SCEV *getExact(
1601const BasicBlock *ExitingBlock, ScalarEvolution *SE,
1602 SmallVectorImpl<const SCEVPredicate *> *Predicates =
nullptr)
const{
1603if (
auto *ENT = getExitNotTaken(ExitingBlock, Predicates))
1604return ENT->ExactNotTaken;
1606return SE->getCouldNotCompute();
1609 /// Get the constant max backedge taken count for the loop. 1610const SCEV *getConstantMax(
1611 ScalarEvolution *SE,
1612 SmallVectorImpl<const SCEVPredicate *> *Predicates =
nullptr)
const;
1614 /// Get the constant max backedge taken count for the particular loop exit. 1615const SCEV *getConstantMax(
1616const BasicBlock *ExitingBlock, ScalarEvolution *SE,
1617 SmallVectorImpl<const SCEVPredicate *> *Predicates =
nullptr)
const{
1618if (
auto *ENT = getExitNotTaken(ExitingBlock, Predicates))
1619return ENT->ConstantMaxNotTaken;
1621return SE->getCouldNotCompute();
1624 /// Get the symbolic max backedge taken count for the loop. 1625const SCEV *getSymbolicMax(
1626const Loop *L, ScalarEvolution *SE,
1627 SmallVectorImpl<const SCEVPredicate *> *Predicates =
nullptr);
1629 /// Get the symbolic max backedge taken count for the particular loop exit. 1630const SCEV *getSymbolicMax(
1631const BasicBlock *ExitingBlock, ScalarEvolution *SE,
1632 SmallVectorImpl<const SCEVPredicate *> *Predicates =
nullptr)
const{
1633if (
auto *ENT = getExitNotTaken(ExitingBlock, Predicates))
1634return ENT->SymbolicMaxNotTaken;
1636return SE->getCouldNotCompute();
1639 /// Return true if the number of times this backedge is taken is either the 1640 /// value returned by getConstantMax or zero. 1641bool isConstantMaxOrZero(ScalarEvolution *SE)
const;
1644 /// Cache the backedge-taken count of the loops for this function as they 1646 DenseMap<const Loop *, BackedgeTakenInfo> BackedgeTakenCounts;
1648 /// Cache the predicated backedge-taken count of the loops for this 1649 /// function as they are computed. 1650 DenseMap<const Loop *, BackedgeTakenInfo> PredicatedBackedgeTakenCounts;
1652 /// Loops whose backedge taken counts directly use this non-constant SCEV. 1653 DenseMap<const SCEV *, SmallPtrSet<PointerIntPair<const Loop *, 1, bool>, 4>>
1656 /// This map contains entries for all of the PHI instructions that we 1657 /// attempt to compute constant evolutions for. This allows us to avoid 1658 /// potentially expensive recomputation of these properties. An instruction 1659 /// maps to null if we are unable to compute its exit value. 1660 DenseMap<PHINode *, Constant *> ConstantEvolutionLoopExitValue;
1662 /// This map contains entries for all the expressions that we attempt to 1663 /// compute getSCEVAtScope information for, which can be expensive in 1665 DenseMap<const SCEV *, SmallVector<std::pair<const Loop *, const SCEV *>, 2>>
1668 /// Reverse map for invalidation purposes: Stores of which SCEV and which 1669 /// loop this is the value-at-scope of. 1670 DenseMap<const SCEV *, SmallVector<std::pair<const Loop *, const SCEV *>, 2>>
1671 ValuesAtScopesUsers;
1673 /// Memoized computeLoopDisposition results. 1674 DenseMap<
const SCEV *,
1675 SmallVector<PointerIntPair<const Loop *, 2, LoopDisposition>, 2>>
1678structLoopProperties {
1679 /// Set to true if the loop contains no instruction that can abnormally exit 1680 /// the loop (i.e. via throwing an exception, by terminating the thread 1681 /// cleanly or by infinite looping in a called function). Strictly 1682 /// speaking, the last one is not leaving the loop, but is identical to 1683 /// leaving the loop for reasoning about undefined behavior. 1684bool HasNoAbnormalExits;
1686 /// Set to true if the loop contains no instruction that can have side 1687 /// effects (i.e. via throwing an exception, volatile or atomic access). 1688bool HasNoSideEffects;
1691 /// Cache for \c getLoopProperties. 1692 DenseMap<const Loop *, LoopProperties> LoopPropertiesCache;
1694 /// Return a \c LoopProperties instance for \p L, creating one if necessary. 1695 LoopProperties getLoopProperties(
const Loop *L);
1697bool loopHasNoSideEffects(
const Loop *L) {
1698return getLoopProperties(L).HasNoSideEffects;
1701 /// Compute a LoopDisposition value. 1704 /// Memoized computeBlockDisposition results. 1707 SmallVector<PointerIntPair<const BasicBlock *, 2, BlockDisposition>, 2>>
1710 /// Compute a BlockDisposition value. 1711BlockDisposition computeBlockDisposition(
const SCEV *S,
const BasicBlock *BB);
1713 /// Stores all SCEV that use a given SCEV as its direct operand. 1714 DenseMap<const SCEV *, SmallPtrSet<const SCEV *, 8> > SCEVUsers;
1716 /// Memoized results from getRange 1717 DenseMap<const SCEV *, ConstantRange> UnsignedRanges;
1719 /// Memoized results from getRange 1720 DenseMap<const SCEV *, ConstantRange> SignedRanges;
1722 /// Used to parameterize getRange 1723enum RangeSignHint { HINT_RANGE_UNSIGNED, HINT_RANGE_SIGNED };
1725 /// Set the memoized range for the given SCEV. 1726const ConstantRange &setRange(
const SCEV *S, RangeSignHint Hint,
1728 DenseMap<const SCEV *, ConstantRange> &Cache =
1729 Hint == HINT_RANGE_UNSIGNED ? UnsignedRanges : SignedRanges;
1731auto Pair = Cache.insert_or_assign(S, std::move(CR));
1732return Pair.first->second;
1735 /// Determine the range for a particular SCEV. 1736 /// NOTE: This returns a reference to an entry in a cache. It must be 1737 /// copied if its needed for longer. 1738const ConstantRange &getRangeRef(
const SCEV *S, RangeSignHint Hint,
1741 /// Determine the range for a particular SCEV, but evaluates ranges for 1742 /// operands iteratively first. 1743const ConstantRange &getRangeRefIter(
const SCEV *S, RangeSignHint Hint);
1745 /// Determines the range for the affine SCEVAddRecExpr {\p Start,+,\p Step}. 1746 /// Helper for \c getRange. 1747 ConstantRange getRangeForAffineAR(
const SCEV *Start,
const SCEV *Step,
1748const APInt &MaxBECount);
1750 /// Determines the range for the affine non-self-wrapping SCEVAddRecExpr {\p 1751 /// Start,+,\p Step}<nw>. 1752 ConstantRange getRangeForAffineNoSelfWrappingAR(
const SCEVAddRecExpr *AddRec,
1753const SCEV *MaxBECount,
1755 RangeSignHint SignHint);
1757 /// Try to compute a range for the affine SCEVAddRecExpr {\p Start,+,\p 1758 /// Step} by "factoring out" a ternary expression from the add recurrence. 1759 /// Helper called by \c getRange. 1760 ConstantRange getRangeViaFactoring(
const SCEV *Start,
const SCEV *Step,
1761const APInt &MaxBECount);
1763 /// If the unknown expression U corresponds to a simple recurrence, return 1764 /// a constant range which represents the entire recurrence. Note that 1765 /// *add* recurrences with loop invariant steps aren't represented by 1766 /// SCEVUnknowns and thus don't use this mechanism. 1767 ConstantRange getRangeForUnknownRecurrence(
constSCEVUnknown *U);
1769 /// We know that there is no SCEV for the specified value. Analyze the 1770 /// expression recursively. 1771const SCEV *createSCEV(Value *V);
1773 /// We know that there is no SCEV for the specified value. Create a new SCEV 1774 /// for \p V iteratively. 1775const SCEV *createSCEVIter(Value *V);
1776 /// Collect operands of \p V for which SCEV expressions should be constructed 1777 /// first. Returns a SCEV directly if it can be constructed trivially for \p 1779const SCEV *getOperandsToCreate(Value *V, SmallVectorImpl<Value *> &Ops);
1781 /// Returns SCEV for the first operand of a phi if all phi operands have 1782 /// identical opcodes and operands. 1783const SCEV *createNodeForPHIWithIdenticalOperands(PHINode *PN);
1785 /// Provide the special handling we need to analyze PHI SCEVs. 1786const SCEV *createNodeForPHI(PHINode *PN);
1788 /// Helper function called from createNodeForPHI. 1789const SCEV *createAddRecFromPHI(PHINode *PN);
1791 /// A helper function for createAddRecFromPHI to handle simple cases. 1792const SCEV *createSimpleAffineAddRec(PHINode *PN, Value *BEValueV,
1793 Value *StartValueV);
1795 /// Helper function called from createNodeForPHI. 1796const SCEV *createNodeFromSelectLikePHI(PHINode *PN);
1798 /// Provide special handling for a select-like instruction (currently this 1799 /// is either a select instruction or a phi node). \p Ty is the type of the 1800 /// instruction being processed, that is assumed equivalent to 1801 /// "Cond ? TrueVal : FalseVal". 1802 std::optional<const SCEV *>
1803 createNodeForSelectOrPHIInstWithICmpInstCond(Type *Ty, ICmpInst *
Cond,
1804 Value *TrueVal, Value *FalseVal);
1806 /// See if we can model this select-like instruction via umin_seq expression. 1807const SCEV *createNodeForSelectOrPHIViaUMinSeq(Value *
I, Value *
Cond,
1811 /// Given a value \p V, which is a select-like instruction (currently this is 1812 /// either a select instruction or a phi node), which is assumed equivalent to 1813 /// Cond ? TrueVal : FalseVal 1814 /// see if we can model it as a SCEV expression. 1815const SCEV *createNodeForSelectOrPHI(Value *V, Value *
Cond, Value *TrueVal,
1818 /// Provide the special handling we need to analyze GEP SCEVs. 1819const SCEV *createNodeForGEP(GEPOperator *
GEP);
1821 /// Implementation code for getSCEVAtScope; called at most once for each 1823const SCEV *computeSCEVAtScope(
const SCEV *S,
const Loop *L);
1825 /// Return the BackedgeTakenInfo for the given loop, lazily computing new 1826 /// values if the loop hasn't been analyzed yet. The returned result is 1827 /// guaranteed not to be predicated. 1828 BackedgeTakenInfo &getBackedgeTakenInfo(
const Loop *L);
1830 /// Similar to getBackedgeTakenInfo, but will add predicates as required 1831 /// with the purpose of returning complete information. 1832 BackedgeTakenInfo &getPredicatedBackedgeTakenInfo(
const Loop *L);
1834 /// Compute the number of times the specified loop will iterate. 1835 /// If AllowPredicates is set, we will create new SCEV predicates as 1836 /// necessary in order to return an exact answer. 1837 BackedgeTakenInfo computeBackedgeTakenCount(
const Loop *L,
1838bool AllowPredicates =
false);
1840 /// Compute the number of times the backedge of the specified loop will 1841 /// execute if it exits via the specified block. If AllowPredicates is set, 1842 /// this call will try to use a minimal set of SCEV predicates in order to 1843 /// return an exact answer. 1844 ExitLimit computeExitLimit(
const Loop *L, BasicBlock *ExitingBlock,
1845bool IsOnlyExit,
bool AllowPredicates =
false);
1847// Helper functions for computeExitLimitFromCond to avoid exponential time 1850classExitLimitCache {
1851// It may look like we need key on the whole (L, ExitIfTrue, 1852// ControlsOnlyExit, AllowPredicates) tuple, but recursive calls to 1853// computeExitLimitFromCondCached from computeExitLimitFromCondImpl only 1854// vary the in \c ExitCond and \c ControlsOnlyExit parameters. We remember 1855// the initial values of the other values to assert our assumption. 1856 SmallDenseMap<PointerIntPair<Value *, 1>, ExitLimit> TripCountMap;
1860bool AllowPredicates;
1863 ExitLimitCache(
const Loop *L,
bool ExitIfTrue,
bool AllowPredicates)
1864 :
L(
L), ExitIfTrue(ExitIfTrue), AllowPredicates(AllowPredicates) {}
1866 std::optional<ExitLimit>
find(
const Loop *L, Value *ExitCond,
1867bool ExitIfTrue,
bool ControlsOnlyExit,
1868bool AllowPredicates);
1870void insert(
const Loop *L, Value *ExitCond,
bool ExitIfTrue,
1871bool ControlsOnlyExit,
bool AllowPredicates,
1872const ExitLimit &EL);
1875usingExitLimitCacheTy = ExitLimitCache;
1877 ExitLimit computeExitLimitFromCondCached(ExitLimitCacheTy &Cache,
1878const Loop *L, Value *ExitCond,
1880bool ControlsOnlyExit,
1881bool AllowPredicates);
1882 ExitLimit computeExitLimitFromCondImpl(ExitLimitCacheTy &Cache,
const Loop *L,
1883 Value *ExitCond,
bool ExitIfTrue,
1884bool ControlsOnlyExit,
1885bool AllowPredicates);
1886 std::optional<ScalarEvolution::ExitLimit> computeExitLimitFromCondFromBinOp(
1887 ExitLimitCacheTy &Cache,
const Loop *L, Value *ExitCond,
bool ExitIfTrue,
1888bool ControlsOnlyExit,
bool AllowPredicates);
1890 /// Compute the number of times the backedge of the specified loop will 1891 /// execute if its exit condition were a conditional branch of the ICmpInst 1892 /// ExitCond and ExitIfTrue. If AllowPredicates is set, this call will try 1893 /// to use a minimal set of SCEV predicates in order to return an exact 1895 ExitLimit computeExitLimitFromICmp(
const Loop *L, ICmpInst *ExitCond,
1898bool AllowPredicates =
false);
1900 /// Variant of previous which takes the components representing an ICmp 1901 /// as opposed to the ICmpInst itself. Note that the prior version can 1902 /// return more precise results in some cases and is preferred when caller 1903 /// has a materialized ICmp. 1904 ExitLimit computeExitLimitFromICmp(
const Loop *L, CmpPredicate Pred,
1905const SCEV *
LHS,
const SCEV *
RHS,
1907bool AllowPredicates =
false);
1909 /// Compute the number of times the backedge of the specified loop will 1910 /// execute if its exit condition were a switch with a single exiting case 1912 ExitLimit computeExitLimitFromSingleExitSwitch(
const Loop *L,
1914 BasicBlock *ExitingBB,
1917 /// Compute the exit limit of a loop that is controlled by a 1918 /// "(IV >> 1) != 0" type comparison. We cannot compute the exact trip 1919 /// count in these cases (since SCEV has no way of expressing them), but we 1920 /// can still sometimes compute an upper bound. 1922 /// Return an ExitLimit for a loop whose backedge is guarded by `LHS Pred 1924 ExitLimit computeShiftCompareExitLimit(Value *
LHS, Value *
RHS,
const Loop *L,
1927 /// If the loop is known to execute a constant number of times (the 1928 /// condition evolves only from constants), try to evaluate a few iterations 1929 /// of the loop until we get the exit condition gets a value of ExitWhen 1930 /// (true or false). If we cannot evaluate the exit count of the loop, 1931 /// return CouldNotCompute. 1932const SCEV *computeExitCountExhaustively(
const Loop *L, Value *
Cond,
1935 /// Return the number of times an exit condition comparing the specified 1936 /// value to zero will execute. If not computable, return CouldNotCompute. 1937 /// If AllowPredicates is set, this call will try to use a minimal set of 1938 /// SCEV predicates in order to return an exact answer. 1939 ExitLimit howFarToZero(
const SCEV *V,
const Loop *L,
bool IsSubExpr,
1940bool AllowPredicates =
false);
1942 /// Return the number of times an exit condition checking the specified 1943 /// value for nonzero will execute. If not computable, return 1944 /// CouldNotCompute. 1945 ExitLimit howFarToNonZero(
const SCEV *V,
const Loop *L);
1947 /// Return the number of times an exit condition containing the specified 1948 /// less-than comparison will execute. If not computable, return 1949 /// CouldNotCompute. 1951 /// \p isSigned specifies whether the less-than is signed. 1953 /// \p ControlsOnlyExit is true when the LHS < RHS condition directly controls 1954 /// the branch (loops exits only if condition is true). In this case, we can 1955 /// use NoWrapFlags to skip overflow checks. 1957 /// If \p AllowPredicates is set, this call will try to use a minimal set of 1958 /// SCEV predicates in order to return an exact answer. 1959 ExitLimit howManyLessThans(
const SCEV *
LHS,
const SCEV *
RHS,
const Loop *L,
1961bool AllowPredicates =
false);
1963 ExitLimit howManyGreaterThans(
const SCEV *
LHS,
const SCEV *
RHS,
const Loop *L,
1965bool AllowPredicates =
false);
1967 /// Return a predecessor of BB (which may not be an immediate predecessor) 1968 /// which has exactly one successor from which BB is reachable, or null if 1969 /// no such block is found. 1970 std::pair<const BasicBlock *, const BasicBlock *>
1971 getPredecessorWithUniqueSuccessorForBB(
const BasicBlock *BB)
const;
1973 /// Test whether the condition described by Pred, LHS, and RHS is true 1974 /// whenever the given FoundCondValue value evaluates to true in given 1975 /// Context. If Context is nullptr, then the found predicate is true 1976 /// everywhere. LHS and FoundLHS may have different type width. 1977bool isImpliedCond(CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS,
1978const Value *FoundCondValue,
bool Inverse,
1979const Instruction *Context =
nullptr);
1981 /// Test whether the condition described by Pred, LHS, and RHS is true 1982 /// whenever the given FoundCondValue value evaluates to true in given 1983 /// Context. If Context is nullptr, then the found predicate is true 1984 /// everywhere. LHS and FoundLHS must have same type width. 1985bool isImpliedCondBalancedTypes(CmpPredicate Pred,
const SCEV *
LHS,
1986const SCEV *
RHS, CmpPredicate FoundPred,
1987const SCEV *FoundLHS,
const SCEV *FoundRHS,
1988const Instruction *CtxI);
1990 /// Test whether the condition described by Pred, LHS, and RHS is true 1991 /// whenever the condition described by FoundPred, FoundLHS, FoundRHS is 1992 /// true in given Context. If Context is nullptr, then the found predicate is 1993 /// true everywhere. 1994bool isImpliedCond(CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS,
1995 CmpPredicate FoundPred,
const SCEV *FoundLHS,
1996const SCEV *FoundRHS,
1997const Instruction *Context =
nullptr);
1999 /// Test whether the condition described by Pred, LHS, and RHS is true 2000 /// whenever the condition described by Pred, FoundLHS, and FoundRHS is 2001 /// true in given Context. If Context is nullptr, then the found predicate is 2002 /// true everywhere. 2003bool isImpliedCondOperands(CmpPredicate Pred,
const SCEV *
LHS,
2004const SCEV *
RHS,
const SCEV *FoundLHS,
2005const SCEV *FoundRHS,
2006const Instruction *Context =
nullptr);
2008 /// Test whether the condition described by Pred, LHS, and RHS is true 2009 /// whenever the condition described by Pred, FoundLHS, and FoundRHS is 2010 /// true. Here LHS is an operation that includes FoundLHS as one of its 2012bool isImpliedViaOperations(CmpPredicate Pred,
const SCEV *
LHS,
2013const SCEV *
RHS,
const SCEV *FoundLHS,
2014const SCEV *FoundRHS,
unsignedDepth = 0);
2016 /// Test whether the condition described by Pred, LHS, and RHS is true. 2017 /// Use only simple non-recursive types of checks, such as range analysis etc. 2018bool isKnownViaNonRecursiveReasoning(CmpPredicate Pred,
const SCEV *
LHS,
2021 /// Test whether the condition described by Pred, LHS, and RHS is true 2022 /// whenever the condition described by Pred, FoundLHS, and FoundRHS is 2024bool isImpliedCondOperandsHelper(CmpPredicate Pred,
const SCEV *
LHS,
2025const SCEV *
RHS,
const SCEV *FoundLHS,
2026const SCEV *FoundRHS);
2028 /// Test whether the condition described by Pred, LHS, and RHS is true 2029 /// whenever the condition described by Pred, FoundLHS, and FoundRHS is 2030 /// true. Utility function used by isImpliedCondOperands. Tries to get 2031 /// cases like "X `sgt` 0 => X - 1 `sgt` -1". 2032bool isImpliedCondOperandsViaRanges(CmpPredicate Pred,
const SCEV *
LHS,
2033const SCEV *
RHS, CmpPredicate FoundPred,
2034const SCEV *FoundLHS,
2035const SCEV *FoundRHS);
2037 /// Return true if the condition denoted by \p LHS \p Pred \p RHS is implied 2038 /// by a call to @llvm.experimental.guard in \p BB. 2039bool isImpliedViaGuard(
const BasicBlock *BB, CmpPredicate Pred,
2040const SCEV *
LHS,
const SCEV *
RHS);
2042 /// Test whether the condition described by Pred, LHS, and RHS is true 2043 /// whenever the condition described by Pred, FoundLHS, and FoundRHS is 2046 /// This routine tries to rule out certain kinds of integer overflow, and 2047 /// then tries to reason about arithmetic properties of the predicates. 2048bool isImpliedCondOperandsViaNoOverflow(CmpPredicate Pred,
const SCEV *
LHS,
2049const SCEV *
RHS,
const SCEV *FoundLHS,
2050const SCEV *FoundRHS);
2052 /// Test whether the condition described by Pred, LHS, and RHS is true 2053 /// whenever the condition described by Pred, FoundLHS, and FoundRHS is 2056 /// This routine tries to weaken the known condition basing on fact that 2057 /// FoundLHS is an AddRec. 2058bool isImpliedCondOperandsViaAddRecStart(CmpPredicate Pred,
const SCEV *
LHS,
2060const SCEV *FoundLHS,
2061const SCEV *FoundRHS,
2062const Instruction *CtxI);
2064 /// Test whether the condition described by Pred, LHS, and RHS is true 2065 /// whenever the condition described by Pred, FoundLHS, and FoundRHS is 2068 /// This routine tries to figure out predicate for Phis which are SCEVUnknown 2069 /// if it is true for every possible incoming value from their respective 2071bool isImpliedViaMerge(CmpPredicate Pred,
const SCEV *
LHS,
const SCEV *
RHS,
2072const SCEV *FoundLHS,
const SCEV *FoundRHS,
2075 /// Test whether the condition described by Pred, LHS, and RHS is true 2076 /// whenever the condition described by Pred, FoundLHS, and FoundRHS is 2079 /// This routine tries to reason about shifts. 2080bool isImpliedCondOperandsViaShift(CmpPredicate Pred,
const SCEV *
LHS,
2081const SCEV *
RHS,
const SCEV *FoundLHS,
2082const SCEV *FoundRHS);
2084 /// If we know that the specified Phi is in the header of its containing 2085 /// loop, we know the loop executes a constant number of times, and the PHI 2086 /// node is just a recurrence involving constants, fold it. 2087Constant *getConstantEvolutionLoopExitValue(PHINode *PN,
const APInt &BEs,
2090 /// Test if the given expression is known to satisfy the condition described 2091 /// by Pred and the known constant ranges of LHS and RHS. 2092bool isKnownPredicateViaConstantRanges(CmpPredicate Pred,
const SCEV *
LHS,
2095 /// Try to prove the condition described by "LHS Pred RHS" by ruling out 2096 /// integer overflow. 2098 /// For instance, this will return true for "A s< (A + C)<nsw>" if C is 2100bool isKnownPredicateViaNoOverflow(CmpPredicate Pred,
const SCEV *
LHS,
2103 /// Try to split Pred LHS RHS into logical conjunctions (and's) and try to 2104 /// prove them individually. 2105bool isKnownPredicateViaSplitting(CmpPredicate Pred,
const SCEV *
LHS,
2108 /// Try to match the Expr as "(L + R)<Flags>". 2109bool splitBinaryAdd(
const SCEV *Expr,
const SCEV *&L,
const SCEV *&R,
2112 /// Forget predicated/non-predicated backedge taken counts for the given loop. 2113void forgetBackedgeTakenCounts(
const Loop *L,
boolPredicated);
2115 /// Drop memoized information for all \p SCEVs. 2116void forgetMemoizedResults(ArrayRef<const SCEV *> SCEVs);
2118 /// Helper for forgetMemoizedResults. 2119void forgetMemoizedResultsImpl(
const SCEV *S);
2121 /// Iterate over instructions in \p Worklist and their users. Erase entries 2122 /// from ValueExprMap and collect SCEV expressions in \p ToForget 2123void visitAndClearUsers(SmallVectorImpl<Instruction *> &Worklist,
2124 SmallPtrSetImpl<Instruction *> &Visited,
2125 SmallVectorImpl<const SCEV *> &ToForget);
2127 /// Erase Value from ValueExprMap and ExprValueMap. 2128void eraseValueFromMap(Value *V);
2130 /// Insert V to S mapping into ValueExprMap and ExprValueMap. 2131void insertValueToMap(Value *V,
const SCEV *S);
2133 /// Return false iff given SCEV contains a SCEVUnknown with NULL value- 2135bool checkValidity(
const SCEV *S)
const;
2137 /// Return true if `ExtendOpTy`({`Start`,+,`Step`}) can be proved to be 2138 /// equal to {`ExtendOpTy`(`Start`),+,`ExtendOpTy`(`Step`)}. This is 2139 /// equivalent to proving no signed (resp. unsigned) wrap in 2140 /// {`Start`,+,`Step`} if `ExtendOpTy` is `SCEVSignExtendExpr` 2141 /// (resp. `SCEVZeroExtendExpr`). 2142template <
typename ExtendOpTy>
2143bool proveNoWrapByVaryingStart(
const SCEV *Start,
const SCEV *Step,
2146 /// Try to prove NSW or NUW on \p AR relying on ConstantRange manipulation. 2149 /// Try to prove NSW on \p AR by proving facts about conditions known on 2150 /// entry and backedge. 2153 /// Try to prove NUW on \p AR by proving facts about conditions known on 2154 /// entry and backedge. 2157 std::optional<MonotonicPredicateType>
2158 getMonotonicPredicateTypeImpl(
const SCEVAddRecExpr *
LHS,
2161 /// Return SCEV no-wrap flags that can be proven based on reasoning about 2162 /// how poison produced from no-wrap flags on this value (e.g. a nuw add) 2163 /// would trigger undefined behavior on overflow. 2166 /// Return a scope which provides an upper bound on the defining scope of 2167 /// 'S'. Specifically, return the first instruction in said bounding scope. 2168 /// Return nullptr if the scope is trivial (function entry). 2169 /// (See scope definition rules associated with flag discussion above) 2170const Instruction *getNonTrivialDefiningScopeBound(
const SCEV *S);
2172 /// Return a scope which provides an upper bound on the defining scope for 2173 /// a SCEV with the operands in Ops. The outparam Precise is set if the 2174 /// bound found is a precise bound (i.e. must be the defining scope.) 2175const Instruction *getDefiningScopeBound(ArrayRef<const SCEV *> Ops,
2178 /// Wrapper around the above for cases which don't care if the bound 2180const Instruction *getDefiningScopeBound(ArrayRef<const SCEV *> Ops);
2182 /// Given two instructions in the same function, return true if we can 2183 /// prove B must execute given A executes. 2184bool isGuaranteedToTransferExecutionTo(
const Instruction *
A,
2185const Instruction *
B);
2187 /// Returns true if \p Op is guaranteed not to cause immediate UB. 2188bool isGuaranteedNotToCauseUB(
const SCEV *
Op);
2190 /// Returns true if \p Op is guaranteed to not be poison. 2191staticbool isGuaranteedNotToBePoison(
const SCEV *
Op);
2193 /// Return true if the SCEV corresponding to \p I is never poison. Proving 2194 /// this is more complex than proving that just \p I is never poison, since 2195 /// SCEV commons expressions across control flow, and you can have cases 2199 /// ptr[idx0] = 100; 2200 /// if (<condition>) { 2201 /// idx1 = a +nsw b; 2202 /// ptr[idx1] = 200; 2205 /// where the SCEV expression (+ a b) is guaranteed to not be poison (and 2206 /// hence not sign-overflow) only if "<condition>" is true. Since both 2207 /// `idx0` and `idx1` will be mapped to the same SCEV expression, (+ a b), 2208 /// it is not okay to annotate (+ a b) with <nsw> in the above example. 2209bool isSCEVExprNeverPoison(
const Instruction *
I);
2211 /// This is like \c isSCEVExprNeverPoison but it specifically works for 2212 /// instructions that will get mapped to SCEV add recurrences. Return true 2213 /// if \p I will never generate poison under the assumption that \p I is an 2214 /// add recurrence on the loop \p L. 2215bool isAddRecNeverPoison(
const Instruction *
I,
const Loop *L);
2217 /// Similar to createAddRecFromPHI, but with the additional flexibility of 2218 /// suggesting runtime overflow checks in case casts are encountered. 2219 /// If successful, the analysis records that for this loop, \p SymbolicPHI, 2220 /// which is the UnknownSCEV currently representing the PHI, can be rewritten 2221 /// into an AddRec, assuming some predicates; The function then returns the 2222 /// AddRec and the predicates as a pair, and caches this pair in 2223 /// PredicatedSCEVRewrites. 2224 /// If the analysis is not successful, a mapping from the \p SymbolicPHI to 2225 /// itself (with no predicates) is recorded, and a nullptr with an empty 2226 /// predicates vector is returned as a pair. 2227 std::optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
2228 createAddRecFromPHIWithCastsImpl(
constSCEVUnknown *SymbolicPHI);
2230 /// Compute the maximum backedge count based on the range of values 2231 /// permitted by Start, End, and Stride. This is for loops of the form 2232 /// {Start, +, Stride} LT End. 2235 /// * the induction variable is known to be positive. 2236 /// * the induction variable is assumed not to overflow (i.e. either it 2237 /// actually doesn't, or we'd have to immediately execute UB) 2238 /// We *don't* assert these preconditions so please be careful. 2239const SCEV *computeMaxBECountForLT(
const SCEV *Start,
const SCEV *Stride,
2243 /// Verify if an linear IV with positive stride can overflow when in a 2244 /// less-than comparison, knowing the invariant term of the comparison, 2246bool canIVOverflowOnLT(
const SCEV *
RHS,
const SCEV *Stride,
bool IsSigned);
2248 /// Verify if an linear IV with negative stride can overflow when in a 2249 /// greater-than comparison, knowing the invariant term of the comparison, 2251bool canIVOverflowOnGT(
const SCEV *
RHS,
const SCEV *Stride,
bool IsSigned);
2253 /// Get add expr already created or create a new one. 2254const SCEV *getOrCreateAddExpr(ArrayRef<const SCEV *> Ops,
2257 /// Get mul expr already created or create a new one. 2258const SCEV *getOrCreateMulExpr(ArrayRef<const SCEV *> Ops,
2261// Get addrec expr already created or create a new one. 2262const SCEV *getOrCreateAddRecExpr(ArrayRef<const SCEV *> Ops,
2265 /// Return x if \p Val is f(x) where f is a 1-1 function. 2266const SCEV *stripInjectiveFunctions(
const SCEV *Val)
const;
2268 /// Find all of the loops transitively used in \p S, and fill \p LoopsUsed. 2269 /// A loop is considered "used" by an expression if it contains 2270 /// an add rec on said loop. 2271void getUsedLoops(
const SCEV *S, SmallPtrSetImpl<const Loop *> &LoopsUsed);
2273 /// Try to match the pattern generated by getURemExpr(A, B). If successful, 2274 /// Assign A and B to LHS and RHS, respectively. 2275bool matchURem(
const SCEV *Expr,
const SCEV *&
LHS,
const SCEV *&
RHS);
2277 /// Look for a SCEV expression with type `SCEVType` and operands `Ops` in 2278 /// `UniqueSCEVs`. Return if found, else nullptr. 2279 SCEV *findExistingSCEVInCache(
SCEVTypes SCEVType, ArrayRef<const SCEV *> Ops);
2281 /// Get reachable blocks in this function, making limited use of SCEV 2282 /// reasoning about conditions. 2283void getReachableBlocks(SmallPtrSetImpl<BasicBlock *> &Reachable,
2286 /// Return the given SCEV expression with a new set of operands. 2287 /// This preserves the origial nowrap flags. 2288const SCEV *getWithOperands(
const SCEV *S,
2289 SmallVectorImpl<const SCEV *> &NewOps);
2291 FoldingSet<SCEV> UniqueSCEVs;
2292 FoldingSet<SCEVPredicate> UniquePreds;
2295 /// This maps loops to a list of addrecs that directly use said loop. 2296 DenseMap<const Loop *, SmallVector<const SCEVAddRecExpr *, 4>> LoopUsers;
2298 /// Cache tentative mappings from UnknownSCEVs in a Loop, to a SCEV expression 2299 /// they can be rewritten into under certain predicates. 2300 DenseMap<std::pair<const SCEVUnknown *, const Loop *>,
2301 std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
2302 PredicatedSCEVRewrites;
2304 /// Set of AddRecs for which proving NUW via an induction has already been 2306 SmallPtrSet<const SCEVAddRecExpr *, 16> UnsignedWrapViaInductionTried;
2308 /// Set of AddRecs for which proving NSW via an induction has already been 2310 SmallPtrSet<const SCEVAddRecExpr *, 16> SignedWrapViaInductionTried;
2312 /// The head of a linked list of all SCEVUnknown values that have been 2313 /// allocated. This is used by releaseMemory to locate them all and call 2314 /// their destructors. 2318/// Analysis pass that exposes the \c ScalarEvolution for a function. 2331/// Verifier pass for the \c ScalarEvolutionAnalysis results. 2339/// Printer pass for the \c ScalarEvolutionAnalysis results. 2353 std::unique_ptr<ScalarEvolution> SE;
2370/// An interface layer with SCEV used to manage how we see SCEV expressions 2371/// for values in the context of existing predicates. We can add new 2372/// predicates, but we cannot remove them. 2374/// This layer has multiple purposes: 2375/// - provides a simple interface for SCEV versioning. 2376/// - guarantees that the order of transformations applied on a SCEV 2377/// expression for a single Value is consistent across two different 2378/// getSCEV calls. This means that, for example, once we've obtained 2379/// an AddRec expression for a certain value through expression 2380/// rewriting, we will continue to get an AddRec expression for that 2382/// - lowers the number of expression rewrites. 2389 /// Returns the SCEV expression of V, in the context of the current SCEV 2390 /// predicate. The order of transformations applied on the expression of V 2391 /// returned by ScalarEvolution is guaranteed to be preserved, even when 2392 /// adding new predicates. 2395 /// Get the (predicated) backedge count for the analyzed loop. 2398 /// Get the (predicated) symbolic max backedge count for the analyzed loop. 2401 /// Returns the upper bound of the loop trip count as a normal unsigned 2402 /// value, or 0 if the trip count is unknown. 2405 /// Adds a new predicate. 2408 /// Attempts to produce an AddRecExpr for V by adding additional SCEV 2409 /// predicates. If we can't transform the expression into an AddRecExpr we 2410 /// return nullptr and not add additional SCEV predicates to the current 2414 /// Proves that V doesn't overflow by adding SCEV predicate. 2417 /// Returns true if we've proved that V doesn't wrap by means of a SCEV 2421 /// Returns the ScalarEvolution analysis used. 2424 /// We need to explicitly define the copy constructor because of FlagsMap. 2427 /// Print the SCEV mappings done by the Predicated Scalar Evolution. 2428 /// The printed text is indented by \p Depth. 2431 /// Check if \p AR1 and \p AR2 are equal, while taking into account 2432 /// Equal predicates in Preds. 2437 /// Increments the version number of the predicate. This needs to be called 2438 /// every time the SCEV predicate changes. 2439void updateGeneration();
2441 /// Holds a SCEV and the version number of the SCEV predicate used to 2442 /// perform the rewrite of the expression. 2443usingRewriteEntry = std::pair<unsigned, const SCEV *>;
2445 /// Maps a SCEV to the rewrite result of that SCEV at a certain version 2446 /// number. If this number doesn't match the current Generation, we will 2447 /// need to do a rewrite. To preserve the transformation order of previous 2448 /// rewrites, we will rewrite the previous result instead of the original 2452 /// Records what NoWrap flags we've added to a Value *. 2455 /// The ScalarEvolution analysis. 2458 /// The analyzed Loop. 2461 /// The SCEVPredicate that forms our context. We will rewrite all 2462 /// expressions assuming that this predicate true. 2463 std::unique_ptr<SCEVUnionPredicate> Preds;
2465 /// Marks the version of the SCEV predicate used. When rewriting a SCEV 2466 /// expression we mark it with the version of the predicate. We use this to 2467 /// figure out if the predicate has changed from the last rewrite of the 2468 /// SCEV. If so, we need to perform a new rewrite. 2469unsigned Generation = 0;
2471 /// The backedge taken count. 2472constSCEV *BackedgeCount =
nullptr;
2474 /// The symbolic backedge taken count. 2475constSCEV *SymbolicMaxBackedgeCount =
nullptr;
2477 /// The constant max trip count for the loop. 2478 std::optional<unsigned> SmallConstantMaxTripCount;
2501}
// end namespace llvm 2503#endif// LLVM_ANALYSIS_SCALAREVOLUTION_H This file implements a class to represent arbitrary precision integral constant values and operations...
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file defines DenseMapInfo traits for DenseMap.
This file defines the DenseMap class.
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
static bool isSigned(unsigned int Opcode)
This file defines a hash set that can be used to remove duplication of nodes in a graph.
This header defines various interfaces for pass management in LLVM.
mir Rename Register Operands
This file defines the PointerIntPair class.
const SmallVectorImpl< MachineOperand > & Cond
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file implements a set that has insertion order iteration characteristics.
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
Class for arbitrary precision integers.
static APInt getOneBitSet(unsigned numBits, unsigned BitNo)
Return an APInt with exactly one bit set in the result.
API to communicate dependencies between analyses during invalidation.
A container for analyses that lazily runs them and caches their results.
Represent the analysis usage information of a pass.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
Value handle with callbacks on RAUW and destruction.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
An abstraction over a floating-point predicate, and a pack of an integer predicate with samesign info...
This is the shared class of boolean and integer constants.
This class represents a range of values.
APInt getUnsignedMin() const
Return the smallest unsigned value contained in the ConstantRange.
APInt getSignedMin() const
Return the smallest signed value contained in the ConstantRange.
APInt getUnsignedMax() const
Return the largest unsigned value contained in the ConstantRange.
APInt getSignedMax() const
Return the largest signed value contained in the ConstantRange.
This class represents an Operation in the Expression.
A parsed version of the target data layout string in and methods for querying it.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Node - This class is used to maintain the singly linked bucket list in a folding set.
FoldingSetNodeIDRef - This class describes a reference to an interned FoldingSetNodeID,...
FoldingSetNodeID - This class is used to gather all the unique data bits of a node.
FunctionPass class - This class is used to implement most global optimizations.
This is an important class for using LLVM in a threaded context.
Represents a single loop in the control flow graph.
A Module instance is used to store all the information related to an LLVM module.
Utility class for integer operators which may exhibit overflow - Add, Sub, Mul, and Shl.
Value handle that poisons itself if the Value is deleted.
An interface layer with SCEV used to manage how we see SCEV expressions for values in the context of ...
void addPredicate(const SCEVPredicate &Pred)
Adds a new predicate.
ScalarEvolution * getSE() const
Returns the ScalarEvolution analysis used.
const SCEVPredicate & getPredicate() const
bool hasNoOverflow(Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags)
Returns true if we've proved that V doesn't wrap by means of a SCEV predicate.
void setNoOverflow(Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags)
Proves that V doesn't overflow by adding SCEV predicate.
void print(raw_ostream &OS, unsigned Depth) const
Print the SCEV mappings done by the Predicated Scalar Evolution.
bool areAddRecsEqualWithPreds(const SCEVAddRecExpr *AR1, const SCEVAddRecExpr *AR2) const
Check if AR1 and AR2 are equal, while taking into account Equal predicates in Preds.
const SCEVAddRecExpr * getAsAddRec(Value *V)
Attempts to produce an AddRecExpr for V by adding additional SCEV predicates.
unsigned getSmallConstantMaxTripCount()
Returns the upper bound of the loop trip count as a normal unsigned value, or 0 if the trip count is ...
const SCEV * getBackedgeTakenCount()
Get the (predicated) backedge count for the analyzed loop.
const SCEV * getSymbolicMaxBackedgeTakenCount()
Get the (predicated) symbolic max backedge count for the analyzed loop.
const SCEV * getSCEV(Value *V)
Returns the SCEV expression of V, in the context of the current SCEV predicate.
A set of analyses that are preserved following a run of a transformation pass.
This node represents a polynomial recurrence on the trip count of the specified loop.
This class represents an assumption that the expression LHS Pred RHS evaluates to true,...
const SCEV * getRHS() const
Returns the right hand side of the predicate.
ICmpInst::Predicate getPredicate() const
bool isAlwaysTrue() const override
Returns true if the predicate is always true.
const SCEV * getLHS() const
Returns the left hand side of the predicate.
static bool classof(const SCEVPredicate *P)
Methods for support type inquiry through isa, cast, and dyn_cast:
void print(raw_ostream &OS, unsigned Depth=0) const override
Prints a textual representation of this predicate with an indentation of Depth.
bool implies(const SCEVPredicate *N, ScalarEvolution &SE) const override
Implementation of the SCEVPredicate interface.
This class uses information about analyze scalars to rewrite expressions in canonical form.
This class represents an assumption made using SCEV expressions which can be checked at run-time.
SCEVPredicateKind getKind() const
virtual unsigned getComplexity() const
Returns the estimated complexity of this predicate.
SCEVPredicate & operator=(const SCEVPredicate &)=default
SCEVPredicate(const SCEVPredicate &)=default
virtual bool implies(const SCEVPredicate *N, ScalarEvolution &SE) const =0
Returns true if this predicate implies N.
virtual void print(raw_ostream &OS, unsigned Depth=0) const =0
Prints a textual representation of this predicate with an indentation of Depth.
virtual bool isAlwaysTrue() const =0
Returns true if the predicate is always true.
This class represents a composition of other SCEV predicates, and is the class that most clients will...
void print(raw_ostream &OS, unsigned Depth) const override
Prints a textual representation of this predicate with an indentation of Depth.
bool implies(const SCEVPredicate *N, ScalarEvolution &SE) const override
Returns true if this predicate implies N.
unsigned getComplexity() const override
We estimate the complexity of a union predicate as the size number of predicates in the union.
bool isAlwaysTrue() const override
Implementation of the SCEVPredicate interface.
ArrayRef< const SCEVPredicate * > getPredicates() const
static bool classof(const SCEVPredicate *P)
Methods for support type inquiry through isa, cast, and dyn_cast:
This means that we are dealing with an entirely unknown SCEV value, and only represent it as its LLVM...
This class represents an assumption made on an AddRec expression.
IncrementWrapFlags
Similar to SCEV::NoWrapFlags, but with slightly different semantics for FlagNUSW.
bool implies(const SCEVPredicate *N, ScalarEvolution &SE) const override
Returns true if this predicate implies N.
static SCEVWrapPredicate::IncrementWrapFlags setFlags(SCEVWrapPredicate::IncrementWrapFlags Flags, SCEVWrapPredicate::IncrementWrapFlags OnFlags)
void print(raw_ostream &OS, unsigned Depth=0) const override
Prints a textual representation of this predicate with an indentation of Depth.
bool isAlwaysTrue() const override
Returns true if the predicate is always true.
const SCEVAddRecExpr * getExpr() const
Implementation of the SCEVPredicate interface.
static SCEVWrapPredicate::IncrementWrapFlags clearFlags(SCEVWrapPredicate::IncrementWrapFlags Flags, SCEVWrapPredicate::IncrementWrapFlags OffFlags)
Convenient IncrementWrapFlags manipulation methods.
static bool classof(const SCEVPredicate *P)
Methods for support type inquiry through isa, cast, and dyn_cast:
static SCEVWrapPredicate::IncrementWrapFlags getImpliedFlags(const SCEVAddRecExpr *AR, ScalarEvolution &SE)
Returns the set of SCEVWrapPredicate no wrap flags implied by a SCEVAddRecExpr.
IncrementWrapFlags getFlags() const
Returns the set assumed no overflow flags.
static SCEVWrapPredicate::IncrementWrapFlags maskFlags(SCEVWrapPredicate::IncrementWrapFlags Flags, int Mask)
This class represents an analyzed expression in the program.
ArrayRef< const SCEV * > operands() const
Return operands of this SCEV expression.
unsigned short getExpressionSize() const
SCEV & operator=(const SCEV &)=delete
bool isOne() const
Return true if the expression is a constant one.
bool isZero() const
Return true if the expression is a constant zero.
SCEV(const SCEV &)=delete
void dump() const
This method is used for debugging.
bool isAllOnesValue() const
Return true if the expression is a constant all-ones value.
bool isNonConstantNegative() const
Return true if the specified scev is negated, but not a constant.
const unsigned short ExpressionSize
void print(raw_ostream &OS) const
Print out the internal representation of this scalar to the specified stream.
SCEV(const FoldingSetNodeIDRef ID, SCEVTypes SCEVTy, unsigned short ExpressionSize)
SCEVTypes getSCEVType() const
unsigned short SubclassData
This field is initialized to zero and may be used in subclasses to store miscellaneous information.
Type * getType() const
Return the LLVM type of this SCEV expression.
NoWrapFlags
NoWrapFlags are bitfield indices into SubclassData.
Analysis pass that exposes the ScalarEvolution for a function.
ScalarEvolution run(Function &F, FunctionAnalysisManager &AM)
Printer pass for the ScalarEvolutionAnalysis results.
ScalarEvolutionPrinterPass(raw_ostream &OS)
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Verifier pass for the ScalarEvolutionAnalysis results.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
void print(raw_ostream &OS, const Module *=nullptr) const override
print - Print out the internal state of the pass.
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
ScalarEvolution & getSE()
void verifyAnalysis() const override
verifyAnalysis() - This member can be implemented by a analysis pass to check state of analysis infor...
ScalarEvolutionWrapperPass()
const ScalarEvolution & getSE() const
bool operator==(const FoldID &RHS) const
FoldID(SCEVTypes C, const SCEV *Op, const Type *Ty)
unsigned computeHash() const
static LoopGuards collect(const Loop *L, ScalarEvolution &SE)
Collect rewrite map for loop guards for loop L, together with flags indicating if NUW and NSW can be ...
const SCEV * rewrite(const SCEV *Expr) const
Try to apply the collected loop guards to Expr.
The main scalar evolution driver.
const SCEV * getConstantMaxBackedgeTakenCount(const Loop *L)
When successful, this returns a SCEVConstant that is greater than or equal to (i.e.
static bool hasFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags TestFlags)
const DataLayout & getDataLayout() const
Return the DataLayout associated with the module this SCEV instance is operating on.
bool isKnownNonNegative(const SCEV *S)
Test if the given expression is known to be non-negative.
bool isKnownOnEveryIteration(CmpPredicate Pred, const SCEVAddRecExpr *LHS, const SCEV *RHS)
Test if the condition described by Pred, LHS, RHS is known to be true on every iteration of the loop ...
const SCEV * getNegativeSCEV(const SCEV *V, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap)
Return the SCEV object corresponding to -V.
std::optional< LoopInvariantPredicate > getLoopInvariantExitCondDuringFirstIterationsImpl(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L, const Instruction *CtxI, const SCEV *MaxIter)
const SCEV * getSMaxExpr(const SCEV *LHS, const SCEV *RHS)
const SCEV * getUDivCeilSCEV(const SCEV *N, const SCEV *D)
Compute ceil(N / D).
const SCEV * getGEPExpr(GEPOperator *GEP, const SmallVectorImpl< const SCEV * > &IndexExprs)
Returns an expression for a GEP.
std::optional< LoopInvariantPredicate > getLoopInvariantExitCondDuringFirstIterations(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L, const Instruction *CtxI, const SCEV *MaxIter)
If the result of the predicate LHS Pred RHS is loop invariant with respect to L at given Context duri...
Type * getWiderType(Type *Ty1, Type *Ty2) const
const SCEV * getAbsExpr(const SCEV *Op, bool IsNSW)
bool isKnownNonPositive(const SCEV *S)
Test if the given expression is known to be non-positive.
const SCEV * getURemExpr(const SCEV *LHS, const SCEV *RHS)
Represents an unsigned remainder expression based on unsigned division.
APInt getConstantMultiple(const SCEV *S)
Returns the max constant multiple of S.
bool isKnownNegative(const SCEV *S)
Test if the given expression is known to be negative.
const SCEV * getPredicatedConstantMaxBackedgeTakenCount(const Loop *L, SmallVectorImpl< const SCEVPredicate * > &Predicates)
Similar to getConstantMaxBackedgeTakenCount, except it will add a set of SCEV predicates to Predicate...
const SCEV * removePointerBase(const SCEV *S)
Compute an expression equivalent to S - getPointerBase(S).
bool isLoopEntryGuardedByCond(const Loop *L, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether entry to the loop is protected by a conditional between LHS and RHS.
bool isKnownNonZero(const SCEV *S)
Test if the given expression is known to be non-zero.
const SCEV * getSCEVAtScope(const SCEV *S, const Loop *L)
Return a SCEV expression for the specified value at the specified scope in the program.
const SCEV * getSMinExpr(const SCEV *LHS, const SCEV *RHS)
const SCEV * getBackedgeTakenCount(const Loop *L, ExitCountKind Kind=Exact)
If the specified loop has a predictable backedge-taken count, return it, otherwise return a SCEVCould...
const SCEV * getUMaxExpr(const SCEV *LHS, const SCEV *RHS)
void setNoWrapFlags(SCEVAddRecExpr *AddRec, SCEV::NoWrapFlags Flags)
Update no-wrap flags of an AddRec.
const SCEV * getAddExpr(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
const SCEV * getUMaxFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS)
Promote the operands to the wider of the types using zero-extension, and then perform a umax operatio...
const SCEV * getZero(Type *Ty)
Return a SCEV for the constant 0 of a specific type.
bool willNotOverflow(Instruction::BinaryOps BinOp, bool Signed, const SCEV *LHS, const SCEV *RHS, const Instruction *CtxI=nullptr)
Is operation BinOp between LHS and RHS provably does not have a signed/unsigned overflow (Signed)?...
ExitLimit computeExitLimitFromCond(const Loop *L, Value *ExitCond, bool ExitIfTrue, bool ControlsOnlyExit, bool AllowPredicates=false)
Compute the number of times the backedge of the specified loop will execute if its exit condition wer...
const SCEV * getZeroExtendExprImpl(const SCEV *Op, Type *Ty, unsigned Depth=0)
const SCEVPredicate * getEqualPredicate(const SCEV *LHS, const SCEV *RHS)
unsigned getSmallConstantTripMultiple(const Loop *L, const SCEV *ExitCount)
Returns the largest constant divisor of the trip count as a normal unsigned value,...
uint64_t getTypeSizeInBits(Type *Ty) const
Return the size in bits of the specified type, for which isSCEVable must return true.
const SCEV * getConstant(ConstantInt *V)
const SCEV * getPredicatedBackedgeTakenCount(const Loop *L, SmallVectorImpl< const SCEVPredicate * > &Predicates)
Similar to getBackedgeTakenCount, except it will add a set of SCEV predicates to Predicates that are ...
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
ConstantRange getSignedRange(const SCEV *S)
Determine the signed range for a particular SCEV.
const SCEV * getNoopOrSignExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
bool loopHasNoAbnormalExits(const Loop *L)
Return true if the loop has no abnormal exits.
const SCEV * getTripCountFromExitCount(const SCEV *ExitCount)
A version of getTripCountFromExitCount below which always picks an evaluation type which can not resu...
const SCEV * getOne(Type *Ty)
Return a SCEV for the constant 1 of a specific type.
const SCEV * getTruncateOrNoop(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
const SCEV * getCastExpr(SCEVTypes Kind, const SCEV *Op, Type *Ty)
const SCEV * getSequentialMinMaxExpr(SCEVTypes Kind, SmallVectorImpl< const SCEV * > &Operands)
const SCEV * getLosslessPtrToIntExpr(const SCEV *Op, unsigned Depth=0)
std::optional< bool > evaluatePredicateAt(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Instruction *CtxI)
Check whether the condition described by Pred, LHS, and RHS is true or false in the given Context.
unsigned getSmallConstantMaxTripCount(const Loop *L, SmallVectorImpl< const SCEVPredicate * > *Predicates=nullptr)
Returns the upper bound of the loop trip count as a normal unsigned value.
const SCEV * getPtrToIntExpr(const SCEV *Op, Type *Ty)
const SCEV * getMulExpr(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
bool isBackedgeTakenCountMaxOrZero(const Loop *L)
Return true if the backedge taken count is either the value returned by getConstantMaxBackedgeTakenCo...
void forgetLoop(const Loop *L)
This method should be called by the client when it has changed a loop in a way that may effect Scalar...
bool isLoopInvariant(const SCEV *S, const Loop *L)
Return true if the value of the given SCEV is unchanging in the specified loop.
bool isKnownPositive(const SCEV *S)
Test if the given expression is known to be positive.
APInt getUnsignedRangeMin(const SCEV *S)
Determine the min of the unsigned range for a particular SCEV.
bool SimplifyICmpOperands(CmpPredicate &Pred, const SCEV *&LHS, const SCEV *&RHS, unsigned Depth=0)
Simplify LHS and RHS in a comparison with predicate Pred.
const SCEV * getOffsetOfExpr(Type *IntTy, StructType *STy, unsigned FieldNo)
Return an expression for offsetof on the given field with type IntTy.
LoopDisposition getLoopDisposition(const SCEV *S, const Loop *L)
Return the "disposition" of the given SCEV with respect to the given loop.
bool containsAddRecurrence(const SCEV *S)
Return true if the SCEV is a scAddRecExpr or it contains scAddRecExpr.
const SCEV * getSignExtendExprImpl(const SCEV *Op, Type *Ty, unsigned Depth=0)
const SCEV * getAddRecExpr(const SCEV *Start, const SCEV *Step, const Loop *L, SCEV::NoWrapFlags Flags)
Get an add recurrence expression for the specified loop.
bool hasOperand(const SCEV *S, const SCEV *Op) const
Test whether the given SCEV has Op as a direct or indirect operand.
const SCEV * getUDivExpr(const SCEV *LHS, const SCEV *RHS)
Get a canonical unsigned division expression, or something simpler if possible.
const SCEV * getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
bool isSCEVable(Type *Ty) const
Test if values of the given type are analyzable within the SCEV framework.
Type * getEffectiveSCEVType(Type *Ty) const
Return a type with the same bitwidth as the given type and which represents how SCEV will treat the g...
const SCEV * getAddRecExpr(const SmallVectorImpl< const SCEV * > &Operands, const Loop *L, SCEV::NoWrapFlags Flags)
const SCEVPredicate * getComparePredicate(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
const SCEV * getNotSCEV(const SCEV *V)
Return the SCEV object corresponding to ~V.
std::optional< LoopInvariantPredicate > getLoopInvariantPredicate(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L, const Instruction *CtxI=nullptr)
If the result of the predicate LHS Pred RHS is loop invariant with respect to L, return a LoopInvaria...
bool instructionCouldExistWithOperands(const SCEV *A, const SCEV *B)
Return true if there exists a point in the program at which both A and B could be operands to the sam...
ConstantRange getUnsignedRange(const SCEV *S)
Determine the unsigned range for a particular SCEV.
uint32_t getMinTrailingZeros(const SCEV *S)
Determine the minimum number of zero bits that S is guaranteed to end in (at every loop iteration).
void print(raw_ostream &OS) const
const SCEV * getUMinExpr(const SCEV *LHS, const SCEV *RHS, bool Sequential=false)
const SCEV * getPredicatedExitCount(const Loop *L, const BasicBlock *ExitingBlock, SmallVectorImpl< const SCEVPredicate * > *Predicates, ExitCountKind Kind=Exact)
Same as above except this uses the predicated backedge taken info and may require predicates.
static SCEV::NoWrapFlags clearFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OffFlags)
void forgetTopmostLoop(const Loop *L)
friend class ScalarEvolutionsTest
void forgetValue(Value *V)
This method should be called by the client when it has changed a value in a way that may effect its v...
APInt getSignedRangeMin(const SCEV *S)
Determine the min of the signed range for a particular SCEV.
const SCEV * getMulExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
const SCEV * getNoopOrAnyExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
void forgetBlockAndLoopDispositions(Value *V=nullptr)
Called when the client has changed the disposition of values in a loop or block.
const SCEV * getTruncateExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
MonotonicPredicateType
A predicate is said to be monotonically increasing if may go from being false to being true as the lo...
@ MonotonicallyDecreasing
@ MonotonicallyIncreasing
const SCEV * getStoreSizeOfExpr(Type *IntTy, Type *StoreTy)
Return an expression for the store size of StoreTy that is type IntTy.
const SCEVPredicate * getWrapPredicate(const SCEVAddRecExpr *AR, SCEVWrapPredicate::IncrementWrapFlags AddedFlags)
bool isLoopBackedgeGuardedByCond(const Loop *L, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether the backedge of the loop is protected by a conditional between LHS and RHS.
const SCEV * getMinusSCEV(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Return LHS-RHS.
APInt getNonZeroConstantMultiple(const SCEV *S)
const SCEV * getMinusOne(Type *Ty)
Return a SCEV for the constant -1 of a specific type.
static SCEV::NoWrapFlags setFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OnFlags)
bool hasLoopInvariantBackedgeTakenCount(const Loop *L)
Return true if the specified loop has an analyzable loop-invariant backedge-taken count.
BlockDisposition getBlockDisposition(const SCEV *S, const BasicBlock *BB)
Return the "disposition" of the given SCEV with respect to the given block.
const SCEV * getNoopOrZeroExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
const SCEV * getUMinFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS, bool Sequential=false)
Promote the operands to the wider of the types using zero-extension, and then perform a umin operatio...
bool loopIsFiniteByAssumption(const Loop *L)
Return true if this loop is finite by assumption.
const SCEV * getExistingSCEV(Value *V)
Return an existing SCEV for V if there is one, otherwise return nullptr.
LoopDisposition
An enum describing the relationship between a SCEV and a loop.
@ LoopComputable
The SCEV varies predictably with the loop.
@ LoopVariant
The SCEV is loop-variant (unknown).
@ LoopInvariant
The SCEV is loop-invariant.
friend class SCEVCallbackVH
const SCEV * getAnyExtendExpr(const SCEV *Op, Type *Ty)
getAnyExtendExpr - Return a SCEV for the given operand extended with unspecified bits out to the give...
bool isKnownToBeAPowerOfTwo(const SCEV *S, bool OrZero=false, bool OrNegative=false)
Test if the given expression is known to be a power of 2.
std::optional< SCEV::NoWrapFlags > getStrengthenedNoWrapFlagsFromBinOp(const OverflowingBinaryOperator *OBO)
Parse NSW/NUW flags from add/sub/mul IR binary operation Op into SCEV no-wrap flags,...
void forgetLcssaPhiWithNewPredecessor(Loop *L, PHINode *V)
Forget LCSSA phi node V of loop L to which a new predecessor was added, such that it may no longer be...
bool containsUndefs(const SCEV *S) const
Return true if the SCEV expression contains an undef value.
std::optional< MonotonicPredicateType > getMonotonicPredicateType(const SCEVAddRecExpr *LHS, ICmpInst::Predicate Pred)
If, for all loop invariant X, the predicate "LHS `Pred` X" is monotonically increasing or decreasing,...
const SCEV * getCouldNotCompute()
bool isAvailableAtLoopEntry(const SCEV *S, const Loop *L)
Determine if the SCEV can be evaluated at loop's entry.
BlockDisposition
An enum describing the relationship between a SCEV and a basic block.
@ DominatesBlock
The SCEV dominates the block.
@ ProperlyDominatesBlock
The SCEV properly dominates the block.
@ DoesNotDominateBlock
The SCEV does not dominate the block.
const SCEV * getExitCount(const Loop *L, const BasicBlock *ExitingBlock, ExitCountKind Kind=Exact)
Return the number of times the backedge executes before the given exit would be taken; if not exactly...
const SCEV * getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
void getPoisonGeneratingValues(SmallPtrSetImpl< const Value * > &Result, const SCEV *S)
Return the set of Values that, if poison, will definitively result in S being poison as well.
void forgetLoopDispositions()
Called when the client has changed the disposition of values in this loop.
const SCEV * getVScale(Type *Ty)
unsigned getSmallConstantTripCount(const Loop *L)
Returns the exact trip count of the loop if we can compute it, and the result is a small constant.
bool hasComputableLoopEvolution(const SCEV *S, const Loop *L)
Return true if the given SCEV changes value in a known way in the specified loop.
const SCEV * getPointerBase(const SCEV *V)
Transitively follow the chain of pointer-type operands until reaching a SCEV that does not have a sin...
const SCEV * getPowerOfTwo(Type *Ty, unsigned Power)
Return a SCEV for the constant Power of two.
const SCEV * getMinMaxExpr(SCEVTypes Kind, SmallVectorImpl< const SCEV * > &Operands)
bool dominates(const SCEV *S, const BasicBlock *BB)
Return true if elements that makes up the given SCEV dominate the specified basic block.
APInt getUnsignedRangeMax(const SCEV *S)
Determine the max of the unsigned range for a particular SCEV.
ExitCountKind
The terms "backedge taken count" and "exit count" are used interchangeably to refer to the number of ...
@ SymbolicMaximum
An expression which provides an upper bound on the exact trip count.
@ ConstantMaximum
A constant which provides an upper bound on the exact trip count.
@ Exact
An expression exactly describing the number of times the backedge has executed when a loop is exited.
const SCEV * applyLoopGuards(const SCEV *Expr, const Loop *L)
Try to apply information from loop guards for L to Expr.
const SCEV * getMulExpr(SmallVectorImpl< const SCEV * > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical multiply expression, or something simpler if possible.
const SCEVAddRecExpr * convertSCEVToAddRecWithPredicates(const SCEV *S, const Loop *L, SmallVectorImpl< const SCEVPredicate * > &Preds)
Tries to convert the S expression to an AddRec expression, adding additional predicates to Preds as r...
const SCEV * getElementSize(Instruction *Inst)
Return the size of an element read or written by Inst.
const SCEV * getSizeOfExpr(Type *IntTy, TypeSize Size)
Return an expression for a TypeSize.
std::optional< bool > evaluatePredicate(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Check whether the condition described by Pred, LHS, and RHS is true or false.
const SCEV * getUnknown(Value *V)
std::optional< std::pair< const SCEV *, SmallVector< const SCEVPredicate *, 3 > > > createAddRecFromPHIWithCasts(const SCEVUnknown *SymbolicPHI)
Checks if SymbolicPHI can be rewritten as an AddRecExpr under some Predicates.
const SCEV * getTruncateOrZeroExtend(const SCEV *V, Type *Ty, unsigned Depth=0)
Return a SCEV corresponding to a conversion of the input value to the specified type.
const SCEV * getElementCount(Type *Ty, ElementCount EC)
static SCEV::NoWrapFlags maskFlags(SCEV::NoWrapFlags Flags, int Mask)
Convenient NoWrapFlags manipulation that hides enum casts and is visible in the ScalarEvolution name ...
std::optional< APInt > computeConstantDifference(const SCEV *LHS, const SCEV *RHS)
Compute LHS - RHS and returns the result as an APInt if it is a constant, and std::nullopt if it isn'...
bool properlyDominates(const SCEV *S, const BasicBlock *BB)
Return true if elements that makes up the given SCEV properly dominate the specified basic block.
const SCEV * getAddExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
const SCEV * rewriteUsingPredicate(const SCEV *S, const Loop *L, const SCEVPredicate &A)
Re-writes the SCEV according to the Predicates in A.
std::pair< const SCEV *, const SCEV * > SplitIntoInitAndPostInc(const Loop *L, const SCEV *S)
Splits SCEV expression S into two SCEVs.
bool canReuseInstruction(const SCEV *S, Instruction *I, SmallVectorImpl< Instruction * > &DropPoisonGeneratingInsts)
Check whether it is poison-safe to represent the expression S using the instruction I.
bool isKnownPredicateAt(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS, const Instruction *CtxI)
Test if the given expression is known to satisfy the condition described by Pred, LHS,...
const SCEV * getPredicatedSymbolicMaxBackedgeTakenCount(const Loop *L, SmallVectorImpl< const SCEVPredicate * > &Predicates)
Similar to getSymbolicMaxBackedgeTakenCount, except it will add a set of SCEV predicates to Predicate...
const SCEV * getUDivExactExpr(const SCEV *LHS, const SCEV *RHS)
Get a canonical unsigned division expression, or something simpler if possible.
void registerUser(const SCEV *User, ArrayRef< const SCEV * > Ops)
Notify this ScalarEvolution that User directly uses SCEVs in Ops.
const SCEV * getAddExpr(SmallVectorImpl< const SCEV * > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical add expression, or something simpler if possible.
bool isBasicBlockEntryGuardedByCond(const BasicBlock *BB, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether entry to the basic block is protected by a conditional between LHS and RHS.
const SCEV * getTruncateOrSignExtend(const SCEV *V, Type *Ty, unsigned Depth=0)
Return a SCEV corresponding to a conversion of the input value to the specified type.
bool containsErasedValue(const SCEV *S) const
Return true if the SCEV expression contains a Value that has been optimised out and is now a nullptr.
bool isKnownPredicate(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Test if the given expression is known to satisfy the condition described by Pred, LHS,...
bool isKnownViaInduction(CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
We'd like to check the predicate on every iteration of the most dominated loop between loops used in ...
const SCEV * getSymbolicMaxBackedgeTakenCount(const Loop *L)
When successful, this returns a SCEV that is greater than or equal to (i.e.
APInt getSignedRangeMax(const SCEV *S)
Determine the max of the signed range for a particular SCEV.
LLVMContext & getContext() const
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
A SetVector that performs no allocations if smaller than a certain size.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Class to represent struct types.
Provides information about what library functions are available for the current target.
The instances of the Type class are immutable: once they are created, they are never changed.
LLVM Value Representation.
This class implements an extremely fast bulk output stream that can only output to a stream.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
@ BasicBlock
Various leaf nodes.
unsigned combineHashValue(unsigned a, unsigned b)
Simplistic combination of 32-bit hash values into 32-bit hash values.
This is an optimization pass for GlobalISel generic memory operations.
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
BumpPtrAllocatorImpl BumpPtrAllocator
The standard BumpPtrAllocator which just uses the default template parameters.
DWARFExpression::Operation Op
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
constexpr unsigned BitWidth
A CRTP mix-in that provides informational APIs needed for analysis passes.
A special type used by analysis passes to provide an address that identifies that particular analysis...
DefaultFoldingSetTrait - This class provides default implementations for FoldingSetTrait implementati...
static unsigned getHashValue(const ScalarEvolution::FoldID &Val)
static ScalarEvolution::FoldID getTombstoneKey()
static ScalarEvolution::FoldID getEmptyKey()
static bool isEqual(const ScalarEvolution::FoldID &LHS, const ScalarEvolution::FoldID &RHS)
An information struct used to provide DenseMap with the various necessary components for a given valu...
static void Profile(const SCEVPredicate &X, FoldingSetNodeID &ID)
static bool Equals(const SCEVPredicate &X, const FoldingSetNodeID &ID, unsigned IDHash, FoldingSetNodeID &TempID)
static unsigned ComputeHash(const SCEVPredicate &X, FoldingSetNodeID &TempID)
static bool Equals(const SCEV &X, const FoldingSetNodeID &ID, unsigned IDHash, FoldingSetNodeID &TempID)
static unsigned ComputeHash(const SCEV &X, FoldingSetNodeID &TempID)
static void Profile(const SCEV &X, FoldingSetNodeID &ID)
FoldingSetTrait - This trait class is used to define behavior of how to "profile" (in the FoldingSet ...
A CRTP mix-in to automatically provide informational APIs needed for passes.
An object of this class is returned by queries that could not be answered.
static bool classof(const SCEV *S)
Methods for support type inquiry through isa, cast, and dyn_cast:
Information about the number of loop iterations for which a loop exit's branch condition evaluates to...
bool hasAnyInfo() const
Test whether this ExitLimit contains any computed information, or whether it's all SCEVCouldNotComput...
const SCEV * ExactNotTaken
const SCEV * SymbolicMaxNotTaken
SmallVector< const SCEVPredicate *, 4 > Predicates
A vector of predicate guards for this ExitLimit.
bool hasFullInfo() const
Test whether this ExitLimit contains all information.
const SCEV * ConstantMaxNotTaken
LoopInvariantPredicate(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
