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