2e4fd7e2106c77ec35b3a81826facee279436f8c
[oota-llvm.git] / include / llvm / Analysis / ScalarEvolutionExpressions.h
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, unsigned Num, ConstantInt *v)
41       : SCEV(ID, Num, 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, unsigned Num,
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, unsigned Num,
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, unsigned Num,
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, unsigned Num,
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, unsigned Num,
191                  enum SCEVTypes T, const SCEV *const *O, size_t N)
192       : SCEV(ID, Num, 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       for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
207         if (!getOperand(i)->isLoopInvariant(L)) return false;
208       return true;
209     }
210
211     // hasComputableLoopEvolution - N-ary expressions have computable loop
212     // evolutions iff they have at least one operand that varies with the loop,
213     // but that all varying operands are computable.
214     virtual bool hasComputableLoopEvolution(const Loop *L) const {
215       bool HasVarying = false;
216       for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
217         if (!getOperand(i)->isLoopInvariant(L)) {
218           if (getOperand(i)->hasComputableLoopEvolution(L))
219             HasVarying = true;
220           else
221             return false;
222         }
223       return HasVarying;
224     }
225
226     virtual bool hasOperand(const SCEV *O) const {
227       for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
228         if (O == getOperand(i) || getOperand(i)->hasOperand(O))
229           return true;
230       return false;
231     }
232
233     bool dominates(BasicBlock *BB, DominatorTree *DT) const;
234
235     bool properlyDominates(BasicBlock *BB, DominatorTree *DT) const;
236
237     virtual const Type *getType() const { return getOperand(0)->getType(); }
238
239     bool hasNoUnsignedWrap() const { return SubclassData & (1 << 0); }
240     void setHasNoUnsignedWrap(bool B) {
241       SubclassData = (SubclassData & ~(1 << 0)) | (B << 0);
242     }
243     bool hasNoSignedWrap() const { return SubclassData & (1 << 1); }
244     void setHasNoSignedWrap(bool B) {
245       SubclassData = (SubclassData & ~(1 << 1)) | (B << 1);
246     }
247
248     /// Methods for support type inquiry through isa, cast, and dyn_cast:
249     static inline bool classof(const SCEVNAryExpr *S) { return true; }
250     static inline bool classof(const SCEV *S) {
251       return S->getSCEVType() == scAddExpr ||
252              S->getSCEVType() == scMulExpr ||
253              S->getSCEVType() == scSMaxExpr ||
254              S->getSCEVType() == scUMaxExpr ||
255              S->getSCEVType() == scAddRecExpr;
256     }
257   };
258
259   //===--------------------------------------------------------------------===//
260   /// SCEVCommutativeExpr - This node is the base class for n'ary commutative
261   /// operators.
262   ///
263   class SCEVCommutativeExpr : public SCEVNAryExpr {
264   protected:
265     SCEVCommutativeExpr(const FoldingSetNodeIDRef ID, unsigned Num,
266                         enum SCEVTypes T, const SCEV *const *O, size_t N)
267       : SCEVNAryExpr(ID, Num, T, O, N) {}
268
269   public:
270     virtual const char *getOperationStr() const = 0;
271
272     virtual void print(raw_ostream &OS) const;
273
274     /// Methods for support type inquiry through isa, cast, and dyn_cast:
275     static inline bool classof(const SCEVCommutativeExpr *S) { return true; }
276     static inline bool classof(const SCEV *S) {
277       return S->getSCEVType() == scAddExpr ||
278              S->getSCEVType() == scMulExpr ||
279              S->getSCEVType() == scSMaxExpr ||
280              S->getSCEVType() == scUMaxExpr;
281     }
282   };
283
284
285   //===--------------------------------------------------------------------===//
286   /// SCEVAddExpr - This node represents an addition of some number of SCEVs.
287   ///
288   class SCEVAddExpr : public SCEVCommutativeExpr {
289     friend class ScalarEvolution;
290
291     SCEVAddExpr(const FoldingSetNodeIDRef ID, unsigned Num,
292                 const SCEV *const *O, size_t N)
293       : SCEVCommutativeExpr(ID, Num, scAddExpr, O, N) {
294     }
295
296   public:
297     virtual const char *getOperationStr() const { return " + "; }
298
299     virtual const Type *getType() const {
300       // Use the type of the last operand, which is likely to be a pointer
301       // type, if there is one. This doesn't usually matter, but it can help
302       // reduce casts when the expressions are expanded.
303       return getOperand(getNumOperands() - 1)->getType();
304     }
305
306     /// Methods for support type inquiry through isa, cast, and dyn_cast:
307     static inline bool classof(const SCEVAddExpr *S) { return true; }
308     static inline bool classof(const SCEV *S) {
309       return S->getSCEVType() == scAddExpr;
310     }
311   };
312
313   //===--------------------------------------------------------------------===//
314   /// SCEVMulExpr - This node represents multiplication of some number of SCEVs.
315   ///
316   class SCEVMulExpr : public SCEVCommutativeExpr {
317     friend class ScalarEvolution;
318
319     SCEVMulExpr(const FoldingSetNodeIDRef ID, unsigned Num,
320                 const SCEV *const *O, size_t N)
321       : SCEVCommutativeExpr(ID, Num, scMulExpr, O, N) {
322     }
323
324   public:
325     virtual const char *getOperationStr() const { return " * "; }
326
327     /// Methods for support type inquiry through isa, cast, and dyn_cast:
328     static inline bool classof(const SCEVMulExpr *S) { return true; }
329     static inline bool classof(const SCEV *S) {
330       return S->getSCEVType() == scMulExpr;
331     }
332   };
333
334
335   //===--------------------------------------------------------------------===//
336   /// SCEVUDivExpr - This class represents a binary unsigned division operation.
337   ///
338   class SCEVUDivExpr : public SCEV {
339     friend class ScalarEvolution;
340
341     const SCEV *LHS;
342     const SCEV *RHS;
343     SCEVUDivExpr(const FoldingSetNodeIDRef ID, unsigned Num,
344                  const SCEV *lhs, const SCEV *rhs)
345       : SCEV(ID, Num, scUDivExpr), LHS(lhs), RHS(rhs) {}
346
347   public:
348     const SCEV *getLHS() const { return LHS; }
349     const SCEV *getRHS() const { return RHS; }
350
351     virtual bool isLoopInvariant(const Loop *L) const {
352       return LHS->isLoopInvariant(L) && RHS->isLoopInvariant(L);
353     }
354
355     virtual bool hasComputableLoopEvolution(const Loop *L) const {
356       return LHS->hasComputableLoopEvolution(L) &&
357              RHS->hasComputableLoopEvolution(L);
358     }
359
360     virtual bool hasOperand(const SCEV *O) const {
361       return O == LHS || O == RHS || LHS->hasOperand(O) || RHS->hasOperand(O);
362     }
363
364     bool dominates(BasicBlock *BB, DominatorTree *DT) const;
365
366     bool properlyDominates(BasicBlock *BB, DominatorTree *DT) const;
367
368     virtual const Type *getType() const;
369
370     void print(raw_ostream &OS) const;
371
372     /// Methods for support type inquiry through isa, cast, and dyn_cast:
373     static inline bool classof(const SCEVUDivExpr *S) { return true; }
374     static inline bool classof(const SCEV *S) {
375       return S->getSCEVType() == scUDivExpr;
376     }
377   };
378
379
380   //===--------------------------------------------------------------------===//
381   /// SCEVAddRecExpr - This node represents a polynomial recurrence on the trip
382   /// count of the specified loop.  This is the primary focus of the
383   /// ScalarEvolution framework; all the other SCEV subclasses are mostly just
384   /// supporting infrastructure to allow SCEVAddRecExpr expressions to be
385   /// created and analyzed.
386   ///
387   /// All operands of an AddRec are required to be loop invariant.
388   ///
389   class SCEVAddRecExpr : public SCEVNAryExpr {
390     friend class ScalarEvolution;
391
392     const Loop *L;
393
394     SCEVAddRecExpr(const FoldingSetNodeIDRef ID, unsigned Num,
395                    const SCEV *const *O, size_t N, const Loop *l)
396       : SCEVNAryExpr(ID, Num, scAddRecExpr, O, N), L(l) {
397       for (size_t i = 0, e = NumOperands; i != e; ++i)
398         assert(Operands[i]->isLoopInvariant(l) &&
399                "Operands of AddRec must be loop-invariant!");
400     }
401
402   public:
403     const SCEV *getStart() const { return Operands[0]; }
404     const Loop *getLoop() const { return L; }
405
406     /// getStepRecurrence - This method constructs and returns the recurrence
407     /// indicating how much this expression steps by.  If this is a polynomial
408     /// of degree N, it returns a chrec of degree N-1.
409     const SCEV *getStepRecurrence(ScalarEvolution &SE) const {
410       if (isAffine()) return getOperand(1);
411       return SE.getAddRecExpr(SmallVector<const SCEV *, 3>(op_begin()+1,
412                                                            op_end()),
413                               getLoop());
414     }
415
416     virtual bool hasComputableLoopEvolution(const Loop *QL) const {
417       return L == QL;
418     }
419
420     virtual bool isLoopInvariant(const Loop *QueryLoop) const;
421
422     bool dominates(BasicBlock *BB, DominatorTree *DT) const;
423
424     bool properlyDominates(BasicBlock *BB, DominatorTree *DT) const;
425
426     /// isAffine - Return true if this is an affine AddRec (i.e., it represents
427     /// an expressions A+B*x where A and B are loop invariant values.
428     bool isAffine() const {
429       // We know that the start value is invariant.  This expression is thus
430       // affine iff the step is also invariant.
431       return getNumOperands() == 2;
432     }
433
434     /// isQuadratic - Return true if this is an quadratic AddRec (i.e., it
435     /// represents an expressions A+B*x+C*x^2 where A, B and C are loop
436     /// invariant values.  This corresponds to an addrec of the form {L,+,M,+,N}
437     bool isQuadratic() const {
438       return getNumOperands() == 3;
439     }
440
441     /// evaluateAtIteration - Return the value of this chain of recurrences at
442     /// the specified iteration number.
443     const SCEV *evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const;
444
445     /// getNumIterationsInRange - Return the number of iterations of this loop
446     /// that produce values in the specified constant range.  Another way of
447     /// looking at this is that it returns the first iteration number where the
448     /// value is not in the condition, thus computing the exit count.  If the
449     /// iteration count can't be computed, an instance of SCEVCouldNotCompute is
450     /// returned.
451     const SCEV *getNumIterationsInRange(ConstantRange Range,
452                                        ScalarEvolution &SE) const;
453
454     /// getPostIncExpr - Return an expression representing the value of
455     /// this expression one iteration of the loop ahead.
456     const SCEVAddRecExpr *getPostIncExpr(ScalarEvolution &SE) const {
457       return cast<SCEVAddRecExpr>(SE.getAddExpr(this, getStepRecurrence(SE)));
458     }
459
460     virtual void print(raw_ostream &OS) const;
461
462     /// Methods for support type inquiry through isa, cast, and dyn_cast:
463     static inline bool classof(const SCEVAddRecExpr *S) { return true; }
464     static inline bool classof(const SCEV *S) {
465       return S->getSCEVType() == scAddRecExpr;
466     }
467   };
468
469
470   //===--------------------------------------------------------------------===//
471   /// SCEVSMaxExpr - This class represents a signed maximum selection.
472   ///
473   class SCEVSMaxExpr : public SCEVCommutativeExpr {
474     friend class ScalarEvolution;
475
476     SCEVSMaxExpr(const FoldingSetNodeIDRef ID, unsigned Num,
477                  const SCEV *const *O, size_t N)
478       : SCEVCommutativeExpr(ID, Num, scSMaxExpr, O, N) {
479       // Max never overflows.
480       setHasNoUnsignedWrap(true);
481       setHasNoSignedWrap(true);
482     }
483
484   public:
485     virtual const char *getOperationStr() const { return " smax "; }
486
487     /// Methods for support type inquiry through isa, cast, and dyn_cast:
488     static inline bool classof(const SCEVSMaxExpr *S) { return true; }
489     static inline bool classof(const SCEV *S) {
490       return S->getSCEVType() == scSMaxExpr;
491     }
492   };
493
494
495   //===--------------------------------------------------------------------===//
496   /// SCEVUMaxExpr - This class represents an unsigned maximum selection.
497   ///
498   class SCEVUMaxExpr : public SCEVCommutativeExpr {
499     friend class ScalarEvolution;
500
501     SCEVUMaxExpr(const FoldingSetNodeIDRef ID, unsigned Num,
502                  const SCEV *const *O, size_t N)
503       : SCEVCommutativeExpr(ID, Num, scUMaxExpr, O, N) {
504       // Max never overflows.
505       setHasNoUnsignedWrap(true);
506       setHasNoSignedWrap(true);
507     }
508
509   public:
510     virtual const char *getOperationStr() const { return " umax "; }
511
512     /// Methods for support type inquiry through isa, cast, and dyn_cast:
513     static inline bool classof(const SCEVUMaxExpr *S) { return true; }
514     static inline bool classof(const SCEV *S) {
515       return S->getSCEVType() == scUMaxExpr;
516     }
517   };
518
519   //===--------------------------------------------------------------------===//
520   /// SCEVUnknown - This means that we are dealing with an entirely unknown SCEV
521   /// value, and only represent it as its LLVM Value.  This is the "bottom"
522   /// value for the analysis.
523   ///
524   class SCEVUnknown : public SCEV {
525     friend class ScalarEvolution;
526
527     Value *V;
528     SCEVUnknown(const FoldingSetNodeIDRef ID, unsigned Num, Value *v)
529       : SCEV(ID, Num, scUnknown), V(v) {}
530
531   public:
532     Value *getValue() const { return V; }
533
534     /// isSizeOf, isAlignOf, isOffsetOf - Test whether this is a special
535     /// constant representing a type size, alignment, or field offset in
536     /// a target-independent manner, and hasn't happened to have been
537     /// folded with other operations into something unrecognizable. This
538     /// is mainly only useful for pretty-printing and other situations
539     /// where it isn't absolutely required for these to succeed.
540     bool isSizeOf(const Type *&AllocTy) const;
541     bool isAlignOf(const Type *&AllocTy) const;
542     bool isOffsetOf(const Type *&STy, Constant *&FieldNo) const;
543
544     virtual bool isLoopInvariant(const Loop *L) const;
545     virtual bool hasComputableLoopEvolution(const Loop *QL) const {
546       return false; // not computable
547     }
548
549     virtual bool hasOperand(const SCEV *) const {
550       return false;
551     }
552
553     bool dominates(BasicBlock *BB, DominatorTree *DT) const;
554
555     bool properlyDominates(BasicBlock *BB, DominatorTree *DT) const;
556
557     virtual const Type *getType() const;
558
559     virtual void print(raw_ostream &OS) const;
560
561     /// Methods for support type inquiry through isa, cast, and dyn_cast:
562     static inline bool classof(const SCEVUnknown *S) { return true; }
563     static inline bool classof(const SCEV *S) {
564       return S->getSCEVType() == scUnknown;
565     }
566   };
567
568   /// SCEVVisitor - This class defines a simple visitor class that may be used
569   /// for various SCEV analysis purposes.
570   template<typename SC, typename RetVal=void>
571   struct SCEVVisitor {
572     RetVal visit(const SCEV *S) {
573       switch (S->getSCEVType()) {
574       case scConstant:
575         return ((SC*)this)->visitConstant((const SCEVConstant*)S);
576       case scTruncate:
577         return ((SC*)this)->visitTruncateExpr((const SCEVTruncateExpr*)S);
578       case scZeroExtend:
579         return ((SC*)this)->visitZeroExtendExpr((const SCEVZeroExtendExpr*)S);
580       case scSignExtend:
581         return ((SC*)this)->visitSignExtendExpr((const SCEVSignExtendExpr*)S);
582       case scAddExpr:
583         return ((SC*)this)->visitAddExpr((const SCEVAddExpr*)S);
584       case scMulExpr:
585         return ((SC*)this)->visitMulExpr((const SCEVMulExpr*)S);
586       case scUDivExpr:
587         return ((SC*)this)->visitUDivExpr((const SCEVUDivExpr*)S);
588       case scAddRecExpr:
589         return ((SC*)this)->visitAddRecExpr((const SCEVAddRecExpr*)S);
590       case scSMaxExpr:
591         return ((SC*)this)->visitSMaxExpr((const SCEVSMaxExpr*)S);
592       case scUMaxExpr:
593         return ((SC*)this)->visitUMaxExpr((const SCEVUMaxExpr*)S);
594       case scUnknown:
595         return ((SC*)this)->visitUnknown((const SCEVUnknown*)S);
596       case scCouldNotCompute:
597         return ((SC*)this)->visitCouldNotCompute((const SCEVCouldNotCompute*)S);
598       default:
599         llvm_unreachable("Unknown SCEV type!");
600       }
601     }
602
603     RetVal visitCouldNotCompute(const SCEVCouldNotCompute *S) {
604       llvm_unreachable("Invalid use of SCEVCouldNotCompute!");
605       return RetVal();
606     }
607   };
608 }
609
610 #endif