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