SelectionDAG.h revision b2efb853f00d45b1c8d57f92acd0028fbdeffda6 
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 "llvm/ADT/ilist"
20
21#include <map>
22#include <list>
23#include <string>
24
25namespace llvm {
26  class TargetLowering;
27  class TargetMachine;
28  class MachineDebugInfo;
29  class MachineFunction;
30
31/// SelectionDAG class - This is used to represent a portion of an LLVM function
32/// in a low-level Data Dependence DAG representation suitable for instruction
33/// selection.  This DAG is constructed as the first step of instruction
34/// selection in order to allow implementation of machine specific optimizations
35/// and code simplifications.
36///
37/// The representation used by the SelectionDAG is a target-independent
38/// representation, which has some similarities to the GCC RTL representation,
39/// but is significantly more simple, powerful, and is a graph form instead of a
40/// linear form.
41///
42class SelectionDAG {
43  TargetLowering &TLI;
44  MachineFunction &MF;
45  MachineDebugInfo *DI;
46
47  // Root - The root of the entire DAG.  EntryNode - The starting token.
48  SDOperand Root, EntryNode;
49
50  // AllNodes - A linked list of nodes in the current DAG.
51  ilist<SDNode> AllNodes;
52
53  // ValueNodes - track SrcValue nodes
54  std::map<std::pair<const Value*, int>, SDNode*> ValueNodes;
55
56public:
57  SelectionDAG(TargetLowering &tli, MachineFunction &mf, MachineDebugInfo *di)
58  : TLI(tli), MF(mf), DI(di) {
59    EntryNode = Root = getNode(ISD::EntryToken, MVT::Other);
60  }
61  ~SelectionDAG();
62
63  MachineFunction &getMachineFunction() const { return MF; }
64  const TargetMachine &getTarget() const;
65  TargetLowering &getTargetLoweringInfo() const { return TLI; }
66  MachineDebugInfo *getMachineDebugInfo() const { return DI; }
67
68  /// viewGraph - Pop up a ghostview window with the DAG rendered using 'dot'.
69  ///
70  void viewGraph();
71
72
73  typedef ilist<SDNode>::const_iterator allnodes_const_iterator;
74  allnodes_const_iterator allnodes_begin() const { return AllNodes.begin(); }
75  allnodes_const_iterator allnodes_end() const { return AllNodes.end(); }
76  typedef ilist<SDNode>::iterator allnodes_iterator;
77  allnodes_iterator allnodes_begin() { return AllNodes.begin(); }
78  allnodes_iterator allnodes_end() { return AllNodes.end(); }
79
80  /// getRoot - Return the root tag of the SelectionDAG.
81  ///
82  const SDOperand &getRoot() const { return Root; }
83
84  /// getEntryNode - Return the token chain corresponding to the entry of the
85  /// function.
86  const SDOperand &getEntryNode() const { return EntryNode; }
87
88  /// setRoot - Set the current root tag of the SelectionDAG.
89  ///
90  const SDOperand &setRoot(SDOperand N) { return Root = N; }
91
92  /// Combine - This iterates over the nodes in the SelectionDAG, folding
93  /// certain types of nodes together, or eliminating superfluous nodes.  When
94  /// the AfterLegalize argument is set to 'true', Combine takes care not to
95  /// generate any nodes that will be illegal on the target.
96  void Combine(bool AfterLegalize);
97
98  /// Legalize - This transforms the SelectionDAG into a SelectionDAG that is
99  /// compatible with the target instruction selector, as indicated by the
100  /// TargetLowering object.
101  ///
102  /// Note that this is an involved process that may invalidate pointers into
103  /// the graph.
104  void Legalize();
105
106  /// RemoveDeadNodes - This method deletes all unreachable nodes in the
107  /// SelectionDAG, including nodes (like loads) that have uses of their token
108  /// chain but no other uses and no side effect.  If a node is passed in as an
109  /// argument, it is used as the seed for node deletion.
110  void RemoveDeadNodes(SDNode *N = 0);
111
112  SDOperand getString(const std::string &Val);
113  SDOperand getConstant(uint64_t Val, MVT::ValueType VT);
114  SDOperand getTargetConstant(uint64_t Val, MVT::ValueType VT);
115  SDOperand getConstantFP(double Val, MVT::ValueType VT);
116  SDOperand getGlobalAddress(const GlobalValue *GV, MVT::ValueType VT,
117                             int offset = 0);
118  SDOperand getTargetGlobalAddress(const GlobalValue *GV, MVT::ValueType VT,
119                                   int offset = 0);
120  SDOperand getFrameIndex(int FI, MVT::ValueType VT);
121  SDOperand getTargetFrameIndex(int FI, MVT::ValueType VT);
122  SDOperand getConstantPool(Constant *C, MVT::ValueType VT);
123  SDOperand getTargetConstantPool(Constant *C, MVT::ValueType VT);
124  SDOperand getBasicBlock(MachineBasicBlock *MBB);
125  SDOperand getExternalSymbol(const char *Sym, MVT::ValueType VT);
126  SDOperand getTargetExternalSymbol(const char *Sym, MVT::ValueType VT);
127  SDOperand getValueType(MVT::ValueType);
128  SDOperand getRegister(unsigned Reg, MVT::ValueType VT);
129
130  SDOperand getCopyToReg(SDOperand Chain, unsigned Reg, SDOperand N) {
131    return getNode(ISD::CopyToReg, MVT::Other, Chain,
132                   getRegister(Reg, N.getValueType()), N);
133  }
134
135  // This version of the getCopyToReg method takes an extra operand, which
136  // indicates that there is potentially an incoming flag value (if Flag is not
137  // null) and that there should be a flag result.
138  SDOperand getCopyToReg(SDOperand Chain, unsigned Reg, SDOperand N,
139                         SDOperand Flag) {
140    std::vector<MVT::ValueType> VTs;
141    VTs.push_back(MVT::Other);
142    VTs.push_back(MVT::Flag);
143    std::vector<SDOperand> Ops;
144    Ops.push_back(Chain);
145    Ops.push_back(getRegister(Reg, N.getValueType()));
146    Ops.push_back(N);
147    if (Flag.Val) Ops.push_back(Flag);
148    return getNode(ISD::CopyToReg, VTs, Ops);
149  }
150
151  // Similar to last getCopyToReg() except parameter Reg is a SDOperand
152  SDOperand getCopyToReg(SDOperand Chain, SDOperand Reg, SDOperand N,
153                         SDOperand Flag) {
154    std::vector<MVT::ValueType> VTs;
155    VTs.push_back(MVT::Other);
156    VTs.push_back(MVT::Flag);
157    std::vector<SDOperand> Ops;
158    Ops.push_back(Chain);
159    Ops.push_back(Reg);
160    Ops.push_back(N);
161    if (Flag.Val) Ops.push_back(Flag);
162    return getNode(ISD::CopyToReg, VTs, Ops);
163  }
164
165  SDOperand getCopyFromReg(SDOperand Chain, unsigned Reg, MVT::ValueType VT) {
166    std::vector<MVT::ValueType> ResultTys;
167    ResultTys.push_back(VT);
168    ResultTys.push_back(MVT::Other);
169    std::vector<SDOperand> Ops;
170    Ops.push_back(Chain);
171    Ops.push_back(getRegister(Reg, VT));
172    return getNode(ISD::CopyFromReg, ResultTys, Ops);
173  }
174
175  // This version of the getCopyFromReg method takes an extra operand, which
176  // indicates that there is potentially an incoming flag value (if Flag is not
177  // null) and that there should be a flag result.
178  SDOperand getCopyFromReg(SDOperand Chain, unsigned Reg, MVT::ValueType VT,
179                           SDOperand Flag) {
180    std::vector<MVT::ValueType> ResultTys;
181    ResultTys.push_back(VT);
182    ResultTys.push_back(MVT::Other);
183    ResultTys.push_back(MVT::Flag);
184    std::vector<SDOperand> Ops;
185    Ops.push_back(Chain);
186    Ops.push_back(getRegister(Reg, VT));
187    if (Flag.Val) Ops.push_back(Flag);
188    return getNode(ISD::CopyFromReg, ResultTys, Ops);
189  }
190
191  /// getCall - Note that this destroys the vector of RetVals passed in.
192  ///
193  SDNode *getCall(std::vector<MVT::ValueType> &RetVals, SDOperand Chain,
194                  SDOperand Callee, bool isTailCall = false) {
195    SDNode *NN = new SDNode(isTailCall ? ISD::TAILCALL : ISD::CALL, Chain,
196                            Callee);
197    setNodeValueTypes(NN, RetVals);
198    AllNodes.push_back(NN);
199    return NN;
200  }
201  /// getCall - Note that this destroys the vector of RetVals passed in.
202  ///
203  SDNode *getCall(std::vector<MVT::ValueType> &RetVals, SDOperand Chain,
204                  SDOperand Callee, SDOperand Flag, bool isTailCall = false) {
205    SDNode *NN = new SDNode(isTailCall ? ISD::TAILCALL : ISD::CALL, Chain,
206                            Callee, Flag);
207    setNodeValueTypes(NN, RetVals);
208    AllNodes.push_back(NN);
209    return NN;
210  }
211
212  /// getCall - This is identical to the one above, and should be used for calls
213  /// where arguments are passed in physical registers.  This destroys the
214  /// RetVals and ArgsInRegs vectors.
215  SDNode *getCall(std::vector<MVT::ValueType> &RetVals, SDOperand Chain,
216                  SDOperand Callee, std::vector<SDOperand> &ArgsInRegs,
217                  bool isTailCall = false) {
218    ArgsInRegs.insert(ArgsInRegs.begin(), Callee);
219    ArgsInRegs.insert(ArgsInRegs.begin(), Chain);
220    SDNode *NN = new SDNode(isTailCall ? ISD::TAILCALL : ISD::CALL, ArgsInRegs);
221    setNodeValueTypes(NN, RetVals);
222    AllNodes.push_back(NN);
223    return NN;
224  }
225
226  SDOperand getCondCode(ISD::CondCode Cond);
227
228  /// getZeroExtendInReg - Return the expression required to zero extend the Op
229  /// value assuming it was the smaller SrcTy value.
230  SDOperand getZeroExtendInReg(SDOperand Op, MVT::ValueType SrcTy);
231
232  /// getNode - Gets or creates the specified node.
233  ///
234  SDOperand getNode(unsigned Opcode, MVT::ValueType VT);
235  SDOperand getNode(unsigned Opcode, MVT::ValueType VT, SDOperand N);
236  SDOperand getNode(unsigned Opcode, MVT::ValueType VT,
237                    SDOperand N1, SDOperand N2);
238  SDOperand getNode(unsigned Opcode, MVT::ValueType VT,
239                    SDOperand N1, SDOperand N2, SDOperand N3);
240  SDOperand getNode(unsigned Opcode, MVT::ValueType VT,
241                    SDOperand N1, SDOperand N2, SDOperand N3, SDOperand N4);
242  SDOperand getNode(unsigned Opcode, MVT::ValueType VT,
243                    SDOperand N1, SDOperand N2, SDOperand N3, SDOperand N4,
244                    SDOperand N5);
245  SDOperand getNode(unsigned Opcode, MVT::ValueType VT,
246                    SDOperand N1, SDOperand N2, SDOperand N3, SDOperand N4,
247                    SDOperand N5, SDOperand N6);
248  SDOperand getNode(unsigned Opcode, MVT::ValueType VT,
249                    std::vector<SDOperand> &Children);
250  SDOperand getNode(unsigned Opcode, std::vector<MVT::ValueType> &ResultTys,
251                    std::vector<SDOperand> &Ops);
252
253  /// getSetCC - Helper function to make it easier to build SetCC's if you just
254  /// have an ISD::CondCode instead of an SDOperand.
255  ///
256  SDOperand getSetCC(MVT::ValueType VT, SDOperand LHS, SDOperand RHS,
257                     ISD::CondCode Cond) {
258    return getNode(ISD::SETCC, VT, LHS, RHS, getCondCode(Cond));
259  }
260
261  /// getSelectCC - Helper function to make it easier to build SelectCC's if you
262  /// just have an ISD::CondCode instead of an SDOperand.
263  ///
264  SDOperand getSelectCC(SDOperand LHS, SDOperand RHS,
265                        SDOperand True, SDOperand False, ISD::CondCode Cond) {
266    MVT::ValueType VT = True.getValueType();
267    return getNode(ISD::SELECT_CC, VT, LHS, RHS, True, False,getCondCode(Cond));
268  }
269
270  /// getBR2Way_CC - Helper function to make it easier to build BRTWOWAY_CC
271  /// nodes.
272  ///
273  SDOperand getBR2Way_CC(SDOperand Chain, SDOperand CCNode, SDOperand LHS,
274                         SDOperand RHS, SDOperand True, SDOperand False) {
275    std::vector<SDOperand> Ops;
276    Ops.push_back(Chain);
277    Ops.push_back(CCNode);
278    Ops.push_back(LHS);
279    Ops.push_back(RHS);
280    Ops.push_back(True);
281    Ops.push_back(False);
282    return getNode(ISD::BRTWOWAY_CC, MVT::Other, Ops);
283  }
284
285  /// getLoad - Loads are not normal binary operators: their result type is not
286  /// determined by their operands, and they produce a value AND a token chain.
287  ///
288  SDOperand getLoad(MVT::ValueType VT, SDOperand Chain, SDOperand Ptr,
289                    SDOperand SV);
290  SDOperand getVecLoad(unsigned Count, MVT::ValueType VT, SDOperand Chain,
291                       SDOperand Ptr, SDOperand SV);
292  SDOperand getExtLoad(unsigned Opcode, MVT::ValueType VT, SDOperand Chain,
293                       SDOperand Ptr, SDOperand SV, MVT::ValueType EVT);
294
295  // getSrcValue - construct a node to track a Value* through the backend
296  SDOperand getSrcValue(const Value* I, int offset = 0);
297
298
299  /// SelectNodeTo - These are used for target selectors to *mutate* the
300  /// specified node to have the specified return type, Target opcode, and
301  /// operands.  Note that target opcodes are stored as
302  /// ISD::BUILTIN_OP_END+TargetOpcode in the node opcode field.  The 0th value
303  /// of the resultant node is returned.
304  SDOperand SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT);
305  SDOperand SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT,
306                         SDOperand Op1);
307  SDOperand SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT,
308                         SDOperand Op1, SDOperand Op2);
309  SDOperand SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT,
310                         SDOperand Op1, SDOperand Op2, SDOperand Op3);
311  SDOperand SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT,
312                         SDOperand Op1, SDOperand Op2, SDOperand Op3,
313                         SDOperand Op4);
314  SDOperand SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT,
315                         SDOperand Op1, SDOperand Op2, SDOperand Op3,
316                         SDOperand Op4, SDOperand Op5);
317  SDOperand SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT,
318                         SDOperand Op1, SDOperand Op2, SDOperand Op3,
319                         SDOperand Op4, SDOperand Op5, SDOperand Op6);
320  SDOperand SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT1,
321                         MVT::ValueType VT2, SDOperand Op1, SDOperand Op2);
322  SDOperand SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT1,
323                         MVT::ValueType VT2, SDOperand Op1, SDOperand Op2,
324                         SDOperand Op3);
325  SDOperand SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT1,
326                         MVT::ValueType VT2, SDOperand Op1, SDOperand Op2,
327                         SDOperand Op3, SDOperand Op4);
328  SDOperand SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT1,
329                         MVT::ValueType VT2, SDOperand Op1, SDOperand Op2,
330                         SDOperand Op3, SDOperand Op4, SDOperand Op5);
331
332  SDOperand getTargetNode(unsigned Opcode, MVT::ValueType VT) {
333    return getNode(ISD::BUILTIN_OP_END+Opcode, VT);
334  }
335  SDOperand getTargetNode(unsigned Opcode, MVT::ValueType VT,
336                          SDOperand Op1) {
337    return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1);
338  }
339  SDOperand getTargetNode(unsigned Opcode, MVT::ValueType VT,
340                          SDOperand Op1, SDOperand Op2) {
341    return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1, Op2);
342  }
343  SDOperand getTargetNode(unsigned Opcode, MVT::ValueType VT,
344                          SDOperand Op1, SDOperand Op2, SDOperand Op3) {
345    return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1, Op2, Op3);
346  }
347  SDOperand getTargetNode(unsigned Opcode, MVT::ValueType VT,
348                          SDOperand Op1, SDOperand Op2, SDOperand Op3,
349                          SDOperand Op4) {
350    return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1, Op2, Op3, Op4);
351  }
352  SDOperand getTargetNode(unsigned Opcode, MVT::ValueType VT,
353                          SDOperand Op1, SDOperand Op2, SDOperand Op3,
354                          SDOperand Op4, SDOperand Op5) {
355    return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1, Op2, Op3, Op4, Op5);
356  }
357  SDOperand getTargetNode(unsigned Opcode, MVT::ValueType VT,
358                          SDOperand Op1, SDOperand Op2, SDOperand Op3,
359                          SDOperand Op4, SDOperand Op5, SDOperand Op6) {
360    return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1, Op2, Op3, Op4, Op5, Op6);
361  }
362  SDOperand getTargetNode(unsigned Opcode, MVT::ValueType VT,
363                          std::vector<SDOperand> &Ops) {
364    return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Ops);
365  }
366  SDOperand getTargetNode(unsigned Opcode, MVT::ValueType VT1,
367                          MVT::ValueType VT2, SDOperand Op1) {
368    std::vector<MVT::ValueType> ResultTys;
369    ResultTys.push_back(VT1);
370    ResultTys.push_back(VT2);
371    std::vector<SDOperand> Ops;
372    Ops.push_back(Op1);
373    return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops);
374  }
375  SDOperand getTargetNode(unsigned Opcode, MVT::ValueType VT1,
376                          MVT::ValueType VT2, SDOperand Op1, SDOperand Op2) {
377    std::vector<MVT::ValueType> ResultTys;
378    ResultTys.push_back(VT1);
379    ResultTys.push_back(VT2);
380    std::vector<SDOperand> Ops;
381    Ops.push_back(Op1);
382    Ops.push_back(Op2);
383    return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops);
384  }
385  SDOperand getTargetNode(unsigned Opcode, MVT::ValueType VT1,
386                          MVT::ValueType VT2, SDOperand Op1, SDOperand Op2,
387                          SDOperand Op3) {
388    std::vector<MVT::ValueType> ResultTys;
389    ResultTys.push_back(VT1);
390    ResultTys.push_back(VT2);
391    std::vector<SDOperand> Ops;
392    Ops.push_back(Op1);
393    Ops.push_back(Op2);
394    Ops.push_back(Op3);
395    return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops);
396  }
397  SDOperand getTargetNode(unsigned Opcode, MVT::ValueType VT1,
398                          MVT::ValueType VT2, SDOperand Op1, SDOperand Op2,
399                          SDOperand Op3, SDOperand Op4) {
400    std::vector<MVT::ValueType> ResultTys;
401    ResultTys.push_back(VT1);
402    ResultTys.push_back(VT2);
403    std::vector<SDOperand> Ops;
404    Ops.push_back(Op1);
405    Ops.push_back(Op2);
406    Ops.push_back(Op3);
407    Ops.push_back(Op4);
408    return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops);
409  }
410  SDOperand getTargetNode(unsigned Opcode, MVT::ValueType VT1,
411                          MVT::ValueType VT2, SDOperand Op1, SDOperand Op2,
412                          SDOperand Op3, SDOperand Op4, SDOperand Op5) {
413    std::vector<MVT::ValueType> ResultTys;
414    ResultTys.push_back(VT1);
415    ResultTys.push_back(VT2);
416    std::vector<SDOperand> Ops;
417    Ops.push_back(Op1);
418    Ops.push_back(Op2);
419    Ops.push_back(Op3);
420    Ops.push_back(Op4);
421    Ops.push_back(Op5);
422    return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops);
423  }
424  SDOperand getTargetNode(unsigned Opcode, MVT::ValueType VT1,
425                          MVT::ValueType VT2, SDOperand Op1, SDOperand Op2,
426                          SDOperand Op3, SDOperand Op4, SDOperand Op5,
427                          SDOperand Op6) {
428    std::vector<MVT::ValueType> ResultTys;
429    ResultTys.push_back(VT1);
430    ResultTys.push_back(VT2);
431    std::vector<SDOperand> Ops;
432    Ops.push_back(Op1);
433    Ops.push_back(Op2);
434    Ops.push_back(Op3);
435    Ops.push_back(Op4);
436    Ops.push_back(Op5);
437    Ops.push_back(Op6);
438    return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops);
439  }
440  SDOperand getTargetNode(unsigned Opcode, MVT::ValueType VT1,
441                          MVT::ValueType VT2, SDOperand Op1, SDOperand Op2,
442                          SDOperand Op3, SDOperand Op4, SDOperand Op5,
443                          SDOperand Op6, SDOperand Op7) {
444    std::vector<MVT::ValueType> ResultTys;
445    ResultTys.push_back(VT1);
446    ResultTys.push_back(VT2);
447    std::vector<SDOperand> Ops;
448    Ops.push_back(Op1);
449    Ops.push_back(Op2);
450    Ops.push_back(Op3);
451    Ops.push_back(Op4);
452    Ops.push_back(Op5);
453    Ops.push_back(Op6);
454    Ops.push_back(Op7);
455   return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops);
456  }
457  SDOperand getTargetNode(unsigned Opcode, MVT::ValueType VT1,
458                          MVT::ValueType VT2, std::vector<SDOperand> &Ops) {
459    std::vector<MVT::ValueType> ResultTys;
460    ResultTys.push_back(VT1);
461    ResultTys.push_back(VT2);
462    return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops);
463  }
464
465  /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
466  /// This can cause recursive merging of nodes in the DAG.  Use the first
467  /// version if 'From' is known to have a single result, use the second
468  /// if you have two nodes with identical results, use the third otherwise.
469  ///
470  /// These methods all take an optional vector, which (if not null) is
471  /// populated with any nodes that are deleted from the SelectionDAG, due to
472  /// new equivalences that are discovered.
473  ///
474  void ReplaceAllUsesWith(SDOperand From, SDOperand Op,
475                          std::vector<SDNode*> *Deleted = 0);
476  void ReplaceAllUsesWith(SDNode *From, SDNode *To,
477                          std::vector<SDNode*> *Deleted = 0);
478  void ReplaceAllUsesWith(SDNode *From, const std::vector<SDOperand> &To,
479                          std::vector<SDNode*> *Deleted = 0);
480
481
482  /// DeleteNode - Remove the specified node from the system.  This node must
483  /// have no referrers.
484  void DeleteNode(SDNode *N);
485
486  void dump() const;
487
488private:
489  void RemoveNodeFromCSEMaps(SDNode *N);
490  SDNode *AddNonLeafNodeToCSEMaps(SDNode *N);
491  void DestroyDeadNode(SDNode *N);
492  void DeleteNodeNotInCSEMaps(SDNode *N);
493  void setNodeValueTypes(SDNode *N, std::vector<MVT::ValueType> &RetVals);
494  void setNodeValueTypes(SDNode *N, MVT::ValueType VT1, MVT::ValueType VT2);
495
496
497  /// SimplifySetCC - Try to simplify a setcc built with the specified operands
498  /// and cc.  If unable to simplify it, return a null SDOperand.
499  SDOperand SimplifySetCC(MVT::ValueType VT, SDOperand N1,
500                          SDOperand N2, ISD::CondCode Cond);
501
502  // List of non-single value types.
503  std::list<std::vector<MVT::ValueType> > VTList;
504
505  // Maps to auto-CSE operations.
506  std::map<std::pair<unsigned, MVT::ValueType>, SDNode *> NullaryOps;
507  std::map<std::pair<unsigned, std::pair<SDOperand, MVT::ValueType> >,
508           SDNode *> UnaryOps;
509  std::map<std::pair<unsigned, std::pair<SDOperand, SDOperand> >,
510           SDNode *> BinaryOps;
511
512  std::map<std::pair<unsigned, MVT::ValueType>, RegisterSDNode*> RegNodes;
513  std::vector<CondCodeSDNode*> CondCodeNodes;
514
515  std::map<std::pair<SDOperand, std::pair<SDOperand, MVT::ValueType> >,
516           SDNode *> Loads;
517
518  std::map<std::pair<const GlobalValue*, int>, SDNode*> GlobalValues;
519  std::map<std::pair<const GlobalValue*, int>, SDNode*> TargetGlobalValues;
520  std::map<std::pair<uint64_t, MVT::ValueType>, SDNode*> Constants;
521  std::map<std::pair<uint64_t, MVT::ValueType>, SDNode*> TargetConstants;
522  std::map<std::pair<uint64_t, MVT::ValueType>, SDNode*> ConstantFPs;
523  std::map<int, SDNode*> FrameIndices, TargetFrameIndices;
524  std::map<Constant *, SDNode*> ConstantPoolIndices;
525  std::map<Constant *, SDNode*> TargetConstantPoolIndices;
526  std::map<MachineBasicBlock *, SDNode*> BBNodes;
527  std::vector<SDNode*> ValueTypeNodes;
528  std::map<std::string, SDNode*> ExternalSymbols;
529  std::map<std::string, SDNode*> TargetExternalSymbols;
530  std::map<std::string, StringSDNode*> StringNodes;
531  std::map<std::pair<unsigned,
532                     std::pair<MVT::ValueType, std::vector<SDOperand> > >,
533           SDNode*> OneResultNodes;
534  std::map<std::pair<unsigned,
535                     std::pair<std::vector<MVT::ValueType>,
536                               std::vector<SDOperand> > >,
537           SDNode*> ArbitraryNodes;
538};
539
540template <> struct GraphTraits<SelectionDAG*> : public GraphTraits<SDNode*> {
541  typedef SelectionDAG::allnodes_iterator nodes_iterator;
542  static nodes_iterator nodes_begin(SelectionDAG *G) {
543    return G->allnodes_begin();
544  }
545  static nodes_iterator nodes_end(SelectionDAG *G) {
546    return G->allnodes_end();
547  }
548};
549
550}  // end namespace llvm
551
552#endif
553