ScalarEvolutionExpressions.h revision fef8bb24de86ff41d09a7787c6c52b058a853e39
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" 18c25e7581b9b8088910da31702d4ca21c4734c6d7Torok Edwin#include "llvm/Support/ErrorHandling.h" 194950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 204950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattnernamespace llvm { 214950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner class ConstantInt; 224950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner class ConstantRange; 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; 40c050fd94c29e31414591e3a18aa20049e6b3a84fDan Gohman SCEVConstant(const FoldingSetNodeID &ID, ConstantInt *v) : 41c050fd94c29e31414591e3a18aa20049e6b3a84fDan Gohman SCEV(ID, scConstant), V(v) {} 424950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner public: 434950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner ConstantInt *getValue() const { return V; } 444950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 454950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool isLoopInvariant(const Loop *L) const { 464950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return true; 474950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 484950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 494950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool hasComputableLoopEvolution(const Loop *L) const { 504950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return false; // Not loop variant 514950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 524950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 534950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual const Type *getType() const; 544950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 55fef8bb24de86ff41d09a7787c6c52b058a853e39Dan Gohman virtual bool hasOperand(const SCEV *) const { 56fef8bb24de86ff41d09a7787c6c52b058a853e39Dan Gohman return false; 57afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner } 58afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner 595a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng bool dominates(BasicBlock *BB, DominatorTree *DT) const { 605a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng return true; 615a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng } 625a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng 63b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman virtual void print(raw_ostream &OS) const; 644950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 654950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 664950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEVConstant *S) { return true; } 674950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEV *S) { 684950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return S->getSCEVType() == scConstant; 694950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 704950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 714950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 724950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner //===--------------------------------------------------------------------===// 7384923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman /// SCEVCastExpr - This is the base class for unary cast operator classes. 744950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 7584923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman class SCEVCastExpr : public SCEV { 7684923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman protected: 770bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *Op; 784950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const Type *Ty; 7984923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman 80c050fd94c29e31414591e3a18aa20049e6b3a84fDan Gohman SCEVCastExpr(const FoldingSetNodeID &ID, 81c050fd94c29e31414591e3a18aa20049e6b3a84fDan Gohman unsigned SCEVTy, const SCEV *op, const Type *ty); 8284923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman 834950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner public: 840bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getOperand() const { return Op; } 854950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual const Type *getType() const { return Ty; } 869769ab22265b313171d201b5928688524a01bd87Misha Brukman 874950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool isLoopInvariant(const Loop *L) const { 884950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return Op->isLoopInvariant(L); 894950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 904950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 914950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool hasComputableLoopEvolution(const Loop *L) const { 924950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return Op->hasComputableLoopEvolution(L); 934950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 944950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 95fef8bb24de86ff41d09a7787c6c52b058a853e39Dan Gohman virtual bool hasOperand(const SCEV *O) const { 96fef8bb24de86ff41d09a7787c6c52b058a853e39Dan Gohman return Op == O || Op->hasOperand(O); 97fef8bb24de86ff41d09a7787c6c52b058a853e39Dan Gohman } 98fef8bb24de86ff41d09a7787c6c52b058a853e39Dan Gohman 9984923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman virtual bool dominates(BasicBlock *BB, DominatorTree *DT) const; 10084923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman 10184923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman /// Methods for support type inquiry through isa, cast, and dyn_cast: 10284923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman static inline bool classof(const SCEVCastExpr *S) { return true; } 10384923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman static inline bool classof(const SCEV *S) { 10484923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman return S->getSCEVType() == scTruncate || 10584923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman S->getSCEVType() == scZeroExtend || 10684923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman S->getSCEVType() == scSignExtend; 10784923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman } 10884923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman }; 10984923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman 11084923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman //===--------------------------------------------------------------------===// 11184923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman /// SCEVTruncateExpr - This class represents a truncation of an integer value 11284923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman /// to a smaller integer value. 11384923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman /// 11484923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman class SCEVTruncateExpr : public SCEVCastExpr { 11584923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman friend class ScalarEvolution; 11684923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman 117c050fd94c29e31414591e3a18aa20049e6b3a84fDan Gohman SCEVTruncateExpr(const FoldingSetNodeID &ID, 118c050fd94c29e31414591e3a18aa20049e6b3a84fDan Gohman const SCEV *op, const Type *ty); 11984923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman 12084923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman public: 121b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman virtual void print(raw_ostream &OS) const; 1224950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 1234950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 1244950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEVTruncateExpr *S) { return true; } 1254950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEV *S) { 1264950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return S->getSCEVType() == scTruncate; 1274950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 1284950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 1294950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 1304950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner //===--------------------------------------------------------------------===// 1314950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// SCEVZeroExtendExpr - This class represents a zero extension of a small 1324950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// integer value to a larger integer value. 1334950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 13484923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman class SCEVZeroExtendExpr : public SCEVCastExpr { 135246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman friend class ScalarEvolution; 136246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman 137c050fd94c29e31414591e3a18aa20049e6b3a84fDan Gohman SCEVZeroExtendExpr(const FoldingSetNodeID &ID, 138c050fd94c29e31414591e3a18aa20049e6b3a84fDan Gohman const SCEV *op, const Type *ty); 1394950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 14084923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman public: 141b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman virtual void print(raw_ostream &OS) const; 1424950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 1434950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 1444950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEVZeroExtendExpr *S) { return true; } 1454950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEV *S) { 1464950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return S->getSCEVType() == scZeroExtend; 1474950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 1484950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 1494950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 150d19534add90a2a894af61523b830887097bb780bDan Gohman //===--------------------------------------------------------------------===// 151d19534add90a2a894af61523b830887097bb780bDan Gohman /// SCEVSignExtendExpr - This class represents a sign extension of a small 152d19534add90a2a894af61523b830887097bb780bDan Gohman /// integer value to a larger integer value. 153d19534add90a2a894af61523b830887097bb780bDan Gohman /// 15484923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman class SCEVSignExtendExpr : public SCEVCastExpr { 155246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman friend class ScalarEvolution; 156246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman 157c050fd94c29e31414591e3a18aa20049e6b3a84fDan Gohman SCEVSignExtendExpr(const FoldingSetNodeID &ID, 158c050fd94c29e31414591e3a18aa20049e6b3a84fDan Gohman const SCEV *op, const Type *ty); 159d19534add90a2a894af61523b830887097bb780bDan Gohman 16084923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman public: 161b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman virtual void print(raw_ostream &OS) const; 162d19534add90a2a894af61523b830887097bb780bDan Gohman 163d19534add90a2a894af61523b830887097bb780bDan Gohman /// Methods for support type inquiry through isa, cast, and dyn_cast: 164d19534add90a2a894af61523b830887097bb780bDan Gohman static inline bool classof(const SCEVSignExtendExpr *S) { return true; } 165d19534add90a2a894af61523b830887097bb780bDan Gohman static inline bool classof(const SCEV *S) { 166d19534add90a2a894af61523b830887097bb780bDan Gohman return S->getSCEVType() == scSignExtend; 167d19534add90a2a894af61523b830887097bb780bDan Gohman } 168d19534add90a2a894af61523b830887097bb780bDan Gohman }; 169d19534add90a2a894af61523b830887097bb780bDan Gohman 1704950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 171d9480d0f6875d8aa3a0d91942d24f0ee416b1ff1Dan Gohman //===--------------------------------------------------------------------===// 172d9480d0f6875d8aa3a0d91942d24f0ee416b1ff1Dan Gohman /// SCEVNAryExpr - This node is a base class providing common 173d9480d0f6875d8aa3a0d91942d24f0ee416b1ff1Dan Gohman /// functionality for n'ary operators. 174d9480d0f6875d8aa3a0d91942d24f0ee416b1ff1Dan Gohman /// 175ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman class SCEVNAryExpr : public SCEV { 176ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman protected: 1770bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman SmallVector<const SCEV *, 8> Operands; 1784950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 179c050fd94c29e31414591e3a18aa20049e6b3a84fDan Gohman SCEVNAryExpr(const FoldingSetNodeID &ID, 180c050fd94c29e31414591e3a18aa20049e6b3a84fDan Gohman enum SCEVTypes T, const SmallVectorImpl<const SCEV *> &ops) 181c050fd94c29e31414591e3a18aa20049e6b3a84fDan Gohman : SCEV(ID, T), Operands(ops.begin(), ops.end()) {} 1824950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 1834950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner public: 18434cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng unsigned getNumOperands() const { return (unsigned)Operands.size(); } 1850bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getOperand(unsigned i) const { 1864950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner assert(i < Operands.size() && "Operand index out of range!"); 1874950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return Operands[i]; 1884950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 1894950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 1900bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SmallVectorImpl<const SCEV *> &getOperands() const { 1910bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman return Operands; 1920bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman } 1930bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman typedef SmallVectorImpl<const SCEV *>::const_iterator op_iterator; 1944950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner op_iterator op_begin() const { return Operands.begin(); } 1954950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner op_iterator op_end() const { return Operands.end(); } 1964950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 1974950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool isLoopInvariant(const Loop *L) const { 1984950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner for (unsigned i = 0, e = getNumOperands(); i != e; ++i) 1994950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner if (!getOperand(i)->isLoopInvariant(L)) return false; 2004950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return true; 2014950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 2024950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 20339592233304acbbeea8c53bac2b6a822a63a4c4bDan Gohman // hasComputableLoopEvolution - N-ary expressions have computable loop 204803513b364e27d303285d396fd8ee5b32149962aChris Lattner // evolutions iff they have at least one operand that varies with the loop, 205803513b364e27d303285d396fd8ee5b32149962aChris Lattner // but that all varying operands are computable. 2064950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool hasComputableLoopEvolution(const Loop *L) const { 207803513b364e27d303285d396fd8ee5b32149962aChris Lattner bool HasVarying = false; 2084950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner for (unsigned i = 0, e = getNumOperands(); i != e; ++i) 209ae9f3a3b7c915f725aef5a7250e88eaeddda03c6Anton Korobeynikov if (!getOperand(i)->isLoopInvariant(L)) { 210803513b364e27d303285d396fd8ee5b32149962aChris Lattner if (getOperand(i)->hasComputableLoopEvolution(L)) 211803513b364e27d303285d396fd8ee5b32149962aChris Lattner HasVarying = true; 212803513b364e27d303285d396fd8ee5b32149962aChris Lattner else 213803513b364e27d303285d396fd8ee5b32149962aChris Lattner return false; 214ae9f3a3b7c915f725aef5a7250e88eaeddda03c6Anton Korobeynikov } 215803513b364e27d303285d396fd8ee5b32149962aChris Lattner return HasVarying; 2164950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 2174950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 218fef8bb24de86ff41d09a7787c6c52b058a853e39Dan Gohman virtual bool hasOperand(const SCEV *O) const { 219fef8bb24de86ff41d09a7787c6c52b058a853e39Dan Gohman for (unsigned i = 0, e = getNumOperands(); i != e; ++i) 220fef8bb24de86ff41d09a7787c6c52b058a853e39Dan Gohman if (O == getOperand(i) || getOperand(i)->hasOperand(O)) 221fef8bb24de86ff41d09a7787c6c52b058a853e39Dan Gohman return true; 222fef8bb24de86ff41d09a7787c6c52b058a853e39Dan Gohman return false; 223fef8bb24de86ff41d09a7787c6c52b058a853e39Dan Gohman } 224fef8bb24de86ff41d09a7787c6c52b058a853e39Dan Gohman 225ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman bool dominates(BasicBlock *BB, DominatorTree *DT) const; 226ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman 227ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman virtual const Type *getType() const { return getOperand(0)->getType(); } 228ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman 229ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman /// Methods for support type inquiry through isa, cast, and dyn_cast: 230ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman static inline bool classof(const SCEVNAryExpr *S) { return true; } 231ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman static inline bool classof(const SCEV *S) { 232ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman return S->getSCEVType() == scAddExpr || 233ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman S->getSCEVType() == scMulExpr || 234ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman S->getSCEVType() == scSMaxExpr || 235ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman S->getSCEVType() == scUMaxExpr || 236ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman S->getSCEVType() == scAddRecExpr; 237ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman } 238ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman }; 239ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman 240ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman //===--------------------------------------------------------------------===// 241ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman /// SCEVCommutativeExpr - This node is the base class for n'ary commutative 242ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman /// operators. 243ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman /// 244ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman class SCEVCommutativeExpr : public SCEVNAryExpr { 245ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman protected: 246c050fd94c29e31414591e3a18aa20049e6b3a84fDan Gohman SCEVCommutativeExpr(const FoldingSetNodeID &ID, 247c050fd94c29e31414591e3a18aa20049e6b3a84fDan Gohman enum SCEVTypes T, 2480bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SmallVectorImpl<const SCEV *> &ops) 249c050fd94c29e31414591e3a18aa20049e6b3a84fDan Gohman : SCEVNAryExpr(ID, T, ops) {} 250ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman 251ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman public: 2524950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual const char *getOperationStr() const = 0; 2534950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 254b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman virtual void print(raw_ostream &OS) const; 2554950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2564950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 2574950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEVCommutativeExpr *S) { return true; } 2584950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEV *S) { 2594950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return S->getSCEVType() == scAddExpr || 260c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky S->getSCEVType() == scMulExpr || 2613e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky S->getSCEVType() == scSMaxExpr || 2623e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky S->getSCEVType() == scUMaxExpr; 2634950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 2644950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 2654950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2664950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2674950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner //===--------------------------------------------------------------------===// 2684950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// SCEVAddExpr - This node represents an addition of some number of SCEVs. 2694950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 2704950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner class SCEVAddExpr : public SCEVCommutativeExpr { 271246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman friend class ScalarEvolution; 272246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman 273c050fd94c29e31414591e3a18aa20049e6b3a84fDan Gohman SCEVAddExpr(const FoldingSetNodeID &ID, 274c050fd94c29e31414591e3a18aa20049e6b3a84fDan Gohman const SmallVectorImpl<const SCEV *> &ops) 275c050fd94c29e31414591e3a18aa20049e6b3a84fDan Gohman : SCEVCommutativeExpr(ID, scAddExpr, ops) { 2764950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 2774950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2784950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner public: 2794950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual const char *getOperationStr() const { return " + "; } 2804950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2814950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 2824950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEVAddExpr *S) { return true; } 2834950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEV *S) { 2844950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return S->getSCEVType() == scAddExpr; 2854950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 2864950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 2874950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2884950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner //===--------------------------------------------------------------------===// 2894950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// SCEVMulExpr - This node represents multiplication of some number of SCEVs. 2904950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 2914950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner class SCEVMulExpr : public SCEVCommutativeExpr { 292246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman friend class ScalarEvolution; 293246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman 294c050fd94c29e31414591e3a18aa20049e6b3a84fDan Gohman SCEVMulExpr(const FoldingSetNodeID &ID, 295c050fd94c29e31414591e3a18aa20049e6b3a84fDan Gohman const SmallVectorImpl<const SCEV *> &ops) 296c050fd94c29e31414591e3a18aa20049e6b3a84fDan Gohman : SCEVCommutativeExpr(ID, scMulExpr, ops) { 2974950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 2984950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2994950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner public: 3004950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual const char *getOperationStr() const { return " * "; } 3014950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3024950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 3034950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEVMulExpr *S) { return true; } 3044950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEV *S) { 3054950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return S->getSCEVType() == scMulExpr; 3064950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 3074950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 3084950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3094950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3104950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner //===--------------------------------------------------------------------===// 311e3320a1bcce3f6653e109cc86ee1011b0a61d808Wojciech Matyjewicz /// SCEVUDivExpr - This class represents a binary unsigned division operation. 3124950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 313e3320a1bcce3f6653e109cc86ee1011b0a61d808Wojciech Matyjewicz class SCEVUDivExpr : public SCEV { 314246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman friend class ScalarEvolution; 315246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman 3160bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *LHS; 3170bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *RHS; 318c050fd94c29e31414591e3a18aa20049e6b3a84fDan Gohman SCEVUDivExpr(const FoldingSetNodeID &ID, const SCEV *lhs, const SCEV *rhs) 319c050fd94c29e31414591e3a18aa20049e6b3a84fDan Gohman : SCEV(ID, scUDivExpr), LHS(lhs), RHS(rhs) {} 3204950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3214950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner public: 3220bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getLHS() const { return LHS; } 3230bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getRHS() const { return RHS; } 3244950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3254950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool isLoopInvariant(const Loop *L) const { 3264950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return LHS->isLoopInvariant(L) && RHS->isLoopInvariant(L); 3274950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 3284950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3294950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool hasComputableLoopEvolution(const Loop *L) const { 3304950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return LHS->hasComputableLoopEvolution(L) && 3314950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner RHS->hasComputableLoopEvolution(L); 3324950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 3334950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 334fef8bb24de86ff41d09a7787c6c52b058a853e39Dan Gohman virtual bool hasOperand(const SCEV *O) const { 335fef8bb24de86ff41d09a7787c6c52b058a853e39Dan Gohman return O == LHS || O == RHS || LHS->hasOperand(O) || RHS->hasOperand(O); 336afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner } 337afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner 3385a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng bool dominates(BasicBlock *BB, DominatorTree *DT) const; 339afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner 3404950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual const Type *getType() const; 3414950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 342b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman void print(raw_ostream &OS) const; 3434950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3444950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 345e3320a1bcce3f6653e109cc86ee1011b0a61d808Wojciech Matyjewicz static inline bool classof(const SCEVUDivExpr *S) { return true; } 3464950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEV *S) { 347e3320a1bcce3f6653e109cc86ee1011b0a61d808Wojciech Matyjewicz return S->getSCEVType() == scUDivExpr; 3484950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 3494950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 3504950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3514950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3524950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner //===--------------------------------------------------------------------===// 3534950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// SCEVAddRecExpr - This node represents a polynomial recurrence on the trip 3541e59aa1332b67256dc0e76237eab7f6dd21a25b4Dan Gohman /// count of the specified loop. This is the primary focus of the 3551e59aa1332b67256dc0e76237eab7f6dd21a25b4Dan Gohman /// ScalarEvolution framework; all the other SCEV subclasses are mostly just 3561e59aa1332b67256dc0e76237eab7f6dd21a25b4Dan Gohman /// supporting infrastructure to allow SCEVAddRecExpr expressions to be 3571e59aa1332b67256dc0e76237eab7f6dd21a25b4Dan Gohman /// created and analyzed. 3584950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 3594950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// All operands of an AddRec are required to be loop invariant. 3604950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 361ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman class SCEVAddRecExpr : public SCEVNAryExpr { 362246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman friend class ScalarEvolution; 363246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman 3644950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const Loop *L; 3654950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 366c050fd94c29e31414591e3a18aa20049e6b3a84fDan Gohman SCEVAddRecExpr(const FoldingSetNodeID &ID, 367c050fd94c29e31414591e3a18aa20049e6b3a84fDan Gohman const SmallVectorImpl<const SCEV *> &ops, const Loop *l) 368c050fd94c29e31414591e3a18aa20049e6b3a84fDan Gohman : SCEVNAryExpr(ID, scAddRecExpr, ops), L(l) { 36934cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng for (size_t i = 0, e = Operands.size(); i != e; ++i) 3704950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner assert(Operands[i]->isLoopInvariant(l) && 3714950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner "Operands of AddRec must be loop-invariant!"); 3724950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 3734950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 374ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman public: 3750bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getStart() const { return Operands[0]; } 3764950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const Loop *getLoop() const { return L; } 3774950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3784950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// getStepRecurrence - This method constructs and returns the recurrence 3794950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// indicating how much this expression steps by. If this is a polynomial 3804950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// of degree N, it returns a chrec of degree N-1. 3810bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getStepRecurrence(ScalarEvolution &SE) const { 38217f1972c770dc18f5c7c3c95776b4d62ae9e121dDan Gohman if (isAffine()) return getOperand(1); 3830bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman return SE.getAddRecExpr(SmallVector<const SCEV *, 3>(op_begin()+1, 3840bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman op_end()), 385246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman getLoop()); 3864950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 3874950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3884950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool hasComputableLoopEvolution(const Loop *QL) const { 3894950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner if (L == QL) return true; 3904950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return false; 3914950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 3924950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3934950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool isLoopInvariant(const Loop *QueryLoop) const; 3944950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3954950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// isAffine - Return true if this is an affine AddRec (i.e., it represents 3964950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// an expressions A+B*x where A and B are loop invariant values. 3974950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner bool isAffine() const { 3984950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner // We know that the start value is invariant. This expression is thus 3994950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner // affine iff the step is also invariant. 4004950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return getNumOperands() == 2; 4014950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 4024950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4034950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// isQuadratic - Return true if this is an quadratic AddRec (i.e., it 4044950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// represents an expressions A+B*x+C*x^2 where A, B and C are loop 4054950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// invariant values. This corresponds to an addrec of the form {L,+,M,+,N} 4064950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner bool isQuadratic() const { 4074950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return getNumOperands() == 3; 4084950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 4094950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4104950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// evaluateAtIteration - Return the value of this chain of recurrences at 4114950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// the specified iteration number. 4120bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const; 4134950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4144950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// getNumIterationsInRange - Return the number of iterations of this loop 4154950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// that produce values in the specified constant range. Another way of 4164950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// looking at this is that it returns the first iteration number where the 4174950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// value is not in the condition, thus computing the exit count. If the 4184950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// iteration count can't be computed, an instance of SCEVCouldNotCompute is 419eefdebe002ede066bf80859e72aec831cfd1d92dNick Lewycky /// returned. 4200bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getNumIterationsInRange(ConstantRange Range, 421246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman ScalarEvolution &SE) const; 4224950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 423c050fd94c29e31414591e3a18aa20049e6b3a84fDan Gohman /// getPostIncExpr - Return an expression representing the value of 424c050fd94c29e31414591e3a18aa20049e6b3a84fDan Gohman /// this expression one iteration of the loop ahead. 425fef8bb24de86ff41d09a7787c6c52b058a853e39Dan Gohman const SCEVAddRecExpr *getPostIncExpr(ScalarEvolution &SE) const { 426fef8bb24de86ff41d09a7787c6c52b058a853e39Dan Gohman return cast<SCEVAddRecExpr>(SE.getAddExpr(this, getStepRecurrence(SE))); 427c050fd94c29e31414591e3a18aa20049e6b3a84fDan Gohman } 428c050fd94c29e31414591e3a18aa20049e6b3a84fDan Gohman 429d3ff30455707d479dfb883b3ea12794bb37b91b3Dan Gohman bool hasNoUnsignedOverflow() const { return SubclassData & (1 << 0); } 430d3ff30455707d479dfb883b3ea12794bb37b91b3Dan Gohman void setHasNoUnsignedOverflow(bool B) { 431d3ff30455707d479dfb883b3ea12794bb37b91b3Dan Gohman SubclassData = (SubclassData & ~(1 << 0)) | (B << 0); 432d3ff30455707d479dfb883b3ea12794bb37b91b3Dan Gohman } 433d3ff30455707d479dfb883b3ea12794bb37b91b3Dan Gohman bool hasNoSignedOverflow() const { return SubclassData & (1 << 1); } 434d3ff30455707d479dfb883b3ea12794bb37b91b3Dan Gohman void setHasNoSignedOverflow(bool B) { 435d3ff30455707d479dfb883b3ea12794bb37b91b3Dan Gohman SubclassData = (SubclassData & ~(1 << 1)) | (B << 1); 436d3ff30455707d479dfb883b3ea12794bb37b91b3Dan Gohman } 437d3ff30455707d479dfb883b3ea12794bb37b91b3Dan Gohman 438b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman virtual void print(raw_ostream &OS) const; 4394950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4404950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 4414950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEVAddRecExpr *S) { return true; } 4424950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEV *S) { 4434950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return S->getSCEVType() == scAddRecExpr; 4444950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 4454950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 4464950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 447c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky 448c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky //===--------------------------------------------------------------------===// 449c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky /// SCEVSMaxExpr - This class represents a signed maximum selection. 450c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky /// 451c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky class SCEVSMaxExpr : public SCEVCommutativeExpr { 452c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky friend class ScalarEvolution; 453c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky 454c050fd94c29e31414591e3a18aa20049e6b3a84fDan Gohman SCEVSMaxExpr(const FoldingSetNodeID &ID, 455c050fd94c29e31414591e3a18aa20049e6b3a84fDan Gohman const SmallVectorImpl<const SCEV *> &ops) 456c050fd94c29e31414591e3a18aa20049e6b3a84fDan Gohman : SCEVCommutativeExpr(ID, scSMaxExpr, ops) { 457c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky } 458c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky 459c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky public: 460c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky virtual const char *getOperationStr() const { return " smax "; } 461c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky 462c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky /// Methods for support type inquiry through isa, cast, and dyn_cast: 463c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky static inline bool classof(const SCEVSMaxExpr *S) { return true; } 464c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky static inline bool classof(const SCEV *S) { 465c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky return S->getSCEVType() == scSMaxExpr; 466c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky } 467c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky }; 468c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky 469c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky 4704950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner //===--------------------------------------------------------------------===// 4713e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky /// SCEVUMaxExpr - This class represents an unsigned maximum selection. 4723e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky /// 4733e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky class SCEVUMaxExpr : public SCEVCommutativeExpr { 4743e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky friend class ScalarEvolution; 4753e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky 476c050fd94c29e31414591e3a18aa20049e6b3a84fDan Gohman SCEVUMaxExpr(const FoldingSetNodeID &ID, 477c050fd94c29e31414591e3a18aa20049e6b3a84fDan Gohman const SmallVectorImpl<const SCEV *> &ops) 478c050fd94c29e31414591e3a18aa20049e6b3a84fDan Gohman : SCEVCommutativeExpr(ID, scUMaxExpr, ops) { 4793e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky } 4803e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky 4813e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky public: 4823e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky virtual const char *getOperationStr() const { return " umax "; } 4833e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky 4843e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky /// Methods for support type inquiry through isa, cast, and dyn_cast: 4853e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky static inline bool classof(const SCEVUMaxExpr *S) { return true; } 4863e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky static inline bool classof(const SCEV *S) { 4873e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky return S->getSCEVType() == scUMaxExpr; 4883e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky } 4893e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky }; 4903e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky 4913e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky 4923e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky //===--------------------------------------------------------------------===// 4934950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// SCEVUnknown - This means that we are dealing with an entirely unknown SCEV 4944950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// value, and only represent it as it's LLVM Value. This is the "bottom" 4954950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// value for the analysis. 4964950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 4974950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner class SCEVUnknown : public SCEV { 498246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman friend class ScalarEvolution; 499246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman 5004950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner Value *V; 501c050fd94c29e31414591e3a18aa20049e6b3a84fDan Gohman SCEVUnknown(const FoldingSetNodeID &ID, Value *v) : 502c050fd94c29e31414591e3a18aa20049e6b3a84fDan Gohman SCEV(ID, scUnknown), V(v) {} 5031c34375f79b7786351c27ae45f0412cfdfa004edDan Gohman 504c050fd94c29e31414591e3a18aa20049e6b3a84fDan Gohman public: 5052cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner Value *getValue() const { return V; } 5064950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 5074950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool isLoopInvariant(const Loop *L) const; 5084950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool hasComputableLoopEvolution(const Loop *QL) const { 5094950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return false; // not computable 5104950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 5114950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 512fef8bb24de86ff41d09a7787c6c52b058a853e39Dan Gohman virtual bool hasOperand(const SCEV *) const { 513fef8bb24de86ff41d09a7787c6c52b058a853e39Dan Gohman return false; 514afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner } 515afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner 5165a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng bool dominates(BasicBlock *BB, DominatorTree *DT) const; 5175a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng 5184950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual const Type *getType() const; 5194950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 520b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman virtual void print(raw_ostream &OS) const; 5214950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 5224950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 5234950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEVUnknown *S) { return true; } 5244950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEV *S) { 5254950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return S->getSCEVType() == scUnknown; 5264950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 5274950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 5282cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner 5292cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner /// SCEVVisitor - This class defines a simple visitor class that may be used 5302cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner /// for various SCEV analysis purposes. 5312cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner template<typename SC, typename RetVal=void> 5322cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner struct SCEVVisitor { 533890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman RetVal visit(const SCEV *S) { 5342cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner switch (S->getSCEVType()) { 5352cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner case scConstant: 536890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman return ((SC*)this)->visitConstant((const SCEVConstant*)S); 5372cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner case scTruncate: 538890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman return ((SC*)this)->visitTruncateExpr((const SCEVTruncateExpr*)S); 5392cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner case scZeroExtend: 540890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman return ((SC*)this)->visitZeroExtendExpr((const SCEVZeroExtendExpr*)S); 541d19534add90a2a894af61523b830887097bb780bDan Gohman case scSignExtend: 542890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman return ((SC*)this)->visitSignExtendExpr((const SCEVSignExtendExpr*)S); 5432cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner case scAddExpr: 544890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman return ((SC*)this)->visitAddExpr((const SCEVAddExpr*)S); 5452cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner case scMulExpr: 546890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman return ((SC*)this)->visitMulExpr((const SCEVMulExpr*)S); 547e3320a1bcce3f6653e109cc86ee1011b0a61d808Wojciech Matyjewicz case scUDivExpr: 548890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman return ((SC*)this)->visitUDivExpr((const SCEVUDivExpr*)S); 5492cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner case scAddRecExpr: 550890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman return ((SC*)this)->visitAddRecExpr((const SCEVAddRecExpr*)S); 551c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky case scSMaxExpr: 552890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman return ((SC*)this)->visitSMaxExpr((const SCEVSMaxExpr*)S); 5533e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky case scUMaxExpr: 554890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman return ((SC*)this)->visitUMaxExpr((const SCEVUMaxExpr*)S); 5552cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner case scUnknown: 556890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman return ((SC*)this)->visitUnknown((const SCEVUnknown*)S); 5572cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner case scCouldNotCompute: 558890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman return ((SC*)this)->visitCouldNotCompute((const SCEVCouldNotCompute*)S); 5592cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner default: 560c23197a26f34f559ea9797de51e187087c039c42Torok Edwin llvm_unreachable("Unknown SCEV type!"); 5612cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner } 5622cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner } 5632cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner 564890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman RetVal visitCouldNotCompute(const SCEVCouldNotCompute *S) { 565c23197a26f34f559ea9797de51e187087c039c42Torok Edwin llvm_unreachable("Invalid use of SCEVCouldNotCompute!"); 5662cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner return RetVal(); 5672cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner } 5682cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner }; 5694950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner} 5704950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 5714950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner#endif 572