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.
15 //===----------------------------------------------------------------------===//
17 #ifndef LLVM_ANALYSIS_DEPENDENCEGRAPH_H
18 #define LLVM_ANALYSIS_DEPENDENCEGRAPH_H
20 #include "Support/hash_map"
30 class DependenceGraph;
33 //----------------------------------------------------------------------------
34 // enum DependenceType: The standard data dependence types.
35 //----------------------------------------------------------------------------
41 OutputDependence = 0x4,
42 ControlDependence = 0x8, // from a terminator to some other instr.
43 IncomingFlag = 0x10 // is this an incoming or outgoing dep?
47 //----------------------------------------------------------------------------
50 // A representation of a simple (non-loop-related) dependence.
51 //----------------------------------------------------------------------------
54 DepGraphNode* toOrFromNode;
55 unsigned char depType;
58 Dependence(DepGraphNode* toOrFromN, DependenceType type, bool isIncoming)
59 : toOrFromNode(toOrFromN),
60 depType(type | (isIncoming? IncomingFlag : 0x0)) { }
62 /* copy ctor*/ Dependence (const Dependence& D)
63 : toOrFromNode(D.toOrFromNode),
64 depType(D.depType) { }
66 bool operator==(const Dependence& D) const {
67 return toOrFromNode == D.toOrFromNode && depType == D.depType;
70 /// Get information about the type of dependence.
72 unsigned getDepType() const {
76 /// Get source or sink depending on what type of node this is!
78 DepGraphNode* getSrc() {
79 assert(depType & IncomingFlag); return toOrFromNode;
81 const DepGraphNode* getSrc() const {
82 assert(depType & IncomingFlag); return toOrFromNode;
85 DepGraphNode* getSink() {
86 assert(! (depType & IncomingFlag)); return toOrFromNode;
88 const DepGraphNode* getSink() const {
89 assert(! (depType & IncomingFlag)); return toOrFromNode;
92 /// Debugging support methods
94 void print(std::ostream &O) const;
96 // Default constructor: Do not use directly except for graph builder code
98 /*ctor*/ Dependence() : toOrFromNode(NULL), depType(NoDependence) { }
102 #ifdef SUPPORTING_LOOP_DEPENDENCES
103 struct LoopDependence: public Dependence {
104 DependenceDirection dir;
107 LoopInfo* enclosingLoop;
112 //----------------------------------------------------------------------------
113 // class DepGraphNode:
115 // A representation of a single node in a dependence graph, corresponding
116 // to a single instruction.
117 //----------------------------------------------------------------------------
121 std::vector<Dependence> inDeps;
122 std::vector<Dependence> outDeps;
123 friend class DependenceGraph;
125 typedef std::vector<Dependence>:: iterator iterator;
126 typedef std::vector<Dependence>::const_iterator const_iterator;
128 iterator inDepBegin() { return inDeps.begin(); }
129 const_iterator inDepBegin() const { return inDeps.begin(); }
130 iterator inDepEnd() { return inDeps.end(); }
131 const_iterator inDepEnd() const { return inDeps.end(); }
133 iterator outDepBegin() { return outDeps.begin(); }
134 const_iterator outDepBegin() const { return outDeps.begin(); }
135 iterator outDepEnd() { return outDeps.end(); }
136 const_iterator outDepEnd() const { return outDeps.end(); }
140 DepGraphNode(Instruction& I) : instr(&I) { }
142 Instruction& getInstr() { return *instr; }
143 const Instruction& getInstr() const { return *instr; }
145 /// Debugging support methods
147 void print(std::ostream &O) const;
151 //----------------------------------------------------------------------------
152 // class DependenceGraph:
154 // A representation of a dependence graph for a procedure.
155 // The primary query operation here is to look up a DepGraphNode for
156 // a particular instruction, and then use the in/out dependence iterators
158 //----------------------------------------------------------------------------
160 class DependenceGraph {
161 DependenceGraph(const DependenceGraph&); // DO NOT IMPLEMENT
162 void operator=(const DependenceGraph&); // DO NOT IMPLEMENT
164 typedef hash_map<Instruction*, DepGraphNode*> DepNodeMapType;
165 typedef DepNodeMapType:: iterator map_iterator;
166 typedef DepNodeMapType::const_iterator const_map_iterator;
168 DepNodeMapType depNodeMap;
170 inline DepGraphNode* getNodeInternal(Instruction& inst,
171 bool createIfMissing = false) {
172 map_iterator I = depNodeMap.find(&inst);
173 if (I == depNodeMap.end())
174 return (!createIfMissing)? NULL :
176 std::make_pair(&inst, new DepGraphNode(inst))).first->second;
182 typedef std::vector<Dependence>:: iterator iterator;
183 typedef std::vector<Dependence>::const_iterator const_iterator;
186 DependenceGraph() { }
189 /// Get the graph node for an instruction. There will be one if and
190 /// only if there are any dependences incident on this instruction.
191 /// If there is none, these methods will return NULL.
193 DepGraphNode* getNode(Instruction& inst, bool createIfMissing = false) {
194 return getNodeInternal(inst, createIfMissing);
196 const DepGraphNode* getNode(const Instruction& inst) const {
197 return const_cast<DependenceGraph*>(this)
198 ->getNodeInternal(const_cast<Instruction&>(inst));
201 iterator inDepBegin(DepGraphNode& T) {
202 return T.inDeps.begin();
204 const_iterator inDepBegin (const DepGraphNode& T) const {
205 return T.inDeps.begin();
208 iterator inDepEnd(DepGraphNode& T) {
209 return T.inDeps.end();
211 const_iterator inDepEnd(const DepGraphNode& T) const {
212 return T.inDeps.end();
215 iterator outDepBegin(DepGraphNode& F) {
216 return F.outDeps.begin();
218 const_iterator outDepBegin(const DepGraphNode& F) const {
219 return F.outDeps.begin();
222 iterator outDepEnd(DepGraphNode& F) {
223 return F.outDeps.end();
225 const_iterator outDepEnd(const DepGraphNode& F) const {
226 return F.outDeps.end();
229 /// Debugging support methods
231 void print(const Function& func, std::ostream &O) const;
234 /// Functions for adding and modifying the dependence graph.
235 /// These should to be used only by dependence analysis implementations.
236 void AddSimpleDependence(Instruction& fromI,
238 DependenceType depType) {
239 DepGraphNode* fromNode = getNodeInternal(fromI, /*create*/ true);
240 DepGraphNode* toNode = getNodeInternal(toI, /*create*/ true);
241 fromNode->outDeps.push_back(Dependence(toNode, depType, false));
242 toNode-> inDeps. push_back(Dependence(fromNode, depType, true));
245 #ifdef SUPPORTING_LOOP_DEPENDENCES
246 /// This interface is a placeholder to show what information is needed.
247 /// It will probably change when it starts being used.
248 void AddLoopDependence(Instruction& fromI,
250 DependenceType depType,
251 DependenceDirection dir,
254 LoopInfo* enclosingLoop);
255 #endif // SUPPORTING_LOOP_DEPENDENCES
258 //===----------------------------------------------------------------------===//