include/llvm/CodeGen/SelectionDAG.h

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