ScalarEvolutionExpressions.h revision 890f92b744fb074465bc2b7006ee753a181f62a4
14950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner//===- llvm/Analysis/ScalarEvolutionExpressions.h - SCEV Exprs --*- C++ -*-===// 29769ab22265b313171d201b5928688524a01bd87Misha Brukman// 34950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner// The LLVM Compiler Infrastructure 44950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner// 57ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// This file is distributed under the University of Illinois Open Source 67ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// License. See LICENSE.TXT for details. 79769ab22265b313171d201b5928688524a01bd87Misha Brukman// 84950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner//===----------------------------------------------------------------------===// 94950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner// 104950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner// This file defines the classes used to represent and build scalar expressions. 119769ab22265b313171d201b5928688524a01bd87Misha Brukman// 124950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner//===----------------------------------------------------------------------===// 134950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 144950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner#ifndef LLVM_ANALYSIS_SCALAREVOLUTION_EXPRESSIONS_H 154950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner#define LLVM_ANALYSIS_SCALAREVOLUTION_EXPRESSIONS_H 164950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 174950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner#include "llvm/Analysis/ScalarEvolution.h" 184950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 194950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattnernamespace llvm { 204950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner class ConstantInt; 214950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner class ConstantRange; 2235fa43907e2ea751ad35bfbaab8c4d3511422c14Reid Spencer class APInt; 235a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng class DominatorTree; 244950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 254950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner enum SCEVTypes { 264950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner // These should be ordered in terms of increasing complexity to make the 274950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner // folders simpler. 28d19534add90a2a894af61523b830887097bb780bDan Gohman scConstant, scTruncate, scZeroExtend, scSignExtend, scAddExpr, scMulExpr, 29789558db70d9513a017c11c5be30945839fdff1cNick Lewycky scUDivExpr, scAddRecExpr, scUMaxExpr, scSMaxExpr, scUnknown, 303e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky scCouldNotCompute 314950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 324950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 334950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner //===--------------------------------------------------------------------===// 344950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// SCEVConstant - This class represents a constant integer value. 354950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 364950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner class SCEVConstant : public SCEV { 37246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman friend class ScalarEvolution; 38246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman 394950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner ConstantInt *V; 409a6ae965d69b131d692de8fc69545b6c7aaea0b2Dan Gohman explicit SCEVConstant(ConstantInt *v) : SCEV(scConstant), V(v) {} 419769ab22265b313171d201b5928688524a01bd87Misha Brukman 424950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual ~SCEVConstant(); 434950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner public: 444950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner ConstantInt *getValue() const { return V; } 454950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 464950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool isLoopInvariant(const Loop *L) const { 474950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return true; 484950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 494950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 504950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool hasComputableLoopEvolution(const Loop *L) const { 514950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return false; // Not loop variant 524950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 534950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 544950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual const Type *getType() const; 554950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 56afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, 57246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman const SCEVHandle &Conc, 58246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman ScalarEvolution &SE) const { 59afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner return this; 60afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner } 61afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner 625a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng bool dominates(BasicBlock *BB, DominatorTree *DT) const { 635a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng return true; 645a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng } 655a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng 664950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual void print(std::ostream &OS) const; 675c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling void print(std::ostream *OS) const { if (OS) print(*OS); } 684950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 694950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 704950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEVConstant *S) { return true; } 714950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEV *S) { 724950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return S->getSCEVType() == scConstant; 734950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 744950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 754950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 764950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner //===--------------------------------------------------------------------===// 774950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// SCEVTruncateExpr - This class represents a truncation of an integer value 784950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// to a smaller integer value. 794950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 804950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner class SCEVTruncateExpr : public SCEV { 81246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman friend class ScalarEvolution; 82246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman 834950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner SCEVHandle Op; 844950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const Type *Ty; 854950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner SCEVTruncateExpr(const SCEVHandle &op, const Type *ty); 864950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual ~SCEVTruncateExpr(); 874950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner public: 884950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const SCEVHandle &getOperand() const { return Op; } 894950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual const Type *getType() const { return Ty; } 909769ab22265b313171d201b5928688524a01bd87Misha Brukman 914950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool isLoopInvariant(const Loop *L) const { 924950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return Op->isLoopInvariant(L); 934950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 944950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 954950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool hasComputableLoopEvolution(const Loop *L) const { 964950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return Op->hasComputableLoopEvolution(L); 974950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 984950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 99afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, 100246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman const SCEVHandle &Conc, 101246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman ScalarEvolution &SE) const { 102246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle H = Op->replaceSymbolicValuesWithConcrete(Sym, Conc, SE); 103afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner if (H == Op) 104afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner return this; 105246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman return SE.getTruncateExpr(H, Ty); 106afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner } 107afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner 1085a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng virtual bool dominates(BasicBlock *BB, DominatorTree *DT) const; 1095a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng 1104950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual void print(std::ostream &OS) const; 1115c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling void print(std::ostream *OS) const { if (OS) print(*OS); } 1124950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 1134950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 1144950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEVTruncateExpr *S) { return true; } 1154950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEV *S) { 1164950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return S->getSCEVType() == scTruncate; 1174950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 1184950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 1194950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 1204950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner //===--------------------------------------------------------------------===// 1214950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// SCEVZeroExtendExpr - This class represents a zero extension of a small 1224950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// integer value to a larger integer value. 1234950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 1244950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner class SCEVZeroExtendExpr : public SCEV { 125246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman friend class ScalarEvolution; 126246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman 1274950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner SCEVHandle Op; 1284950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const Type *Ty; 1294950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner SCEVZeroExtendExpr(const SCEVHandle &op, const Type *ty); 1304950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual ~SCEVZeroExtendExpr(); 1314950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner public: 1324950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const SCEVHandle &getOperand() const { return Op; } 1334950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual const Type *getType() const { return Ty; } 1349769ab22265b313171d201b5928688524a01bd87Misha Brukman 1354950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool isLoopInvariant(const Loop *L) const { 1364950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return Op->isLoopInvariant(L); 1374950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 1384950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 1394950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool hasComputableLoopEvolution(const Loop *L) const { 1404950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return Op->hasComputableLoopEvolution(L); 1414950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 1424950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 143afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, 144246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman const SCEVHandle &Conc, 145246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman ScalarEvolution &SE) const { 146246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle H = Op->replaceSymbolicValuesWithConcrete(Sym, Conc, SE); 147afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner if (H == Op) 148afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner return this; 149246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman return SE.getZeroExtendExpr(H, Ty); 150afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner } 151afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner 1525a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng bool dominates(BasicBlock *BB, DominatorTree *DT) const; 1535a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng 1544950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual void print(std::ostream &OS) const; 1555c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling void print(std::ostream *OS) const { if (OS) print(*OS); } 1564950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 1574950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 1584950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEVZeroExtendExpr *S) { return true; } 1594950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEV *S) { 1604950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return S->getSCEVType() == scZeroExtend; 1614950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 1624950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 1634950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 164d19534add90a2a894af61523b830887097bb780bDan Gohman //===--------------------------------------------------------------------===// 165d19534add90a2a894af61523b830887097bb780bDan Gohman /// SCEVSignExtendExpr - This class represents a sign extension of a small 166d19534add90a2a894af61523b830887097bb780bDan Gohman /// integer value to a larger integer value. 167d19534add90a2a894af61523b830887097bb780bDan Gohman /// 168d19534add90a2a894af61523b830887097bb780bDan Gohman class SCEVSignExtendExpr : public SCEV { 169246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman friend class ScalarEvolution; 170246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman 171d19534add90a2a894af61523b830887097bb780bDan Gohman SCEVHandle Op; 172d19534add90a2a894af61523b830887097bb780bDan Gohman const Type *Ty; 173d19534add90a2a894af61523b830887097bb780bDan Gohman SCEVSignExtendExpr(const SCEVHandle &op, const Type *ty); 174d19534add90a2a894af61523b830887097bb780bDan Gohman virtual ~SCEVSignExtendExpr(); 175d19534add90a2a894af61523b830887097bb780bDan Gohman public: 176d19534add90a2a894af61523b830887097bb780bDan Gohman const SCEVHandle &getOperand() const { return Op; } 177d19534add90a2a894af61523b830887097bb780bDan Gohman virtual const Type *getType() const { return Ty; } 178d19534add90a2a894af61523b830887097bb780bDan Gohman 179d19534add90a2a894af61523b830887097bb780bDan Gohman virtual bool isLoopInvariant(const Loop *L) const { 180d19534add90a2a894af61523b830887097bb780bDan Gohman return Op->isLoopInvariant(L); 181d19534add90a2a894af61523b830887097bb780bDan Gohman } 182d19534add90a2a894af61523b830887097bb780bDan Gohman 183d19534add90a2a894af61523b830887097bb780bDan Gohman virtual bool hasComputableLoopEvolution(const Loop *L) const { 184d19534add90a2a894af61523b830887097bb780bDan Gohman return Op->hasComputableLoopEvolution(L); 185d19534add90a2a894af61523b830887097bb780bDan Gohman } 186d19534add90a2a894af61523b830887097bb780bDan Gohman 187d19534add90a2a894af61523b830887097bb780bDan Gohman SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, 188246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman const SCEVHandle &Conc, 189246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman ScalarEvolution &SE) const { 190246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle H = Op->replaceSymbolicValuesWithConcrete(Sym, Conc, SE); 191d19534add90a2a894af61523b830887097bb780bDan Gohman if (H == Op) 192d19534add90a2a894af61523b830887097bb780bDan Gohman return this; 193246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman return SE.getSignExtendExpr(H, Ty); 194d19534add90a2a894af61523b830887097bb780bDan Gohman } 195d19534add90a2a894af61523b830887097bb780bDan Gohman 1965a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng bool dominates(BasicBlock *BB, DominatorTree *DT) const; 1975a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng 198d19534add90a2a894af61523b830887097bb780bDan Gohman virtual void print(std::ostream &OS) const; 199d19534add90a2a894af61523b830887097bb780bDan Gohman void print(std::ostream *OS) const { if (OS) print(*OS); } 200d19534add90a2a894af61523b830887097bb780bDan Gohman 201d19534add90a2a894af61523b830887097bb780bDan Gohman /// Methods for support type inquiry through isa, cast, and dyn_cast: 202d19534add90a2a894af61523b830887097bb780bDan Gohman static inline bool classof(const SCEVSignExtendExpr *S) { return true; } 203d19534add90a2a894af61523b830887097bb780bDan Gohman static inline bool classof(const SCEV *S) { 204d19534add90a2a894af61523b830887097bb780bDan Gohman return S->getSCEVType() == scSignExtend; 205d19534add90a2a894af61523b830887097bb780bDan Gohman } 206d19534add90a2a894af61523b830887097bb780bDan Gohman }; 207d19534add90a2a894af61523b830887097bb780bDan Gohman 2084950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2094950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner //===--------------------------------------------------------------------===// 2104950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// SCEVCommutativeExpr - This node is the base class for n'ary commutative 2114950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// operators. 2124950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 2134950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner class SCEVCommutativeExpr : public SCEV { 214246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman friend class ScalarEvolution; 215246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman 2164950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner std::vector<SCEVHandle> Operands; 2174950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2184950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner protected: 2194950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner SCEVCommutativeExpr(enum SCEVTypes T, const std::vector<SCEVHandle> &ops) 2204950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner : SCEV(T) { 2214950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner Operands.reserve(ops.size()); 2224950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner Operands.insert(Operands.end(), ops.begin(), ops.end()); 2234950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 2244950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner ~SCEVCommutativeExpr(); 2254950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2264950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner public: 22734cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng unsigned getNumOperands() const { return (unsigned)Operands.size(); } 2284950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const SCEVHandle &getOperand(unsigned i) const { 2294950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner assert(i < Operands.size() && "Operand index out of range!"); 2304950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return Operands[i]; 2314950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 2324950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2334950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const std::vector<SCEVHandle> &getOperands() const { return Operands; } 2344950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner typedef std::vector<SCEVHandle>::const_iterator op_iterator; 2354950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner op_iterator op_begin() const { return Operands.begin(); } 2364950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner op_iterator op_end() const { return Operands.end(); } 2374950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2384950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2394950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool isLoopInvariant(const Loop *L) const { 2404950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner for (unsigned i = 0, e = getNumOperands(); i != e; ++i) 2414950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner if (!getOperand(i)->isLoopInvariant(L)) return false; 2424950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return true; 2434950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 2444950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 245803513b364e27d303285d396fd8ee5b32149962aChris Lattner // hasComputableLoopEvolution - Commutative expressions have computable loop 246803513b364e27d303285d396fd8ee5b32149962aChris Lattner // evolutions iff they have at least one operand that varies with the loop, 247803513b364e27d303285d396fd8ee5b32149962aChris Lattner // but that all varying operands are computable. 2484950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool hasComputableLoopEvolution(const Loop *L) const { 249803513b364e27d303285d396fd8ee5b32149962aChris Lattner bool HasVarying = false; 2504950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner for (unsigned i = 0, e = getNumOperands(); i != e; ++i) 251ae9f3a3b7c915f725aef5a7250e88eaeddda03c6Anton Korobeynikov if (!getOperand(i)->isLoopInvariant(L)) { 252803513b364e27d303285d396fd8ee5b32149962aChris Lattner if (getOperand(i)->hasComputableLoopEvolution(L)) 253803513b364e27d303285d396fd8ee5b32149962aChris Lattner HasVarying = true; 254803513b364e27d303285d396fd8ee5b32149962aChris Lattner else 255803513b364e27d303285d396fd8ee5b32149962aChris Lattner return false; 256ae9f3a3b7c915f725aef5a7250e88eaeddda03c6Anton Korobeynikov } 257803513b364e27d303285d396fd8ee5b32149962aChris Lattner return HasVarying; 2584950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 2594950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 260afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, 261246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman const SCEVHandle &Conc, 262246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman ScalarEvolution &SE) const; 263afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner 2645a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng bool dominates(BasicBlock *BB, DominatorTree *DT) const; 2655a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng 2664950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual const char *getOperationStr() const = 0; 2674950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2684950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual const Type *getType() const { return getOperand(0)->getType(); } 2694950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual void print(std::ostream &OS) const; 2705c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling void print(std::ostream *OS) const { if (OS) print(*OS); } 2714950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2724950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 2734950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEVCommutativeExpr *S) { return true; } 2744950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEV *S) { 2754950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return S->getSCEVType() == scAddExpr || 276c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky S->getSCEVType() == scMulExpr || 2773e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky S->getSCEVType() == scSMaxExpr || 2783e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky S->getSCEVType() == scUMaxExpr; 2794950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 2804950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 2814950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2824950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2834950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner //===--------------------------------------------------------------------===// 2844950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// SCEVAddExpr - This node represents an addition of some number of SCEVs. 2854950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 2864950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner class SCEVAddExpr : public SCEVCommutativeExpr { 287246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman friend class ScalarEvolution; 288246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman 289adf3eab7735741926c67e6fc12b952500c45a9baDan Gohman explicit SCEVAddExpr(const std::vector<SCEVHandle> &ops) 2904950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner : SCEVCommutativeExpr(scAddExpr, ops) { 2914950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 2924950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2934950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner public: 2944950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual const char *getOperationStr() const { return " + "; } 2954950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2964950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 2974950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEVAddExpr *S) { return true; } 2984950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEV *S) { 2994950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return S->getSCEVType() == scAddExpr; 3004950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 3014950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 3024950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3034950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner //===--------------------------------------------------------------------===// 3044950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// SCEVMulExpr - This node represents multiplication of some number of SCEVs. 3054950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 3064950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner class SCEVMulExpr : public SCEVCommutativeExpr { 307246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman friend class ScalarEvolution; 308246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman 309adf3eab7735741926c67e6fc12b952500c45a9baDan Gohman explicit SCEVMulExpr(const std::vector<SCEVHandle> &ops) 3104950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner : SCEVCommutativeExpr(scMulExpr, ops) { 3114950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 3124950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3134950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner public: 3144950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual const char *getOperationStr() const { return " * "; } 3154950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3164950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 3174950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEVMulExpr *S) { return true; } 3184950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEV *S) { 3194950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return S->getSCEVType() == scMulExpr; 3204950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 3214950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 3224950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3234950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3244950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner //===--------------------------------------------------------------------===// 325e3320a1bcce3f6653e109cc86ee1011b0a61d808Wojciech Matyjewicz /// SCEVUDivExpr - This class represents a binary unsigned division operation. 3264950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 327e3320a1bcce3f6653e109cc86ee1011b0a61d808Wojciech Matyjewicz class SCEVUDivExpr : public SCEV { 328246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman friend class ScalarEvolution; 329246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman 3304950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner SCEVHandle LHS, RHS; 331e3320a1bcce3f6653e109cc86ee1011b0a61d808Wojciech Matyjewicz SCEVUDivExpr(const SCEVHandle &lhs, const SCEVHandle &rhs) 332e3320a1bcce3f6653e109cc86ee1011b0a61d808Wojciech Matyjewicz : SCEV(scUDivExpr), LHS(lhs), RHS(rhs) {} 3334950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 334e3320a1bcce3f6653e109cc86ee1011b0a61d808Wojciech Matyjewicz virtual ~SCEVUDivExpr(); 3354950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner public: 3364950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const SCEVHandle &getLHS() const { return LHS; } 3374950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const SCEVHandle &getRHS() const { return RHS; } 3384950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3394950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool isLoopInvariant(const Loop *L) const { 3404950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return LHS->isLoopInvariant(L) && RHS->isLoopInvariant(L); 3414950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 3424950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3434950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool hasComputableLoopEvolution(const Loop *L) const { 3444950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return LHS->hasComputableLoopEvolution(L) && 3454950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner RHS->hasComputableLoopEvolution(L); 3464950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 3474950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 348afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, 349246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman const SCEVHandle &Conc, 350246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman ScalarEvolution &SE) const { 351246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle L = LHS->replaceSymbolicValuesWithConcrete(Sym, Conc, SE); 352246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle R = RHS->replaceSymbolicValuesWithConcrete(Sym, Conc, SE); 353afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner if (L == LHS && R == RHS) 354afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner return this; 355afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner else 356e3320a1bcce3f6653e109cc86ee1011b0a61d808Wojciech Matyjewicz return SE.getUDivExpr(L, R); 357afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner } 358afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner 3595a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng bool dominates(BasicBlock *BB, DominatorTree *DT) const; 360afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner 3614950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual const Type *getType() const; 3624950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3634950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner void print(std::ostream &OS) const; 3645c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling void print(std::ostream *OS) const { if (OS) print(*OS); } 3654950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3664950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 367e3320a1bcce3f6653e109cc86ee1011b0a61d808Wojciech Matyjewicz static inline bool classof(const SCEVUDivExpr *S) { return true; } 3684950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEV *S) { 369e3320a1bcce3f6653e109cc86ee1011b0a61d808Wojciech Matyjewicz return S->getSCEVType() == scUDivExpr; 3704950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 3714950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 3724950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3734950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3744950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner //===--------------------------------------------------------------------===// 3754950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// SCEVAddRecExpr - This node represents a polynomial recurrence on the trip 3764950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// count of the specified loop. 3774950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 3784950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// All operands of an AddRec are required to be loop invariant. 3794950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 3804950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner class SCEVAddRecExpr : public SCEV { 381246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman friend class ScalarEvolution; 382246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman 3834950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner std::vector<SCEVHandle> Operands; 3844950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const Loop *L; 3854950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3864950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner SCEVAddRecExpr(const std::vector<SCEVHandle> &ops, const Loop *l) 3874950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner : SCEV(scAddRecExpr), Operands(ops), L(l) { 38834cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng for (size_t i = 0, e = Operands.size(); i != e; ++i) 3894950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner assert(Operands[i]->isLoopInvariant(l) && 3904950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner "Operands of AddRec must be loop-invariant!"); 3914950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 3924950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner ~SCEVAddRecExpr(); 3934950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner public: 3944950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner typedef std::vector<SCEVHandle>::const_iterator op_iterator; 3954950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner op_iterator op_begin() const { return Operands.begin(); } 3964950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner op_iterator op_end() const { return Operands.end(); } 3974950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 39834cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng unsigned getNumOperands() const { return (unsigned)Operands.size(); } 3994950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const SCEVHandle &getOperand(unsigned i) const { return Operands[i]; } 4004950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const SCEVHandle &getStart() const { return Operands[0]; } 4014950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const Loop *getLoop() const { return L; } 4024950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4034950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4044950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// getStepRecurrence - This method constructs and returns the recurrence 4054950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// indicating how much this expression steps by. If this is a polynomial 4064950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// of degree N, it returns a chrec of degree N-1. 407246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getStepRecurrence(ScalarEvolution &SE) const { 40817f1972c770dc18f5c7c3c95776b4d62ae9e121dDan Gohman if (isAffine()) return getOperand(1); 409246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman return SE.getAddRecExpr(std::vector<SCEVHandle>(op_begin()+1,op_end()), 410246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman getLoop()); 4114950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 4124950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4134950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool hasComputableLoopEvolution(const Loop *QL) const { 4144950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner if (L == QL) return true; 4154950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return false; 4164950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 4174950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4184950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool isLoopInvariant(const Loop *QueryLoop) const; 4194950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4204950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual const Type *getType() const { return Operands[0]->getType(); } 4214950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4224950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// isAffine - Return true if this is an affine AddRec (i.e., it represents 4234950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// an expressions A+B*x where A and B are loop invariant values. 4244950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner bool isAffine() const { 4254950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner // We know that the start value is invariant. This expression is thus 4264950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner // affine iff the step is also invariant. 4274950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return getNumOperands() == 2; 4284950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 4294950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4304950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// isQuadratic - Return true if this is an quadratic AddRec (i.e., it 4314950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// represents an expressions A+B*x+C*x^2 where A, B and C are loop 4324950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// invariant values. This corresponds to an addrec of the form {L,+,M,+,N} 4334950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner bool isQuadratic() const { 4344950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return getNumOperands() == 3; 4354950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 4364950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4374950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// evaluateAtIteration - Return the value of this chain of recurrences at 4384950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// the specified iteration number. 439246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle evaluateAtIteration(SCEVHandle It, ScalarEvolution &SE) const; 4404950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4414950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// getNumIterationsInRange - Return the number of iterations of this loop 4424950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// that produce values in the specified constant range. Another way of 4434950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// looking at this is that it returns the first iteration number where the 4444950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// value is not in the condition, thus computing the exit count. If the 4454950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// iteration count can't be computed, an instance of SCEVCouldNotCompute is 446eefdebe002ede066bf80859e72aec831cfd1d92dNick Lewycky /// returned. 447246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle getNumIterationsInRange(ConstantRange Range, 448246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman ScalarEvolution &SE) const; 4494950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 450afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, 451246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman const SCEVHandle &Conc, 452246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman ScalarEvolution &SE) const; 4534950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4545a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng bool dominates(BasicBlock *BB, DominatorTree *DT) const; 4555a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng 4564950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual void print(std::ostream &OS) const; 4575c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling void print(std::ostream *OS) const { if (OS) print(*OS); } 4584950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4594950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 4604950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEVAddRecExpr *S) { return true; } 4614950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEV *S) { 4624950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return S->getSCEVType() == scAddRecExpr; 4634950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 4644950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 4654950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 466c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky 467c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky //===--------------------------------------------------------------------===// 468c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky /// SCEVSMaxExpr - This class represents a signed maximum selection. 469c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky /// 470c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky class SCEVSMaxExpr : public SCEVCommutativeExpr { 471c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky friend class ScalarEvolution; 472c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky 473c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky explicit SCEVSMaxExpr(const std::vector<SCEVHandle> &ops) 474c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky : SCEVCommutativeExpr(scSMaxExpr, ops) { 475c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky } 476c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky 477c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky public: 478c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky virtual const char *getOperationStr() const { return " smax "; } 479c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky 480c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky /// Methods for support type inquiry through isa, cast, and dyn_cast: 481c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky static inline bool classof(const SCEVSMaxExpr *S) { return true; } 482c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky static inline bool classof(const SCEV *S) { 483c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky return S->getSCEVType() == scSMaxExpr; 484c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky } 485c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky }; 486c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky 487c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky 4884950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner //===--------------------------------------------------------------------===// 4893e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky /// SCEVUMaxExpr - This class represents an unsigned maximum selection. 4903e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky /// 4913e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky class SCEVUMaxExpr : public SCEVCommutativeExpr { 4923e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky friend class ScalarEvolution; 4933e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky 4943e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky explicit SCEVUMaxExpr(const std::vector<SCEVHandle> &ops) 4953e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky : SCEVCommutativeExpr(scUMaxExpr, ops) { 4963e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky } 4973e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky 4983e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky public: 4993e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky virtual const char *getOperationStr() const { return " umax "; } 5003e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky 5013e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky /// Methods for support type inquiry through isa, cast, and dyn_cast: 5023e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky static inline bool classof(const SCEVUMaxExpr *S) { return true; } 5033e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky static inline bool classof(const SCEV *S) { 5043e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky return S->getSCEVType() == scUMaxExpr; 5053e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky } 5063e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky }; 5073e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky 5083e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky 5093e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky //===--------------------------------------------------------------------===// 5104950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// SCEVUnknown - This means that we are dealing with an entirely unknown SCEV 5114950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// value, and only represent it as it's LLVM Value. This is the "bottom" 5124950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// value for the analysis. 5134950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 5144950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner class SCEVUnknown : public SCEV { 515246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman friend class ScalarEvolution; 516246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman 5174950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner Value *V; 518adf3eab7735741926c67e6fc12b952500c45a9baDan Gohman explicit SCEVUnknown(Value *v) : SCEV(scUnknown), V(v) {} 5194950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 5204950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner protected: 5214950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner ~SCEVUnknown(); 5224950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner public: 5232cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner Value *getValue() const { return V; } 5244950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 5254950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool isLoopInvariant(const Loop *L) const; 5264950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool hasComputableLoopEvolution(const Loop *QL) const { 5274950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return false; // not computable 5284950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 5294950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 530afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, 531246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman const SCEVHandle &Conc, 532246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman ScalarEvolution &SE) const { 533afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner if (&*Sym == this) return Conc; 534afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner return this; 535afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner } 536afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner 5375a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng bool dominates(BasicBlock *BB, DominatorTree *DT) const; 5385a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng 5394950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual const Type *getType() const; 5404950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 5414950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual void print(std::ostream &OS) const; 5425c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling void print(std::ostream *OS) const { if (OS) print(*OS); } 5434950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 5444950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 5454950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEVUnknown *S) { return true; } 5464950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEV *S) { 5474950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return S->getSCEVType() == scUnknown; 5484950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 5494950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 5502cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner 5512cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner /// SCEVVisitor - This class defines a simple visitor class that may be used 5522cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner /// for various SCEV analysis purposes. 5532cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner template<typename SC, typename RetVal=void> 5542cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner struct SCEVVisitor { 555890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman RetVal visit(const SCEV *S) { 5562cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner switch (S->getSCEVType()) { 5572cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner case scConstant: 558890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman return ((SC*)this)->visitConstant((const SCEVConstant*)S); 5592cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner case scTruncate: 560890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman return ((SC*)this)->visitTruncateExpr((const SCEVTruncateExpr*)S); 5612cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner case scZeroExtend: 562890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman return ((SC*)this)->visitZeroExtendExpr((const SCEVZeroExtendExpr*)S); 563d19534add90a2a894af61523b830887097bb780bDan Gohman case scSignExtend: 564890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman return ((SC*)this)->visitSignExtendExpr((const SCEVSignExtendExpr*)S); 5652cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner case scAddExpr: 566890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman return ((SC*)this)->visitAddExpr((const SCEVAddExpr*)S); 5672cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner case scMulExpr: 568890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman return ((SC*)this)->visitMulExpr((const SCEVMulExpr*)S); 569e3320a1bcce3f6653e109cc86ee1011b0a61d808Wojciech Matyjewicz case scUDivExpr: 570890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman return ((SC*)this)->visitUDivExpr((const SCEVUDivExpr*)S); 5712cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner case scAddRecExpr: 572890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman return ((SC*)this)->visitAddRecExpr((const SCEVAddRecExpr*)S); 573c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky case scSMaxExpr: 574890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman return ((SC*)this)->visitSMaxExpr((const SCEVSMaxExpr*)S); 5753e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky case scUMaxExpr: 576890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman return ((SC*)this)->visitUMaxExpr((const SCEVUMaxExpr*)S); 5772cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner case scUnknown: 578890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman return ((SC*)this)->visitUnknown((const SCEVUnknown*)S); 5792cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner case scCouldNotCompute: 580890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman return ((SC*)this)->visitCouldNotCompute((const SCEVCouldNotCompute*)S); 5812cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner default: 5822cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner assert(0 && "Unknown SCEV type!"); 5830ebf428e48ab258012d94d8efa05a4ae5932e2dbChris Lattner abort(); 5842cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner } 5852cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner } 5862cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner 587890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman RetVal visitCouldNotCompute(const SCEVCouldNotCompute *S) { 5882cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner assert(0 && "Invalid use of SCEVCouldNotCompute!"); 5892cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner abort(); 5902cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner return RetVal(); 5912cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner } 5922cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner }; 5934950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner} 5944950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 5954950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner#endif 596