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