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