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