]>
Commit | Line | Data |
---|---|---|
223e47cc LB |
1 | //===- llvm/Analysis/ScalarEvolution.h - Scalar Evolution -------*- C++ -*-===// |
2 | // | |
3 | // The LLVM Compiler Infrastructure | |
4 | // | |
5 | // This file is distributed under the University of Illinois Open Source | |
6 | // License. See LICENSE.TXT for details. | |
7 | // | |
8 | //===----------------------------------------------------------------------===// | |
9 | // | |
10 | // The ScalarEvolution class is an LLVM pass which can be used to analyze and | |
11 | // categorize scalar expressions in loops. It specializes in recognizing | |
12 | // general induction variables, representing them with the abstract and opaque | |
13 | // SCEV class. Given this analysis, trip counts of loops and other important | |
14 | // properties can be obtained. | |
15 | // | |
16 | // This analysis is primarily useful for induction variable substitution and | |
17 | // strength reduction. | |
18 | // | |
19 | //===----------------------------------------------------------------------===// | |
20 | ||
21 | #ifndef LLVM_ANALYSIS_SCALAREVOLUTION_H | |
22 | #define LLVM_ANALYSIS_SCALAREVOLUTION_H | |
23 | ||
970d7e83 LB |
24 | #include "llvm/ADT/DenseSet.h" |
25 | #include "llvm/ADT/FoldingSet.h" | |
1a4d82fc | 26 | #include "llvm/IR/ConstantRange.h" |
970d7e83 LB |
27 | #include "llvm/IR/Function.h" |
28 | #include "llvm/IR/Instructions.h" | |
29 | #include "llvm/IR/Operator.h" | |
1a4d82fc | 30 | #include "llvm/IR/ValueHandle.h" |
223e47cc | 31 | #include "llvm/Pass.h" |
223e47cc | 32 | #include "llvm/Support/Allocator.h" |
970d7e83 | 33 | #include "llvm/Support/DataTypes.h" |
223e47cc LB |
34 | #include <map> |
35 | ||
36 | namespace llvm { | |
37 | class APInt; | |
85aaf69f | 38 | class AssumptionCache; |
223e47cc LB |
39 | class Constant; |
40 | class ConstantInt; | |
41 | class DominatorTree; | |
42 | class Type; | |
43 | class ScalarEvolution; | |
970d7e83 | 44 | class DataLayout; |
223e47cc LB |
45 | class TargetLibraryInfo; |
46 | class LLVMContext; | |
47 | class Loop; | |
48 | class LoopInfo; | |
49 | class Operator; | |
50 | class SCEVUnknown; | |
51 | class SCEV; | |
52 | template<> struct FoldingSetTrait<SCEV>; | |
53 | ||
54 | /// SCEV - This class represents an analyzed expression in the program. These | |
55 | /// are opaque objects that the client is not allowed to do much with | |
56 | /// directly. | |
57 | /// | |
58 | class SCEV : public FoldingSetNode { | |
59 | friend struct FoldingSetTrait<SCEV>; | |
60 | ||
61 | /// FastID - A reference to an Interned FoldingSetNodeID for this node. | |
62 | /// The ScalarEvolution's BumpPtrAllocator holds the data. | |
63 | FoldingSetNodeIDRef FastID; | |
64 | ||
65 | // The SCEV baseclass this node corresponds to | |
66 | const unsigned short SCEVType; | |
67 | ||
68 | protected: | |
69 | /// SubclassData - This field is initialized to zero and may be used in | |
70 | /// subclasses to store miscellaneous information. | |
71 | unsigned short SubclassData; | |
72 | ||
73 | private: | |
74 | SCEV(const SCEV &) LLVM_DELETED_FUNCTION; | |
75 | void operator=(const SCEV &) LLVM_DELETED_FUNCTION; | |
76 | ||
77 | public: | |
78 | /// NoWrapFlags are bitfield indices into SubclassData. | |
79 | /// | |
80 | /// Add and Mul expressions may have no-unsigned-wrap <NUW> or | |
81 | /// no-signed-wrap <NSW> properties, which are derived from the IR | |
82 | /// operator. NSW is a misnomer that we use to mean no signed overflow or | |
83 | /// underflow. | |
84 | /// | |
85 | /// AddRec expression may have a no-self-wraparound <NW> property if the | |
86 | /// result can never reach the start value. This property is independent of | |
87 | /// the actual start value and step direction. Self-wraparound is defined | |
88 | /// purely in terms of the recurrence's loop, step size, and | |
89 | /// bitwidth. Formally, a recurrence with no self-wraparound satisfies: | |
90 | /// abs(step) * max-iteration(loop) <= unsigned-max(bitwidth). | |
91 | /// | |
92 | /// Note that NUW and NSW are also valid properties of a recurrence, and | |
93 | /// either implies NW. For convenience, NW will be set for a recurrence | |
94 | /// whenever either NUW or NSW are set. | |
95 | enum NoWrapFlags { FlagAnyWrap = 0, // No guarantee. | |
96 | FlagNW = (1 << 0), // No self-wrap. | |
97 | FlagNUW = (1 << 1), // No unsigned wrap. | |
98 | FlagNSW = (1 << 2), // No signed wrap. | |
99 | NoWrapMask = (1 << 3) -1 }; | |
100 | ||
101 | explicit SCEV(const FoldingSetNodeIDRef ID, unsigned SCEVTy) : | |
102 | FastID(ID), SCEVType(SCEVTy), SubclassData(0) {} | |
103 | ||
104 | unsigned getSCEVType() const { return SCEVType; } | |
105 | ||
106 | /// getType - Return the LLVM type of this SCEV expression. | |
107 | /// | |
108 | Type *getType() const; | |
109 | ||
110 | /// isZero - Return true if the expression is a constant zero. | |
111 | /// | |
112 | bool isZero() const; | |
113 | ||
114 | /// isOne - Return true if the expression is a constant one. | |
115 | /// | |
116 | bool isOne() const; | |
117 | ||
118 | /// isAllOnesValue - Return true if the expression is a constant | |
119 | /// all-ones value. | |
120 | /// | |
121 | bool isAllOnesValue() const; | |
122 | ||
123 | /// isNonConstantNegative - Return true if the specified scev is negated, | |
124 | /// but not a constant. | |
125 | bool isNonConstantNegative() const; | |
126 | ||
127 | /// print - Print out the internal representation of this scalar to the | |
128 | /// specified stream. This should really only be used for debugging | |
129 | /// purposes. | |
130 | void print(raw_ostream &OS) const; | |
131 | ||
85aaf69f | 132 | #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
223e47cc LB |
133 | /// dump - This method is used for debugging. |
134 | /// | |
135 | void dump() const; | |
85aaf69f | 136 | #endif |
223e47cc LB |
137 | }; |
138 | ||
139 | // Specialize FoldingSetTrait for SCEV to avoid needing to compute | |
140 | // temporary FoldingSetNodeID values. | |
141 | template<> struct FoldingSetTrait<SCEV> : DefaultFoldingSetTrait<SCEV> { | |
142 | static void Profile(const SCEV &X, FoldingSetNodeID& ID) { | |
143 | ID = X.FastID; | |
144 | } | |
145 | static bool Equals(const SCEV &X, const FoldingSetNodeID &ID, | |
146 | unsigned IDHash, FoldingSetNodeID &TempID) { | |
147 | return ID == X.FastID; | |
148 | } | |
149 | static unsigned ComputeHash(const SCEV &X, FoldingSetNodeID &TempID) { | |
150 | return X.FastID.ComputeHash(); | |
151 | } | |
152 | }; | |
153 | ||
154 | inline raw_ostream &operator<<(raw_ostream &OS, const SCEV &S) { | |
155 | S.print(OS); | |
156 | return OS; | |
157 | } | |
158 | ||
159 | /// SCEVCouldNotCompute - An object of this class is returned by queries that | |
160 | /// could not be answered. For example, if you ask for the number of | |
161 | /// iterations of a linked-list traversal loop, you will get one of these. | |
162 | /// None of the standard SCEV operations are valid on this class, it is just a | |
163 | /// marker. | |
164 | struct SCEVCouldNotCompute : public SCEV { | |
165 | SCEVCouldNotCompute(); | |
166 | ||
167 | /// Methods for support type inquiry through isa, cast, and dyn_cast: | |
223e47cc LB |
168 | static bool classof(const SCEV *S); |
169 | }; | |
170 | ||
171 | /// ScalarEvolution - This class is the main scalar evolution driver. Because | |
172 | /// client code (intentionally) can't do much with the SCEV objects directly, | |
173 | /// they must ask this class for services. | |
174 | /// | |
175 | class ScalarEvolution : public FunctionPass { | |
176 | public: | |
177 | /// LoopDisposition - An enum describing the relationship between a | |
178 | /// SCEV and a loop. | |
179 | enum LoopDisposition { | |
180 | LoopVariant, ///< The SCEV is loop-variant (unknown). | |
181 | LoopInvariant, ///< The SCEV is loop-invariant. | |
182 | LoopComputable ///< The SCEV varies predictably with the loop. | |
183 | }; | |
184 | ||
185 | /// BlockDisposition - An enum describing the relationship between a | |
186 | /// SCEV and a basic block. | |
187 | enum BlockDisposition { | |
188 | DoesNotDominateBlock, ///< The SCEV does not dominate the block. | |
189 | DominatesBlock, ///< The SCEV dominates the block. | |
190 | ProperlyDominatesBlock ///< The SCEV properly dominates the block. | |
191 | }; | |
192 | ||
193 | /// Convenient NoWrapFlags manipulation that hides enum casts and is | |
194 | /// visible in the ScalarEvolution name space. | |
1a4d82fc JJ |
195 | static SCEV::NoWrapFlags LLVM_ATTRIBUTE_UNUSED_RESULT |
196 | maskFlags(SCEV::NoWrapFlags Flags, int Mask) { | |
223e47cc LB |
197 | return (SCEV::NoWrapFlags)(Flags & Mask); |
198 | } | |
1a4d82fc JJ |
199 | static SCEV::NoWrapFlags LLVM_ATTRIBUTE_UNUSED_RESULT |
200 | setFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OnFlags) { | |
223e47cc LB |
201 | return (SCEV::NoWrapFlags)(Flags | OnFlags); |
202 | } | |
1a4d82fc JJ |
203 | static SCEV::NoWrapFlags LLVM_ATTRIBUTE_UNUSED_RESULT |
204 | clearFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OffFlags) { | |
223e47cc LB |
205 | return (SCEV::NoWrapFlags)(Flags & ~OffFlags); |
206 | } | |
207 | ||
208 | private: | |
209 | /// SCEVCallbackVH - A CallbackVH to arrange for ScalarEvolution to be | |
210 | /// notified whenever a Value is deleted. | |
211 | class SCEVCallbackVH : public CallbackVH { | |
212 | ScalarEvolution *SE; | |
1a4d82fc JJ |
213 | void deleted() override; |
214 | void allUsesReplacedWith(Value *New) override; | |
223e47cc | 215 | public: |
1a4d82fc | 216 | SCEVCallbackVH(Value *V, ScalarEvolution *SE = nullptr); |
223e47cc LB |
217 | }; |
218 | ||
219 | friend class SCEVCallbackVH; | |
220 | friend class SCEVExpander; | |
221 | friend class SCEVUnknown; | |
222 | ||
223 | /// F - The function we are analyzing. | |
224 | /// | |
225 | Function *F; | |
226 | ||
1a4d82fc | 227 | /// The tracker for @llvm.assume intrinsics in this function. |
85aaf69f | 228 | AssumptionCache *AC; |
1a4d82fc | 229 | |
223e47cc LB |
230 | /// LI - The loop information for the function we are currently analyzing. |
231 | /// | |
232 | LoopInfo *LI; | |
233 | ||
1a4d82fc | 234 | /// The DataLayout information for the target we are targeting. |
223e47cc | 235 | /// |
1a4d82fc | 236 | const DataLayout *DL; |
223e47cc LB |
237 | |
238 | /// TLI - The target library information for the target we are targeting. | |
239 | /// | |
240 | TargetLibraryInfo *TLI; | |
241 | ||
242 | /// DT - The dominator tree. | |
243 | /// | |
244 | DominatorTree *DT; | |
245 | ||
246 | /// CouldNotCompute - This SCEV is used to represent unknown trip | |
247 | /// counts and things. | |
248 | SCEVCouldNotCompute CouldNotCompute; | |
249 | ||
250 | /// ValueExprMapType - The typedef for ValueExprMap. | |
251 | /// | |
252 | typedef DenseMap<SCEVCallbackVH, const SCEV *, DenseMapInfo<Value *> > | |
253 | ValueExprMapType; | |
254 | ||
255 | /// ValueExprMap - This is a cache of the values we have analyzed so far. | |
256 | /// | |
257 | ValueExprMapType ValueExprMap; | |
258 | ||
259 | /// Mark predicate values currently being processed by isImpliedCond. | |
260 | DenseSet<Value*> PendingLoopPredicates; | |
261 | ||
1a4d82fc JJ |
262 | /// ExitLimit - Information about the number of loop iterations for which a |
263 | /// loop exit's branch condition evaluates to the not-taken path. This is a | |
264 | /// temporary pair of exact and max expressions that are eventually | |
265 | /// summarized in ExitNotTakenInfo and BackedgeTakenInfo. | |
223e47cc LB |
266 | struct ExitLimit { |
267 | const SCEV *Exact; | |
268 | const SCEV *Max; | |
269 | ||
85aaf69f | 270 | /*implicit*/ ExitLimit(const SCEV *E) : Exact(E), Max(E) {} |
223e47cc | 271 | |
85aaf69f | 272 | ExitLimit(const SCEV *E, const SCEV *M) : Exact(E), Max(M) {} |
223e47cc LB |
273 | |
274 | /// hasAnyInfo - Test whether this ExitLimit contains any computed | |
275 | /// information, or whether it's all SCEVCouldNotCompute values. | |
276 | bool hasAnyInfo() const { | |
277 | return !isa<SCEVCouldNotCompute>(Exact) || | |
278 | !isa<SCEVCouldNotCompute>(Max); | |
279 | } | |
280 | }; | |
281 | ||
282 | /// ExitNotTakenInfo - Information about the number of times a particular | |
283 | /// loop exit may be reached before exiting the loop. | |
284 | struct ExitNotTakenInfo { | |
285 | AssertingVH<BasicBlock> ExitingBlock; | |
286 | const SCEV *ExactNotTaken; | |
287 | PointerIntPair<ExitNotTakenInfo*, 1> NextExit; | |
288 | ||
1a4d82fc | 289 | ExitNotTakenInfo() : ExitingBlock(nullptr), ExactNotTaken(nullptr) {} |
223e47cc LB |
290 | |
291 | /// isCompleteList - Return true if all loop exits are computable. | |
292 | bool isCompleteList() const { | |
293 | return NextExit.getInt() == 0; | |
294 | } | |
295 | ||
296 | void setIncomplete() { NextExit.setInt(1); } | |
297 | ||
298 | /// getNextExit - Return a pointer to the next exit's not-taken info. | |
299 | ExitNotTakenInfo *getNextExit() const { | |
300 | return NextExit.getPointer(); | |
301 | } | |
302 | ||
303 | void setNextExit(ExitNotTakenInfo *ENT) { NextExit.setPointer(ENT); } | |
304 | }; | |
305 | ||
306 | /// BackedgeTakenInfo - Information about the backedge-taken count | |
307 | /// of a loop. This currently includes an exact count and a maximum count. | |
308 | /// | |
309 | class BackedgeTakenInfo { | |
310 | /// ExitNotTaken - A list of computable exits and their not-taken counts. | |
311 | /// Loops almost never have more than one computable exit. | |
312 | ExitNotTakenInfo ExitNotTaken; | |
313 | ||
314 | /// Max - An expression indicating the least maximum backedge-taken | |
315 | /// count of the loop that is known, or a SCEVCouldNotCompute. | |
316 | const SCEV *Max; | |
317 | ||
318 | public: | |
1a4d82fc | 319 | BackedgeTakenInfo() : Max(nullptr) {} |
223e47cc LB |
320 | |
321 | /// Initialize BackedgeTakenInfo from a list of exact exit counts. | |
322 | BackedgeTakenInfo( | |
323 | SmallVectorImpl< std::pair<BasicBlock *, const SCEV *> > &ExitCounts, | |
324 | bool Complete, const SCEV *MaxCount); | |
325 | ||
326 | /// hasAnyInfo - Test whether this BackedgeTakenInfo contains any | |
327 | /// computed information, or whether it's all SCEVCouldNotCompute | |
328 | /// values. | |
329 | bool hasAnyInfo() const { | |
330 | return ExitNotTaken.ExitingBlock || !isa<SCEVCouldNotCompute>(Max); | |
331 | } | |
332 | ||
333 | /// getExact - Return an expression indicating the exact backedge-taken | |
334 | /// count of the loop if it is known, or SCEVCouldNotCompute | |
335 | /// otherwise. This is the number of times the loop header can be | |
336 | /// guaranteed to execute, minus one. | |
337 | const SCEV *getExact(ScalarEvolution *SE) const; | |
338 | ||
339 | /// getExact - Return the number of times this loop exit may fall through | |
340 | /// to the back edge, or SCEVCouldNotCompute. The loop is guaranteed not | |
341 | /// to exit via this block before this number of iterations, but may exit | |
342 | /// via another block. | |
343 | const SCEV *getExact(BasicBlock *ExitingBlock, ScalarEvolution *SE) const; | |
344 | ||
345 | /// getMax - Get the max backedge taken count for the loop. | |
346 | const SCEV *getMax(ScalarEvolution *SE) const; | |
347 | ||
1a4d82fc JJ |
348 | /// Return true if any backedge taken count expressions refer to the given |
349 | /// subexpression. | |
350 | bool hasOperand(const SCEV *S, ScalarEvolution *SE) const; | |
351 | ||
223e47cc LB |
352 | /// clear - Invalidate this result and free associated memory. |
353 | void clear(); | |
354 | }; | |
355 | ||
356 | /// BackedgeTakenCounts - Cache the backedge-taken count of the loops for | |
357 | /// this function as they are computed. | |
358 | DenseMap<const Loop*, BackedgeTakenInfo> BackedgeTakenCounts; | |
359 | ||
360 | /// ConstantEvolutionLoopExitValue - This map contains entries for all of | |
361 | /// the PHI instructions that we attempt to compute constant evolutions for. | |
362 | /// This allows us to avoid potentially expensive recomputation of these | |
363 | /// properties. An instruction maps to null if we are unable to compute its | |
364 | /// exit value. | |
365 | DenseMap<PHINode*, Constant*> ConstantEvolutionLoopExitValue; | |
366 | ||
367 | /// ValuesAtScopes - This map contains entries for all the expressions | |
368 | /// that we attempt to compute getSCEVAtScope information for, which can | |
369 | /// be expensive in extreme cases. | |
370 | DenseMap<const SCEV *, | |
1a4d82fc | 371 | SmallVector<std::pair<const Loop *, const SCEV *>, 2> > ValuesAtScopes; |
223e47cc LB |
372 | |
373 | /// LoopDispositions - Memoized computeLoopDisposition results. | |
374 | DenseMap<const SCEV *, | |
1a4d82fc | 375 | SmallVector<std::pair<const Loop *, LoopDisposition>, 2> > LoopDispositions; |
223e47cc LB |
376 | |
377 | /// computeLoopDisposition - Compute a LoopDisposition value. | |
378 | LoopDisposition computeLoopDisposition(const SCEV *S, const Loop *L); | |
379 | ||
380 | /// BlockDispositions - Memoized computeBlockDisposition results. | |
381 | DenseMap<const SCEV *, | |
1a4d82fc | 382 | SmallVector<std::pair<const BasicBlock *, BlockDisposition>, 2> > BlockDispositions; |
223e47cc LB |
383 | |
384 | /// computeBlockDisposition - Compute a BlockDisposition value. | |
385 | BlockDisposition computeBlockDisposition(const SCEV *S, const BasicBlock *BB); | |
386 | ||
387 | /// UnsignedRanges - Memoized results from getUnsignedRange | |
388 | DenseMap<const SCEV *, ConstantRange> UnsignedRanges; | |
389 | ||
390 | /// SignedRanges - Memoized results from getSignedRange | |
391 | DenseMap<const SCEV *, ConstantRange> SignedRanges; | |
392 | ||
393 | /// setUnsignedRange - Set the memoized unsigned range for the given SCEV. | |
394 | const ConstantRange &setUnsignedRange(const SCEV *S, | |
395 | const ConstantRange &CR) { | |
396 | std::pair<DenseMap<const SCEV *, ConstantRange>::iterator, bool> Pair = | |
397 | UnsignedRanges.insert(std::make_pair(S, CR)); | |
398 | if (!Pair.second) | |
399 | Pair.first->second = CR; | |
400 | return Pair.first->second; | |
401 | } | |
402 | ||
403 | /// setUnsignedRange - Set the memoized signed range for the given SCEV. | |
404 | const ConstantRange &setSignedRange(const SCEV *S, | |
405 | const ConstantRange &CR) { | |
406 | std::pair<DenseMap<const SCEV *, ConstantRange>::iterator, bool> Pair = | |
407 | SignedRanges.insert(std::make_pair(S, CR)); | |
408 | if (!Pair.second) | |
409 | Pair.first->second = CR; | |
410 | return Pair.first->second; | |
411 | } | |
412 | ||
413 | /// createSCEV - We know that there is no SCEV for the specified value. | |
414 | /// Analyze the expression. | |
415 | const SCEV *createSCEV(Value *V); | |
416 | ||
417 | /// createNodeForPHI - Provide the special handling we need to analyze PHI | |
418 | /// SCEVs. | |
419 | const SCEV *createNodeForPHI(PHINode *PN); | |
420 | ||
421 | /// createNodeForGEP - Provide the special handling we need to analyze GEP | |
422 | /// SCEVs. | |
423 | const SCEV *createNodeForGEP(GEPOperator *GEP); | |
424 | ||
425 | /// computeSCEVAtScope - Implementation code for getSCEVAtScope; called | |
426 | /// at most once for each SCEV+Loop pair. | |
427 | /// | |
428 | const SCEV *computeSCEVAtScope(const SCEV *S, const Loop *L); | |
429 | ||
430 | /// ForgetSymbolicValue - This looks up computed SCEV values for all | |
431 | /// instructions that depend on the given instruction and removes them from | |
432 | /// the ValueExprMap map if they reference SymName. This is used during PHI | |
433 | /// resolution. | |
434 | void ForgetSymbolicName(Instruction *I, const SCEV *SymName); | |
435 | ||
223e47cc LB |
436 | /// getBackedgeTakenInfo - Return the BackedgeTakenInfo for the given |
437 | /// loop, lazily computing new values if the loop hasn't been analyzed | |
438 | /// yet. | |
439 | const BackedgeTakenInfo &getBackedgeTakenInfo(const Loop *L); | |
440 | ||
441 | /// ComputeBackedgeTakenCount - Compute the number of times the specified | |
442 | /// loop will iterate. | |
443 | BackedgeTakenInfo ComputeBackedgeTakenCount(const Loop *L); | |
444 | ||
445 | /// ComputeExitLimit - Compute the number of times the backedge of the | |
446 | /// specified loop will execute if it exits via the specified block. | |
447 | ExitLimit ComputeExitLimit(const Loop *L, BasicBlock *ExitingBlock); | |
448 | ||
449 | /// ComputeExitLimitFromCond - Compute the number of times the backedge of | |
450 | /// the specified loop will execute if its exit condition were a conditional | |
451 | /// branch of ExitCond, TBB, and FBB. | |
452 | ExitLimit ComputeExitLimitFromCond(const Loop *L, | |
453 | Value *ExitCond, | |
454 | BasicBlock *TBB, | |
1a4d82fc JJ |
455 | BasicBlock *FBB, |
456 | bool IsSubExpr); | |
223e47cc LB |
457 | |
458 | /// ComputeExitLimitFromICmp - Compute the number of times the backedge of | |
459 | /// the specified loop will execute if its exit condition were a conditional | |
460 | /// branch of the ICmpInst ExitCond, TBB, and FBB. | |
461 | ExitLimit ComputeExitLimitFromICmp(const Loop *L, | |
462 | ICmpInst *ExitCond, | |
463 | BasicBlock *TBB, | |
1a4d82fc JJ |
464 | BasicBlock *FBB, |
465 | bool IsSubExpr); | |
466 | ||
467 | /// ComputeExitLimitFromSingleExitSwitch - Compute the number of times the | |
468 | /// backedge of the specified loop will execute if its exit condition were a | |
469 | /// switch with a single exiting case to ExitingBB. | |
470 | ExitLimit | |
471 | ComputeExitLimitFromSingleExitSwitch(const Loop *L, SwitchInst *Switch, | |
472 | BasicBlock *ExitingBB, bool IsSubExpr); | |
223e47cc LB |
473 | |
474 | /// ComputeLoadConstantCompareExitLimit - Given an exit condition | |
475 | /// of 'icmp op load X, cst', try to see if we can compute the | |
476 | /// backedge-taken count. | |
477 | ExitLimit ComputeLoadConstantCompareExitLimit(LoadInst *LI, | |
478 | Constant *RHS, | |
479 | const Loop *L, | |
480 | ICmpInst::Predicate p); | |
481 | ||
482 | /// ComputeExitCountExhaustively - If the loop is known to execute a | |
483 | /// constant number of times (the condition evolves only from constants), | |
484 | /// try to evaluate a few iterations of the loop until we get the exit | |
485 | /// condition gets a value of ExitWhen (true or false). If we cannot | |
486 | /// evaluate the exit count of the loop, return CouldNotCompute. | |
487 | const SCEV *ComputeExitCountExhaustively(const Loop *L, | |
488 | Value *Cond, | |
489 | bool ExitWhen); | |
490 | ||
491 | /// HowFarToZero - Return the number of times an exit condition comparing | |
492 | /// the specified value to zero will execute. If not computable, return | |
493 | /// CouldNotCompute. | |
1a4d82fc | 494 | ExitLimit HowFarToZero(const SCEV *V, const Loop *L, bool IsSubExpr); |
223e47cc LB |
495 | |
496 | /// HowFarToNonZero - Return the number of times an exit condition checking | |
497 | /// the specified value for nonzero will execute. If not computable, return | |
498 | /// CouldNotCompute. | |
499 | ExitLimit HowFarToNonZero(const SCEV *V, const Loop *L); | |
500 | ||
501 | /// HowManyLessThans - Return the number of times an exit condition | |
502 | /// containing the specified less-than comparison will execute. If not | |
503 | /// computable, return CouldNotCompute. isSigned specifies whether the | |
504 | /// less-than is signed. | |
505 | ExitLimit HowManyLessThans(const SCEV *LHS, const SCEV *RHS, | |
1a4d82fc JJ |
506 | const Loop *L, bool isSigned, bool IsSubExpr); |
507 | ExitLimit HowManyGreaterThans(const SCEV *LHS, const SCEV *RHS, | |
508 | const Loop *L, bool isSigned, bool IsSubExpr); | |
223e47cc LB |
509 | |
510 | /// getPredecessorWithUniqueSuccessorForBB - Return a predecessor of BB | |
511 | /// (which may not be an immediate predecessor) which has exactly one | |
512 | /// successor from which BB is reachable, or null if no such block is | |
513 | /// found. | |
514 | std::pair<BasicBlock *, BasicBlock *> | |
515 | getPredecessorWithUniqueSuccessorForBB(BasicBlock *BB); | |
516 | ||
517 | /// isImpliedCond - Test whether the condition described by Pred, LHS, and | |
518 | /// RHS is true whenever the given FoundCondValue value evaluates to true. | |
519 | bool isImpliedCond(ICmpInst::Predicate Pred, | |
520 | const SCEV *LHS, const SCEV *RHS, | |
521 | Value *FoundCondValue, | |
522 | bool Inverse); | |
523 | ||
524 | /// isImpliedCondOperands - Test whether the condition described by Pred, | |
525 | /// LHS, and RHS is true whenever the condition described by Pred, FoundLHS, | |
526 | /// and FoundRHS is true. | |
527 | bool isImpliedCondOperands(ICmpInst::Predicate Pred, | |
528 | const SCEV *LHS, const SCEV *RHS, | |
529 | const SCEV *FoundLHS, const SCEV *FoundRHS); | |
530 | ||
531 | /// isImpliedCondOperandsHelper - Test whether the condition described by | |
532 | /// Pred, LHS, and RHS is true whenever the condition described by Pred, | |
533 | /// FoundLHS, and FoundRHS is true. | |
534 | bool isImpliedCondOperandsHelper(ICmpInst::Predicate Pred, | |
535 | const SCEV *LHS, const SCEV *RHS, | |
536 | const SCEV *FoundLHS, | |
537 | const SCEV *FoundRHS); | |
538 | ||
539 | /// getConstantEvolutionLoopExitValue - If we know that the specified Phi is | |
540 | /// in the header of its containing loop, we know the loop executes a | |
541 | /// constant number of times, and the PHI node is just a recurrence | |
542 | /// involving constants, fold it. | |
543 | Constant *getConstantEvolutionLoopExitValue(PHINode *PN, const APInt& BEs, | |
544 | const Loop *L); | |
545 | ||
546 | /// isKnownPredicateWithRanges - Test if the given expression is known to | |
547 | /// satisfy the condition described by Pred and the known constant ranges | |
548 | /// of LHS and RHS. | |
549 | /// | |
550 | bool isKnownPredicateWithRanges(ICmpInst::Predicate Pred, | |
551 | const SCEV *LHS, const SCEV *RHS); | |
552 | ||
553 | /// forgetMemoizedResults - Drop memoized information computed for S. | |
554 | void forgetMemoizedResults(const SCEV *S); | |
555 | ||
1a4d82fc JJ |
556 | /// Return false iff given SCEV contains a SCEVUnknown with NULL value- |
557 | /// pointer. | |
558 | bool checkValidity(const SCEV *S) const; | |
559 | ||
223e47cc LB |
560 | public: |
561 | static char ID; // Pass identification, replacement for typeid | |
562 | ScalarEvolution(); | |
563 | ||
564 | LLVMContext &getContext() const { return F->getContext(); } | |
565 | ||
566 | /// isSCEVable - Test if values of the given type are analyzable within | |
567 | /// the SCEV framework. This primarily includes integer types, and it | |
568 | /// can optionally include pointer types if the ScalarEvolution class | |
569 | /// has access to target-specific information. | |
570 | bool isSCEVable(Type *Ty) const; | |
571 | ||
572 | /// getTypeSizeInBits - Return the size in bits of the specified type, | |
573 | /// for which isSCEVable must return true. | |
574 | uint64_t getTypeSizeInBits(Type *Ty) const; | |
575 | ||
576 | /// getEffectiveSCEVType - Return a type with the same bitwidth as | |
577 | /// the given type and which represents how SCEV will treat the given | |
578 | /// type, for which isSCEVable must return true. For pointer types, | |
579 | /// this is the pointer-sized integer type. | |
580 | Type *getEffectiveSCEVType(Type *Ty) const; | |
581 | ||
582 | /// getSCEV - Return a SCEV expression for the full generality of the | |
583 | /// specified expression. | |
584 | const SCEV *getSCEV(Value *V); | |
585 | ||
586 | const SCEV *getConstant(ConstantInt *V); | |
587 | const SCEV *getConstant(const APInt& Val); | |
588 | const SCEV *getConstant(Type *Ty, uint64_t V, bool isSigned = false); | |
589 | const SCEV *getTruncateExpr(const SCEV *Op, Type *Ty); | |
590 | const SCEV *getZeroExtendExpr(const SCEV *Op, Type *Ty); | |
591 | const SCEV *getSignExtendExpr(const SCEV *Op, Type *Ty); | |
592 | const SCEV *getAnyExtendExpr(const SCEV *Op, Type *Ty); | |
593 | const SCEV *getAddExpr(SmallVectorImpl<const SCEV *> &Ops, | |
594 | SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap); | |
595 | const SCEV *getAddExpr(const SCEV *LHS, const SCEV *RHS, | |
596 | SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap) { | |
597 | SmallVector<const SCEV *, 2> Ops; | |
598 | Ops.push_back(LHS); | |
599 | Ops.push_back(RHS); | |
600 | return getAddExpr(Ops, Flags); | |
601 | } | |
602 | const SCEV *getAddExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2, | |
603 | SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap) { | |
604 | SmallVector<const SCEV *, 3> Ops; | |
605 | Ops.push_back(Op0); | |
606 | Ops.push_back(Op1); | |
607 | Ops.push_back(Op2); | |
608 | return getAddExpr(Ops, Flags); | |
609 | } | |
610 | const SCEV *getMulExpr(SmallVectorImpl<const SCEV *> &Ops, | |
611 | SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap); | |
612 | const SCEV *getMulExpr(const SCEV *LHS, const SCEV *RHS, | |
613 | SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap) | |
614 | { | |
615 | SmallVector<const SCEV *, 2> Ops; | |
616 | Ops.push_back(LHS); | |
617 | Ops.push_back(RHS); | |
618 | return getMulExpr(Ops, Flags); | |
619 | } | |
620 | const SCEV *getMulExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2, | |
621 | SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap) { | |
622 | SmallVector<const SCEV *, 3> Ops; | |
623 | Ops.push_back(Op0); | |
624 | Ops.push_back(Op1); | |
625 | Ops.push_back(Op2); | |
626 | return getMulExpr(Ops, Flags); | |
627 | } | |
628 | const SCEV *getUDivExpr(const SCEV *LHS, const SCEV *RHS); | |
1a4d82fc | 629 | const SCEV *getUDivExactExpr(const SCEV *LHS, const SCEV *RHS); |
223e47cc LB |
630 | const SCEV *getAddRecExpr(const SCEV *Start, const SCEV *Step, |
631 | const Loop *L, SCEV::NoWrapFlags Flags); | |
632 | const SCEV *getAddRecExpr(SmallVectorImpl<const SCEV *> &Operands, | |
633 | const Loop *L, SCEV::NoWrapFlags Flags); | |
634 | const SCEV *getAddRecExpr(const SmallVectorImpl<const SCEV *> &Operands, | |
635 | const Loop *L, SCEV::NoWrapFlags Flags) { | |
636 | SmallVector<const SCEV *, 4> NewOp(Operands.begin(), Operands.end()); | |
637 | return getAddRecExpr(NewOp, L, Flags); | |
638 | } | |
639 | const SCEV *getSMaxExpr(const SCEV *LHS, const SCEV *RHS); | |
640 | const SCEV *getSMaxExpr(SmallVectorImpl<const SCEV *> &Operands); | |
641 | const SCEV *getUMaxExpr(const SCEV *LHS, const SCEV *RHS); | |
642 | const SCEV *getUMaxExpr(SmallVectorImpl<const SCEV *> &Operands); | |
643 | const SCEV *getSMinExpr(const SCEV *LHS, const SCEV *RHS); | |
644 | const SCEV *getUMinExpr(const SCEV *LHS, const SCEV *RHS); | |
645 | const SCEV *getUnknown(Value *V); | |
646 | const SCEV *getCouldNotCompute(); | |
647 | ||
1a4d82fc JJ |
648 | /// getSizeOfExpr - Return an expression for sizeof AllocTy that is type |
649 | /// IntTy | |
223e47cc | 650 | /// |
1a4d82fc | 651 | const SCEV *getSizeOfExpr(Type *IntTy, Type *AllocTy); |
223e47cc | 652 | |
1a4d82fc JJ |
653 | /// getOffsetOfExpr - Return an expression for offsetof on the given field |
654 | /// with type IntTy | |
223e47cc | 655 | /// |
1a4d82fc | 656 | const SCEV *getOffsetOfExpr(Type *IntTy, StructType *STy, unsigned FieldNo); |
223e47cc LB |
657 | |
658 | /// getNegativeSCEV - Return the SCEV object corresponding to -V. | |
659 | /// | |
660 | const SCEV *getNegativeSCEV(const SCEV *V); | |
661 | ||
662 | /// getNotSCEV - Return the SCEV object corresponding to ~V. | |
663 | /// | |
664 | const SCEV *getNotSCEV(const SCEV *V); | |
665 | ||
666 | /// getMinusSCEV - Return LHS-RHS. Minus is represented in SCEV as A+B*-1. | |
667 | const SCEV *getMinusSCEV(const SCEV *LHS, const SCEV *RHS, | |
668 | SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap); | |
669 | ||
670 | /// getTruncateOrZeroExtend - Return a SCEV corresponding to a conversion | |
671 | /// of the input value to the specified type. If the type must be | |
672 | /// extended, it is zero extended. | |
673 | const SCEV *getTruncateOrZeroExtend(const SCEV *V, Type *Ty); | |
674 | ||
675 | /// getTruncateOrSignExtend - Return a SCEV corresponding to a conversion | |
676 | /// of the input value to the specified type. If the type must be | |
677 | /// extended, it is sign extended. | |
678 | const SCEV *getTruncateOrSignExtend(const SCEV *V, Type *Ty); | |
679 | ||
680 | /// getNoopOrZeroExtend - Return a SCEV corresponding to a conversion of | |
681 | /// the input value to the specified type. If the type must be extended, | |
682 | /// it is zero extended. The conversion must not be narrowing. | |
683 | const SCEV *getNoopOrZeroExtend(const SCEV *V, Type *Ty); | |
684 | ||
685 | /// getNoopOrSignExtend - Return a SCEV corresponding to a conversion of | |
686 | /// the input value to the specified type. If the type must be extended, | |
687 | /// it is sign extended. The conversion must not be narrowing. | |
688 | const SCEV *getNoopOrSignExtend(const SCEV *V, Type *Ty); | |
689 | ||
690 | /// getNoopOrAnyExtend - Return a SCEV corresponding to a conversion of | |
691 | /// the input value to the specified type. If the type must be extended, | |
692 | /// it is extended with unspecified bits. The conversion must not be | |
693 | /// narrowing. | |
694 | const SCEV *getNoopOrAnyExtend(const SCEV *V, Type *Ty); | |
695 | ||
696 | /// getTruncateOrNoop - Return a SCEV corresponding to a conversion of the | |
697 | /// input value to the specified type. The conversion must not be | |
698 | /// widening. | |
699 | const SCEV *getTruncateOrNoop(const SCEV *V, Type *Ty); | |
700 | ||
701 | /// getUMaxFromMismatchedTypes - Promote the operands to the wider of | |
702 | /// the types using zero-extension, and then perform a umax operation | |
703 | /// with them. | |
704 | const SCEV *getUMaxFromMismatchedTypes(const SCEV *LHS, | |
705 | const SCEV *RHS); | |
706 | ||
707 | /// getUMinFromMismatchedTypes - Promote the operands to the wider of | |
708 | /// the types using zero-extension, and then perform a umin operation | |
709 | /// with them. | |
710 | const SCEV *getUMinFromMismatchedTypes(const SCEV *LHS, | |
711 | const SCEV *RHS); | |
712 | ||
713 | /// getPointerBase - Transitively follow the chain of pointer-type operands | |
714 | /// until reaching a SCEV that does not have a single pointer operand. This | |
715 | /// returns a SCEVUnknown pointer for well-formed pointer-type expressions, | |
716 | /// but corner cases do exist. | |
717 | const SCEV *getPointerBase(const SCEV *V); | |
718 | ||
719 | /// getSCEVAtScope - Return a SCEV expression for the specified value | |
720 | /// at the specified scope in the program. The L value specifies a loop | |
721 | /// nest to evaluate the expression at, where null is the top-level or a | |
722 | /// specified loop is immediately inside of the loop. | |
723 | /// | |
724 | /// This method can be used to compute the exit value for a variable defined | |
725 | /// in a loop by querying what the value will hold in the parent loop. | |
726 | /// | |
727 | /// In the case that a relevant loop exit value cannot be computed, the | |
728 | /// original value V is returned. | |
729 | const SCEV *getSCEVAtScope(const SCEV *S, const Loop *L); | |
730 | ||
731 | /// getSCEVAtScope - This is a convenience function which does | |
732 | /// getSCEVAtScope(getSCEV(V), L). | |
733 | const SCEV *getSCEVAtScope(Value *V, const Loop *L); | |
734 | ||
735 | /// isLoopEntryGuardedByCond - Test whether entry to the loop is protected | |
736 | /// by a conditional between LHS and RHS. This is used to help avoid max | |
737 | /// expressions in loop trip counts, and to eliminate casts. | |
738 | bool isLoopEntryGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, | |
739 | const SCEV *LHS, const SCEV *RHS); | |
740 | ||
741 | /// isLoopBackedgeGuardedByCond - Test whether the backedge of the loop is | |
742 | /// protected by a conditional between LHS and RHS. This is used to | |
743 | /// to eliminate casts. | |
744 | bool isLoopBackedgeGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, | |
745 | const SCEV *LHS, const SCEV *RHS); | |
746 | ||
85aaf69f SL |
747 | /// \brief Returns the maximum trip count of the loop if it is a single-exit |
748 | /// loop and we can compute a small maximum for that loop. | |
749 | /// | |
750 | /// Implemented in terms of the \c getSmallConstantTripCount overload with | |
751 | /// the single exiting block passed to it. See that routine for details. | |
752 | unsigned getSmallConstantTripCount(Loop *L); | |
753 | ||
223e47cc LB |
754 | /// getSmallConstantTripCount - Returns the maximum trip count of this loop |
755 | /// as a normal unsigned value. Returns 0 if the trip count is unknown or | |
756 | /// not constant. This "trip count" assumes that control exits via | |
757 | /// ExitingBlock. More precisely, it is the number of times that control may | |
758 | /// reach ExitingBlock before taking the branch. For loops with multiple | |
759 | /// exits, it may not be the number times that the loop header executes if | |
760 | /// the loop exits prematurely via another branch. | |
761 | unsigned getSmallConstantTripCount(Loop *L, BasicBlock *ExitingBlock); | |
762 | ||
85aaf69f SL |
763 | /// \brief Returns the largest constant divisor of the trip count of the |
764 | /// loop if it is a single-exit loop and we can compute a small maximum for | |
765 | /// that loop. | |
766 | /// | |
767 | /// Implemented in terms of the \c getSmallConstantTripMultiple overload with | |
768 | /// the single exiting block passed to it. See that routine for details. | |
769 | unsigned getSmallConstantTripMultiple(Loop *L); | |
770 | ||
223e47cc LB |
771 | /// getSmallConstantTripMultiple - Returns the largest constant divisor of |
772 | /// the trip count of this loop as a normal unsigned value, if | |
773 | /// possible. This means that the actual trip count is always a multiple of | |
774 | /// the returned value (don't forget the trip count could very well be zero | |
775 | /// as well!). As explained in the comments for getSmallConstantTripCount, | |
776 | /// this assumes that control exits the loop via ExitingBlock. | |
777 | unsigned getSmallConstantTripMultiple(Loop *L, BasicBlock *ExitingBlock); | |
778 | ||
779 | // getExitCount - Get the expression for the number of loop iterations for | |
780 | // which this loop is guaranteed not to exit via ExitingBlock. Otherwise | |
781 | // return SCEVCouldNotCompute. | |
782 | const SCEV *getExitCount(Loop *L, BasicBlock *ExitingBlock); | |
783 | ||
784 | /// getBackedgeTakenCount - If the specified loop has a predictable | |
785 | /// backedge-taken count, return it, otherwise return a SCEVCouldNotCompute | |
786 | /// object. The backedge-taken count is the number of times the loop header | |
787 | /// will be branched to from within the loop. This is one less than the | |
788 | /// trip count of the loop, since it doesn't count the first iteration, | |
789 | /// when the header is branched to from outside the loop. | |
790 | /// | |
791 | /// Note that it is not valid to call this method on a loop without a | |
792 | /// loop-invariant backedge-taken count (see | |
793 | /// hasLoopInvariantBackedgeTakenCount). | |
794 | /// | |
795 | const SCEV *getBackedgeTakenCount(const Loop *L); | |
796 | ||
797 | /// getMaxBackedgeTakenCount - Similar to getBackedgeTakenCount, except | |
798 | /// return the least SCEV value that is known never to be less than the | |
799 | /// actual backedge taken count. | |
800 | const SCEV *getMaxBackedgeTakenCount(const Loop *L); | |
801 | ||
802 | /// hasLoopInvariantBackedgeTakenCount - Return true if the specified loop | |
803 | /// has an analyzable loop-invariant backedge-taken count. | |
804 | bool hasLoopInvariantBackedgeTakenCount(const Loop *L); | |
805 | ||
806 | /// forgetLoop - This method should be called by the client when it has | |
807 | /// changed a loop in a way that may effect ScalarEvolution's ability to | |
1a4d82fc JJ |
808 | /// compute a trip count, or if the loop is deleted. This call is |
809 | /// potentially expensive for large loop bodies. | |
223e47cc LB |
810 | void forgetLoop(const Loop *L); |
811 | ||
812 | /// forgetValue - This method should be called by the client when it has | |
813 | /// changed a value in a way that may effect its value, or which may | |
814 | /// disconnect it from a def-use chain linking it to a loop. | |
815 | void forgetValue(Value *V); | |
816 | ||
1a4d82fc JJ |
817 | /// \brief Called when the client has changed the disposition of values in |
818 | /// this loop. | |
819 | /// | |
820 | /// We don't have a way to invalidate per-loop dispositions. Clear and | |
821 | /// recompute is simpler. | |
822 | void forgetLoopDispositions(const Loop *L) { LoopDispositions.clear(); } | |
823 | ||
223e47cc LB |
824 | /// GetMinTrailingZeros - Determine the minimum number of zero bits that S |
825 | /// is guaranteed to end in (at every loop iteration). It is, at the same | |
826 | /// time, the minimum number of times S is divisible by 2. For example, | |
827 | /// given {4,+,8} it returns 2. If S is guaranteed to be 0, it returns the | |
828 | /// bitwidth of S. | |
829 | uint32_t GetMinTrailingZeros(const SCEV *S); | |
830 | ||
831 | /// getUnsignedRange - Determine the unsigned range for a particular SCEV. | |
832 | /// | |
833 | ConstantRange getUnsignedRange(const SCEV *S); | |
834 | ||
835 | /// getSignedRange - Determine the signed range for a particular SCEV. | |
836 | /// | |
837 | ConstantRange getSignedRange(const SCEV *S); | |
838 | ||
839 | /// isKnownNegative - Test if the given expression is known to be negative. | |
840 | /// | |
841 | bool isKnownNegative(const SCEV *S); | |
842 | ||
843 | /// isKnownPositive - Test if the given expression is known to be positive. | |
844 | /// | |
845 | bool isKnownPositive(const SCEV *S); | |
846 | ||
847 | /// isKnownNonNegative - Test if the given expression is known to be | |
848 | /// non-negative. | |
849 | /// | |
850 | bool isKnownNonNegative(const SCEV *S); | |
851 | ||
852 | /// isKnownNonPositive - Test if the given expression is known to be | |
853 | /// non-positive. | |
854 | /// | |
855 | bool isKnownNonPositive(const SCEV *S); | |
856 | ||
857 | /// isKnownNonZero - Test if the given expression is known to be | |
858 | /// non-zero. | |
859 | /// | |
860 | bool isKnownNonZero(const SCEV *S); | |
861 | ||
862 | /// isKnownPredicate - Test if the given expression is known to satisfy | |
863 | /// the condition described by Pred, LHS, and RHS. | |
864 | /// | |
865 | bool isKnownPredicate(ICmpInst::Predicate Pred, | |
866 | const SCEV *LHS, const SCEV *RHS); | |
867 | ||
868 | /// SimplifyICmpOperands - Simplify LHS and RHS in a comparison with | |
869 | /// predicate Pred. Return true iff any changes were made. If the | |
970d7e83 | 870 | /// operands are provably equal or unequal, LHS and RHS are set to |
223e47cc LB |
871 | /// the same value and Pred is set to either ICMP_EQ or ICMP_NE. |
872 | /// | |
873 | bool SimplifyICmpOperands(ICmpInst::Predicate &Pred, | |
874 | const SCEV *&LHS, | |
875 | const SCEV *&RHS, | |
876 | unsigned Depth = 0); | |
877 | ||
878 | /// getLoopDisposition - Return the "disposition" of the given SCEV with | |
879 | /// respect to the given loop. | |
880 | LoopDisposition getLoopDisposition(const SCEV *S, const Loop *L); | |
881 | ||
882 | /// isLoopInvariant - Return true if the value of the given SCEV is | |
883 | /// unchanging in the specified loop. | |
884 | bool isLoopInvariant(const SCEV *S, const Loop *L); | |
885 | ||
886 | /// hasComputableLoopEvolution - Return true if the given SCEV changes value | |
887 | /// in a known way in the specified loop. This property being true implies | |
888 | /// that the value is variant in the loop AND that we can emit an expression | |
889 | /// to compute the value of the expression at any particular loop iteration. | |
890 | bool hasComputableLoopEvolution(const SCEV *S, const Loop *L); | |
891 | ||
892 | /// getLoopDisposition - Return the "disposition" of the given SCEV with | |
893 | /// respect to the given block. | |
894 | BlockDisposition getBlockDisposition(const SCEV *S, const BasicBlock *BB); | |
895 | ||
896 | /// dominates - Return true if elements that makes up the given SCEV | |
897 | /// dominate the specified basic block. | |
898 | bool dominates(const SCEV *S, const BasicBlock *BB); | |
899 | ||
900 | /// properlyDominates - Return true if elements that makes up the given SCEV | |
901 | /// properly dominate the specified basic block. | |
902 | bool properlyDominates(const SCEV *S, const BasicBlock *BB); | |
903 | ||
904 | /// hasOperand - Test whether the given SCEV has Op as a direct or | |
905 | /// indirect operand. | |
906 | bool hasOperand(const SCEV *S, const SCEV *Op) const; | |
907 | ||
1a4d82fc JJ |
908 | /// Return the size of an element read or written by Inst. |
909 | const SCEV *getElementSize(Instruction *Inst); | |
910 | ||
911 | /// Compute the array dimensions Sizes from the set of Terms extracted from | |
912 | /// the memory access function of this SCEVAddRecExpr. | |
913 | void findArrayDimensions(SmallVectorImpl<const SCEV *> &Terms, | |
914 | SmallVectorImpl<const SCEV *> &Sizes, | |
915 | const SCEV *ElementSize) const; | |
916 | ||
917 | bool runOnFunction(Function &F) override; | |
918 | void releaseMemory() override; | |
919 | void getAnalysisUsage(AnalysisUsage &AU) const override; | |
920 | void print(raw_ostream &OS, const Module* = nullptr) const override; | |
921 | void verifyAnalysis() const override; | |
922 | ||
923 | private: | |
924 | /// Compute the backedge taken count knowing the interval difference, the | |
925 | /// stride and presence of the equality in the comparison. | |
926 | const SCEV *computeBECount(const SCEV *Delta, const SCEV *Stride, | |
927 | bool Equality); | |
928 | ||
929 | /// Verify if an linear IV with positive stride can overflow when in a | |
930 | /// less-than comparison, knowing the invariant term of the comparison, | |
931 | /// the stride and the knowledge of NSW/NUW flags on the recurrence. | |
932 | bool doesIVOverflowOnLT(const SCEV *RHS, const SCEV *Stride, | |
933 | bool IsSigned, bool NoWrap); | |
934 | ||
935 | /// Verify if an linear IV with negative stride can overflow when in a | |
936 | /// greater-than comparison, knowing the invariant term of the comparison, | |
937 | /// the stride and the knowledge of NSW/NUW flags on the recurrence. | |
938 | bool doesIVOverflowOnGT(const SCEV *RHS, const SCEV *Stride, | |
939 | bool IsSigned, bool NoWrap); | |
223e47cc LB |
940 | |
941 | private: | |
942 | FoldingSet<SCEV> UniqueSCEVs; | |
943 | BumpPtrAllocator SCEVAllocator; | |
944 | ||
945 | /// FirstUnknown - The head of a linked list of all SCEVUnknown | |
946 | /// values that have been allocated. This is used by releaseMemory | |
947 | /// to locate them all and call their destructors. | |
948 | SCEVUnknown *FirstUnknown; | |
949 | }; | |
950 | } | |
951 | ||
952 | #endif |