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