1 //===-- SchedGraph.h - Scheduling Graph -------------------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
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.
8 //===----------------------------------------------------------------------===//
10 // This is a scheduling graph based on SSA graph plus extra dependence edges
11 // capturing dependences due to machine resources (machine registers, CC
12 // registers, and any others).
14 // This graph tries to leverage the SSA graph as much as possible, but captures
15 // the extra dependences through a common interface.
17 //===----------------------------------------------------------------------===//
19 #ifndef LLVM_CODEGEN_SCHEDGRAPH_H
20 #define LLVM_CODEGEN_SCHEDGRAPH_H
22 #include "llvm/CodeGen/SchedGraphCommon.h"
23 #include "llvm/CodeGen/MachineInstr.h"
24 #include "llvm/Transforms/Scalar.h"
25 #include "Support/hash_map"
26 #include "Support/GraphTraits.h"
31 class ValueToDefVecMap;
34 class SchedGraphNode : public SchedGraphNodeCommon {
36 MachineBasicBlock *MBB;
37 const MachineInstr *MI;
40 SchedGraphNode(unsigned nodeId, MachineBasicBlock *mbb, int indexInBB,
41 const TargetMachine& Target);
44 friend class SchedGraph; // give access for ctor and dtor
45 friend class SchedGraphEdge; // give access for adding edges
50 const MachineInstr* getMachineInstr() const { return MI; }
51 const MachineOpCode getOpcode() const { return MI->getOpcode(); }
52 bool isDummyNode() const { return (MI == NULL); }
53 MachineBasicBlock &getMachineBasicBlock() const { return *MBB; }
55 void print(std::ostream &os) const;
58 class SchedGraph : public SchedGraphCommon {
59 MachineBasicBlock &MBB;
60 hash_map<const MachineInstr*, SchedGraphNode*> GraphMap;
63 typedef hash_map<const MachineInstr*, SchedGraphNode*>::const_iterator iterator;
64 typedef hash_map<const MachineInstr*, SchedGraphNode*>::const_iterator const_iterator;
66 MachineBasicBlock& getBasicBlock() const{return MBB;}
67 const unsigned int getNumNodes() const { return GraphMap.size()+2; }
68 SchedGraphNode* getGraphNodeForInstr(const MachineInstr* MI) const {
69 const_iterator onePair = find(MI);
70 return (onePair != end())? onePair->second : NULL;
77 SchedGraph(MachineBasicBlock& mbb, const TargetMachine& TM);
80 // Unordered iterators.
81 // Return values is pair<const MachineIntr*,SchedGraphNode*>.
83 hash_map<const MachineInstr*, SchedGraphNode*>::const_iterator begin() const {
84 return GraphMap.begin();
86 hash_map<const MachineInstr*, SchedGraphNode*>::const_iterator end() const {
87 return GraphMap.end();
90 unsigned size() { return GraphMap.size(); }
91 iterator find(const MachineInstr *MI) const { return GraphMap.find(MI); }
93 SchedGraphNode *&operator[](const MachineInstr *MI) {
98 friend class SchedGraphSet; // give access to ctor
100 inline void noteGraphNodeForInstr (const MachineInstr* minstr,
101 SchedGraphNode* node) {
102 assert((*this)[minstr] == NULL);
103 (*this)[minstr] = node;
109 void buildGraph(const TargetMachine& target);
111 void buildNodesForBB(const TargetMachine& target,MachineBasicBlock &MBB,
112 std::vector<SchedGraphNode*>& memNV,
113 std::vector<SchedGraphNode*>& callNV,
114 RegToRefVecMap& regToRefVecMap,
115 ValueToDefVecMap& valueToDefVecMap);
118 void findDefUseInfoAtInstr(const TargetMachine& target, SchedGraphNode* node,
119 std::vector<SchedGraphNode*>& memNV,
120 std::vector<SchedGraphNode*>& callNV,
121 RegToRefVecMap& regToRefVecMap,
122 ValueToDefVecMap& valueToDefVecMap);
124 void addEdgesForInstruction(const MachineInstr& minstr,
125 const ValueToDefVecMap& valueToDefVecMap,
126 const TargetMachine& target);
128 void addCDEdges(const TerminatorInst* term, const TargetMachine& target);
130 void addMemEdges(const std::vector<SchedGraphNode*>& memNod,
131 const TargetMachine& target);
133 void addCallCCEdges(const std::vector<SchedGraphNode*>& memNod,
134 MachineBasicBlock& bbMvec,
135 const TargetMachine& target);
137 void addCallDepEdges(const std::vector<SchedGraphNode*>& callNV,
138 const TargetMachine& target);
140 void addMachineRegEdges(RegToRefVecMap& regToRefVecMap,
141 const TargetMachine& target);
143 void addEdgesForValue(SchedGraphNode* refNode, const RefVec& defVec,
144 const Value* defValue, bool refNodeIsDef,
145 bool refNodeIsDefAndUse,
146 const TargetMachine& target);
148 void addDummyEdges();
154 class SchedGraphSet {
155 const Function* function;
156 std::vector<SchedGraph*> Graphs;
159 void buildGraphsForMethod(const Function *F, const TargetMachine& target);
161 inline void addGraph(SchedGraph* graph) {
162 assert(graph != NULL);
163 Graphs.push_back(graph);
167 SchedGraphSet(const Function *function, const TargetMachine& target);
171 typedef std::vector<SchedGraph*>::const_iterator iterator;
172 typedef std::vector<SchedGraph*>::const_iterator const_iterator;
174 std::vector<SchedGraph*>::const_iterator begin() const { return Graphs.begin(); }
175 std::vector<SchedGraph*>::const_iterator end() const { return Graphs.end(); }
186 // sg_pred_const_iterator
188 typedef SGPredIterator<SchedGraphNode, SchedGraphEdge, SchedGraphNode::iterator>
190 typedef SGPredIterator<const SchedGraphNode, const SchedGraphEdge,SchedGraphNode::const_iterator>
191 sg_pred_const_iterator;
193 inline sg_pred_iterator pred_begin(SchedGraphNode *N) {
194 return sg_pred_iterator(N->beginInEdges());
196 inline sg_pred_iterator pred_end(SchedGraphNode *N) {
197 return sg_pred_iterator(N->endInEdges());
199 inline sg_pred_const_iterator pred_begin(const SchedGraphNode *N) {
200 return sg_pred_const_iterator(N->beginInEdges());
202 inline sg_pred_const_iterator pred_end(const SchedGraphNode *N) {
203 return sg_pred_const_iterator(N->endInEdges());
209 // sg_succ_const_iterator
211 typedef SGSuccIterator<SchedGraphNode, SchedGraphEdge, SchedGraphNode::iterator>
213 typedef SGSuccIterator<const SchedGraphNode, const SchedGraphEdge,SchedGraphNode::const_iterator>
214 sg_succ_const_iterator;
216 inline sg_succ_iterator succ_begin(SchedGraphNode *N) {
217 return sg_succ_iterator(N->beginOutEdges());
219 inline sg_succ_iterator succ_end(SchedGraphNode *N) {
220 return sg_succ_iterator(N->endOutEdges());
222 inline sg_succ_const_iterator succ_begin(const SchedGraphNode *N) {
223 return sg_succ_const_iterator(N->beginOutEdges());
225 inline sg_succ_const_iterator succ_end(const SchedGraphNode *N) {
226 return sg_succ_const_iterator(N->endOutEdges());
229 // Provide specializations of GraphTraits to be able to use graph iterators on
230 // the scheduling graph!
232 template <> struct GraphTraits<SchedGraph*> {
233 typedef SchedGraphNode NodeType;
234 typedef sg_succ_iterator ChildIteratorType;
236 static inline NodeType *getEntryNode(SchedGraph *SG) { return (NodeType*)SG->getRoot(); }
237 static inline ChildIteratorType child_begin(NodeType *N) {
238 return succ_begin(N);
240 static inline ChildIteratorType child_end(NodeType *N) {
245 template <> struct GraphTraits<const SchedGraph*> {
246 typedef const SchedGraphNode NodeType;
247 typedef sg_succ_const_iterator ChildIteratorType;
249 static inline NodeType *getEntryNode(const SchedGraph *SG) {
250 return (NodeType*)SG->getRoot();
252 static inline ChildIteratorType child_begin(NodeType *N) {
253 return succ_begin(N);
255 static inline ChildIteratorType child_end(NodeType *N) {
260 } // End llvm namespace