1 | //===- llvm/Analysis/ScalarEvolution.h - Scalar Evolution -------*- C++ -*-===// |
---|---|

2 | // |

3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |

4 | // See https://llvm.org/LICENSE.txt for license information. |

5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |

6 | // |

7 | //===----------------------------------------------------------------------===// |

8 | // |

9 | // The ScalarEvolution class is an LLVM pass which can be used to analyze and |

10 | // categorize scalar expressions in loops. It specializes in recognizing |

11 | // general induction variables, representing them with the abstract and opaque |

12 | // SCEV class. Given this analysis, trip counts of loops and other important |

13 | // properties can be obtained. |

14 | // |

15 | // This analysis is primarily useful for induction variable substitution and |

16 | // strength reduction. |

17 | // |

18 | //===----------------------------------------------------------------------===// |

19 | |

20 | #ifndef LLVM_ANALYSIS_SCALAREVOLUTION_H |

21 | #define LLVM_ANALYSIS_SCALAREVOLUTION_H |

22 | |

23 | #include "llvm/ADT/APInt.h" |

24 | #include "llvm/ADT/ArrayRef.h" |

25 | #include "llvm/ADT/DenseMap.h" |

26 | #include "llvm/ADT/DenseMapInfo.h" |

27 | #include "llvm/ADT/FoldingSet.h" |

28 | #include "llvm/ADT/Optional.h" |

29 | #include "llvm/ADT/PointerIntPair.h" |

30 | #include "llvm/ADT/SetVector.h" |

31 | #include "llvm/ADT/SmallPtrSet.h" |

32 | #include "llvm/ADT/SmallVector.h" |

33 | #include "llvm/IR/ConstantRange.h" |

34 | #include "llvm/IR/InstrTypes.h" |

35 | #include "llvm/IR/Instructions.h" |

36 | #include "llvm/IR/PassManager.h" |

37 | #include "llvm/IR/ValueHandle.h" |

38 | #include "llvm/IR/ValueMap.h" |

39 | #include "llvm/Pass.h" |

40 | #include <cassert> |

41 | #include <cstdint> |

42 | #include <memory> |

43 | #include <utility> |

44 | |

45 | namespace llvm { |

46 | |

47 | class OverflowingBinaryOperator; |

48 | class AssumptionCache; |

49 | class BasicBlock; |

50 | class Constant; |

51 | class ConstantInt; |

52 | class DataLayout; |

53 | class DominatorTree; |

54 | class Function; |

55 | class GEPOperator; |

56 | class Instruction; |

57 | class LLVMContext; |

58 | class Loop; |

59 | class LoopInfo; |

60 | class raw_ostream; |

61 | class ScalarEvolution; |

62 | class SCEVAddRecExpr; |

63 | class SCEVUnknown; |

64 | class StructType; |

65 | class TargetLibraryInfo; |

66 | class Type; |

67 | class Value; |

68 | enum SCEVTypes : unsigned short; |

69 | |

70 | extern bool VerifySCEV; |

71 | |

72 | /// This class represents an analyzed expression in the program. These are |

73 | /// opaque objects that the client is not allowed to do much with directly. |

74 | /// |

75 | class SCEV : public FoldingSetNode { |

76 | friend struct FoldingSetTrait<SCEV>; |

77 | |

78 | /// A reference to an Interned FoldingSetNodeID for this node. The |

79 | /// ScalarEvolution's BumpPtrAllocator holds the data. |

80 | FoldingSetNodeIDRef FastID; |

81 | |

82 | // The SCEV baseclass this node corresponds to |

83 | const SCEVTypes SCEVType; |

84 | |

85 | protected: |

86 | // Estimated complexity of this node's expression tree size. |

87 | const unsigned short ExpressionSize; |

88 | |

89 | /// This field is initialized to zero and may be used in subclasses to store |

90 | /// miscellaneous information. |

91 | unsigned short SubclassData = 0; |

92 | |

93 | public: |

94 | /// NoWrapFlags are bitfield indices into SubclassData. |

95 | /// |

96 | /// Add and Mul expressions may have no-unsigned-wrap <NUW> or |

97 | /// no-signed-wrap <NSW> properties, which are derived from the IR |

98 | /// operator. NSW is a misnomer that we use to mean no signed overflow or |

99 | /// underflow. |

100 | /// |

101 | /// AddRec expressions may have a no-self-wraparound <NW> property if, in |

102 | /// the integer domain, abs(step) * max-iteration(loop) <= |

103 | /// unsigned-max(bitwidth). This means that the recurrence will never reach |

104 | /// its start value if the step is non-zero. Computing the same value on |

105 | /// each iteration is not considered wrapping, and recurrences with step = 0 |

106 | /// are trivially <NW>. <NW> is independent of the sign of step and the |

107 | /// value the add recurrence starts with. |

108 | /// |

109 | /// Note that NUW and NSW are also valid properties of a recurrence, and |

110 | /// either implies NW. For convenience, NW will be set for a recurrence |

111 | /// whenever either NUW or NSW are set. |

112 | /// |

113 | /// We require that the flag on a SCEV apply to the entire scope in which |

114 | /// that SCEV is defined. A SCEV's scope is set of locations dominated by |

115 | /// a defining location, which is in turn described by the following rules: |

116 | /// * A SCEVUnknown is at the point of definition of the Value. |

117 | /// * A SCEVConstant is defined at all points. |

118 | /// * A SCEVAddRec is defined starting with the header of the associated |

119 | /// loop. |

120 | /// * All other SCEVs are defined at the earlest point all operands are |

121 | /// defined. |

122 | /// |

123 | /// The above rules describe a maximally hoisted form (without regards to |

124 | /// potential control dependence). A SCEV is defined anywhere a |

125 | /// corresponding instruction could be defined in said maximally hoisted |

126 | /// form. Note that SCEVUDivExpr (currently the only expression type which |

127 | /// can trap) can be defined per these rules in regions where it would trap |

128 | /// at runtime. A SCEV being defined does not require the existence of any |

129 | /// instruction within the defined scope. |

130 | enum NoWrapFlags { |

131 | FlagAnyWrap = 0, // No guarantee. |

132 | FlagNW = (1 << 0), // No self-wrap. |

133 | FlagNUW = (1 << 1), // No unsigned wrap. |

134 | FlagNSW = (1 << 2), // No signed wrap. |

135 | NoWrapMask = (1 << 3) - 1 |

136 | }; |

137 | |

138 | explicit SCEV(const FoldingSetNodeIDRef ID, SCEVTypes SCEVTy, |

139 | unsigned short ExpressionSize) |

140 | : FastID(ID), SCEVType(SCEVTy), ExpressionSize(ExpressionSize) {} |

141 | SCEV(const SCEV &) = delete; |

142 | SCEV &operator=(const SCEV &) = delete; |

143 | |

144 | SCEVTypes getSCEVType() const { return SCEVType; } |

145 | |

146 | /// Return the LLVM type of this SCEV expression. |

147 | Type *getType() const; |

148 | |

149 | /// Return true if the expression is a constant zero. |

150 | bool isZero() const; |

151 | |

152 | /// Return true if the expression is a constant one. |

153 | bool isOne() const; |

154 | |

155 | /// Return true if the expression is a constant all-ones value. |

156 | bool isAllOnesValue() const; |

157 | |

158 | /// Return true if the specified scev is negated, but not a constant. |

159 | bool isNonConstantNegative() const; |

160 | |

161 | // Returns estimated size of the mathematical expression represented by this |

162 | // SCEV. The rules of its calculation are following: |

163 | // 1) Size of a SCEV without operands (like constants and SCEVUnknown) is 1; |

164 | // 2) Size SCEV with operands Op1, Op2, ..., OpN is calculated by formula: |

165 | // (1 + Size(Op1) + ... + Size(OpN)). |

166 | // This value gives us an estimation of time we need to traverse through this |

167 | // SCEV and all its operands recursively. We may use it to avoid performing |

168 | // heavy transformations on SCEVs of excessive size for sake of saving the |

169 | // compilation time. |

170 | unsigned short getExpressionSize() const { |

171 | return ExpressionSize; |

172 | } |

173 | |

174 | /// Print out the internal representation of this scalar to the specified |

175 | /// stream. This should really only be used for debugging purposes. |

176 | void print(raw_ostream &OS) const; |

177 | |

178 | /// This method is used for debugging. |

179 | void dump() const; |

180 | }; |

181 | |

182 | // Specialize FoldingSetTrait for SCEV to avoid needing to compute |

183 | // temporary FoldingSetNodeID values. |

184 | template <> struct FoldingSetTrait<SCEV> : DefaultFoldingSetTrait<SCEV> { |

185 | static void Profile(const SCEV &X, FoldingSetNodeID &ID) { ID = X.FastID; } |

186 | |

187 | static bool Equals(const SCEV &X, const FoldingSetNodeID &ID, unsigned IDHash, |

188 | FoldingSetNodeID &TempID) { |

189 | return ID == X.FastID; |

190 | } |

191 | |

192 | static unsigned ComputeHash(const SCEV &X, FoldingSetNodeID &TempID) { |

193 | return X.FastID.ComputeHash(); |

194 | } |

195 | }; |

196 | |

197 | inline raw_ostream &operator<<(raw_ostream &OS, const SCEV &S) { |

198 | S.print(OS); |

199 | return OS; |

200 | } |

201 | |

202 | /// An object of this class is returned by queries that could not be answered. |

203 | /// For example, if you ask for the number of iterations of a linked-list |

204 | /// traversal loop, you will get one of these. None of the standard SCEV |

205 | /// operations are valid on this class, it is just a marker. |

206 | struct SCEVCouldNotCompute : public SCEV { |

207 | SCEVCouldNotCompute(); |

208 | |

209 | /// Methods for support type inquiry through isa, cast, and dyn_cast: |

210 | static bool classof(const SCEV *S); |

211 | }; |

212 | |

213 | /// This class represents an assumption made using SCEV expressions which can |

214 | /// be checked at run-time. |

215 | class SCEVPredicate : public FoldingSetNode { |

216 | friend struct FoldingSetTrait<SCEVPredicate>; |

217 | |

218 | /// A reference to an Interned FoldingSetNodeID for this node. The |

219 | /// ScalarEvolution's BumpPtrAllocator holds the data. |

220 | FoldingSetNodeIDRef FastID; |

221 | |

222 | public: |

223 | enum SCEVPredicateKind { P_Union, P_Compare, P_Wrap }; |

224 | |

225 | protected: |

226 | SCEVPredicateKind Kind; |

227 | ~SCEVPredicate() = default; |

228 | SCEVPredicate(const SCEVPredicate &) = default; |

229 | SCEVPredicate &operator=(const SCEVPredicate &) = default; |

230 | |

231 | public: |

232 | SCEVPredicate(const FoldingSetNodeIDRef ID, SCEVPredicateKind Kind); |

233 | |

234 | SCEVPredicateKind getKind() const { return Kind; } |

235 | |

236 | /// Returns the estimated complexity of this predicate. This is roughly |

237 | /// measured in the number of run-time checks required. |

238 | virtual unsigned getComplexity() const { return 1; } |

239 | |

240 | /// Returns true if the predicate is always true. This means that no |

241 | /// assumptions were made and nothing needs to be checked at run-time. |

242 | virtual bool isAlwaysTrue() const = 0; |

243 | |

244 | /// Returns true if this predicate implies \p N. |

245 | virtual bool implies(const SCEVPredicate *N) const = 0; |

246 | |

247 | /// Prints a textual representation of this predicate with an indentation of |

248 | /// \p Depth. |

249 | virtual void print(raw_ostream &OS, unsigned Depth = 0) const = 0; |

250 | }; |

251 | |

252 | inline raw_ostream &operator<<(raw_ostream &OS, const SCEVPredicate &P) { |

253 | P.print(OS); |

254 | return OS; |

255 | } |

256 | |

257 | // Specialize FoldingSetTrait for SCEVPredicate to avoid needing to compute |

258 | // temporary FoldingSetNodeID values. |

259 | template <> |

260 | struct FoldingSetTrait<SCEVPredicate> : DefaultFoldingSetTrait<SCEVPredicate> { |

261 | static void Profile(const SCEVPredicate &X, FoldingSetNodeID &ID) { |

262 | ID = X.FastID; |

263 | } |

264 | |

265 | static bool Equals(const SCEVPredicate &X, const FoldingSetNodeID &ID, |

266 | unsigned IDHash, FoldingSetNodeID &TempID) { |

267 | return ID == X.FastID; |

268 | } |

269 | |

270 | static unsigned ComputeHash(const SCEVPredicate &X, |

271 | FoldingSetNodeID &TempID) { |

272 | return X.FastID.ComputeHash(); |

273 | } |

274 | }; |

275 | |

276 | /// This class represents an assumption that the expression LHS Pred RHS |

277 | /// evaluates to true, and this can be checked at run-time. |

278 | class SCEVComparePredicate final : public SCEVPredicate { |

279 | /// We assume that LHS Pred RHS is true. |

280 | const ICmpInst::Predicate Pred; |

281 | const SCEV *LHS; |

282 | const SCEV *RHS; |

283 | |

284 | public: |

285 | SCEVComparePredicate(const FoldingSetNodeIDRef ID, |

286 | const ICmpInst::Predicate Pred, |

287 | const SCEV *LHS, const SCEV *RHS); |

288 | |

289 | /// Implementation of the SCEVPredicate interface |

290 | bool implies(const SCEVPredicate *N) const override; |

291 | void print(raw_ostream &OS, unsigned Depth = 0) const override; |

292 | bool isAlwaysTrue() const override; |

293 | |

294 | ICmpInst::Predicate getPredicate() const { return Pred; } |

295 | |

296 | /// Returns the left hand side of the predicate. |

297 | const SCEV *getLHS() const { return LHS; } |

298 | |

299 | /// Returns the right hand side of the predicate. |

300 | const SCEV *getRHS() const { return RHS; } |

301 | |

302 | /// Methods for support type inquiry through isa, cast, and dyn_cast: |

303 | static bool classof(const SCEVPredicate *P) { |

304 | return P->getKind() == P_Compare; |

305 | } |

306 | }; |

307 | |

308 | /// This class represents an assumption made on an AddRec expression. Given an |

309 | /// affine AddRec expression {a,+,b}, we assume that it has the nssw or nusw |

310 | /// flags (defined below) in the first X iterations of the loop, where X is a |

311 | /// SCEV expression returned by getPredicatedBackedgeTakenCount). |

312 | /// |

313 | /// Note that this does not imply that X is equal to the backedge taken |

314 | /// count. This means that if we have a nusw predicate for i32 {0,+,1} with a |

315 | /// predicated backedge taken count of X, we only guarantee that {0,+,1} has |

316 | /// nusw in the first X iterations. {0,+,1} may still wrap in the loop if we |

317 | /// have more than X iterations. |

318 | class SCEVWrapPredicate final : public SCEVPredicate { |

319 | public: |

320 | /// Similar to SCEV::NoWrapFlags, but with slightly different semantics |

321 | /// for FlagNUSW. The increment is considered to be signed, and a + b |

322 | /// (where b is the increment) is considered to wrap if: |

323 | /// zext(a + b) != zext(a) + sext(b) |

324 | /// |

325 | /// If Signed is a function that takes an n-bit tuple and maps to the |

326 | /// integer domain as the tuples value interpreted as twos complement, |

327 | /// and Unsigned a function that takes an n-bit tuple and maps to the |

328 | /// integer domain as as the base two value of input tuple, then a + b |

329 | /// has IncrementNUSW iff: |

330 | /// |

331 | /// 0 <= Unsigned(a) + Signed(b) < 2^n |

332 | /// |

333 | /// The IncrementNSSW flag has identical semantics with SCEV::FlagNSW. |

334 | /// |

335 | /// Note that the IncrementNUSW flag is not commutative: if base + inc |

336 | /// has IncrementNUSW, then inc + base doesn't neccessarily have this |

337 | /// property. The reason for this is that this is used for sign/zero |

338 | /// extending affine AddRec SCEV expressions when a SCEVWrapPredicate is |

339 | /// assumed. A {base,+,inc} expression is already non-commutative with |

340 | /// regards to base and inc, since it is interpreted as: |

341 | /// (((base + inc) + inc) + inc) ... |

342 | enum IncrementWrapFlags { |

343 | IncrementAnyWrap = 0, // No guarantee. |

344 | IncrementNUSW = (1 << 0), // No unsigned with signed increment wrap. |

345 | IncrementNSSW = (1 << 1), // No signed with signed increment wrap |

346 | // (equivalent with SCEV::NSW) |

347 | IncrementNoWrapMask = (1 << 2) - 1 |

348 | }; |

349 | |

350 | /// Convenient IncrementWrapFlags manipulation methods. |

351 | [[nodiscard]] static SCEVWrapPredicate::IncrementWrapFlags |

352 | clearFlags(SCEVWrapPredicate::IncrementWrapFlags Flags, |

353 | SCEVWrapPredicate::IncrementWrapFlags OffFlags) { |

354 | assert((Flags & IncrementNoWrapMask) == Flags && "Invalid flags value!"); |

355 | assert((OffFlags & IncrementNoWrapMask) == OffFlags && |

356 | "Invalid flags value!"); |

357 | return (SCEVWrapPredicate::IncrementWrapFlags)(Flags & ~OffFlags); |

358 | } |

359 | |

360 | [[nodiscard]] static SCEVWrapPredicate::IncrementWrapFlags |

361 | maskFlags(SCEVWrapPredicate::IncrementWrapFlags Flags, int Mask) { |

362 | assert((Flags & IncrementNoWrapMask) == Flags && "Invalid flags value!"); |

363 | assert((Mask & IncrementNoWrapMask) == Mask && "Invalid mask value!"); |

364 | |

365 | return (SCEVWrapPredicate::IncrementWrapFlags)(Flags & Mask); |

366 | } |

367 | |

368 | [[nodiscard]] static SCEVWrapPredicate::IncrementWrapFlags |

369 | setFlags(SCEVWrapPredicate::IncrementWrapFlags Flags, |

370 | SCEVWrapPredicate::IncrementWrapFlags OnFlags) { |

371 | assert((Flags & IncrementNoWrapMask) == Flags && "Invalid flags value!"); |

372 | assert((OnFlags & IncrementNoWrapMask) == OnFlags && |

373 | "Invalid flags value!"); |

374 | |

375 | return (SCEVWrapPredicate::IncrementWrapFlags)(Flags | OnFlags); |

376 | } |

377 | |

378 | /// Returns the set of SCEVWrapPredicate no wrap flags implied by a |

379 | /// SCEVAddRecExpr. |

380 | [[nodiscard]] static SCEVWrapPredicate::IncrementWrapFlags |

381 | getImpliedFlags(const SCEVAddRecExpr *AR, ScalarEvolution &SE); |

382 | |

383 | private: |

384 | const SCEVAddRecExpr *AR; |

385 | IncrementWrapFlags Flags; |

386 | |

387 | public: |

388 | explicit SCEVWrapPredicate(const FoldingSetNodeIDRef ID, |

389 | const SCEVAddRecExpr *AR, |

390 | IncrementWrapFlags Flags); |

391 | |

392 | /// Returns the set assumed no overflow flags. |

393 | IncrementWrapFlags getFlags() const { return Flags; } |

394 | |

395 | /// Implementation of the SCEVPredicate interface |

396 | const SCEVAddRecExpr *getExpr() const; |

397 | bool implies(const SCEVPredicate *N) const override; |

398 | void print(raw_ostream &OS, unsigned Depth = 0) const override; |

399 | bool isAlwaysTrue() const override; |

400 | |

401 | /// Methods for support type inquiry through isa, cast, and dyn_cast: |

402 | static bool classof(const SCEVPredicate *P) { |

403 | return P->getKind() == P_Wrap; |

404 | } |

405 | }; |

406 | |

407 | /// This class represents a composition of other SCEV predicates, and is the |

408 | /// class that most clients will interact with. This is equivalent to a |

409 | /// logical "AND" of all the predicates in the union. |

410 | /// |

411 | /// NB! Unlike other SCEVPredicate sub-classes this class does not live in the |

412 | /// ScalarEvolution::Preds folding set. This is why the \c add function is sound. |

413 | class SCEVUnionPredicate final : public SCEVPredicate { |

414 | private: |

415 | using PredicateMap = |

416 | DenseMap<const SCEV *, SmallVector<const SCEVPredicate *, 4>>; |

417 | |

418 | /// Vector with references to all predicates in this union. |

419 | SmallVector<const SCEVPredicate *, 16> Preds; |

420 | |

421 | /// Adds a predicate to this union. |

422 | void add(const SCEVPredicate *N); |

423 | |

424 | public: |

425 | SCEVUnionPredicate(ArrayRef<const SCEVPredicate *> Preds); |

426 | |

427 | const SmallVectorImpl<const SCEVPredicate *> &getPredicates() const { |

428 | return Preds; |

429 | } |

430 | |

431 | /// Implementation of the SCEVPredicate interface |

432 | bool isAlwaysTrue() const override; |

433 | bool implies(const SCEVPredicate *N) const override; |

434 | void print(raw_ostream &OS, unsigned Depth) const override; |

435 | |

436 | /// We estimate the complexity of a union predicate as the size number of |

437 | /// predicates in the union. |

438 | unsigned getComplexity() const override { return Preds.size(); } |

439 | |

440 | /// Methods for support type inquiry through isa, cast, and dyn_cast: |

441 | static bool classof(const SCEVPredicate *P) { |

442 | return P->getKind() == P_Union; |

443 | } |

444 | }; |

445 | |

446 | /// The main scalar evolution driver. Because client code (intentionally) |

447 | /// can't do much with the SCEV objects directly, they must ask this class |

448 | /// for services. |

449 | class ScalarEvolution { |

450 | friend class ScalarEvolutionsTest; |

451 | |

452 | public: |

453 | /// An enum describing the relationship between a SCEV and a loop. |

454 | enum LoopDisposition { |

455 | LoopVariant, ///< The SCEV is loop-variant (unknown). |

456 | LoopInvariant, ///< The SCEV is loop-invariant. |

457 | LoopComputable ///< The SCEV varies predictably with the loop. |

458 | }; |

459 | |

460 | /// An enum describing the relationship between a SCEV and a basic block. |

461 | enum BlockDisposition { |

462 | DoesNotDominateBlock, ///< The SCEV does not dominate the block. |

463 | DominatesBlock, ///< The SCEV dominates the block. |

464 | ProperlyDominatesBlock ///< The SCEV properly dominates the block. |

465 | }; |

466 | |

467 | /// Convenient NoWrapFlags manipulation that hides enum casts and is |

468 | /// visible in the ScalarEvolution name space. |

469 | [[nodiscard]] static SCEV::NoWrapFlags maskFlags(SCEV::NoWrapFlags Flags, |

470 | int Mask) { |

471 | return (SCEV::NoWrapFlags)(Flags & Mask); |

472 | } |

473 | [[nodiscard]] static SCEV::NoWrapFlags setFlags(SCEV::NoWrapFlags Flags, |

474 | SCEV::NoWrapFlags OnFlags) { |

475 | return (SCEV::NoWrapFlags)(Flags | OnFlags); |

476 | } |

477 | [[nodiscard]] static SCEV::NoWrapFlags |

478 | clearFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OffFlags) { |

479 | return (SCEV::NoWrapFlags)(Flags & ~OffFlags); |

480 | } |

481 | [[nodiscard]] static bool hasFlags(SCEV::NoWrapFlags Flags, |

482 | SCEV::NoWrapFlags TestFlags) { |

483 | return TestFlags == maskFlags(Flags, TestFlags); |

484 | }; |

485 | |

486 | ScalarEvolution(Function &F, TargetLibraryInfo &TLI, AssumptionCache &AC, |

487 | DominatorTree &DT, LoopInfo &LI); |

488 | ScalarEvolution(ScalarEvolution &&Arg); |

489 | ~ScalarEvolution(); |

490 | |

491 | LLVMContext &getContext() const { return F.getContext(); } |

492 | |

493 | /// Test if values of the given type are analyzable within the SCEV |

494 | /// framework. This primarily includes integer types, and it can optionally |

495 | /// include pointer types if the ScalarEvolution class has access to |

496 | /// target-specific information. |

497 | bool isSCEVable(Type *Ty) const; |

498 | |

499 | /// Return the size in bits of the specified type, for which isSCEVable must |

500 | /// return true. |

501 | uint64_t getTypeSizeInBits(Type *Ty) const; |

502 | |

503 | /// Return a type with the same bitwidth as the given type and which |

504 | /// represents how SCEV will treat the given type, for which isSCEVable must |

505 | /// return true. For pointer types, this is the pointer-sized integer type. |

506 | Type *getEffectiveSCEVType(Type *Ty) const; |

507 | |

508 | // Returns a wider type among {Ty1, Ty2}. |

509 | Type *getWiderType(Type *Ty1, Type *Ty2) const; |

510 | |

511 | /// Return true if there exists a point in the program at which both |

512 | /// A and B could be operands to the same instruction. |

513 | /// SCEV expressions are generally assumed to correspond to instructions |

514 | /// which could exists in IR. In general, this requires that there exists |

515 | /// a use point in the program where all operands dominate the use. |

516 | /// |

517 | /// Example: |

518 | /// loop { |

519 | /// if |

520 | /// loop { v1 = load @global1; } |

521 | /// else |

522 | /// loop { v2 = load @global2; } |

523 | /// } |

524 | /// No SCEV with operand V1, and v2 can exist in this program. |

525 | bool instructionCouldExistWitthOperands(const SCEV *A, const SCEV *B); |

526 | |

527 | /// Return true if the SCEV is a scAddRecExpr or it contains |

528 | /// scAddRecExpr. The result will be cached in HasRecMap. |

529 | bool containsAddRecurrence(const SCEV *S); |

530 | |

531 | /// Is operation \p BinOp between \p LHS and \p RHS provably does not have |

532 | /// a signed/unsigned overflow (\p Signed)? If \p CtxI is specified, the |

533 | /// no-overflow fact should be true in the context of this instruction. |

534 | bool willNotOverflow(Instruction::BinaryOps BinOp, bool Signed, |

535 | const SCEV *LHS, const SCEV *RHS, |

536 | const Instruction *CtxI = nullptr); |

537 | |

538 | /// Parse NSW/NUW flags from add/sub/mul IR binary operation \p Op into |

539 | /// SCEV no-wrap flags, and deduce flag[s] that aren't known yet. |

540 | /// Does not mutate the original instruction. Returns None if it could not |

541 | /// deduce more precise flags than the instruction already has, otherwise |

542 | /// returns proven flags. |

543 | Optional<SCEV::NoWrapFlags> |

544 | getStrengthenedNoWrapFlagsFromBinOp(const OverflowingBinaryOperator *OBO); |

545 | |

546 | /// Notify this ScalarEvolution that \p User directly uses SCEVs in \p Ops. |

547 | void registerUser(const SCEV *User, ArrayRef<const SCEV *> Ops); |

548 | |

549 | /// Return true if the SCEV expression contains an undef value. |

550 | bool containsUndefs(const SCEV *S) const; |

551 | |

552 | /// Return true if the SCEV expression contains a Value that has been |

553 | /// optimised out and is now a nullptr. |

554 | bool containsErasedValue(const SCEV *S) const; |

555 | |

556 | /// Return a SCEV expression for the full generality of the specified |

557 | /// expression. |

558 | const SCEV *getSCEV(Value *V); |

559 | |

560 | const SCEV *getConstant(ConstantInt *V); |

561 | const SCEV *getConstant(const APInt &Val); |

562 | const SCEV *getConstant(Type *Ty, uint64_t V, bool isSigned = false); |

563 | const SCEV *getLosslessPtrToIntExpr(const SCEV *Op, unsigned Depth = 0); |

564 | const SCEV *getPtrToIntExpr(const SCEV *Op, Type *Ty); |

565 | const SCEV *getTruncateExpr(const SCEV *Op, Type *Ty, unsigned Depth = 0); |

566 | const SCEV *getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth = 0); |

