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   typedef DenseMap<const SDNode*, SmallVector<SDDbgValue*, 2> > DbgValMapType;
  76   DbgValMapType DbgValMap;
  77
  78   void operator=(const SDDbgInfo&) LLVM_DELETED_FUNCTION;
  79   SDDbgInfo(const SDDbgInfo&) LLVM_DELETED_FUNCTION;
  80 public:
  81   SDDbgInfo() {}
  82
  83   void add(SDDbgValue *V, const SDNode *Node, bool isParameter) {
  84     if (isParameter) {
  85       ByvalParmDbgValues.push_back(V);
  86     } else     DbgValues.push_back(V);
  87     if (Node)
  88       DbgValMap[Node].push_back(V);
  89   }
  90
  91   void clear() {
  92     DbgValMap.clear();
  93     DbgValues.clear();
  94     ByvalParmDbgValues.clear();
  95   }
  96
  97   bool empty() const {
  98     return DbgValues.empty() && ByvalParmDbgValues.empty();
  99   }
 100
 101   ArrayRef<SDDbgValue*> getSDDbgValues(const SDNode *Node) {
 102     DbgValMapType::iterator I = DbgValMap.find(Node);
 103     if (I != DbgValMap.end())
 104       return I->second;
 105     return ArrayRef<SDDbgValue*>();
 106   }
 107
 108   typedef SmallVectorImpl<SDDbgValue*>::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   /// getAtomic - Gets a node for an atomic op, produces result and chain and
 681   /// takes N operands.
 682   SDValue getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTList,
 683                     SDValue* Ops, unsigned NumOps, MachineMemOperand *MMO,
 684                     AtomicOrdering Ordering,
 685                     SynchronizationScope SynchScope);
 686
 687   /// getMemIntrinsicNode - Creates a MemIntrinsicNode that may produce a
 688   /// result and takes a list of operands. Opcode may be INTRINSIC_VOID,
 689   /// INTRINSIC_W_CHAIN, or a target-specific opcode with a value not
 690   /// less than FIRST_TARGET_MEMORY_OPCODE.
 691   SDValue getMemIntrinsicNode(unsigned Opcode, SDLoc dl,
 692                               const EVT *VTs, unsigned NumVTs,
 693                               const SDValue *Ops, unsigned NumOps,
 694                               EVT MemVT, MachinePointerInfo PtrInfo,
 695                               unsigned Align = 0, bool Vol = false,
 696                               bool ReadMem = true, bool WriteMem = true);
 697
 698   SDValue getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
 699                               const SDValue *Ops, unsigned NumOps,
 700                               EVT MemVT, MachinePointerInfo PtrInfo,
 701                               unsigned Align = 0, bool Vol = false,
 702                               bool ReadMem = true, bool WriteMem = true);
 703
 704   SDValue getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
 705                               const SDValue *Ops, unsigned NumOps,
 706                               EVT MemVT, MachineMemOperand *MMO);
 707
 708   /// getMergeValues - Create a MERGE_VALUES node from the given operands.
 709   SDValue getMergeValues(const SDValue *Ops, unsigned NumOps, SDLoc dl);
 710
 711   /// getLoad - Loads are not normal binary operators: their result type is not
 712   /// determined by their operands, and they produce a value AND a token chain.
 713   ///
 714   SDValue getLoad(EVT VT, SDLoc dl, SDValue Chain, SDValue Ptr,
 715                   MachinePointerInfo PtrInfo, bool isVolatile,
 716                   bool isNonTemporal, bool isInvariant, unsigned Alignment,
 717                   const MDNode *TBAAInfo = 0, const MDNode *Ranges = 0);
 718   SDValue getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
 719                      SDValue Chain, SDValue Ptr, MachinePointerInfo PtrInfo,
 720                      EVT MemVT, bool isVolatile,
 721                      bool isNonTemporal, unsigned Alignment,
 722                      const MDNode *TBAAInfo = 0);
 723   SDValue getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
 724                          SDValue Offset, ISD::MemIndexedMode AM);
 725   SDValue getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
 726                   EVT VT, SDLoc dl,
 727                   SDValue Chain, SDValue Ptr, SDValue Offset,
 728                   MachinePointerInfo PtrInfo, EVT MemVT,
 729                   bool isVolatile, bool isNonTemporal, bool isInvariant,
 730                   unsigned Alignment, const MDNode *TBAAInfo = 0,
 731                   const MDNode *Ranges = 0);
 732   SDValue getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
 733                   EVT VT, SDLoc dl,
 734                   SDValue Chain, SDValue Ptr, SDValue Offset,
 735                   EVT MemVT, MachineMemOperand *MMO);
 736
 737   /// getStore - Helper function to build ISD::STORE nodes.
 738   ///
 739   SDValue getStore(SDValue Chain, SDLoc dl, SDValue Val, SDValue Ptr,
 740                    MachinePointerInfo PtrInfo, bool isVolatile,
 741                    bool isNonTemporal, unsigned Alignment,
 742                    const MDNode *TBAAInfo = 0);
 743   SDValue getStore(SDValue Chain, SDLoc dl, SDValue Val, SDValue Ptr,
 744                    MachineMemOperand *MMO);
 745   SDValue getTruncStore(SDValue Chain, SDLoc dl, SDValue Val, SDValue Ptr,
 746                         MachinePointerInfo PtrInfo, EVT TVT,
 747                         bool isNonTemporal, bool isVolatile,
 748                         unsigned Alignment,
 749                         const MDNode *TBAAInfo = 0);
 750   SDValue getTruncStore(SDValue Chain, SDLoc dl, SDValue Val, SDValue Ptr,
 751                         EVT TVT, MachineMemOperand *MMO);
 752   SDValue getIndexedStore(SDValue OrigStoe, SDLoc dl, SDValue Base,
 753                            SDValue Offset, ISD::MemIndexedMode AM);
 754
 755   /// getSrcValue - Construct a node to track a Value* through the backend.
 756   SDValue getSrcValue(const Value *v);
 757
 758   /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
 759   SDValue getMDNode(const MDNode *MD);
 760
 761   /// getShiftAmountOperand - Return the specified value casted to
 762   /// the target's desired shift amount type.
 763   SDValue getShiftAmountOperand(EVT LHSTy, SDValue Op);
 764
 765   /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
 766   /// specified operands.  If the resultant node already exists in the DAG,
 767   /// this does not modify the specified node, instead it returns the node that
 768   /// already exists.  If the resultant node does not exist in the DAG, the
 769   /// input node is returned.  As a degenerate case, if you specify the same
 770   /// input operands as the node already has, the input node is returned.
 771   SDNode *UpdateNodeOperands(SDNode *N, SDValue Op);
 772   SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2);
 773   SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
 774                                SDValue Op3);
 775   SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
 776                                SDValue Op3, SDValue Op4);
 777   SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
 778                                SDValue Op3, SDValue Op4, SDValue Op5);
 779   SDNode *UpdateNodeOperands(SDNode *N,
 780                                const SDValue *Ops, unsigned NumOps);
 781
 782   /// SelectNodeTo - These are used for target selectors to *mutate* the
 783   /// specified node to have the specified return type, Target opcode, and
 784   /// operands.  Note that target opcodes are stored as
 785   /// ~TargetOpcode in the node opcode field.  The resultant node is returned.
 786   SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT);
 787   SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT, SDValue Op1);
 788   SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT,
 789                        SDValue Op1, SDValue Op2);
 790   SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT,
 791                        SDValue Op1, SDValue Op2, SDValue Op3);
 792   SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT,
 793                        const SDValue *Ops, unsigned NumOps);
 794   SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1, EVT VT2);
 795   SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
 796                        EVT VT2, const SDValue *Ops, unsigned NumOps);
 797   SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
 798                        EVT VT2, EVT VT3, const SDValue *Ops, unsigned NumOps);
 799   SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT1,
 800                        EVT VT2, EVT VT3, EVT VT4, const SDValue *Ops,
 801                        unsigned NumOps);
 802   SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
 803                        EVT VT2, SDValue Op1);
 804   SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
 805                        EVT VT2, SDValue Op1, SDValue Op2);
 806   SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
 807                        EVT VT2, SDValue Op1, SDValue Op2, SDValue Op3);
 808   SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
 809                        EVT VT2, EVT VT3, SDValue Op1, SDValue Op2, SDValue Op3);
 810   SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, SDVTList VTs,
 811                        const SDValue *Ops, unsigned NumOps);
 812
 813   /// MorphNodeTo - This *mutates* the specified node to have the specified
 814   /// return type, opcode, and operands.
 815   SDNode *MorphNodeTo(SDNode *N, unsigned Opc, SDVTList VTs,
 816                       const SDValue *Ops, unsigned NumOps);
 817
 818   /// getMachineNode - These are used for target selectors to create a new node
 819   /// with specified return type(s), MachineInstr opcode, and operands.
 820   ///
 821   /// Note that getMachineNode returns the resultant node.  If there is already
 822   /// a node of the specified opcode and operands, it returns that node instead
 823   /// of the current one.
 824   MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT);
 825   MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
 826                                 SDValue Op1);
 827   MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
 828                                 SDValue Op1, SDValue Op2);
 829   MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
 830                                 SDValue Op1, SDValue Op2, SDValue Op3);
 831   MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
 832                                 ArrayRef<SDValue> Ops);
 833   MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2);
 834   MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
 835                                 SDValue Op1);
 836   MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
 837                                 SDValue Op1, SDValue Op2);
 838   MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
 839                                 SDValue Op1, SDValue Op2, SDValue Op3);
 840   MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
 841                                 ArrayRef<SDValue> Ops);
 842   MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
 843                                 EVT VT3, SDValue Op1, SDValue Op2);
 844   MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
 845                                 EVT VT3, SDValue Op1, SDValue Op2,
 846                                 SDValue Op3);
 847   MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
 848                                 EVT VT3, ArrayRef<SDValue> Ops);
 849   MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
 850                                 EVT VT3, EVT VT4, ArrayRef<SDValue> Ops);
 851   MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl,
 852                                 ArrayRef<EVT> ResultTys,
 853                                 ArrayRef<SDValue> Ops);
 854   MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, SDVTList VTs,
 855                                 ArrayRef<SDValue> Ops);
 856
 857   /// getTargetExtractSubreg - A convenience function for creating
 858   /// TargetInstrInfo::EXTRACT_SUBREG nodes.
 859   SDValue getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
 860                                  SDValue Operand);
 861
 862   /// getTargetInsertSubreg - A convenience function for creating
 863   /// TargetInstrInfo::INSERT_SUBREG nodes.
 864   SDValue getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
 865                                 SDValue Operand, SDValue Subreg);
 866
 867   /// getNodeIfExists - Get the specified node if it's already available, or
 868   /// else return NULL.
 869   SDNode *getNodeIfExists(unsigned Opcode, SDVTList VTs,
 870                           const SDValue *Ops, unsigned NumOps);
 871
 872   /// getDbgValue - Creates a SDDbgValue node.
 873   ///
 874   SDDbgValue *getDbgValue(MDNode *MDPtr, SDNode *N, unsigned R, uint64_t Off,
 875                           DebugLoc DL, unsigned O);
 876   SDDbgValue *getDbgValue(MDNode *MDPtr, const Value *C, uint64_t Off,
 877                           DebugLoc DL, unsigned O);
 878   SDDbgValue *getDbgValue(MDNode *MDPtr, unsigned FI, uint64_t Off,
 879                           DebugLoc DL, unsigned O);
 880
 881   /// RemoveDeadNode - Remove the specified node from the system. If any of its
 882   /// operands then becomes dead, remove them as well. Inform UpdateListener
 883   /// for each node deleted.
 884   void RemoveDeadNode(SDNode *N);
 885
 886   /// RemoveDeadNodes - This method deletes the unreachable nodes in the
 887   /// given list, and any nodes that become unreachable as a result.
 888   void RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes);
 889
 890   /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
 891   /// This can cause recursive merging of nodes in the DAG.  Use the first
 892   /// version if 'From' is known to have a single result, use the second
 893   /// if you have two nodes with identical results (or if 'To' has a superset
 894   /// of the results of 'From'), use the third otherwise.
 895   ///
 896   /// These methods all take an optional UpdateListener, which (if not null) is
 897   /// informed about nodes that are deleted and modified due to recursive
 898   /// changes in the dag.
 899   ///
 900   /// These functions only replace all existing uses. It's possible that as
 901   /// these replacements are being performed, CSE may cause the From node
 902   /// to be given new uses. These new uses of From are left in place, and
 903   /// not automatically transferred to To.
 904   ///
 905   void ReplaceAllUsesWith(SDValue From, SDValue Op);
 906   void ReplaceAllUsesWith(SDNode *From, SDNode *To);
 907   void ReplaceAllUsesWith(SDNode *From, const SDValue *To);
 908
 909   /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
 910   /// uses of other values produced by From.Val alone.
 911   void ReplaceAllUsesOfValueWith(SDValue From, SDValue To);
 912
 913   /// ReplaceAllUsesOfValuesWith - Like ReplaceAllUsesOfValueWith, but
 914   /// for multiple values at once. This correctly handles the case where
 915   /// there is an overlap between the From values and the To values.
 916   void ReplaceAllUsesOfValuesWith(const SDValue *From, const SDValue *To,
 917                                   unsigned Num);
 918
 919   /// AssignTopologicalOrder - Topological-sort the AllNodes list and a
 920   /// assign a unique node id for each node in the DAG based on their
 921   /// topological order. Returns the number of nodes.
 922   unsigned AssignTopologicalOrder();
 923
 924   /// RepositionNode - Move node N in the AllNodes list to be immediately
 925   /// before the given iterator Position. This may be used to update the
 926   /// topological ordering when the list of nodes is modified.
 927   void RepositionNode(allnodes_iterator Position, SDNode *N) {
 928     AllNodes.insert(Position, AllNodes.remove(N));
 929   }
 930
 931   /// isCommutativeBinOp - Returns true if the opcode is a commutative binary
 932   /// operation.
 933   static bool isCommutativeBinOp(unsigned Opcode) {
 934     // FIXME: This should get its info from the td file, so that we can include
 935     // target info.
 936     switch (Opcode) {
 937     case ISD::ADD:
 938     case ISD::MUL:
 939     case ISD::MULHU:
 940     case ISD::MULHS:
 941     case ISD::SMUL_LOHI:
 942     case ISD::UMUL_LOHI:
 943     case ISD::FADD:
 944     case ISD::FMUL:
 945     case ISD::AND:
 946     case ISD::OR:
 947     case ISD::XOR:
 948     case ISD::SADDO:
 949     case ISD::UADDO:
 950     case ISD::ADDC:
 951     case ISD::ADDE: return true;
 952     default: return false;
 953     }
 954   }
 955
 956   /// Returns an APFloat semantics tag appropriate for the given type. If VT is
 957   /// a vector type, the element semantics are returned.
 958   static const fltSemantics &EVTToAPFloatSemantics(EVT VT) {
 959     switch (VT.getScalarType().getSimpleVT().SimpleTy) {
 960     default: llvm_unreachable("Unknown FP format");
 961     case MVT::f16:     return APFloat::IEEEhalf;
 962     case MVT::f32:     return APFloat::IEEEsingle;
 963     case MVT::f64:     return APFloat::IEEEdouble;
 964     case MVT::f80:     return APFloat::x87DoubleExtended;
 965     case MVT::f128:    return APFloat::IEEEquad;
 966     case MVT::ppcf128: return APFloat::PPCDoubleDouble;
 967     }
 968   }
 969
 970   /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
 971   /// value is produced by SD.
 972   void AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter);
 973
 974   /// GetDbgValues - Get the debug values which reference the given SDNode.
 975   ArrayRef<SDDbgValue*> GetDbgValues(const SDNode* SD) {
 976     return DbgInfo->getSDDbgValues(SD);
 977   }
 978
 979   /// TransferDbgValues - Transfer SDDbgValues.
 980   void TransferDbgValues(SDValue From, SDValue To);
 981
 982   /// hasDebugValues - Return true if there are any SDDbgValue nodes associated
 983   /// with this SelectionDAG.
 984   bool hasDebugValues() const { return !DbgInfo->empty(); }
 985
 986   SDDbgInfo::DbgIterator DbgBegin() { return DbgInfo->DbgBegin(); }
 987   SDDbgInfo::DbgIterator DbgEnd()   { return DbgInfo->DbgEnd(); }
 988   SDDbgInfo::DbgIterator ByvalParmDbgBegin() {
 989     return DbgInfo->ByvalParmDbgBegin();
 990   }
 991   SDDbgInfo::DbgIterator ByvalParmDbgEnd()   {
 992     return DbgInfo->ByvalParmDbgEnd();
 993   }
 994
 995   void dump() const;
 996
 997   /// CreateStackTemporary - Create a stack temporary, suitable for holding the
 998   /// specified value type.  If minAlign is specified, the slot size will have
 999   /// at least that alignment.
