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