SelectionDAG.h revision 583bd47f777fe3eb8305872fa0eadab31e833dff
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/ADT/FoldingSet.h" 19#include "llvm/ADT/ilist" 20#include "llvm/CodeGen/SelectionDAGNodes.h" 21 22#include <list> 23#include <vector> 24#include <map> 25#include <set> 26#include <string> 27 28namespace llvm { 29 class AliasAnalysis; 30 class TargetLowering; 31 class TargetMachine; 32 class MachineDebugInfo; 33 class MachineFunction; 34 class MachineConstantPoolValue; 35 class SDOperand; 36 37/// SelectionDAG class - This is used to represent a portion of an LLVM function 38/// in a low-level Data Dependence DAG representation suitable for instruction 39/// selection. This DAG is constructed as the first step of instruction 40/// selection in order to allow implementation of machine specific optimizations 41/// and code simplifications. 42/// 43/// The representation used by the SelectionDAG is a target-independent 44/// representation, which has some similarities to the GCC RTL representation, 45/// but is significantly more simple, powerful, and is a graph form instead of a 46/// linear form. 47/// 48class SelectionDAG { 49 TargetLowering &TLI; 50 MachineFunction &MF; 51 MachineDebugInfo *DI; 52 53 /// Root - The root of the entire DAG. EntryNode - The starting token. 54 SDOperand Root, EntryNode; 55 56 /// AllNodes - A linked list of nodes in the current DAG. 57 ilist<SDNode> AllNodes; 58 59 /// CSEMap - This structure is used to memoize nodes, automatically performing 60 /// CSE with existing nodes with a duplicate is requested. 61 FoldingSet<SDNode> CSEMap; 62 63public: 64 SelectionDAG(TargetLowering &tli, MachineFunction &mf, MachineDebugInfo *di) 65 : TLI(tli), MF(mf), DI(di) { 66 EntryNode = Root = getNode(ISD::EntryToken, MVT::Other); 67 } 68 ~SelectionDAG(); 69 70 MachineFunction &getMachineFunction() const { return MF; } 71 const TargetMachine &getTarget() const; 72 TargetLowering &getTargetLoweringInfo() const { return TLI; } 73 MachineDebugInfo *getMachineDebugInfo() const { return DI; } 74 75 /// viewGraph - Pop up a GraphViz/gv window with the DAG rendered using 'dot'. 76 /// 77 void viewGraph(); 78 79#ifndef NDEBUG 80 std::map<const SDNode *, std::string> NodeGraphAttrs; 81#endif 82 83 /// clearGraphAttrs - Clear all previously defined node graph attributes. 84 /// Intended to be used from a debugging tool (eg. gdb). 85 void clearGraphAttrs(); 86 87 /// setGraphAttrs - Set graph attributes for a node. (eg. "color=red".) 88 /// 89 void setGraphAttrs(const SDNode *N, const char *Attrs); 90 91 /// getGraphAttrs - Get graph attributes for a node. (eg. "color=red".) 92 /// Used from getNodeAttributes. 93 const std::string getGraphAttrs(const SDNode *N) const; 94 95 /// setGraphColor - Convenience for setting node color attribute. 96 /// 97 void setGraphColor(const SDNode *N, const char *Color); 98 99 typedef ilist<SDNode>::const_iterator allnodes_const_iterator; 100 allnodes_const_iterator allnodes_begin() const { return AllNodes.begin(); } 101 allnodes_const_iterator allnodes_end() const { return AllNodes.end(); } 102 typedef ilist<SDNode>::iterator allnodes_iterator; 103 allnodes_iterator allnodes_begin() { return AllNodes.begin(); } 104 allnodes_iterator allnodes_end() { return AllNodes.end(); } 105 106 /// getRoot - Return the root tag of the SelectionDAG. 107 /// 108 const SDOperand &getRoot() const { return Root; } 109 110 /// getEntryNode - Return the token chain corresponding to the entry of the 111 /// function. 112 const SDOperand &getEntryNode() const { return EntryNode; } 113 114 /// setRoot - Set the current root tag of the SelectionDAG. 115 /// 116 const SDOperand &setRoot(SDOperand N) { return Root = N; } 117 118 /// Combine - This iterates over the nodes in the SelectionDAG, folding 119 /// certain types of nodes together, or eliminating superfluous nodes. When 120 /// the AfterLegalize argument is set to 'true', Combine takes care not to 121 /// generate any nodes that will be illegal on the target. 122 void Combine(bool AfterLegalize, AliasAnalysis &AA); 123 124 /// Legalize - This transforms the SelectionDAG into a SelectionDAG that is 125 /// compatible with the target instruction selector, as indicated by the 126 /// TargetLowering object. 127 /// 128 /// Note that this is an involved process that may invalidate pointers into 129 /// the graph. 130 void Legalize(); 131 132 /// RemoveDeadNodes - This method deletes all unreachable nodes in the 133 /// SelectionDAG. 134 void RemoveDeadNodes(); 135 136 /// RemoveDeadNode - Remove the specified node from the system. If any of its 137 /// operands then becomes dead, remove them as well. The vector Deleted is 138 /// populated with nodes that are deleted. 139 void RemoveDeadNode(SDNode *N, std::vector<SDNode*> &Deleted); 140 141 /// DeleteNode - Remove the specified node from the system. This node must 142 /// have no referrers. 143 void DeleteNode(SDNode *N); 144 145 /// getVTList - Return an SDVTList that represents the list of values 146 /// specified. 147 SDVTList getVTList(MVT::ValueType VT); 148 SDVTList getVTList(MVT::ValueType VT1, MVT::ValueType VT2); 149 SDVTList getVTList(MVT::ValueType VT1, MVT::ValueType VT2,MVT::ValueType VT3); 150 SDVTList getVTList(const MVT::ValueType *VTs, unsigned NumVTs); 151 152 /// getNodeValueTypes - These are obsolete, use getVTList instead. 153 const MVT::ValueType *getNodeValueTypes(MVT::ValueType VT) { 154 return getVTList(VT).VTs; 155 } 156 const MVT::ValueType *getNodeValueTypes(MVT::ValueType VT1, 157 MVT::ValueType VT2) { 158 return getVTList(VT1, VT2).VTs; 159 } 160 const MVT::ValueType *getNodeValueTypes(MVT::ValueType VT1,MVT::ValueType VT2, 161 MVT::ValueType VT3) { 162 return getVTList(VT1, VT2, VT3).VTs; 163 } 164 const MVT::ValueType *getNodeValueTypes(std::vector<MVT::ValueType> &VTList) { 165 return getVTList(&VTList[0], VTList.size()).VTs; 166 } 167 168 169 //===--------------------------------------------------------------------===// 170 // Node creation methods. 171 // 172 SDOperand getString(const std::string &Val); 173 SDOperand getConstant(uint64_t Val, MVT::ValueType VT, bool isTarget = false); 174 SDOperand getTargetConstant(uint64_t Val, MVT::ValueType VT) { 175 return getConstant(Val, VT, true); 176 } 177 SDOperand getConstantFP(double Val, MVT::ValueType VT, bool isTarget = false); 178 SDOperand getTargetConstantFP(double Val, MVT::ValueType VT) { 179 return getConstantFP(Val, VT, true); 180 } 181 SDOperand getGlobalAddress(const GlobalValue *GV, MVT::ValueType VT, 182 int offset = 0, bool isTargetGA = false); 183 SDOperand getTargetGlobalAddress(const GlobalValue *GV, MVT::ValueType VT, 184 int offset = 0) { 185 return getGlobalAddress(GV, VT, offset, true); 186 } 187 SDOperand getFrameIndex(int FI, MVT::ValueType VT, bool isTarget = false); 188 SDOperand getTargetFrameIndex(int FI, MVT::ValueType VT) { 189 return getFrameIndex(FI, VT, true); 190 } 191 SDOperand getJumpTable(int JTI, MVT::ValueType VT, bool isTarget = false); 192 SDOperand getTargetJumpTable(int JTI, MVT::ValueType VT) { 193 return getJumpTable(JTI, VT, true); 194 } 195 SDOperand getConstantPool(Constant *C, MVT::ValueType VT, 196 unsigned Align = 0, int Offs = 0, bool isT=false); 197 SDOperand getTargetConstantPool(Constant *C, MVT::ValueType VT, 198 unsigned Align = 0, int Offset = 0) { 199 return getConstantPool(C, VT, Align, Offset, true); 200 } 201 SDOperand getConstantPool(MachineConstantPoolValue *C, MVT::ValueType VT, 202 unsigned Align = 0, int Offs = 0, bool isT=false); 203 SDOperand getTargetConstantPool(MachineConstantPoolValue *C, 204 MVT::ValueType VT, unsigned Align = 0, 205 int Offset = 0) { 206 return getConstantPool(C, VT, Align, Offset, true); 207 } 208 SDOperand getBasicBlock(MachineBasicBlock *MBB); 209 SDOperand getExternalSymbol(const char *Sym, MVT::ValueType VT); 210 SDOperand getTargetExternalSymbol(const char *Sym, MVT::ValueType VT); 211 SDOperand getValueType(MVT::ValueType); 212 SDOperand getRegister(unsigned Reg, MVT::ValueType VT); 213 214 SDOperand getCopyToReg(SDOperand Chain, unsigned Reg, SDOperand N) { 215 return getNode(ISD::CopyToReg, MVT::Other, Chain, 216 getRegister(Reg, N.getValueType()), N); 217 } 218 219 // This version of the getCopyToReg method takes an extra operand, which 220 // indicates that there is potentially an incoming flag value (if Flag is not 221 // null) and that there should be a flag result. 222 SDOperand getCopyToReg(SDOperand Chain, unsigned Reg, SDOperand N, 223 SDOperand Flag) { 224 const MVT::ValueType *VTs = getNodeValueTypes(MVT::Other, MVT::Flag); 225 SDOperand Ops[] = { Chain, getRegister(Reg, N.getValueType()), N, Flag }; 226 return getNode(ISD::CopyToReg, VTs, 2, Ops, Flag.Val ? 4 : 3); 227 } 228 229 // Similar to last getCopyToReg() except parameter Reg is a SDOperand 230 SDOperand getCopyToReg(SDOperand Chain, SDOperand Reg, SDOperand N, 231 SDOperand Flag) { 232 const MVT::ValueType *VTs = getNodeValueTypes(MVT::Other, MVT::Flag); 233 SDOperand Ops[] = { Chain, Reg, N, Flag }; 234 return getNode(ISD::CopyToReg, VTs, 2, Ops, Flag.Val ? 4 : 3); 235 } 236 237 SDOperand getCopyFromReg(SDOperand Chain, unsigned Reg, MVT::ValueType VT) { 238 const MVT::ValueType *VTs = getNodeValueTypes(VT, MVT::Other); 239 SDOperand Ops[] = { Chain, getRegister(Reg, VT) }; 240 return getNode(ISD::CopyFromReg, VTs, 2, Ops, 2); 241 } 242 243 // This version of the getCopyFromReg method takes an extra operand, which 244 // indicates that there is potentially an incoming flag value (if Flag is not 245 // null) and that there should be a flag result. 246 SDOperand getCopyFromReg(SDOperand Chain, unsigned Reg, MVT::ValueType VT, 247 SDOperand Flag) { 248 const MVT::ValueType *VTs = getNodeValueTypes(VT, MVT::Other, MVT::Flag); 249 SDOperand Ops[] = { Chain, getRegister(Reg, VT), Flag }; 250 return getNode(ISD::CopyFromReg, VTs, 3, Ops, Flag.Val ? 3 : 2); 251 } 252 253 SDOperand getCondCode(ISD::CondCode Cond); 254 255 /// getZeroExtendInReg - Return the expression required to zero extend the Op 256 /// value assuming it was the smaller SrcTy value. 257 SDOperand getZeroExtendInReg(SDOperand Op, MVT::ValueType SrcTy); 258 259 /// getCALLSEQ_START - Return a new CALLSEQ_START node, which always must have 260 /// a flag result (to ensure it's not CSE'd). 261 SDOperand getCALLSEQ_START(SDOperand Chain, SDOperand Op) { 262 const MVT::ValueType *VTs = getNodeValueTypes(MVT::Other, MVT::Flag); 263 SDOperand Ops[] = { Chain, Op }; 264 return getNode(ISD::CALLSEQ_START, VTs, 2, Ops, 2); 265 } 266 267 /// getNode - Gets or creates the specified node. 268 /// 269 SDOperand getNode(unsigned Opcode, MVT::ValueType VT); 270 SDOperand getNode(unsigned Opcode, MVT::ValueType VT, SDOperand N); 271 SDOperand getNode(unsigned Opcode, MVT::ValueType VT, 272 SDOperand N1, SDOperand N2); 273 SDOperand getNode(unsigned Opcode, MVT::ValueType VT, 274 SDOperand N1, SDOperand N2, SDOperand N3); 275 SDOperand getNode(unsigned Opcode, MVT::ValueType VT, 276 SDOperand N1, SDOperand N2, SDOperand N3, SDOperand N4); 277 SDOperand getNode(unsigned Opcode, MVT::ValueType VT, 278 SDOperand N1, SDOperand N2, SDOperand N3, SDOperand N4, 279 SDOperand N5); 280 SDOperand getNode(unsigned Opcode, MVT::ValueType VT, 281 const SDOperand *Ops, unsigned NumOps); 282 SDOperand getNode(unsigned Opcode, std::vector<MVT::ValueType> &ResultTys, 283 const SDOperand *Ops, unsigned NumOps); 284 SDOperand getNode(unsigned Opcode, const MVT::ValueType *VTs, unsigned NumVTs, 285 const SDOperand *Ops, unsigned NumOps); 286 SDOperand getNode(unsigned Opcode, SDVTList VTs, 287 const SDOperand *Ops, unsigned NumOps); 288 289 /// getSetCC - Helper function to make it easier to build SetCC's if you just 290 /// have an ISD::CondCode instead of an SDOperand. 291 /// 292 SDOperand getSetCC(MVT::ValueType VT, SDOperand LHS, SDOperand RHS, 293 ISD::CondCode Cond) { 294 return getNode(ISD::SETCC, VT, LHS, RHS, getCondCode(Cond)); 295 } 296 297 /// getSelectCC - Helper function to make it easier to build SelectCC's if you 298 /// just have an ISD::CondCode instead of an SDOperand. 299 /// 300 SDOperand getSelectCC(SDOperand LHS, SDOperand RHS, 301 SDOperand True, SDOperand False, ISD::CondCode Cond) { 302 return getNode(ISD::SELECT_CC, True.getValueType(), LHS, RHS, True, False, 303 getCondCode(Cond)); 304 } 305 306 /// getVAArg - VAArg produces a result and token chain, and takes a pointer 307 /// and a source value as input. 308 SDOperand getVAArg(MVT::ValueType VT, SDOperand Chain, SDOperand Ptr, 309 SDOperand SV); 310 311 /// getLoad - Loads are not normal binary operators: their result type is not 312 /// determined by their operands, and they produce a value AND a token chain. 313 /// 314 SDOperand getLoad(MVT::ValueType VT, SDOperand Chain, SDOperand Ptr, 315 const Value *SV, int SVOffset, bool isVolatile=false); 316 SDOperand getExtLoad(ISD::LoadExtType ExtType, MVT::ValueType VT, 317 SDOperand Chain, SDOperand Ptr, const Value *SV, 318 int SVOffset, MVT::ValueType EVT, bool isVolatile=false); 319 SDOperand getIndexedLoad(SDOperand OrigLoad, SDOperand Base, 320 SDOperand Offset, ISD::MemOpAddrMode AM); 321 SDOperand getVecLoad(unsigned Count, MVT::ValueType VT, SDOperand Chain, 322 SDOperand Ptr, SDOperand SV); 323 324 /// getStore - Helper function to build ISD::STORE nodes. 325 /// 326 SDOperand getStore(SDOperand Chain, SDOperand Value, SDOperand Ptr, 327 const Value *SV, int SVOffset, bool isVolatile=false); 328 SDOperand getTruncStore(SDOperand Chain, SDOperand Value, SDOperand Ptr, 329 const Value *SV, int SVOffset, MVT::ValueType TVT, 330 bool isVolatile=false); 331 332 // getSrcValue - construct a node to track a Value* through the backend 333 SDOperand getSrcValue(const Value* I, int offset = 0); 334 335 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the 336 /// specified operands. If the resultant node already exists in the DAG, 337 /// this does not modify the specified node, instead it returns the node that 338 /// already exists. If the resultant node does not exist in the DAG, the 339 /// input node is returned. As a degenerate case, if you specify the same 340 /// input operands as the node already has, the input node is returned. 341 SDOperand UpdateNodeOperands(SDOperand N, SDOperand Op); 342 SDOperand UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2); 343 SDOperand UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2, 344 SDOperand Op3); 345 SDOperand UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2, 346 SDOperand Op3, SDOperand Op4); 347 SDOperand UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2, 348 SDOperand Op3, SDOperand Op4, SDOperand Op5); 349 SDOperand UpdateNodeOperands(SDOperand N, SDOperand *Ops, unsigned NumOps); 350 351 /// SelectNodeTo - These are used for target selectors to *mutate* the 352 /// specified node to have the specified return type, Target opcode, and 353 /// operands. Note that target opcodes are stored as 354 /// ISD::BUILTIN_OP_END+TargetOpcode in the node opcode field. The 0th value 355 /// of the resultant node is returned. 356 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT); 357 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT, 358 SDOperand Op1); 359 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT, 360 SDOperand Op1, SDOperand Op2); 361 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT, 362 SDOperand Op1, SDOperand Op2, SDOperand Op3); 363 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT, 364 const SDOperand *Ops, unsigned NumOps); 365 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT1, 366 MVT::ValueType VT2, SDOperand Op1, SDOperand Op2); 367 SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT1, 368 MVT::ValueType VT2, SDOperand Op1, SDOperand Op2, 369 SDOperand Op3); 370 371 372 /// getTargetNode - These are used for target selectors to create a new node 373 /// with specified return type(s), target opcode, and operands. 374 /// 375 /// Note that getTargetNode returns the resultant node. If there is already a 376 /// node of the specified opcode and operands, it returns that node instead of 377 /// the current one. 378 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT); 379 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT, 380 SDOperand Op1); 381 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT, 382 SDOperand Op1, SDOperand Op2); 383 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT, 384 SDOperand Op1, SDOperand Op2, SDOperand Op3); 385 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT, 386 const SDOperand *Ops, unsigned NumOps); 387 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1, 388 MVT::ValueType VT2, SDOperand Op1); 389 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1, 390 MVT::ValueType VT2, SDOperand Op1, SDOperand Op2); 391 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1, 392 MVT::ValueType VT2, SDOperand Op1, SDOperand Op2, 393 SDOperand Op3); 394 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1, 395 MVT::ValueType VT2, 396 const SDOperand *Ops, unsigned NumOps); 397 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1, 398 MVT::ValueType VT2, MVT::ValueType VT3, 399 SDOperand Op1, SDOperand Op2); 400 SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1, 401 MVT::ValueType VT2, MVT::ValueType VT3, 402 const SDOperand *Ops, unsigned NumOps); 403 404 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead. 405 /// This can cause recursive merging of nodes in the DAG. Use the first 406 /// version if 'From' is known to have a single result, use the second 407 /// if you have two nodes with identical results, use the third otherwise. 408 /// 409 /// These methods all take an optional vector, which (if not null) is 410 /// populated with any nodes that are deleted from the SelectionDAG, due to 411 /// new equivalences that are discovered. 412 /// 413 void ReplaceAllUsesWith(SDOperand From, SDOperand Op, 414 std::vector<SDNode*> *Deleted = 0); 415 void ReplaceAllUsesWith(SDNode *From, SDNode *To, 416 std::vector<SDNode*> *Deleted = 0); 417 void ReplaceAllUsesWith(SDNode *From, const SDOperand *To, 418 std::vector<SDNode*> *Deleted = 0); 419 420 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving 421 /// uses of other values produced by From.Val alone. The Deleted vector is 422 /// handled the same was as for ReplaceAllUsesWith, but it is required for 423 /// this method. 424 void ReplaceAllUsesOfValueWith(SDOperand From, SDOperand To, 425 std::vector<SDNode*> &Deleted); 426 427 /// AssignNodeIds - Assign a unique node id for each node in the DAG based on 428 /// their allnodes order. It returns the maximum id. 429 unsigned AssignNodeIds(); 430 431 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG 432 /// based on their topological order. It returns the maximum id and a vector 433 /// of the SDNodes* in assigned order by reference. 434 unsigned AssignTopologicalOrder(std::vector<SDNode*> &TopOrder); 435 436 /// isCommutativeBinOp - Returns true if the opcode is a commutative binary 437 /// operation. 438 static bool isCommutativeBinOp(unsigned Opcode) { 439 switch (Opcode) { 440 case ISD::ADD: 441 case ISD::MUL: 442 case ISD::MULHU: 443 case ISD::MULHS: 444 case ISD::FADD: 445 case ISD::FMUL: 446 case ISD::AND: 447 case ISD::OR: 448 case ISD::XOR: 449 case ISD::ADDC: 450 case ISD::ADDE: return true; 451 default: return false; 452 } 453 } 454 455 void dump() const; 456 457 /// FoldSetCC - Constant fold a setcc to true or false. 458 SDOperand FoldSetCC(MVT::ValueType VT, SDOperand N1, 459 SDOperand N2, ISD::CondCode Cond); 460 461private: 462 void RemoveNodeFromCSEMaps(SDNode *N); 463 SDNode *AddNonLeafNodeToCSEMaps(SDNode *N); 464 SDNode *FindModifiedNodeSlot(SDNode *N, SDOperand Op, void *&InsertPos); 465 SDNode *FindModifiedNodeSlot(SDNode *N, SDOperand Op1, SDOperand Op2, 466 void *&InsertPos); 467 SDNode *FindModifiedNodeSlot(SDNode *N, const SDOperand *Ops, unsigned NumOps, 468 void *&InsertPos); 469 470 void DeleteNodeNotInCSEMaps(SDNode *N); 471 472 // List of non-single value types. 473 std::list<std::vector<MVT::ValueType> > VTList; 474 475 // Maps to auto-CSE operations. 476 std::vector<CondCodeSDNode*> CondCodeNodes; 477 478 std::vector<SDNode*> ValueTypeNodes; 479 std::map<std::string, SDNode*> ExternalSymbols; 480 std::map<std::string, SDNode*> TargetExternalSymbols; 481 std::map<std::string, StringSDNode*> StringNodes; 482}; 483 484template <> struct GraphTraits<SelectionDAG*> : public GraphTraits<SDNode*> { 485 typedef SelectionDAG::allnodes_iterator nodes_iterator; 486 static nodes_iterator nodes_begin(SelectionDAG *G) { 487 return G->allnodes_begin(); 488 } 489 static nodes_iterator nodes_end(SelectionDAG *G) { 490 return G->allnodes_end(); 491 } 492}; 493 494} // end namespace llvm 495 496#endif 497