Coverage Report

Created: 2019-07-24 05:18

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