1 //===- DependenceGraph.h - Dependence graph for a function ------*- C++ -*-===//
3 // This file provides an explicit representation for the dependence graph
4 // of a function, with one node per instruction and one edge per dependence.
5 // Dependences include both data and control dependences.
7 // Each dep. graph node (class DepGraphNode) keeps lists of incoming and
8 // outgoing dependence edges.
10 // Each dep. graph edge (class Dependence) keeps a pointer to one end-point
11 // of the dependence. This saves space and is important because dep. graphs
12 // can grow quickly. It works just fine because the standard idiom is to
13 // start with a known node and enumerate the dependences to or from that node.
14 //===----------------------------------------------------------------------===//
17 #ifndef LLVM_ANALYSIS_DEPENDENCEGRAPH_H
18 #define LLVM_ANALYSIS_DEPENDENCEGRAPH_H
21 #include <Support/NonCopyable.h>
22 #include <Support/hash_map>
31 class DependenceGraph;
34 //----------------------------------------------------------------------------
35 // enum DependenceType: The standard data dependence types.
36 //----------------------------------------------------------------------------
42 OutputDependence = 0x4,
43 ControlDependence = 0x8, // from a terminator to some other instr.
44 IncomingFlag = 0x10 // is this an incoming or outgoing dep?
47 #undef SUPPORTING_LOOP_DEPENDENCES
48 #ifdef SUPPORTING_LOOP_DEPENDENCES
49 typedef int DependenceDistance; // negative means unknown distance
50 typedef short DependenceLevel; // 0 means global level outside loops
54 //----------------------------------------------------------------------------
57 // A representation of a simple (non-loop-related) dependence.
58 //----------------------------------------------------------------------------
61 DepGraphNode* toOrFromNode;
62 unsigned char depType;
65 /*ctor*/ Dependence (DepGraphNode* toOrFromN,
68 : toOrFromNode(toOrFromN),
69 depType(type | (isIncoming? IncomingFlag : 0x0)) { }
71 /* copy ctor*/ Dependence (const Dependence& D)
72 : toOrFromNode(D.toOrFromNode),
73 depType(D.depType) { }
75 bool operator==(const Dependence& D) {
76 return toOrFromNode == D.toOrFromNode && depType == D.depType;
79 /// Get information about the type of dependence.
81 unsigned getDepType() const {
85 /// Get source or sink depending on what type of node this is!
87 DepGraphNode* getSrc() {
88 assert(depType & IncomingFlag); return toOrFromNode;
90 const DepGraphNode* getSrc() const {
91 assert(depType & IncomingFlag); return toOrFromNode;
94 DepGraphNode* getSink() {
95 assert(! (depType & IncomingFlag)); return toOrFromNode;
97 const DepGraphNode* getSink() const {
98 assert(! (depType & IncomingFlag)); return toOrFromNode;
101 /// Debugging support methods
103 void print(std::ostream &O) const;
105 // Default constructor: Do not use directly except for graph builder code
107 /*ctor*/ Dependence() : toOrFromNode(NULL), depType(NoDependence) { }
111 #ifdef SUPPORTING_LOOP_DEPENDENCES
112 struct LoopDependence: public Dependence {
113 DependenceDirection dir;
114 DependenceDistance distance;
115 DependenceLevel level;
116 LoopInfo* enclosingLoop;
121 //----------------------------------------------------------------------------
122 // class DepGraphNode:
124 // A representation of a single node in a dependence graph, corresponding
125 // to a single instruction.
126 //----------------------------------------------------------------------------
130 std::vector<Dependence> inDeps;
131 std::vector<Dependence> outDeps;
132 friend class DependenceGraph;
134 typedef std::vector<Dependence>:: iterator iterator;
135 typedef std::vector<Dependence>::const_iterator const_iterator;
137 iterator inDepBegin() { return inDeps.begin(); }
138 const_iterator inDepBegin() const { return inDeps.begin(); }
139 iterator inDepEnd() { return inDeps.end(); }
140 const_iterator inDepEnd() const { return inDeps.end(); }
142 iterator outDepBegin() { return outDeps.begin(); }
143 const_iterator outDepBegin() const { return outDeps.begin(); }
144 iterator outDepEnd() { return outDeps.end(); }
145 const_iterator outDepEnd() const { return outDeps.end(); }
149 DepGraphNode(Instruction& I) : instr(&I) { }
151 Instruction& getInstr() { return *instr; }
152 const Instruction& getInstr() const { return *instr; }
154 /// Debugging support methods
156 void print(std::ostream &O) const;
160 //----------------------------------------------------------------------------
161 // class DependenceGraph:
163 // A representation of a dependence graph for a procedure.
164 // The primary query operation here is to look up a DepGraphNode for
165 // a particular instruction, and then use the in/out dependence iterators
167 //----------------------------------------------------------------------------
169 class DependenceGraph: public NonCopyable {
170 typedef hash_map<Instruction*, DepGraphNode*> DepNodeMapType;
171 typedef DepNodeMapType:: iterator map_iterator;
172 typedef DepNodeMapType::const_iterator const_map_iterator;
174 DepNodeMapType depNodeMap;
176 inline DepGraphNode* getNodeInternal(Instruction& inst,
177 bool createIfMissing = false) {
178 map_iterator I = depNodeMap.find(&inst);
179 if (I == depNodeMap.end())
180 return (!createIfMissing)? NULL :
182 std::make_pair(&inst, new DepGraphNode(inst))).first->second;
188 typedef std::vector<Dependence>:: iterator iterator;
189 typedef std::vector<Dependence>::const_iterator const_iterator;
192 DependenceGraph() { }
195 /// Get the graph node for an instruction. There will be one if and
196 /// only if there are any dependences incident on this instruction.
197 /// If there is none, these methods will return NULL.
199 DepGraphNode* getNode(Instruction& inst, bool createIfMissing = false) {
200 return getNodeInternal(inst, createIfMissing);
202 const DepGraphNode* getNode(const Instruction& inst) const {
203 return const_cast<DependenceGraph*>(this)
204 ->getNodeInternal(const_cast<Instruction&>(inst));
207 iterator inDepBegin ( DepGraphNode& T) { return T.inDeps.begin(); }
208 const_iterator inDepBegin (const DepGraphNode& T) const { return T.inDeps.begin(); }
210 iterator inDepEnd ( DepGraphNode& T) { return T.inDeps.end(); }
211 const_iterator inDepEnd (const DepGraphNode& T) const { return T.inDeps.end(); }
213 iterator outDepBegin( DepGraphNode& F) { return F.outDeps.begin();}
214 const_iterator outDepBegin(const DepGraphNode& F) const { return F.outDeps.begin();}
216 iterator outDepEnd ( DepGraphNode& F) { return F.outDeps.end(); }
217 const_iterator outDepEnd (const DepGraphNode& F) const { return F.outDeps.end(); }
219 /// Debugging support methods
221 void print(const Function& func, std::ostream &O) const;
224 /// Functions for adding and modifying the dependence graph.
225 /// These should to be used only by dependence analysis implementations.
226 void AddSimpleDependence(Instruction& fromI,
228 DependenceType depType) {
229 DepGraphNode* fromNode = getNodeInternal(fromI, /*create*/ true);
230 DepGraphNode* toNode = getNodeInternal(toI, /*create*/ true);
231 fromNode->outDeps.push_back(Dependence(toNode, depType, false));
232 toNode-> inDeps. push_back(Dependence(fromNode, depType, true));
235 #ifdef SUPPORTING_LOOP_DEPENDENCES
236 /// This interface is a placeholder to show what information is needed.
237 /// It will probably change when it starts being used.
238 void AddLoopDependence(Instruction& fromI,
240 DependenceType depType,
241 DependenceDirection dir,
242 DependenceDistance distance,
243 DependenceLevel level,
244 LoopInfo* enclosingLoop);
245 #endif // SUPPORTING_LOOP_DEPENDENCES
248 //===----------------------------------------------------------------------===//