SelectionDAG.h revision 6765bfed31f06d7ed2f5a87248ffadc9dce10de4
1//===-- llvm/CodeGen/SelectionDAG.h - InstSelection DAG ---------*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by the LLVM research group and is distributed under 6// the University of Illinois Open Source License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file declares the SelectionDAG class, and transitively defines the 11// SDNode class and subclasses. 12// 13//===----------------------------------------------------------------------===// 14 15#ifndef LLVM_CODEGEN_SELECTIONDAG_H 16#define LLVM_CODEGEN_SELECTIONDAG_H 17 18#include "llvm/CodeGen/SelectionDAGNodes.h" 19#include <map> 20#include <string> // FIXME remove eventually, turning map into const char* map. 21 22namespace llvm { 23 class TargetLowering; 24 class TargetMachine; 25 class MachineFunction; 26 27/// SelectionDAG class - This is used to represent a portion of an LLVM function 28/// in a low-level Data Dependence DAG representation suitable for instruction 29/// selection. This DAG is constructed as the first step of instruction 30/// selection in order to allow implementation of machine specific optimizations 31/// and code simplifications. 32/// 33/// The representation used by the SelectionDAG is a target-independent 34/// representation, which has some similarities to the GCC RTL representation, 35/// but is significantly more simple, powerful, and is a graph form instead of a 36/// linear form. 37/// 38class SelectionDAG { 39 TargetLowering &TLI; 40 MachineFunction &MF; 41 42 // Root - The root of the entire DAG. EntryNode - The starting token. 43 SDOperand Root, EntryNode; 44 45 // AllNodes - All of the nodes in the DAG 46 std::vector<SDNode*> AllNodes; 47 48 // ValueNodes - track SrcValue nodes 49 std::map<std::pair<const Value*, int>, SDNode*> ValueNodes; 50 51public: 52 SelectionDAG(TargetLowering &tli, MachineFunction &mf) : TLI(tli), MF(mf) { 53 EntryNode = Root = getNode(ISD::EntryToken, MVT::Other); 54 } 55 ~SelectionDAG(); 56 57 MachineFunction &getMachineFunction() const { return MF; } 58 const TargetMachine &getTarget() const; 59 TargetLowering &getTargetLoweringInfo() const { return TLI; } 60 61 /// viewGraph - Pop up a ghostview window with the DAG rendered using 'dot'. 62 /// 63 void viewGraph(); 64 65 66 typedef std::vector<SDNode*>::const_iterator allnodes_iterator; 67 allnodes_iterator allnodes_begin() const { return AllNodes.begin(); } 68 allnodes_iterator allnodes_end() const { return AllNodes.end(); } 69 70 /// getRoot - Return the root tag of the SelectionDAG. 71 /// 72 const SDOperand &getRoot() const { return Root; } 73 74 /// getEntryNode - Return the token chain corresponding to the entry of the 75 /// function. 76 const SDOperand &getEntryNode() const { return EntryNode; } 77 78 /// setRoot - Set the current root tag of the SelectionDAG. 79 /// 80 const SDOperand &setRoot(SDOperand N) { return Root = N; } 81 82 /// Legalize - This transforms the SelectionDAG into a SelectionDAG that is 83 /// compatible with the target instruction selector, as indicated by the 84 /// TargetLowering object. 85 /// 86 /// Note that this is an involved process that may invalidate pointers into 87 /// the graph. 88 void Legalize(); 89 90 /// RemoveDeadNodes - This method deletes all unreachable nodes in the 91 /// SelectionDAG, including nodes (like loads) that have uses of their token 92 /// chain but no other uses and no side effect. If a node is passed in as an 93 /// argument, it is used as the seed for node deletion. 94 void RemoveDeadNodes(SDNode *N = 0); 95 96 SDOperand getConstant(uint64_t Val, MVT::ValueType VT); 97 SDOperand getConstantFP(double Val, MVT::ValueType VT); 98 SDOperand getGlobalAddress(const GlobalValue *GV, MVT::ValueType VT); 99 SDOperand getFrameIndex(int FI, MVT::ValueType VT); 100 SDOperand getConstantPool(unsigned CPIdx, MVT::ValueType VT); 101 SDOperand getBasicBlock(MachineBasicBlock *MBB); 102 SDOperand getExternalSymbol(const char *Sym, MVT::ValueType VT); 103 104 SDOperand getCopyToReg(SDOperand Chain, SDOperand N, unsigned Reg) { 105 // Note: these are auto-CSE'd because the caller doesn't make requests that 106 // could cause duplicates to occur. 107 SDNode *NN = new RegSDNode(ISD::CopyToReg, Chain, N, Reg); 108 NN->setValueTypes(MVT::Other); 109 AllNodes.push_back(NN); 110 return SDOperand(NN, 0); 111 } 112 113 SDOperand getCopyFromReg(unsigned Reg, MVT::ValueType VT, SDOperand Chain) { 114 // Note: These nodes are auto-CSE'd by the caller of this method. 115 SDNode *NN = new RegSDNode(ISD::CopyFromReg, Chain, Reg); 116 NN->setValueTypes(VT, MVT::Other); 117 AllNodes.push_back(NN); 118 return SDOperand(NN, 0); 119 } 120 121 SDOperand getImplicitDef(SDOperand Chain, unsigned Reg) { 122 // Note: These nodes are auto-CSE'd by the caller of this method. 123 SDNode *NN = new RegSDNode(ISD::ImplicitDef, Chain, Reg); 124 NN->setValueTypes(MVT::Other); 125 AllNodes.push_back(NN); 126 return SDOperand(NN, 0); 127 } 128 129 /// getCall - Note that this destroys the vector of RetVals passed in. 130 /// 131 SDNode *getCall(std::vector<MVT::ValueType> &RetVals, SDOperand Chain, 132 SDOperand Callee, bool isTailCall = false) { 133 SDNode *NN = new SDNode(isTailCall ? ISD::TAILCALL : ISD::CALL, Chain, 134 Callee); 135 NN->setValueTypes(RetVals); 136 AllNodes.push_back(NN); 137 return NN; 138 } 139 140 /// getCall - This is identical to the one above, and should be used for calls 141 /// where arguments are passed in physical registers. This destroys the 142 /// RetVals and ArgsInRegs vectors. 143 SDNode *getCall(std::vector<MVT::ValueType> &RetVals, SDOperand Chain, 144 SDOperand Callee, std::vector<SDOperand> &ArgsInRegs, 145 bool isTailCall = false) { 146 ArgsInRegs.insert(ArgsInRegs.begin(), Callee); 147 ArgsInRegs.insert(ArgsInRegs.begin(), Chain); 148 SDNode *NN = new SDNode(isTailCall ? ISD::TAILCALL : ISD::CALL, ArgsInRegs); 149 NN->setValueTypes(RetVals); 150 AllNodes.push_back(NN); 151 return NN; 152 } 153 154 155 SDOperand getSetCC(ISD::CondCode, MVT::ValueType VT, 156 SDOperand LHS, SDOperand RHS); 157 158 /// getZeroExtendInReg - Return the expression required to zero extend the Op 159 /// value assuming it was the smaller SrcTy value. 160 SDOperand getZeroExtendInReg(SDOperand Op, MVT::ValueType SrcTy); 161 162 /// getNode - Gets or creates the specified node. 163 /// 164 SDOperand getNode(unsigned Opcode, MVT::ValueType VT); 165 SDOperand getNode(unsigned Opcode, MVT::ValueType VT, SDOperand N); 166 SDOperand getNode(unsigned Opcode, MVT::ValueType VT, 167 SDOperand N1, SDOperand N2); 168 SDOperand getNode(unsigned Opcode, MVT::ValueType VT, 169 SDOperand N1, SDOperand N2, SDOperand N3); 170 SDOperand getNode(unsigned Opcode, MVT::ValueType VT, 171 SDOperand N1, SDOperand N2, SDOperand N3, SDOperand N4); 172 SDOperand getNode(unsigned Opcode, MVT::ValueType VT, 173 std::vector<SDOperand> &Children); 174 SDOperand getNode(unsigned Opcode, std::vector<MVT::ValueType> &ResultTys, 175 std::vector<SDOperand> &Ops); 176 177 // getNode - These versions take an extra value type for extending and 178 // truncating loads, stores, rounds, extends etc. 179 SDOperand getNode(unsigned Opcode, MVT::ValueType VT, SDOperand N1, 180 SDOperand N2, MVT::ValueType EVT); 181 SDOperand getNode(unsigned Opcode, MVT::ValueType VT, 182 SDOperand N, MVT::ValueType EVT); 183 SDOperand getNode(unsigned Opcode, MVT::ValueType VT, SDOperand N1, 184 SDOperand N2, SDOperand N3, MVT::ValueType EVT); 185 SDOperand getNode(unsigned Opcode, MVT::ValueType VT, SDOperand N1, 186 SDOperand N2, SDOperand N3, SDOperand N4, 187 MVT::ValueType EVT); 188 189 190 /// getLoad - Loads are not normal binary operators: their result type is not 191 /// determined by their operands, and they produce a value AND a token chain. 192 /// 193 SDOperand getLoad(MVT::ValueType VT, SDOperand Chain, SDOperand Ptr, 194 SDOperand SV); 195 196 // getSrcValue - construct a node to track a Value* through the backend 197 SDOperand getSrcValue(const Value* I, int offset = 0); 198 199 void replaceAllUsesWith(SDOperand Old, SDOperand New) { 200 assert(Old != New && "RAUW self!"); 201 assert(0 && "Unimplemented!"); 202 } 203 204 void dump() const; 205 206private: 207 void DeleteNodeIfDead(SDNode *N, void *NodeSet); 208 209 // Maps to auto-CSE operations. 210 std::map<std::pair<unsigned, std::pair<SDOperand, MVT::ValueType> >, 211 SDNode *> UnaryOps; 212 std::map<std::pair<unsigned, std::pair<SDOperand, SDOperand> >, 213 SDNode *> BinaryOps; 214 215 std::map<std::pair<std::pair<SDOperand, SDOperand>, 216 std::pair<ISD::CondCode, MVT::ValueType> >, 217 SetCCSDNode*> SetCCs; 218 219 std::map<std::pair<SDOperand, std::pair<SDOperand, MVT::ValueType> >, 220 SDNode *> Loads; 221 222 std::map<const GlobalValue*, SDNode*> GlobalValues; 223 std::map<std::pair<uint64_t, MVT::ValueType>, SDNode*> Constants; 224 std::map<std::pair<uint64_t, MVT::ValueType>, SDNode*> ConstantFPs; 225 std::map<int, SDNode*> FrameIndices; 226 std::map<unsigned, SDNode*> ConstantPoolIndices; 227 std::map<MachineBasicBlock *, SDNode*> BBNodes; 228 std::map<std::pair<unsigned, 229 std::pair<MVT::ValueType, std::vector<SDOperand> > >, 230 SDNode*> OneResultNodes; 231 std::map<std::pair<unsigned, 232 std::pair<std::vector<MVT::ValueType>, 233 std::vector<SDOperand> > >, 234 SDNode*> ArbitraryNodes; 235 236 std::map<std::string, SDNode*> ExternalSymbols; 237 struct EVTStruct { 238 unsigned Opcode; 239 MVT::ValueType VT, EVT; 240 std::vector<SDOperand> Ops; 241 bool operator<(const EVTStruct &RHS) const { 242 if (Opcode < RHS.Opcode) return true; 243 if (Opcode > RHS.Opcode) return false; 244 if (VT < RHS.VT) return true; 245 if (VT > RHS.VT) return false; 246 if (EVT < RHS.EVT) return true; 247 if (EVT > RHS.EVT) return false; 248 return Ops < RHS.Ops; 249 } 250 }; 251 std::map<EVTStruct, SDNode*> MVTSDNodes; 252}; 253 254template <> struct GraphTraits<SelectionDAG*> : public GraphTraits<SDNode*> { 255 typedef SelectionDAG::allnodes_iterator nodes_iterator; 256 static nodes_iterator nodes_begin(SelectionDAG *G) { 257 return G->allnodes_begin(); 258 } 259 static nodes_iterator nodes_end(SelectionDAG *G) { 260 return G->allnodes_end(); 261 } 262}; 263 264} 265 266#endif 267