SelectionDAG.h revision b4e6a5df5dada0cd919cc6e2717eb3118db9cc45 
1//===-- llvm/CodeGen/SelectionDAG.h - InstSelection DAG ---------*- C++ -*-===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// 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/ilist.h"
19#include "llvm/ADT/DenseSet.h"
20#include "llvm/ADT/StringMap.h"
21#include "llvm/CodeGen/SelectionDAGNodes.h"
22#include "llvm/Support/RecyclingAllocator.h"
23#include "llvm/Target/TargetMachine.h"
24#include <cassert>
25#include <vector>
26#include <map>
27#include <string>
28
29namespace llvm {
30
31class AliasAnalysis;
32class DwarfWriter;
33class FunctionLoweringInfo;
34class MachineConstantPoolValue;
35class MachineFunction;
36class MachineModuleInfo;
37class SDNodeOrdering;
38class TargetLowering;
39
40template<> struct ilist_traits<SDNode> : public ilist_default_traits<SDNode> {
41private:
42  mutable ilist_half_node<SDNode> Sentinel;
43public:
44  SDNode *createSentinel() const {
45    return static_cast<SDNode*>(&Sentinel);
46  }
47  static void destroySentinel(SDNode *) {}
48
49  SDNode *provideInitialHead() const { return createSentinel(); }
50  SDNode *ensureHead(SDNode*) const { return createSentinel(); }
51  static void noteHead(SDNode*, SDNode*) {}
52
53  static void deleteNode(SDNode *) {
54    assert(0 && "ilist_traits<SDNode> shouldn't see a deleteNode call!");
55  }
56private:
57  static void createNode(const SDNode &);
58};
59
60enum CombineLevel {
61  Unrestricted,   // Combine may create illegal operations and illegal types.
62  NoIllegalTypes, // Combine may create illegal operations but no illegal types.
63  NoIllegalOperations // Combine may only create legal operations and types.
64};
65
66/// SelectionDAG class - This is used to represent a portion of an LLVM function
67/// in a low-level Data Dependence DAG representation suitable for instruction
68/// selection.  This DAG is constructed as the first step of instruction
69/// selection in order to allow implementation of machine specific optimizations
70/// and code simplifications.
71///
72/// The representation used by the SelectionDAG is a target-independent
73/// representation, which has some similarities to the GCC RTL representation,
74/// but is significantly more simple, powerful, and is a graph form instead of a
75/// linear form.
76///
77class SelectionDAG {
78  TargetLowering &TLI;
79  MachineFunction *MF;
80  FunctionLoweringInfo &FLI;
81  MachineModuleInfo *MMI;
82  DwarfWriter *DW;
83  LLVMContext* Context;
84
85  /// EntryNode - The starting token.
86  SDNode EntryNode;
87
88  /// Root - The root of the entire DAG.
89  SDValue Root;
90
91  /// AllNodes - A linked list of nodes in the current DAG.
92  ilist<SDNode> AllNodes;
93
94  /// NodeAllocatorType - The AllocatorType for allocating SDNodes. We use
95  /// pool allocation with recycling.
96  typedef RecyclingAllocator<BumpPtrAllocator, SDNode, sizeof(LargestSDNode),
97                             AlignOf<MostAlignedSDNode>::Alignment>
98    NodeAllocatorType;
99
100  /// NodeAllocator - Pool allocation for nodes.
101  NodeAllocatorType NodeAllocator;
102
103  /// CSEMap - This structure is used to memoize nodes, automatically performing
104  /// CSE with existing nodes when a duplicate is requested.
105  FoldingSet<SDNode> CSEMap;
106
107  /// OperandAllocator - Pool allocation for machine-opcode SDNode operands.
108  BumpPtrAllocator OperandAllocator;
109
110  /// Allocator - Pool allocation for misc. objects that are created once per
111  /// SelectionDAG.
112  BumpPtrAllocator Allocator;
113
114  /// SDNodeOrdering - The ordering of the SDNodes. It roughly corresponds to
115  /// the ordering of the original LLVM instructions.
116  SDNodeOrdering *Ordering;
117
118  /// VerifyNode - Sanity check the given node.  Aborts if it is invalid.
119  void VerifyNode(SDNode *N);
120
121  /// setGraphColorHelper - Implementation of setSubgraphColor.
122  /// Return whether we had to truncate the search.
123  ///
124  bool setSubgraphColorHelper(SDNode *N, const char *Color,
125                              DenseSet<SDNode *> &visited,
126                              int level, bool &printed);
127
128  void operator=(const SelectionDAG&); // Do not implement.
129  SelectionDAG(const SelectionDAG&);   // Do not implement.
130
131public:
132  SelectionDAG(TargetLowering &tli, FunctionLoweringInfo &fli);
133  ~SelectionDAG();
134
135  /// init - Prepare this SelectionDAG to process code in the given
136  /// MachineFunction.
137  ///
138  void init(MachineFunction &mf, MachineModuleInfo *mmi, DwarfWriter *dw);
139
140  /// clear - Clear state and free memory necessary to make this
141  /// SelectionDAG ready to process a new block.
142  ///
143  void clear();
144
145  MachineFunction &getMachineFunction() const { return *MF; }
146  const TargetMachine &getTarget() const;
147  TargetLowering &getTargetLoweringInfo() const { return TLI; }
148  FunctionLoweringInfo &getFunctionLoweringInfo() const { return FLI; }
149  MachineModuleInfo *getMachineModuleInfo() const { return MMI; }
150  DwarfWriter *getDwarfWriter() const { return DW; }
151  LLVMContext *getContext() const {return Context; }
152
153  /// viewGraph - Pop up a GraphViz/gv window with the DAG rendered using 'dot'.
154  ///
155  void viewGraph(const std::string &Title);
156  void viewGraph();
157
158#ifndef NDEBUG
159  std::map<const SDNode *, std::string> NodeGraphAttrs;
160#endif
161
162  /// clearGraphAttrs - Clear all previously defined node graph attributes.
163  /// Intended to be used from a debugging tool (eg. gdb).
164  void clearGraphAttrs();
165
166  /// setGraphAttrs - Set graph attributes for a node. (eg. "color=red".)
167  ///
168  void setGraphAttrs(const SDNode *N, const char *Attrs);
169
170  /// getGraphAttrs - Get graph attributes for a node. (eg. "color=red".)
171  /// Used from getNodeAttributes.
172  const std::string getGraphAttrs(const SDNode *N) const;
173
174  /// setGraphColor - Convenience for setting node color attribute.
175  ///
176  void setGraphColor(const SDNode *N, const char *Color);
177
178  /// setGraphColor - Convenience for setting subgraph color attribute.
179  ///
180  void setSubgraphColor(SDNode *N, const char *Color);
181
182  typedef ilist<SDNode>::const_iterator allnodes_const_iterator;
183  allnodes_const_iterator allnodes_begin() const { return AllNodes.begin(); }
184  allnodes_const_iterator allnodes_end() const { return AllNodes.end(); }
185  typedef ilist<SDNode>::iterator allnodes_iterator;
186  allnodes_iterator allnodes_begin() { return AllNodes.begin(); }
187  allnodes_iterator allnodes_end() { return AllNodes.end(); }
188  ilist<SDNode>::size_type allnodes_size() const {
189    return AllNodes.size();
190  }
191
192  /// getRoot - Return the root tag of the SelectionDAG.
193  ///
194  const SDValue &getRoot() const { return Root; }
195
196  /// getEntryNode - Return the token chain corresponding to the entry of the
197  /// function.
198  SDValue getEntryNode() const {
199    return SDValue(const_cast<SDNode *>(&EntryNode), 0);
200  }
201
202  /// setRoot - Set the current root tag of the SelectionDAG.
203  ///
204  const SDValue &setRoot(SDValue N) {
205    assert((!N.getNode() || N.getValueType() == MVT::Other) &&
206           "DAG root value is not a chain!");
207    return Root = N;
208  }
209
210  /// Combine - This iterates over the nodes in the SelectionDAG, folding
211  /// certain types of nodes together, or eliminating superfluous nodes.  The
212  /// Level argument controls whether Combine is allowed to produce nodes and
213  /// types that are illegal on the target.
214  void Combine(CombineLevel Level, AliasAnalysis &AA,
215               CodeGenOpt::Level OptLevel);
216
217  /// LegalizeTypes - This transforms the SelectionDAG into a SelectionDAG that
218  /// only uses types natively supported by the target.  Returns "true" if it
219  /// made any changes.
220  ///
221  /// Note that this is an involved process that may invalidate pointers into
222  /// the graph.
223  bool LegalizeTypes();
224
225  /// Legalize - This transforms the SelectionDAG into a SelectionDAG that is
226  /// compatible with the target instruction selector, as indicated by the
227  /// TargetLowering object.
228  ///
229  /// Note that this is an involved process that may invalidate pointers into
230  /// the graph.
231  void Legalize(CodeGenOpt::Level OptLevel);
232
233  /// LegalizeVectors - This transforms the SelectionDAG into a SelectionDAG
234  /// that only uses vector math operations supported by the target.  This is
235  /// necessary as a separate step from Legalize because unrolling a vector
236  /// operation can introduce illegal types, which requires running
237  /// LegalizeTypes again.
238  ///
239  /// This returns true if it made any changes; in that case, LegalizeTypes
240  /// is called again before Legalize.
241  ///
242  /// Note that this is an involved process that may invalidate pointers into
243  /// the graph.
244  bool LegalizeVectors();
245
246  /// RemoveDeadNodes - This method deletes all unreachable nodes in the
247  /// SelectionDAG.
248  void RemoveDeadNodes();
249
250  /// DeleteNode - Remove the specified node from the system.  This node must
251  /// have no referrers.
252  void DeleteNode(SDNode *N);
253
254  /// getVTList - Return an SDVTList that represents the list of values
255  /// specified.
256  SDVTList getVTList(EVT VT);
257  SDVTList getVTList(EVT VT1, EVT VT2);
258  SDVTList getVTList(EVT VT1, EVT VT2, EVT VT3);
259  SDVTList getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4);
260  SDVTList getVTList(const EVT *VTs, unsigned NumVTs);
261
262  //===--------------------------------------------------------------------===//
263  // Node creation methods.
264  //
265  SDValue getConstant(uint64_t Val, EVT VT, bool isTarget = false);
266  SDValue getConstant(const APInt &Val, EVT VT, bool isTarget = false);
267  SDValue getConstant(const ConstantInt &Val, EVT VT, bool isTarget = false);
268  SDValue getIntPtrConstant(uint64_t Val, bool isTarget = false);
269  SDValue getTargetConstant(uint64_t Val, EVT VT) {
270    return getConstant(Val, VT, true);
271  }
272  SDValue getTargetConstant(const APInt &Val, EVT VT) {
273    return getConstant(Val, VT, true);
274  }
275  SDValue getTargetConstant(const ConstantInt &Val, EVT VT) {
276    return getConstant(Val, VT, true);
277  }
278  SDValue getConstantFP(double Val, EVT VT, bool isTarget = false);
279  SDValue getConstantFP(const APFloat& Val, EVT VT, bool isTarget = false);
280  SDValue getConstantFP(const ConstantFP &CF, EVT VT, bool isTarget = false);
281  SDValue getTargetConstantFP(double Val, EVT VT) {
282    return getConstantFP(Val, VT, true);
283  }
284  SDValue getTargetConstantFP(const APFloat& Val, EVT VT) {
285    return getConstantFP(Val, VT, true);
286  }
287  SDValue getTargetConstantFP(const ConstantFP &Val, EVT VT) {
288    return getConstantFP(Val, VT, true);
289  }
290  SDValue getGlobalAddress(const GlobalValue *GV, EVT VT,
291                           int64_t offset = 0, bool isTargetGA = false,
292                           unsigned char TargetFlags = 0);
293  SDValue getTargetGlobalAddress(const GlobalValue *GV, EVT VT,
294                                 int64_t offset = 0,
295                                 unsigned char TargetFlags = 0) {
296    return getGlobalAddress(GV, VT, offset, true, TargetFlags);
297  }
298  SDValue getFrameIndex(int FI, EVT VT, bool isTarget = false);
299  SDValue getTargetFrameIndex(int FI, EVT VT) {
300    return getFrameIndex(FI, VT, true);
301  }
302  SDValue getJumpTable(int JTI, EVT VT, bool isTarget = false,
303                       unsigned char TargetFlags = 0);
304  SDValue getTargetJumpTable(int JTI, EVT VT, unsigned char TargetFlags = 0) {
305    return getJumpTable(JTI, VT, true, TargetFlags);
306  }
307  SDValue getConstantPool(Constant *C, EVT VT,
308                          unsigned Align = 0, int Offs = 0, bool isT=false,
309                          unsigned char TargetFlags = 0);
310  SDValue getTargetConstantPool(Constant *C, EVT VT,
311                                unsigned Align = 0, int Offset = 0,
312                                unsigned char TargetFlags = 0) {
313    return getConstantPool(C, VT, Align, Offset, true, TargetFlags);
314  }
315  SDValue getConstantPool(MachineConstantPoolValue *C, EVT VT,
316                          unsigned Align = 0, int Offs = 0, bool isT=false,
317                          unsigned char TargetFlags = 0);
318  SDValue getTargetConstantPool(MachineConstantPoolValue *C,
319                                  EVT VT, unsigned Align = 0,
320                                  int Offset = 0, unsigned char TargetFlags=0) {
321    return getConstantPool(C, VT, Align, Offset, true, TargetFlags);
322  }
323  // When generating a branch to a BB, we don't in general know enough
324  // to provide debug info for the BB at that time, so keep this one around.
325  SDValue getBasicBlock(MachineBasicBlock *MBB);
326  SDValue getBasicBlock(MachineBasicBlock *MBB, DebugLoc dl);
327  SDValue getExternalSymbol(const char *Sym, EVT VT);
328  SDValue getExternalSymbol(const char *Sym, DebugLoc dl, EVT VT);
329  SDValue getTargetExternalSymbol(const char *Sym, EVT VT,
330                                  unsigned char TargetFlags = 0);
331  SDValue getValueType(EVT);
332  SDValue getRegister(unsigned Reg, EVT VT);
333  SDValue getLabel(unsigned Opcode, DebugLoc dl, SDValue Root,
334                   unsigned LabelID);
335  SDValue getBlockAddress(BlockAddress *BA, EVT VT,
336                          bool isTarget = false, unsigned char TargetFlags = 0);
337
338  SDValue getCopyToReg(SDValue Chain, DebugLoc dl, unsigned Reg, SDValue N) {
339    return getNode(ISD::CopyToReg, dl, MVT::Other, Chain,
340                   getRegister(Reg, N.getValueType()), N);
341  }
342
343  // This version of the getCopyToReg method takes an extra operand, which
344  // indicates that there is potentially an incoming flag value (if Flag is not
345  // null) and that there should be a flag result.
346  SDValue getCopyToReg(SDValue Chain, DebugLoc dl, unsigned Reg, SDValue N,
347                       SDValue Flag) {
348    SDVTList VTs = getVTList(MVT::Other, MVT::Flag);
349    SDValue Ops[] = { Chain, getRegister(Reg, N.getValueType()), N, Flag };
350    return getNode(ISD::CopyToReg, dl, VTs, Ops, Flag.getNode() ? 4 : 3);
351  }
352
353  // Similar to last getCopyToReg() except parameter Reg is a SDValue
354  SDValue getCopyToReg(SDValue Chain, DebugLoc dl, SDValue Reg, SDValue N,
355                         SDValue Flag) {
356    SDVTList VTs = getVTList(MVT::Other, MVT::Flag);
357    SDValue Ops[] = { Chain, Reg, N, Flag };
358    return getNode(ISD::CopyToReg, dl, VTs, Ops, Flag.getNode() ? 4 : 3);
359  }
360
361  SDValue getCopyFromReg(SDValue Chain, DebugLoc dl, unsigned Reg, EVT VT) {
362    SDVTList VTs = getVTList(VT, MVT::Other);
363    SDValue Ops[] = { Chain, getRegister(Reg, VT) };
364    return getNode(ISD::CopyFromReg, dl, VTs, Ops, 2);
365  }
366
367  // This version of the getCopyFromReg method takes an extra operand, which
368  // indicates that there is potentially an incoming flag value (if Flag is not
369  // null) and that there should be a flag result.
370  SDValue getCopyFromReg(SDValue Chain, DebugLoc dl, unsigned Reg, EVT VT,
371                           SDValue Flag) {
372    SDVTList VTs = getVTList(VT, MVT::Other, MVT::Flag);
373    SDValue Ops[] = { Chain, getRegister(Reg, VT), Flag };
374    return getNode(ISD::CopyFromReg, dl, VTs, Ops, Flag.getNode() ? 3 : 2);
375  }
376
377  SDValue getCondCode(ISD::CondCode Cond);
378
379  /// Returns the ConvertRndSat Note: Avoid using this node because it may
380  /// disappear in the future and most targets don't support it.
381  SDValue getConvertRndSat(EVT VT, DebugLoc dl, SDValue Val, SDValue DTy,
382                           SDValue STy,
383                           SDValue Rnd, SDValue Sat, ISD::CvtCode Code);
384
385  /// getVectorShuffle - Return an ISD::VECTOR_SHUFFLE node.  The number of
386  /// elements in VT, which must be a vector type, must match the number of
387  /// mask elements NumElts.  A integer mask element equal to -1 is treated as
388  /// undefined.
389  SDValue getVectorShuffle(EVT VT, DebugLoc dl, SDValue N1, SDValue N2,
390                           const int *MaskElts);
391
392  /// getSExtOrTrunc - Convert Op, which must be of integer type, to the
393  /// integer type VT, by either sign-extending or truncating it.
394  SDValue getSExtOrTrunc(SDValue Op, DebugLoc DL, EVT VT);
395
396  /// getZExtOrTrunc - Convert Op, which must be of integer type, to the
397  /// integer type VT, by either zero-extending or truncating it.
398  SDValue getZExtOrTrunc(SDValue Op, DebugLoc DL, EVT VT);
399
400  /// getZeroExtendInReg - Return the expression required to zero extend the Op
401  /// value assuming it was the smaller SrcTy value.
402  SDValue getZeroExtendInReg(SDValue Op, DebugLoc DL, EVT SrcTy);
403
404  /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
405  SDValue getNOT(DebugLoc DL, SDValue Val, EVT VT);
406
407  /// getCALLSEQ_START - Return a new CALLSEQ_START node, which always must have
408  /// a flag result (to ensure it's not CSE'd).  CALLSEQ_START does not have a
409  /// useful DebugLoc.
410  SDValue getCALLSEQ_START(SDValue Chain, SDValue Op) {
411    SDVTList VTs = getVTList(MVT::Other, MVT::Flag);
412    SDValue Ops[] = { Chain,  Op };
413    return getNode(ISD::CALLSEQ_START, DebugLoc::getUnknownLoc(),
414                   VTs, Ops, 2);
415  }
416
417  /// getCALLSEQ_END - Return a new CALLSEQ_END node, which always must have a
418  /// flag result (to ensure it's not CSE'd).  CALLSEQ_END does not have
419  /// a useful DebugLoc.
420  SDValue getCALLSEQ_END(SDValue Chain, SDValue Op1, SDValue Op2,
421                           SDValue InFlag) {
422    SDVTList NodeTys = getVTList(MVT::Other, MVT::Flag);
423    SmallVector<SDValue, 4> Ops;
424    Ops.push_back(Chain);
425    Ops.push_back(Op1);
426    Ops.push_back(Op2);
427    Ops.push_back(InFlag);
428    return getNode(ISD::CALLSEQ_END, DebugLoc::getUnknownLoc(), NodeTys,
429                   &Ops[0],
430                   (unsigned)Ops.size() - (InFlag.getNode() == 0 ? 1 : 0));
431  }
432
433  /// getUNDEF - Return an UNDEF node.  UNDEF does not have a useful DebugLoc.
434  SDValue getUNDEF(EVT VT) {
435    return getNode(ISD::UNDEF, DebugLoc::getUnknownLoc(), VT);
436  }
437
438  /// getGLOBAL_OFFSET_TABLE - Return a GLOBAL_OFFSET_TABLE node.  This does
439  /// not have a useful DebugLoc.
440  SDValue getGLOBAL_OFFSET_TABLE(EVT VT) {
441    return getNode(ISD::GLOBAL_OFFSET_TABLE, DebugLoc::getUnknownLoc(), VT);
442  }
443
444  /// getNode - Gets or creates the specified node.
445  ///
446  SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT);
447  SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT, SDValue N);
448  SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT, SDValue N1, SDValue N2);
449  SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT,
450                  SDValue N1, SDValue N2, SDValue N3);
451  SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT,
452                  SDValue N1, SDValue N2, SDValue N3, SDValue N4);
453  SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT,
454                  SDValue N1, SDValue N2, SDValue N3, SDValue N4,
455                  SDValue N5);
456  SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT,
457                  const SDUse *Ops, unsigned NumOps);
458  SDValue getNode(unsigned Opcode, DebugLoc DL, EVT VT,
459                  const SDValue *Ops, unsigned NumOps);
460  SDValue getNode(unsigned Opcode, DebugLoc DL,
461                  const std::vector<EVT> &ResultTys,
462                  const SDValue *Ops, unsigned NumOps);
463  SDValue getNode(unsigned Opcode, DebugLoc DL, const EVT *VTs, unsigned NumVTs,
464                  const SDValue *Ops, unsigned NumOps);
465  SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs,
466                  const SDValue *Ops, unsigned NumOps);
467  SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs);
468  SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs, SDValue N);
469  SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs,
470                  SDValue N1, SDValue N2);
471  SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs,
472                  SDValue N1, SDValue N2, SDValue N3);
473  SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs,
474                  SDValue N1, SDValue N2, SDValue N3, SDValue N4);
475  SDValue getNode(unsigned Opcode, DebugLoc DL, SDVTList VTs,
476                  SDValue N1, SDValue N2, SDValue N3, SDValue N4,
477                  SDValue N5);
478
479  /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
480  /// the incoming stack arguments to be loaded from the stack. This is
481  /// used in tail call lowering to protect stack arguments from being
482  /// clobbered.
483  SDValue getStackArgumentTokenFactor(SDValue Chain);
484
485  SDValue getMemcpy(SDValue Chain, DebugLoc dl, SDValue Dst, SDValue Src,
486                    SDValue Size, unsigned Align, bool AlwaysInline,
487                    const Value *DstSV, uint64_t DstSVOff,
488                    const Value *SrcSV, uint64_t SrcSVOff);
489
490  SDValue getMemmove(SDValue Chain, DebugLoc dl, SDValue Dst, SDValue Src,
491                     SDValue Size, unsigned Align,
492                     const Value *DstSV, uint64_t DstOSVff,
493                     const Value *SrcSV, uint64_t SrcSVOff);
494
495  SDValue getMemset(SDValue Chain, DebugLoc dl, SDValue Dst, SDValue Src,
496                    SDValue Size, unsigned Align,
497                    const Value *DstSV, uint64_t DstSVOff);
498
499  /// getSetCC - Helper function to make it easier to build SetCC's if you just
500  /// have an ISD::CondCode instead of an SDValue.
501  ///
502  SDValue getSetCC(DebugLoc DL, EVT VT, SDValue LHS, SDValue RHS,
503                   ISD::CondCode Cond) {
504    return getNode(ISD::SETCC, DL, VT, LHS, RHS, getCondCode(Cond));
505  }
506
507  /// getVSetCC - Helper function to make it easier to build VSetCC's nodes
508  /// if you just have an ISD::CondCode instead of an SDValue.
509  ///
510  SDValue getVSetCC(DebugLoc DL, EVT VT, SDValue LHS, SDValue RHS,
511                    ISD::CondCode Cond) {
512    return getNode(ISD::VSETCC, DL, VT, LHS, RHS, getCondCode(Cond));
513  }
514
515  /// getSelectCC - Helper function to make it easier to build SelectCC's if you
516  /// just have an ISD::CondCode instead of an SDValue.
517  ///
518  SDValue getSelectCC(DebugLoc DL, SDValue LHS, SDValue RHS,
519                      SDValue True, SDValue False, ISD::CondCode Cond) {
520    return getNode(ISD::SELECT_CC, DL, True.getValueType(),
521                   LHS, RHS, True, False, getCondCode(Cond));
522  }
523
524  /// getVAArg - VAArg produces a result and token chain, and takes a pointer
525  /// and a source value as input.
526  SDValue getVAArg(EVT VT, DebugLoc dl, SDValue Chain, SDValue Ptr,
527                   SDValue SV);
528
529  /// getAtomic - Gets a node for an atomic op, produces result and chain and
530  /// takes 3 operands
531  SDValue getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, SDValue Chain,
532                    SDValue Ptr, SDValue Cmp, SDValue Swp, const Value* PtrVal,
533                    unsigned Alignment=0);
534  SDValue getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, SDValue Chain,
535                    SDValue Ptr, SDValue Cmp, SDValue Swp,
536                    MachineMemOperand *MMO);
537
538  /// getAtomic - Gets a node for an atomic op, produces result and chain and
539  /// takes 2 operands.
540  SDValue getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, SDValue Chain,
541                    SDValue Ptr, SDValue Val, const Value* PtrVal,
542                    unsigned Alignment = 0);
543  SDValue getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, SDValue Chain,
544                    SDValue Ptr, SDValue Val,
545                    MachineMemOperand *MMO);
546
547  /// getMemIntrinsicNode - Creates a MemIntrinsicNode that may produce a
548  /// result and takes a list of operands. Opcode may be INTRINSIC_VOID,
549  /// INTRINSIC_W_CHAIN, or a target-specific opcode with a value not
550  /// less than FIRST_TARGET_MEMORY_OPCODE.
551  SDValue getMemIntrinsicNode(unsigned Opcode, DebugLoc dl,
552                              const EVT *VTs, unsigned NumVTs,
553                              const SDValue *Ops, unsigned NumOps,
554                              EVT MemVT, const Value *srcValue, int SVOff,
555                              unsigned Align = 0, bool Vol = false,
556                              bool ReadMem = true, bool WriteMem = true);
557
558  SDValue getMemIntrinsicNode(unsigned Opcode, DebugLoc dl, SDVTList VTList,
559                              const SDValue *Ops, unsigned NumOps,
560                              EVT MemVT, const Value *srcValue, int SVOff,
561                              unsigned Align = 0, bool Vol = false,
562                              bool ReadMem = true, bool WriteMem = true);
563
564  SDValue getMemIntrinsicNode(unsigned Opcode, DebugLoc dl, SDVTList VTList,
565                              const SDValue *Ops, unsigned NumOps,
566                              EVT MemVT, MachineMemOperand *MMO);
567
568  /// getMergeValues - Create a MERGE_VALUES node from the given operands.
569  SDValue getMergeValues(const SDValue *Ops, unsigned NumOps, DebugLoc dl);
570
571  /// getLoad - Loads are not normal binary operators: their result type is not
572  /// determined by their operands, and they produce a value AND a token chain.
573  ///
574  SDValue getLoad(EVT VT, DebugLoc dl, SDValue Chain, SDValue Ptr,
575                    const Value *SV, int SVOffset, bool isVolatile=false,
576                    unsigned Alignment=0);
577  SDValue getExtLoad(ISD::LoadExtType ExtType, DebugLoc dl, EVT VT,
578                       SDValue Chain, SDValue Ptr, const Value *SV,
579                       int SVOffset, EVT MemVT, bool isVolatile=false,
580                       unsigned Alignment=0);
581  SDValue getIndexedLoad(SDValue OrigLoad, DebugLoc dl, SDValue Base,
582                           SDValue Offset, ISD::MemIndexedMode AM);
583  SDValue getLoad(ISD::MemIndexedMode AM, DebugLoc dl, ISD::LoadExtType ExtType,
584                  EVT VT, SDValue Chain, SDValue Ptr, SDValue Offset,
585                  const Value *SV, int SVOffset, EVT MemVT,
586                  bool isVolatile=false, unsigned Alignment=0);
587  SDValue getLoad(ISD::MemIndexedMode AM, DebugLoc dl, ISD::LoadExtType ExtType,
588                  EVT VT, SDValue Chain, SDValue Ptr, SDValue Offset,
589                  EVT MemVT, MachineMemOperand *MMO);
590
591  /// getStore - Helper function to build ISD::STORE nodes.
592  ///
593  SDValue getStore(SDValue Chain, DebugLoc dl, SDValue Val, SDValue Ptr,
594                     const Value *SV, int SVOffset, bool isVolatile=false,
595                     unsigned Alignment=0);
596  SDValue getStore(SDValue Chain, DebugLoc dl, SDValue Val, SDValue Ptr,
597                   MachineMemOperand *MMO);
598  SDValue getTruncStore(SDValue Chain, DebugLoc dl, SDValue Val, SDValue Ptr,
599                          const Value *SV, int SVOffset, EVT TVT,
600                          bool isVolatile=false, unsigned Alignment=0);
601  SDValue getTruncStore(SDValue Chain, DebugLoc dl, SDValue Val, SDValue Ptr,
602                        EVT TVT, MachineMemOperand *MMO);
603  SDValue getIndexedStore(SDValue OrigStoe, DebugLoc dl, SDValue Base,
604                           SDValue Offset, ISD::MemIndexedMode AM);
605
606  /// getSrcValue - Construct a node to track a Value* through the backend.
607  SDValue getSrcValue(const Value *v);
608
609  /// getShiftAmountOperand - Return the specified value casted to
610  /// the target's desired shift amount type.
611  SDValue getShiftAmountOperand(SDValue Op);
612
613  /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
614  /// specified operands.  If the resultant node already exists in the DAG,
615  /// this does not modify the specified node, instead it returns the node that
616  /// already exists.  If the resultant node does not exist in the DAG, the
617  /// input node is returned.  As a degenerate case, if you specify the same
618  /// input operands as the node already has, the input node is returned.
619  SDValue UpdateNodeOperands(SDValue N, SDValue Op);
620  SDValue UpdateNodeOperands(SDValue N, SDValue Op1, SDValue Op2);
621  SDValue UpdateNodeOperands(SDValue N, SDValue Op1, SDValue Op2,
622                               SDValue Op3);
623  SDValue UpdateNodeOperands(SDValue N, SDValue Op1, SDValue Op2,
624                               SDValue Op3, SDValue Op4);
625  SDValue UpdateNodeOperands(SDValue N, SDValue Op1, SDValue Op2,
626                               SDValue Op3, SDValue Op4, SDValue Op5);
627  SDValue UpdateNodeOperands(SDValue N,
628                               const SDValue *Ops, unsigned NumOps);
629
630  /// SelectNodeTo - These are used for target selectors to *mutate* the
631  /// specified node to have the specified return type, Target opcode, and
632  /// operands.  Note that target opcodes are stored as
633  /// ~TargetOpcode in the node opcode field.  The resultant node is returned.
634  SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT);
635  SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT, SDValue Op1);
636  SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT,
637                       SDValue Op1, SDValue Op2);
638  SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT,
639                       SDValue Op1, SDValue Op2, SDValue Op3);
640  SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT,
641                       const SDValue *Ops, unsigned NumOps);
642  SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1, EVT VT2);
643  SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
644                       EVT VT2, const SDValue *Ops, unsigned NumOps);
645  SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
646                       EVT VT2, EVT VT3, const SDValue *Ops, unsigned NumOps);
647  SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT1,
648                       EVT VT2, EVT VT3, EVT VT4, const SDValue *Ops,
649                       unsigned NumOps);
650  SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
651                       EVT VT2, SDValue Op1);
652  SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
653                       EVT VT2, SDValue Op1, SDValue Op2);
654  SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
655                       EVT VT2, SDValue Op1, SDValue Op2, SDValue Op3);
656  SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
657                       EVT VT2, EVT VT3, SDValue Op1, SDValue Op2, SDValue Op3);
658  SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, SDVTList VTs,
659                       const SDValue *Ops, unsigned NumOps);
660
661  /// MorphNodeTo - These *mutate* the specified node to have the specified
662  /// return type, opcode, and operands.
663  SDNode *MorphNodeTo(SDNode *N, unsigned Opc, EVT VT);
664  SDNode *MorphNodeTo(SDNode *N, unsigned Opc, EVT VT, SDValue Op1);
665  SDNode *MorphNodeTo(SDNode *N, unsigned Opc, EVT VT,
666                      SDValue Op1, SDValue Op2);
667  SDNode *MorphNodeTo(SDNode *N, unsigned Opc, EVT VT,
668                      SDValue Op1, SDValue Op2, SDValue Op3);
669  SDNode *MorphNodeTo(SDNode *N, unsigned Opc, EVT VT,
670                      const SDValue *Ops, unsigned NumOps);
671  SDNode *MorphNodeTo(SDNode *N, unsigned Opc, EVT VT1, EVT VT2);
672  SDNode *MorphNodeTo(SDNode *N, unsigned Opc, EVT VT1,
673                      EVT VT2, const SDValue *Ops, unsigned NumOps);
674  SDNode *MorphNodeTo(SDNode *N, unsigned Opc, EVT VT1,
675                      EVT VT2, EVT VT3, const SDValue *Ops, unsigned NumOps);
676  SDNode *MorphNodeTo(SDNode *N, unsigned Opc, EVT VT1,
677                      EVT VT2, SDValue Op1);
678  SDNode *MorphNodeTo(SDNode *N, unsigned Opc, EVT VT1,
679                      EVT VT2, SDValue Op1, SDValue Op2);
680  SDNode *MorphNodeTo(SDNode *N, unsigned Opc, EVT VT1,
681                      EVT VT2, SDValue Op1, SDValue Op2, SDValue Op3);
682  SDNode *MorphNodeTo(SDNode *N, unsigned Opc, SDVTList VTs,
683                      const SDValue *Ops, unsigned NumOps);
684
685  /// getMachineNode - These are used for target selectors to create a new node
686  /// with specified return type(s), MachineInstr opcode, and operands.
687  ///
688  /// Note that getMachineNode returns the resultant node.  If there is already
689  /// a node of the specified opcode and operands, it returns that node instead
690  /// of the current one.
691  MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT);
692  MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT,
693                                SDValue Op1);
694  MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT,
695                                SDValue Op1, SDValue Op2);
696  MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT,
697                         SDValue Op1, SDValue Op2, SDValue Op3);
698  MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT,
699                         const SDValue *Ops, unsigned NumOps);
700  MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2);
701  MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2,
702                         SDValue Op1);
703  MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1,
704                         EVT VT2, SDValue Op1, SDValue Op2);
705  MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1,
706                         EVT VT2, SDValue Op1, SDValue Op2, SDValue Op3);
707  MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2,
708                         const SDValue *Ops, unsigned NumOps);
709  MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2,
710                         EVT VT3, SDValue Op1, SDValue Op2);
711  MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2,
712                         EVT VT3, SDValue Op1, SDValue Op2, SDValue Op3);
713  MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2,
714                         EVT VT3, const SDValue *Ops, unsigned NumOps);
715  MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2,
716                         EVT VT3, EVT VT4, const SDValue *Ops, unsigned NumOps);
717  MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl,
718                         const std::vector<EVT> &ResultTys, const SDValue *Ops,
719                         unsigned NumOps);
720  MachineSDNode *getMachineNode(unsigned Opcode, DebugLoc dl, SDVTList VTs,
721                         const SDValue *Ops, unsigned NumOps);
722
723  /// getTargetExtractSubreg - A convenience function for creating
724  /// TargetInstrInfo::EXTRACT_SUBREG nodes.
725  SDValue getTargetExtractSubreg(int SRIdx, DebugLoc DL, EVT VT,
726                                 SDValue Operand);
727
728  /// getTargetInsertSubreg - A convenience function for creating
729  /// TargetInstrInfo::INSERT_SUBREG nodes.
730  SDValue getTargetInsertSubreg(int SRIdx, DebugLoc DL, EVT VT,
731                                SDValue Operand, SDValue Subreg);
732
733  /// getNodeIfExists - Get the specified node if it's already available, or
734  /// else return NULL.
735  SDNode *getNodeIfExists(unsigned Opcode, SDVTList VTs,
736                          const SDValue *Ops, unsigned NumOps);
737
738  /// DAGUpdateListener - Clients of various APIs that cause global effects on
739  /// the DAG can optionally implement this interface.  This allows the clients
740  /// to handle the various sorts of updates that happen.
741  class DAGUpdateListener {
742  public:
743    virtual ~DAGUpdateListener();
744
745    /// NodeDeleted - The node N that was deleted and, if E is not null, an
746    /// equivalent node E that replaced it.
747    virtual void NodeDeleted(SDNode *N, SDNode *E) = 0;
748
749    /// NodeUpdated - The node N that was updated.
750    virtual void NodeUpdated(SDNode *N) = 0;
751  };
752
753  /// RemoveDeadNode - Remove the specified node from the system. If any of its
754  /// operands then becomes dead, remove them as well. Inform UpdateListener
755  /// for each node deleted.
756  void RemoveDeadNode(SDNode *N, DAGUpdateListener *UpdateListener = 0);
757
758  /// RemoveDeadNodes - This method deletes the unreachable nodes in the
759  /// given list, and any nodes that become unreachable as a result.
760  void RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes,
761                       DAGUpdateListener *UpdateListener = 0);
762
763  /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
764  /// This can cause recursive merging of nodes in the DAG.  Use the first
765  /// version if 'From' is known to have a single result, use the second
766  /// if you have two nodes with identical results (or if 'To' has a superset
767  /// of the results of 'From'), use the third otherwise.
768  ///
769  /// These methods all take an optional UpdateListener, which (if not null) is
770  /// informed about nodes that are deleted and modified due to recursive
771  /// changes in the dag.
772  ///
773  /// These functions only replace all existing uses. It's possible that as
774  /// these replacements are being performed, CSE may cause the From node
775  /// to be given new uses. These new uses of From are left in place, and
776  /// not automatically transfered to To.
777  ///
778  void ReplaceAllUsesWith(SDValue From, SDValue Op,
779                          DAGUpdateListener *UpdateListener = 0);
780  void ReplaceAllUsesWith(SDNode *From, SDNode *To,
781                          DAGUpdateListener *UpdateListener = 0);
782  void ReplaceAllUsesWith(SDNode *From, const SDValue *To,
783                          DAGUpdateListener *UpdateListener = 0);
784
785  /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
786  /// uses of other values produced by From.Val alone.
787  void ReplaceAllUsesOfValueWith(SDValue From, SDValue To,
788                                 DAGUpdateListener *UpdateListener = 0);
789
790  /// ReplaceAllUsesOfValuesWith - Like ReplaceAllUsesOfValueWith, but
791  /// for multiple values at once. This correctly handles the case where
792  /// there is an overlap between the From values and the To values.
793  void ReplaceAllUsesOfValuesWith(const SDValue *From, const SDValue *To,
794                                  unsigned Num,
795                                  DAGUpdateListener *UpdateListener = 0);
796
797  /// AssignTopologicalOrder - Topological-sort the AllNodes list and a
798  /// assign a unique node id for each node in the DAG based on their
799  /// topological order. Returns the number of nodes.
800  unsigned AssignTopologicalOrder();
801
802  /// RepositionNode - Move node N in the AllNodes list to be immediately
803  /// before the given iterator Position. This may be used to update the
804  /// topological ordering when the list of nodes is modified.
805  void RepositionNode(allnodes_iterator Position, SDNode *N) {
806    AllNodes.insert(Position, AllNodes.remove(N));
807  }
808
809  /// isCommutativeBinOp - Returns true if the opcode is a commutative binary
810  /// operation.
811  static bool isCommutativeBinOp(unsigned Opcode) {
812    // FIXME: This should get its info from the td file, so that we can include
813    // target info.
814    switch (Opcode) {
815    case ISD::ADD:
816    case ISD::MUL:
817    case ISD::MULHU:
818    case ISD::MULHS:
819    case ISD::SMUL_LOHI:
820    case ISD::UMUL_LOHI:
821    case ISD::FADD:
822    case ISD::FMUL:
823    case ISD::AND:
824    case ISD::OR:
825    case ISD::XOR:
826    case ISD::SADDO:
827    case ISD::UADDO:
828    case ISD::ADDC:
829    case ISD::ADDE: return true;
830    default: return false;
831    }
832  }
833
834  /// AssignOrdering - Assign an order to the SDNode.
835  void AssignOrdering(SDNode *SD, unsigned Order);
836
837  void dump() const;
838
839  /// CreateStackTemporary - Create a stack temporary, suitable for holding the
840  /// specified value type.  If minAlign is specified, the slot size will have
841  /// at least that alignment.
842  SDValue CreateStackTemporary(EVT VT, unsigned minAlign = 1);
843
844  /// CreateStackTemporary - Create a stack temporary suitable for holding
845  /// either of the specified value types.
846  SDValue CreateStackTemporary(EVT VT1, EVT VT2);
847
848  /// FoldConstantArithmetic -
849  SDValue FoldConstantArithmetic(unsigned Opcode,
850                                 EVT VT,
851                                 ConstantSDNode *Cst1,
852                                 ConstantSDNode *Cst2);
853
854  /// FoldSetCC - Constant fold a setcc to true or false.
855  SDValue FoldSetCC(EVT VT, SDValue N1,
856                    SDValue N2, ISD::CondCode Cond, DebugLoc dl);
857
858  /// SignBitIsZero - Return true if the sign bit of Op is known to be zero.  We
859  /// use this predicate to simplify operations downstream.
860  bool SignBitIsZero(SDValue Op, unsigned Depth = 0) const;
861
862  /// MaskedValueIsZero - Return true if 'Op & Mask' is known to be zero.  We
863  /// use this predicate to simplify operations downstream.  Op and Mask are
864  /// known to be the same type.
865  bool MaskedValueIsZero(SDValue Op, const APInt &Mask, unsigned Depth = 0)
866    const;
867
868  /// ComputeMaskedBits - Determine which of the bits specified in Mask are
869  /// known to be either zero or one and return them in the KnownZero/KnownOne
870  /// bitsets.  This code only analyzes bits in Mask, in order to short-circuit
871  /// processing.  Targets can implement the computeMaskedBitsForTargetNode
872  /// method in the TargetLowering class to allow target nodes to be understood.
873  void ComputeMaskedBits(SDValue Op, const APInt &Mask, APInt &KnownZero,
874                         APInt &KnownOne, unsigned Depth = 0) const;
875
876  /// ComputeNumSignBits - Return the number of times the sign bit of the
877  /// register is replicated into the other bits.  We know that at least 1 bit
878  /// is always equal to the sign bit (itself), but other cases can give us
879  /// information.  For example, immediately after an "SRA X, 2", we know that
880  /// the top 3 bits are all equal to each other, so we return 3.  Targets can
881  /// implement the ComputeNumSignBitsForTarget method in the TargetLowering
882  /// class to allow target nodes to be understood.
883  unsigned ComputeNumSignBits(SDValue Op, unsigned Depth = 0) const;
884
885  /// isKnownNeverNan - Test whether the given SDValue is known to never be NaN.
886  bool isKnownNeverNaN(SDValue Op) const;
887
888  /// isVerifiedDebugInfoDesc - Returns true if the specified SDValue has
889  /// been verified as a debug information descriptor.
890  bool isVerifiedDebugInfoDesc(SDValue Op) const;
891
892  /// getShuffleScalarElt - Returns the scalar element that will make up the ith
893  /// element of the result of the vector shuffle.
894  SDValue getShuffleScalarElt(const ShuffleVectorSDNode *N, unsigned Idx);
895
896  /// UnrollVectorOp - Utility function used by legalize and lowering to
897  /// "unroll" a vector operation by splitting out the scalars and operating
898  /// on each element individually.  If the ResNE is 0, fully unroll the vector
899  /// op. If ResNE is less than the width of the vector op, unroll up to ResNE.
900  /// If the  ResNE is greater than the width of the vector op, unroll the
901  /// vector op and fill the end of the resulting vector with UNDEFS.
902  SDValue UnrollVectorOp(SDNode *N, unsigned ResNE = 0);
903
904  /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
905  /// location that is 'Dist' units away from the location that the 'Base' load
906  /// is loading from.
907  bool isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
908                         unsigned Bytes, int Dist) const;
909
910  /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
911  /// it cannot be inferred.
912  unsigned InferPtrAlignment(SDValue Ptr) const;
913
914private:
915  bool RemoveNodeFromCSEMaps(SDNode *N);
916  void AddModifiedNodeToCSEMaps(SDNode *N, DAGUpdateListener *UpdateListener);
917  SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op, void *&InsertPos);
918  SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op1, SDValue Op2,
919                               void *&InsertPos);
920  SDNode *FindModifiedNodeSlot(SDNode *N, const SDValue *Ops, unsigned NumOps,
921                               void *&InsertPos);
922
923  void DeleteNodeNotInCSEMaps(SDNode *N);
924  void DeallocateNode(SDNode *N);
925
926  unsigned getEVTAlignment(EVT MemoryVT) const;
927
928  void allnodes_clear();
929
930  /// VTList - List of non-single value types.
931  std::vector<SDVTList> VTList;
932
933  /// CondCodeNodes - Maps to auto-CSE operations.
934  std::vector<CondCodeSDNode*> CondCodeNodes;
935
936  std::vector<SDNode*> ValueTypeNodes;
937  std::map<EVT, SDNode*, EVT::compareRawBits> ExtendedValueTypeNodes;
938  StringMap<SDNode*> ExternalSymbols;
939
940  std::map<std::pair<std::string, unsigned char>,SDNode*> TargetExternalSymbols;
941};
942
943template <> struct GraphTraits<SelectionDAG*> : public GraphTraits<SDNode*> {
944  typedef SelectionDAG::allnodes_iterator nodes_iterator;
945  static nodes_iterator nodes_begin(SelectionDAG *G) {
946    return G->allnodes_begin();
947  }
948  static nodes_iterator nodes_end(SelectionDAG *G) {
949    return G->allnodes_end();
950  }
951};
952
953}  // end namespace llvm
954
955#endif
956