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
  19 namespace llvm {
  20   class ConstantInt;
  21   class ConstantRange;
  22   class APInt;
  23
  24   enum SCEVTypes {
  25     // These should be ordered in terms of increasing complexity to make the
  26     // folders simpler.
  27     scConstant, scTruncate, scZeroExtend, scSignExtend, scAddExpr, scMulExpr,
  28     scUDivExpr, scAddRecExpr, scUMaxExpr, scSMaxExpr, scUnknown,
  29     scCouldNotCompute
  30   };
  31
  32   //===--------------------------------------------------------------------===//
  33   /// SCEVConstant - This class represents a constant integer value.
  34   ///
  35   class SCEVConstant : public SCEV {
  36     friend class ScalarEvolution;
  37
  38     ConstantInt *V;
  39     explicit SCEVConstant(ConstantInt *v) : SCEV(scConstant), V(v) {}
  40
  41     virtual ~SCEVConstant();
  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     SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
  56                                                  const SCEVHandle &Conc,
  57                                                  ScalarEvolution &SE) const {
  58       return this;
  59     }
  60
  61     virtual void print(std::ostream &OS) const;
  62     void print(std::ostream *OS) const { if (OS) print(*OS); }
  63
  64     /// Methods for support type inquiry through isa, cast, and dyn_cast:
  65     static inline bool classof(const SCEVConstant *S) { return true; }
  66     static inline bool classof(const SCEV *S) {
  67       return S->getSCEVType() == scConstant;
  68     }
  69   };
  70
  71   //===--------------------------------------------------------------------===//
  72   /// SCEVTruncateExpr - This class represents a truncation of an integer value
  73   /// to a smaller integer value.
  74   ///
  75   class SCEVTruncateExpr : public SCEV {
  76     friend class ScalarEvolution;
  77
  78     SCEVHandle Op;
  79     const Type *Ty;
  80     SCEVTruncateExpr(const SCEVHandle &op, const Type *ty);
  81     virtual ~SCEVTruncateExpr();
  82   public:
  83     const SCEVHandle &getOperand() const { return Op; }
  84     virtual const Type *getType() const { return Ty; }
  85
  86     virtual bool isLoopInvariant(const Loop *L) const {
  87       return Op->isLoopInvariant(L);
  88     }
  89
  90     virtual bool hasComputableLoopEvolution(const Loop *L) const {
  91       return Op->hasComputableLoopEvolution(L);
  92     }
  93
  94     SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
  95                                                  const SCEVHandle &Conc,
  96                                                  ScalarEvolution &SE) const {
  97       SCEVHandle H = Op->replaceSymbolicValuesWithConcrete(Sym, Conc, SE);
  98       if (H == Op)
  99         return this;
 100       return SE.getTruncateExpr(H, Ty);
 101     }
 102
 103     virtual void print(std::ostream &OS) const;
 104     void print(std::ostream *OS) const { if (OS) print(*OS); }
 105
 106     /// Methods for support type inquiry through isa, cast, and dyn_cast:
 107     static inline bool classof(const SCEVTruncateExpr *S) { return true; }
 108     static inline bool classof(const SCEV *S) {
 109       return S->getSCEVType() == scTruncate;
 110     }
 111   };
 112
 113   //===--------------------------------------------------------------------===//
 114   /// SCEVZeroExtendExpr - This class represents a zero extension of a small
 115   /// integer value to a larger integer value.
 116   ///
 117   class SCEVZeroExtendExpr : public SCEV {
 118     friend class ScalarEvolution;
 119
 120     SCEVHandle Op;
 121     const Type *Ty;
 122     SCEVZeroExtendExpr(const SCEVHandle &op, const Type *ty);
 123     virtual ~SCEVZeroExtendExpr();
 124   public:
 125     const SCEVHandle &getOperand() const { return Op; }
 126     virtual const Type *getType() const { return Ty; }
 127
 128     virtual bool isLoopInvariant(const Loop *L) const {
 129       return Op->isLoopInvariant(L);
 130     }
 131
 132     virtual bool hasComputableLoopEvolution(const Loop *L) const {
 133       return Op->hasComputableLoopEvolution(L);
 134     }
 135
 136     SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
 137                                                  const SCEVHandle &Conc,
 138                                                  ScalarEvolution &SE) const {
 139       SCEVHandle H = Op->replaceSymbolicValuesWithConcrete(Sym, Conc, SE);
 140       if (H == Op)
 141         return this;
 142       return SE.getZeroExtendExpr(H, Ty);
 143     }
 144
 145     virtual void print(std::ostream &OS) const;
 146     void print(std::ostream *OS) const { if (OS) print(*OS); }
 147
 148     /// Methods for support type inquiry through isa, cast, and dyn_cast:
 149     static inline bool classof(const SCEVZeroExtendExpr *S) { return true; }
 150     static inline bool classof(const SCEV *S) {
 151       return S->getSCEVType() == scZeroExtend;
 152     }
 153   };
 154
 155   //===--------------------------------------------------------------------===//
 156   /// SCEVSignExtendExpr - This class represents a sign extension of a small
 157   /// integer value to a larger integer value.
 158   ///
 159   class SCEVSignExtendExpr : public SCEV {
 160     friend class ScalarEvolution;
 161
 162     SCEVHandle Op;
 163     const Type *Ty;
 164     SCEVSignExtendExpr(const SCEVHandle &op, const Type *ty);
 165     virtual ~SCEVSignExtendExpr();
 166   public:
 167     const SCEVHandle &getOperand() const { return Op; }
 168     virtual const Type *getType() const { return Ty; }
 169
 170     virtual bool isLoopInvariant(const Loop *L) const {
 171       return Op->isLoopInvariant(L);
 172     }
 173
 174     virtual bool hasComputableLoopEvolution(const Loop *L) const {
 175       return Op->hasComputableLoopEvolution(L);
 176     }
 177
 178     SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
 179                                                  const SCEVHandle &Conc,
 180                                                  ScalarEvolution &SE) const {
 181       SCEVHandle H = Op->replaceSymbolicValuesWithConcrete(Sym, Conc, SE);
 182       if (H == Op)
 183         return this;
 184       return SE.getSignExtendExpr(H, Ty);
 185     }
 186
 187     virtual void print(std::ostream &OS) const;
 188     void print(std::ostream *OS) const { if (OS) print(*OS); }
 189
 190     /// Methods for support type inquiry through isa, cast, and dyn_cast:
 191     static inline bool classof(const SCEVSignExtendExpr *S) { return true; }
 192     static inline bool classof(const SCEV *S) {
 193       return S->getSCEVType() == scSignExtend;
 194     }
 195   };
 196
 197
 198   //===--------------------------------------------------------------------===//
 199   /// SCEVCommutativeExpr - This node is the base class for n'ary commutative
 200   /// operators.
 201   ///
 202   class SCEVCommutativeExpr : public SCEV {
 203     friend class ScalarEvolution;
 204
 205     std::vector<SCEVHandle> Operands;
 206
 207   protected:
 208     SCEVCommutativeExpr(enum SCEVTypes T, const std::vector<SCEVHandle> &ops)
 209       : SCEV(T) {
 210       Operands.reserve(ops.size());
 211       Operands.insert(Operands.end(), ops.begin(), ops.end());
 212     }
 213     ~SCEVCommutativeExpr();
 214
 215   public:
 216     unsigned getNumOperands() const { return (unsigned)Operands.size(); }
 217     const SCEVHandle &getOperand(unsigned i) const {
 218       assert(i < Operands.size() && "Operand index out of range!");
 219       return Operands[i];
 220     }
 221
 222     const std::vector<SCEVHandle> &getOperands() const { return Operands; }
 223     typedef std::vector<SCEVHandle>::const_iterator op_iterator;
 224     op_iterator op_begin() const { return Operands.begin(); }
 225     op_iterator op_end() const { return Operands.end(); }
 226
 227
 228     virtual bool isLoopInvariant(const Loop *L) const {
 229       for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
 230         if (!getOperand(i)->isLoopInvariant(L)) return false;
 231       return true;
 232     }
 233
 234     // hasComputableLoopEvolution - Commutative expressions have computable loop
 235     // evolutions iff they have at least one operand that varies with the loop,
 236     // but that all varying operands are computable.
 237     virtual bool hasComputableLoopEvolution(const Loop *L) const {
 238       bool HasVarying = false;
 239       for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
 240         if (!getOperand(i)->isLoopInvariant(L)) {
 241           if (getOperand(i)->hasComputableLoopEvolution(L))
 242             HasVarying = true;
 243           else
 244             return false;
 245         }
 246       return HasVarying;
 247     }
 248
 249     SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
 250                                                  const SCEVHandle &Conc,
 251                                                  ScalarEvolution &SE) const;
 252
 253     virtual const char *getOperationStr() const = 0;
 254
 255     virtual const Type *getType() const { return getOperand(0)->getType(); }
 256     virtual void print(std::ostream &OS) const;
 257     void print(std::ostream *OS) const { if (OS) print(*OS); }
 258
 259     /// Methods for support type inquiry through isa, cast, and dyn_cast:
 260     static inline bool classof(const SCEVCommutativeExpr *S) { return true; }
 261     static inline bool classof(const SCEV *S) {
 262       return S->getSCEVType() == scAddExpr ||
 263              S->getSCEVType() == scMulExpr ||
 264              S->getSCEVType() == scSMaxExpr ||
 265              S->getSCEVType() == scUMaxExpr;
 266     }
 267   };
 268
 269
 270   //===--------------------------------------------------------------------===//
 271   /// SCEVAddExpr - This node represents an addition of some number of SCEVs.
 272   ///
 273   class SCEVAddExpr : public SCEVCommutativeExpr {
 274     friend class ScalarEvolution;
 275
 276     explicit SCEVAddExpr(const std::vector<SCEVHandle> &ops)
 277       : SCEVCommutativeExpr(scAddExpr, ops) {
 278     }
 279
 280   public:
 281     virtual const char *getOperationStr() const { return " + "; }
 282
 283     /// Methods for support type inquiry through isa, cast, and dyn_cast:
 284     static inline bool classof(const SCEVAddExpr *S) { return true; }
 285     static inline bool classof(const SCEV *S) {
 286       return S->getSCEVType() == scAddExpr;
 287     }
 288   };
 289
 290   //===--------------------------------------------------------------------===//
 291   /// SCEVMulExpr - This node represents multiplication of some number of SCEVs.
 292   ///
 293   class SCEVMulExpr : public SCEVCommutativeExpr {
 294     friend class ScalarEvolution;
 295
 296     explicit SCEVMulExpr(const std::vector<SCEVHandle> &ops)
 297       : SCEVCommutativeExpr(scMulExpr, ops) {
 298     }
 299
 300   public:
 301     virtual const char *getOperationStr() const { return " * "; }
 302
 303     /// Methods for support type inquiry through isa, cast, and dyn_cast:
 304     static inline bool classof(const SCEVMulExpr *S) { return true; }
 305     static inline bool classof(const SCEV *S) {
 306       return S->getSCEVType() == scMulExpr;
 307     }
 308   };
 309
 310
 311   //===--------------------------------------------------------------------===//
 312   /// SCEVUDivExpr - This class represents a binary unsigned division operation.
 313   ///
 314   class SCEVUDivExpr : public SCEV {
 315     friend class ScalarEvolution;
 316
 317     SCEVHandle LHS, RHS;
 318     SCEVUDivExpr(const SCEVHandle &lhs, const SCEVHandle &rhs)
 319       : SCEV(scUDivExpr), LHS(lhs), RHS(rhs) {}
 320
 321     virtual ~SCEVUDivExpr();
 322   public:
 323     const SCEVHandle &getLHS() const { return LHS; }
 324     const SCEVHandle &getRHS() const { return RHS; }
 325
 326     virtual bool isLoopInvariant(const Loop *L) const {
 327       return LHS->isLoopInvariant(L) && RHS->isLoopInvariant(L);
 328     }
 329
 330     virtual bool hasComputableLoopEvolution(const Loop *L) const {
 331       return LHS->hasComputableLoopEvolution(L) &&
 332              RHS->hasComputableLoopEvolution(L);
 333     }
 334
 335     SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
 336                                                  const SCEVHandle &Conc,
 337                                                  ScalarEvolution &SE) const {
 338       SCEVHandle L = LHS->replaceSymbolicValuesWithConcrete(Sym, Conc, SE);
 339       SCEVHandle R = RHS->replaceSymbolicValuesWithConcrete(Sym, Conc, SE);
 340       if (L == LHS && R == RHS)
 341         return this;
 342       else
 343         return SE.getUDivExpr(L, R);
 344     }
 345
 346
 347     virtual const Type *getType() const;
 348
 349     void print(std::ostream &OS) const;
 350     void print(std::ostream *OS) const { if (OS) print(*OS); }
 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.
 363   ///
 364   /// All operands of an AddRec are required to be loop invariant.
 365   ///
 366   class SCEVAddRecExpr : public SCEV {
 367     friend class ScalarEvolution;
 368
 369     std::vector<SCEVHandle> Operands;
 370     const Loop *L;
 371
 372     SCEVAddRecExpr(const std::vector<SCEVHandle> &ops, const Loop *l)
 373       : SCEV(scAddRecExpr), Operands(ops), L(l) {
 374       for (size_t i = 0, e = Operands.size(); i != e; ++i)
 375         assert(Operands[i]->isLoopInvariant(l) &&
 376                "Operands of AddRec must be loop-invariant!");
 377     }
 378     ~SCEVAddRecExpr();
 379   public:
 380     typedef std::vector<SCEVHandle>::const_iterator op_iterator;
 381     op_iterator op_begin() const { return Operands.begin(); }
 382     op_iterator op_end() const { return Operands.end(); }
 383
 384     unsigned getNumOperands() const { return (unsigned)Operands.size(); }
 385     const SCEVHandle &getOperand(unsigned i) const { return Operands[i]; }
 386     const SCEVHandle &getStart() const { return Operands[0]; }
 387     const Loop *getLoop() const { return L; }
 388
 389
 390     /// getStepRecurrence - This method constructs and returns the recurrence
 391     /// indicating how much this expression steps by.  If this is a polynomial
 392     /// of degree N, it returns a chrec of degree N-1.
 393     SCEVHandle getStepRecurrence(ScalarEvolution &SE) const {
 394       if (isAffine()) return getOperand(1);
 395       return SE.getAddRecExpr(std::vector<SCEVHandle>(op_begin()+1,op_end()),
 396                               getLoop());
 397     }
 398
 399     virtual bool hasComputableLoopEvolution(const Loop *QL) const {
 400       if (L == QL) return true;
 401       return false;
 402     }
 403
 404     virtual bool isLoopInvariant(const Loop *QueryLoop) const;
 405
 406     virtual const Type *getType() const { return Operands[0]->getType(); }
 407
 408     /// isAffine - Return true if this is an affine AddRec (i.e., it represents
 409     /// an expressions A+B*x where A and B are loop invariant values.
 410     bool isAffine() const {
 411       // We know that the start value is invariant.  This expression is thus
 412       // affine iff the step is also invariant.
 413       return getNumOperands() == 2;
 414     }
 415
 416     /// isQuadratic - Return true if this is an quadratic AddRec (i.e., it
 417     /// represents an expressions A+B*x+C*x^2 where A, B and C are loop
 418     /// invariant values.  This corresponds to an addrec of the form {L,+,M,+,N}
 419     bool isQuadratic() const {
 420       return getNumOperands() == 3;
 421     }
 422
 423     /// evaluateAtIteration - Return the value of this chain of recurrences at
 424     /// the specified iteration number.
 425     SCEVHandle evaluateAtIteration(SCEVHandle It, ScalarEvolution &SE) const;
 426
 427     /// getNumIterationsInRange - Return the number of iterations of this loop
 428     /// that produce values in the specified constant range.  Another way of
 429     /// looking at this is that it returns the first iteration number where the
 430     /// value is not in the condition, thus computing the exit count.  If the
 431     /// iteration count can't be computed, an instance of SCEVCouldNotCompute is
 432     /// returned.
 433     SCEVHandle getNumIterationsInRange(ConstantRange Range,
 434                                        ScalarEvolution &SE) const;
 435
 436     SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
 437                                                  const SCEVHandle &Conc,
 438                                                  ScalarEvolution &SE) const;
 439
 440     virtual void print(std::ostream &OS) const;
 441     void print(std::ostream *OS) const { if (OS) print(*OS); }
 442
 443     /// Methods for support type inquiry through isa, cast, and dyn_cast:
 444     static inline bool classof(const SCEVAddRecExpr *S) { return true; }
 445     static inline bool classof(const SCEV *S) {
 446       return S->getSCEVType() == scAddRecExpr;
 447     }
 448   };
 449
 450
 451   //===--------------------------------------------------------------------===//
 452   /// SCEVSMaxExpr - This class represents a signed maximum selection.
 453   ///
 454   class SCEVSMaxExpr : public SCEVCommutativeExpr {
 455     friend class ScalarEvolution;
 456
 457     explicit SCEVSMaxExpr(const std::vector<SCEVHandle> &ops)
 458       : SCEVCommutativeExpr(scSMaxExpr, ops) {
 459     }
 460
 461   public:
 462     virtual const char *getOperationStr() const { return " smax "; }
 463
 464     /// Methods for support type inquiry through isa, cast, and dyn_cast:
 465     static inline bool classof(const SCEVSMaxExpr *S) { return true; }
 466     static inline bool classof(const SCEV *S) {
 467       return S->getSCEVType() == scSMaxExpr;
 468     }
 469   };
 470
 471
 472   //===--------------------------------------------------------------------===//
 473   /// SCEVUMaxExpr - This class represents an unsigned maximum selection.
 474   ///
 475   class SCEVUMaxExpr : public SCEVCommutativeExpr {
 476     friend class ScalarEvolution;
 477
 478     explicit SCEVUMaxExpr(const std::vector<SCEVHandle> &ops)
 479       : SCEVCommutativeExpr(scUMaxExpr, ops) {
 480     }
 481
 482   public:
 483     virtual const char *getOperationStr() const { return " umax "; }
 484
 485     /// Methods for support type inquiry through isa, cast, and dyn_cast:
 486     static inline bool classof(const SCEVUMaxExpr *S) { return true; }
 487     static inline bool classof(const SCEV *S) {
 488       return S->getSCEVType() == scUMaxExpr;
 489     }
 490   };
 491
 492
 493   //===--------------------------------------------------------------------===//
 494   /// SCEVUnknown - This means that we are dealing with an entirely unknown SCEV
 495   /// value, and only represent it as it's LLVM Value.  This is the "bottom"
 496   /// value for the analysis.
 497   ///
 498   class SCEVUnknown : public SCEV {
 499     friend class ScalarEvolution;
 500
 501     Value *V;
 502     explicit SCEVUnknown(Value *v) : SCEV(scUnknown), V(v) {}
 503
 504   protected:
 505     ~SCEVUnknown();
 506   public:
 507     Value *getValue() const { return V; }
 508
 509     virtual bool isLoopInvariant(const Loop *L) const;
 510     virtual bool hasComputableLoopEvolution(const Loop *QL) const {
 511       return false; // not computable
 512     }
 513
 514     SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
 515                                                  const SCEVHandle &Conc,
 516                                                  ScalarEvolution &SE) const {
 517       if (&*Sym == this) return Conc;
 518       return this;
 519     }
 520
 521     virtual const Type *getType() const;
 522
 523     virtual void print(std::ostream &OS) const;
 524     void print(std::ostream *OS) const { if (OS) print(*OS); }
 525
 526     /// Methods for support type inquiry through isa, cast, and dyn_cast:
 527     static inline bool classof(const SCEVUnknown *S) { return true; }
 528     static inline bool classof(const SCEV *S) {
 529       return S->getSCEVType() == scUnknown;
 530     }
 531   };
 532
 533   /// SCEVVisitor - This class defines a simple visitor class that may be used
 534   /// for various SCEV analysis purposes.
 535   template<typename SC, typename RetVal=void>
 536   struct SCEVVisitor {
 537     RetVal visit(SCEV *S) {
 538       switch (S->getSCEVType()) {
 539       case scConstant:
 540         return ((SC*)this)->visitConstant((SCEVConstant*)S);
 541       case scTruncate:
 542         return ((SC*)this)->visitTruncateExpr((SCEVTruncateExpr*)S);
 543       case scZeroExtend:
 544         return ((SC*)this)->visitZeroExtendExpr((SCEVZeroExtendExpr*)S);
 545       case scSignExtend:
 546         return ((SC*)this)->visitSignExtendExpr((SCEVSignExtendExpr*)S);
 547       case scAddExpr:
 548         return ((SC*)this)->visitAddExpr((SCEVAddExpr*)S);
 549       case scMulExpr:
 550         return ((SC*)this)->visitMulExpr((SCEVMulExpr*)S);
 551       case scUDivExpr:
 552         return ((SC*)this)->visitUDivExpr((SCEVUDivExpr*)S);
 553       case scAddRecExpr:
 554         return ((SC*)this)->visitAddRecExpr((SCEVAddRecExpr*)S);
 555       case scSMaxExpr:
 556         return ((SC*)this)->visitSMaxExpr((SCEVSMaxExpr*)S);
 557       case scUMaxExpr:
 558         return ((SC*)this)->visitUMaxExpr((SCEVUMaxExpr*)S);
 559       case scUnknown:
 560         return ((SC*)this)->visitUnknown((SCEVUnknown*)S);
 561       case scCouldNotCompute:
 562         return ((SC*)this)->visitCouldNotCompute((SCEVCouldNotCompute*)S);
 563       default:
 564         assert(0 && "Unknown SCEV type!");
 565         abort();
 566       }
 567     }
 568
 569     RetVal visitCouldNotCompute(SCEVCouldNotCompute *S) {
 570       assert(0 && "Invalid use of SCEVCouldNotCompute!");
 571       abort();
 572       return RetVal();
 573     }
 574   };
 575 }
 576
 577 #endif