567 | const SCEV *getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth = 0); |

568 | const SCEV *getCastExpr(SCEVTypes Kind, const SCEV *Op, Type *Ty); |

569 | const SCEV *getAnyExtendExpr(const SCEV *Op, Type *Ty); |

570 | const SCEV *getAddExpr(SmallVectorImpl<const SCEV *> &Ops, |

571 | SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap, |

572 | unsigned Depth = 0); |

573 | const SCEV *getAddExpr(const SCEV *LHS, const SCEV *RHS, |

574 | SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap, |

575 | unsigned Depth = 0) { |

576 | SmallVector<const SCEV *, 2> Ops = {LHS, RHS}; |

577 | return getAddExpr(Ops, Flags, Depth); |

578 | } |

579 | const SCEV *getAddExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2, |

580 | SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap, |

581 | unsigned Depth = 0) { |

582 | SmallVector<const SCEV *, 3> Ops = {Op0, Op1, Op2}; |

583 | return getAddExpr(Ops, Flags, Depth); |

584 | } |

585 | const SCEV *getMulExpr(SmallVectorImpl<const SCEV *> &Ops, |

586 | SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap, |

587 | unsigned Depth = 0); |

588 | const SCEV *getMulExpr(const SCEV *LHS, const SCEV *RHS, |

589 | SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap, |

590 | unsigned Depth = 0) { |

591 | SmallVector<const SCEV *, 2> Ops = {LHS, RHS}; |

592 | return getMulExpr(Ops, Flags, Depth); |

593 | } |

594 | const SCEV *getMulExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2, |

595 | SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap, |

596 | unsigned Depth = 0) { |

597 | SmallVector<const SCEV *, 3> Ops = {Op0, Op1, Op2}; |

598 | return getMulExpr(Ops, Flags, Depth); |

599 | } |

600 | const SCEV *getUDivExpr(const SCEV *LHS, const SCEV *RHS); |

601 | const SCEV *getUDivExactExpr(const SCEV *LHS, const SCEV *RHS); |

602 | const SCEV *getURemExpr(const SCEV *LHS, const SCEV *RHS); |

603 | const SCEV *getAddRecExpr(const SCEV *Start, const SCEV *Step, const Loop *L, |

604 | SCEV::NoWrapFlags Flags); |

605 | const SCEV *getAddRecExpr(SmallVectorImpl<const SCEV *> &Operands, |

606 | const Loop *L, SCEV::NoWrapFlags Flags); |

607 | const SCEV *getAddRecExpr(const SmallVectorImpl<const SCEV *> &Operands, |

608 | const Loop *L, SCEV::NoWrapFlags Flags) { |

609 | SmallVector<const SCEV *, 4> NewOp(Operands.begin(), Operands.end()); |

610 | return getAddRecExpr(NewOp, L, Flags); |

611 | } |

612 | |

613 | /// Checks if \p SymbolicPHI can be rewritten as an AddRecExpr under some |

614 | /// Predicates. If successful return these <AddRecExpr, Predicates>; |

615 | /// The function is intended to be called from PSCEV (the caller will decide |

