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