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