616 | /// whether to actually add the predicates and carry out the rewrites). |

617 | Optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>> |

618 | createAddRecFromPHIWithCasts(const SCEVUnknown *SymbolicPHI); |

619 | |

620 | /// Returns an expression for a GEP |

621 | /// |

622 | /// \p GEP The GEP. The indices contained in the GEP itself are ignored, |

623 | /// instead we use IndexExprs. |

624 | /// \p IndexExprs The expressions for the indices. |

625 | const SCEV *getGEPExpr(GEPOperator *GEP, |

626 | const SmallVectorImpl<const SCEV *> &IndexExprs); |

627 | const SCEV *getAbsExpr(const SCEV *Op, bool IsNSW); |

628 | const SCEV *getMinMaxExpr(SCEVTypes Kind, |

629 | SmallVectorImpl<const SCEV *> &Operands); |

630 | const SCEV *getSequentialMinMaxExpr(SCEVTypes Kind, |

631 | SmallVectorImpl<const SCEV *> &Operands); |

632 | const SCEV *getSMaxExpr(const SCEV *LHS, const SCEV *RHS); |

633 | const SCEV *getSMaxExpr(SmallVectorImpl<const SCEV *> &Operands); |

634 | const SCEV *getUMaxExpr(const SCEV *LHS, const SCEV *RHS); |

635 | const SCEV *getUMaxExpr(SmallVectorImpl<const SCEV *> &Operands); |

636 | const SCEV *getSMinExpr(const SCEV *LHS, const SCEV *RHS); |

637 | const SCEV *getSMinExpr(SmallVectorImpl<const SCEV *> &Operands); |

638 | const SCEV *getUMinExpr(const SCEV *LHS, const SCEV *RHS, |

639 | bool Sequential = false); |

640 | const SCEV *getUMinExpr(SmallVectorImpl<const SCEV *> &Operands, |

641 | bool Sequential = false); |

642 | const SCEV *getUnknown(Value *V); |

643 | const SCEV *getCouldNotCompute(); |

644 | |

645 | /// Return a SCEV for the constant 0 of a specific type. |

646 | const SCEV *getZero(Type *Ty) { return getConstant(Ty, 0); } |

647 | |

648 | /// Return a SCEV for the constant 1 of a specific type. |

649 | const SCEV *getOne(Type *Ty) { return getConstant(Ty, 1); } |

650 | |

651 | /// Return a SCEV for the constant -1 of a specific type. |

652 | const SCEV *getMinusOne(Type *Ty) { |

653 | return getConstant(Ty, -1, /*isSigned=*/true); |

654 | } |

655 | |

656 | /// Return an expression for sizeof ScalableTy that is type IntTy, where |

657 | /// ScalableTy is a scalable vector type. |

658 | const SCEV *getSizeOfScalableVectorExpr(Type *IntTy, |

659 | ScalableVectorType *ScalableTy); |

660 | |

661 | /// Return an expression for the alloc size of AllocTy that is type IntTy |

662 | const SCEV *getSizeOfExpr(Type *IntTy, Type *AllocTy); |

663 | |

664 | /// Return an expression for the store size of StoreTy that is type IntTy |

665 | const SCEV *getStoreSizeOfExpr(Type *IntTy, Type *StoreTy); |

666 | |

667 | /// Return an expression for offsetof on the given field with type IntTy |

668 | const SCEV *getOffsetOfExpr(Type *IntTy, StructType *STy, unsigned FieldNo); |

669 | |

670 | /// Return the SCEV object corresponding to -V. |

671 | const SCEV *getNegativeSCEV(const SCEV *V, |

672 | SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap); |

673 | |

674 | /// Return the SCEV object corresponding to ~V. |

675 | const SCEV *getNotSCEV(const SCEV *V); |

676 | |

677 | /// Return LHS-RHS. Minus is represented in SCEV as A+B*-1. |

678 | /// |

679 | /// If the LHS and RHS are pointers which don't share a common base |

680 | /// (according to getPointerBase()), this returns a SCEVCouldNotCompute. |

681 | /// To compute the difference between two unrelated pointers, you can |

682 | /// explicitly convert the arguments using getPtrToIntExpr(), for pointer |

683 | /// types that support it. |

684 | const SCEV *getMinusSCEV(const SCEV *LHS, const SCEV *RHS, |

685 | SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap, |

686 | unsigned Depth = 0); |

687 | |

688 | /// Compute ceil(N / D). N and D are treated as unsigned values. |

689 | /// |

690 | /// Since SCEV doesn't have native ceiling division, this generates a |

691 | /// SCEV expression of the following form: |

692 | /// |

693 | /// umin(N, 1) + floor((N - umin(N, 1)) / D) |

694 | /// |

695 | /// A denominator of zero or poison is handled the same way as getUDivExpr(). |

696 | const SCEV *getUDivCeilSCEV(const SCEV *N, const SCEV *D); |

697 | |

698 | /// Return a SCEV corresponding to a conversion of the input value to the |

699 | /// specified type. If the type must be extended, it is zero extended. |

700 | const SCEV *getTruncateOrZeroExtend(const SCEV *V, Type *Ty, |

701 | unsigned Depth = 0); |

702 | |

703 | /// Return a SCEV corresponding to a conversion of the input value to the |

704 | /// specified type. If the type must be extended, it is sign extended. |

705 | const SCEV *getTruncateOrSignExtend(const SCEV *V, Type *Ty, |

706 | unsigned Depth = 0); |

707 | |

708 | /// Return a SCEV corresponding to a conversion of the input value to the |

709 | /// specified type. If the type must be extended, it is zero extended. The |

710 | /// conversion must not be narrowing. |

711 | const SCEV *getNoopOrZeroExtend(const SCEV *V, Type *Ty); |

712 | |

713 | /// Return a SCEV corresponding to a conversion of the input value to the |

714 | /// specified type. If the type must be extended, it is sign extended. The |

715 | /// conversion must not be narrowing. |

716 | const SCEV *getNoopOrSignExtend(const SCEV *V, Type *Ty); |

717 | |

718 | /// Return a SCEV corresponding to a conversion of the input value to the |

719 | /// specified type. If the type must be extended, it is extended with |

720 | /// unspecified bits. The conversion must not be narrowing. |

721 | const SCEV *getNoopOrAnyExtend(const SCEV *V, Type *Ty); |

722 | |

723 | /// Return a SCEV corresponding to a conversion of the input value to the |

724 | /// specified type. The conversion must not be widening. |

725 | const SCEV *getTruncateOrNoop(const SCEV *V, Type *Ty); |

726 | |

727 | /// Promote the operands to the wider of the types using zero-extension, and |

728 | /// then perform a umax operation with them. |

729 | const SCEV *getUMaxFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS); |

730 | |

731 | /// Promote the operands to the wider of the types using zero-extension, and |

732 | /// then perform a umin operation with them. |

733 | const SCEV *getUMinFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS, |

734 | bool Sequential = false); |

735 | |

736 | /// Promote the operands to the wider of the types using zero-extension, and |

737 | /// then perform a umin operation with them. N-ary function. |

738 | const SCEV *getUMinFromMismatchedTypes(SmallVectorImpl<const SCEV *> &Ops, |

739 | bool Sequential = false); |

740 | |

741 | /// Transitively follow the chain of pointer-type operands until reaching a |

742 | /// SCEV that does not have a single pointer operand. This returns a |

743 | /// SCEVUnknown pointer for well-formed pointer-type expressions, but corner |

744 | /// cases do exist. |

745 | const SCEV *getPointerBase(const SCEV *V); |

746 | |

747 | /// Compute an expression equivalent to S - getPointerBase(S). |

748 | const SCEV *removePointerBase(const SCEV *S); |

749 | |

750 | /// Return a SCEV expression for the specified value at the specified scope |

751 | /// in the program. The L value specifies a loop nest to evaluate the |

752 | /// expression at, where null is the top-level or a specified loop is |

753 | /// immediately inside of the loop. |

754 | /// |

755 | /// This method can be used to compute the exit value for a variable defined |

756 | /// in a loop by querying what the value will hold in the parent loop. |

757 | /// |

758 | /// In the case that a relevant loop exit value cannot be computed, the |

759 | /// original value V is returned. |

760 | const SCEV *getSCEVAtScope(const SCEV *S, const Loop *L); |

761 | |

762 | /// This is a convenience function which does getSCEVAtScope(getSCEV(V), L). |

763 | const SCEV *getSCEVAtScope(Value *V, const Loop *L); |

764 | |

765 | /// Test whether entry to the loop is protected by a conditional between LHS |

766 | /// and RHS. This is used to help avoid max expressions in loop trip |

767 | /// counts, and to eliminate casts. |

768 | bool isLoopEntryGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, |

769 | const SCEV *LHS, const SCEV *RHS); |

770 | |

771 | /// Test whether entry to the basic block is protected by a conditional |

772 | /// between LHS and RHS. |

773 | bool isBasicBlockEntryGuardedByCond(const BasicBlock *BB, |

774 | ICmpInst::Predicate Pred, const SCEV *LHS, |

775 | const SCEV *RHS); |

776 | |

777 | /// Test whether the backedge of the loop is protected by a conditional |

778 | /// between LHS and RHS. This is used to eliminate casts. |

779 | bool isLoopBackedgeGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, |

780 | const SCEV *LHS, const SCEV *RHS); |

781 | |

782 | /// Convert from an "exit count" (i.e. "backedge taken count") to a "trip |

783 | /// count". A "trip count" is the number of times the header of the loop |

784 | /// will execute if an exit is taken after the specified number of backedges |

785 | /// have been taken. (e.g. TripCount = ExitCount + 1). Note that the |

786 | /// expression can overflow if ExitCount = UINT_MAX. \p Extend controls |

787 | /// how potential overflow is handled. If true, a wider result type is |

788 | /// returned. ex: EC = 255 (i8), TC = 256 (i9). If false, result unsigned |

789 | /// wraps with 2s-complement semantics. ex: EC = 255 (i8), TC = 0 (i8) |

790 | const SCEV *getTripCountFromExitCount(const SCEV *ExitCount, |

791 | bool Extend = true); |

792 | |

793 | /// Returns the exact trip count of the loop if we can compute it, and |

794 | /// the result is a small constant. '0' is used to represent an unknown |

795 | /// or non-constant trip count. Note that a trip count is simply one more |

796 | /// than the backedge taken count for the loop. |

797 | unsigned getSmallConstantTripCount(const Loop *L); |

798 | |

799 | /// Return the exact trip count for this loop if we exit through ExitingBlock. |

800 | /// '0' is used to represent an unknown or non-constant trip count. Note |

801 | /// that a trip count is simply one more than the backedge taken count for |

802 | /// the same exit. |

803 | /// This "trip count" assumes that control exits via ExitingBlock. More |

804 | /// precisely, it is the number of times that control will reach ExitingBlock |

805 | /// before taking the branch. For loops with multiple exits, it may not be |

806 | /// the number times that the loop header executes if the loop exits |

807 | /// prematurely via another branch. |

808 | unsigned getSmallConstantTripCount(const Loop *L, |

809 | const BasicBlock *ExitingBlock); |

810 | |

811 | /// Returns the upper bound of the loop trip count as a normal unsigned |

812 | /// value. |

813 | /// Returns 0 if the trip count is unknown or not constant. |

814 | unsigned getSmallConstantMaxTripCount(const Loop *L); |

815 | |

816 | /// Returns the upper bound of the loop trip count infered from array size. |

817 | /// Can not access bytes starting outside the statically allocated size |

818 | /// without being immediate UB. |

819 | /// Returns SCEVCouldNotCompute if the trip count could not inferred |

820 | /// from array accesses. |

821 | const SCEV *getConstantMaxTripCountFromArray(const Loop *L); |

822 | |

823 | /// Returns the largest constant divisor of the trip count as a normal |

824 | /// unsigned value, if possible. This means that the actual trip count is |

825 | /// always a multiple of the returned value. Returns 1 if the trip count is |

826 | /// unknown or not guaranteed to be the multiple of a constant., Will also |

827 | /// return 1 if the trip count is very large (>= 2^32). |

828 | /// Note that the argument is an exit count for loop L, NOT a trip count. |

829 | unsigned getSmallConstantTripMultiple(const Loop *L, |

830 | const SCEV *ExitCount); |

831 | |

832 | /// Returns the largest constant divisor of the trip count of the |

833 | /// loop. Will return 1 if no trip count could be computed, or if a |

834 | /// divisor could not be found. |

835 | unsigned getSmallConstantTripMultiple(const Loop *L); |

836 | |

837 | /// Returns the largest constant divisor of the trip count of this loop as a |

838 | /// normal unsigned value, if possible. This means that the actual trip |

839 | /// count is always a multiple of the returned value (don't forget the trip |

840 | /// count could very well be zero as well!). As explained in the comments |

841 | /// for getSmallConstantTripCount, this assumes that control exits the loop |

842 | /// via ExitingBlock. |

843 | unsigned getSmallConstantTripMultiple(const Loop *L, |

844 | const BasicBlock *ExitingBlock); |

845 | |

846 | /// The terms "backedge taken count" and "exit count" are used |

847 | /// interchangeably to refer to the number of times the backedge of a loop |

848 | /// has executed before the loop is exited. |

849 | enum ExitCountKind { |

850 | /// An expression exactly describing the number of times the backedge has |

851 | /// executed when a loop is exited. |

852 | Exact, |

853 | /// A constant which provides an upper bound on the exact trip count. |

854 | ConstantMaximum, |

855 | /// An expression which provides an upper bound on the exact trip count. |

856 | SymbolicMaximum, |

857 | }; |

858 | |

859 | /// Return the number of times the backedge executes before the given exit |

860 | /// would be taken; if not exactly computable, return SCEVCouldNotCompute. |

861 | /// For a single exit loop, this value is equivelent to the result of |

862 | /// getBackedgeTakenCount. The loop is guaranteed to exit (via *some* exit) |

863 | /// before the backedge is executed (ExitCount + 1) times. Note that there |

864 | /// is no guarantee about *which* exit is taken on the exiting iteration. |

865 | const SCEV *getExitCount(const Loop *L, const BasicBlock *ExitingBlock, |

866 | ExitCountKind Kind = Exact); |

867 | |

868 | /// If the specified loop has a predictable backedge-taken count, return it, |

869 | /// otherwise return a SCEVCouldNotCompute object. The backedge-taken count is |

870 | /// the number of times the loop header will be branched to from within the |

871 | /// loop, assuming there are no abnormal exists like exception throws. This is |

872 | /// one less than the trip count of the loop, since it doesn't count the first |

873 | /// iteration, when the header is branched to from outside the loop. |

874 | /// |

875 | /// Note that it is not valid to call this method on a loop without a |

876 | /// loop-invariant backedge-taken count (see |

877 | /// hasLoopInvariantBackedgeTakenCount). |

878 | const SCEV *getBackedgeTakenCount(const Loop *L, ExitCountKind Kind = Exact); |

879 | |

880 | /// Similar to getBackedgeTakenCount, except it will add a set of |

881 | /// SCEV predicates to Predicates that are required to be true in order for |

882 | /// the answer to be correct. Predicates can be checked with run-time |

883 | /// checks and can be used to perform loop versioning. |

884 | const SCEV *getPredicatedBackedgeTakenCount(const Loop *L, |

885 | SmallVector<const SCEVPredicate *, 4> &Predicates); |

886 | |

887 | /// When successful, this returns a SCEVConstant that is greater than or equal |

888 | /// to (i.e. a "conservative over-approximation") of the value returend by |

