ScalarEvolutionExpressions.h revision b7ef72963b2215ca23c27fa8ea777bada06994d0 
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
19namespace llvm {
20  class ConstantInt;
21  class ConstantRange;
22  class APInt;
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, scUnknown,
30    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    explicit SCEVConstant(ConstantInt *v) : SCEV(scConstant), V(v) {}
41
42    virtual ~SCEVConstant();
43  public:
44    ConstantInt *getValue() const { return V; }
45
46    virtual bool isLoopInvariant(const Loop *L) const {
47      return true;
48    }
49
50    virtual bool hasComputableLoopEvolution(const Loop *L) const {
51      return false;  // Not loop variant
52    }
53
54    virtual const Type *getType() const;
55
56    SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
57                                                 const SCEVHandle &Conc,
58                                                 ScalarEvolution &SE) const {
59      return this;
60    }
61
62    bool dominates(BasicBlock *BB, DominatorTree *DT) const {
63      return true;
64    }
65
66    virtual void print(raw_ostream &OS) const;
67
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;
72    }
73  };
74
75  //===--------------------------------------------------------------------===//
76  /// SCEVTruncateExpr - This class represents a truncation of an integer value
77  /// to a smaller integer value.
78  ///
79  class SCEVTruncateExpr : public SCEV {
80    friend class ScalarEvolution;
81
82    SCEVHandle Op;
83    const Type *Ty;
84    SCEVTruncateExpr(const SCEVHandle &op, const Type *ty);
85    virtual ~SCEVTruncateExpr();
86  public:
87    const SCEVHandle &getOperand() const { return Op; }
88    virtual const Type *getType() const { return Ty; }
89
90    virtual bool isLoopInvariant(const Loop *L) const {
91      return Op->isLoopInvariant(L);
92    }
93
94    virtual bool hasComputableLoopEvolution(const Loop *L) const {
95      return Op->hasComputableLoopEvolution(L);
96    }
97
98    SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
99                                                 const SCEVHandle &Conc,
100                                                 ScalarEvolution &SE) const {
101      SCEVHandle H = Op->replaceSymbolicValuesWithConcrete(Sym, Conc, SE);
102      if (H == Op)
103        return this;
104      return SE.getTruncateExpr(H, Ty);
105    }
106
107    virtual bool dominates(BasicBlock *BB, DominatorTree *DT) const;
108
109    virtual void print(raw_ostream &OS) const;
110
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;
115    }
116  };
117
118  //===--------------------------------------------------------------------===//
119  /// SCEVZeroExtendExpr - This class represents a zero extension of a small
120  /// integer value to a larger integer value.
121  ///
122  class SCEVZeroExtendExpr : public SCEV {
123    friend class ScalarEvolution;
124
125    SCEVHandle Op;
126    const Type *Ty;
127    SCEVZeroExtendExpr(const SCEVHandle &op, const Type *ty);
128    virtual ~SCEVZeroExtendExpr();
129  public:
130    const SCEVHandle &getOperand() const { return Op; }
131    virtual const Type *getType() const { return Ty; }
132
133    virtual bool isLoopInvariant(const Loop *L) const {
134      return Op->isLoopInvariant(L);
135    }
136
137    virtual bool hasComputableLoopEvolution(const Loop *L) const {
138      return Op->hasComputableLoopEvolution(L);
139    }
140
141    SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
142                                                 const SCEVHandle &Conc,
143                                                 ScalarEvolution &SE) const {
144      SCEVHandle H = Op->replaceSymbolicValuesWithConcrete(Sym, Conc, SE);
145      if (H == Op)
146        return this;
147      return SE.getZeroExtendExpr(H, Ty);
148    }
149
150    bool dominates(BasicBlock *BB, DominatorTree *DT) const;
151
152    virtual void print(raw_ostream &OS) const;
153
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;
158    }
159  };
160
161  //===--------------------------------------------------------------------===//
162  /// SCEVSignExtendExpr - This class represents a sign extension of a small
163  /// integer value to a larger integer value.
164  ///
165  class SCEVSignExtendExpr : public SCEV {
166    friend class ScalarEvolution;
167
168    SCEVHandle Op;
169    const Type *Ty;
170    SCEVSignExtendExpr(const SCEVHandle &op, const Type *ty);
171    virtual ~SCEVSignExtendExpr();
172  public:
173    const SCEVHandle &getOperand() const { return Op; }
174    virtual const Type *getType() const { return Ty; }
175
176    virtual bool isLoopInvariant(const Loop *L) const {
177      return Op->isLoopInvariant(L);
178    }
179
180    virtual bool hasComputableLoopEvolution(const Loop *L) const {
181      return Op->hasComputableLoopEvolution(L);
182    }
183
184    SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
185                                                 const SCEVHandle &Conc,
186                                                 ScalarEvolution &SE) const {
187      SCEVHandle H = Op->replaceSymbolicValuesWithConcrete(Sym, Conc, SE);
188      if (H == Op)
189        return this;
190      return SE.getSignExtendExpr(H, Ty);
191    }
192
193    bool dominates(BasicBlock *BB, DominatorTree *DT) const;
194
195    virtual void print(raw_ostream &OS) const;
196
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;
201    }
202  };
203
204
205  //===--------------------------------------------------------------------===//
206  /// SCEVCommutativeExpr - This node is the base class for n'ary commutative
207  /// operators.
208  ///
209  class SCEVCommutativeExpr : public SCEV {
210    friend class ScalarEvolution;
211
212    std::vector<SCEVHandle> Operands;
213
214  protected:
215    SCEVCommutativeExpr(enum SCEVTypes T, const std::vector<SCEVHandle> &ops)
216      : SCEV(T) {
217      Operands.reserve(ops.size());
218      Operands.insert(Operands.end(), ops.begin(), ops.end());
219    }
220    ~SCEVCommutativeExpr();
221
222  public:
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!");
226      return Operands[i];
227    }
228
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(); }
233
234
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;
238      return true;
239    }
240
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))
249            HasVarying = true;
250          else
251            return false;
252        }
253      return HasVarying;
254    }
255
256    SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
257                                                 const SCEVHandle &Conc,
258                                                 ScalarEvolution &SE) const;
259
260    bool dominates(BasicBlock *BB, DominatorTree *DT) const;
261
262    virtual const char *getOperationStr() const = 0;
263
264    virtual const Type *getType() const { return getOperand(0)->getType(); }
265    virtual void print(raw_ostream &OS) const;
266
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;
274    }
275  };
276
277
278  //===--------------------------------------------------------------------===//
279  /// SCEVAddExpr - This node represents an addition of some number of SCEVs.
280  ///
281  class SCEVAddExpr : public SCEVCommutativeExpr {
282    friend class ScalarEvolution;
283
284    explicit SCEVAddExpr(const std::vector<SCEVHandle> &ops)
285      : SCEVCommutativeExpr(scAddExpr, ops) {
286    }
287
288  public:
289    virtual const char *getOperationStr() const { return " + "; }
290
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;
295    }
296  };
297
298  //===--------------------------------------------------------------------===//
299  /// SCEVMulExpr - This node represents multiplication of some number of SCEVs.
300  ///
301  class SCEVMulExpr : public SCEVCommutativeExpr {
302    friend class ScalarEvolution;
303
304    explicit SCEVMulExpr(const std::vector<SCEVHandle> &ops)
305      : SCEVCommutativeExpr(scMulExpr, ops) {
306    }
307
308  public:
309    virtual const char *getOperationStr() const { return " * "; }
310
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;
315    }
316  };
317
318
319  //===--------------------------------------------------------------------===//
320  /// SCEVUDivExpr - This class represents a binary unsigned division operation.
321  ///
322  class SCEVUDivExpr : public SCEV {
323    friend class ScalarEvolution;
324
325    SCEVHandle LHS, RHS;
326    SCEVUDivExpr(const SCEVHandle &lhs, const SCEVHandle &rhs)
327      : SCEV(scUDivExpr), LHS(lhs), RHS(rhs) {}
328
329    virtual ~SCEVUDivExpr();
330  public:
331    const SCEVHandle &getLHS() const { return LHS; }
332    const SCEVHandle &getRHS() const { return RHS; }
333
334    virtual bool isLoopInvariant(const Loop *L) const {
335      return LHS->isLoopInvariant(L) && RHS->isLoopInvariant(L);
336    }
337
338    virtual bool hasComputableLoopEvolution(const Loop *L) const {
339      return LHS->hasComputableLoopEvolution(L) &&
340             RHS->hasComputableLoopEvolution(L);
341    }
342
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)
349        return this;
350      else
351        return SE.getUDivExpr(L, R);
352    }
353
354    bool dominates(BasicBlock *BB, DominatorTree *DT) const;
355
356    virtual const Type *getType() const;
357
358    void print(raw_ostream &OS) const;
359
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;
364    }
365  };
366
367
368  //===--------------------------------------------------------------------===//
369  /// SCEVAddRecExpr - This node represents a polynomial recurrence on the trip
370  /// count of the specified loop.
371  ///
372  /// All operands of an AddRec are required to be loop invariant.
373  ///
374  class SCEVAddRecExpr : public SCEV {
375    friend class ScalarEvolution;
376
377    std::vector<SCEVHandle> Operands;
378    const Loop *L;
379
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!");
385    }
386    ~SCEVAddRecExpr();
387  public:
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(); }
391
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; }
396
397
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()),
404                              getLoop());
405    }
406
407    virtual bool hasComputableLoopEvolution(const Loop *QL) const {
408      if (L == QL) return true;
409      return false;
410    }
411
412    virtual bool isLoopInvariant(const Loop *QueryLoop) const;
413
414    virtual const Type *getType() const { return Operands[0]->getType(); }
415
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;
422    }
423
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;
429    }
430
431    /// evaluateAtIteration - Return the value of this chain of recurrences at
432    /// the specified iteration number.
433    SCEVHandle evaluateAtIteration(SCEVHandle It, ScalarEvolution &SE) const;
434
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
440    /// returned.
441    SCEVHandle getNumIterationsInRange(ConstantRange Range,
442                                       ScalarEvolution &SE) const;
443
444    SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
445                                                 const SCEVHandle &Conc,
446                                                 ScalarEvolution &SE) const;
447
448    bool dominates(BasicBlock *BB, DominatorTree *DT) const;
449
450    virtual void print(raw_ostream &OS) const;
451
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;
456    }
457  };
458
459
460  //===--------------------------------------------------------------------===//
461  /// SCEVSMaxExpr - This class represents a signed maximum selection.
462  ///
463  class SCEVSMaxExpr : public SCEVCommutativeExpr {
464    friend class ScalarEvolution;
465
466    explicit SCEVSMaxExpr(const std::vector<SCEVHandle> &ops)
467      : SCEVCommutativeExpr(scSMaxExpr, ops) {
468    }
469
470  public:
471    virtual const char *getOperationStr() const { return " smax "; }
472
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;
477    }
478  };
479
480
481  //===--------------------------------------------------------------------===//
482  /// SCEVUMaxExpr - This class represents an unsigned maximum selection.
483  ///
484  class SCEVUMaxExpr : public SCEVCommutativeExpr {
485    friend class ScalarEvolution;
486
487    explicit SCEVUMaxExpr(const std::vector<SCEVHandle> &ops)
488      : SCEVCommutativeExpr(scUMaxExpr, ops) {
489    }
490
491  public:
492    virtual const char *getOperationStr() const { return " umax "; }
493
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;
498    }
499  };
500
501
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.
506  ///
507  class SCEVUnknown : public SCEV {
508    friend class ScalarEvolution;
509
510    Value *V;
511    explicit SCEVUnknown(Value *v) : SCEV(scUnknown), V(v) {}
512
513  protected:
514    ~SCEVUnknown();
515  public:
516    Value *getValue() const { return V; }
517
518    virtual bool isLoopInvariant(const Loop *L) const;
519    virtual bool hasComputableLoopEvolution(const Loop *QL) const {
520      return false; // not computable
521    }
522
523    SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
524                                                 const SCEVHandle &Conc,
525                                                 ScalarEvolution &SE) const {
526      if (&*Sym == this) return Conc;
527      return this;
528    }
529
530    bool dominates(BasicBlock *BB, DominatorTree *DT) const;
531
532    virtual const Type *getType() const;
533
534    virtual void print(raw_ostream &OS) const;
535
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;
540    }
541  };
542
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>
546  struct SCEVVisitor {
547    RetVal visit(const SCEV *S) {
548      switch (S->getSCEVType()) {
549      case scConstant:
550        return ((SC*)this)->visitConstant((const SCEVConstant*)S);
551      case scTruncate:
552        return ((SC*)this)->visitTruncateExpr((const SCEVTruncateExpr*)S);
553      case scZeroExtend:
554        return ((SC*)this)->visitZeroExtendExpr((const SCEVZeroExtendExpr*)S);
555      case scSignExtend:
556        return ((SC*)this)->visitSignExtendExpr((const SCEVSignExtendExpr*)S);
557      case scAddExpr:
558        return ((SC*)this)->visitAddExpr((const SCEVAddExpr*)S);
559      case scMulExpr:
560        return ((SC*)this)->visitMulExpr((const SCEVMulExpr*)S);
561      case scUDivExpr:
562        return ((SC*)this)->visitUDivExpr((const SCEVUDivExpr*)S);
563      case scAddRecExpr:
564        return ((SC*)this)->visitAddRecExpr((const SCEVAddRecExpr*)S);
565      case scSMaxExpr:
566        return ((SC*)this)->visitSMaxExpr((const SCEVSMaxExpr*)S);
567      case scUMaxExpr:
568        return ((SC*)this)->visitUMaxExpr((const SCEVUMaxExpr*)S);
569      case scUnknown:
570        return ((SC*)this)->visitUnknown((const SCEVUnknown*)S);
571      case scCouldNotCompute:
572        return ((SC*)this)->visitCouldNotCompute((const SCEVCouldNotCompute*)S);
573      default:
574        assert(0 && "Unknown SCEV type!");
575        abort();
576      }
577    }
578
579    RetVal visitCouldNotCompute(const SCEVCouldNotCompute *S) {
580      assert(0 && "Invalid use of SCEVCouldNotCompute!");
581      abort();
582      return RetVal();
583    }
584  };
585}
586
587#endif
588