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