889 | /// getBackedgeTakenCount. If such a value cannot be computed, it returns the |

890 | /// SCEVCouldNotCompute object. |

891 | const SCEV *getConstantMaxBackedgeTakenCount(const Loop *L) { |

892 | return getBackedgeTakenCount(L, ConstantMaximum); |

893 | } |

894 | |

895 | /// When successful, this returns a SCEV that is greater than or equal |

896 | /// to (i.e. a "conservative over-approximation") of the value returend by |

897 | /// getBackedgeTakenCount. If such a value cannot be computed, it returns the |

898 | /// SCEVCouldNotCompute object. |

899 | const SCEV *getSymbolicMaxBackedgeTakenCount(const Loop *L) { |

900 | return getBackedgeTakenCount(L, SymbolicMaximum); |

901 | } |

902 | |

903 | /// Return true if the backedge taken count is either the value returned by |

904 | /// getConstantMaxBackedgeTakenCount or zero. |

905 | bool isBackedgeTakenCountMaxOrZero(const Loop *L); |

906 | |

907 | /// Return true if the specified loop has an analyzable loop-invariant |

908 | /// backedge-taken count. |

909 | bool hasLoopInvariantBackedgeTakenCount(const Loop *L); |

910 | |

911 | // This method should be called by the client when it made any change that |

912 | // would invalidate SCEV's answers, and the client wants to remove all loop |

913 | // information held internally by ScalarEvolution. This is intended to be used |

914 | // when the alternative to forget a loop is too expensive (i.e. large loop |

915 | // bodies). |

916 | void forgetAllLoops(); |

917 | |

918 | /// This method should be called by the client when it has changed a loop in |

919 | /// a way that may effect ScalarEvolution's ability to compute a trip count, |

920 | /// or if the loop is deleted. This call is potentially expensive for large |

921 | /// loop bodies. |

922 | void forgetLoop(const Loop *L); |

923 | |

924 | // This method invokes forgetLoop for the outermost loop of the given loop |

925 | // \p L, making ScalarEvolution forget about all this subtree. This needs to |

926 | // be done whenever we make a transform that may affect the parameters of the |

927 | // outer loop, such as exit counts for branches. |

928 | void forgetTopmostLoop(const Loop *L); |

929 | |

930 | /// This method should be called by the client when it has changed a value |

931 | /// in a way that may effect its value, or which may disconnect it from a |

932 | /// def-use chain linking it to a loop. |

933 | void forgetValue(Value *V); |

934 | |

935 | /// Called when the client has changed the disposition of values in |

936 | /// this loop. |

937 | /// |

938 | /// We don't have a way to invalidate per-loop dispositions. Clear and |

939 | /// recompute is simpler. |

940 | void forgetLoopDispositions(const Loop *L); |

941 | |

942 | /// Determine the minimum number of zero bits that S is guaranteed to end in |

943 | /// (at every loop iteration). It is, at the same time, the minimum number |

944 | /// of times S is divisible by 2. For example, given {4,+,8} it returns 2. |

945 | /// If S is guaranteed to be 0, it returns the bitwidth of S. |

946 | uint32_t GetMinTrailingZeros(const SCEV *S); |

947 | |

948 | /// Determine the unsigned range for a particular SCEV. |

949 | /// NOTE: This returns a copy of the reference returned by getRangeRef. |

950 | ConstantRange getUnsignedRange(const SCEV *S) { |

951 | return getRangeRef(S, HINT_RANGE_UNSIGNED); |

952 | } |

953 | |

954 | /// Determine the min of the unsigned range for a particular SCEV. |

955 | APInt getUnsignedRangeMin(const SCEV *S) { |

956 | return getRangeRef(S, HINT_RANGE_UNSIGNED).getUnsignedMin(); |

957 | } |

958 | |

959 | /// Determine the max of the unsigned range for a particular SCEV. |

960 | APInt getUnsignedRangeMax(const SCEV *S) { |

961 | return getRangeRef(S, HINT_RANGE_UNSIGNED).getUnsignedMax(); |

962 | } |

963 | |

964 | /// Determine the signed range for a particular SCEV. |

965 | /// NOTE: This returns a copy of the reference returned by getRangeRef. |

966 | ConstantRange getSignedRange(const SCEV *S) { |

967 | return getRangeRef(S, HINT_RANGE_SIGNED); |

968 | } |

969 | |

970 | /// Determine the min of the signed range for a particular SCEV. |

971 | APInt getSignedRangeMin(const SCEV *S) { |

972 | return getRangeRef(S, HINT_RANGE_SIGNED).getSignedMin(); |

973 | } |

974 | |

975 | /// Determine the max of the signed range for a particular SCEV. |

976 | APInt getSignedRangeMax(const SCEV *S) { |

977 | return getRangeRef(S, HINT_RANGE_SIGNED).getSignedMax(); |

978 | } |

979 | |

980 | /// Test if the given expression is known to be negative. |

981 | bool isKnownNegative(const SCEV *S); |

982 | |

983 | /// Test if the given expression is known to be positive. |

984 | bool isKnownPositive(const SCEV *S); |

985 | |

986 | /// Test if the given expression is known to be non-negative. |

987 | bool isKnownNonNegative(const SCEV *S); |

988 | |

989 | /// Test if the given expression is known to be non-positive. |

990 | bool isKnownNonPositive(const SCEV *S); |

991 | |

992 | /// Test if the given expression is known to be non-zero. |

993 | bool isKnownNonZero(const SCEV *S); |

994 | |

995 | /// Splits SCEV expression \p S into two SCEVs. One of them is obtained from |

996 | /// \p S by substitution of all AddRec sub-expression related to loop \p L |

997 | /// with initial value of that SCEV. The second is obtained from \p S by |

998 | /// substitution of all AddRec sub-expressions related to loop \p L with post |

999 | /// increment of this AddRec in the loop \p L. In both cases all other AddRec |

1000 | /// sub-expressions (not related to \p L) remain the same. |

1001 | /// If the \p S contains non-invariant unknown SCEV the function returns |

1002 | /// CouldNotCompute SCEV in both values of std::pair. |

1003 | /// For example, for SCEV S={0, +, 1}<L1> + {0, +, 1}<L2> and loop L=L1 |

1004 | /// the function returns pair: |

1005 | /// first = {0, +, 1}<L2> |

1006 | /// second = {1, +, 1}<L1> + {0, +, 1}<L2> |

1007 | /// We can see that for the first AddRec sub-expression it was replaced with |

1008 | /// 0 (initial value) for the first element and to {1, +, 1}<L1> (post |

1009 | /// increment value) for the second one. In both cases AddRec expression |

1010 | /// related to L2 remains the same. |

1011 | std::pair<const SCEV *, const SCEV *> SplitIntoInitAndPostInc(const Loop *L, |

1012 | const SCEV *S); |

1013 | |

1014 | /// We'd like to check the predicate on every iteration of the most dominated |

1015 | /// loop between loops used in LHS and RHS. |

1016 | /// To do this we use the following list of steps: |

1017 | /// 1. Collect set S all loops on which either LHS or RHS depend. |

1018 | /// 2. If S is non-empty |

1019 | /// a. Let PD be the element of S which is dominated by all other elements. |

1020 | /// b. Let E(LHS) be value of LHS on entry of PD. |

1021 | /// To get E(LHS), we should just take LHS and replace all AddRecs that are |

1022 | /// attached to PD on with their entry values. |

1023 | /// Define E(RHS) in the same way. |

1024 | /// c. Let B(LHS) be value of L on backedge of PD. |

1025 | /// To get B(LHS), we should just take LHS and replace all AddRecs that are |

1026 | /// attached to PD on with their backedge values. |

1027 | /// Define B(RHS) in the same way. |

1028 | /// d. Note that E(LHS) and E(RHS) are automatically available on entry of PD, |

1029 | /// so we can assert on that. |

1030 | /// e. Return true if isLoopEntryGuardedByCond(Pred, E(LHS), E(RHS)) && |

1031 | /// isLoopBackedgeGuardedByCond(Pred, B(LHS), B(RHS)) |

1032 | bool isKnownViaInduction(ICmpInst::Predicate Pred, const SCEV *LHS, |

1033 | const SCEV *RHS); |

1034 | |

1035 | /// Test if the given expression is known to satisfy the condition described |

1036 | /// by Pred, LHS, and RHS. |

1037 | bool isKnownPredicate(ICmpInst::Predicate Pred, const SCEV *LHS, |

1038 | const SCEV *RHS); |

1039 | |

1040 | /// Check whether the condition described by Pred, LHS, and RHS is true or |

1041 | /// false. If we know it, return the evaluation of this condition. If neither |

1042 | /// is proved, return None. |

1043 | Optional<bool> evaluatePredicate(ICmpInst::Predicate Pred, const SCEV *LHS, |

1044 | const SCEV *RHS); |

1045 | |

1046 | /// Test if the given expression is known to satisfy the condition described |

1047 | /// by Pred, LHS, and RHS in the given Context. |

1048 | bool isKnownPredicateAt(ICmpInst::Predicate Pred, const SCEV *LHS, |

1049 | const SCEV *RHS, const Instruction *CtxI); |

1050 | |

1051 | /// Check whether the condition described by Pred, LHS, and RHS is true or |

1052 | /// false in the given \p Context. If we know it, return the evaluation of |

1053 | /// this condition. If neither is proved, return None. |

1054 | Optional<bool> evaluatePredicateAt(ICmpInst::Predicate Pred, const SCEV *LHS, |

1055 | const SCEV *RHS, const Instruction *CtxI); |

1056 | |

1057 | /// Test if the condition described by Pred, LHS, RHS is known to be true on |

1058 | /// every iteration of the loop of the recurrency LHS. |

1059 | bool isKnownOnEveryIteration(ICmpInst::Predicate Pred, |

1060 | const SCEVAddRecExpr *LHS, const SCEV *RHS); |

1061 | |

1062 | /// A predicate is said to be monotonically increasing if may go from being |

1063 | /// false to being true as the loop iterates, but never the other way |

1064 | /// around. A predicate is said to be monotonically decreasing if may go |

1065 | /// from being true to being false as the loop iterates, but never the other |

1066 | /// way around. |

1067 | enum MonotonicPredicateType { |

1068 | MonotonicallyIncreasing, |

1069 | MonotonicallyDecreasing |

1070 | }; |

1071 | |

1072 | /// If, for all loop invariant X, the predicate "LHS `Pred` X" is |

1073 | /// monotonically increasing or decreasing, returns |

1074 | /// Some(MonotonicallyIncreasing) and Some(MonotonicallyDecreasing) |

1075 | /// respectively. If we could not prove either of these facts, returns None. |

1076 | Optional<MonotonicPredicateType> |

1077 | getMonotonicPredicateType(const SCEVAddRecExpr *LHS, |

1078 | ICmpInst::Predicate Pred); |

1079 | |

1080 | struct LoopInvariantPredicate { |

1081 | ICmpInst::Predicate Pred; |

1082 | const SCEV *LHS; |

1083 | const SCEV *RHS; |

1084 | |

1085 | LoopInvariantPredicate(ICmpInst::Predicate Pred, const SCEV *LHS, |

1086 | const SCEV *RHS) |

1087 | : Pred(Pred), LHS(LHS), RHS(RHS) {} |

1088 | }; |

1089 | /// If the result of the predicate LHS `Pred` RHS is loop invariant with |

1090 | /// respect to L, return a LoopInvariantPredicate with LHS and RHS being |

1091 | /// invariants, available at L's entry. Otherwise, return None. |

1092 | Optional<LoopInvariantPredicate> |

1093 | getLoopInvariantPredicate(ICmpInst::Predicate Pred, const SCEV *LHS, |

1094 | const SCEV *RHS, const Loop *L, |

1095 | const Instruction *CtxI = nullptr); |

1096 | |

1097 | /// If the result of the predicate LHS `Pred` RHS is loop invariant with |

1098 | /// respect to L at given Context during at least first MaxIter iterations, |

1099 | /// return a LoopInvariantPredicate with LHS and RHS being invariants, |

1100 | /// available at L's entry. Otherwise, return None. The predicate should be |

1101 | /// the loop's exit condition. |

1102 | Optional<LoopInvariantPredicate> |

1103 | getLoopInvariantExitCondDuringFirstIterations(ICmpInst::Predicate Pred, |

1104 | const SCEV *LHS, |

1105 | const SCEV *RHS, const Loop *L, |

1106 | const Instruction *CtxI, |

1107 | const SCEV *MaxIter); |

1108 | |

1109 | /// Simplify LHS and RHS in a comparison with predicate Pred. Return true |

1110 | /// iff any changes were made. If the operands are provably equal or |

1111 | /// unequal, LHS and RHS are set to the same value and Pred is set to either |

1112 | /// ICMP_EQ or ICMP_NE. ControllingFiniteLoop is set if this comparison |

1113 | /// controls the exit of a loop known to have a finite number of iterations. |

1114 | bool SimplifyICmpOperands(ICmpInst::Predicate &Pred, const SCEV *&LHS, |

1115 | const SCEV *&RHS, unsigned Depth = 0, |

1116 | bool ControllingFiniteLoop = false); |

1117 | |

1118 | /// Return the "disposition" of the given SCEV with respect to the given |

1119 | /// loop. |

1120 | LoopDisposition getLoopDisposition(const SCEV *S, const Loop *L); |

1121 | |

1122 | /// Return true if the value of the given SCEV is unchanging in the |

1123 | /// specified loop. |

1124 | bool isLoopInvariant(const SCEV *S, const Loop *L); |

1125 | |

1126 | /// Determine if the SCEV can be evaluated at loop's entry. It is true if it |

1127 | /// doesn't depend on a SCEVUnknown of an instruction which is dominated by |

1128 | /// the header of loop L. |

1129 | bool isAvailableAtLoopEntry(const SCEV *S, const Loop *L); |

1130 | |

1131 | /// Return true if the given SCEV changes value in a known way in the |

1132 | /// specified loop. This property being true implies that the value is |

1133 | /// variant in the loop AND that we can emit an expression to compute the |

1134 | /// value of the expression at any particular loop iteration. |

1135 | bool hasComputableLoopEvolution(const SCEV *S, const Loop *L); |

1136 | |

1137 | /// Return the "disposition" of the given SCEV with respect to the given |

1138 | /// block. |

1139 | BlockDisposition getBlockDisposition(const SCEV *S, const BasicBlock *BB); |

1140 | |

1141 | /// Return true if elements that makes up the given SCEV dominate the |

1142 | /// specified basic block. |

1143 | bool dominates(const SCEV *S, const BasicBlock *BB); |

1144 | |

1145 | /// Return true if elements that makes up the given SCEV properly dominate |

1146 | /// the specified basic block. |

1147 | bool properlyDominates(const SCEV *S, const BasicBlock *BB); |

1148 | |

1149 | /// Test whether the given SCEV has Op as a direct or indirect operand. |

1150 | bool hasOperand(const SCEV *S, const SCEV *Op) const; |

1151 | |

1152 | /// Return the size of an element read or written by Inst. |

1153 | const SCEV *getElementSize(Instruction *Inst); |

1154 | |

1155 | void print(raw_ostream &OS) const; |

1156 | void verify() const; |

1157 | bool invalidate(Function &F, const PreservedAnalyses &PA, |

1158 | FunctionAnalysisManager::Invalidator &Inv); |

1159 | |

1160 | /// Return the DataLayout associated with the module this SCEV instance is |

1161 | /// operating on. |

1162 | const DataLayout &getDataLayout() const { |

1163 | return F.getParent()->getDataLayout(); |

1164 | } |

1165 | |

