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