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