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   /// getBoolExtOrTrunc - Convert Op, which must be of integer type, to the
 566   /// integer type VT, by using an extension appropriate for the target's
 567   /// BooleanContent or truncating it.
 568   SDValue getBoolExtOrTrunc(SDValue Op, SDLoc SL, EVT VT);
 569
 570   /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
 571   SDValue getNOT(SDLoc DL, SDValue Val, EVT VT);
 572
 573   /// \brief Create a logical NOT operation as (XOR Val, BooleanOne).
 574   SDValue getLogicalNOT(SDLoc DL, SDValue Val, EVT VT);
 575
 576   /// getCALLSEQ_START - Return a new CALLSEQ_START node, which always must have
 577   /// a glue result (to ensure it's not CSE'd).  CALLSEQ_START does not have a
 578   /// useful SDLoc.
 579   SDValue getCALLSEQ_START(SDValue Chain, SDValue Op, SDLoc DL) {
 580     SDVTList VTs = getVTList(MVT::Other, MVT::Glue);
 581     SDValue Ops[] = { Chain,  Op };
 582     return getNode(ISD::CALLSEQ_START, DL, VTs, Ops);
 583   }
 584
 585   /// getCALLSEQ_END - Return a new CALLSEQ_END node, which always must have a
 586   /// glue result (to ensure it's not CSE'd).  CALLSEQ_END does not have
 587   /// a useful SDLoc.
 588   SDValue getCALLSEQ_END(SDValue Chain, SDValue Op1, SDValue Op2,
 589                            SDValue InGlue, SDLoc DL) {
 590     SDVTList NodeTys = getVTList(MVT::Other, MVT::Glue);
 591     SmallVector<SDValue, 4> Ops;
 592     Ops.push_back(Chain);
 593     Ops.push_back(Op1);
 594     Ops.push_back(Op2);
 595     if (InGlue.getNode())
 596       Ops.push_back(InGlue);
 597     return getNode(ISD::CALLSEQ_END, DL, NodeTys, Ops);
 598   }
 599
 600   /// getUNDEF - Return an UNDEF node.  UNDEF does not have a useful SDLoc.
 601   SDValue getUNDEF(EVT VT) {
 602     return getNode(ISD::UNDEF, SDLoc(), VT);
 603   }
 604
 605   /// getGLOBAL_OFFSET_TABLE - Return a GLOBAL_OFFSET_TABLE node.  This does
 606   /// not have a useful SDLoc.
 607   SDValue getGLOBAL_OFFSET_TABLE(EVT VT) {
 608     return getNode(ISD::GLOBAL_OFFSET_TABLE, SDLoc(), VT);
 609   }
 610
 611   /// getNode - Gets or creates the specified node.
 612   ///
 613   SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT);
 614   SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N);
 615   SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1, SDValue N2,
 616                   bool nuw = false, bool nsw = false, bool exact = false);
 617   SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1, SDValue N2,
 618                   SDValue N3);
 619   SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1, SDValue N2,
 620                   SDValue N3, SDValue N4);
 621   SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1, SDValue N2,
 622                   SDValue N3, SDValue N4, SDValue N5);
 623   SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT, ArrayRef<SDUse> Ops);
 624   SDValue getNode(unsigned Opcode, SDLoc DL, EVT VT,
 625                   ArrayRef<SDValue> Ops);
 626   SDValue getNode(unsigned Opcode, SDLoc DL,
 627                   ArrayRef<EVT> ResultTys,
 628                   ArrayRef<SDValue> Ops);
 629   SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
 630                   ArrayRef<SDValue> Ops);
 631   SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs);
 632   SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs, SDValue N);
 633   SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
 634                   SDValue N1, SDValue N2);
 635   SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
 636                   SDValue N1, SDValue N2, SDValue N3);
 637   SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
 638                   SDValue N1, SDValue N2, SDValue N3, SDValue N4);
 639   SDValue getNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
 640                   SDValue N1, SDValue N2, SDValue N3, SDValue N4,
 641                   SDValue N5);
 642
 643   /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
 644   /// the incoming stack arguments to be loaded from the stack. This is
 645   /// used in tail call lowering to protect stack arguments from being
 646   /// clobbered.
 647   SDValue getStackArgumentTokenFactor(SDValue Chain);
 648
 649   SDValue getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst, SDValue Src,
 650                     SDValue Size, unsigned Align, bool isVol, bool AlwaysInline,
 651                     MachinePointerInfo DstPtrInfo,
 652                     MachinePointerInfo SrcPtrInfo);
 653
 654   SDValue getMemmove(SDValue Chain, SDLoc dl, SDValue Dst, SDValue Src,
 655                      SDValue Size, unsigned Align, bool isVol,
 656                      MachinePointerInfo DstPtrInfo,
 657                      MachinePointerInfo SrcPtrInfo);
 658
 659   SDValue getMemset(SDValue Chain, SDLoc dl, SDValue Dst, SDValue Src,
 660                     SDValue Size, unsigned Align, bool isVol,
 661                     MachinePointerInfo DstPtrInfo);
 662
 663   /// getSetCC - Helper function to make it easier to build SetCC's if you just
 664   /// have an ISD::CondCode instead of an SDValue.
 665   ///
 666   SDValue getSetCC(SDLoc DL, EVT VT, SDValue LHS, SDValue RHS,
 667                    ISD::CondCode Cond) {
 668     assert(LHS.getValueType().isVector() == RHS.getValueType().isVector() &&
 669       "Cannot compare scalars to vectors");
 670     assert(LHS.getValueType().isVector() == VT.isVector() &&
 671       "Cannot compare scalars to vectors");
 672     assert(Cond != ISD::SETCC_INVALID &&
 673         "Cannot create a setCC of an invalid node.");
 674     return getNode(ISD::SETCC, DL, VT, LHS, RHS, getCondCode(Cond));
 675   }
 676
 677   // getSelect - Helper function to make it easier to build Select's if you just
 678   // have operands and don't want to check for vector.
 679   SDValue getSelect(SDLoc DL, EVT VT, SDValue Cond,
 680                     SDValue LHS, SDValue RHS) {
 681     assert(LHS.getValueType() == RHS.getValueType() &&
 682            "Cannot use select on differing types");
 683     assert(VT.isVector() == LHS.getValueType().isVector() &&
 684            "Cannot mix vectors and scalars");
 685     return getNode(Cond.getValueType().isVector() ? ISD::VSELECT : ISD::SELECT, DL, VT,
 686                    Cond, LHS, RHS);
 687   }
 688
 689   /// getSelectCC - Helper function to make it easier to build SelectCC's if you
 690   /// just have an ISD::CondCode instead of an SDValue.
 691   ///
 692   SDValue getSelectCC(SDLoc DL, SDValue LHS, SDValue RHS,
 693                       SDValue True, SDValue False, ISD::CondCode Cond) {
 694     return getNode(ISD::SELECT_CC, DL, True.getValueType(),
 695                    LHS, RHS, True, False, getCondCode(Cond));
 696   }
 697
 698   /// getVAArg - VAArg produces a result and token chain, and takes a pointer
 699   /// and a source value as input.
 700   SDValue getVAArg(EVT VT, SDLoc dl, SDValue Chain, SDValue Ptr,
 701                    SDValue SV, unsigned Align);
 702
 703   /// getAtomic - Gets a node for an atomic op, produces result and chain and
 704   /// takes 3 operands
 705   SDValue getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT, SDValue Chain,
 706                     SDValue Ptr, SDValue Cmp, SDValue Swp,
 707                     MachinePointerInfo PtrInfo, unsigned Alignment,
 708                     AtomicOrdering SuccessOrdering,
 709                     AtomicOrdering FailureOrdering,
 710                     SynchronizationScope SynchScope);
 711   SDValue getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT, SDValue Chain,
 712                     SDValue Ptr, SDValue Cmp, SDValue Swp,
 713                     MachineMemOperand *MMO,
 714                     AtomicOrdering SuccessOrdering,
 715                     AtomicOrdering FailureOrdering,
 716                     SynchronizationScope SynchScope);
 717
 718   /// getAtomic - Gets a node for an atomic op, produces result (if relevant)
 719   /// and chain and takes 2 operands.
 720   SDValue getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT, SDValue Chain,
 721                     SDValue Ptr, SDValue Val, const Value *PtrVal,
 722                     unsigned Alignment, AtomicOrdering Ordering,
 723                     SynchronizationScope SynchScope);
 724   SDValue getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT, SDValue Chain,
 725                     SDValue Ptr, SDValue Val, MachineMemOperand *MMO,
 726                     AtomicOrdering Ordering,
 727                     SynchronizationScope SynchScope);
 728
 729   /// getAtomic - Gets a node for an atomic op, produces result and chain and
 730   /// takes 1 operand.
 731   SDValue getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT, EVT VT,
 732                     SDValue Chain, SDValue Ptr, MachineMemOperand *MMO,
 733                     AtomicOrdering Ordering,
 734                     SynchronizationScope SynchScope);
 735
 736   /// getAtomic - Gets a node for an atomic op, produces result and chain and
 737   /// takes N operands.
 738   SDValue getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTList,
 739                     ArrayRef<SDValue> Ops, MachineMemOperand *MMO,
 740                     AtomicOrdering SuccessOrdering,
 741                     AtomicOrdering FailureOrdering,
 742                     SynchronizationScope SynchScope);
 743   SDValue getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTList,
 744                     ArrayRef<SDValue> Ops, MachineMemOperand *MMO,
 745                     AtomicOrdering Ordering, SynchronizationScope SynchScope);
 746
 747   /// getMemIntrinsicNode - Creates a MemIntrinsicNode that may produce a
 748   /// result and takes a list of operands. Opcode may be INTRINSIC_VOID,
 749   /// INTRINSIC_W_CHAIN, or a target-specific opcode with a value not
 750   /// less than FIRST_TARGET_MEMORY_OPCODE.
 751   SDValue getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
 752                               ArrayRef<SDValue> Ops,
 753                               EVT MemVT, MachinePointerInfo PtrInfo,
 754                               unsigned Align = 0, bool Vol = false,
 755                               bool ReadMem = true, bool WriteMem = true);
 756
 757   SDValue getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
 758                               ArrayRef<SDValue> Ops,
 759                               EVT MemVT, MachineMemOperand *MMO);
 760
 761   /// getMergeValues - Create a MERGE_VALUES node from the given operands.
 762   SDValue getMergeValues(ArrayRef<SDValue> Ops, SDLoc dl);
 763
 764   /// getLoad - Loads are not normal binary operators: their result type is not
 765   /// determined by their operands, and they produce a value AND a token chain.
 766   ///
 767   SDValue getLoad(EVT VT, SDLoc dl, SDValue Chain, SDValue Ptr,
 768                   MachinePointerInfo PtrInfo, bool isVolatile,
 769                   bool isNonTemporal, bool isInvariant, unsigned Alignment,
 770                   const MDNode *TBAAInfo = nullptr,
 771                   const MDNode *Ranges = nullptr);
 772   SDValue getLoad(EVT VT, SDLoc dl, SDValue Chain, SDValue Ptr,
 773                   MachineMemOperand *MMO);
 774   SDValue getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
 775                      SDValue Chain, SDValue Ptr, MachinePointerInfo PtrInfo,
 776                      EVT MemVT, bool isVolatile,
 777                      bool isNonTemporal, unsigned Alignment,
 778                      const MDNode *TBAAInfo = nullptr);
 779   SDValue getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
 780                      SDValue Chain, SDValue Ptr, EVT MemVT,
 781                      MachineMemOperand *MMO);
 782   SDValue getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
 783                          SDValue Offset, ISD::MemIndexedMode AM);
 784   SDValue getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
 785                   EVT VT, SDLoc dl,
 786                   SDValue Chain, SDValue Ptr, SDValue Offset,
 787                   MachinePointerInfo PtrInfo, EVT MemVT,
 788                   bool isVolatile, bool isNonTemporal, bool isInvariant,
 789                   unsigned Alignment, const MDNode *TBAAInfo = nullptr,
 790                   const MDNode *Ranges = nullptr);
 791   SDValue getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
 792                   EVT VT, SDLoc dl,
 793                   SDValue Chain, SDValue Ptr, SDValue Offset,
 794                   EVT MemVT, MachineMemOperand *MMO);
 795
 796   /// getStore - Helper function to build ISD::STORE nodes.
 797   ///
 798   SDValue getStore(SDValue Chain, SDLoc dl, SDValue Val, SDValue Ptr,
 799                    MachinePointerInfo PtrInfo, bool isVolatile,
 800                    bool isNonTemporal, unsigned Alignment,
 801                    const MDNode *TBAAInfo = nullptr);
 802   SDValue getStore(SDValue Chain, SDLoc dl, SDValue Val, SDValue Ptr,
 803                    MachineMemOperand *MMO);
 804   SDValue getTruncStore(SDValue Chain, SDLoc dl, SDValue Val, SDValue Ptr,
 805                         MachinePointerInfo PtrInfo, EVT TVT,
 806                         bool isNonTemporal, bool isVolatile,
 807                         unsigned Alignment,
 808                         const MDNode *TBAAInfo = nullptr);
 809   SDValue getTruncStore(SDValue Chain, SDLoc dl, SDValue Val, SDValue Ptr,
 810                         EVT TVT, MachineMemOperand *MMO);
 811   SDValue getIndexedStore(SDValue OrigStoe, SDLoc dl, SDValue Base,
 812                            SDValue Offset, ISD::MemIndexedMode AM);
 813
 814   /// getSrcValue - Construct a node to track a Value* through the backend.
 815   SDValue getSrcValue(const Value *v);
 816
 817   /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
 818   SDValue getMDNode(const MDNode *MD);
 819
 820   /// getAddrSpaceCast - Return an AddrSpaceCastSDNode.
 821   SDValue getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr,
 822                            unsigned SrcAS, unsigned DestAS);
 823
 824   /// getShiftAmountOperand - Return the specified value casted to
 825   /// the target's desired shift amount type.
 826   SDValue getShiftAmountOperand(EVT LHSTy, SDValue Op);
 827
 828   /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
 829   /// specified operands.  If the resultant node already exists in the DAG,
 830   /// this does not modify the specified node, instead it returns the node that
 831   /// already exists.  If the resultant node does not exist in the DAG, the
 832   /// input node is returned.  As a degenerate case, if you specify the same
 833   /// input operands as the node already has, the input node is returned.
 834   SDNode *UpdateNodeOperands(SDNode *N, SDValue Op);
 835   SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2);
 836   SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
 837                                SDValue Op3);
 838   SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
 839                                SDValue Op3, SDValue Op4);
 840   SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
 841                                SDValue Op3, SDValue Op4, SDValue Op5);
 842   SDNode *UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops);
 843
 844   /// SelectNodeTo - These are used for target selectors to *mutate* the
 845   /// specified node to have the specified return type, Target opcode, and
 846   /// operands.  Note that target opcodes are stored as
 847   /// ~TargetOpcode in the node opcode field.  The resultant node is returned.
 848   SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT);
 849   SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT, SDValue Op1);
 850   SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT,
 851                        SDValue Op1, SDValue Op2);
 852   SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT,
 853                        SDValue Op1, SDValue Op2, SDValue Op3);
 854   SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT,
 855                        ArrayRef<SDValue> Ops);
 856   SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1, EVT VT2);
 857   SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
 858                        EVT VT2, ArrayRef<SDValue> Ops);
 859   SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
 860                        EVT VT2, EVT VT3, ArrayRef<SDValue> Ops);
 861   SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT1,
 862                        EVT VT2, EVT VT3, EVT VT4, ArrayRef<SDValue> Ops);
 863   SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
 864                        EVT VT2, SDValue Op1);
 865   SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
 866                        EVT VT2, SDValue Op1, SDValue Op2);
 867   SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
 868                        EVT VT2, SDValue Op1, SDValue Op2, SDValue Op3);
 869   SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
 870                        EVT VT2, EVT VT3, SDValue Op1, SDValue Op2, SDValue Op3);
 871   SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, SDVTList VTs,
 872                        ArrayRef<SDValue> Ops);
 873
 874   /// MorphNodeTo - This *mutates* the specified node to have the specified
 875   /// return type, opcode, and operands.
 876   SDNode *MorphNodeTo(SDNode *N, unsigned Opc, SDVTList VTs,
 877                       ArrayRef<SDValue> Ops);
 878
 879   /// getMachineNode - These are used for target selectors to create a new node
 880   /// with specified return type(s), MachineInstr opcode, and operands.
 881   ///
 882   /// Note that getMachineNode returns the resultant node.  If there is already
 883   /// a node of the specified opcode and operands, it returns that node instead
 884   /// of the current one.
 885   MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT);
 886   MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
 887                                 SDValue Op1);
 888   MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
 889                                 SDValue Op1, SDValue Op2);
 890   MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
 891                                 SDValue Op1, SDValue Op2, SDValue Op3);
 892   MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
 893                                 ArrayRef<SDValue> Ops);
 894   MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2);
 895   MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
 896                                 SDValue Op1);
 897   MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
 898                                 SDValue Op1, SDValue Op2);
 899   MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
 900                                 SDValue Op1, SDValue Op2, SDValue Op3);
 901   MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
 902                                 ArrayRef<SDValue> Ops);
 903   MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
 904                                 EVT VT3, SDValue Op1, SDValue Op2);
 905   MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
 906                                 EVT VT3, SDValue Op1, SDValue Op2,
 907                                 SDValue Op3);
 908   MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
 909                                 EVT VT3, ArrayRef<SDValue> Ops);
 910   MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2,
 911                                 EVT VT3, EVT VT4, ArrayRef<SDValue> Ops);
 912   MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl,
 913                                 ArrayRef<EVT> ResultTys,
 914                                 ArrayRef<SDValue> Ops);
 915   MachineSDNode *getMachineNode(unsigned Opcode, SDLoc dl, SDVTList VTs,
 916                                 ArrayRef<SDValue> Ops);
 917
 918   /// getTargetExtractSubreg - A convenience function for creating
 919   /// TargetInstrInfo::EXTRACT_SUBREG nodes.
 920   SDValue getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
 921                                  SDValue Operand);
 922
 923   /// getTargetInsertSubreg - A convenience function for creating
 924   /// TargetInstrInfo::INSERT_SUBREG nodes.
 925   SDValue getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
 926                                 SDValue Operand, SDValue Subreg);
 927
 928   /// getNodeIfExists - Get the specified node if it's already available, or
 929   /// else return NULL.
 930   SDNode *getNodeIfExists(unsigned Opcode, SDVTList VTs, ArrayRef<SDValue> Ops,
 931                           bool nuw = false, bool nsw = false,
 932                           bool exact = false);
 933
 934   /// getDbgValue - Creates a SDDbgValue node.
 935   ///
 936   SDDbgValue *getDbgValue(MDNode *MDPtr, SDNode *N, unsigned R,
 937                           bool IsIndirect, uint64_t Off,
 938                           DebugLoc DL, unsigned O);
 939   /// Constant.
 940   SDDbgValue *getConstantDbgValue(MDNode *MDPtr, const Value *C, uint64_t Off,
 941                                   DebugLoc DL, unsigned O);
 942   /// Frame index.
 943   SDDbgValue *getFrameIndexDbgValue(MDNode *MDPtr, unsigned FI, uint64_t Off,
 944                                     DebugLoc DL, unsigned O);
 945
 946   /// RemoveDeadNode - Remove the specified node from the system. If any of its
 947   /// operands then becomes dead, remove them as well. Inform UpdateListener
 948   /// for each node deleted.
 949   void RemoveDeadNode(SDNode *N);
 950
 951   /// RemoveDeadNodes - This method deletes the unreachable nodes in the
 952   /// given list, and any nodes that become unreachable as a result.
 953   void RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes);
 954
 955   /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
 956   /// This can cause recursive merging of nodes in the DAG.  Use the first
 957   /// version if 'From' is known to have a single result, use the second
 958   /// if you have two nodes with identical results (or if 'To' has a superset
 959   /// of the results of 'From'), use the third otherwise.
 960   ///
 961   /// These methods all take an optional UpdateListener, which (if not null) is
 962   /// informed about nodes that are deleted and modified due to recursive
 963   /// changes in the dag.
 964   ///
 965   /// These functions only replace all existing uses. It's possible that as
 966   /// these replacements are being performed, CSE may cause the From node
 967   /// to be given new uses. These new uses of From are left in place, and
 968   /// not automatically transferred to To.
 969   ///
 970   void ReplaceAllUsesWith(SDValue From, SDValue Op);
 971   void ReplaceAllUsesWith(SDNode *From, SDNode *To);
 972   void ReplaceAllUsesWith(SDNode *From, const SDValue *To);
 973
 974   /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
 975   /// uses of other values produced by From.Val alone.
 976   void ReplaceAllUsesOfValueWith(SDValue From, SDValue To);
 977
 978   /// ReplaceAllUsesOfValuesWith - Like ReplaceAllUsesOfValueWith, but
 979   /// for multiple values at once. This correctly handles the case where
 980   /// there is an overlap between the From values and the To values.
 981   void ReplaceAllUsesOfValuesWith(const SDValue *From, const SDValue *To,
 982                                   unsigned Num);
 983
 984   /// AssignTopologicalOrder - Topological-sort the AllNodes list and a
 985   /// assign a unique node id for each node in the DAG based on their
 986   /// topological order. Returns the number of nodes.
 987   unsigned AssignTopologicalOrder();
 988
 989   /// RepositionNode - Move node N in the AllNodes list to be immediately
 990   /// before the given iterator Position. This may be used to update the
 991   /// topological ordering when the list of nodes is modified.
 992   void RepositionNode(allnodes_iterator Position, SDNode *N) {
 993     AllNodes.insert(Position, AllNodes.remove(N));
 994   }
 995
 996   /// isCommutativeBinOp - Returns true if the opcode is a commutative binary
 997   /// operation.
 998   static bool isCommutativeBinOp(unsigned Opcode) {
 999     // FIXME: This should get its info from the td file, so that we can include
1000     // target info.
1001     switch (Opcode) {
1002     case ISD::ADD:
1003     case ISD::MUL:
1004     case ISD::MULHU:
1005     case ISD::MULHS:
1006     case ISD::SMUL_LOHI:
1007     case ISD::UMUL_LOHI:
1008     case ISD::FADD:
1009     case ISD::FMUL:
1010     case ISD::AND:
1011     case ISD::OR:
1012     case ISD::XOR:
1013     case ISD::SADDO:
1014     case ISD::UADDO:
1015     case ISD::ADDC:
1016     case ISD::ADDE: return true;
1017     default: return false;
1018     }
1019   }
1020
1021   /// Returns an APFloat semantics tag appropriate for the given type. If VT is
1022   /// a vector type, the element semantics are returned.
1023   static const fltSemantics &EVTToAPFloatSemantics(EVT VT) {
1024     switch (VT.getScalarType().getSimpleVT().SimpleTy) {
1025     default: llvm_unreachable("Unknown FP format");
1026     case MVT::f16:     return APFloat::IEEEhalf;
1027     case MVT::f32:     return APFloat::IEEEsingle;
1028     case MVT::f64:     return APFloat::IEEEdouble;
1029     case MVT::f80:     return APFloat::x87DoubleExtended;
1030     case MVT::f128:    return APFloat::IEEEquad;
1031     case MVT::ppcf128: return APFloat::PPCDoubleDouble;
1032     }
1033   }
1034
1035   /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
1036   /// value is produced by SD.
1037   void AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter);
1038
1039   /// GetDbgValues - Get the debug values which reference the given SDNode.
1040   ArrayRef<SDDbgValue*> GetDbgValues(const SDNode* SD) {
1041     return DbgInfo->getSDDbgValues(SD);
1042   }
1043
1044   /// TransferDbgValues - Transfer SDDbgValues.
1045   void TransferDbgValues(SDValue From, SDValue To);
1046
1047   /// hasDebugValues - Return true if there are any SDDbgValue nodes associated
1048   /// with this SelectionDAG.
1049   bool hasDebugValues() const { return !DbgInfo->empty(); }
1050
1051   SDDbgInfo::DbgIterator DbgBegin() { return DbgInfo->DbgBegin(); }
1052   SDDbgInfo::DbgIterator DbgEnd()   { return DbgInfo->DbgEnd(); }
1053   SDDbgInfo::DbgIterator ByvalParmDbgBegin() {
1054     return DbgInfo->ByvalParmDbgBegin();
1055   }
1056   SDDbgInfo::DbgIterator ByvalParmDbgEnd()   {
1057     return DbgInfo->ByvalParmDbgEnd();
1058   }
1059
1060   void dump() const;
1061
1062   /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1063   /// specified value type.  If minAlign is specified, the slot size will have
1064   /// at least that alignment.
1065   SDValue CreateStackTemporary(EVT VT, unsigned minAlign = 1);
1066
1067   /// CreateStackTemporary - Create a stack temporary suitable for holding
1068   /// either of the specified value types.
1069   SDValue CreateStackTemporary(EVT VT1, EVT VT2);
1070
1071   /// FoldConstantArithmetic -
1072   SDValue FoldConstantArithmetic(unsigned Opcode, EVT VT,
1073                                  SDNode *Cst1, SDNode *Cst2);
1074
1075   /// FoldSetCC - Constant fold a setcc to true or false.
1076   SDValue FoldSetCC(EVT VT, SDValue N1,
1077                     SDValue N2, ISD::CondCode Cond, SDLoc dl);
1078
1079   /// SignBitIsZero - Return true if the sign bit of Op is known to be zero.  We
1080   /// use this predicate to simplify operations downstream.
1081   bool SignBitIsZero(SDValue Op, unsigned Depth = 0) const;
1082
1083   /// MaskedValueIsZero - Return true if 'Op & Mask' is known to be zero.  We
1084   /// use this predicate to simplify operations downstream.  Op and Mask are
1085   /// known to be the same type.
1086   bool MaskedValueIsZero(SDValue Op, const APInt &Mask, unsigned Depth = 0)
1087     const;
1088
1089   /// Determine which bits of Op are known to be either zero or one and return
1090   /// them in the KnownZero/KnownOne bitsets.  Targets can implement the
1091   /// computeKnownBitsForTargetNode method in the TargetLowering class to allow
1092   /// target nodes to be understood.
1093   void computeKnownBits(SDValue Op, APInt &KnownZero, APInt &KnownOne,
1094                         unsigned Depth = 0) const;
1095
1096   /// ComputeNumSignBits - Return the number of times the sign bit of the
1097   /// register is replicated into the other bits.  We know that at least 1 bit
1098   /// is always equal to the sign bit (itself), but other cases can give us
1099   /// information.  For example, immediately after an "SRA X, 2", we know that
1100   /// the top 3 bits are all equal to each other, so we return 3.  Targets can
1101   /// implement the ComputeNumSignBitsForTarget method in the TargetLowering
1102   /// class to allow target nodes to be understood.
1103   unsigned ComputeNumSignBits(SDValue Op, unsigned Depth = 0) const;
1104
1105   /// isBaseWithConstantOffset - Return true if the specified operand is an
1106   /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
1107   /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
1108   /// semantics as an ADD.  This handles the equivalence:
1109   ///     X|Cst == X+Cst iff X&Cst = 0.
1110   bool isBaseWithConstantOffset(SDValue Op) const;
1111
1112   /// isKnownNeverNan - Test whether the given SDValue is known to never be NaN.
1113   bool isKnownNeverNaN(SDValue Op) const;
1114
1115   /// isKnownNeverZero - Test whether the given SDValue is known to never be
1116   /// positive or negative Zero.
1117   bool isKnownNeverZero(SDValue Op) const;
1118
1119   /// isEqualTo - Test whether two SDValues are known to compare equal. This
1120   /// is true if they are the same value, or if one is negative zero and the
1121   /// other positive zero.
1122   bool isEqualTo(SDValue A, SDValue B) const;
1123
1124   /// UnrollVectorOp - Utility function used by legalize and lowering to
1125   /// "unroll" a vector operation by splitting out the scalars and operating
1126   /// on each element individually.  If the ResNE is 0, fully unroll the vector
1127   /// op. If ResNE is less than the width of the vector op, unroll up to ResNE.
1128   /// If the  ResNE is greater than the width of the vector op, unroll the
1129   /// vector op and fill the end of the resulting vector with UNDEFS.
1130   SDValue UnrollVectorOp(SDNode *N, unsigned ResNE = 0);
1131
1132   /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
1133   /// location that is 'Dist' units away from the location that the 'Base' load
1134   /// is loading from.
1135   bool isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
1136                          unsigned Bytes, int Dist) const;
1137
1138   /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
1139   /// it cannot be inferred.
1140   unsigned InferPtrAlignment(SDValue Ptr) const;
1141
1142   /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
1143   /// which is split (or expanded) into two not necessarily identical pieces.
1144   std::pair<EVT, EVT> GetSplitDestVTs(const EVT &VT) const;
1145
1146   /// SplitVector - Split the vector with EXTRACT_SUBVECTOR using the provides
1147   /// VTs and return the low/high part.
1148   std::pair<SDValue, SDValue> SplitVector(const SDValue &N, const SDLoc &DL,
1149                                           const EVT &LoVT, const EVT &HiVT);
1150
1151   /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
1152   /// low/high part.
1153   std::pair<SDValue, SDValue> SplitVector(const SDValue &N, const SDLoc &DL) {
1154     EVT LoVT, HiVT;
1155     std::tie(LoVT, HiVT) = GetSplitDestVTs(N.getValueType());
1156     return SplitVector(N, DL, LoVT, HiVT);
1157   }
1158
1159   /// SplitVectorOperand - Split the node's operand with EXTRACT_SUBVECTOR and
1160   /// return the low/high part.
1161   std::pair<SDValue, SDValue> SplitVectorOperand(const SDNode *N, unsigned OpNo)
1162   {
1163     return SplitVector(N->getOperand(OpNo), SDLoc(N));
1164   }
1165
1166   /// ExtractVectorElements - Append the extracted elements from Start to Count
1167   /// out of the vector Op in Args. If Count is 0, all of the elements will be
1168   /// extracted.
1169   void ExtractVectorElements(SDValue Op, SmallVectorImpl<SDValue> &Args,
1170                              unsigned Start = 0, unsigned Count = 0);
1171
1172   unsigned getEVTAlignment(EVT MemoryVT) const;
1173
1174 private:
1175   bool RemoveNodeFromCSEMaps(SDNode *N);
1176   void AddModifiedNodeToCSEMaps(SDNode *N);
1177   SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op, void *&InsertPos);
1178   SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op1, SDValue Op2,
1179                                void *&InsertPos);
1180   SDNode *FindModifiedNodeSlot(SDNode *N, ArrayRef<SDValue> Ops,
1181                                void *&InsertPos);
1182   SDNode *UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc loc);
1183
1184   void DeleteNodeNotInCSEMaps(SDNode *N);
1185   void DeallocateNode(SDNode *N);
1186
1187   void allnodes_clear();
1188
1189   BinarySDNode *GetBinarySDNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
1190                                 SDValue N1, SDValue N2, bool nuw, bool nsw,
1191                                 bool exact);
1192
1193   /// VTList - List of non-single value types.
1194   FoldingSet<SDVTListNode> VTListMap;
1195
1196   /// CondCodeNodes - Maps to auto-CSE operations.
1197   std::vector<CondCodeSDNode*> CondCodeNodes;
1198
1199   std::vector<SDNode*> ValueTypeNodes;
1200   std::map<EVT, SDNode*, EVT::compareRawBits> ExtendedValueTypeNodes;
1201   StringMap<SDNode*> ExternalSymbols;
1202
1203   std::map<std::pair<std::string, unsigned char>,SDNode*> TargetExternalSymbols;
1204 };
1205
1206 template <> struct GraphTraits<SelectionDAG*> : public GraphTraits<SDNode*> {
1207   typedef SelectionDAG::allnodes_iterator nodes_iterator;
1208   static nodes_iterator nodes_begin(SelectionDAG *G) {
1209     return G->allnodes_begin();
1210   }
1211   static nodes_iterator nodes_end(SelectionDAG *G) {
1212     return G->allnodes_end();
1213   }
1214 };
1215
1216 }  // end namespace llvm
1217
1218 #endif