include/llvm/CodeGen/SelectionDAG.h

   1 //===-- llvm/CodeGen/SelectionDAG.h - InstSelection DAG ---------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source 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/CodeGen/SelectionDAGNodes.h"
  19 #include "llvm/CodeGen/SelectionDAGCSEMap.h"
  20 #include "llvm/ADT/ilist"
  21
  22 #include <list>
  23 #include <map>
  24 #include <set>
  25 #include <string>
  26
  27 namespace llvm {
  28   class TargetLowering;
  29   class TargetMachine;
  30   class MachineDebugInfo;
  31   class MachineFunction;
  32
  33 /// SelectionDAG class - This is used to represent a portion of an LLVM function
  34 /// in a low-level Data Dependence DAG representation suitable for instruction
  35 /// selection.  This DAG is constructed as the first step of instruction
  36 /// selection in order to allow implementation of machine specific optimizations
  37 /// and code simplifications.
  38 ///
  39 /// The representation used by the SelectionDAG is a target-independent
  40 /// representation, which has some similarities to the GCC RTL representation,
  41 /// but is significantly more simple, powerful, and is a graph form instead of a
  42 /// linear form.
  43 ///
  44 class SelectionDAG {
  45   TargetLowering &TLI;
  46   MachineFunction &MF;
  47   MachineDebugInfo *DI;
  48
  49   /// Root - The root of the entire DAG.  EntryNode - The starting token.
  50   SDOperand Root, EntryNode;
  51
  52   /// AllNodes - A linked list of nodes in the current DAG.
  53   ilist<SDNode> AllNodes;
  54
  55   /// CSEMap - This structure is used to memoize nodes, automatically performing
  56   /// CSE with existing nodes with a duplicate is requested.
  57   SelectionDAGCSEMap CSEMap;
  58
  59 public:
  60   SelectionDAG(TargetLowering &tli, MachineFunction &mf, MachineDebugInfo *di)
  61   : TLI(tli), MF(mf), DI(di) {
  62     EntryNode = Root = getNode(ISD::EntryToken, MVT::Other);
  63   }
  64   ~SelectionDAG();
  65
  66   MachineFunction &getMachineFunction() const { return MF; }
  67   const TargetMachine &getTarget() const;
  68   TargetLowering &getTargetLoweringInfo() const { return TLI; }
  69   MachineDebugInfo *getMachineDebugInfo() const { return DI; }
  70
  71   /// viewGraph - Pop up a ghostview window with the DAG rendered using 'dot'.
  72   ///
  73   void viewGraph();
  74
  75
  76   typedef ilist<SDNode>::const_iterator allnodes_const_iterator;
  77   allnodes_const_iterator allnodes_begin() const { return AllNodes.begin(); }
  78   allnodes_const_iterator allnodes_end() const { return AllNodes.end(); }
  79   typedef ilist<SDNode>::iterator allnodes_iterator;
  80   allnodes_iterator allnodes_begin() { return AllNodes.begin(); }
  81   allnodes_iterator allnodes_end() { return AllNodes.end(); }
  82
  83   /// getRoot - Return the root tag of the SelectionDAG.
  84   ///
  85   const SDOperand &getRoot() const { return Root; }
  86
  87   /// getEntryNode - Return the token chain corresponding to the entry of the
  88   /// function.
  89   const SDOperand &getEntryNode() const { return EntryNode; }
  90
  91   /// setRoot - Set the current root tag of the SelectionDAG.
  92   ///
  93   const SDOperand &setRoot(SDOperand N) { return Root = N; }
  94
  95   /// Combine - This iterates over the nodes in the SelectionDAG, folding
  96   /// certain types of nodes together, or eliminating superfluous nodes.  When
  97   /// the AfterLegalize argument is set to 'true', Combine takes care not to
  98   /// generate any nodes that will be illegal on the target.
  99   void Combine(bool AfterLegalize);
 100
 101   /// Legalize - This transforms the SelectionDAG into a SelectionDAG that is
 102   /// compatible with the target instruction selector, as indicated by the
 103   /// TargetLowering object.
 104   ///
 105   /// Note that this is an involved process that may invalidate pointers into
 106   /// the graph.
 107   void Legalize();
 108
 109   /// RemoveDeadNodes - This method deletes all unreachable nodes in the
 110   /// SelectionDAG.
 111   void RemoveDeadNodes();
 112
 113   /// getVTList - Return an SDVTList that represents the list of values
 114   /// specified.
 115   SDVTList getVTList(MVT::ValueType VT);
 116   SDVTList getVTList(MVT::ValueType VT1, MVT::ValueType VT2);
 117   SDVTList getVTList(MVT::ValueType VT1, MVT::ValueType VT2,MVT::ValueType VT3);
 118   SDVTList getVTList(const MVT::ValueType *VTs, unsigned NumVTs);
 119
 120   /// getNodeValueTypes - These are obsolete, use getVTList instead.
 121   const MVT::ValueType *getNodeValueTypes(MVT::ValueType VT) {
 122     return getVTList(VT).VTs;
 123   }
 124   const MVT::ValueType *getNodeValueTypes(MVT::ValueType VT1,
 125                                           MVT::ValueType VT2) {
 126     return getVTList(VT1, VT2).VTs;
 127   }
 128   const MVT::ValueType *getNodeValueTypes(MVT::ValueType VT1,MVT::ValueType VT2,
 129                                           MVT::ValueType VT3) {
 130     return getVTList(VT1, VT2, VT3).VTs;
 131   }
 132   const MVT::ValueType *getNodeValueTypes(std::vector<MVT::ValueType> &VTList) {
 133     return getVTList(&VTList[0], VTList.size()).VTs;
 134   }
 135
 136
 137   //===----------------------------------------------------------------------===//
 138   // Node creation methods.
 139   //
 140   SDOperand getString(const std::string &Val);
 141   SDOperand getConstant(uint64_t Val, MVT::ValueType VT, bool isTarget = false);
 142   SDOperand getTargetConstant(uint64_t Val, MVT::ValueType VT) {
 143     return getConstant(Val, VT, true);
 144   }
 145   SDOperand getConstantFP(double Val, MVT::ValueType VT, bool isTarget = false);
 146   SDOperand getTargetConstantFP(double Val, MVT::ValueType VT) {
 147     return getConstantFP(Val, VT, true);
 148   }
 149   SDOperand getGlobalAddress(const GlobalValue *GV, MVT::ValueType VT,
 150                              int offset = 0, bool isTargetGA = false);
 151   SDOperand getTargetGlobalAddress(const GlobalValue *GV, MVT::ValueType VT,
 152                                    int offset = 0) {
 153     return getGlobalAddress(GV, VT, offset, true);
 154   }
 155   SDOperand getFrameIndex(int FI, MVT::ValueType VT, bool isTarget = false);
 156   SDOperand getTargetFrameIndex(int FI, MVT::ValueType VT) {
 157     return getFrameIndex(FI, VT, true);
 158   }
 159   SDOperand getJumpTable(int JTI, MVT::ValueType VT, bool isTarget = false);
 160   SDOperand getTargetJumpTable(int JTI, MVT::ValueType VT) {
 161     return getJumpTable(JTI, VT, true);
 162   }
 163   SDOperand getConstantPool(Constant *C, MVT::ValueType VT,
 164                             unsigned Align = 0, int Offs = 0, bool isT=false);
 165   SDOperand getTargetConstantPool(Constant *C, MVT::ValueType VT,
 166                                   unsigned Align = 0, int Offset = 0) {
 167     return getConstantPool(C, VT, Align, Offset, true);
 168   }
 169   SDOperand getBasicBlock(MachineBasicBlock *MBB);
 170   SDOperand getExternalSymbol(const char *Sym, MVT::ValueType VT);
 171   SDOperand getTargetExternalSymbol(const char *Sym, MVT::ValueType VT);
 172   SDOperand getValueType(MVT::ValueType);
 173   SDOperand getRegister(unsigned Reg, MVT::ValueType VT);
 174
 175   SDOperand getCopyToReg(SDOperand Chain, unsigned Reg, SDOperand N) {
 176     return getNode(ISD::CopyToReg, MVT::Other, Chain,
 177                    getRegister(Reg, N.getValueType()), N);
 178   }
 179
 180   // This version of the getCopyToReg method takes an extra operand, which
 181   // indicates that there is potentially an incoming flag value (if Flag is not
 182   // null) and that there should be a flag result.
 183   SDOperand getCopyToReg(SDOperand Chain, unsigned Reg, SDOperand N,
 184                          SDOperand Flag) {
 185     const MVT::ValueType *VTs = getNodeValueTypes(MVT::Other, MVT::Flag);
 186     SDOperand Ops[] = { Chain, getRegister(Reg, N.getValueType()), N, Flag };
 187     return getNode(ISD::CopyToReg, VTs, 2, Ops, Flag.Val ? 4 : 3);
 188   }
 189
 190   // Similar to last getCopyToReg() except parameter Reg is a SDOperand
 191   SDOperand getCopyToReg(SDOperand Chain, SDOperand Reg, SDOperand N,
 192                          SDOperand Flag) {
 193     const MVT::ValueType *VTs = getNodeValueTypes(MVT::Other, MVT::Flag);
 194     SDOperand Ops[] = { Chain, Reg, N, Flag };
 195     return getNode(ISD::CopyToReg, VTs, 2, Ops, Flag.Val ? 4 : 3);
 196   }
 197
 198   SDOperand getCopyFromReg(SDOperand Chain, unsigned Reg, MVT::ValueType VT) {
 199     const MVT::ValueType *VTs = getNodeValueTypes(VT, MVT::Other);
 200     SDOperand Ops[] = { Chain, getRegister(Reg, VT) };
 201     return getNode(ISD::CopyFromReg, VTs, 2, Ops, 2);
 202   }
 203
 204   // This version of the getCopyFromReg method takes an extra operand, which
 205   // indicates that there is potentially an incoming flag value (if Flag is not
 206   // null) and that there should be a flag result.
 207   SDOperand getCopyFromReg(SDOperand Chain, unsigned Reg, MVT::ValueType VT,
 208                            SDOperand Flag) {
 209     const MVT::ValueType *VTs = getNodeValueTypes(VT, MVT::Other, MVT::Flag);
 210     SDOperand Ops[] = { Chain, getRegister(Reg, VT), Flag };
 211     return getNode(ISD::CopyFromReg, VTs, 3, Ops, Flag.Val ? 3 : 2);
 212   }
 213
 214   SDOperand getCondCode(ISD::CondCode Cond);
 215
 216   /// getZeroExtendInReg - Return the expression required to zero extend the Op
 217   /// value assuming it was the smaller SrcTy value.
 218   SDOperand getZeroExtendInReg(SDOperand Op, MVT::ValueType SrcTy);
 219
 220   /// getCALLSEQ_START - Return a new CALLSEQ_START node, which always must have
 221   /// a flag result (to ensure it's not CSE'd).
 222   SDOperand getCALLSEQ_START(SDOperand Chain, SDOperand Op) {
 223     const MVT::ValueType *VTs = getNodeValueTypes(MVT::Other, MVT::Flag);
 224     SDOperand Ops[] = { Chain,  Op };
 225     return getNode(ISD::CALLSEQ_START, VTs, 2, Ops, 2);
 226   }
 227
 228   /// getNode - Gets or creates the specified node.
 229   ///
 230   SDOperand getNode(unsigned Opcode, MVT::ValueType VT);
 231   SDOperand getNode(unsigned Opcode, MVT::ValueType VT, SDOperand N);
 232   SDOperand getNode(unsigned Opcode, MVT::ValueType VT,
 233                     SDOperand N1, SDOperand N2);
 234   SDOperand getNode(unsigned Opcode, MVT::ValueType VT,
 235                     SDOperand N1, SDOperand N2, SDOperand N3);
 236   SDOperand getNode(unsigned Opcode, MVT::ValueType VT,
 237                     SDOperand N1, SDOperand N2, SDOperand N3, SDOperand N4);
 238   SDOperand getNode(unsigned Opcode, MVT::ValueType VT,
 239                     SDOperand N1, SDOperand N2, SDOperand N3, SDOperand N4,
 240                     SDOperand N5);
 241   SDOperand getNode(unsigned Opcode, MVT::ValueType VT,
 242                     const SDOperand *Ops, unsigned NumOps);
 243   SDOperand getNode(unsigned Opcode, std::vector<MVT::ValueType> &ResultTys,
 244                     const SDOperand *Ops, unsigned NumOps);
 245   SDOperand getNode(unsigned Opcode, const MVT::ValueType *VTs, unsigned NumVTs,
 246                     const SDOperand *Ops, unsigned NumOps);
 247
 248   /// getSetCC - Helper function to make it easier to build SetCC's if you just
 249   /// have an ISD::CondCode instead of an SDOperand.
 250   ///
 251   SDOperand getSetCC(MVT::ValueType VT, SDOperand LHS, SDOperand RHS,
 252                      ISD::CondCode Cond) {
 253     return getNode(ISD::SETCC, VT, LHS, RHS, getCondCode(Cond));
 254   }
 255
 256   /// getSelectCC - Helper function to make it easier to build SelectCC's if you
 257   /// just have an ISD::CondCode instead of an SDOperand.
 258   ///
 259   SDOperand getSelectCC(SDOperand LHS, SDOperand RHS,
 260                         SDOperand True, SDOperand False, ISD::CondCode Cond) {
 261     return getNode(ISD::SELECT_CC, True.getValueType(), LHS, RHS, True, False,
 262                    getCondCode(Cond));
 263   }
 264
 265   /// getVAArg - VAArg produces a result and token chain, and takes a pointer
 266   /// and a source value as input.
 267   SDOperand getVAArg(MVT::ValueType VT, SDOperand Chain, SDOperand Ptr,
 268                      SDOperand SV);
 269
 270   /// getLoad - Loads are not normal binary operators: their result type is not
 271   /// determined by their operands, and they produce a value AND a token chain.
 272   ///
 273   SDOperand getLoad(MVT::ValueType VT, SDOperand Chain, SDOperand Ptr,
 274                     SDOperand SV);
 275   SDOperand getVecLoad(unsigned Count, MVT::ValueType VT, SDOperand Chain,
 276                        SDOperand Ptr, SDOperand SV);
 277   SDOperand getExtLoad(unsigned Opcode, MVT::ValueType VT, SDOperand Chain,
 278                        SDOperand Ptr, SDOperand SV, MVT::ValueType EVT);
 279
 280   // getSrcValue - construct a node to track a Value* through the backend
 281   SDOperand getSrcValue(const Value* I, int offset = 0);
 282
 283   /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
 284   /// specified operands.  If the resultant node already exists in the DAG,
 285   /// this does not modify the specified node, instead it returns the node that
 286   /// already exists.  If the resultant node does not exist in the DAG, the
 287   /// input node is returned.  As a degenerate case, if you specify the same
 288   /// input operands as the node already has, the input node is returned.
 289   SDOperand UpdateNodeOperands(SDOperand N, SDOperand Op);
 290   SDOperand UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2);
 291   SDOperand UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2,
 292                                SDOperand Op3);
 293   SDOperand UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2,
 294                                SDOperand Op3, SDOperand Op4);
 295   SDOperand UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2,
 296                                SDOperand Op3, SDOperand Op4, SDOperand Op5);
 297   SDOperand UpdateNodeOperands(SDOperand N, SDOperand *Ops, unsigned NumOps);
 298
 299   /// SelectNodeTo - These are used for target selectors to *mutate* the
 300   /// specified node to have the specified return type, Target opcode, and
 301   /// operands.  Note that target opcodes are stored as
 302   /// ISD::BUILTIN_OP_END+TargetOpcode in the node opcode field.  The 0th value
 303   /// of the resultant node is returned.
 304   SDOperand SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT);
 305   SDOperand SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT,
 306                          SDOperand Op1);
 307   SDOperand SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT,
 308                          SDOperand Op1, SDOperand Op2);
 309   SDOperand SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT,
 310                          SDOperand Op1, SDOperand Op2, SDOperand Op3);
 311   SDOperand SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT,
 312                          SDOperand Op1, SDOperand Op2, SDOperand Op3,
 313                          SDOperand Op4);
 314   SDOperand SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT,
 315                          SDOperand Op1, SDOperand Op2, SDOperand Op3,
 316                          SDOperand Op4, SDOperand Op5);
 317   SDOperand SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT,
 318                          SDOperand Op1, SDOperand Op2, SDOperand Op3,
 319                          SDOperand Op4, SDOperand Op5, SDOperand Op6);
 320   SDOperand SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT,
 321                          SDOperand Op1, SDOperand Op2, SDOperand Op3,
 322                          SDOperand Op4, SDOperand Op5, SDOperand Op6,
 323                          SDOperand Op7);
 324   SDOperand SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT,
 325                          SDOperand Op1, SDOperand Op2, SDOperand Op3,
 326                          SDOperand Op4, SDOperand Op5, SDOperand Op6,
 327                          SDOperand Op7, SDOperand Op8);
 328   SDOperand SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT1,
 329                          MVT::ValueType VT2, SDOperand Op1, SDOperand Op2);
 330   SDOperand SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT1,
 331                          MVT::ValueType VT2, SDOperand Op1, SDOperand Op2,
 332                          SDOperand Op3);
 333   SDOperand SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT1,
 334                          MVT::ValueType VT2, SDOperand Op1, SDOperand Op2,
 335                          SDOperand Op3, SDOperand Op4);
 336   SDOperand SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT1,
 337                          MVT::ValueType VT2, SDOperand Op1, SDOperand Op2,
 338                          SDOperand Op3, SDOperand Op4, SDOperand Op5);
 339
 340   /// getTargetNode - These are used for target selectors to create a new node
 341   /// with specified return type(s), target opcode, and operands.
 342   ///
 343   /// Note that getTargetNode returns the resultant node.  If there is already a
 344   /// node of the specified opcode and operands, it returns that node instead of
 345   /// the current one.
 346   SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT);
 347   SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT,
 348                         SDOperand Op1);
 349   SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT,
 350                         SDOperand Op1, SDOperand Op2);
 351   SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT,
 352                         SDOperand Op1, SDOperand Op2, SDOperand Op3);
 353   SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT,
 354                         SDOperand Op1, SDOperand Op2, SDOperand Op3,
 355                         SDOperand Op4);
 356   SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT,
 357                         SDOperand Op1, SDOperand Op2, SDOperand Op3,
 358                         SDOperand Op4, SDOperand Op5);
 359   SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT,
 360                         SDOperand Op1, SDOperand Op2, SDOperand Op3,
 361                         SDOperand Op4, SDOperand Op5, SDOperand Op6);
 362   SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT,
 363                         SDOperand Op1, SDOperand Op2, SDOperand Op3,
 364                         SDOperand Op4, SDOperand Op5, SDOperand Op6,
 365                         SDOperand Op7);
 366   SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT,
 367                         SDOperand Op1, SDOperand Op2, SDOperand Op3,
 368                         SDOperand Op4, SDOperand Op5, SDOperand Op6,
 369                         SDOperand Op7, SDOperand Op8);
 370   SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT,
 371                         const SDOperand *Ops, unsigned NumOps);
 372   SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1,
 373                         MVT::ValueType VT2, SDOperand Op1);
 374   SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1,
 375                         MVT::ValueType VT2, SDOperand Op1, SDOperand Op2);
 376   SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1,
 377                         MVT::ValueType VT2, SDOperand Op1, SDOperand Op2,
 378                         SDOperand Op3);
 379   SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1,
 380                         MVT::ValueType VT2, SDOperand Op1, SDOperand Op2,
 381                         SDOperand Op3, SDOperand Op4);
 382   SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1,
 383                         MVT::ValueType VT2, SDOperand Op1, SDOperand Op2,
 384                         SDOperand Op3, SDOperand Op4, SDOperand Op5);
 385   SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1,
 386                         MVT::ValueType VT2, SDOperand Op1, SDOperand Op2,
 387                         SDOperand Op3, SDOperand Op4, SDOperand Op5,
 388                         SDOperand Op6);
 389   SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1,
 390                         MVT::ValueType VT2, SDOperand Op1, SDOperand Op2,
 391                         SDOperand Op3, SDOperand Op4, SDOperand Op5,
 392                         SDOperand Op6, SDOperand Op7);
 393   SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1,
 394                         MVT::ValueType VT2, MVT::ValueType VT3,
 395                         SDOperand Op1, SDOperand Op2);
 396   SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1,
 397                         MVT::ValueType VT2, MVT::ValueType VT3,
 398                         SDOperand Op1, SDOperand Op2,
 399                         SDOperand Op3, SDOperand Op4, SDOperand Op5);
 400   SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1,
 401                         MVT::ValueType VT2, MVT::ValueType VT3,
 402                         SDOperand Op1, SDOperand Op2,
 403                         SDOperand Op3, SDOperand Op4, SDOperand Op5,
 404                         SDOperand Op6);
 405   SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1,
 406                         MVT::ValueType VT2, MVT::ValueType VT3,
 407                         SDOperand Op1, SDOperand Op2,
 408                         SDOperand Op3, SDOperand Op4, SDOperand Op5,
 409                         SDOperand Op6, SDOperand Op7);
 410   SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1,
 411                         MVT::ValueType VT2,
 412                         const SDOperand *Ops, unsigned NumOps);
 413
 414   /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
 415   /// This can cause recursive merging of nodes in the DAG.  Use the first
 416   /// version if 'From' is known to have a single result, use the second
 417   /// if you have two nodes with identical results, use the third otherwise.
 418   ///
 419   /// These methods all take an optional vector, which (if not null) is
 420   /// populated with any nodes that are deleted from the SelectionDAG, due to
 421   /// new equivalences that are discovered.
 422   ///
 423   void ReplaceAllUsesWith(SDOperand From, SDOperand Op,
 424                           std::vector<SDNode*> *Deleted = 0);
 425   void ReplaceAllUsesWith(SDNode *From, SDNode *To,
 426                           std::vector<SDNode*> *Deleted = 0);
 427   void ReplaceAllUsesWith(SDNode *From, const SDOperand *To,
 428                           std::vector<SDNode*> *Deleted = 0);
 429
 430   /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
 431   /// uses of other values produced by From.Val alone.  The Deleted vector is
 432   /// handled the same was as for ReplaceAllUsesWith, but it is required for
 433   /// this method.
 434   void ReplaceAllUsesOfValueWith(SDOperand From, SDOperand To,
 435                                  std::vector<SDNode*> &Deleted);
 436
 437   /// DeleteNode - Remove the specified node from the system.  This node must
 438   /// have no referrers.
 439   void DeleteNode(SDNode *N);
 440
 441   /// AssignNodeIds - Assign a unique node id for each node in the DAG based on
 442   /// their allnodes order. It returns the maximum id.
 443   unsigned AssignNodeIds();
 444
 445   /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
 446   /// based on their topological order. It returns the maximum id and a vector
 447   /// of the SDNodes* in assigned order by reference.
 448   unsigned AssignTopologicalOrder(std::vector<SDNode*> &TopOrder);
 449
 450   void dump() const;
 451
 452 private:
 453   void RemoveNodeFromCSEMaps(SDNode *N);
 454   SDNode *AddNonLeafNodeToCSEMaps(SDNode *N);
 455   SDNode *FindModifiedNodeSlot(SDNode *N, SDOperand Op, void *&InsertPos);
 456   SDNode *FindModifiedNodeSlot(SDNode *N, SDOperand Op1, SDOperand Op2,
 457                                void *&InsertPos);
 458   SDNode *FindModifiedNodeSlot(SDNode *N, const SDOperand *Ops, unsigned NumOps,
 459                                void *&InsertPos);
 460
 461   void DeleteNodeNotInCSEMaps(SDNode *N);
 462
 463   /// SimplifySetCC - Try to simplify a setcc built with the specified operands
 464   /// and cc.  If unable to simplify it, return a null SDOperand.
 465   SDOperand SimplifySetCC(MVT::ValueType VT, SDOperand N1,
 466                           SDOperand N2, ISD::CondCode Cond);
 467
 468   // List of non-single value types.
 469   std::list<std::vector<MVT::ValueType> > VTList;
 470
 471   // Maps to auto-CSE operations.
 472   std::vector<CondCodeSDNode*> CondCodeNodes;
 473
 474   std::vector<SDNode*> ValueTypeNodes;
 475   std::map<std::string, SDNode*> ExternalSymbols;
 476   std::map<std::string, SDNode*> TargetExternalSymbols;
 477   std::map<std::string, StringSDNode*> StringNodes;
 478 };
 479
 480 template <> struct GraphTraits<SelectionDAG*> : public GraphTraits<SDNode*> {
 481   typedef SelectionDAG::allnodes_iterator nodes_iterator;
 482   static nodes_iterator nodes_begin(SelectionDAG *G) {
 483     return G->allnodes_begin();
 484   }
 485   static nodes_iterator nodes_end(SelectionDAG *G) {
 486     return G->allnodes_end();
 487   }
 488 };
 489
 490 }  // end namespace llvm
 491
 492 #endif