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