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