1166 | const SCEVPredicate *getEqualPredicate(const SCEV *LHS, const SCEV *RHS); |

1167 | const SCEVPredicate *getComparePredicate(ICmpInst::Predicate Pred, |

1168 | const SCEV *LHS, const SCEV *RHS); |

1169 | |

1170 | const SCEVPredicate * |

1171 | getWrapPredicate(const SCEVAddRecExpr *AR, |

1172 | SCEVWrapPredicate::IncrementWrapFlags AddedFlags); |

1173 | |

1174 | /// Re-writes the SCEV according to the Predicates in \p A. |

1175 | const SCEV *rewriteUsingPredicate(const SCEV *S, const Loop *L, |

1176 | const SCEVPredicate &A); |

1177 | /// Tries to convert the \p S expression to an AddRec expression, |

1178 | /// adding additional predicates to \p Preds as required. |

1179 | const SCEVAddRecExpr *convertSCEVToAddRecWithPredicates( |

1180 | const SCEV *S, const Loop *L, |

1181 | SmallPtrSetImpl<const SCEVPredicate *> &Preds); |

1182 | |

1183 | /// Compute \p LHS - \p RHS and returns the result as an APInt if it is a |

1184 | /// constant, and None if it isn't. |

1185 | /// |

1186 | /// This is intended to be a cheaper version of getMinusSCEV. We can be |

1187 | /// frugal here since we just bail out of actually constructing and |

1188 | /// canonicalizing an expression in the cases where the result isn't going |

1189 | /// to be a constant. |

1190 | Optional<APInt> computeConstantDifference(const SCEV *LHS, const SCEV *RHS); |

1191 | |

1192 | /// Update no-wrap flags of an AddRec. This may drop the cached info about |

1193 | /// this AddRec (such as range info) in case if new flags may potentially |

1194 | /// sharpen it. |

1195 | void setNoWrapFlags(SCEVAddRecExpr *AddRec, SCEV::NoWrapFlags Flags); |

1196 | |

1197 | /// Try to apply information from loop guards for \p L to \p Expr. |

1198 | const SCEV *applyLoopGuards(const SCEV *Expr, const Loop *L); |

1199 | |

1200 | /// Return true if the loop has no abnormal exits. That is, if the loop |

1201 | /// is not infinite, it must exit through an explicit edge in the CFG. |

1202 | /// (As opposed to either a) throwing out of the function or b) entering a |

1203 | /// well defined infinite loop in some callee.) |

1204 | bool loopHasNoAbnormalExits(const Loop *L) { |

1205 | return getLoopProperties(L).HasNoAbnormalExits; |

1206 | } |

1207 | |

1208 | /// Return true if this loop is finite by assumption. That is, |

1209 | /// to be infinite, it must also be undefined. |

1210 | bool loopIsFiniteByAssumption(const Loop *L); |

1211 | |

1212 | private: |

1213 | /// A CallbackVH to arrange for ScalarEvolution to be notified whenever a |

1214 | /// Value is deleted. |

1215 | class SCEVCallbackVH final : public CallbackVH { |

1216 | ScalarEvolution *SE; |

1217 | |

1218 | void deleted() override; |

1219 | void allUsesReplacedWith(Value *New) override; |

1220 | |

1221 | public: |

1222 | SCEVCallbackVH(Value *V, ScalarEvolution *SE = nullptr); |

1223 | }; |

1224 | |

1225 | friend class SCEVCallbackVH; |

1226 | friend class SCEVExpander; |

1227 | friend class SCEVUnknown; |

1228 | |

1229 | /// The function we are analyzing. |

1230 | Function &F; |

1231 | |

1232 | /// Does the module have any calls to the llvm.experimental.guard intrinsic |

1233 | /// at all? If this is false, we avoid doing work that will only help if |

1234 | /// thare are guards present in the IR. |

1235 | bool HasGuards; |

1236 | |

1237 | /// The target library information for the target we are targeting. |

1238 | TargetLibraryInfo &TLI; |

1239 | |

1240 | /// The tracker for \@llvm.assume intrinsics in this function. |

1241 | AssumptionCache &AC; |

1242 | |

1243 | /// The dominator tree. |

1244 | DominatorTree &DT; |

1245 | |

1246 | /// The loop information for the function we are currently analyzing. |

1247 | LoopInfo &LI; |

1248 | |

1249 | /// This SCEV is used to represent unknown trip counts and things. |

1250 | std::unique_ptr<SCEVCouldNotCompute> CouldNotCompute; |

1251 | |

1252 | /// The type for HasRecMap. |

1253 | using HasRecMapType = DenseMap<const SCEV *, bool>; |

1254 | |

1255 | /// This is a cache to record whether a SCEV contains any scAddRecExpr. |

1256 | HasRecMapType HasRecMap; |

1257 | |

1258 | /// The type for ExprValueMap. |

1259 | using ValueSetVector = SmallSetVector<Value *, 4>; |

1260 | using ExprValueMapType = DenseMap<const SCEV *, ValueSetVector>; |

1261 | |

1262 | /// ExprValueMap -- This map records the original values from which |

1263 | /// the SCEV expr is generated from. |

1264 | ExprValueMapType ExprValueMap; |

1265 | |

1266 | /// The type for ValueExprMap. |

1267 | using ValueExprMapType = |

1268 | DenseMap<SCEVCallbackVH, const SCEV *, DenseMapInfo<Value *>>; |

1269 | |

1270 | /// This is a cache of the values we have analyzed so far. |

1271 | ValueExprMapType ValueExprMap; |

1272 | |

1273 | /// Mark predicate values currently being processed by isImpliedCond. |

1274 | SmallPtrSet<const Value *, 6> PendingLoopPredicates; |

1275 | |

1276 | /// Mark SCEVUnknown Phis currently being processed by getRangeRef. |

1277 | SmallPtrSet<const PHINode *, 6> PendingPhiRanges; |

1278 | |

1279 | // Mark SCEVUnknown Phis currently being processed by isImpliedViaMerge. |

1280 | SmallPtrSet<const PHINode *, 6> PendingMerges; |

1281 | |

1282 | /// Set to true by isLoopBackedgeGuardedByCond when we're walking the set of |

1283 | /// conditions dominating the backedge of a loop. |

1284 | bool WalkingBEDominatingConds = false; |

1285 | |

1286 | /// Set to true by isKnownPredicateViaSplitting when we're trying to prove a |

1287 | /// predicate by splitting it into a set of independent predicates. |

1288 | bool ProvingSplitPredicate = false; |

1289 | |

1290 | /// Memoized values for the GetMinTrailingZeros |

1291 | DenseMap<const SCEV *, uint32_t> MinTrailingZerosCache; |

1292 | |

1293 | /// Return the Value set from which the SCEV expr is generated. |

1294 | ArrayRef<Value *> getSCEVValues(const SCEV *S); |

1295 | |

1296 | /// Private helper method for the GetMinTrailingZeros method |

1297 | uint32_t GetMinTrailingZerosImpl(const SCEV *S); |

1298 | |

1299 | /// Information about the number of loop iterations for which a loop exit's |

1300 | /// branch condition evaluates to the not-taken path. This is a temporary |

1301 | /// pair of exact and max expressions that are eventually summarized in |

1302 | /// ExitNotTakenInfo and BackedgeTakenInfo. |

1303 | struct ExitLimit { |

1304 | const SCEV *ExactNotTaken; // The exit is not taken exactly this many times |

1305 | const SCEV *MaxNotTaken; // The exit is not taken at most this many times |

1306 | |

1307 | // Not taken either exactly MaxNotTaken or zero times |

1308 | bool MaxOrZero = false; |

1309 | |

1310 | /// A set of predicate guards for this ExitLimit. The result is only valid |

1311 | /// if all of the predicates in \c Predicates evaluate to 'true' at |

1312 | /// run-time. |

1313 | SmallPtrSet<const SCEVPredicate *, 4> Predicates; |

1314 | |

1315 | void addPredicate(const SCEVPredicate *P) { |

1316 | assert(!isa<SCEVUnionPredicate>(P) && "Only add leaf predicates here!"); |

1317 | Predicates.insert(P); |

1318 | } |

1319 | |

1320 | /// Construct either an exact exit limit from a constant, or an unknown |

1321 | /// one from a SCEVCouldNotCompute. No other types of SCEVs are allowed |

1322 | /// as arguments and asserts enforce that internally. |

1323 | /*implicit*/ ExitLimit(const SCEV *E); |

1324 | |

1325 | ExitLimit( |

1326 | const SCEV *E, const SCEV *M, bool MaxOrZero, |

1327 | ArrayRef<const SmallPtrSetImpl<const SCEVPredicate *> *> PredSetList); |

1328 | |

1329 | ExitLimit(const SCEV *E, const SCEV *M, bool MaxOrZero, |

1330 | const SmallPtrSetImpl<const SCEVPredicate *> &PredSet); |

1331 | |

1332 | ExitLimit(const SCEV *E, const SCEV *M, bool MaxOrZero); |

1333 | |

1334 | /// Test whether this ExitLimit contains any computed information, or |

1335 | /// whether it's all SCEVCouldNotCompute values. |

1336 | bool hasAnyInfo() const { |

1337 | return !isa<SCEVCouldNotCompute>(ExactNotTaken) || |

1338 | !isa<SCEVCouldNotCompute>(MaxNotTaken); |

1339 | } |

1340 | |

1341 | /// Test whether this ExitLimit contains all information. |

1342 | bool hasFullInfo() const { |

1343 | return !isa<SCEVCouldNotCompute>(ExactNotTaken); |

1344 | } |

1345 | }; |

1346 | |

1347 | /// Information about the number of times a particular loop exit may be |

1348 | /// reached before exiting the loop. |

1349 | struct ExitNotTakenInfo { |

1350 | PoisoningVH<BasicBlock> ExitingBlock; |

1351 | const SCEV *ExactNotTaken; |

1352 | const SCEV *MaxNotTaken; |

1353 | SmallPtrSet<const SCEVPredicate *, 4> Predicates; |

1354 | |

1355 | explicit ExitNotTakenInfo(PoisoningVH<BasicBlock> ExitingBlock, |

1356 | const SCEV *ExactNotTaken, |

1357 | const SCEV *MaxNotTaken, |

1358 | const SmallPtrSet<const SCEVPredicate *, 4> &Predicates) |

1359 | : ExitingBlock(ExitingBlock), ExactNotTaken(ExactNotTaken), |

1360 | MaxNotTaken(ExactNotTaken), Predicates(Predicates) {} |

1361 | |

1362 | bool hasAlwaysTruePredicate() const { |

1363 | return Predicates.empty(); |

1364 | } |

1365 | }; |

1366 | |

1367 | /// Information about the backedge-taken count of a loop. This currently |

1368 | /// includes an exact count and a maximum count. |

1369 | /// |

1370 | class BackedgeTakenInfo { |

1371 | friend class ScalarEvolution; |

1372 | |

1373 | /// A list of computable exits and their not-taken counts. Loops almost |

1374 | /// never have more than one computable exit. |

1375 | SmallVector<ExitNotTakenInfo, 1> ExitNotTaken; |

1376 | |

1377 | /// Expression indicating the least constant maximum backedge-taken count of |

1378 | /// the loop that is known, or a SCEVCouldNotCompute. This expression is |

1379 | /// only valid if the redicates associated with all loop exits are true. |

1380 | const SCEV *ConstantMax = nullptr; |

1381 | |

1382 | /// Indicating if \c ExitNotTaken has an element for every exiting block in |

1383 | /// the loop. |

1384 | bool IsComplete = false; |

1385 | |

1386 | /// Expression indicating the least maximum backedge-taken count of the loop |

1387 | /// that is known, or a SCEVCouldNotCompute. Lazily computed on first query. |

1388 | const SCEV *SymbolicMax = nullptr; |

1389 | |

1390 | /// True iff the backedge is taken either exactly Max or zero times. |

1391 | bool MaxOrZero = false; |

1392 | |

1393 | bool isComplete() const { return IsComplete; } |

1394 | const SCEV *getConstantMax() const { return ConstantMax; } |

1395 | |

1396 | public: |

1397 | BackedgeTakenInfo() = default; |

1398 | BackedgeTakenInfo(BackedgeTakenInfo &&) = default; |

1399 | BackedgeTakenInfo &operator=(BackedgeTakenInfo &&) = default; |

1400 | |

1401 | using EdgeExitInfo = std::pair<BasicBlock *, ExitLimit>; |

1402 | |

1403 | /// Initialize BackedgeTakenInfo from a list of exact exit counts. |

1404 | BackedgeTakenInfo(ArrayRef<EdgeExitInfo> ExitCounts, bool IsComplete, |

1405 | const SCEV *ConstantMax, bool MaxOrZero); |

1406 | |

1407 | /// Test whether this BackedgeTakenInfo contains any computed information, |

1408 | /// or whether it's all SCEVCouldNotCompute values. |

1409 | bool hasAnyInfo() const { |

1410 | return !ExitNotTaken.empty() || |

1411 | !isa<SCEVCouldNotCompute>(getConstantMax()); |

1412 | } |

1413 | |

1414 | /// Test whether this BackedgeTakenInfo contains complete information. |

1415 | bool hasFullInfo() const { return isComplete(); } |

1416 | |

1417 | /// Return an expression indicating the exact *backedge-taken* |

1418 | /// count of the loop if it is known or SCEVCouldNotCompute |

1419 | /// otherwise. If execution makes it to the backedge on every |

1420 | /// iteration (i.e. there are no abnormal exists like exception |

1421 | /// throws and thread exits) then this is the number of times the |

1422 | /// loop header will execute minus one. |

1423 | /// |

1424 | /// If the SCEV predicate associated with the answer can be different |

1425 | /// from AlwaysTrue, we must add a (non null) Predicates argument. |

1426 | /// The SCEV predicate associated with the answer will be added to |

1427 | /// Predicates. A run-time check needs to be emitted for the SCEV |

1428 | /// predicate in order for the answer to be valid. |

1429 | /// |

1430 | /// Note that we should always know if we need to pass a predicate |

1431 | /// argument or not from the way the ExitCounts vector was computed. |

1432 | /// If we allowed SCEV predicates to be generated when populating this |

1433 | /// vector, this information can contain them and therefore a |

1434 | /// SCEVPredicate argument should be added to getExact. |

1435 | const SCEV *getExact(const Loop *L, ScalarEvolution *SE, |

1436 | SmallVector<const SCEVPredicate *, 4> *Predicates = nullptr) const; |

1437 | |

1438 | /// Return the number of times this loop exit may fall through to the back |

1439 | /// edge, or SCEVCouldNotCompute. The loop is guaranteed not to exit via |

1440 | /// this block before this number of iterations, but may exit via another |

1441 | /// block. |

1442 | const SCEV *getExact(const BasicBlock *ExitingBlock, |

1443 | ScalarEvolution *SE) const; |

1444 | |

1445 | /// Get the constant max backedge taken count for the loop. |

1446 | const SCEV *getConstantMax(ScalarEvolution *SE) const; |

1447 | |

1448 | /// Get the constant max backedge taken count for the particular loop exit. |

1449 | const SCEV *getConstantMax(const BasicBlock *ExitingBlock, |

1450 | ScalarEvolution *SE) const; |

1451 | |

1452 | /// Get the symbolic max backedge taken count for the loop. |

1453 | const SCEV *getSymbolicMax(const Loop *L, ScalarEvolution *SE); |

1454 | |

1455 | /// Return true if the number of times this backedge is taken is either the |

1456 | /// value returned by getConstantMax or zero. |

1457 | bool isConstantMaxOrZero(ScalarEvolution *SE) const; |

1458 | }; |

