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