include/llvm/CodeGen/SelectionDAG.h

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