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