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