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