ScalarEvolutionExpressions.h revision 2f199f9952b9dd62b5a0d0f4350b8fa780ebb9cc
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, 29c40f17b08774c2dcc5787fd83241e3c64ba82974Dan Gohman scUDivExpr, scAddRecExpr, scUMaxExpr, scSMaxExpr, 300f5efe56258f8cd6ceff4d7955a5d80144cd9cb0Dan Gohman scUnknown, 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; 403bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman SCEVConstant(const FoldingSetNodeIDRef ID, ConstantInt *v) : 413bf63768e574a2065de1aebba12f6c2e80f4fb16Dan 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 636e70e31810464289a9e9b37e0345847e3ca5d5cfDan Gohman bool properlyDominates(BasicBlock *BB, DominatorTree *DT) const { 646e70e31810464289a9e9b37e0345847e3ca5d5cfDan Gohman return true; 656e70e31810464289a9e9b37e0345847e3ca5d5cfDan Gohman } 666e70e31810464289a9e9b37e0345847e3ca5d5cfDan Gohman 67b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman virtual void print(raw_ostream &OS) const; 684950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 694950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 704950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEVConstant *S) { return true; } 714950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEV *S) { 724950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return S->getSCEVType() == scConstant; 734950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 744950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 754950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 764950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner //===--------------------------------------------------------------------===// 7784923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman /// SCEVCastExpr - This is the base class for unary cast operator classes. 784950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 7984923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman class SCEVCastExpr : public SCEV { 8084923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman protected: 810bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *Op; 824950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const Type *Ty; 8384923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman 843bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman SCEVCastExpr(const FoldingSetNodeIDRef ID, 85c050fd94c29e31414591e3a18aa20049e6b3a84fDan Gohman unsigned SCEVTy, const SCEV *op, const Type *ty); 8684923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman 874950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner public: 880bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getOperand() const { return Op; } 894950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual const Type *getType() const { return Ty; } 909769ab22265b313171d201b5928688524a01bd87Misha Brukman 914950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool isLoopInvariant(const Loop *L) const { 924950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return Op->isLoopInvariant(L); 934950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 944950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 954950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool hasComputableLoopEvolution(const Loop *L) const { 964950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return Op->hasComputableLoopEvolution(L); 974950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 984950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 99fef8bb24de86ff41d09a7787c6c52b058a853e39Dan Gohman virtual bool hasOperand(const SCEV *O) const { 100fef8bb24de86ff41d09a7787c6c52b058a853e39Dan Gohman return Op == O || Op->hasOperand(O); 101fef8bb24de86ff41d09a7787c6c52b058a853e39Dan Gohman } 102fef8bb24de86ff41d09a7787c6c52b058a853e39Dan Gohman 10384923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman virtual bool dominates(BasicBlock *BB, DominatorTree *DT) const; 10484923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman 1056e70e31810464289a9e9b37e0345847e3ca5d5cfDan Gohman virtual bool properlyDominates(BasicBlock *BB, DominatorTree *DT) const; 1066e70e31810464289a9e9b37e0345847e3ca5d5cfDan Gohman 10784923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman /// Methods for support type inquiry through isa, cast, and dyn_cast: 10884923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman static inline bool classof(const SCEVCastExpr *S) { return true; } 10984923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman static inline bool classof(const SCEV *S) { 11084923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman return S->getSCEVType() == scTruncate || 11184923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman S->getSCEVType() == scZeroExtend || 11284923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman S->getSCEVType() == scSignExtend; 11384923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman } 11484923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman }; 11584923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman 11684923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman //===--------------------------------------------------------------------===// 11784923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman /// SCEVTruncateExpr - This class represents a truncation of an integer value 11884923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman /// to a smaller integer value. 11984923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman /// 12084923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman class SCEVTruncateExpr : public SCEVCastExpr { 12184923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman friend class ScalarEvolution; 12284923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman 1233bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman SCEVTruncateExpr(const FoldingSetNodeIDRef ID, 124c050fd94c29e31414591e3a18aa20049e6b3a84fDan Gohman const SCEV *op, const Type *ty); 12584923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman 12684923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman public: 127b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman virtual void print(raw_ostream &OS) const; 1284950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 129ef0bedaba7c1466af4275e720a73f3421b9b5631Dan Gohman virtual bool hasComputableLoopEvolution(const Loop *QL) const { 130ef0bedaba7c1466af4275e720a73f3421b9b5631Dan Gohman // Not computable. A truncate of an addrec is always folded into 131ef0bedaba7c1466af4275e720a73f3421b9b5631Dan Gohman // the addrec. 132ef0bedaba7c1466af4275e720a73f3421b9b5631Dan Gohman return false; 133ef0bedaba7c1466af4275e720a73f3421b9b5631Dan Gohman } 134ef0bedaba7c1466af4275e720a73f3421b9b5631Dan Gohman 1354950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 1364950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEVTruncateExpr *S) { return true; } 1374950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEV *S) { 1384950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return S->getSCEVType() == scTruncate; 1394950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 1404950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 1414950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 1424950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner //===--------------------------------------------------------------------===// 1434950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// SCEVZeroExtendExpr - This class represents a zero extension of a small 1444950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// integer value to a larger integer value. 1454950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 14684923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman class SCEVZeroExtendExpr : public SCEVCastExpr { 147246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman friend class ScalarEvolution; 148246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman 1493bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman SCEVZeroExtendExpr(const FoldingSetNodeIDRef ID, 150c050fd94c29e31414591e3a18aa20049e6b3a84fDan Gohman const SCEV *op, const Type *ty); 1514950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 15284923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman public: 153b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman virtual void print(raw_ostream &OS) const; 1544950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 1554950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 1564950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEVZeroExtendExpr *S) { return true; } 1574950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEV *S) { 1584950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return S->getSCEVType() == scZeroExtend; 1594950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 1604950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 1614950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 162d19534add90a2a894af61523b830887097bb780bDan Gohman //===--------------------------------------------------------------------===// 163d19534add90a2a894af61523b830887097bb780bDan Gohman /// SCEVSignExtendExpr - This class represents a sign extension of a small 164d19534add90a2a894af61523b830887097bb780bDan Gohman /// integer value to a larger integer value. 165d19534add90a2a894af61523b830887097bb780bDan Gohman /// 16684923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman class SCEVSignExtendExpr : public SCEVCastExpr { 167246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman friend class ScalarEvolution; 168246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman 1693bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman SCEVSignExtendExpr(const FoldingSetNodeIDRef ID, 170c050fd94c29e31414591e3a18aa20049e6b3a84fDan Gohman const SCEV *op, const Type *ty); 171d19534add90a2a894af61523b830887097bb780bDan Gohman 17284923602fdc2a81957e5dee178d5737ad8e72f55Dan Gohman public: 173b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman virtual void print(raw_ostream &OS) const; 174d19534add90a2a894af61523b830887097bb780bDan Gohman 175d19534add90a2a894af61523b830887097bb780bDan Gohman /// Methods for support type inquiry through isa, cast, and dyn_cast: 176d19534add90a2a894af61523b830887097bb780bDan Gohman static inline bool classof(const SCEVSignExtendExpr *S) { return true; } 177d19534add90a2a894af61523b830887097bb780bDan Gohman static inline bool classof(const SCEV *S) { 178d19534add90a2a894af61523b830887097bb780bDan Gohman return S->getSCEVType() == scSignExtend; 179d19534add90a2a894af61523b830887097bb780bDan Gohman } 180d19534add90a2a894af61523b830887097bb780bDan Gohman }; 181d19534add90a2a894af61523b830887097bb780bDan Gohman 1824950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 183d9480d0f6875d8aa3a0d91942d24f0ee416b1ff1Dan Gohman //===--------------------------------------------------------------------===// 184d9480d0f6875d8aa3a0d91942d24f0ee416b1ff1Dan Gohman /// SCEVNAryExpr - This node is a base class providing common 185d9480d0f6875d8aa3a0d91942d24f0ee416b1ff1Dan Gohman /// functionality for n'ary operators. 186d9480d0f6875d8aa3a0d91942d24f0ee416b1ff1Dan Gohman /// 187ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman class SCEVNAryExpr : public SCEV { 188ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman protected: 189f9e64729afec646fe93b51417e66e552e8e630a4Dan Gohman // Since SCEVs are immutable, ScalarEvolution allocates operand 190f9e64729afec646fe93b51417e66e552e8e630a4Dan Gohman // arrays with its SCEVAllocator, so this class just needs a simple 191f9e64729afec646fe93b51417e66e552e8e630a4Dan Gohman // pointer rather than a more elaborate vector-like data structure. 192f9e64729afec646fe93b51417e66e552e8e630a4Dan Gohman // This also avoids the need for a non-trivial destructor. 193f9e64729afec646fe93b51417e66e552e8e630a4Dan Gohman const SCEV *const *Operands; 194f9e64729afec646fe93b51417e66e552e8e630a4Dan Gohman size_t NumOperands; 1954950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 1963bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman SCEVNAryExpr(const FoldingSetNodeIDRef ID, 197f9e64729afec646fe93b51417e66e552e8e630a4Dan Gohman enum SCEVTypes T, const SCEV *const *O, size_t N) 1983bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman : SCEV(ID, T), Operands(O), NumOperands(N) {} 1994950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2004950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner public: 201f9e64729afec646fe93b51417e66e552e8e630a4Dan Gohman size_t getNumOperands() const { return NumOperands; } 2020bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getOperand(unsigned i) const { 203f9e64729afec646fe93b51417e66e552e8e630a4Dan Gohman assert(i < NumOperands && "Operand index out of range!"); 2044950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return Operands[i]; 2054950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 2064950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 207f9e64729afec646fe93b51417e66e552e8e630a4Dan Gohman typedef const SCEV *const *op_iterator; 208f9e64729afec646fe93b51417e66e552e8e630a4Dan Gohman op_iterator op_begin() const { return Operands; } 209f9e64729afec646fe93b51417e66e552e8e630a4Dan Gohman op_iterator op_end() const { return Operands + NumOperands; } 2104950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2112f199f9952b9dd62b5a0d0f4350b8fa780ebb9ccDan Gohman virtual bool isLoopInvariant(const Loop *L) const; 2124950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 21339592233304acbbeea8c53bac2b6a822a63a4c4bDan Gohman // hasComputableLoopEvolution - N-ary expressions have computable loop 214803513b364e27d303285d396fd8ee5b32149962aChris Lattner // evolutions iff they have at least one operand that varies with the loop, 215803513b364e27d303285d396fd8ee5b32149962aChris Lattner // but that all varying operands are computable. 2162f199f9952b9dd62b5a0d0f4350b8fa780ebb9ccDan Gohman virtual bool hasComputableLoopEvolution(const Loop *L) const; 2174950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2182f199f9952b9dd62b5a0d0f4350b8fa780ebb9ccDan Gohman virtual bool hasOperand(const SCEV *O) const; 219fef8bb24de86ff41d09a7787c6c52b058a853e39Dan Gohman 220ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman bool dominates(BasicBlock *BB, DominatorTree *DT) const; 221ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman 2226e70e31810464289a9e9b37e0345847e3ca5d5cfDan Gohman bool properlyDominates(BasicBlock *BB, DominatorTree *DT) const; 2236e70e31810464289a9e9b37e0345847e3ca5d5cfDan Gohman 224ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman virtual const Type *getType() const { return getOperand(0)->getType(); } 225ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman 2263645b01002e7ac244c1f3d163e5e350df21d869dDan Gohman bool hasNoUnsignedWrap() const { return SubclassData & (1 << 0); } 2273645b01002e7ac244c1f3d163e5e350df21d869dDan Gohman void setHasNoUnsignedWrap(bool B) { 2283645b01002e7ac244c1f3d163e5e350df21d869dDan Gohman SubclassData = (SubclassData & ~(1 << 0)) | (B << 0); 2293645b01002e7ac244c1f3d163e5e350df21d869dDan Gohman } 2303645b01002e7ac244c1f3d163e5e350df21d869dDan Gohman bool hasNoSignedWrap() const { return SubclassData & (1 << 1); } 2313645b01002e7ac244c1f3d163e5e350df21d869dDan Gohman void setHasNoSignedWrap(bool B) { 2323645b01002e7ac244c1f3d163e5e350df21d869dDan Gohman SubclassData = (SubclassData & ~(1 << 1)) | (B << 1); 2333645b01002e7ac244c1f3d163e5e350df21d869dDan Gohman } 2343645b01002e7ac244c1f3d163e5e350df21d869dDan Gohman 235ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman /// Methods for support type inquiry through isa, cast, and dyn_cast: 236ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman static inline bool classof(const SCEVNAryExpr *S) { return true; } 237ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman static inline bool classof(const SCEV *S) { 238ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman return S->getSCEVType() == scAddExpr || 239ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman S->getSCEVType() == scMulExpr || 240ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman S->getSCEVType() == scSMaxExpr || 241ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman S->getSCEVType() == scUMaxExpr || 242ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman S->getSCEVType() == scAddRecExpr; 243ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman } 244ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman }; 245ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman 246ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman //===--------------------------------------------------------------------===// 247ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman /// SCEVCommutativeExpr - This node is the base class for n'ary commutative 248ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman /// operators. 249ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman /// 250ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman class SCEVCommutativeExpr : public SCEVNAryExpr { 251ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman protected: 2523bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman SCEVCommutativeExpr(const FoldingSetNodeIDRef ID, 253c93b4cff89d85a13d4eaf1551af9fab276b88450Dan Gohman enum SCEVTypes T, const SCEV *const *O, size_t N) 2543bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman : SCEVNAryExpr(ID, T, O, N) {} 255ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman 256ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman public: 2574950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual const char *getOperationStr() const = 0; 2584950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 259b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman virtual void print(raw_ostream &OS) const; 2604950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2614950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 2624950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEVCommutativeExpr *S) { return true; } 2634950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEV *S) { 2644950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return S->getSCEVType() == scAddExpr || 265c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky S->getSCEVType() == scMulExpr || 2663e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky S->getSCEVType() == scSMaxExpr || 2673e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky S->getSCEVType() == scUMaxExpr; 2684950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 2694950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 2704950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2714950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2724950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner //===--------------------------------------------------------------------===// 2734950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// SCEVAddExpr - This node represents an addition of some number of SCEVs. 2744950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 2754950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner class SCEVAddExpr : public SCEVCommutativeExpr { 276246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman friend class ScalarEvolution; 277246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman 2783bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman SCEVAddExpr(const FoldingSetNodeIDRef ID, 279f9e64729afec646fe93b51417e66e552e8e630a4Dan Gohman const SCEV *const *O, size_t N) 2803bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman : SCEVCommutativeExpr(ID, scAddExpr, O, N) { 2814950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 2824950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2834950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner public: 284ef0bedaba7c1466af4275e720a73f3421b9b5631Dan Gohman virtual bool hasComputableLoopEvolution(const Loop *QL) const { 285ef0bedaba7c1466af4275e720a73f3421b9b5631Dan Gohman // Not computable. An add of an addrec is always folded into the addrec 286ef0bedaba7c1466af4275e720a73f3421b9b5631Dan Gohman // if the other operands are loop-variant or loop-computable. 287ef0bedaba7c1466af4275e720a73f3421b9b5631Dan Gohman return false; 288ef0bedaba7c1466af4275e720a73f3421b9b5631Dan Gohman } 289ef0bedaba7c1466af4275e720a73f3421b9b5631Dan Gohman 2904950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual const char *getOperationStr() const { return " + "; } 2914950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 2922b98bd23cb0bfa0dc09e1bcaef83a0e606e6ec1aDan Gohman virtual const Type *getType() const { 2932b98bd23cb0bfa0dc09e1bcaef83a0e606e6ec1aDan Gohman // Use the type of the last operand, which is likely to be a pointer 2942b98bd23cb0bfa0dc09e1bcaef83a0e606e6ec1aDan Gohman // type, if there is one. This doesn't usually matter, but it can help 2952b98bd23cb0bfa0dc09e1bcaef83a0e606e6ec1aDan Gohman // reduce casts when the expressions are expanded. 2962b98bd23cb0bfa0dc09e1bcaef83a0e606e6ec1aDan Gohman return getOperand(getNumOperands() - 1)->getType(); 2972b98bd23cb0bfa0dc09e1bcaef83a0e606e6ec1aDan Gohman } 2982b98bd23cb0bfa0dc09e1bcaef83a0e606e6ec1aDan Gohman 2994950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 3004950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEVAddExpr *S) { return true; } 3014950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEV *S) { 3024950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return S->getSCEVType() == scAddExpr; 3034950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 3044950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 3054950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3064950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner //===--------------------------------------------------------------------===// 3074950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// SCEVMulExpr - This node represents multiplication of some number of SCEVs. 3084950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 3094950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner class SCEVMulExpr : public SCEVCommutativeExpr { 310246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman friend class ScalarEvolution; 311246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman 3123bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman SCEVMulExpr(const FoldingSetNodeIDRef ID, 313f9e64729afec646fe93b51417e66e552e8e630a4Dan Gohman const SCEV *const *O, size_t N) 3143bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman : SCEVCommutativeExpr(ID, scMulExpr, O, N) { 3154950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 3164950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3174950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner public: 318ef0bedaba7c1466af4275e720a73f3421b9b5631Dan Gohman virtual bool hasComputableLoopEvolution(const Loop *QL) const { 319ef0bedaba7c1466af4275e720a73f3421b9b5631Dan Gohman // Not computable. A mul of an addrec is always folded into the addrec 320ef0bedaba7c1466af4275e720a73f3421b9b5631Dan Gohman // if the other operands are loop-variant or loop-computable. 321ef0bedaba7c1466af4275e720a73f3421b9b5631Dan Gohman return false; 322ef0bedaba7c1466af4275e720a73f3421b9b5631Dan Gohman } 323ef0bedaba7c1466af4275e720a73f3421b9b5631Dan Gohman 3244950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual const char *getOperationStr() const { return " * "; } 3254950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3264950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 3274950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEVMulExpr *S) { return true; } 3284950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEV *S) { 3294950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return S->getSCEVType() == scMulExpr; 3304950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 3314950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 3324950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3334950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3344950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner //===--------------------------------------------------------------------===// 335e3320a1bcce3f6653e109cc86ee1011b0a61d808Wojciech Matyjewicz /// SCEVUDivExpr - This class represents a binary unsigned division operation. 3364950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 337e3320a1bcce3f6653e109cc86ee1011b0a61d808Wojciech Matyjewicz class SCEVUDivExpr : public SCEV { 338246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman friend class ScalarEvolution; 339246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman 3400bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *LHS; 3410bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *RHS; 3423bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman SCEVUDivExpr(const FoldingSetNodeIDRef ID, const SCEV *lhs, const SCEV *rhs) 3433bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman : SCEV(ID, scUDivExpr), LHS(lhs), RHS(rhs) {} 3444950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3454950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner public: 3460bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getLHS() const { return LHS; } 3470bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getRHS() const { return RHS; } 3484950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3494950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool isLoopInvariant(const Loop *L) const { 3504950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return LHS->isLoopInvariant(L) && RHS->isLoopInvariant(L); 3514950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 3524950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3534950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool hasComputableLoopEvolution(const Loop *L) const { 3544950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return LHS->hasComputableLoopEvolution(L) && 3554950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner RHS->hasComputableLoopEvolution(L); 3564950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 3574950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 358fef8bb24de86ff41d09a7787c6c52b058a853e39Dan Gohman virtual bool hasOperand(const SCEV *O) const { 359fef8bb24de86ff41d09a7787c6c52b058a853e39Dan Gohman return O == LHS || O == RHS || LHS->hasOperand(O) || RHS->hasOperand(O); 360afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner } 361afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner 3625a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng bool dominates(BasicBlock *BB, DominatorTree *DT) const; 363afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner 3646e70e31810464289a9e9b37e0345847e3ca5d5cfDan Gohman bool properlyDominates(BasicBlock *BB, DominatorTree *DT) const; 3656e70e31810464289a9e9b37e0345847e3ca5d5cfDan Gohman 3664950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual const Type *getType() const; 3674950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 368b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman void print(raw_ostream &OS) const; 3694950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3704950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 371e3320a1bcce3f6653e109cc86ee1011b0a61d808Wojciech Matyjewicz static inline bool classof(const SCEVUDivExpr *S) { return true; } 3724950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEV *S) { 373e3320a1bcce3f6653e109cc86ee1011b0a61d808Wojciech Matyjewicz return S->getSCEVType() == scUDivExpr; 3744950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 3754950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 3764950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3774950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3784950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner //===--------------------------------------------------------------------===// 3794950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// SCEVAddRecExpr - This node represents a polynomial recurrence on the trip 3801e59aa1332b67256dc0e76237eab7f6dd21a25b4Dan Gohman /// count of the specified loop. This is the primary focus of the 3811e59aa1332b67256dc0e76237eab7f6dd21a25b4Dan Gohman /// ScalarEvolution framework; all the other SCEV subclasses are mostly just 3821e59aa1332b67256dc0e76237eab7f6dd21a25b4Dan Gohman /// supporting infrastructure to allow SCEVAddRecExpr expressions to be 3831e59aa1332b67256dc0e76237eab7f6dd21a25b4Dan Gohman /// created and analyzed. 3844950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 3854950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// All operands of an AddRec are required to be loop invariant. 3864950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 387ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman class SCEVAddRecExpr : public SCEVNAryExpr { 388246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman friend class ScalarEvolution; 389246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman 3904950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const Loop *L; 3914950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 3923bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman SCEVAddRecExpr(const FoldingSetNodeIDRef ID, 393f9e64729afec646fe93b51417e66e552e8e630a4Dan Gohman const SCEV *const *O, size_t N, const Loop *l) 3943bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman : SCEVNAryExpr(ID, scAddRecExpr, O, N), L(l) { 395f9e64729afec646fe93b51417e66e552e8e630a4Dan Gohman for (size_t i = 0, e = NumOperands; i != e; ++i) 3964950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner assert(Operands[i]->isLoopInvariant(l) && 3974950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner "Operands of AddRec must be loop-invariant!"); 3984950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 3994950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 400ecb403a9d3a340009c266d05cfca2bd778c7b156Dan Gohman public: 4010bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getStart() const { return Operands[0]; } 4024950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner const Loop *getLoop() const { return L; } 4034950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4044950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// getStepRecurrence - This method constructs and returns the recurrence 4054950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// indicating how much this expression steps by. If this is a polynomial 4064950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// of degree N, it returns a chrec of degree N-1. 4070bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getStepRecurrence(ScalarEvolution &SE) const { 40817f1972c770dc18f5c7c3c95776b4d62ae9e121dDan Gohman if (isAffine()) return getOperand(1); 4090bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman return SE.getAddRecExpr(SmallVector<const SCEV *, 3>(op_begin()+1, 4100bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman op_end()), 411246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman getLoop()); 4124950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 4134950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4144950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool hasComputableLoopEvolution(const Loop *QL) const { 415c056baed8704bd715ee58e5dfe724c255e68abbdDan Gohman return L == QL; 4164950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 4174950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4184950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool isLoopInvariant(const Loop *QueryLoop) const; 4194950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 42039125d8ef94cbadccd7339d3344e114dedaab12cDan Gohman bool dominates(BasicBlock *BB, DominatorTree *DT) const; 42139125d8ef94cbadccd7339d3344e114dedaab12cDan Gohman 42239125d8ef94cbadccd7339d3344e114dedaab12cDan Gohman bool properlyDominates(BasicBlock *BB, DominatorTree *DT) const; 42339125d8ef94cbadccd7339d3344e114dedaab12cDan Gohman 4244950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// isAffine - Return true if this is an affine AddRec (i.e., it represents 4254950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// an expressions A+B*x where A and B are loop invariant values. 4264950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner bool isAffine() const { 4274950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner // We know that the start value is invariant. This expression is thus 4284950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner // affine iff the step is also invariant. 4294950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return getNumOperands() == 2; 4304950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 4314950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4324950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// isQuadratic - Return true if this is an quadratic AddRec (i.e., it 4334950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// represents an expressions A+B*x+C*x^2 where A, B and C are loop 4344950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// invariant values. This corresponds to an addrec of the form {L,+,M,+,N} 4354950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner bool isQuadratic() const { 4364950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return getNumOperands() == 3; 4374950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 4384950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4394950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// evaluateAtIteration - Return the value of this chain of recurrences at 4404950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// the specified iteration number. 4410bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const; 4424950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4434950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// getNumIterationsInRange - Return the number of iterations of this loop 4444950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// that produce values in the specified constant range. Another way of 4454950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// looking at this is that it returns the first iteration number where the 4464950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// value is not in the condition, thus computing the exit count. If the 4474950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// iteration count can't be computed, an instance of SCEVCouldNotCompute is 448eefdebe002ede066bf80859e72aec831cfd1d92dNick Lewycky /// returned. 4490bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *getNumIterationsInRange(ConstantRange Range, 450246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman ScalarEvolution &SE) const; 4514950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 452c050fd94c29e31414591e3a18aa20049e6b3a84fDan Gohman /// getPostIncExpr - Return an expression representing the value of 453c050fd94c29e31414591e3a18aa20049e6b3a84fDan Gohman /// this expression one iteration of the loop ahead. 454fef8bb24de86ff41d09a7787c6c52b058a853e39Dan Gohman const SCEVAddRecExpr *getPostIncExpr(ScalarEvolution &SE) const { 455fef8bb24de86ff41d09a7787c6c52b058a853e39Dan Gohman return cast<SCEVAddRecExpr>(SE.getAddExpr(this, getStepRecurrence(SE))); 456c050fd94c29e31414591e3a18aa20049e6b3a84fDan Gohman } 457c050fd94c29e31414591e3a18aa20049e6b3a84fDan Gohman 458b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman virtual void print(raw_ostream &OS) const; 4594950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 4604950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 4614950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEVAddRecExpr *S) { return true; } 4624950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEV *S) { 4634950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return S->getSCEVType() == scAddRecExpr; 4644950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 4654950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 4664950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 467c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky 468c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky //===--------------------------------------------------------------------===// 469c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky /// SCEVSMaxExpr - This class represents a signed maximum selection. 470c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky /// 471c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky class SCEVSMaxExpr : public SCEVCommutativeExpr { 472c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky friend class ScalarEvolution; 473c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky 4743bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman SCEVSMaxExpr(const FoldingSetNodeIDRef ID, 475f9e64729afec646fe93b51417e66e552e8e630a4Dan Gohman const SCEV *const *O, size_t N) 4763bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman : SCEVCommutativeExpr(ID, scSMaxExpr, O, N) { 4773645b01002e7ac244c1f3d163e5e350df21d869dDan Gohman // Max never overflows. 4783645b01002e7ac244c1f3d163e5e350df21d869dDan Gohman setHasNoUnsignedWrap(true); 4793645b01002e7ac244c1f3d163e5e350df21d869dDan Gohman setHasNoSignedWrap(true); 480c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky } 481c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky 482c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky public: 483c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky virtual const char *getOperationStr() const { return " smax "; } 484c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky 485c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky /// Methods for support type inquiry through isa, cast, and dyn_cast: 486c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky static inline bool classof(const SCEVSMaxExpr *S) { return true; } 487c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky static inline bool classof(const SCEV *S) { 488c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky return S->getSCEVType() == scSMaxExpr; 489c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky } 490c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky }; 491c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky 492c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky 4934950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner //===--------------------------------------------------------------------===// 4943e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky /// SCEVUMaxExpr - This class represents an unsigned maximum selection. 4953e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky /// 4963e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky class SCEVUMaxExpr : public SCEVCommutativeExpr { 4973e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky friend class ScalarEvolution; 4983e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky 4993bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman SCEVUMaxExpr(const FoldingSetNodeIDRef ID, 500f9e64729afec646fe93b51417e66e552e8e630a4Dan Gohman const SCEV *const *O, size_t N) 5013bf63768e574a2065de1aebba12f6c2e80f4fb16Dan Gohman : SCEVCommutativeExpr(ID, scUMaxExpr, O, N) { 5023645b01002e7ac244c1f3d163e5e350df21d869dDan Gohman // Max never overflows. 5033645b01002e7ac244c1f3d163e5e350df21d869dDan Gohman setHasNoUnsignedWrap(true); 5043645b01002e7ac244c1f3d163e5e350df21d869dDan Gohman setHasNoSignedWrap(true); 5053e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky } 5063e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky 5073e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky public: 5083e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky virtual const char *getOperationStr() const { return " umax "; } 5093e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky 5103e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky /// Methods for support type inquiry through isa, cast, and dyn_cast: 5113e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky static inline bool classof(const SCEVUMaxExpr *S) { return true; } 5123e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky static inline bool classof(const SCEV *S) { 5133e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky return S->getSCEVType() == scUMaxExpr; 5143e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky } 5153e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky }; 5163e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky 517c40f17b08774c2dcc5787fd83241e3c64ba82974Dan Gohman //===--------------------------------------------------------------------===// 5184950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// SCEVUnknown - This means that we are dealing with an entirely unknown SCEV 51975144f93eb7e4dbf22d308d21581ae255dd520c6Dan Gohman /// value, and only represent it as its LLVM Value. This is the "bottom" 5204950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// value for the analysis. 5214950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// 522ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman class SCEVUnknown : public SCEV, private CallbackVH { 523246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman friend class ScalarEvolution; 524246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman 525ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman // Implement CallbackVH. 526ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman virtual void deleted(); 527ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman virtual void allUsesReplacedWith(Value *New); 528ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman 529ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman /// SE - The parent ScalarEvolution value. This is used to update 530ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman /// the parent's maps when the value associated with a SCEVUnknown 531ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman /// is deleted or RAUW'd. 532ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman ScalarEvolution *SE; 533ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman 534ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman /// Next - The next pointer in the linked list of all 535ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman /// SCEVUnknown instances owned by a ScalarEvolution. 536ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman SCEVUnknown *Next; 537ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman 538ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman SCEVUnknown(const FoldingSetNodeIDRef ID, Value *V, 539ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman ScalarEvolution *se, SCEVUnknown *next) : 540ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman SCEV(ID, scUnknown), CallbackVH(V), SE(se), Next(next) {} 5411c34375f79b7786351c27ae45f0412cfdfa004edDan Gohman 542c050fd94c29e31414591e3a18aa20049e6b3a84fDan Gohman public: 543ab37f50838350e1104579fbd1f7c8820473485a5Dan Gohman Value *getValue() const { return getValPtr(); } 5444950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 5450f5efe56258f8cd6ceff4d7955a5d80144cd9cb0Dan Gohman /// isSizeOf, isAlignOf, isOffsetOf - Test whether this is a special 5460f5efe56258f8cd6ceff4d7955a5d80144cd9cb0Dan Gohman /// constant representing a type size, alignment, or field offset in 5470f5efe56258f8cd6ceff4d7955a5d80144cd9cb0Dan Gohman /// a target-independent manner, and hasn't happened to have been 5480f5efe56258f8cd6ceff4d7955a5d80144cd9cb0Dan Gohman /// folded with other operations into something unrecognizable. This 5490f5efe56258f8cd6ceff4d7955a5d80144cd9cb0Dan Gohman /// is mainly only useful for pretty-printing and other situations 5500f5efe56258f8cd6ceff4d7955a5d80144cd9cb0Dan Gohman /// where it isn't absolutely required for these to succeed. 5510f5efe56258f8cd6ceff4d7955a5d80144cd9cb0Dan Gohman bool isSizeOf(const Type *&AllocTy) const; 5520f5efe56258f8cd6ceff4d7955a5d80144cd9cb0Dan Gohman bool isAlignOf(const Type *&AllocTy) const; 5534f8eea82d8967cffa85b9df6c9255717b059009eDan Gohman bool isOffsetOf(const Type *&STy, Constant *&FieldNo) const; 5540f5efe56258f8cd6ceff4d7955a5d80144cd9cb0Dan Gohman 5554950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool isLoopInvariant(const Loop *L) const; 5564950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual bool hasComputableLoopEvolution(const Loop *QL) const { 5574950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return false; // not computable 5584950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 5594950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 560fef8bb24de86ff41d09a7787c6c52b058a853e39Dan Gohman virtual bool hasOperand(const SCEV *) const { 561fef8bb24de86ff41d09a7787c6c52b058a853e39Dan Gohman return false; 562afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner } 563afc0dc7184cf73ff7ac64e516284fbe0c7023ba4Chris Lattner 5645a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng bool dominates(BasicBlock *BB, DominatorTree *DT) const; 5655a6c1a840ad343c0ed2fa54a0edb50b61f828f0fEvan Cheng 5666e70e31810464289a9e9b37e0345847e3ca5d5cfDan Gohman bool properlyDominates(BasicBlock *BB, DominatorTree *DT) const; 5676e70e31810464289a9e9b37e0345847e3ca5d5cfDan Gohman 5684950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner virtual const Type *getType() const; 5694950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 570b7ef72963b2215ca23c27fa8ea777bada06994d0Dan Gohman virtual void print(raw_ostream &OS) const; 5714950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 5724950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner /// Methods for support type inquiry through isa, cast, and dyn_cast: 5734950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEVUnknown *S) { return true; } 5744950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner static inline bool classof(const SCEV *S) { 5754950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner return S->getSCEVType() == scUnknown; 5764950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner } 5774950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner }; 5782cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner 5792cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner /// SCEVVisitor - This class defines a simple visitor class that may be used 5802cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner /// for various SCEV analysis purposes. 5812cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner template<typename SC, typename RetVal=void> 5822cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner struct SCEVVisitor { 583890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman RetVal visit(const SCEV *S) { 5842cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner switch (S->getSCEVType()) { 5852cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner case scConstant: 586890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman return ((SC*)this)->visitConstant((const SCEVConstant*)S); 5872cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner case scTruncate: 588890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman return ((SC*)this)->visitTruncateExpr((const SCEVTruncateExpr*)S); 5892cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner case scZeroExtend: 590890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman return ((SC*)this)->visitZeroExtendExpr((const SCEVZeroExtendExpr*)S); 591d19534add90a2a894af61523b830887097bb780bDan Gohman case scSignExtend: 592890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman return ((SC*)this)->visitSignExtendExpr((const SCEVSignExtendExpr*)S); 5932cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner case scAddExpr: 594890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman return ((SC*)this)->visitAddExpr((const SCEVAddExpr*)S); 5952cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner case scMulExpr: 596890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman return ((SC*)this)->visitMulExpr((const SCEVMulExpr*)S); 597e3320a1bcce3f6653e109cc86ee1011b0a61d808Wojciech Matyjewicz case scUDivExpr: 598890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman return ((SC*)this)->visitUDivExpr((const SCEVUDivExpr*)S); 5992cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner case scAddRecExpr: 600890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman return ((SC*)this)->visitAddRecExpr((const SCEVAddRecExpr*)S); 601c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky case scSMaxExpr: 602890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman return ((SC*)this)->visitSMaxExpr((const SCEVSMaxExpr*)S); 6033e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky case scUMaxExpr: 604890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman return ((SC*)this)->visitUMaxExpr((const SCEVUMaxExpr*)S); 6052cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner case scUnknown: 606890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman return ((SC*)this)->visitUnknown((const SCEVUnknown*)S); 6072cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner case scCouldNotCompute: 608890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman return ((SC*)this)->visitCouldNotCompute((const SCEVCouldNotCompute*)S); 6092cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner default: 610c23197a26f34f559ea9797de51e187087c039c42Torok Edwin llvm_unreachable("Unknown SCEV type!"); 6112cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner } 6122cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner } 6132cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner 614890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman RetVal visitCouldNotCompute(const SCEVCouldNotCompute *S) { 615c23197a26f34f559ea9797de51e187087c039c42Torok Edwin llvm_unreachable("Invalid use of SCEVCouldNotCompute!"); 6162cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner return RetVal(); 6172cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner } 6182cdf0a7a32f08674562b0cf6b071b96b36421f87Chris Lattner }; 6194950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner} 6204950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner 6214950e88e0fa7c44c0b54e2f64ddf57415ed83d40Chris Lattner#endif 622