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