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