1459 | |

1460 | /// Cache the backedge-taken count of the loops for this function as they |

1461 | /// are computed. |

1462 | DenseMap<const Loop *, BackedgeTakenInfo> BackedgeTakenCounts; |

1463 | |

1464 | /// Cache the predicated backedge-taken count of the loops for this |

1465 | /// function as they are computed. |

1466 | DenseMap<const Loop *, BackedgeTakenInfo> PredicatedBackedgeTakenCounts; |

1467 | |

1468 | /// Loops whose backedge taken counts directly use this non-constant SCEV. |

1469 | DenseMap<const SCEV *, SmallPtrSet<PointerIntPair<const Loop *, 1, bool>, 4>> |

1470 | BECountUsers; |

1471 | |

1472 | /// This map contains entries for all of the PHI instructions that we |

1473 | /// attempt to compute constant evolutions for. This allows us to avoid |

1474 | /// potentially expensive recomputation of these properties. An instruction |

1475 | /// maps to null if we are unable to compute its exit value. |

1476 | DenseMap<PHINode *, Constant *> ConstantEvolutionLoopExitValue; |

1477 | |

1478 | /// This map contains entries for all the expressions that we attempt to |

1479 | /// compute getSCEVAtScope information for, which can be expensive in |

1480 | /// extreme cases. |

1481 | DenseMap<const SCEV *, SmallVector<std::pair<const Loop *, const SCEV *>, 2>> |

1482 | ValuesAtScopes; |

1483 | |

1484 | /// Reverse map for invalidation purposes: Stores of which SCEV and which |

1485 | /// loop this is the value-at-scope of. |

1486 | DenseMap<const SCEV *, SmallVector<std::pair<const Loop *, const SCEV *>, 2>> |

1487 | ValuesAtScopesUsers; |

1488 | |

1489 | /// Memoized computeLoopDisposition results. |

1490 | DenseMap<const SCEV *, |

1491 | SmallVector<PointerIntPair<const Loop *, 2, LoopDisposition>, 2>> |

1492 | LoopDispositions; |

1493 | |

1494 | struct LoopProperties { |

1495 | /// Set to true if the loop contains no instruction that can abnormally exit |

1496 | /// the loop (i.e. via throwing an exception, by terminating the thread |

1497 | /// cleanly or by infinite looping in a called function). Strictly |

1498 | /// speaking, the last one is not leaving the loop, but is identical to |

1499 | /// leaving the loop for reasoning about undefined behavior. |

1500 | bool HasNoAbnormalExits; |

1501 | |

1502 | /// Set to true if the loop contains no instruction that can have side |

1503 | /// effects (i.e. via throwing an exception, volatile or atomic access). |

1504 | bool HasNoSideEffects; |

1505 | }; |

1506 | |

1507 | /// Cache for \c getLoopProperties. |

1508 | DenseMap<const Loop *, LoopProperties> LoopPropertiesCache; |

1509 | |

1510 | /// Return a \c LoopProperties instance for \p L, creating one if necessary. |

1511 | LoopProperties getLoopProperties(const Loop *L); |

1512 | |

1513 | bool loopHasNoSideEffects(const Loop *L) { |

1514 | return getLoopProperties(L).HasNoSideEffects; |

1515 | } |

1516 | |

1517 | /// Compute a LoopDisposition value. |

1518 | LoopDisposition computeLoopDisposition(const SCEV *S, const Loop *L); |

1519 | |

1520 | /// Memoized computeBlockDisposition results. |

1521 | DenseMap< |

1522 | const SCEV *, |

1523 | SmallVector<PointerIntPair<const BasicBlock *, 2, BlockDisposition>, 2>> |

1524 | BlockDispositions; |

1525 | |

1526 | /// Compute a BlockDisposition value. |

1527 | BlockDisposition computeBlockDisposition(const SCEV *S, const BasicBlock *BB); |

1528 | |

1529 | /// Stores all SCEV that use a given SCEV as its direct operand. |

1530 | DenseMap<const SCEV *, SmallPtrSet<const SCEV *, 8> > SCEVUsers; |

1531 | |

1532 | /// Memoized results from getRange |

1533 | DenseMap<const SCEV *, ConstantRange> UnsignedRanges; |

1534 | |

1535 | /// Memoized results from getRange |

1536 | DenseMap<const SCEV *, ConstantRange> SignedRanges; |

1537 | |

1538 | /// Used to parameterize getRange |

1539 | enum RangeSignHint { HINT_RANGE_UNSIGNED, HINT_RANGE_SIGNED }; |

1540 | |

1541 | /// Set the memoized range for the given SCEV. |

1542 | const ConstantRange &setRange(const SCEV *S, RangeSignHint Hint, |

1543 | ConstantRange CR) { |

1544 | DenseMap<const SCEV *, ConstantRange> &Cache = |

1545 | Hint == HINT_RANGE_UNSIGNED ? UnsignedRanges : SignedRanges; |

1546 | |

1547 | auto Pair = Cache.try_emplace(S, std::move(CR)); |

1548 | if (!Pair.second) |

1549 | Pair.first->second = std::move(CR); |

1550 | return Pair.first->second; |

1551 | } |

1552 | |

1553 | /// Determine the range for a particular SCEV. |

1554 | /// NOTE: This returns a reference to an entry in a cache. It must be |

1555 | /// copied if its needed for longer. |

1556 | const ConstantRange &getRangeRef(const SCEV *S, RangeSignHint Hint); |

1557 | |

1558 | /// Determines the range for the affine SCEVAddRecExpr {\p Start,+,\p Step}. |

1559 | /// Helper for \c getRange. |

1560 | ConstantRange getRangeForAffineAR(const SCEV *Start, const SCEV *Step, |

1561 | const SCEV *MaxBECount, unsigned BitWidth); |

1562 | |

1563 | /// Determines the range for the affine non-self-wrapping SCEVAddRecExpr {\p |

1564 | /// Start,+,\p Step}<nw>. |

1565 | ConstantRange getRangeForAffineNoSelfWrappingAR(const SCEVAddRecExpr *AddRec, |

1566 | const SCEV *MaxBECount, |

1567 | unsigned BitWidth, |

1568 | RangeSignHint SignHint); |

1569 | |

1570 | /// Try to compute a range for the affine SCEVAddRecExpr {\p Start,+,\p |

1571 | /// Step} by "factoring out" a ternary expression from the add recurrence. |

1572 | /// Helper called by \c getRange. |

1573 | ConstantRange getRangeViaFactoring(const SCEV *Start, const SCEV *Step, |

1574 | const SCEV *MaxBECount, unsigned BitWidth); |

1575 | |

1576 | /// If the unknown expression U corresponds to a simple recurrence, return |

1577 | /// a constant range which represents the entire recurrence. Note that |

1578 | /// *add* recurrences with loop invariant steps aren't represented by |

1579 | /// SCEVUnknowns and thus don't use this mechanism. |

1580 | ConstantRange getRangeForUnknownRecurrence(const SCEVUnknown *U); |

1581 | |

1582 | /// We know that there is no SCEV for the specified value. Analyze the |

1583 | /// expression recursively. |

1584 | const SCEV *createSCEV(Value *V); |

1585 | |

1586 | /// We know that there is no SCEV for the specified value. Create a new SCEV |

1587 | /// for \p V iteratively. |

1588 | const SCEV *createSCEVIter(Value *V); |

1589 | /// Collect operands of \p V for which SCEV expressions should be constructed |

1590 | /// first. Returns a SCEV directly if it can be constructed trivially for \p |

1591 | /// V. |

1592 | const SCEV *getOperandsToCreate(Value *V, SmallVectorImpl<Value *> &Ops); |

1593 | |

1594 | /// Provide the special handling we need to analyze PHI SCEVs. |

1595 | const SCEV *createNodeForPHI(PHINode *PN); |

1596 | |

1597 | /// Helper function called from createNodeForPHI. |

1598 | const SCEV *createAddRecFromPHI(PHINode *PN); |

1599 | |

1600 | /// A helper function for createAddRecFromPHI to handle simple cases. |

1601 | const SCEV *createSimpleAffineAddRec(PHINode *PN, Value *BEValueV, |

1602 | Value *StartValueV); |

1603 | |

1604 | /// Helper function called from createNodeForPHI. |

1605 | const SCEV *createNodeFromSelectLikePHI(PHINode *PN); |

1606 | |

1607 | /// Provide special handling for a select-like instruction (currently this |

1608 | /// is either a select instruction or a phi node). \p I is the instruction |

1609 | /// being processed, and it is assumed equivalent to "Cond ? TrueVal : |

1610 | /// FalseVal". |

1611 | const SCEV *createNodeForSelectOrPHIInstWithICmpInstCond(Instruction *I, |

1612 | ICmpInst *Cond, |

1613 | Value *TrueVal, |

1614 | Value *FalseVal); |

1615 | |

1616 | /// See if we can model this select-like instruction via umin_seq expression. |

1617 | const SCEV *createNodeForSelectOrPHIViaUMinSeq(Value *I, Value *Cond, |

1618 | Value *TrueVal, |

1619 | Value *FalseVal); |

1620 | |

1621 | /// Given a value \p V, which is a select-like instruction (currently this is |

1622 | /// either a select instruction or a phi node), which is assumed equivalent to |

1623 | /// Cond ? TrueVal : FalseVal |

1624 | /// see if we can model it as a SCEV expression. |

1625 | const SCEV *createNodeForSelectOrPHI(Value *V, Value *Cond, Value *TrueVal, |

1626 | Value *FalseVal); |

1627 | |

1628 | /// Provide the special handling we need to analyze GEP SCEVs. |

1629 | const SCEV *createNodeForGEP(GEPOperator *GEP); |

1630 | |

1631 | /// Implementation code for getSCEVAtScope; called at most once for each |

1632 | /// SCEV+Loop pair. |

1633 | const SCEV *computeSCEVAtScope(const SCEV *S, const Loop *L); |

1634 | |

1635 | /// Return the BackedgeTakenInfo for the given loop, lazily computing new |

1636 | /// values if the loop hasn't been analyzed yet. The returned result is |

1637 | /// guaranteed not to be predicated. |

1638 | BackedgeTakenInfo &getBackedgeTakenInfo(const Loop *L); |

1639 | |

1640 | /// Similar to getBackedgeTakenInfo, but will add predicates as required |

1641 | /// with the purpose of returning complete information. |

1642 | const BackedgeTakenInfo &getPredicatedBackedgeTakenInfo(const Loop *L); |

1643 | |

1644 | /// Compute the number of times the specified loop will iterate. |

1645 | /// If AllowPredicates is set, we will create new SCEV predicates as |

1646 | /// necessary in order to return an exact answer. |

1647 | BackedgeTakenInfo computeBackedgeTakenCount(const Loop *L, |

1648 | bool AllowPredicates = false); |

1649 | |

1650 | /// Compute the number of times the backedge of the specified loop will |

1651 | /// execute if it exits via the specified block. If AllowPredicates is set, |

1652 | /// this call will try to use a minimal set of SCEV predicates in order to |

1653 | /// return an exact answer. |

1654 | ExitLimit computeExitLimit(const Loop *L, BasicBlock *ExitingBlock, |

1655 | bool AllowPredicates = false); |

1656 | |

1657 | /// Compute the number of times the backedge of the specified loop will |

1658 | /// execute if its exit condition were a conditional branch of ExitCond. |

1659 | /// |

1660 | /// \p ControlsExit is true if ExitCond directly controls the exit |

1661 | /// branch. In this case, we can assume that the loop exits only if the |

1662 | /// condition is true and can infer that failing to meet the condition prior |

1663 | /// to integer wraparound results in undefined behavior. |

1664 | /// |

1665 | /// If \p AllowPredicates is set, this call will try to use a minimal set of |

1666 | /// SCEV predicates in order to return an exact answer. |

1667 | ExitLimit computeExitLimitFromCond(const Loop *L, Value *ExitCond, |

1668 | bool ExitIfTrue, bool ControlsExit, |

1669 | bool AllowPredicates = false); |

1670 | |

1671 | /// Return a symbolic upper bound for the backedge taken count of the loop. |

1672 | /// This is more general than getConstantMaxBackedgeTakenCount as it returns |

1673 | /// an arbitrary expression as opposed to only constants. |

1674 | const SCEV *computeSymbolicMaxBackedgeTakenCount(const Loop *L); |

1675 | |

1676 | // Helper functions for computeExitLimitFromCond to avoid exponential time |

1677 | // complexity. |

1678 | |

1679 | class ExitLimitCache { |

1680 | // It may look like we need key on the whole (L, ExitIfTrue, ControlsExit, |

1681 | // AllowPredicates) tuple, but recursive calls to |

1682 | // computeExitLimitFromCondCached from computeExitLimitFromCondImpl only |

1683 | // vary the in \c ExitCond and \c ControlsExit parameters. We remember the |

1684 | // initial values of the other values to assert our assumption. |

1685 | SmallDenseMap<PointerIntPair<Value *, 1>, ExitLimit> TripCountMap; |

1686 | |

1687 | const Loop *L; |

1688 | bool ExitIfTrue; |

1689 | bool AllowPredicates; |

1690 | |

1691 | public: |

1692 | ExitLimitCache(const Loop *L, bool ExitIfTrue, bool AllowPredicates) |

1693 | : L(L), ExitIfTrue(ExitIfTrue), AllowPredicates(AllowPredicates) {} |

1694 | |

1695 | Optional<ExitLimit> find(const Loop *L, Value *ExitCond, bool ExitIfTrue, |

1696 | bool ControlsExit, bool AllowPredicates); |

1697 | |

1698 | void insert(const Loop *L, Value *ExitCond, bool ExitIfTrue, |

1699 | bool ControlsExit, bool AllowPredicates, const ExitLimit &EL); |

1700 | }; |

1701 | |

1702 | using ExitLimitCacheTy = ExitLimitCache; |

1703 | |

1704 | ExitLimit computeExitLimitFromCondCached(ExitLimitCacheTy &Cache, |

1705 | const Loop *L, Value *ExitCond, |

1706 | bool ExitIfTrue, |

1707 | bool ControlsExit, |

1708 | bool AllowPredicates); |

1709 | ExitLimit computeExitLimitFromCondImpl(ExitLimitCacheTy &Cache, const Loop *L, |

1710 | Value *ExitCond, bool ExitIfTrue, |

1711 | bool ControlsExit, |

1712 | bool AllowPredicates); |

1713 | Optional<ScalarEvolution::ExitLimit> |

1714 | computeExitLimitFromCondFromBinOp(ExitLimitCacheTy &Cache, const Loop *L, |

1715 | Value *ExitCond, bool ExitIfTrue, |

1716 | bool ControlsExit, bool AllowPredicates); |

1717 | |

1718 | /// Compute the number of times the backedge of the specified loop will |

1719 | /// execute if its exit condition were a conditional branch of the ICmpInst |

1720 | /// ExitCond and ExitIfTrue. If AllowPredicates is set, this call will try |

1721 | /// to use a minimal set of SCEV predicates in order to return an exact |

1722 | /// answer. |

1723 | ExitLimit computeExitLimitFromICmp(const Loop *L, ICmpInst *ExitCond, |

1724 | bool ExitIfTrue, |

1725 | bool IsSubExpr, |

1726 | bool AllowPredicates = false); |

1727 | |

1728 | /// Variant of previous which takes the components representing an ICmp |

1729 | /// as opposed to the ICmpInst itself. Note that the prior version can |

1730 | /// return more precise results in some cases and is preferred when caller |

1731 | /// has a materialized ICmp. |

