1 //===- llvm/Analysis/ScalarEvolutionExpressions.h - SCEV Exprs --*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines the classes used to represent and build scalar expressions.
12 //===----------------------------------------------------------------------===//
14 #ifndef LLVM_ANALYSIS_SCALAREVOLUTION_EXPRESSIONS_H
15 #define LLVM_ANALYSIS_SCALAREVOLUTION_EXPRESSIONS_H
17 #include "llvm/Analysis/ScalarEvolution.h"
26 // These should be ordered in terms of increasing complexity to make the
28 scConstant, scTruncate, scZeroExtend, scSignExtend, scAddExpr, scMulExpr,
29 scUDivExpr, scAddRecExpr, scUMaxExpr, scSMaxExpr, scUnknown,
33 //===--------------------------------------------------------------------===//
34 /// SCEVConstant - This class represents a constant integer value.
36 class SCEVConstant : public SCEV {
37 friend class ScalarEvolution;
40 explicit SCEVConstant(ConstantInt *v) : SCEV(scConstant), V(v) {}
42 virtual ~SCEVConstant();
44 ConstantInt *getValue() const { return V; }
46 virtual bool isLoopInvariant(const Loop *L) const {
50 virtual bool hasComputableLoopEvolution(const Loop *L) const {
51 return false; // Not loop variant
54 virtual const Type *getType() const;
56 SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
57 const SCEVHandle &Conc,
58 ScalarEvolution &SE) const {
62 bool dominates(BasicBlock *BB, DominatorTree *DT) const {
66 virtual void print(raw_ostream &OS) const;
68 /// Methods for support type inquiry through isa, cast, and dyn_cast:
69 static inline bool classof(const SCEVConstant *S) { return true; }
70 static inline bool classof(const SCEV *S) {
71 return S->getSCEVType() == scConstant;
75 //===--------------------------------------------------------------------===//
76 /// SCEVTruncateExpr - This class represents a truncation of an integer value
77 /// to a smaller integer value.
79 class SCEVTruncateExpr : public SCEV {
80 friend class ScalarEvolution;
84 SCEVTruncateExpr(const SCEVHandle &op, const Type *ty);
85 virtual ~SCEVTruncateExpr();
87 const SCEVHandle &getOperand() const { return Op; }
88 virtual const Type *getType() const { return Ty; }
90 virtual bool isLoopInvariant(const Loop *L) const {
91 return Op->isLoopInvariant(L);
94 virtual bool hasComputableLoopEvolution(const Loop *L) const {
95 return Op->hasComputableLoopEvolution(L);
98 SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
99 const SCEVHandle &Conc,
100 ScalarEvolution &SE) const {
101 SCEVHandle H = Op->replaceSymbolicValuesWithConcrete(Sym, Conc, SE);
104 return SE.getTruncateExpr(H, Ty);
107 virtual bool dominates(BasicBlock *BB, DominatorTree *DT) const;
109 virtual void print(raw_ostream &OS) const;
111 /// Methods for support type inquiry through isa, cast, and dyn_cast:
112 static inline bool classof(const SCEVTruncateExpr *S) { return true; }
113 static inline bool classof(const SCEV *S) {
114 return S->getSCEVType() == scTruncate;
118 //===--------------------------------------------------------------------===//
119 /// SCEVZeroExtendExpr - This class represents a zero extension of a small
120 /// integer value to a larger integer value.
122 class SCEVZeroExtendExpr : public SCEV {
123 friend class ScalarEvolution;
127 SCEVZeroExtendExpr(const SCEVHandle &op, const Type *ty);
128 virtual ~SCEVZeroExtendExpr();
130 const SCEVHandle &getOperand() const { return Op; }
131 virtual const Type *getType() const { return Ty; }
133 virtual bool isLoopInvariant(const Loop *L) const {
134 return Op->isLoopInvariant(L);
137 virtual bool hasComputableLoopEvolution(const Loop *L) const {
138 return Op->hasComputableLoopEvolution(L);
141 SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
142 const SCEVHandle &Conc,
143 ScalarEvolution &SE) const {
144 SCEVHandle H = Op->replaceSymbolicValuesWithConcrete(Sym, Conc, SE);
147 return SE.getZeroExtendExpr(H, Ty);
150 bool dominates(BasicBlock *BB, DominatorTree *DT) const;
152 virtual void print(raw_ostream &OS) const;
154 /// Methods for support type inquiry through isa, cast, and dyn_cast:
155 static inline bool classof(const SCEVZeroExtendExpr *S) { return true; }
156 static inline bool classof(const SCEV *S) {
157 return S->getSCEVType() == scZeroExtend;
161 //===--------------------------------------------------------------------===//
162 /// SCEVSignExtendExpr - This class represents a sign extension of a small
163 /// integer value to a larger integer value.
165 class SCEVSignExtendExpr : public SCEV {
166 friend class ScalarEvolution;
170 SCEVSignExtendExpr(const SCEVHandle &op, const Type *ty);
171 virtual ~SCEVSignExtendExpr();
173 const SCEVHandle &getOperand() const { return Op; }
174 virtual const Type *getType() const { return Ty; }
176 virtual bool isLoopInvariant(const Loop *L) const {
177 return Op->isLoopInvariant(L);
180 virtual bool hasComputableLoopEvolution(const Loop *L) const {
181 return Op->hasComputableLoopEvolution(L);
184 SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
185 const SCEVHandle &Conc,
186 ScalarEvolution &SE) const {
187 SCEVHandle H = Op->replaceSymbolicValuesWithConcrete(Sym, Conc, SE);
190 return SE.getSignExtendExpr(H, Ty);
193 bool dominates(BasicBlock *BB, DominatorTree *DT) const;
195 virtual void print(raw_ostream &OS) const;
197 /// Methods for support type inquiry through isa, cast, and dyn_cast:
198 static inline bool classof(const SCEVSignExtendExpr *S) { return true; }
199 static inline bool classof(const SCEV *S) {
200 return S->getSCEVType() == scSignExtend;
205 //===--------------------------------------------------------------------===//
206 /// SCEVCommutativeExpr - This node is the base class for n'ary commutative
209 class SCEVCommutativeExpr : public SCEV {
210 friend class ScalarEvolution;
212 std::vector<SCEVHandle> Operands;
215 SCEVCommutativeExpr(enum SCEVTypes T, const std::vector<SCEVHandle> &ops)
217 Operands.reserve(ops.size());
218 Operands.insert(Operands.end(), ops.begin(), ops.end());
220 ~SCEVCommutativeExpr();
223 unsigned getNumOperands() const { return (unsigned)Operands.size(); }
224 const SCEVHandle &getOperand(unsigned i) const {
225 assert(i < Operands.size() && "Operand index out of range!");
229 const std::vector<SCEVHandle> &getOperands() const { return Operands; }
230 typedef std::vector<SCEVHandle>::const_iterator op_iterator;
231 op_iterator op_begin() const { return Operands.begin(); }
232 op_iterator op_end() const { return Operands.end(); }
235 virtual bool isLoopInvariant(const Loop *L) const {
236 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
237 if (!getOperand(i)->isLoopInvariant(L)) return false;
241 // hasComputableLoopEvolution - Commutative expressions have computable loop
242 // evolutions iff they have at least one operand that varies with the loop,
243 // but that all varying operands are computable.
244 virtual bool hasComputableLoopEvolution(const Loop *L) const {
245 bool HasVarying = false;
246 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
247 if (!getOperand(i)->isLoopInvariant(L)) {
248 if (getOperand(i)->hasComputableLoopEvolution(L))
256 SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
257 const SCEVHandle &Conc,
258 ScalarEvolution &SE) const;
260 bool dominates(BasicBlock *BB, DominatorTree *DT) const;
262 virtual const char *getOperationStr() const = 0;
264 virtual const Type *getType() const { return getOperand(0)->getType(); }
265 virtual void print(raw_ostream &OS) const;
267 /// Methods for support type inquiry through isa, cast, and dyn_cast:
268 static inline bool classof(const SCEVCommutativeExpr *S) { return true; }
269 static inline bool classof(const SCEV *S) {
270 return S->getSCEVType() == scAddExpr ||
271 S->getSCEVType() == scMulExpr ||
272 S->getSCEVType() == scSMaxExpr ||
273 S->getSCEVType() == scUMaxExpr;
278 //===--------------------------------------------------------------------===//
279 /// SCEVAddExpr - This node represents an addition of some number of SCEVs.
281 class SCEVAddExpr : public SCEVCommutativeExpr {
282 friend class ScalarEvolution;
284 explicit SCEVAddExpr(const std::vector<SCEVHandle> &ops)
285 : SCEVCommutativeExpr(scAddExpr, ops) {
289 virtual const char *getOperationStr() const { return " + "; }
291 /// Methods for support type inquiry through isa, cast, and dyn_cast:
292 static inline bool classof(const SCEVAddExpr *S) { return true; }
293 static inline bool classof(const SCEV *S) {
294 return S->getSCEVType() == scAddExpr;
298 //===--------------------------------------------------------------------===//
299 /// SCEVMulExpr - This node represents multiplication of some number of SCEVs.
301 class SCEVMulExpr : public SCEVCommutativeExpr {
302 friend class ScalarEvolution;
304 explicit SCEVMulExpr(const std::vector<SCEVHandle> &ops)
305 : SCEVCommutativeExpr(scMulExpr, ops) {
309 virtual const char *getOperationStr() const { return " * "; }
311 /// Methods for support type inquiry through isa, cast, and dyn_cast:
312 static inline bool classof(const SCEVMulExpr *S) { return true; }
313 static inline bool classof(const SCEV *S) {
314 return S->getSCEVType() == scMulExpr;
319 //===--------------------------------------------------------------------===//
320 /// SCEVUDivExpr - This class represents a binary unsigned division operation.
322 class SCEVUDivExpr : public SCEV {
323 friend class ScalarEvolution;
326 SCEVUDivExpr(const SCEVHandle &lhs, const SCEVHandle &rhs)
327 : SCEV(scUDivExpr), LHS(lhs), RHS(rhs) {}
329 virtual ~SCEVUDivExpr();
331 const SCEVHandle &getLHS() const { return LHS; }
332 const SCEVHandle &getRHS() const { return RHS; }
334 virtual bool isLoopInvariant(const Loop *L) const {
335 return LHS->isLoopInvariant(L) && RHS->isLoopInvariant(L);
338 virtual bool hasComputableLoopEvolution(const Loop *L) const {
339 return LHS->hasComputableLoopEvolution(L) &&
340 RHS->hasComputableLoopEvolution(L);
343 SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
344 const SCEVHandle &Conc,
345 ScalarEvolution &SE) const {
346 SCEVHandle L = LHS->replaceSymbolicValuesWithConcrete(Sym, Conc, SE);
347 SCEVHandle R = RHS->replaceSymbolicValuesWithConcrete(Sym, Conc, SE);
348 if (L == LHS && R == RHS)
351 return SE.getUDivExpr(L, R);
354 bool dominates(BasicBlock *BB, DominatorTree *DT) const;
356 virtual const Type *getType() const;
358 void print(raw_ostream &OS) const;
360 /// Methods for support type inquiry through isa, cast, and dyn_cast:
361 static inline bool classof(const SCEVUDivExpr *S) { return true; }
362 static inline bool classof(const SCEV *S) {
363 return S->getSCEVType() == scUDivExpr;
368 //===--------------------------------------------------------------------===//
369 /// SCEVAddRecExpr - This node represents a polynomial recurrence on the trip
370 /// count of the specified loop.
372 /// All operands of an AddRec are required to be loop invariant.
374 class SCEVAddRecExpr : public SCEV {
375 friend class ScalarEvolution;
377 std::vector<SCEVHandle> Operands;
380 SCEVAddRecExpr(const std::vector<SCEVHandle> &ops, const Loop *l)
381 : SCEV(scAddRecExpr), Operands(ops), L(l) {
382 for (size_t i = 0, e = Operands.size(); i != e; ++i)
383 assert(Operands[i]->isLoopInvariant(l) &&
384 "Operands of AddRec must be loop-invariant!");
388 typedef std::vector<SCEVHandle>::const_iterator op_iterator;
389 op_iterator op_begin() const { return Operands.begin(); }
390 op_iterator op_end() const { return Operands.end(); }
392 unsigned getNumOperands() const { return (unsigned)Operands.size(); }
393 const SCEVHandle &getOperand(unsigned i) const { return Operands[i]; }
394 const SCEVHandle &getStart() const { return Operands[0]; }
395 const Loop *getLoop() const { return L; }
398 /// getStepRecurrence - This method constructs and returns the recurrence
399 /// indicating how much this expression steps by. If this is a polynomial
400 /// of degree N, it returns a chrec of degree N-1.
401 SCEVHandle getStepRecurrence(ScalarEvolution &SE) const {
402 if (isAffine()) return getOperand(1);
403 return SE.getAddRecExpr(std::vector<SCEVHandle>(op_begin()+1,op_end()),
407 virtual bool hasComputableLoopEvolution(const Loop *QL) const {
408 if (L == QL) return true;
412 virtual bool isLoopInvariant(const Loop *QueryLoop) const;
414 virtual const Type *getType() const { return Operands[0]->getType(); }
416 /// isAffine - Return true if this is an affine AddRec (i.e., it represents
417 /// an expressions A+B*x where A and B are loop invariant values.
418 bool isAffine() const {
419 // We know that the start value is invariant. This expression is thus
420 // affine iff the step is also invariant.
421 return getNumOperands() == 2;
424 /// isQuadratic - Return true if this is an quadratic AddRec (i.e., it
425 /// represents an expressions A+B*x+C*x^2 where A, B and C are loop
426 /// invariant values. This corresponds to an addrec of the form {L,+,M,+,N}
427 bool isQuadratic() const {
428 return getNumOperands() == 3;
431 /// evaluateAtIteration - Return the value of this chain of recurrences at
432 /// the specified iteration number.
433 SCEVHandle evaluateAtIteration(SCEVHandle It, ScalarEvolution &SE) const;
435 /// getNumIterationsInRange - Return the number of iterations of this loop
436 /// that produce values in the specified constant range. Another way of
437 /// looking at this is that it returns the first iteration number where the
438 /// value is not in the condition, thus computing the exit count. If the
439 /// iteration count can't be computed, an instance of SCEVCouldNotCompute is
441 SCEVHandle getNumIterationsInRange(ConstantRange Range,
442 ScalarEvolution &SE) const;
444 SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
445 const SCEVHandle &Conc,
446 ScalarEvolution &SE) const;
448 bool dominates(BasicBlock *BB, DominatorTree *DT) const;
450 virtual void print(raw_ostream &OS) const;
452 /// Methods for support type inquiry through isa, cast, and dyn_cast:
453 static inline bool classof(const SCEVAddRecExpr *S) { return true; }
454 static inline bool classof(const SCEV *S) {
455 return S->getSCEVType() == scAddRecExpr;
460 //===--------------------------------------------------------------------===//
461 /// SCEVSMaxExpr - This class represents a signed maximum selection.
463 class SCEVSMaxExpr : public SCEVCommutativeExpr {
464 friend class ScalarEvolution;
466 explicit SCEVSMaxExpr(const std::vector<SCEVHandle> &ops)
467 : SCEVCommutativeExpr(scSMaxExpr, ops) {
471 virtual const char *getOperationStr() const { return " smax "; }
473 /// Methods for support type inquiry through isa, cast, and dyn_cast:
474 static inline bool classof(const SCEVSMaxExpr *S) { return true; }
475 static inline bool classof(const SCEV *S) {
476 return S->getSCEVType() == scSMaxExpr;
481 //===--------------------------------------------------------------------===//
482 /// SCEVUMaxExpr - This class represents an unsigned maximum selection.
484 class SCEVUMaxExpr : public SCEVCommutativeExpr {
485 friend class ScalarEvolution;
487 explicit SCEVUMaxExpr(const std::vector<SCEVHandle> &ops)
488 : SCEVCommutativeExpr(scUMaxExpr, ops) {
492 virtual const char *getOperationStr() const { return " umax "; }
494 /// Methods for support type inquiry through isa, cast, and dyn_cast:
495 static inline bool classof(const SCEVUMaxExpr *S) { return true; }
496 static inline bool classof(const SCEV *S) {
497 return S->getSCEVType() == scUMaxExpr;
502 //===--------------------------------------------------------------------===//
503 /// SCEVUnknown - This means that we are dealing with an entirely unknown SCEV
504 /// value, and only represent it as it's LLVM Value. This is the "bottom"
505 /// value for the analysis.
507 class SCEVUnknown : public SCEV {
508 friend class ScalarEvolution;
511 explicit SCEVUnknown(Value *v) : SCEV(scUnknown), V(v) {}
516 Value *getValue() const { return V; }
518 virtual bool isLoopInvariant(const Loop *L) const;
519 virtual bool hasComputableLoopEvolution(const Loop *QL) const {
520 return false; // not computable
523 SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
524 const SCEVHandle &Conc,
525 ScalarEvolution &SE) const {
526 if (&*Sym == this) return Conc;
530 bool dominates(BasicBlock *BB, DominatorTree *DT) const;
532 virtual const Type *getType() const;
534 virtual void print(raw_ostream &OS) const;
536 /// Methods for support type inquiry through isa, cast, and dyn_cast:
537 static inline bool classof(const SCEVUnknown *S) { return true; }
538 static inline bool classof(const SCEV *S) {
539 return S->getSCEVType() == scUnknown;
543 /// SCEVVisitor - This class defines a simple visitor class that may be used
544 /// for various SCEV analysis purposes.
545 template<typename SC, typename RetVal=void>
547 RetVal visit(const SCEV *S) {
548 switch (S->getSCEVType()) {
550 return ((SC*)this)->visitConstant((const SCEVConstant*)S);
552 return ((SC*)this)->visitTruncateExpr((const SCEVTruncateExpr*)S);
554 return ((SC*)this)->visitZeroExtendExpr((const SCEVZeroExtendExpr*)S);
556 return ((SC*)this)->visitSignExtendExpr((const SCEVSignExtendExpr*)S);
558 return ((SC*)this)->visitAddExpr((const SCEVAddExpr*)S);
560 return ((SC*)this)->visitMulExpr((const SCEVMulExpr*)S);
562 return ((SC*)this)->visitUDivExpr((const SCEVUDivExpr*)S);
564 return ((SC*)this)->visitAddRecExpr((const SCEVAddRecExpr*)S);
566 return ((SC*)this)->visitSMaxExpr((const SCEVSMaxExpr*)S);
568 return ((SC*)this)->visitUMaxExpr((const SCEVUMaxExpr*)S);
570 return ((SC*)this)->visitUnknown((const SCEVUnknown*)S);
571 case scCouldNotCompute:
572 return ((SC*)this)->visitCouldNotCompute((const SCEVCouldNotCompute*)S);
574 assert(0 && "Unknown SCEV type!");
579 RetVal visitCouldNotCompute(const SCEVCouldNotCompute *S) {
580 assert(0 && "Invalid use of SCEVCouldNotCompute!");