include/llvm/CodeGen/SelectionDAG.h

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