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