LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

SchedGraph.h

Go to the documentation of this file.
00001 //===-- SchedGraph.h - Scheduling Graph -------------------------*- 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 is a scheduling graph based on SSA graph plus extra dependence edges
00011 // capturing dependences due to machine resources (machine registers, CC
00012 // registers, and any others).
00013 // 
00014 // This graph tries to leverage the SSA graph as much as possible, but captures
00015 // the extra dependences through a common interface.
00016 // 
00017 //===----------------------------------------------------------------------===//
00018 
00019 #ifndef LLVM_CODEGEN_SCHEDGRAPH_H
00020 #define LLVM_CODEGEN_SCHEDGRAPH_H
00021 
00022 #include "llvm/CodeGen/SchedGraphCommon.h"
00023 #include "llvm/CodeGen/MachineInstr.h"
00024 #include "llvm/Transforms/Scalar.h"
00025 #include "llvm/ADT/hash_map"
00026 #include "llvm/ADT/GraphTraits.h"
00027 
00028 namespace llvm {
00029 
00030 class RegToRefVecMap;
00031 class ValueToDefVecMap;
00032 class RefVec;
00033 
00034 class SchedGraphNode : public SchedGraphNodeCommon {
00035 
00036   MachineBasicBlock *MBB;
00037   const MachineInstr *MI;
00038 
00039 
00040   SchedGraphNode(unsigned nodeId, MachineBasicBlock *mbb, int indexInBB, 
00041      const TargetMachine& Target);
00042   ~SchedGraphNode();
00043 
00044   friend class SchedGraph;    // give access for ctor and dtor
00045   friend class SchedGraphEdge;    // give access for adding edges
00046 
00047 public:
00048 
00049   // Accessor methods
00050   const MachineInstr* getMachineInstr() const { return MI; }
00051   const MachineOpCode getOpcode() const { return MI->getOpcode(); }
00052   bool isDummyNode() const { return (MI == NULL); }
00053   MachineBasicBlock &getMachineBasicBlock() const { return *MBB; }
00054 
00055   void print(std::ostream &os) const;
00056 };
00057 
00058 class SchedGraph : public SchedGraphCommon {
00059   MachineBasicBlock &MBB;
00060   hash_map<const MachineInstr*, SchedGraphNode*> GraphMap;
00061   
00062 public:
00063   typedef hash_map<const MachineInstr*, SchedGraphNode*>::const_iterator iterator;
00064   typedef hash_map<const MachineInstr*, SchedGraphNode*>::const_iterator const_iterator;
00065     
00066   MachineBasicBlock& getBasicBlock() const{return MBB;}
00067   const unsigned int getNumNodes() const { return GraphMap.size()+2; }
00068   SchedGraphNode* getGraphNodeForInstr(const MachineInstr* MI) const {
00069     const_iterator onePair = find(MI);
00070     return (onePair != end())? onePair->second : NULL;
00071   }
00072   
00073   // Debugging support
00074   void dump() const;
00075   
00076 protected:
00077   SchedGraph(MachineBasicBlock& mbb, const TargetMachine& TM);
00078   ~SchedGraph();
00079 
00080   // Unordered iterators.
00081   // Return values is pair<const MachineIntr*,SchedGraphNode*>.
00082   //
00083   hash_map<const MachineInstr*, SchedGraphNode*>::const_iterator begin() const {
00084     return GraphMap.begin();
00085   }
00086   hash_map<const MachineInstr*, SchedGraphNode*>::const_iterator end() const {
00087     return GraphMap.end();
00088   }
00089  
00090   unsigned size() { return GraphMap.size(); }
00091   iterator find(const MachineInstr *MI) const { return GraphMap.find(MI); }
00092   
00093   SchedGraphNode *&operator[](const MachineInstr *MI) {
00094     return GraphMap[MI];
00095   }
00096   
00097 private:
00098   friend class SchedGraphSet;   // give access to ctor
00099     
00100   inline void noteGraphNodeForInstr (const MachineInstr* minstr,
00101            SchedGraphNode* node) {
00102     assert((*this)[minstr] == NULL);
00103     (*this)[minstr] = node;
00104   }
00105 
00106   //
00107   // Graph builder
00108   //
00109   void buildGraph(const TargetMachine& target);
00110   
00111   void  buildNodesForBB(const TargetMachine& target,MachineBasicBlock &MBB,
00112       std::vector<SchedGraphNode*>& memNV,
00113       std::vector<SchedGraphNode*>& callNV,
00114       RegToRefVecMap& regToRefVecMap,
00115       ValueToDefVecMap& valueToDefVecMap);
00116 
00117   
00118   void findDefUseInfoAtInstr(const TargetMachine& target, SchedGraphNode* node,
00119            std::vector<SchedGraphNode*>& memNV,
00120            std::vector<SchedGraphNode*>& callNV,
00121            RegToRefVecMap& regToRefVecMap,
00122            ValueToDefVecMap& valueToDefVecMap);
00123                                          
00124   void addEdgesForInstruction(const MachineInstr& minstr,
00125             const ValueToDefVecMap& valueToDefVecMap,
00126             const TargetMachine& target);
00127   
00128   void addCDEdges(const TerminatorInst* term, const TargetMachine& target);
00129   
00130   void addMemEdges(const std::vector<SchedGraphNode*>& memNod,
00131        const TargetMachine& target);
00132   
00133   void addCallCCEdges(const std::vector<SchedGraphNode*>& memNod,
00134           MachineBasicBlock& bbMvec,
00135           const TargetMachine& target);
00136 
00137   void addCallDepEdges(const std::vector<SchedGraphNode*>& callNV,
00138            const TargetMachine& target);
00139   
00140   void addMachineRegEdges(RegToRefVecMap& regToRefVecMap,
00141         const TargetMachine& target);
00142   
00143   void addEdgesForValue(SchedGraphNode* refNode, const RefVec& defVec,
00144       const Value* defValue, bool  refNodeIsDef,
00145       bool  refNodeIsDefAndUse,
00146       const TargetMachine& target);
00147 
00148   void addDummyEdges();
00149 
00150 };
00151 
00152 
00153 
00154 class SchedGraphSet {
00155   const Function* function;
00156   std::vector<SchedGraph*> Graphs;
00157 
00158   // Graph builder
00159   void buildGraphsForMethod(const Function *F, const TargetMachine& target);
00160 
00161   inline void addGraph(SchedGraph* graph) {
00162     assert(graph != NULL);
00163     Graphs.push_back(graph);
00164   }  
00165 
00166 public:
00167   SchedGraphSet(const Function *function, const TargetMachine& target);
00168   ~SchedGraphSet();
00169   
00170   //iterators
00171   typedef std::vector<SchedGraph*>::const_iterator iterator;
00172   typedef std::vector<SchedGraph*>::const_iterator const_iterator;
00173 
00174   std::vector<SchedGraph*>::const_iterator begin() const { return Graphs.begin(); }
00175   std::vector<SchedGraph*>::const_iterator end() const { return Graphs.end(); }
00176 
00177   // Debugging support
00178   void dump() const;
00179 };
00180 
00181 
00182 
00183 
00184 // 
00185 // sg_pred_iterator
00186 // sg_pred_const_iterator
00187 //
00188 typedef SGPredIterator<SchedGraphNode, SchedGraphEdge, SchedGraphNode::iterator>
00189     sg_pred_iterator;
00190 typedef SGPredIterator<const SchedGraphNode, const SchedGraphEdge,SchedGraphNode::const_iterator>
00191     sg_pred_const_iterator;
00192 
00193 inline sg_pred_iterator pred_begin(SchedGraphNode *N) {
00194   return sg_pred_iterator(N->beginInEdges());
00195 }
00196 inline sg_pred_iterator pred_end(SchedGraphNode *N) {
00197   return sg_pred_iterator(N->endInEdges());
00198 }
00199 inline sg_pred_const_iterator pred_begin(const SchedGraphNode *N) {
00200   return sg_pred_const_iterator(N->beginInEdges());
00201 }
00202 inline sg_pred_const_iterator pred_end(const SchedGraphNode *N) {
00203   return sg_pred_const_iterator(N->endInEdges());
00204 }
00205 
00206 
00207 // 
00208 // sg_succ_iterator
00209 // sg_succ_const_iterator
00210 //
00211 typedef SGSuccIterator<SchedGraphNode, SchedGraphEdge, SchedGraphNode::iterator>
00212     sg_succ_iterator;
00213 typedef SGSuccIterator<const SchedGraphNode, const SchedGraphEdge,SchedGraphNode::const_iterator>
00214     sg_succ_const_iterator;
00215 
00216 inline sg_succ_iterator succ_begin(SchedGraphNode *N) {
00217   return sg_succ_iterator(N->beginOutEdges());
00218 }
00219 inline sg_succ_iterator succ_end(SchedGraphNode *N) {
00220   return sg_succ_iterator(N->endOutEdges());
00221 }
00222 inline sg_succ_const_iterator succ_begin(const SchedGraphNode *N) {
00223   return sg_succ_const_iterator(N->beginOutEdges());
00224 }
00225 inline sg_succ_const_iterator succ_end(const SchedGraphNode *N) {
00226   return sg_succ_const_iterator(N->endOutEdges());
00227 }
00228 
00229 // Provide specializations of GraphTraits to be able to use graph iterators on
00230 // the scheduling graph!
00231 //
00232 template <> struct GraphTraits<SchedGraph*> {
00233   typedef SchedGraphNode NodeType;
00234   typedef sg_succ_iterator ChildIteratorType;
00235 
00236   static inline NodeType *getEntryNode(SchedGraph *SG) { return (NodeType*)SG->getRoot(); }
00237   static inline ChildIteratorType child_begin(NodeType *N) { 
00238     return succ_begin(N); 
00239   }
00240   static inline ChildIteratorType child_end(NodeType *N) { 
00241     return succ_end(N);
00242   }
00243 };
00244 
00245 template <> struct GraphTraits<const SchedGraph*> {
00246   typedef const SchedGraphNode NodeType;
00247   typedef sg_succ_const_iterator ChildIteratorType;
00248 
00249   static inline NodeType *getEntryNode(const SchedGraph *SG) {
00250     return (NodeType*)SG->getRoot();
00251   }
00252   static inline ChildIteratorType child_begin(NodeType *N) { 
00253     return succ_begin(N); 
00254   }
00255   static inline ChildIteratorType child_end(NodeType *N) { 
00256     return succ_end(N);
00257   }
00258 };
00259 
00260 } // End llvm namespace
00261 
00262 #endif