1732 | ExitLimit computeExitLimitFromICmp(const Loop *L, ICmpInst::Predicate Pred, |

1733 | const SCEV *LHS, const SCEV *RHS, |

1734 | bool IsSubExpr, |

1735 | bool AllowPredicates = false); |

1736 | |

1737 | /// Compute the number of times the backedge of the specified loop will |

1738 | /// execute if its exit condition were a switch with a single exiting case |

1739 | /// to ExitingBB. |

1740 | ExitLimit computeExitLimitFromSingleExitSwitch(const Loop *L, |

1741 | SwitchInst *Switch, |

1742 | BasicBlock *ExitingBB, |

1743 | bool IsSubExpr); |

1744 | |

1745 | /// Compute the exit limit of a loop that is controlled by a |

1746 | /// "(IV >> 1) != 0" type comparison. We cannot compute the exact trip |

1747 | /// count in these cases (since SCEV has no way of expressing them), but we |

1748 | /// can still sometimes compute an upper bound. |

1749 | /// |

1750 | /// Return an ExitLimit for a loop whose backedge is guarded by `LHS Pred |

1751 | /// RHS`. |

1752 | ExitLimit computeShiftCompareExitLimit(Value *LHS, Value *RHS, const Loop *L, |

1753 | ICmpInst::Predicate Pred); |

1754 | |

1755 | /// If the loop is known to execute a constant number of times (the |

1756 | /// condition evolves only from constants), try to evaluate a few iterations |

1757 | /// of the loop until we get the exit condition gets a value of ExitWhen |

1758 | /// (true or false). If we cannot evaluate the exit count of the loop, |

1759 | /// return CouldNotCompute. |

1760 | const SCEV *computeExitCountExhaustively(const Loop *L, Value *Cond, |

1761 | bool ExitWhen); |

1762 | |

1763 | /// Return the number of times an exit condition comparing the specified |

1764 | /// value to zero will execute. If not computable, return CouldNotCompute. |

1765 | /// If AllowPredicates is set, this call will try to use a minimal set of |

1766 | /// SCEV predicates in order to return an exact answer. |

1767 | ExitLimit howFarToZero(const SCEV *V, const Loop *L, bool IsSubExpr, |

1768 | bool AllowPredicates = false); |

1769 | |

1770 | /// Return the number of times an exit condition checking the specified |

1771 | /// value for nonzero will execute. If not computable, return |

1772 | /// CouldNotCompute. |

1773 | ExitLimit howFarToNonZero(const SCEV *V, const Loop *L); |

1774 | |

1775 | /// Return the number of times an exit condition containing the specified |

1776 | /// less-than comparison will execute. If not computable, return |

1777 | /// CouldNotCompute. |

1778 | /// |

1779 | /// \p isSigned specifies whether the less-than is signed. |

1780 | /// |

1781 | /// \p ControlsExit is true when the LHS < RHS condition directly controls |

1782 | /// the branch (loops exits only if condition is true). In this case, we can |

1783 | /// use NoWrapFlags to skip overflow checks. |

1784 | /// |

1785 | /// If \p AllowPredicates is set, this call will try to use a minimal set of |

1786 | /// SCEV predicates in order to return an exact answer. |

1787 | ExitLimit howManyLessThans(const SCEV *LHS, const SCEV *RHS, const Loop *L, |

1788 | bool isSigned, bool ControlsExit, |

1789 | bool AllowPredicates = false); |

1790 | |

1791 | ExitLimit howManyGreaterThans(const SCEV *LHS, const SCEV *RHS, const Loop *L, |

1792 | bool isSigned, bool IsSubExpr, |

1793 | bool AllowPredicates = false); |

1794 | |

1795 | /// Return a predecessor of BB (which may not be an immediate predecessor) |

1796 | /// which has exactly one successor from which BB is reachable, or null if |

1797 | /// no such block is found. |

1798 | std::pair<const BasicBlock *, const BasicBlock *> |

1799 | getPredecessorWithUniqueSuccessorForBB(const BasicBlock *BB) const; |

1800 | |

1801 | /// Test whether the condition described by Pred, LHS, and RHS is true |

1802 | /// whenever the given FoundCondValue value evaluates to true in given |

1803 | /// Context. If Context is nullptr, then the found predicate is true |

1804 | /// everywhere. LHS and FoundLHS may have different type width. |

1805 | bool isImpliedCond(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, |

1806 | const Value *FoundCondValue, bool Inverse, |

1807 | const Instruction *Context = nullptr); |

1808 | |

1809 | /// Test whether the condition described by Pred, LHS, and RHS is true |

1810 | /// whenever the given FoundCondValue value evaluates to true in given |

1811 | /// Context. If Context is nullptr, then the found predicate is true |

1812 | /// everywhere. LHS and FoundLHS must have same type width. |

1813 | bool isImpliedCondBalancedTypes(ICmpInst::Predicate Pred, const SCEV *LHS, |

1814 | const SCEV *RHS, |

1815 | ICmpInst::Predicate FoundPred, |

1816 | const SCEV *FoundLHS, const SCEV *FoundRHS, |

1817 | const Instruction *CtxI); |

1818 | |

1819 | /// Test whether the condition described by Pred, LHS, and RHS is true |

1820 | /// whenever the condition described by FoundPred, FoundLHS, FoundRHS is |

1821 | /// true in given Context. If Context is nullptr, then the found predicate is |

1822 | /// true everywhere. |

1823 | bool isImpliedCond(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, |

1824 | ICmpInst::Predicate FoundPred, const SCEV *FoundLHS, |

1825 | const SCEV *FoundRHS, |

1826 | const Instruction *Context = nullptr); |

1827 | |

1828 | /// Test whether the condition described by Pred, LHS, and RHS is true |

1829 | /// whenever the condition described by Pred, FoundLHS, and FoundRHS is |

1830 | /// true in given Context. If Context is nullptr, then the found predicate is |

1831 | /// true everywhere. |

1832 | bool isImpliedCondOperands(ICmpInst::Predicate Pred, const SCEV *LHS, |

1833 | const SCEV *RHS, const SCEV *FoundLHS, |

1834 | const SCEV *FoundRHS, |

1835 | const Instruction *Context = nullptr); |

1836 | |

1837 | /// Test whether the condition described by Pred, LHS, and RHS is true |

1838 | /// whenever the condition described by Pred, FoundLHS, and FoundRHS is |

1839 | /// true. Here LHS is an operation that includes FoundLHS as one of its |

1840 | /// arguments. |

1841 | bool isImpliedViaOperations(ICmpInst::Predicate Pred, |

1842 | const SCEV *LHS, const SCEV *RHS, |

1843 | const SCEV *FoundLHS, const SCEV *FoundRHS, |

1844 | unsigned Depth = 0); |

1845 | |

1846 | /// Test whether the condition described by Pred, LHS, and RHS is true. |

1847 | /// Use only simple non-recursive types of checks, such as range analysis etc. |

1848 | bool isKnownViaNonRecursiveReasoning(ICmpInst::Predicate Pred, |

1849 | const SCEV *LHS, const SCEV *RHS); |

1850 | |

1851 | /// Test whether the condition described by Pred, LHS, and RHS is true |

1852 | /// whenever the condition described by Pred, FoundLHS, and FoundRHS is |

1853 | /// true. |

1854 | bool isImpliedCondOperandsHelper(ICmpInst::Predicate Pred, const SCEV *LHS, |

1855 | const SCEV *RHS, const SCEV *FoundLHS, |

1856 | const SCEV *FoundRHS); |

1857 | |

1858 | /// Test whether the condition described by Pred, LHS, and RHS is true |

1859 | /// whenever the condition described by Pred, FoundLHS, and FoundRHS is |

1860 | /// true. Utility function used by isImpliedCondOperands. Tries to get |

1861 | /// cases like "X `sgt` 0 => X - 1 `sgt` -1". |

1862 | bool isImpliedCondOperandsViaRanges(ICmpInst::Predicate Pred, const SCEV *LHS, |

1863 | const SCEV *RHS, const SCEV *FoundLHS, |

1864 | const SCEV *FoundRHS); |

1865 | |

1866 | /// Return true if the condition denoted by \p LHS \p Pred \p RHS is implied |

1867 | /// by a call to @llvm.experimental.guard in \p BB. |

1868 | bool isImpliedViaGuard(const BasicBlock *BB, ICmpInst::Predicate Pred, |

1869 | const SCEV *LHS, const SCEV *RHS); |

1870 | |

1871 | /// Test whether the condition described by Pred, LHS, and RHS is true |

1872 | /// whenever the condition described by Pred, FoundLHS, and FoundRHS is |

1873 | /// true. |

1874 | /// |

1875 | /// This routine tries to rule out certain kinds of integer overflow, and |

1876 | /// then tries to reason about arithmetic properties of the predicates. |

1877 | bool isImpliedCondOperandsViaNoOverflow(ICmpInst::Predicate Pred, |

1878 | const SCEV *LHS, const SCEV *RHS, |

1879 | const SCEV *FoundLHS, |

1880 | const SCEV *FoundRHS); |

1881 | |

1882 | /// Test whether the condition described by Pred, LHS, and RHS is true |

1883 | /// whenever the condition described by Pred, FoundLHS, and FoundRHS is |

1884 | /// true. |

1885 | /// |

1886 | /// This routine tries to weaken the known condition basing on fact that |

1887 | /// FoundLHS is an AddRec. |

1888 | bool isImpliedCondOperandsViaAddRecStart(ICmpInst::Predicate Pred, |

1889 | const SCEV *LHS, const SCEV *RHS, |

1890 | const SCEV *FoundLHS, |

1891 | const SCEV *FoundRHS, |

1892 | const Instruction *CtxI); |

1893 | |

1894 | /// Test whether the condition described by Pred, LHS, and RHS is true |

1895 | /// whenever the condition described by Pred, FoundLHS, and FoundRHS is |

1896 | /// true. |

1897 | /// |

1898 | /// This routine tries to figure out predicate for Phis which are SCEVUnknown |

1899 | /// if it is true for every possible incoming value from their respective |

1900 | /// basic blocks. |

1901 | bool isImpliedViaMerge(ICmpInst::Predicate Pred, |

1902 | const SCEV *LHS, const SCEV *RHS, |

1903 | const SCEV *FoundLHS, const SCEV *FoundRHS, |

1904 | unsigned Depth); |

1905 | |

1906 | /// Test whether the condition described by Pred, LHS, and RHS is true |

1907 | /// whenever the condition described by Pred, FoundLHS, and FoundRHS is |

1908 | /// true. |

1909 | /// |

1910 | /// This routine tries to reason about shifts. |

1911 | bool isImpliedCondOperandsViaShift(ICmpInst::Predicate Pred, const SCEV *LHS, |

1912 | const SCEV *RHS, const SCEV *FoundLHS, |

1913 | const SCEV *FoundRHS); |

1914 | |

1915 | /// If we know that the specified Phi is in the header of its containing |

1916 | /// loop, we know the loop executes a constant number of times, and the PHI |

1917 | /// node is just a recurrence involving constants, fold it. |

1918 | Constant *getConstantEvolutionLoopExitValue(PHINode *PN, const APInt &BEs, |

1919 | const Loop *L); |

1920 | |

1921 | /// Test if the given expression is known to satisfy the condition described |

1922 | /// by Pred and the known constant ranges of LHS and RHS. |

1923 | bool isKnownPredicateViaConstantRanges(ICmpInst::Predicate Pred, |

1924 | const SCEV *LHS, const SCEV *RHS); |

1925 | |

1926 | /// Try to prove the condition described by "LHS Pred RHS" by ruling out |

1927 | /// integer overflow. |

1928 | /// |

1929 | /// For instance, this will return true for "A s< (A + C)<nsw>" if C is |

1930 | /// positive. |

1931 | bool isKnownPredicateViaNoOverflow(ICmpInst::Predicate Pred, const SCEV *LHS, |

1932 | const SCEV *RHS); |

1933 | |

1934 | /// Try to split Pred LHS RHS into logical conjunctions (and's) and try to |

1935 | /// prove them individually. |

1936 | bool isKnownPredicateViaSplitting(ICmpInst::Predicate Pred, const SCEV *LHS, |

1937 | const SCEV *RHS); |

1938 | |

1939 | /// Try to match the Expr as "(L + R)<Flags>". |

1940 | bool splitBinaryAdd(const SCEV *Expr, const SCEV *&L, const SCEV *&R, |

1941 | SCEV::NoWrapFlags &Flags); |

1942 | |

1943 | /// Forget predicated/non-predicated backedge taken counts for the given loop. |

1944 | void forgetBackedgeTakenCounts(const Loop *L, bool Predicated); |

1945 | |

1946 | /// Drop memoized information for all \p SCEVs. |

1947 | void forgetMemoizedResults(ArrayRef<const SCEV *> SCEVs); |

1948 | |

1949 | /// Helper for forgetMemoizedResults. |

1950 | void forgetMemoizedResultsImpl(const SCEV *S); |

1951 | |

1952 | /// Return an existing SCEV for V if there is one, otherwise return nullptr. |

1953 | const SCEV *getExistingSCEV(Value *V); |

1954 | |

1955 | /// Erase Value from ValueExprMap and ExprValueMap. |

1956 | void eraseValueFromMap(Value *V); |

1957 | |

1958 | /// Insert V to S mapping into ValueExprMap and ExprValueMap. |

1959 | void insertValueToMap(Value *V, const SCEV *S); |

1960 | |

1961 | /// Return false iff given SCEV contains a SCEVUnknown with NULL value- |

1962 | /// pointer. |

1963 | bool checkValidity(const SCEV *S) const; |

1964 | |

1965 | /// Return true if `ExtendOpTy`({`Start`,+,`Step`}) can be proved to be |

1966 | /// equal to {`ExtendOpTy`(`Start`),+,`ExtendOpTy`(`Step`)}. This is |

1967 | /// equivalent to proving no signed (resp. unsigned) wrap in |

1968 | /// {`Start`,+,`Step`} if `ExtendOpTy` is `SCEVSignExtendExpr` |

1969 | /// (resp. `SCEVZeroExtendExpr`). |

1970 | template <typename ExtendOpTy> |

1971 | bool proveNoWrapByVaryingStart(const SCEV *Start, const SCEV *Step, |

1972 | const Loop *L); |

1973 | |

1974 | /// Try to prove NSW or NUW on \p AR relying on ConstantRange manipulation. |

1975 | SCEV::NoWrapFlags proveNoWrapViaConstantRanges(const SCEVAddRecExpr *AR); |

1976 | |

1977 | /// Try to prove NSW on \p AR by proving facts about conditions known on |

1978 | /// entry and backedge. |

1979 | SCEV::NoWrapFlags proveNoSignedWrapViaInduction(const SCEVAddRecExpr *AR); |

1980 | |

1981 | /// Try to prove NUW on \p AR by proving facts about conditions known on |

1982 | /// entry and backedge. |

1983 | SCEV::NoWrapFlags proveNoUnsignedWrapViaInduction(const SCEVAddRecExpr *AR); |

1984 | |

1985 | Optional<MonotonicPredicateType> |

1986 | getMonotonicPredicateTypeImpl(const SCEVAddRecExpr *LHS, |

1987 | ICmpInst::Predicate Pred); |

1988 | |

1989 | /// Return SCEV no-wrap flags that can be proven based on reasoning about |

1990 | /// how poison produced from no-wrap flags on this value (e.g. a nuw add) |

1991 | /// would trigger undefined behavior on overflow. |

1992 | SCEV::NoWrapFlags getNoWrapFlagsFromUB(const Value *V); |

1993 | |

