LLVM API Documentation

SelectionDAG.h

Go to the documentation of this file.
00001 //===-- llvm/CodeGen/SelectionDAG.h - InstSelection DAG ---------*- C++ -*-===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file declares the SelectionDAG class, and transitively defines the
00011 // SDNode class and subclasses.
00012 //
00013 //===----------------------------------------------------------------------===//
00014 
00015 #ifndef LLVM_CODEGEN_SELECTIONDAG_H
00016 #define LLVM_CODEGEN_SELECTIONDAG_H
00017 
00018 #include "llvm/CodeGen/SelectionDAGNodes.h"
00019 #include "llvm/ADT/ilist"
00020 
00021 #include <list>
00022 #include <map>
00023 #include <set>
00024 #include <string>
00025 
00026 namespace llvm {
00027   class TargetLowering;
00028   class TargetMachine;
00029   class MachineDebugInfo;
00030   class MachineFunction;
00031 
00032 /// SelectionDAG class - This is used to represent a portion of an LLVM function
00033 /// in a low-level Data Dependence DAG representation suitable for instruction
00034 /// selection.  This DAG is constructed as the first step of instruction
00035 /// selection in order to allow implementation of machine specific optimizations
00036 /// and code simplifications.
00037 ///
00038 /// The representation used by the SelectionDAG is a target-independent
00039 /// representation, which has some similarities to the GCC RTL representation,
00040 /// but is significantly more simple, powerful, and is a graph form instead of a
00041 /// linear form.
00042 ///
00043 class SelectionDAG {
00044   TargetLowering &TLI;
00045   MachineFunction &MF;
00046   MachineDebugInfo *DI;
00047 
00048   // Root - The root of the entire DAG.  EntryNode - The starting token.
00049   SDOperand Root, EntryNode;
00050 
00051   // AllNodes - A linked list of nodes in the current DAG.
00052   ilist<SDNode> AllNodes;
00053 
00054   // ValueNodes - track SrcValue nodes
00055   std::map<std::pair<const Value*, int>, SDNode*> ValueNodes;
00056 
00057 public:
00058   SelectionDAG(TargetLowering &tli, MachineFunction &mf, MachineDebugInfo *di)
00059   : TLI(tli), MF(mf), DI(di) {
00060     EntryNode = Root = getNode(ISD::EntryToken, MVT::Other);
00061   }
00062   ~SelectionDAG();
00063 
00064   MachineFunction &getMachineFunction() const { return MF; }
00065   const TargetMachine &getTarget() const;
00066   TargetLowering &getTargetLoweringInfo() const { return TLI; }
00067   MachineDebugInfo *getMachineDebugInfo() const { return DI; }
00068 
00069   /// viewGraph - Pop up a ghostview window with the DAG rendered using 'dot'.
00070   ///
00071   void viewGraph();
00072 
00073 
00074   typedef ilist<SDNode>::const_iterator allnodes_const_iterator;
00075   allnodes_const_iterator allnodes_begin() const { return AllNodes.begin(); }
00076   allnodes_const_iterator allnodes_end() const { return AllNodes.end(); }
00077   typedef ilist<SDNode>::iterator allnodes_iterator;
00078   allnodes_iterator allnodes_begin() { return AllNodes.begin(); }
00079   allnodes_iterator allnodes_end() { return AllNodes.end(); }
00080   
00081   /// getRoot - Return the root tag of the SelectionDAG.
00082   ///
00083   const SDOperand &getRoot() const { return Root; }
00084 
00085   /// getEntryNode - Return the token chain corresponding to the entry of the
00086   /// function.
00087   const SDOperand &getEntryNode() const { return EntryNode; }
00088 
00089   /// setRoot - Set the current root tag of the SelectionDAG.
00090   ///
00091   const SDOperand &setRoot(SDOperand N) { return Root = N; }
00092 
00093   /// Combine - This iterates over the nodes in the SelectionDAG, folding
00094   /// certain types of nodes together, or eliminating superfluous nodes.  When
00095   /// the AfterLegalize argument is set to 'true', Combine takes care not to
00096   /// generate any nodes that will be illegal on the target.
00097   void Combine(bool AfterLegalize);
00098   
00099   /// Legalize - This transforms the SelectionDAG into a SelectionDAG that is
00100   /// compatible with the target instruction selector, as indicated by the
00101   /// TargetLowering object.
00102   ///
00103   /// Note that this is an involved process that may invalidate pointers into
00104   /// the graph.
00105   void Legalize();
00106 
00107   /// RemoveDeadNodes - This method deletes all unreachable nodes in the
00108   /// SelectionDAG, including nodes (like loads) that have uses of their token
00109   /// chain but no other uses and no side effect.  If a node is passed in as an
00110   /// argument, it is used as the seed for node deletion.
00111   void RemoveDeadNodes(SDNode *N = 0);
00112 
00113   SDOperand getString(const std::string &Val);
00114   SDOperand getConstant(uint64_t Val, MVT::ValueType VT);
00115   SDOperand getTargetConstant(uint64_t Val, MVT::ValueType VT);
00116   SDOperand getConstantFP(double Val, MVT::ValueType VT);
00117   SDOperand getTargetConstantFP(double Val, MVT::ValueType VT);
00118   SDOperand getGlobalAddress(const GlobalValue *GV, MVT::ValueType VT,
00119                              int offset = 0);
00120   SDOperand getTargetGlobalAddress(const GlobalValue *GV, MVT::ValueType VT,
00121                                    int offset = 0);
00122   SDOperand getFrameIndex(int FI, MVT::ValueType VT);
00123   SDOperand getTargetFrameIndex(int FI, MVT::ValueType VT);
00124   SDOperand getJumpTable(int JTI, MVT::ValueType VT);
00125   SDOperand getTargetJumpTable(int JTI, MVT::ValueType VT);
00126   SDOperand getConstantPool(Constant *C, MVT::ValueType VT,
00127                            unsigned Alignment=0,  int offset = 0);
00128   SDOperand getTargetConstantPool(Constant *C, MVT::ValueType VT,
00129                                   unsigned Alignment=0, int offset = 0);
00130   SDOperand getBasicBlock(MachineBasicBlock *MBB);
00131   SDOperand getExternalSymbol(const char *Sym, MVT::ValueType VT);
00132   SDOperand getTargetExternalSymbol(const char *Sym, MVT::ValueType VT);
00133   SDOperand getValueType(MVT::ValueType);
00134   SDOperand getRegister(unsigned Reg, MVT::ValueType VT);
00135 
00136   SDOperand getCopyToReg(SDOperand Chain, unsigned Reg, SDOperand N) {
00137     return getNode(ISD::CopyToReg, MVT::Other, Chain,
00138                    getRegister(Reg, N.getValueType()), N);
00139   }
00140 
00141   // This version of the getCopyToReg method takes an extra operand, which
00142   // indicates that there is potentially an incoming flag value (if Flag is not
00143   // null) and that there should be a flag result.
00144   SDOperand getCopyToReg(SDOperand Chain, unsigned Reg, SDOperand N,
00145                          SDOperand Flag) {
00146     std::vector<MVT::ValueType> VTs;
00147     VTs.push_back(MVT::Other);
00148     VTs.push_back(MVT::Flag);
00149     std::vector<SDOperand> Ops;
00150     Ops.push_back(Chain);
00151     Ops.push_back(getRegister(Reg, N.getValueType()));
00152     Ops.push_back(N);
00153     if (Flag.Val) Ops.push_back(Flag);
00154     return getNode(ISD::CopyToReg, VTs, Ops);
00155   }
00156 
00157   // Similar to last getCopyToReg() except parameter Reg is a SDOperand
00158   SDOperand getCopyToReg(SDOperand Chain, SDOperand Reg, SDOperand N,
00159                          SDOperand Flag) {
00160     std::vector<MVT::ValueType> VTs;
00161     VTs.push_back(MVT::Other);
00162     VTs.push_back(MVT::Flag);
00163     std::vector<SDOperand> Ops;
00164     Ops.push_back(Chain);
00165     Ops.push_back(Reg);
00166     Ops.push_back(N);
00167     if (Flag.Val) Ops.push_back(Flag);
00168     return getNode(ISD::CopyToReg, VTs, Ops);
00169   }
00170   
00171   SDOperand getCopyFromReg(SDOperand Chain, unsigned Reg, MVT::ValueType VT) {
00172     std::vector<MVT::ValueType> ResultTys;
00173     ResultTys.push_back(VT);
00174     ResultTys.push_back(MVT::Other);
00175     std::vector<SDOperand> Ops;
00176     Ops.push_back(Chain);
00177     Ops.push_back(getRegister(Reg, VT));
00178     return getNode(ISD::CopyFromReg, ResultTys, Ops);
00179   }
00180   
00181   // This version of the getCopyFromReg method takes an extra operand, which
00182   // indicates that there is potentially an incoming flag value (if Flag is not
00183   // null) and that there should be a flag result.
00184   SDOperand getCopyFromReg(SDOperand Chain, unsigned Reg, MVT::ValueType VT,
00185                            SDOperand Flag) {
00186     std::vector<MVT::ValueType> ResultTys;
00187     ResultTys.push_back(VT);
00188     ResultTys.push_back(MVT::Other);
00189     ResultTys.push_back(MVT::Flag);
00190     std::vector<SDOperand> Ops;
00191     Ops.push_back(Chain);
00192     Ops.push_back(getRegister(Reg, VT));
00193     if (Flag.Val) Ops.push_back(Flag);
00194     return getNode(ISD::CopyFromReg, ResultTys, Ops);
00195   }
00196 
00197   SDOperand getCondCode(ISD::CondCode Cond);
00198 
00199   /// getZeroExtendInReg - Return the expression required to zero extend the Op
00200   /// value assuming it was the smaller SrcTy value.
00201   SDOperand getZeroExtendInReg(SDOperand Op, MVT::ValueType SrcTy);
00202   
00203   /// getCALLSEQ_START - Return a new CALLSEQ_START node, which always must have
00204   /// a flag result (to ensure it's not CSE'd).
00205   SDOperand getCALLSEQ_START(SDOperand Chain, SDOperand Op) {
00206     std::vector<MVT::ValueType> ResultTys;
00207     ResultTys.push_back(MVT::Other);
00208     ResultTys.push_back(MVT::Flag);
00209     std::vector<SDOperand> Ops;
00210     Ops.push_back(Chain);
00211     Ops.push_back(Op);
00212     return getNode(ISD::CALLSEQ_START, ResultTys, Ops);
00213   }
00214 
00215   /// getNode - Gets or creates the specified node.
00216   ///
00217   SDOperand getNode(unsigned Opcode, MVT::ValueType VT);
00218   SDOperand getNode(unsigned Opcode, MVT::ValueType VT, SDOperand N);
00219   SDOperand getNode(unsigned Opcode, MVT::ValueType VT,
00220                     SDOperand N1, SDOperand N2);
00221   SDOperand getNode(unsigned Opcode, MVT::ValueType VT,
00222                     SDOperand N1, SDOperand N2, SDOperand N3);
00223   SDOperand getNode(unsigned Opcode, MVT::ValueType VT,
00224                     SDOperand N1, SDOperand N2, SDOperand N3, SDOperand N4);
00225   SDOperand getNode(unsigned Opcode, MVT::ValueType VT,
00226                     SDOperand N1, SDOperand N2, SDOperand N3, SDOperand N4,
00227                     SDOperand N5);
00228   SDOperand getNode(unsigned Opcode, MVT::ValueType VT,
00229                     std::vector<SDOperand> &Children);
00230   SDOperand getNode(unsigned Opcode, std::vector<MVT::ValueType> &ResultTys,
00231                     std::vector<SDOperand> &Ops);
00232 
00233   /// getSetCC - Helper function to make it easier to build SetCC's if you just
00234   /// have an ISD::CondCode instead of an SDOperand.
00235   ///
00236   SDOperand getSetCC(MVT::ValueType VT, SDOperand LHS, SDOperand RHS,
00237                      ISD::CondCode Cond) {
00238     return getNode(ISD::SETCC, VT, LHS, RHS, getCondCode(Cond));
00239   }
00240 
00241   /// getSelectCC - Helper function to make it easier to build SelectCC's if you
00242   /// just have an ISD::CondCode instead of an SDOperand.
00243   ///
00244   SDOperand getSelectCC(SDOperand LHS, SDOperand RHS,
00245                         SDOperand True, SDOperand False, ISD::CondCode Cond) {
00246     MVT::ValueType VT = True.getValueType();
00247     return getNode(ISD::SELECT_CC, VT, LHS, RHS, True, False,getCondCode(Cond));
00248   }
00249   
00250   /// getVAArg - VAArg produces a result and token chain, and takes a pointer
00251   /// and a source value as input.
00252   SDOperand getVAArg(MVT::ValueType VT, SDOperand Chain, SDOperand Ptr,
00253                      SDOperand SV);
00254 
00255   /// getLoad - Loads are not normal binary operators: their result type is not
00256   /// determined by their operands, and they produce a value AND a token chain.
00257   ///
00258   SDOperand getLoad(MVT::ValueType VT, SDOperand Chain, SDOperand Ptr,
00259                     SDOperand SV);
00260   SDOperand getVecLoad(unsigned Count, MVT::ValueType VT, SDOperand Chain, 
00261                        SDOperand Ptr, SDOperand SV);
00262   SDOperand getExtLoad(unsigned Opcode, MVT::ValueType VT, SDOperand Chain,
00263                        SDOperand Ptr, SDOperand SV, MVT::ValueType EVT);
00264 
00265   // getSrcValue - construct a node to track a Value* through the backend
00266   SDOperand getSrcValue(const Value* I, int offset = 0);
00267 
00268   /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
00269   /// specified operands.  If the resultant node already exists in the DAG,
00270   /// this does not modify the specified node, instead it returns the node that
00271   /// already exists.  If the resultant node does not exist in the DAG, the
00272   /// input node is returned.  As a degenerate case, if you specify the same
00273   /// input operands as the node already has, the input node is returned.
00274   SDOperand UpdateNodeOperands(SDOperand N, SDOperand Op);
00275   SDOperand UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2);
00276   SDOperand UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2,
00277                                SDOperand Op3);
00278   SDOperand UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2,
00279                                SDOperand Op3, SDOperand Op4);
00280   SDOperand UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2,
00281                                SDOperand Op3, SDOperand Op4, SDOperand Op5);
00282   SDOperand UpdateNodeOperands(SDOperand N, const std::vector<SDOperand> &Op);
00283   
00284   /// SelectNodeTo - These are used for target selectors to *mutate* the
00285   /// specified node to have the specified return type, Target opcode, and
00286   /// operands.  Note that target opcodes are stored as
00287   /// ISD::BUILTIN_OP_END+TargetOpcode in the node opcode field.  The 0th value
00288   /// of the resultant node is returned.
00289   SDOperand SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT);
00290   SDOperand SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT, 
00291                          SDOperand Op1);
00292   SDOperand SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT, 
00293                          SDOperand Op1, SDOperand Op2);
00294   SDOperand SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT, 
00295                          SDOperand Op1, SDOperand Op2, SDOperand Op3);
00296   SDOperand SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT, 
00297                          SDOperand Op1, SDOperand Op2, SDOperand Op3, 
00298                          SDOperand Op4);
00299   SDOperand SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT, 
00300                          SDOperand Op1, SDOperand Op2, SDOperand Op3,
00301                          SDOperand Op4, SDOperand Op5);
00302   SDOperand SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT, 
00303                          SDOperand Op1, SDOperand Op2, SDOperand Op3, 
00304                          SDOperand Op4, SDOperand Op5, SDOperand Op6);
00305   SDOperand SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT, 
00306                          SDOperand Op1, SDOperand Op2, SDOperand Op3,
00307                          SDOperand Op4, SDOperand Op5, SDOperand Op6,
00308        SDOperand Op7);
00309   SDOperand SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT, 
00310                          SDOperand Op1, SDOperand Op2, SDOperand Op3,
00311                          SDOperand Op4, SDOperand Op5, SDOperand Op6,
00312        SDOperand Op7, SDOperand Op8);
00313   SDOperand SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT1, 
00314                          MVT::ValueType VT2, SDOperand Op1, SDOperand Op2);
00315   SDOperand SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT1,
00316                          MVT::ValueType VT2, SDOperand Op1, SDOperand Op2,
00317                          SDOperand Op3);
00318   SDOperand SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT1,
00319                          MVT::ValueType VT2, SDOperand Op1, SDOperand Op2,
00320                          SDOperand Op3, SDOperand Op4);
00321   SDOperand SelectNodeTo(SDNode *N, unsigned TargetOpc, MVT::ValueType VT1,
00322                          MVT::ValueType VT2, SDOperand Op1, SDOperand Op2,
00323                          SDOperand Op3, SDOperand Op4, SDOperand Op5);
00324 
00325   /// getTargetNode - These are used for target selectors to create a new node
00326   /// with specified return type(s), target opcode, and operands.
00327   ///
00328   /// Note that getTargetNode returns the resultant node.  If there is already a
00329   /// node of the specified opcode and operands, it returns that node instead of
00330   /// the current one.
00331   SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT);
00332   SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT,
00333                         SDOperand Op1);
00334   SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT,
00335                         SDOperand Op1, SDOperand Op2);
00336   SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT,
00337                         SDOperand Op1, SDOperand Op2, SDOperand Op3);
00338   SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT,
00339                         SDOperand Op1, SDOperand Op2, SDOperand Op3,
00340                         SDOperand Op4);
00341   SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT,
00342                         SDOperand Op1, SDOperand Op2, SDOperand Op3,
00343                         SDOperand Op4, SDOperand Op5);
00344   SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT,
00345                         SDOperand Op1, SDOperand Op2, SDOperand Op3,
00346                         SDOperand Op4, SDOperand Op5, SDOperand Op6);
00347   SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT,
00348                         SDOperand Op1, SDOperand Op2, SDOperand Op3,
00349                         SDOperand Op4, SDOperand Op5, SDOperand Op6,
00350                         SDOperand Op7);
00351   SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT,
00352                         SDOperand Op1, SDOperand Op2, SDOperand Op3,
00353                         SDOperand Op4, SDOperand Op5, SDOperand Op6,
00354                         SDOperand Op7, SDOperand Op8);
00355   SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT,
00356                         std::vector<SDOperand> &Ops);
00357   SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1,
00358                         MVT::ValueType VT2, SDOperand Op1);
00359   SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1,
00360                         MVT::ValueType VT2, SDOperand Op1, SDOperand Op2);
00361   SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1,
00362                         MVT::ValueType VT2, SDOperand Op1, SDOperand Op2,
00363                         SDOperand Op3);
00364   SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1,
00365                         MVT::ValueType VT2, SDOperand Op1, SDOperand Op2,
00366                         SDOperand Op3, SDOperand Op4);
00367   SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1,
00368                         MVT::ValueType VT2, SDOperand Op1, SDOperand Op2,
00369                         SDOperand Op3, SDOperand Op4, SDOperand Op5);
00370   SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1,
00371                         MVT::ValueType VT2, SDOperand Op1, SDOperand Op2,
00372                         SDOperand Op3, SDOperand Op4, SDOperand Op5,
00373                         SDOperand Op6);
00374   SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1,
00375                         MVT::ValueType VT2, SDOperand Op1, SDOperand Op2,
00376                         SDOperand Op3, SDOperand Op4, SDOperand Op5,
00377                         SDOperand Op6, SDOperand Op7);
00378   SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1,
00379                         MVT::ValueType VT2, MVT::ValueType VT3,
00380                         SDOperand Op1, SDOperand Op2);
00381   SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1,
00382                         MVT::ValueType VT2, MVT::ValueType VT3,
00383                         SDOperand Op1, SDOperand Op2,
00384                         SDOperand Op3, SDOperand Op4, SDOperand Op5);
00385   SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1,
00386                         MVT::ValueType VT2, MVT::ValueType VT3,
00387                         SDOperand Op1, SDOperand Op2,
00388                         SDOperand Op3, SDOperand Op4, SDOperand Op5,
00389                         SDOperand Op6);
00390   SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1,
00391                         MVT::ValueType VT2, MVT::ValueType VT3,
00392                         SDOperand Op1, SDOperand Op2,
00393                         SDOperand Op3, SDOperand Op4, SDOperand Op5,
00394                         SDOperand Op6, SDOperand Op7);
00395   SDNode *getTargetNode(unsigned Opcode, MVT::ValueType VT1, 
00396                         MVT::ValueType VT2, std::vector<SDOperand> &Ops);
00397   
00398   /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
00399   /// This can cause recursive merging of nodes in the DAG.  Use the first
00400   /// version if 'From' is known to have a single result, use the second
00401   /// if you have two nodes with identical results, use the third otherwise.
00402   ///
00403   /// These methods all take an optional vector, which (if not null) is 
00404   /// populated with any nodes that are deleted from the SelectionDAG, due to
00405   /// new equivalences that are discovered.
00406   ///
00407   void ReplaceAllUsesWith(SDOperand From, SDOperand Op,
00408                           std::vector<SDNode*> *Deleted = 0);
00409   void ReplaceAllUsesWith(SDNode *From, SDNode *To,
00410                           std::vector<SDNode*> *Deleted = 0);
00411   void ReplaceAllUsesWith(SDNode *From, const std::vector<SDOperand> &To,
00412                           std::vector<SDNode*> *Deleted = 0);
00413 
00414   /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
00415   /// uses of other values produced by From.Val alone.  The Deleted vector is
00416   /// handled the same was as for ReplaceAllUsesWith, but it is required for
00417   /// this method.
00418   void ReplaceAllUsesOfValueWith(SDOperand From, SDOperand To,
00419                                  std::vector<SDNode*> &Deleted);
00420 
00421   /// DeleteNode - Remove the specified node from the system.  This node must
00422   /// have no referrers.
00423   void DeleteNode(SDNode *N);
00424   
00425   void dump() const;
00426 
00427   /// InsertISelMapEntry - A helper function to insert a key / element pair
00428   /// into a SDOperand to SDOperand map. This is added to avoid the map
00429   /// insertion operator from being inlined.
00430   static void InsertISelMapEntry(std::map<SDOperand, SDOperand> &Map,
00431                                  SDNode *Key, unsigned KeyResNo,
00432                                  SDNode *Element, unsigned ElementResNo);
00433 
00434   /// InsertInFlightSetEntry - A helper function to insert a SDNode* to a
00435   /// SDNode* set. This is added to avoid the set insertion operator from being
00436   /// inlined.
00437   static void InsertInFlightSetEntry(std::set<SDNode*> &Set, SDNode *N);
00438 
00439   /// RemoveInFlightSetEntry - A helper function to remove a SDNode* from a
00440   /// SDNode* set. This is added to avoid the set removal operator from being
00441   /// inlined.
00442   static void RemoveInFlightSetEntry(std::set<SDNode*> &Set, SDNode *N);
00443   
00444 private:
00445   void RemoveNodeFromCSEMaps(SDNode *N);
00446   SDNode *AddNonLeafNodeToCSEMaps(SDNode *N);
00447   SDNode **FindModifiedNodeSlot(SDNode *N, SDOperand Op);
00448   SDNode **FindModifiedNodeSlot(SDNode *N, SDOperand Op1, SDOperand Op2);
00449   SDNode **FindModifiedNodeSlot(SDNode *N, const std::vector<SDOperand> &Ops);
00450 
00451   void DestroyDeadNode(SDNode *N);
00452   void DeleteNodeNotInCSEMaps(SDNode *N);
00453   void setNodeValueTypes(SDNode *N, std::vector<MVT::ValueType> &RetVals);
00454   void setNodeValueTypes(SDNode *N, MVT::ValueType VT1, MVT::ValueType VT2);
00455   
00456   
00457   /// SimplifySetCC - Try to simplify a setcc built with the specified operands 
00458   /// and cc.  If unable to simplify it, return a null SDOperand.
00459   SDOperand SimplifySetCC(MVT::ValueType VT, SDOperand N1,
00460                           SDOperand N2, ISD::CondCode Cond);
00461   
00462   // List of non-single value types.
00463   std::list<std::vector<MVT::ValueType> > VTList;
00464   
00465   // Maps to auto-CSE operations.
00466   std::map<std::pair<unsigned, MVT::ValueType>, SDNode *> NullaryOps;
00467   std::map<std::pair<unsigned, std::pair<SDOperand, MVT::ValueType> >,
00468            SDNode *> UnaryOps;
00469   std::map<std::pair<unsigned, std::pair<SDOperand, SDOperand> >,
00470            SDNode *> BinaryOps;
00471 
00472   std::map<std::pair<unsigned, MVT::ValueType>, RegisterSDNode*> RegNodes;
00473   std::vector<CondCodeSDNode*> CondCodeNodes;
00474 
00475   std::map<std::pair<SDOperand, std::pair<SDOperand, MVT::ValueType> >,
00476            SDNode *> Loads;
00477 
00478   std::map<std::pair<const GlobalValue*, int>, SDNode*> GlobalValues;
00479   std::map<std::pair<const GlobalValue*, int>, SDNode*> TargetGlobalValues;
00480   std::map<std::pair<uint64_t, MVT::ValueType>, SDNode*> Constants;
00481   std::map<std::pair<uint64_t, MVT::ValueType>, SDNode*> TargetConstants;
00482   std::map<std::pair<uint64_t, MVT::ValueType>, SDNode*> ConstantFPs;
00483   std::map<std::pair<uint64_t, MVT::ValueType>, SDNode*> TargetConstantFPs;
00484   std::map<int, SDNode*> FrameIndices, TargetFrameIndices, JumpTableIndices,
00485     TargetJumpTableIndices;
00486   std::map<std::pair<Constant *,
00487                      std::pair<int, unsigned> >, SDNode*> ConstantPoolIndices;
00488   std::map<std::pair<Constant *,
00489                  std::pair<int, unsigned> >, SDNode*> TargetConstantPoolIndices;
00490   std::map<MachineBasicBlock *, SDNode*> BBNodes;
00491   std::vector<SDNode*> ValueTypeNodes;
00492   std::map<std::string, SDNode*> ExternalSymbols;
00493   std::map<std::string, SDNode*> TargetExternalSymbols;
00494   std::map<std::string, StringSDNode*> StringNodes;
00495   std::map<std::pair<unsigned,
00496                      std::pair<MVT::ValueType, std::vector<SDOperand> > >,
00497            SDNode*> OneResultNodes;
00498   std::map<std::pair<unsigned,
00499                      std::pair<std::vector<MVT::ValueType>,
00500                                std::vector<SDOperand> > >,
00501            SDNode*> ArbitraryNodes;
00502 };
00503 
00504 template <> struct GraphTraits<SelectionDAG*> : public GraphTraits<SDNode*> {
00505   typedef SelectionDAG::allnodes_iterator nodes_iterator;
00506   static nodes_iterator nodes_begin(SelectionDAG *G) {
00507     return G->allnodes_begin();
00508   }
00509   static nodes_iterator nodes_end(SelectionDAG *G) {
00510     return G->allnodes_end();
00511   }
00512 };
00513 
00514 }  // end namespace llvm
00515 
00516 #endif