1 //===- DependenceGraph.h - Dependence graph for a function ------*- 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 file provides an explicit representation for the dependence graph
11 // of a function, with one node per instruction and one edge per dependence.
12 // Dependences include both data and control dependences.
14 // Each dep. graph node (class DepGraphNode) keeps lists of incoming and
15 // outgoing dependence edges.
17 // Each dep. graph edge (class Dependence) keeps a pointer to one end-point
18 // of the dependence. This saves space and is important because dep. graphs
19 // can grow quickly. It works just fine because the standard idiom is to
20 // start with a known node and enumerate the dependences to or from that node.
22 //===----------------------------------------------------------------------===//
24 #ifndef LLVM_ANALYSIS_DEPENDENCEGRAPH_H
25 #define LLVM_ANALYSIS_DEPENDENCEGRAPH_H
27 #include "Support/hash_map"
39 class DependenceGraph;
41 //----------------------------------------------------------------------------
42 /// enum DependenceType - The standard data dependence types
48 OutputDependence = 0x4,
49 ControlDependence = 0x8, // from a terminator to some other instr.
50 IncomingFlag = 0x10 // is this an incoming or outgoing dep?
53 //----------------------------------------------------------------------------
54 /// Dependence Class - A representation of a simple (non-loop-related)
58 DepGraphNode* toOrFromNode;
59 unsigned char depType;
62 Dependence(DepGraphNode* toOrFromN, DependenceType type, bool isIncoming)
63 : toOrFromNode(toOrFromN),
64 depType(type | (isIncoming? IncomingFlag : 0x0)) { }
66 Dependence(const Dependence& D) : toOrFromNode(D.toOrFromNode),
67 depType(D.depType) { }
69 bool operator==(const Dependence& D) const {
70 return toOrFromNode == D.toOrFromNode && depType == D.depType;
73 /// Get information about the type of dependence.
75 unsigned getDepType() const {
79 /// Get source or sink depending on what type of node this is!
81 DepGraphNode* getSrc() {
82 assert(depType & IncomingFlag); return toOrFromNode;
84 const DepGraphNode* getSrc() const {
85 assert(depType & IncomingFlag); return toOrFromNode;
88 DepGraphNode* getSink() {
89 assert(! (depType & IncomingFlag)); return toOrFromNode;
91 const DepGraphNode* getSink() const {
92 assert(! (depType & IncomingFlag)); return toOrFromNode;
95 /// Debugging support methods
97 void print(std::ostream &O) const;
99 // Default constructor: Do not use directly except for graph builder code
101 Dependence() : toOrFromNode(NULL), depType(NoDependence) { }
104 #ifdef SUPPORTING_LOOP_DEPENDENCES
105 struct LoopDependence: public Dependence {
106 DependenceDirection dir;
109 LoopInfo* enclosingLoop;
114 //----------------------------------------------------------------------------
115 /// DepGraphNode Class - A representation of a single node in a dependence
116 /// graph, corresponding to a single instruction.
120 std::vector<Dependence> inDeps;
121 std::vector<Dependence> outDeps;
122 friend class DependenceGraph;
124 typedef std::vector<Dependence>:: iterator iterator;
125 typedef std::vector<Dependence>::const_iterator const_iterator;
127 iterator inDepBegin() { return inDeps.begin(); }
128 const_iterator inDepBegin() const { return inDeps.begin(); }
129 iterator inDepEnd() { return inDeps.end(); }
130 const_iterator inDepEnd() const { return inDeps.end(); }
132 iterator outDepBegin() { return outDeps.begin(); }
133 const_iterator outDepBegin() const { return outDeps.begin(); }
134 iterator outDepEnd() { return outDeps.end(); }
135 const_iterator outDepEnd() const { return outDeps.end(); }
138 DepGraphNode(Instruction& I) : instr(&I) { }
140 Instruction& getInstr() { return *instr; }
141 const Instruction& getInstr() const { return *instr; }
143 /// Debugging support methods
145 void print(std::ostream &O) const;
149 //----------------------------------------------------------------------------
150 /// DependenceGraph Class - A representation of a dependence graph for a
151 /// procedure. The primary query operation here is to look up a DepGraphNode for
152 /// a particular instruction, and then use the in/out dependence iterators
155 class DependenceGraph {
156 DependenceGraph(const DependenceGraph&); // DO NOT IMPLEMENT
157 void operator=(const DependenceGraph&); // DO NOT IMPLEMENT
159 typedef hash_map<Instruction*, DepGraphNode*> DepNodeMapType;
160 typedef DepNodeMapType:: iterator map_iterator;
161 typedef DepNodeMapType::const_iterator const_map_iterator;
163 DepNodeMapType depNodeMap;
165 inline DepGraphNode* getNodeInternal(Instruction& inst,
166 bool createIfMissing = false) {
167 map_iterator I = depNodeMap.find(&inst);
168 if (I == depNodeMap.end())
169 return (!createIfMissing)? NULL :
171 std::make_pair(&inst, new DepGraphNode(inst))).first->second;
177 typedef std::vector<Dependence>:: iterator iterator;
178 typedef std::vector<Dependence>::const_iterator const_iterator;
181 DependenceGraph() { }
184 /// Get the graph node for an instruction. There will be one if and
185 /// only if there are any dependences incident on this instruction.
186 /// If there is none, these methods will return NULL.
188 DepGraphNode* getNode(Instruction& inst, bool createIfMissing = false) {
189 return getNodeInternal(inst, createIfMissing);
191 const DepGraphNode* getNode(const Instruction& inst) const {
192 return const_cast<DependenceGraph*>(this)
193 ->getNodeInternal(const_cast<Instruction&>(inst));
196 iterator inDepBegin(DepGraphNode& T) {
197 return T.inDeps.begin();
199 const_iterator inDepBegin (const DepGraphNode& T) const {
200 return T.inDeps.begin();
203 iterator inDepEnd(DepGraphNode& T) {
204 return T.inDeps.end();
206 const_iterator inDepEnd(const DepGraphNode& T) const {
207 return T.inDeps.end();
210 iterator outDepBegin(DepGraphNode& F) {
211 return F.outDeps.begin();
213 const_iterator outDepBegin(const DepGraphNode& F) const {
214 return F.outDeps.begin();
217 iterator outDepEnd(DepGraphNode& F) {
218 return F.outDeps.end();
220 const_iterator outDepEnd(const DepGraphNode& F) const {
221 return F.outDeps.end();
224 /// Debugging support methods
226 void print(const Function& func, std::ostream &O) const;
229 /// AddSimpleDependence - adding and modifying the dependence graph.
230 /// These should to be used only by dependence analysis implementations.
232 void AddSimpleDependence(Instruction& fromI, Instruction& toI,
233 DependenceType depType) {
234 DepGraphNode* fromNode = getNodeInternal(fromI, /*create*/ true);
235 DepGraphNode* toNode = getNodeInternal(toI, /*create*/ true);
236 fromNode->outDeps.push_back(Dependence(toNode, depType, false));
237 toNode-> inDeps. push_back(Dependence(fromNode, depType, true));
240 #ifdef SUPPORTING_LOOP_DEPENDENCES
241 // This interface is a placeholder to show what information is needed.
242 // It will probably change when it starts being used.
243 void AddLoopDependence(Instruction& fromI,
245 DependenceType depType,
246 DependenceDirection dir,
249 LoopInfo* enclosingLoop);
250 #endif // SUPPORTING_LOOP_DEPENDENCES
253 } // End llvm namespace