1994 | /// Return a scope which provides an upper bound on the defining scope of |

1995 | /// 'S'. Specifically, return the first instruction in said bounding scope. |

1996 | /// Return nullptr if the scope is trivial (function entry). |

1997 | /// (See scope definition rules associated with flag discussion above) |

1998 | const Instruction *getNonTrivialDefiningScopeBound(const SCEV *S); |

1999 | |

2000 | /// Return a scope which provides an upper bound on the defining scope for |

2001 | /// a SCEV with the operands in Ops. The outparam Precise is set if the |

2002 | /// bound found is a precise bound (i.e. must be the defining scope.) |

2003 | const Instruction *getDefiningScopeBound(ArrayRef<const SCEV *> Ops, |

2004 | bool &Precise); |

2005 | |

2006 | /// Wrapper around the above for cases which don't care if the bound |

2007 | /// is precise. |

2008 | const Instruction *getDefiningScopeBound(ArrayRef<const SCEV *> Ops); |

2009 | |

2010 | /// Given two instructions in the same function, return true if we can |

2011 | /// prove B must execute given A executes. |

2012 | bool isGuaranteedToTransferExecutionTo(const Instruction *A, |

2013 | const Instruction *B); |

2014 | |

2015 | /// Return true if the SCEV corresponding to \p I is never poison. Proving |

2016 | /// this is more complex than proving that just \p I is never poison, since |

2017 | /// SCEV commons expressions across control flow, and you can have cases |

2018 | /// like: |

2019 | /// |

2020 | /// idx0 = a + b; |

2021 | /// ptr[idx0] = 100; |

2022 | /// if (<condition>) { |

2023 | /// idx1 = a +nsw b; |

2024 | /// ptr[idx1] = 200; |

2025 | /// } |

2026 | /// |

2027 | /// where the SCEV expression (+ a b) is guaranteed to not be poison (and |

2028 | /// hence not sign-overflow) only if "<condition>" is true. Since both |

2029 | /// `idx0` and `idx1` will be mapped to the same SCEV expression, (+ a b), |

2030 | /// it is not okay to annotate (+ a b) with <nsw> in the above example. |

2031 | bool isSCEVExprNeverPoison(const Instruction *I); |

2032 | |

2033 | /// This is like \c isSCEVExprNeverPoison but it specifically works for |

2034 | /// instructions that will get mapped to SCEV add recurrences. Return true |

2035 | /// if \p I will never generate poison under the assumption that \p I is an |

2036 | /// add recurrence on the loop \p L. |

2037 | bool isAddRecNeverPoison(const Instruction *I, const Loop *L); |

2038 | |

2039 | /// Similar to createAddRecFromPHI, but with the additional flexibility of |

2040 | /// suggesting runtime overflow checks in case casts are encountered. |

2041 | /// If successful, the analysis records that for this loop, \p SymbolicPHI, |

2042 | /// which is the UnknownSCEV currently representing the PHI, can be rewritten |

2043 | /// into an AddRec, assuming some predicates; The function then returns the |

2044 | /// AddRec and the predicates as a pair, and caches this pair in |

2045 | /// PredicatedSCEVRewrites. |

2046 | /// If the analysis is not successful, a mapping from the \p SymbolicPHI to |

2047 | /// itself (with no predicates) is recorded, and a nullptr with an empty |

2048 | /// predicates vector is returned as a pair. |

2049 | Optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>> |

2050 | createAddRecFromPHIWithCastsImpl(const SCEVUnknown *SymbolicPHI); |

2051 | |

2052 | /// Compute the maximum backedge count based on the range of values |

2053 | /// permitted by Start, End, and Stride. This is for loops of the form |

2054 | /// {Start, +, Stride} LT End. |

2055 | /// |

2056 | /// Preconditions: |

2057 | /// * the induction variable is known to be positive. |

2058 | /// * the induction variable is assumed not to overflow (i.e. either it |

2059 | /// actually doesn't, or we'd have to immediately execute UB) |

2060 | /// We *don't* assert these preconditions so please be careful. |

2061 | const SCEV *computeMaxBECountForLT(const SCEV *Start, const SCEV *Stride, |

2062 | const SCEV *End, unsigned BitWidth, |

2063 | bool IsSigned); |

2064 | |

2065 | /// Verify if an linear IV with positive stride can overflow when in a |

2066 | /// less-than comparison, knowing the invariant term of the comparison, |

2067 | /// the stride. |

2068 | bool canIVOverflowOnLT(const SCEV *RHS, const SCEV *Stride, bool IsSigned); |

2069 | |

2070 | /// Verify if an linear IV with negative stride can overflow when in a |

2071 | /// greater-than comparison, knowing the invariant term of the comparison, |

2072 | /// the stride. |

2073 | bool canIVOverflowOnGT(const SCEV *RHS, const SCEV *Stride, bool IsSigned); |

2074 | |

2075 | /// Get add expr already created or create a new one. |

2076 | const SCEV *getOrCreateAddExpr(ArrayRef<const SCEV *> Ops, |

2077 | SCEV::NoWrapFlags Flags); |

2078 | |

2079 | /// Get mul expr already created or create a new one. |

2080 | const SCEV *getOrCreateMulExpr(ArrayRef<const SCEV *> Ops, |

2081 | SCEV::NoWrapFlags Flags); |

2082 | |

2083 | // Get addrec expr already created or create a new one. |

2084 | const SCEV *getOrCreateAddRecExpr(ArrayRef<const SCEV *> Ops, |

2085 | const Loop *L, SCEV::NoWrapFlags Flags); |

2086 | |

2087 | /// Return x if \p Val is f(x) where f is a 1-1 function. |

2088 | const SCEV *stripInjectiveFunctions(const SCEV *Val) const; |

2089 | |

2090 | /// Find all of the loops transitively used in \p S, and fill \p LoopsUsed. |

2091 | /// A loop is considered "used" by an expression if it contains |

2092 | /// an add rec on said loop. |

2093 | void getUsedLoops(const SCEV *S, SmallPtrSetImpl<const Loop *> &LoopsUsed); |

2094 | |

2095 | /// Try to match the pattern generated by getURemExpr(A, B). If successful, |

2096 | /// Assign A and B to LHS and RHS, respectively. |

2097 | bool matchURem(const SCEV *Expr, const SCEV *&LHS, const SCEV *&RHS); |

2098 | |

2099 | /// Look for a SCEV expression with type `SCEVType` and operands `Ops` in |

2100 | /// `UniqueSCEVs`. Return if found, else nullptr. |

2101 | SCEV *findExistingSCEVInCache(SCEVTypes SCEVType, ArrayRef<const SCEV *> Ops); |

2102 | |

2103 | /// Get reachable blocks in this function, making limited use of SCEV |

2104 | /// reasoning about conditions. |

2105 | void getReachableBlocks(SmallPtrSetImpl<BasicBlock *> &Reachable, |

2106 | Function &F); |

2107 | |

2108 | FoldingSet<SCEV> UniqueSCEVs; |

2109 | FoldingSet<SCEVPredicate> UniquePreds; |

2110 | BumpPtrAllocator SCEVAllocator; |

2111 | |

2112 | /// This maps loops to a list of addrecs that directly use said loop. |

2113 | DenseMap<const Loop *, SmallVector<const SCEVAddRecExpr *, 4>> LoopUsers; |

2114 | |

2115 | /// Cache tentative mappings from UnknownSCEVs in a Loop, to a SCEV expression |

2116 | /// they can be rewritten into under certain predicates. |

2117 | DenseMap<std::pair<const SCEVUnknown *, const Loop *>, |

2118 | std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>> |

2119 | PredicatedSCEVRewrites; |

2120 | |

2121 | /// Set of AddRecs for which proving NUW via an induction has already been |

2122 | /// tried. |

2123 | SmallPtrSet<const SCEVAddRecExpr *, 16> UnsignedWrapViaInductionTried; |

2124 | |

2125 | /// Set of AddRecs for which proving NSW via an induction has already been |

2126 | /// tried. |

2127 | SmallPtrSet<const SCEVAddRecExpr *, 16> SignedWrapViaInductionTried; |

2128 | |

2129 | /// The head of a linked list of all SCEVUnknown values that have been |

2130 | /// allocated. This is used by releaseMemory to locate them all and call |

2131 | /// their destructors. |

2132 | SCEVUnknown *FirstUnknown = nullptr; |

2133 | }; |

2134 | |

2135 | /// Analysis pass that exposes the \c ScalarEvolution for a function. |

2136 | class ScalarEvolutionAnalysis |

2137 | : public AnalysisInfoMixin<ScalarEvolutionAnalysis> { |

2138 | friend AnalysisInfoMixin<ScalarEvolutionAnalysis>; |

2139 | |

2140 | static AnalysisKey Key; |

2141 | |

2142 | public: |

2143 | using Result = ScalarEvolution; |

2144 | |

2145 | ScalarEvolution run(Function &F, FunctionAnalysisManager &AM); |

2146 | }; |

2147 | |

2148 | /// Verifier pass for the \c ScalarEvolutionAnalysis results. |

2149 | class ScalarEvolutionVerifierPass |

2150 | : public PassInfoMixin<ScalarEvolutionVerifierPass> { |

2151 | public: |

2152 | PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); |

2153 | }; |

2154 | |

2155 | /// Printer pass for the \c ScalarEvolutionAnalysis results. |

2156 | class ScalarEvolutionPrinterPass |

2157 | : public PassInfoMixin<ScalarEvolutionPrinterPass> { |

2158 | raw_ostream &OS; |

2159 | |

2160 | public: |

2161 | explicit ScalarEvolutionPrinterPass(raw_ostream &OS) : OS(OS) {} |

2162 | |

2163 | PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); |

2164 | }; |

2165 | |

2166 | class ScalarEvolutionWrapperPass : public FunctionPass { |

2167 | std::unique_ptr<ScalarEvolution> SE; |

2168 | |

2169 | public: |

2170 | static char ID; |

2171 | |

2172 | ScalarEvolutionWrapperPass(); |

2173 | |

2174 | ScalarEvolution &getSE() { return *SE; } |

2175 | const ScalarEvolution &getSE() const { return *SE; } |

2176 | |

2177 | bool runOnFunction(Function &F) override; |

2178 | void releaseMemory() override; |

2179 | void getAnalysisUsage(AnalysisUsage &AU) const override; |

2180 | void print(raw_ostream &OS, const Module * = nullptr) const override; |

2181 | void verifyAnalysis() const override; |

2182 | }; |

2183 | |

2184 | /// An interface layer with SCEV used to manage how we see SCEV expressions |

2185 | /// for values in the context of existing predicates. We can add new |

2186 | /// predicates, but we cannot remove them. |

2187 | /// |

2188 | /// This layer has multiple purposes: |

2189 | /// - provides a simple interface for SCEV versioning. |

2190 | /// - guarantees that the order of transformations applied on a SCEV |

2191 | /// expression for a single Value is consistent across two different |

2192 | /// getSCEV calls. This means that, for example, once we've obtained |

2193 | /// an AddRec expression for a certain value through expression |

2194 | /// rewriting, we will continue to get an AddRec expression for that |

2195 | /// Value. |

2196 | /// - lowers the number of expression rewrites. |

2197 | class PredicatedScalarEvolution { |

2198 | public: |

2199 | PredicatedScalarEvolution(ScalarEvolution &SE, Loop &L); |

2200 | |

2201 | const SCEVPredicate &getPredicate() const; |

2202 | |

2203 | /// Returns the SCEV expression of V, in the context of the current SCEV |

2204 | /// predicate. The order of transformations applied on the expression of V |

2205 | /// returned by ScalarEvolution is guaranteed to be preserved, even when |

2206 | /// adding new predicates. |

2207 | const SCEV *getSCEV(Value *V); |

2208 | |

2209 | /// Get the (predicated) backedge count for the analyzed loop. |

2210 | const SCEV *getBackedgeTakenCount(); |

2211 | |

2212 | /// Adds a new predicate. |

2213 | void addPredicate(const SCEVPredicate &Pred); |

2214 | |

2215 | /// Attempts to produce an AddRecExpr for V by adding additional SCEV |

2216 | /// predicates. If we can't transform the expression into an AddRecExpr we |

2217 | /// return nullptr and not add additional SCEV predicates to the current |

2218 | /// context. |

2219 | const SCEVAddRecExpr *getAsAddRec(Value *V); |

2220 | |

2221 | /// Proves that V doesn't overflow by adding SCEV predicate. |

2222 | void setNoOverflow(Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags); |

2223 | |

2224 | /// Returns true if we've proved that V doesn't wrap by means of a SCEV |

2225 | /// predicate. |

2226 | bool hasNoOverflow(Value *V, SCEVWrapPredicate::IncrementWrapFlags Flags); |

2227 | |

2228 | /// Returns the ScalarEvolution analysis used. |

2229 | ScalarEvolution *getSE() const { return &SE; } |

2230 | |

2231 | /// We need to explicitly define the copy constructor because of FlagsMap. |

2232 | PredicatedScalarEvolution(const PredicatedScalarEvolution &); |

2233 | |

2234 | /// Print the SCEV mappings done by the Predicated Scalar Evolution. |

2235 | /// The printed text is indented by \p Depth. |

2236 | void print(raw_ostream &OS, unsigned Depth) const; |

2237 | |

2238 | /// Check if \p AR1 and \p AR2 are equal, while taking into account |

2239 | /// Equal predicates in Preds. |

2240 | bool areAddRecsEqualWithPreds(const SCEVAddRecExpr *AR1, |

2241 | const SCEVAddRecExpr *AR2) const; |

2242 | |

2243 | private: |

2244 | /// Increments the version number of the predicate. This needs to be called |

2245 | /// every time the SCEV predicate changes. |

2246 | void updateGeneration(); |

2247 | |

2248 | /// Holds a SCEV and the version number of the SCEV predicate used to |

2249 | /// perform the rewrite of the expression. |

2250 | using RewriteEntry = std::pair<unsigned, const SCEV *>; |

2251 | |

2252 | /// Maps a SCEV to the rewrite result of that SCEV at a certain version |

2253 | /// number. If this number doesn't match the current Generation, we will |

2254 | /// need to do a rewrite. To preserve the transformation order of previous |

2255 | /// rewrites, we will rewrite the previous result instead of the original |

2256 | /// SCEV. |

2257 | DenseMap<const SCEV *, RewriteEntry> RewriteMap; |

2258 | |

2259 | /// Records what NoWrap flags we've added to a Value *. |

2260 | ValueMap<Value *, SCEVWrapPredicate::IncrementWrapFlags> FlagsMap; |

2261 | |

2262 | /// The ScalarEvolution analysis. |

2263 | ScalarEvolution &SE; |

2264 | |

2265 | /// The analyzed Loop. |

2266 | const Loop &L; |

2267 | |

2268 | /// The SCEVPredicate that forms our context. We will rewrite all |

2269 | /// expressions assuming that this predicate true. |

2270 | std::unique_ptr<SCEVUnionPredicate> Preds; |

2271 | |

2272 | /// Marks the version of the SCEV predicate used. When rewriting a SCEV |

2273 | /// expression we mark it with the version of the predicate. We use this to |

2274 | /// figure out if the predicate has changed from the last rewrite of the |

2275 | /// SCEV. If so, we need to perform a new rewrite. |

2276 | unsigned Generation = 0; |

2277 | |

2278 | /// The backedge taken count. |

2279 | const SCEV *BackedgeCount = nullptr; |

2280 | }; |

2281 | |

2282 | } // end namespace llvm |

2283 | |

2284 | #endif // LLVM_ANALYSIS_SCALAREVOLUTION_H |

2285 |