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