0.47.15
by Scott Kitterman
Import upstream version 0.98.6+dfsg |
1 |
//===- llvm/Analysis/ScalarEvolutionExpressions.h - SCEV Exprs --*- 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 |
// This file defines the classes used to represent and build scalar expressions.
|
|
11 |
//
|
|
12 |
//===----------------------------------------------------------------------===//
|
|
13 |
||
14 |
#ifndef LLVM_ANALYSIS_SCALAREVOLUTION_EXPRESSIONS_H
|
|
15 |
#define LLVM_ANALYSIS_SCALAREVOLUTION_EXPRESSIONS_H
|
|
16 |
||
17 |
#include "llvm/Analysis/ScalarEvolution.h" |
|
18 |
#include "llvm/Support/ErrorHandling.h" |
|
19 |
||
20 |
namespace llvm { |
|
21 |
class ConstantInt; |
|
22 |
class ConstantRange; |
|
23 |
class DominatorTree; |
|
24 |
||
25 |
enum SCEVTypes { |
|
26 |
// These should be ordered in terms of increasing complexity to make the
|
|
27 |
// folders simpler.
|
|
28 |
scConstant, scTruncate, scZeroExtend, scSignExtend, scAddExpr, scMulExpr, |
|
29 |
scUDivExpr, scAddRecExpr, scUMaxExpr, scSMaxExpr, |
|
30 |
scUnknown, scCouldNotCompute |
|
31 |
};
|
|
32 |
||
33 |
//===--------------------------------------------------------------------===//
|
|
34 |
/// SCEVConstant - This class represents a constant integer value.
|
|
35 |
///
|
|
36 |
class SCEVConstant : public SCEV { |
|
37 |
friend class ScalarEvolution; |
|
38 |
||
39 |
ConstantInt *V; |
|
40 |
SCEVConstant(const FoldingSetNodeIDRef ID, ConstantInt *v) : |
|
41 |
SCEV(ID, scConstant), V(v) {} |
|
42 |
public: |
|
43 |
ConstantInt *getValue() const { return V; } |
|
44 |
||
45 |
virtual bool isLoopInvariant(const Loop *L) const { |
|
46 |
return true; |
|
47 |
}
|
|
48 |
||
49 |
virtual bool hasComputableLoopEvolution(const Loop *L) const { |
|
50 |
return false; // Not loop variant |
|
51 |
}
|
|
52 |
||
53 |
virtual const Type *getType() const; |
|
54 |
||
55 |
virtual bool hasOperand(const SCEV *) const { |
|
56 |
return false; |
|
57 |
}
|
|
58 |
||
59 |
bool dominates(BasicBlock *BB, DominatorTree *DT) const { |
|
60 |
return true; |
|
61 |
}
|
|
62 |
||
63 |
bool properlyDominates(BasicBlock *BB, DominatorTree *DT) const { |
|
64 |
return true; |
|
65 |
}
|
|
66 |
||
67 |
virtual void print(raw_ostream &OS) const; |
|
68 |
||
69 |
/// Methods for support type inquiry through isa, cast, and dyn_cast:
|
|
70 |
static inline bool classof(const SCEVConstant *S) { return true; } |
|
71 |
static inline bool classof(const SCEV *S) { |
|
72 |
return S->getSCEVType() == scConstant; |
|
73 |
}
|
|
74 |
};
|
|
75 |
||
76 |
//===--------------------------------------------------------------------===//
|
|
77 |
/// SCEVCastExpr - This is the base class for unary cast operator classes.
|
|
78 |
///
|
|
79 |
class SCEVCastExpr : public SCEV { |
|
80 |
protected: |
|
81 |
const SCEV *Op; |
|
82 |
const Type *Ty; |
|
83 |
||
84 |
SCEVCastExpr(const FoldingSetNodeIDRef ID, |
|
85 |
unsigned SCEVTy, const SCEV *op, const Type *ty); |
|
86 |
||
87 |
public: |
|
88 |
const SCEV *getOperand() const { return Op; } |
|
89 |
virtual const Type *getType() const { return Ty; } |
|
90 |
||
91 |
virtual bool isLoopInvariant(const Loop *L) const { |
|
92 |
return Op->isLoopInvariant(L); |
|
93 |
}
|
|
94 |
||
95 |
virtual bool hasComputableLoopEvolution(const Loop *L) const { |
|
96 |
return Op->hasComputableLoopEvolution(L); |
|
97 |
}
|
|
98 |
||
99 |
virtual bool hasOperand(const SCEV *O) const { |
|
100 |
return Op == O || Op->hasOperand(O); |
|
101 |
}
|
|
102 |
||
103 |
virtual bool dominates(BasicBlock *BB, DominatorTree *DT) const; |
|
104 |
||
105 |
virtual bool properlyDominates(BasicBlock *BB, DominatorTree *DT) const; |
|
106 |
||
107 |
/// Methods for support type inquiry through isa, cast, and dyn_cast:
|
|
108 |
static inline bool classof(const SCEVCastExpr *S) { return true; } |
|
109 |
static inline bool classof(const SCEV *S) { |
|
110 |
return S->getSCEVType() == scTruncate || |
|
111 |
S->getSCEVType() == scZeroExtend || |
|
112 |
S->getSCEVType() == scSignExtend; |
|
113 |
}
|
|
114 |
};
|
|
115 |
||
116 |
//===--------------------------------------------------------------------===//
|
|
117 |
/// SCEVTruncateExpr - This class represents a truncation of an integer value
|
|
118 |
/// to a smaller integer value.
|
|
119 |
///
|
|
120 |
class SCEVTruncateExpr : public SCEVCastExpr { |
|
121 |
friend class ScalarEvolution; |
|
122 |
||
123 |
SCEVTruncateExpr(const FoldingSetNodeIDRef ID, |
|
124 |
const SCEV *op, const Type *ty); |
|
125 |
||
126 |
public: |
|
127 |
virtual void print(raw_ostream &OS) const; |
|
128 |
||
129 |
/// Methods for support type inquiry through isa, cast, and dyn_cast:
|
|
130 |
static inline bool classof(const SCEVTruncateExpr *S) { return true; } |
|
131 |
static inline bool classof(const SCEV *S) { |
|
132 |
return S->getSCEVType() == scTruncate; |
|
133 |
}
|
|
134 |
};
|
|
135 |
||
136 |
//===--------------------------------------------------------------------===//
|
|
137 |
/// SCEVZeroExtendExpr - This class represents a zero extension of a small
|
|
138 |
/// integer value to a larger integer value.
|
|
139 |
///
|
|
140 |
class SCEVZeroExtendExpr : public SCEVCastExpr { |
|
141 |
friend class ScalarEvolution; |
|
142 |
||
143 |
SCEVZeroExtendExpr(const FoldingSetNodeIDRef ID, |
|
144 |
const SCEV *op, const Type *ty); |
|
145 |
||
146 |
public: |
|
147 |
virtual void print(raw_ostream &OS) const; |
|
148 |
||
149 |
/// Methods for support type inquiry through isa, cast, and dyn_cast:
|
|
150 |
static inline bool classof(const SCEVZeroExtendExpr *S) { return true; } |
|
151 |
static inline bool classof(const SCEV *S) { |
|
152 |
return S->getSCEVType() == scZeroExtend; |
|
153 |
}
|
|
154 |
};
|
|
155 |
||
156 |
//===--------------------------------------------------------------------===//
|
|
157 |
/// SCEVSignExtendExpr - This class represents a sign extension of a small
|
|
158 |
/// integer value to a larger integer value.
|
|
159 |
///
|
|
160 |
class SCEVSignExtendExpr : public SCEVCastExpr { |
|
161 |
friend class ScalarEvolution; |
|
162 |
||
163 |
SCEVSignExtendExpr(const FoldingSetNodeIDRef ID, |
|
164 |
const SCEV *op, const Type *ty); |
|
165 |
||
166 |
public: |
|
167 |
virtual void print(raw_ostream &OS) const; |
|
168 |
||
169 |
/// Methods for support type inquiry through isa, cast, and dyn_cast:
|
|
170 |
static inline bool classof(const SCEVSignExtendExpr *S) { return true; } |
|
171 |
static inline bool classof(const SCEV *S) { |
|
172 |
return S->getSCEVType() == scSignExtend; |
|
173 |
}
|
|
174 |
};
|
|
175 |
||
176 |
||
177 |
//===--------------------------------------------------------------------===//
|
|
178 |
/// SCEVNAryExpr - This node is a base class providing common
|
|
179 |
/// functionality for n'ary operators.
|
|
180 |
///
|
|
181 |
class SCEVNAryExpr : public SCEV { |
|
182 |
protected: |
|
183 |
// Since SCEVs are immutable, ScalarEvolution allocates operand
|
|
184 |
// arrays with its SCEVAllocator, so this class just needs a simple
|
|
185 |
// pointer rather than a more elaborate vector-like data structure.
|
|
186 |
// This also avoids the need for a non-trivial destructor.
|
|
187 |
const SCEV *const *Operands; |
|
188 |
size_t NumOperands; |
|
189 |
||
190 |
SCEVNAryExpr(const FoldingSetNodeIDRef ID, |
|
191 |
enum SCEVTypes T, const SCEV *const *O, size_t N) |
|
192 |
: SCEV(ID, T), Operands(O), NumOperands(N) {} |
|
193 |
||
194 |
public: |
|
195 |
size_t getNumOperands() const { return NumOperands; } |
|
196 |
const SCEV *getOperand(unsigned i) const { |
|
197 |
assert(i < NumOperands && "Operand index out of range!"); |
|
198 |
return Operands[i]; |
|
199 |
}
|
|
200 |
||
201 |
typedef const SCEV *const *op_iterator; |
|
202 |
op_iterator op_begin() const { return Operands; } |
|
203 |
op_iterator op_end() const { return Operands + NumOperands; } |
|
204 |
||
205 |
virtual bool isLoopInvariant(const Loop *L) const; |
|
206 |
||
207 |
// hasComputableLoopEvolution - N-ary expressions have computable loop
|
|
208 |
// evolutions iff they have at least one operand that varies with the loop,
|
|
209 |
// but that all varying operands are computable.
|
|
210 |
virtual bool hasComputableLoopEvolution(const Loop *L) const; |
|
211 |
||
212 |
virtual bool hasOperand(const SCEV *O) const; |
|
213 |
||
214 |
bool dominates(BasicBlock *BB, DominatorTree *DT) const; |
|
215 |
||
216 |
bool properlyDominates(BasicBlock *BB, DominatorTree *DT) const; |
|
217 |
||
218 |
virtual const Type *getType() const { return getOperand(0)->getType(); } |
|
219 |
||
220 |
bool hasNoUnsignedWrap() const { return SubclassData & (1 << 0); } |
|
221 |
void setHasNoUnsignedWrap(bool B) { |
|
222 |
SubclassData = (SubclassData & ~(1 << 0)) | (B << 0); |
|
223 |
}
|
|
224 |
bool hasNoSignedWrap() const { return SubclassData & (1 << 1); } |
|
225 |
void setHasNoSignedWrap(bool B) { |
|
226 |
SubclassData = (SubclassData & ~(1 << 1)) | (B << 1); |
|
227 |
}
|
|
228 |
||
229 |
/// Methods for support type inquiry through isa, cast, and dyn_cast:
|
|
230 |
static inline bool classof(const SCEVNAryExpr *S) { return true; } |
|
231 |
static inline bool classof(const SCEV *S) { |
|
232 |
return S->getSCEVType() == scAddExpr || |
|
233 |
S->getSCEVType() == scMulExpr || |
|
234 |
S->getSCEVType() == scSMaxExpr || |
|
235 |
S->getSCEVType() == scUMaxExpr || |
|
236 |
S->getSCEVType() == scAddRecExpr; |
|
237 |
}
|
|
238 |
};
|
|
239 |
||
240 |
//===--------------------------------------------------------------------===//
|
|
241 |
/// SCEVCommutativeExpr - This node is the base class for n'ary commutative
|
|
242 |
/// operators.
|
|
243 |
///
|
|
244 |
class SCEVCommutativeExpr : public SCEVNAryExpr { |
|
245 |
protected: |
|
246 |
SCEVCommutativeExpr(const FoldingSetNodeIDRef ID, |
|
247 |
enum SCEVTypes T, const SCEV *const *O, size_t N) |
|
248 |
: SCEVNAryExpr(ID, T, O, N) {} |
|
249 |
||
250 |
public: |
|
251 |
virtual const char *getOperationStr() const = 0; |
|
252 |
||
253 |
virtual void print(raw_ostream &OS) const; |
|
254 |
||
255 |
/// Methods for support type inquiry through isa, cast, and dyn_cast:
|
|
256 |
static inline bool classof(const SCEVCommutativeExpr *S) { return true; } |
|
257 |
static inline bool classof(const SCEV *S) { |
|
258 |
return S->getSCEVType() == scAddExpr || |
|
259 |
S->getSCEVType() == scMulExpr || |
|
260 |
S->getSCEVType() == scSMaxExpr || |
|
261 |
S->getSCEVType() == scUMaxExpr; |
|
262 |
}
|
|
263 |
};
|
|
264 |
||
265 |
||
266 |
//===--------------------------------------------------------------------===//
|
|
267 |
/// SCEVAddExpr - This node represents an addition of some number of SCEVs.
|
|
268 |
///
|
|
269 |
class SCEVAddExpr : public SCEVCommutativeExpr { |
|
270 |
friend class ScalarEvolution; |
|
271 |
||
272 |
SCEVAddExpr(const FoldingSetNodeIDRef ID, |
|
273 |
const SCEV *const *O, size_t N) |
|
274 |
: SCEVCommutativeExpr(ID, scAddExpr, O, N) { |
|
275 |
}
|
|
276 |
||
277 |
public: |
|
278 |
virtual const char *getOperationStr() const { return " + "; } |
|
279 |
||
280 |
virtual const Type *getType() const { |
|
281 |
// Use the type of the last operand, which is likely to be a pointer
|
|
282 |
// type, if there is one. This doesn't usually matter, but it can help
|
|
283 |
// reduce casts when the expressions are expanded.
|
|
284 |
return getOperand(getNumOperands() - 1)->getType(); |
|
285 |
}
|
|
286 |
||
287 |
/// Methods for support type inquiry through isa, cast, and dyn_cast:
|
|
288 |
static inline bool classof(const SCEVAddExpr *S) { return true; } |
|
289 |
static inline bool classof(const SCEV *S) { |
|
290 |
return S->getSCEVType() == scAddExpr; |
|
291 |
}
|
|
292 |
};
|
|
293 |
||
294 |
//===--------------------------------------------------------------------===//
|
|
295 |
/// SCEVMulExpr - This node represents multiplication of some number of SCEVs.
|
|
296 |
///
|
|
297 |
class SCEVMulExpr : public SCEVCommutativeExpr { |
|
298 |
friend class ScalarEvolution; |
|
299 |
||
300 |
SCEVMulExpr(const FoldingSetNodeIDRef ID, |
|
301 |
const SCEV *const *O, size_t N) |
|
302 |
: SCEVCommutativeExpr(ID, scMulExpr, O, N) { |
|
303 |
}
|
|
304 |
||
305 |
public: |
|
306 |
virtual const char *getOperationStr() const { return " * "; } |
|
307 |
||
308 |
/// Methods for support type inquiry through isa, cast, and dyn_cast:
|
|
309 |
static inline bool classof(const SCEVMulExpr *S) { return true; } |
|
310 |
static inline bool classof(const SCEV *S) { |
|
311 |
return S->getSCEVType() == scMulExpr; |
|
312 |
}
|
|
313 |
};
|
|
314 |
||
315 |
||
316 |
//===--------------------------------------------------------------------===//
|
|
317 |
/// SCEVUDivExpr - This class represents a binary unsigned division operation.
|
|
318 |
///
|
|
319 |
class SCEVUDivExpr : public SCEV { |
|
320 |
friend class ScalarEvolution; |
|
321 |
||
322 |
const SCEV *LHS; |
|
323 |
const SCEV *RHS; |
|
324 |
SCEVUDivExpr(const FoldingSetNodeIDRef ID, const SCEV *lhs, const SCEV *rhs) |
|
325 |
: SCEV(ID, scUDivExpr), LHS(lhs), RHS(rhs) {} |
|
326 |
||
327 |
public: |
|
328 |
const SCEV *getLHS() const { return LHS; } |
|
329 |
const SCEV *getRHS() const { return RHS; } |
|
330 |
||
331 |
virtual bool isLoopInvariant(const Loop *L) const { |
|
332 |
return LHS->isLoopInvariant(L) && RHS->isLoopInvariant(L); |
|
333 |
}
|
|
334 |
||
335 |
virtual bool hasComputableLoopEvolution(const Loop *L) const { |
|
336 |
return LHS->hasComputableLoopEvolution(L) && |
|
337 |
RHS->hasComputableLoopEvolution(L); |
|
338 |
}
|
|
339 |
||
340 |
virtual bool hasOperand(const SCEV *O) const { |
|
341 |
return O == LHS || O == RHS || LHS->hasOperand(O) || RHS->hasOperand(O); |
|
342 |
}
|
|
343 |
||
344 |
bool dominates(BasicBlock *BB, DominatorTree *DT) const; |
|
345 |
||
346 |
bool properlyDominates(BasicBlock *BB, DominatorTree *DT) const; |
|
347 |
||
348 |
virtual const Type *getType() const; |
|
349 |
||
350 |
void print(raw_ostream &OS) const; |
|
351 |
||
352 |
/// Methods for support type inquiry through isa, cast, and dyn_cast:
|
|
353 |
static inline bool classof(const SCEVUDivExpr *S) { return true; } |
|
354 |
static inline bool classof(const SCEV *S) { |
|
355 |
return S->getSCEVType() == scUDivExpr; |
|
356 |
}
|
|
357 |
};
|
|
358 |
||
359 |
||
360 |
//===--------------------------------------------------------------------===//
|
|
361 |
/// SCEVAddRecExpr - This node represents a polynomial recurrence on the trip
|
|
362 |
/// count of the specified loop. This is the primary focus of the
|
|
363 |
/// ScalarEvolution framework; all the other SCEV subclasses are mostly just
|
|
364 |
/// supporting infrastructure to allow SCEVAddRecExpr expressions to be
|
|
365 |
/// created and analyzed.
|
|
366 |
///
|
|
367 |
/// All operands of an AddRec are required to be loop invariant.
|
|
368 |
///
|
|
369 |
class SCEVAddRecExpr : public SCEVNAryExpr { |
|
370 |
friend class ScalarEvolution; |
|
371 |
||
372 |
const Loop *L; |
|
373 |
||
374 |
SCEVAddRecExpr(const FoldingSetNodeIDRef ID, |
|
375 |
const SCEV *const *O, size_t N, const Loop *l) |
|
376 |
: SCEVNAryExpr(ID, scAddRecExpr, O, N), L(l) { |
|
377 |
for (size_t i = 0, e = NumOperands; i != e; ++i) |
|
378 |
assert(Operands[i]->isLoopInvariant(l) && |
|
379 |
"Operands of AddRec must be loop-invariant!"); |
|
380 |
}
|
|
381 |
||
382 |
public: |
|
383 |
const SCEV *getStart() const { return Operands[0]; } |
|
384 |
const Loop *getLoop() const { return L; } |
|
385 |
||
386 |
/// getStepRecurrence - This method constructs and returns the recurrence
|
|
387 |
/// indicating how much this expression steps by. If this is a polynomial
|
|
388 |
/// of degree N, it returns a chrec of degree N-1.
|
|
389 |
const SCEV *getStepRecurrence(ScalarEvolution &SE) const { |
|
390 |
if (isAffine()) return getOperand(1); |
|
391 |
return SE.getAddRecExpr(SmallVector<const SCEV *, 3>(op_begin()+1, |
|
392 |
op_end()), |
|
393 |
getLoop()); |
|
394 |
}
|
|
395 |
||
396 |
virtual bool hasComputableLoopEvolution(const Loop *QL) const { |
|
397 |
return L == QL; |
|
398 |
}
|
|
399 |
||
400 |
virtual bool isLoopInvariant(const Loop *QueryLoop) const; |
|
401 |
||
402 |
bool dominates(BasicBlock *BB, DominatorTree *DT) const; |
|
403 |
||
404 |
bool properlyDominates(BasicBlock *BB, DominatorTree *DT) const; |
|
405 |
||
406 |
/// isAffine - Return true if this is an affine AddRec (i.e., it represents
|
|
407 |
/// an expressions A+B*x where A and B are loop invariant values.
|
|
408 |
bool isAffine() const { |
|
409 |
// We know that the start value is invariant. This expression is thus
|
|
410 |
// affine iff the step is also invariant.
|
|
411 |
return getNumOperands() == 2; |
|
412 |
}
|
|
413 |
||
414 |
/// isQuadratic - Return true if this is an quadratic AddRec (i.e., it
|
|
415 |
/// represents an expressions A+B*x+C*x^2 where A, B and C are loop
|
|
416 |
/// invariant values. This corresponds to an addrec of the form {L,+,M,+,N}
|
|
417 |
bool isQuadratic() const { |
|
418 |
return getNumOperands() == 3; |
|
419 |
}
|
|
420 |
||
421 |
/// evaluateAtIteration - Return the value of this chain of recurrences at
|
|
422 |
/// the specified iteration number.
|
|
423 |
const SCEV *evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const; |
|
424 |
||
425 |
/// getNumIterationsInRange - Return the number of iterations of this loop
|
|
426 |
/// that produce values in the specified constant range. Another way of
|
|
427 |
/// looking at this is that it returns the first iteration number where the
|
|
428 |
/// value is not in the condition, thus computing the exit count. If the
|
|
429 |
/// iteration count can't be computed, an instance of SCEVCouldNotCompute is
|
|
430 |
/// returned.
|
|
431 |
const SCEV *getNumIterationsInRange(ConstantRange Range, |
|
432 |
ScalarEvolution &SE) const; |
|
433 |
||
434 |
/// getPostIncExpr - Return an expression representing the value of
|
|
435 |
/// this expression one iteration of the loop ahead.
|
|
436 |
const SCEVAddRecExpr *getPostIncExpr(ScalarEvolution &SE) const { |
|
437 |
return cast<SCEVAddRecExpr>(SE.getAddExpr(this, getStepRecurrence(SE))); |
|
438 |
}
|
|
439 |
||
440 |
virtual void print(raw_ostream &OS) const; |
|
441 |
||
442 |
/// Methods for support type inquiry through isa, cast, and dyn_cast:
|
|
443 |
static inline bool classof(const SCEVAddRecExpr *S) { return true; } |
|
444 |
static inline bool classof(const SCEV *S) { |
|
445 |
return S->getSCEVType() == scAddRecExpr; |
|
446 |
}
|
|
447 |
};
|
|
448 |
||
449 |
||
450 |
//===--------------------------------------------------------------------===//
|
|
451 |
/// SCEVSMaxExpr - This class represents a signed maximum selection.
|
|
452 |
///
|
|
453 |
class SCEVSMaxExpr : public SCEVCommutativeExpr { |
|
454 |
friend class ScalarEvolution; |
|
455 |
||
456 |
SCEVSMaxExpr(const FoldingSetNodeIDRef ID, |
|
457 |
const SCEV *const *O, size_t N) |
|
458 |
: SCEVCommutativeExpr(ID, scSMaxExpr, O, N) { |
|
459 |
// Max never overflows.
|
|
460 |
setHasNoUnsignedWrap(true); |
|
461 |
setHasNoSignedWrap(true); |
|
462 |
}
|
|
463 |
||
464 |
public: |
|
465 |
virtual const char *getOperationStr() const { return " smax "; } |
|
466 |
||
467 |
/// Methods for support type inquiry through isa, cast, and dyn_cast:
|
|
468 |
static inline bool classof(const SCEVSMaxExpr *S) { return true; } |
|
469 |
static inline bool classof(const SCEV *S) { |
|
470 |
return S->getSCEVType() == scSMaxExpr; |
|
471 |
}
|
|
472 |
};
|
|
473 |
||
474 |
||
475 |
//===--------------------------------------------------------------------===//
|
|
476 |
/// SCEVUMaxExpr - This class represents an unsigned maximum selection.
|
|
477 |
///
|
|
478 |
class SCEVUMaxExpr : public SCEVCommutativeExpr { |
|
479 |
friend class ScalarEvolution; |
|
480 |
||
481 |
SCEVUMaxExpr(const FoldingSetNodeIDRef ID, |
|
482 |
const SCEV *const *O, size_t N) |
|
483 |
: SCEVCommutativeExpr(ID, scUMaxExpr, O, N) { |
|
484 |
// Max never overflows.
|
|
485 |
setHasNoUnsignedWrap(true); |
|
486 |
setHasNoSignedWrap(true); |
|
487 |
}
|
|
488 |
||
489 |
public: |
|
490 |
virtual const char *getOperationStr() const { return " umax "; } |
|
491 |
||
492 |
/// Methods for support type inquiry through isa, cast, and dyn_cast:
|
|
493 |
static inline bool classof(const SCEVUMaxExpr *S) { return true; } |
|
494 |
static inline bool classof(const SCEV *S) { |
|
495 |
return S->getSCEVType() == scUMaxExpr; |
|
496 |
}
|
|
497 |
};
|
|
498 |
||
499 |
//===--------------------------------------------------------------------===//
|
|
500 |
/// SCEVUnknown - This means that we are dealing with an entirely unknown SCEV
|
|
501 |
/// value, and only represent it as its LLVM Value. This is the "bottom"
|
|
502 |
/// value for the analysis.
|
|
503 |
///
|
|
504 |
class SCEVUnknown : public SCEV, private CallbackVH { |
|
505 |
friend class ScalarEvolution; |
|
506 |
||
507 |
// Implement CallbackVH.
|
|
508 |
virtual void deleted(); |
|
509 |
virtual void allUsesReplacedWith(Value *New); |
|
510 |
||
511 |
/// SE - The parent ScalarEvolution value. This is used to update
|
|
512 |
/// the parent's maps when the value associated with a SCEVUnknown
|
|
513 |
/// is deleted or RAUW'd.
|
|
514 |
ScalarEvolution *SE; |
|
515 |
||
516 |
/// Next - The next pointer in the linked list of all
|
|
517 |
/// SCEVUnknown instances owned by a ScalarEvolution.
|
|
518 |
SCEVUnknown *Next; |
|
519 |
||
520 |
SCEVUnknown(const FoldingSetNodeIDRef ID, Value *V, |
|
521 |
ScalarEvolution *se, SCEVUnknown *next) : |
|
522 |
SCEV(ID, scUnknown), CallbackVH(V), SE(se), Next(next) {} |
|
523 |
||
524 |
public: |
|
525 |
Value *getValue() const { return getValPtr(); } |
|
526 |
||
527 |
/// isSizeOf, isAlignOf, isOffsetOf - Test whether this is a special
|
|
528 |
/// constant representing a type size, alignment, or field offset in
|
|
529 |
/// a target-independent manner, and hasn't happened to have been
|
|
530 |
/// folded with other operations into something unrecognizable. This
|
|
531 |
/// is mainly only useful for pretty-printing and other situations
|
|
532 |
/// where it isn't absolutely required for these to succeed.
|
|
533 |
bool isSizeOf(const Type *&AllocTy) const; |
|
534 |
bool isAlignOf(const Type *&AllocTy) const; |
|
535 |
bool isOffsetOf(const Type *&STy, Constant *&FieldNo) const; |
|
536 |
||
537 |
virtual bool isLoopInvariant(const Loop *L) const; |
|
538 |
virtual bool hasComputableLoopEvolution(const Loop *QL) const { |
|
539 |
return false; // not computable |
|
540 |
}
|
|
541 |
||
542 |
virtual bool hasOperand(const SCEV *) const { |
|
543 |
return false; |
|
544 |
}
|
|
545 |
||
546 |
bool dominates(BasicBlock *BB, DominatorTree *DT) const; |
|
547 |
||
548 |
bool properlyDominates(BasicBlock *BB, DominatorTree *DT) const; |
|
549 |
||
550 |
virtual const Type *getType() const; |
|
551 |
||
552 |
virtual void print(raw_ostream &OS) const; |
|
553 |
||
554 |
/// Methods for support type inquiry through isa, cast, and dyn_cast:
|
|
555 |
static inline bool classof(const SCEVUnknown *S) { return true; } |
|
556 |
static inline bool classof(const SCEV *S) { |
|
557 |
return S->getSCEVType() == scUnknown; |
|
558 |
}
|
|
559 |
};
|
|
560 |
||
561 |
/// SCEVVisitor - This class defines a simple visitor class that may be used
|
|
562 |
/// for various SCEV analysis purposes.
|
|
563 |
template<typename SC, typename RetVal=void> |
|
564 |
struct SCEVVisitor { |
|
565 |
RetVal visit(const SCEV *S) { |
|
566 |
switch (S->getSCEVType()) { |
|
567 |
case scConstant: |
|
568 |
return ((SC*)this)->visitConstant((const SCEVConstant*)S); |
|
569 |
case scTruncate: |
|
570 |
return ((SC*)this)->visitTruncateExpr((const SCEVTruncateExpr*)S); |
|
571 |
case scZeroExtend: |
|
572 |
return ((SC*)this)->visitZeroExtendExpr((const SCEVZeroExtendExpr*)S); |
|
573 |
case scSignExtend: |
|
574 |
return ((SC*)this)->visitSignExtendExpr((const SCEVSignExtendExpr*)S); |
|
575 |
case scAddExpr: |
|
576 |
return ((SC*)this)->visitAddExpr((const SCEVAddExpr*)S); |
|
577 |
case scMulExpr: |
|
578 |
return ((SC*)this)->visitMulExpr((const SCEVMulExpr*)S); |
|
579 |
case scUDivExpr: |
|
580 |
return ((SC*)this)->visitUDivExpr((const SCEVUDivExpr*)S); |
|
581 |
case scAddRecExpr: |
|
582 |
return ((SC*)this)->visitAddRecExpr((const SCEVAddRecExpr*)S); |
|
583 |
case scSMaxExpr: |
|
584 |
return ((SC*)this)->visitSMaxExpr((const SCEVSMaxExpr*)S); |
|
585 |
case scUMaxExpr: |
|
586 |
return ((SC*)this)->visitUMaxExpr((const SCEVUMaxExpr*)S); |
|
587 |
case scUnknown: |
|
588 |
return ((SC*)this)->visitUnknown((const SCEVUnknown*)S); |
|
589 |
case scCouldNotCompute: |
|
590 |
return ((SC*)this)->visitCouldNotCompute((const SCEVCouldNotCompute*)S); |
|
591 |
default: |
|
592 |
llvm_unreachable("Unknown SCEV type!"); |
|
593 |
}
|
|
594 |
}
|
|
595 |
||
596 |
RetVal visitCouldNotCompute(const SCEVCouldNotCompute *S) { |
|
597 |
llvm_unreachable("Invalid use of SCEVCouldNotCompute!"); |
|
598 |
return RetVal(); |
|
599 |
}
|
|
600 |
};
|
|
601 |
}
|
|
602 |
||
603 |
#endif
|