SelectionDAG.h revision 26005b1b672aebd437edc561d381c5dd19a03ddb
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 getTargetConstant(uint64_t Val, MVT::ValueType VT); 98 SDOperand getConstantFP(double Val, MVT::ValueType VT); 99 SDOperand getGlobalAddress(const GlobalValue *GV, MVT::ValueType VT); 100 SDOperand getTargetGlobalAddress(const GlobalValue *GV, MVT::ValueType VT); 101 SDOperand getFrameIndex(int FI, MVT::ValueType VT); 102 SDOperand getTargetFrameIndex(int FI, MVT::ValueType VT); 103 SDOperand getConstantPool(Constant *C, MVT::ValueType VT); 104 SDOperand getTargetConstantPool(Constant *C, MVT::ValueType VT); 105 SDOperand getBasicBlock(MachineBasicBlock *MBB); 106 SDOperand getExternalSymbol(const char *Sym, MVT::ValueType VT); 107 SDOperand getValueType(MVT::ValueType); 108 SDOperand getRegister(unsigned Reg, MVT::ValueType VT); 109 110 SDOperand getCopyToReg(SDOperand Chain, unsigned Reg, SDOperand N) { 111 return getNode(ISD::CopyToReg, MVT::Other, Chain, 112 getRegister(Reg, N.getValueType()), N); 113 } 114 115 SDOperand getCopyFromReg(SDOperand Chain, unsigned Reg, MVT::ValueType VT) { 116 std::vector<MVT::ValueType> ResultTys; 117 ResultTys.push_back(VT); 118 ResultTys.push_back(MVT::Other); 119 std::vector<SDOperand> Ops; 120 Ops.push_back(Chain); 121 Ops.push_back(getRegister(Reg, VT)); 122 return getNode(ISD::CopyFromReg, ResultTys, Ops); 123 } 124 125 SDOperand getImplicitDef(SDOperand Chain, unsigned Reg, MVT::ValueType VT) { 126 return getNode(ISD::ImplicitDef, MVT::Other, Chain, getRegister(Reg, VT)); 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 SDOperand getCondCode(ISD::CondCode Cond); 155 156 /// getZeroExtendInReg - Return the expression required to zero extend the Op 157 /// value assuming it was the smaller SrcTy value. 158 SDOperand getZeroExtendInReg(SDOperand Op, MVT::ValueType SrcTy); 159 160 /// getNode - Gets or creates the specified node. 161 /// 162 SDOperand getNode(unsigned Opcode, MVT::ValueType VT); 163 SDOperand getNode(unsigned Opcode, MVT::ValueType VT, SDOperand N); 164 SDOperand getNode(unsigned Opcode, MVT::ValueType VT, 165 SDOperand N1, SDOperand N2); 166 SDOperand getNode(unsigned Opcode, MVT::ValueType VT, 167 SDOperand N1, SDOperand N2, SDOperand N3); 168 SDOperand getNode(unsigned Opcode, MVT::ValueType VT, 169 SDOperand N1, SDOperand N2, SDOperand N3, SDOperand N4); 170 SDOperand getNode(unsigned Opcode, MVT::ValueType VT, 171 SDOperand N1, SDOperand N2, SDOperand N3, SDOperand N4, 172 SDOperand N5); 173 SDOperand getNode(unsigned Opcode, MVT::ValueType VT, 174 std::vector<SDOperand> &Children); 175 SDOperand getNode(unsigned Opcode, std::vector<MVT::ValueType> &ResultTys, 176 std::vector<SDOperand> &Ops); 177 178 /// getSetCC - Helper function to make it easier to build SetCC's if you just 179 /// have an ISD::CondCode instead of an SDOperand. 180 /// 181 SDOperand getSetCC(MVT::ValueType VT, SDOperand LHS, SDOperand RHS, 182 ISD::CondCode Cond) { 183 return getNode(ISD::SETCC, VT, LHS, RHS, getCondCode(Cond)); 184 } 185 186 /// getSelectCC - Helper function to make it easier to build SelectCC's if you 187 /// just have an ISD::CondCode instead of an SDOperand. 188 /// 189 SDOperand getSelectCC(SDOperand LHS, SDOperand RHS, 190 SDOperand True, SDOperand False, ISD::CondCode Cond) { 191 MVT::ValueType VT = True.getValueType(); 192 return getNode(ISD::SELECT_CC, VT, LHS, RHS, True, False,getCondCode(Cond)); 193 } 194 195 /// getBR2Way_CC - Helper function to make it easier to build BRTWOWAY_CC 196 /// nodes. 197 /// 198 SDOperand getBR2Way_CC(SDOperand Chain, SDOperand CCNode, SDOperand LHS, 199 SDOperand RHS, SDOperand True, SDOperand False) { 200 std::vector<SDOperand> Ops; 201 Ops.push_back(Chain); 202 Ops.push_back(CCNode); 203 Ops.push_back(LHS); 204 Ops.push_back(RHS); 205 Ops.push_back(True); 206 Ops.push_back(False); 207 return getNode(ISD::BRTWOWAY_CC, MVT::Other, Ops); 208 } 209 210 /// getLoad - Loads are not normal binary operators: their result type is not 211 /// determined by their operands, and they produce a value AND a token chain. 212 /// 213 SDOperand getLoad(MVT::ValueType VT, SDOperand Chain, SDOperand Ptr, 214 SDOperand SV); 215 SDOperand getExtLoad(unsigned Opcode, MVT::ValueType VT, SDOperand Chain, 216 SDOperand Ptr, SDOperand SV, MVT::ValueType EVT); 217 218 // getSrcValue - construct a node to track a Value* through the backend 219 SDOperand getSrcValue(const Value* I, int offset = 0); 220 221 222 /// SelectNodeTo - These are used for target selectors to *mutate* the 223 /// specified node to have the specified return type, Target opcode, and 224 /// operands. Note that target opcodes are stored as 225 /// ISD::BUILTIN_OP_END+TargetOpcode in the node opcode field. 226 void SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT); 227 void SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT, 228 SDOperand Op1); 229 void SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT, 230 SDOperand Op1, SDOperand Op2); 231 void SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT, 232 SDOperand Op1, SDOperand Op2, SDOperand Op3); 233 void SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT, 234 SDOperand Op1, SDOperand Op2, SDOperand Op3, SDOperand Op4); 235 void SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT, 236 SDOperand Op1, SDOperand Op2, SDOperand Op3, SDOperand Op4, 237 SDOperand Op5); 238 void SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT1, 239 MVT::ValueType VT2, SDOperand Op1, SDOperand Op2); 240 void SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT1, 241 MVT::ValueType VT2, SDOperand Op1, SDOperand Op2, 242 SDOperand Op3); 243 244 SDOperand getTargetNode(unsigned Opcode, MVT::ValueType VT, 245 SDOperand Op1) { 246 return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1); 247 } 248 SDOperand getTargetNode(unsigned Opcode, MVT::ValueType VT, 249 SDOperand Op1, SDOperand Op2) { 250 return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1, Op2); 251 } 252 SDOperand getTargetNode(unsigned Opcode, MVT::ValueType VT1, 253 MVT::ValueType VT2, SDOperand Op1, SDOperand Op2) { 254 std::vector<MVT::ValueType> ResultTys; 255 ResultTys.push_back(VT1); 256 ResultTys.push_back(VT2); 257 std::vector<SDOperand> Ops; 258 Ops.push_back(Op1); 259 Ops.push_back(Op2); 260 return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops); 261 } 262 SDOperand getTargetNode(unsigned Opcode, MVT::ValueType VT, 263 SDOperand Op1, SDOperand Op2, SDOperand Op3) { 264 return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1, Op2, Op3); 265 } 266 SDOperand getTargetNode(unsigned Opcode, MVT::ValueType VT, 267 SDOperand Op1, SDOperand Op2, SDOperand Op3, 268 SDOperand Op4) { 269 return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1, Op2, Op3, Op4); 270 } 271 SDOperand getTargetNode(unsigned Opcode, MVT::ValueType VT, 272 SDOperand Op1, SDOperand Op2, SDOperand Op3, 273 SDOperand Op4, SDOperand Op5) { 274 return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1, Op2, Op3, Op4, Op5); 275 } 276 SDOperand getTargetNode(unsigned Opcode, MVT::ValueType VT, 277 std::vector<SDOperand> &Ops) { 278 return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Ops); 279 } 280 281 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead. 282 /// This can cause recursive merging of nodes in the DAG. Use the first 283 /// version if 'From' is known to have a single result, use the second 284 /// if you have two nodes with identical results, use the third otherwise. 285 /// 286 void ReplaceAllUsesWith(SDOperand From, SDOperand Op); 287 void ReplaceAllUsesWith(SDNode *From, SDNode *To); 288 void ReplaceAllUsesWith(SDNode *From, const std::vector<SDOperand> &To); 289 290 void dump() const; 291 292private: 293 void RemoveNodeFromCSEMaps(SDNode *N); 294 SDNode *AddNonLeafNodeToCSEMaps(SDNode *N); 295 void DeleteNodeIfDead(SDNode *N, void *NodeSet); 296 297 /// SimplifySetCC - Try to simplify a setcc built with the specified operands 298 /// and cc. If unable to simplify it, return a null SDOperand. 299 SDOperand SimplifySetCC(MVT::ValueType VT, SDOperand N1, 300 SDOperand N2, ISD::CondCode Cond); 301 302 /// SimplifySelectCC - Try to simplify a select_cc built with the specified 303 /// operands and cc. This can be used to simplify both the select_cc node, 304 /// and a select node whose first operand is a setcc. 305 SDOperand SimplifySelectCC(SDOperand N1, SDOperand N2, SDOperand N3, 306 SDOperand N4, ISD::CondCode CC); 307 308 // Maps to auto-CSE operations. 309 std::map<std::pair<unsigned, std::pair<SDOperand, MVT::ValueType> >, 310 SDNode *> UnaryOps; 311 std::map<std::pair<unsigned, std::pair<SDOperand, SDOperand> >, 312 SDNode *> BinaryOps; 313 314 std::vector<RegisterSDNode*> RegNodes; 315 std::vector<CondCodeSDNode*> CondCodeNodes; 316 317 std::map<std::pair<SDOperand, std::pair<SDOperand, MVT::ValueType> >, 318 SDNode *> Loads; 319 320 std::map<const GlobalValue*, SDNode*> GlobalValues; 321 std::map<const GlobalValue*, SDNode*> TargetGlobalValues; 322 std::map<std::pair<uint64_t, MVT::ValueType>, SDNode*> Constants; 323 std::map<std::pair<uint64_t, MVT::ValueType>, SDNode*> TargetConstants; 324 std::map<std::pair<uint64_t, MVT::ValueType>, SDNode*> ConstantFPs; 325 std::map<int, SDNode*> FrameIndices, TargetFrameIndices; 326 std::map<Constant *, SDNode*> ConstantPoolIndices; 327 std::map<Constant *, SDNode*> TargetConstantPoolIndices; 328 std::map<MachineBasicBlock *, SDNode*> BBNodes; 329 std::vector<SDNode*> ValueTypeNodes; 330 std::map<std::string, SDNode*> ExternalSymbols; 331 std::map<std::pair<unsigned, 332 std::pair<MVT::ValueType, std::vector<SDOperand> > >, 333 SDNode*> OneResultNodes; 334 std::map<std::pair<unsigned, 335 std::pair<std::vector<MVT::ValueType>, 336 std::vector<SDOperand> > >, 337 SDNode*> ArbitraryNodes; 338}; 339 340template <> struct GraphTraits<SelectionDAG*> : public GraphTraits<SDNode*> { 341 typedef SelectionDAG::allnodes_iterator nodes_iterator; 342 static nodes_iterator nodes_begin(SelectionDAG *G) { 343 return G->allnodes_begin(); 344 } 345 static nodes_iterator nodes_end(SelectionDAG *G) { 346 return G->allnodes_end(); 347 } 348}; 349 350} 351 352#endif 353