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