ScalarEvolutionExpressions.h revision d19534add90a2a894af61523b830887097bb780b
14950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner//===- llvm/Analysis/ScalarEvolutionExpressions.h - SCEV Exprs --*- C++ -*-===// 29769ab22265b313171d201b5928688524a01bd87Misha Brukman// 34950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner// The LLVM Compiler Infrastructure 44950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner// 54950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner// This file was developed by the LLVM research group and is distributed under 64950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner// the University of Illinois Open Source 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; 234950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 244950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner enum SCEVTypes { 254950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner // These should be ordered in terms of increasing complexity to make the 264950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner // folders simpler. 27d19534add90a2a894af61523b830887097bb780bDan Gohman scConstant, scTruncate, scZeroExtend, scSignExtend, scAddExpr, scMulExpr, 28d19534add90a2a894af61523b830887097bb780bDan Gohman scSDivExpr, scAddRecExpr, scUnknown, scCouldNotCompute 294950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 304950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 314950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner //===--------------------------------------------------------------------===// 324950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// SCEVConstant - This class represents a constant integer value. 334950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 344950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner class SCEVConstant : public SCEV { 354950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner ConstantInt *V; 364950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner SCEVConstant(ConstantInt *v) : SCEV(scConstant), V(v) {} 379769ab22265b313171d201b5928688524a01bd87Misha Brukman 384950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual ~SCEVConstant(); 394950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner public: 404950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// get method - This just gets and returns a new SCEVConstant object. 414950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 424950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static SCEVHandle get(ConstantInt *V); 434950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 444950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner ConstantInt *getValue() const { return V; } 454950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 464950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// getValueRange - Return the tightest constant bounds that this value is 474950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// known to have. This method is only valid on integer SCEV objects. 484950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual ConstantRange getValueRange() const; 494950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 504950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool isLoopInvariant(const Loop *L) const { 514950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return true; 524950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 534950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 544950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool hasComputableLoopEvolution(const Loop *L) const { 554950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return false; // Not loop variant 564950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 574950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 584950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual const Type *getType() const; 594950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 60afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, 61afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner const SCEVHandle &Conc) const { 62afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner return this; 63afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner } 64afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner 654950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual void print(std::ostream &OS) const; 665c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling void print(std::ostream *OS) const { if (OS) print(*OS); } 674950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 684950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 694950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEVConstant *S) { return true; } 704950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEV *S) { 714950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return S->getSCEVType() == scConstant; 724950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 734950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 744950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 754950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner //===--------------------------------------------------------------------===// 764950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// SCEVTruncateExpr - This class represents a truncation of an integer value 774950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// to a smaller integer value. 784950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 794950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner class SCEVTruncateExpr : public SCEV { 804950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner SCEVHandle Op; 814950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const Type *Ty; 824950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner SCEVTruncateExpr(const SCEVHandle &op, const Type *ty); 834950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual ~SCEVTruncateExpr(); 844950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner public: 854950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// get method - This just gets and returns a new SCEVTruncate object 864950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 874950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static SCEVHandle get(const SCEVHandle &Op, const Type *Ty); 884950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 894950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const SCEVHandle &getOperand() const { return Op; } 904950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual const Type *getType() const { return Ty; } 919769ab22265b313171d201b5928688524a01bd87Misha Brukman 924950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool isLoopInvariant(const Loop *L) const { 934950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return Op->isLoopInvariant(L); 944950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 954950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 964950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool hasComputableLoopEvolution(const Loop *L) const { 974950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return Op->hasComputableLoopEvolution(L); 984950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 994950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 100afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, 101afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner const SCEVHandle &Conc) const { 102afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner SCEVHandle H = Op->replaceSymbolicValuesWithConcrete(Sym, Conc); 103afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner if (H == Op) 104afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner return this; 105afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner return get(H, Ty); 106afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner } 107afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner 1084950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// getValueRange - Return the tightest constant bounds that this value is 1094950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// known to have. This method is only valid on integer SCEV objects. 1104950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual ConstantRange getValueRange() const; 1114950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 1124950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual void print(std::ostream &OS) const; 1135c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling void print(std::ostream *OS) const { if (OS) print(*OS); } 1144950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 1154950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 1164950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEVTruncateExpr *S) { return true; } 1174950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEV *S) { 1184950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return S->getSCEVType() == scTruncate; 1194950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 1204950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 1214950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 1224950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner //===--------------------------------------------------------------------===// 1234950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// SCEVZeroExtendExpr - This class represents a zero extension of a small 1244950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// integer value to a larger integer value. 1254950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 1264950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner class SCEVZeroExtendExpr : public SCEV { 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 /// get method - This just gets and returns a new SCEVZeroExtend object 1334950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 1344950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static SCEVHandle get(const SCEVHandle &Op, const Type *Ty); 1354950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 1364950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const SCEVHandle &getOperand() const { return Op; } 1374950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual const Type *getType() const { return Ty; } 1389769ab22265b313171d201b5928688524a01bd87Misha Brukman 1394950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool isLoopInvariant(const Loop *L) const { 1404950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return Op->isLoopInvariant(L); 1414950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 1424950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 1434950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool hasComputableLoopEvolution(const Loop *L) const { 1444950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return Op->hasComputableLoopEvolution(L); 1454950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 1464950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 1474950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// getValueRange - Return the tightest constant bounds that this value is 1484950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// known to have. This method is only valid on integer SCEV objects. 1494950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual ConstantRange getValueRange() const; 1504950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 151afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, 152afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner const SCEVHandle &Conc) const { 153afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner SCEVHandle H = Op->replaceSymbolicValuesWithConcrete(Sym, Conc); 154afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner if (H == Op) 155afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner return this; 156afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner return get(H, Ty); 157afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner } 158afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner 1594950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual void print(std::ostream &OS) const; 1605c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling void print(std::ostream *OS) const { if (OS) print(*OS); } 1614950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 1624950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 1634950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEVZeroExtendExpr *S) { return true; } 1644950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEV *S) { 1654950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return S->getSCEVType() == scZeroExtend; 1664950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 1674950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 1684950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 169d19534add90a2a894af61523b830887097bb780bDan Gohman //===--------------------------------------------------------------------===// 170d19534add90a2a894af61523b830887097bb780bDan Gohman /// SCEVSignExtendExpr - This class represents a sign extension of a small 171d19534add90a2a894af61523b830887097bb780bDan Gohman /// integer value to a larger integer value. 172d19534add90a2a894af61523b830887097bb780bDan Gohman /// 173d19534add90a2a894af61523b830887097bb780bDan Gohman class SCEVSignExtendExpr : public SCEV { 174d19534add90a2a894af61523b830887097bb780bDan Gohman SCEVHandle Op; 175d19534add90a2a894af61523b830887097bb780bDan Gohman const Type *Ty; 176d19534add90a2a894af61523b830887097bb780bDan Gohman SCEVSignExtendExpr(const SCEVHandle &op, const Type *ty); 177d19534add90a2a894af61523b830887097bb780bDan Gohman virtual ~SCEVSignExtendExpr(); 178d19534add90a2a894af61523b830887097bb780bDan Gohman public: 179d19534add90a2a894af61523b830887097bb780bDan Gohman /// get method - This just gets and returns a new SCEVSignExtend object 180d19534add90a2a894af61523b830887097bb780bDan Gohman /// 181d19534add90a2a894af61523b830887097bb780bDan Gohman static SCEVHandle get(const SCEVHandle &Op, const Type *Ty); 182d19534add90a2a894af61523b830887097bb780bDan Gohman 183d19534add90a2a894af61523b830887097bb780bDan Gohman const SCEVHandle &getOperand() const { return Op; } 184d19534add90a2a894af61523b830887097bb780bDan Gohman virtual const Type *getType() const { return Ty; } 185d19534add90a2a894af61523b830887097bb780bDan Gohman 186d19534add90a2a894af61523b830887097bb780bDan Gohman virtual bool isLoopInvariant(const Loop *L) const { 187d19534add90a2a894af61523b830887097bb780bDan Gohman return Op->isLoopInvariant(L); 188d19534add90a2a894af61523b830887097bb780bDan Gohman } 189d19534add90a2a894af61523b830887097bb780bDan Gohman 190d19534add90a2a894af61523b830887097bb780bDan Gohman virtual bool hasComputableLoopEvolution(const Loop *L) const { 191d19534add90a2a894af61523b830887097bb780bDan Gohman return Op->hasComputableLoopEvolution(L); 192d19534add90a2a894af61523b830887097bb780bDan Gohman } 193d19534add90a2a894af61523b830887097bb780bDan Gohman 194d19534add90a2a894af61523b830887097bb780bDan Gohman /// getValueRange - Return the tightest constant bounds that this value is 195d19534add90a2a894af61523b830887097bb780bDan Gohman /// known to have. This method is only valid on integer SCEV objects. 196d19534add90a2a894af61523b830887097bb780bDan Gohman virtual ConstantRange getValueRange() const; 197d19534add90a2a894af61523b830887097bb780bDan Gohman 198d19534add90a2a894af61523b830887097bb780bDan Gohman SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, 199d19534add90a2a894af61523b830887097bb780bDan Gohman const SCEVHandle &Conc) const { 200d19534add90a2a894af61523b830887097bb780bDan Gohman SCEVHandle H = Op->replaceSymbolicValuesWithConcrete(Sym, Conc); 201d19534add90a2a894af61523b830887097bb780bDan Gohman if (H == Op) 202d19534add90a2a894af61523b830887097bb780bDan Gohman return this; 203d19534add90a2a894af61523b830887097bb780bDan Gohman return get(H, Ty); 204d19534add90a2a894af61523b830887097bb780bDan Gohman } 205d19534add90a2a894af61523b830887097bb780bDan Gohman 206d19534add90a2a894af61523b830887097bb780bDan Gohman virtual void print(std::ostream &OS) const; 207d19534add90a2a894af61523b830887097bb780bDan Gohman void print(std::ostream *OS) const { if (OS) print(*OS); } 208d19534add90a2a894af61523b830887097bb780bDan Gohman 209d19534add90a2a894af61523b830887097bb780bDan Gohman /// Methods for support type inquiry through isa, cast, and dyn_cast: 210d19534add90a2a894af61523b830887097bb780bDan Gohman static inline bool classof(const SCEVSignExtendExpr *S) { return true; } 211d19534add90a2a894af61523b830887097bb780bDan Gohman static inline bool classof(const SCEV *S) { 212d19534add90a2a894af61523b830887097bb780bDan Gohman return S->getSCEVType() == scSignExtend; 213d19534add90a2a894af61523b830887097bb780bDan Gohman } 214d19534add90a2a894af61523b830887097bb780bDan Gohman }; 215d19534add90a2a894af61523b830887097bb780bDan Gohman 2164950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2174950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner //===--------------------------------------------------------------------===// 2184950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// SCEVCommutativeExpr - This node is the base class for n'ary commutative 2194950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// operators. 2204950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 2214950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner class SCEVCommutativeExpr : public SCEV { 2224950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner std::vector<SCEVHandle> Operands; 2234950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2244950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner protected: 2254950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner SCEVCommutativeExpr(enum SCEVTypes T, const std::vector<SCEVHandle> &ops) 2264950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner : SCEV(T) { 2274950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner Operands.reserve(ops.size()); 2284950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner Operands.insert(Operands.end(), ops.begin(), ops.end()); 2294950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 2304950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner ~SCEVCommutativeExpr(); 2314950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2324950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner public: 2334950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner unsigned getNumOperands() const { return Operands.size(); } 2344950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const SCEVHandle &getOperand(unsigned i) const { 2354950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner assert(i < Operands.size() && "Operand index out of range!"); 2364950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return Operands[i]; 2374950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 2384950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2394950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const std::vector<SCEVHandle> &getOperands() const { return Operands; } 2404950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner typedef std::vector<SCEVHandle>::const_iterator op_iterator; 2414950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner op_iterator op_begin() const { return Operands.begin(); } 2424950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner op_iterator op_end() const { return Operands.end(); } 2434950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2444950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2454950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool isLoopInvariant(const Loop *L) const { 2464950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner for (unsigned i = 0, e = getNumOperands(); i != e; ++i) 2474950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner if (!getOperand(i)->isLoopInvariant(L)) return false; 2484950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return true; 2494950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 2504950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 251803513b364e27d303285d396fd8ee5b32149962aChris Lattner // hasComputableLoopEvolution - Commutative expressions have computable loop 252803513b364e27d303285d396fd8ee5b32149962aChris Lattner // evolutions iff they have at least one operand that varies with the loop, 253803513b364e27d303285d396fd8ee5b32149962aChris Lattner // but that all varying operands are computable. 2544950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool hasComputableLoopEvolution(const Loop *L) const { 255803513b364e27d303285d396fd8ee5b32149962aChris Lattner bool HasVarying = false; 2564950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner for (unsigned i = 0, e = getNumOperands(); i != e; ++i) 257803513b364e27d303285d396fd8ee5b32149962aChris Lattner if (!getOperand(i)->isLoopInvariant(L)) 258803513b364e27d303285d396fd8ee5b32149962aChris Lattner if (getOperand(i)->hasComputableLoopEvolution(L)) 259803513b364e27d303285d396fd8ee5b32149962aChris Lattner HasVarying = true; 260803513b364e27d303285d396fd8ee5b32149962aChris Lattner else 261803513b364e27d303285d396fd8ee5b32149962aChris Lattner return false; 262803513b364e27d303285d396fd8ee5b32149962aChris Lattner return HasVarying; 2634950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 2644950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 265afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, 266afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner const SCEVHandle &Conc) const; 267afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner 2684950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual const char *getOperationStr() const = 0; 2694950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2704950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual const Type *getType() const { return getOperand(0)->getType(); } 2714950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual void print(std::ostream &OS) const; 2725c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling void print(std::ostream *OS) const { if (OS) print(*OS); } 2734950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2744950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 2754950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEVCommutativeExpr *S) { return true; } 2764950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEV *S) { 2774950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return S->getSCEVType() == scAddExpr || 2784950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner S->getSCEVType() == scMulExpr; 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 { 2874950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner SCEVAddExpr(const std::vector<SCEVHandle> &ops) 2884950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner : SCEVCommutativeExpr(scAddExpr, ops) { 2894950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 2904950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2914950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner public: 2924950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static SCEVHandle get(std::vector<SCEVHandle> &Ops); 2934950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2944950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static SCEVHandle get(const SCEVHandle &LHS, const SCEVHandle &RHS) { 2954950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner std::vector<SCEVHandle> Ops; 2964950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner Ops.push_back(LHS); 2974950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner Ops.push_back(RHS); 2984950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return get(Ops); 2994950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 3004950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3014950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static SCEVHandle get(const SCEVHandle &Op0, const SCEVHandle &Op1, 3024950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const SCEVHandle &Op2) { 3034950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner std::vector<SCEVHandle> Ops; 3044950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner Ops.push_back(Op0); 3054950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner Ops.push_back(Op1); 3064950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner Ops.push_back(Op2); 3074950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return get(Ops); 3084950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 3094950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3104950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual const char *getOperationStr() const { return " + "; } 3114950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3124950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 3134950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEVAddExpr *S) { return true; } 3144950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEV *S) { 3154950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return S->getSCEVType() == scAddExpr; 3164950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 3174950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 3184950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3194950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner //===--------------------------------------------------------------------===// 3204950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// SCEVMulExpr - This node represents multiplication of some number of SCEVs. 3214950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 3224950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner class SCEVMulExpr : public SCEVCommutativeExpr { 3234950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner SCEVMulExpr(const std::vector<SCEVHandle> &ops) 3244950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner : SCEVCommutativeExpr(scMulExpr, ops) { 3254950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 3264950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3274950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner public: 3284950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static SCEVHandle get(std::vector<SCEVHandle> &Ops); 3294950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3304950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static SCEVHandle get(const SCEVHandle &LHS, const SCEVHandle &RHS) { 3314950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner std::vector<SCEVHandle> Ops; 3324950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner Ops.push_back(LHS); 3334950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner Ops.push_back(RHS); 3344950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return get(Ops); 3354950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 3364950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3374950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual const char *getOperationStr() const { return " * "; } 3384950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3394950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 3404950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEVMulExpr *S) { return true; } 3414950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEV *S) { 3424950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return S->getSCEVType() == scMulExpr; 3434950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 3444950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 3454950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3464950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3474950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner //===--------------------------------------------------------------------===// 3481628cec4d7fce310d9cde0bcc73997e5a71692c4Reid Spencer /// SCEVSDivExpr - This class represents a binary signed division operation. 3494950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 35060a05cc118763c680834a61280f48530482a1f86Chris Lattner class SCEVSDivExpr : public SCEV { 3514950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner SCEVHandle LHS, RHS; 35260a05cc118763c680834a61280f48530482a1f86Chris Lattner SCEVSDivExpr(const SCEVHandle &lhs, const SCEVHandle &rhs) 35360a05cc118763c680834a61280f48530482a1f86Chris Lattner : SCEV(scSDivExpr), LHS(lhs), RHS(rhs) {} 3544950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 35560a05cc118763c680834a61280f48530482a1f86Chris Lattner virtual ~SCEVSDivExpr(); 3564950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner public: 35760a05cc118763c680834a61280f48530482a1f86Chris Lattner /// get method - This just gets and returns a new SCEVSDiv object. 3584950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 3594950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static SCEVHandle get(const SCEVHandle &LHS, const SCEVHandle &RHS); 3604950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3614950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const SCEVHandle &getLHS() const { return LHS; } 3624950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const SCEVHandle &getRHS() const { return RHS; } 3634950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3644950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool isLoopInvariant(const Loop *L) const { 3654950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return LHS->isLoopInvariant(L) && RHS->isLoopInvariant(L); 3664950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 3674950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3684950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool hasComputableLoopEvolution(const Loop *L) const { 3694950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return LHS->hasComputableLoopEvolution(L) && 3704950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner RHS->hasComputableLoopEvolution(L); 3714950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 3724950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 373afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, 374afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner const SCEVHandle &Conc) const { 375afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner SCEVHandle L = LHS->replaceSymbolicValuesWithConcrete(Sym, Conc); 376afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner SCEVHandle R = RHS->replaceSymbolicValuesWithConcrete(Sym, Conc); 377afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner if (L == LHS && R == RHS) 378afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner return this; 379afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner else 380afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner return get(L, R); 381afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner } 382afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner 383afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner 3844950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual const Type *getType() const; 3854950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3864950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner void print(std::ostream &OS) const; 3875c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling void print(std::ostream *OS) const { if (OS) print(*OS); } 3884950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3894950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 39060a05cc118763c680834a61280f48530482a1f86Chris Lattner static inline bool classof(const SCEVSDivExpr *S) { return true; } 3914950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEV *S) { 39260a05cc118763c680834a61280f48530482a1f86Chris Lattner return S->getSCEVType() == scSDivExpr; 3934950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 3944950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 3954950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3964950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3974950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner //===--------------------------------------------------------------------===// 3984950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// SCEVAddRecExpr - This node represents a polynomial recurrence on the trip 3994950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// count of the specified loop. 4004950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 4014950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// All operands of an AddRec are required to be loop invariant. 4024950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 4034950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner class SCEVAddRecExpr : public SCEV { 4044950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner std::vector<SCEVHandle> Operands; 4054950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const Loop *L; 4064950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4074950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner SCEVAddRecExpr(const std::vector<SCEVHandle> &ops, const Loop *l) 4084950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner : SCEV(scAddRecExpr), Operands(ops), L(l) { 4094950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner for (unsigned i = 0, e = Operands.size(); i != e; ++i) 4104950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner assert(Operands[i]->isLoopInvariant(l) && 4114950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner "Operands of AddRec must be loop-invariant!"); 4124950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 4134950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner ~SCEVAddRecExpr(); 4144950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner public: 4154950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static SCEVHandle get(const SCEVHandle &Start, const SCEVHandle &Step, 4164950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const Loop *); 4174950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static SCEVHandle get(std::vector<SCEVHandle> &Operands, 4184950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const Loop *); 4194950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static SCEVHandle get(const std::vector<SCEVHandle> &Operands, 4204950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const Loop *L) { 4214950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner std::vector<SCEVHandle> NewOp(Operands); 4224950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return get(NewOp, L); 4234950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 4244950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4254950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner typedef std::vector<SCEVHandle>::const_iterator op_iterator; 4264950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner op_iterator op_begin() const { return Operands.begin(); } 4274950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner op_iterator op_end() const { return Operands.end(); } 4284950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4294950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner unsigned getNumOperands() const { return Operands.size(); } 4304950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const SCEVHandle &getOperand(unsigned i) const { return Operands[i]; } 4314950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const SCEVHandle &getStart() const { return Operands[0]; } 4324950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const Loop *getLoop() const { return L; } 4334950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4344950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4354950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// getStepRecurrence - This method constructs and returns the recurrence 4364950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// indicating how much this expression steps by. If this is a polynomial 4374950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// of degree N, it returns a chrec of degree N-1. 4384950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner SCEVHandle getStepRecurrence() const { 4394950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner if (getNumOperands() == 2) return getOperand(1); 4404950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return SCEVAddRecExpr::get(std::vector<SCEVHandle>(op_begin()+1,op_end()), 4414950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner getLoop()); 4424950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 4434950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4444950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool hasComputableLoopEvolution(const Loop *QL) const { 4454950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner if (L == QL) return true; 4464950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return false; 4474950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 4484950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4494950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool isLoopInvariant(const Loop *QueryLoop) const; 4504950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4514950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual const Type *getType() const { return Operands[0]->getType(); } 4524950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4534950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// isAffine - Return true if this is an affine AddRec (i.e., it represents 4544950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// an expressions A+B*x where A and B are loop invariant values. 4554950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner bool isAffine() const { 4564950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner // We know that the start value is invariant. This expression is thus 4574950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner // affine iff the step is also invariant. 4584950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return getNumOperands() == 2; 4594950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 4604950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4614950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// isQuadratic - Return true if this is an quadratic AddRec (i.e., it 4624950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// represents an expressions A+B*x+C*x^2 where A, B and C are loop 4634950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// invariant values. This corresponds to an addrec of the form {L,+,M,+,N} 4644950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner bool isQuadratic() const { 4654950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return getNumOperands() == 3; 4664950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 4674950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4684950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// evaluateAtIteration - Return the value of this chain of recurrences at 4694950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// the specified iteration number. 4704950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner SCEVHandle evaluateAtIteration(SCEVHandle It) const; 4714950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4724950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// getNumIterationsInRange - Return the number of iterations of this loop 4734950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// that produce values in the specified constant range. Another way of 4744950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// looking at this is that it returns the first iteration number where the 4754950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// value is not in the condition, thus computing the exit count. If the 4764950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// iteration count can't be computed, an instance of SCEVCouldNotCompute is 477e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer /// returned. The isSigned parameter indicates whether the ConstantRange 478e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer /// should be treated as signed or unsigned. 479e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer SCEVHandle getNumIterationsInRange(ConstantRange Range, 480e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer bool isSigned) const; 4814950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 482afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, 483afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner const SCEVHandle &Conc) const; 4844950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4854950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual void print(std::ostream &OS) const; 4865c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling void print(std::ostream *OS) const { if (OS) print(*OS); } 4874950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4884950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 4894950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEVAddRecExpr *S) { return true; } 4904950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEV *S) { 4914950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return S->getSCEVType() == scAddRecExpr; 4924950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 4934950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 4944950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4954950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner //===--------------------------------------------------------------------===// 4964950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// SCEVUnknown - This means that we are dealing with an entirely unknown SCEV 4974950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// value, and only represent it as it's LLVM Value. This is the "bottom" 4984950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// value for the analysis. 4994950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 5004950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner class SCEVUnknown : public SCEV { 5014950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner Value *V; 5024950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner SCEVUnknown(Value *v) : SCEV(scUnknown), V(v) {} 5034950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 5044950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner protected: 5054950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner ~SCEVUnknown(); 5064950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner public: 5074950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// get method - For SCEVUnknown, this just gets and returns a new 5084950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// SCEVUnknown. 5094950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static SCEVHandle get(Value *V); 5104950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 5112cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner /// getIntegerSCEV - Given an integer or FP type, create a constant for the 5122cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner /// specified signed integer value and return a SCEV for the constant. 5132cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner static SCEVHandle getIntegerSCEV(int Val, const Type *Ty); 51435fa43907e2ea751ad35bfbaab8c4d3511422c14Reid Spencer static SCEVHandle getIntegerSCEV(const APInt& Val); 5154950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 5162cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner Value *getValue() const { return V; } 5174950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 5184950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool isLoopInvariant(const Loop *L) const; 5194950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool hasComputableLoopEvolution(const Loop *QL) const { 5204950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return false; // not computable 5214950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 5224950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 523afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym, 524afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner const SCEVHandle &Conc) const { 525afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner if (&*Sym == this) return Conc; 526afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner return this; 527afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner } 528afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner 5294950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual const Type *getType() const; 5304950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 5314950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual void print(std::ostream &OS) const; 5325c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling void print(std::ostream *OS) const { if (OS) print(*OS); } 5334950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 5344950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 5354950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEVUnknown *S) { return true; } 5364950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEV *S) { 5374950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return S->getSCEVType() == scUnknown; 5384950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 5394950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 5402cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner 5412cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner /// SCEVVisitor - This class defines a simple visitor class that may be used 5422cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner /// for various SCEV analysis purposes. 5432cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner template<typename SC, typename RetVal=void> 5442cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner struct SCEVVisitor { 5452cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner RetVal visit(SCEV *S) { 5462cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner switch (S->getSCEVType()) { 5472cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner case scConstant: 5482cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner return ((SC*)this)->visitConstant((SCEVConstant*)S); 5492cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner case scTruncate: 5502cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner return ((SC*)this)->visitTruncateExpr((SCEVTruncateExpr*)S); 5512cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner case scZeroExtend: 5522cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner return ((SC*)this)->visitZeroExtendExpr((SCEVZeroExtendExpr*)S); 553d19534add90a2a894af61523b830887097bb780bDan Gohman case scSignExtend: 554d19534add90a2a894af61523b830887097bb780bDan Gohman return ((SC*)this)->visitSignExtendExpr((SCEVSignExtendExpr*)S); 5552cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner case scAddExpr: 5562cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner return ((SC*)this)->visitAddExpr((SCEVAddExpr*)S); 5572cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner case scMulExpr: 5582cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner return ((SC*)this)->visitMulExpr((SCEVMulExpr*)S); 55960a05cc118763c680834a61280f48530482a1f86Chris Lattner case scSDivExpr: 56060a05cc118763c680834a61280f48530482a1f86Chris Lattner return ((SC*)this)->visitSDivExpr((SCEVSDivExpr*)S); 5612cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner case scAddRecExpr: 5622cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner return ((SC*)this)->visitAddRecExpr((SCEVAddRecExpr*)S); 5632cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner case scUnknown: 5642cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner return ((SC*)this)->visitUnknown((SCEVUnknown*)S); 5652cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner case scCouldNotCompute: 5662cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner return ((SC*)this)->visitCouldNotCompute((SCEVCouldNotCompute*)S); 5672cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner default: 5682cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner assert(0 && "Unknown SCEV type!"); 5690ebf428e48ab258012d94d8efa05a4ae5932e2dbChris Lattner abort(); 5702cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner } 5712cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner } 5722cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner 5732cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner RetVal visitCouldNotCompute(SCEVCouldNotCompute *S) { 5742cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner assert(0 && "Invalid use of SCEVCouldNotCompute!"); 5752cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner abort(); 5762cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner return RetVal(); 5772cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner } 5782cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner }; 5794950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner} 5804950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 5814950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner#endif 5824950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 583