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