1000   SDValue CreateStackTemporary(EVT VT, unsigned minAlign = 1);
1001
1002   /// CreateStackTemporary - Create a stack temporary suitable for holding
1003   /// either of the specified value types.
1004   SDValue CreateStackTemporary(EVT VT1, EVT VT2);
1005
1006   /// FoldConstantArithmetic -
1007   SDValue FoldConstantArithmetic(unsigned Opcode, EVT VT,
1008                                  SDNode *Cst1, SDNode *Cst2);
1009
1010   /// FoldSetCC - Constant fold a setcc to true or false.
1011   SDValue FoldSetCC(EVT VT, SDValue N1,
1012                     SDValue N2, ISD::CondCode Cond, SDLoc dl);
1013
1014   /// SignBitIsZero - Return true if the sign bit of Op is known to be zero.  We
1015   /// use this predicate to simplify operations downstream.
1016   bool SignBitIsZero(SDValue Op, unsigned Depth = 0) const;
1017
1018   /// MaskedValueIsZero - Return true if 'Op & Mask' is known to be zero.  We
1019   /// use this predicate to simplify operations downstream.  Op and Mask are
1020   /// known to be the same type.
1021   bool MaskedValueIsZero(SDValue Op, const APInt &Mask, unsigned Depth = 0)
1022     const;
1023
1024   /// ComputeMaskedBits - Determine which of the bits specified in Mask are
1025   /// known to be either zero or one and return them in the KnownZero/KnownOne
1026   /// bitsets.  This code only analyzes bits in Mask, in order to short-circuit
1027   /// processing.  Targets can implement the computeMaskedBitsForTargetNode
1028   /// method in the TargetLowering class to allow target nodes to be understood.
1029   void ComputeMaskedBits(SDValue Op, APInt &KnownZero, APInt &KnownOne,
1030                          unsigned Depth = 0) const;
1031
1032   /// ComputeNumSignBits - Return the number of times the sign bit of the
1033   /// register is replicated into the other bits.  We know that at least 1 bit
1034   /// is always equal to the sign bit (itself), but other cases can give us
1035   /// information.  For example, immediately after an "SRA X, 2", we know that
1036   /// the top 3 bits are all equal to each other, so we return 3.  Targets can
1037   /// implement the ComputeNumSignBitsForTarget method in the TargetLowering
1038   /// class to allow target nodes to be understood.
1039   unsigned ComputeNumSignBits(SDValue Op, unsigned Depth = 0) const;
1040
1041   /// isBaseWithConstantOffset - Return true if the specified operand is an
1042   /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
1043   /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
1044   /// semantics as an ADD.  This handles the equivalence:
1045   ///     X|Cst == X+Cst iff X&Cst = 0.
1046   bool isBaseWithConstantOffset(SDValue Op) const;
1047
1048   /// isKnownNeverNan - Test whether the given SDValue is known to never be NaN.
1049   bool isKnownNeverNaN(SDValue Op) const;
1050
1051   /// isKnownNeverZero - Test whether the given SDValue is known to never be
1052   /// positive or negative Zero.
1053   bool isKnownNeverZero(SDValue Op) const;
1054
1055   /// isEqualTo - Test whether two SDValues are known to compare equal. This
1056   /// is true if they are the same value, or if one is negative zero and the
1057   /// other positive zero.
1058   bool isEqualTo(SDValue A, SDValue B) const;
1059
1060   /// UnrollVectorOp - Utility function used by legalize and lowering to
1061   /// "unroll" a vector operation by splitting out the scalars and operating
1062   /// on each element individually.  If the ResNE is 0, fully unroll the vector
1063   /// op. If ResNE is less than the width of the vector op, unroll up to ResNE.
1064   /// If the  ResNE is greater than the width of the vector op, unroll the
1065   /// vector op and fill the end of the resulting vector with UNDEFS.
1066   SDValue UnrollVectorOp(SDNode *N, unsigned ResNE = 0);
1067
1068   /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
1069   /// location that is 'Dist' units away from the location that the 'Base' load
1070   /// is loading from.
1071   bool isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
1072                          unsigned Bytes, int Dist) const;
1073
1074   /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
1075   /// it cannot be inferred.
1076   unsigned InferPtrAlignment(SDValue Ptr) const;
1077
1078 private:
1079   bool RemoveNodeFromCSEMaps(SDNode *N);
1080   void AddModifiedNodeToCSEMaps(SDNode *N);
1081   SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op, void *&InsertPos);
1082   SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op1, SDValue Op2,
1083                                void *&InsertPos);
1084   SDNode *FindModifiedNodeSlot(SDNode *N, const SDValue *Ops, unsigned NumOps,
1085                                void *&InsertPos);
1086   SDNode *UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc loc);
1087
1088   void DeleteNodeNotInCSEMaps(SDNode *N);
1089   void DeallocateNode(SDNode *N);
1090
1091   unsigned getEVTAlignment(EVT MemoryVT) const;
1092
1093   void allnodes_clear();
1094
1095   /// VTList - List of non-single value types.
1096   std::vector<SDVTList> VTList;
1097
1098   /// CondCodeNodes - Maps to auto-CSE operations.
1099   std::vector<CondCodeSDNode*> CondCodeNodes;
1100
1101   std::vector<SDNode*> ValueTypeNodes;
1102   std::map<EVT, SDNode*, EVT::compareRawBits> ExtendedValueTypeNodes;
1103   StringMap<SDNode*> ExternalSymbols;
1104
1105   std::map<std::pair<std::string, unsigned char>,SDNode*> TargetExternalSymbols;
1106 };
1107
1108 template <> struct GraphTraits<SelectionDAG*> : public GraphTraits<SDNode*> {
1109   typedef SelectionDAG::allnodes_iterator nodes_iterator;
1110   static nodes_iterator nodes_begin(SelectionDAG *G) {
1111     return G->allnodes_begin();
1112   }
1113   static nodes_iterator nodes_end(SelectionDAG *G) {
1114     return G->allnodes_end();
1115   }
1116 };
1117
1118 }  // end namespace llvm
1119
1120 #endif