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