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