LLVM API Documentation

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