1 //===- PgmDependenceGraph.h - Enumerate the PDG 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 // The Program Dependence Graph (PDG) for a single function represents all
11 // data and control dependences for the function. This file provides an
12 // iterator to enumerate all these dependences. In particular, it enumerates:
14 // -- Data dependences on memory locations, computed using the
15 // MemoryDepAnalysis pass;
16 // -- Data dependences on SSA registers, directly from Def-Use edges of Values;
17 // -- Control dependences, computed using postdominance frontiers
18 // (NOT YET IMPLEMENTED).
20 // Note that this file does not create an explicit dependence graph --
21 // it only provides an iterator to traverse the PDG conceptually.
22 // The MemoryDepAnalysis does build an explicit graph, which is used internally
23 // here. That graph could be augmented with the other dependences above if
24 // desired, but for most uses there will be little need to do that.
28 // enum PDGIteratorFlags -- Specify which dependences to enumerate.
30 // class PDGIterator -- The PDG iterator. This is essentially like a
31 // pointer to class Dependence, but doesn't explicitly
32 // construct a Dependence object for each dependence.
34 // class PgmDependenceGraph -- Interface to obtain PDGIterators for each
37 //===----------------------------------------------------------------------===//
39 #ifndef LLVM_ANALYSIS_PGMDEPENDENCEGRAPH_H
40 #define LLVM_ANALYSIS_PGMDEPENDENCEGRAPH_H
42 #include "MemoryDepAnalysis.h"
43 /* #include "llvm/Analysis/PostDominators.h" -- see below */
44 #include "llvm/Instruction.h"
45 #include "llvm/Pass.h"
46 #include "Support/iterator"
51 class DependenceGraph;
52 class PgmDependenceGraph;
54 //---------------------------------------------------------------------------
55 /// enum PDGIteratorFlags - specify which dependences incident on a statement
56 /// are to be enumerated: Memory deps, SSA deps, Control deps, or any
57 /// combination thereof.
59 enum PDGIteratorFlags {
60 MemoryDeps = 0x1, // load/store/call deps
61 SSADeps = 0x2, // SSA deps (true)
62 ControlDeps = /* 0x4*/ 0x0, // control dependences
63 AllDataDeps = MemoryDeps | SSADeps, // shorthand for data deps
64 AllDeps = MemoryDeps | SSADeps | ControlDeps // shorthand for all three
67 //---------------------------------------------------------------------------
68 /// struct DepIterState - an internal implementation detail.
69 /// It are exposed here only to give inlinable access to field dep,
70 /// which is the representation for the current dependence pointed to by
71 /// a PgmDependenceGraph::iterator.
75 typedef char IterStateFlags;
76 static const IterStateFlags NoFlag, MemDone, SSADone, AllDone, FirstTimeFlag;
79 DepGraphNode* depNode; // the node being enumerated
80 DependenceGraph::iterator memDepIter; // pointer to current memory dep
81 Instruction::op_iterator ssaInEdgeIter; // pointer to current SSA in-dep
82 Value::use_iterator ssaOutEdgeIter; // pointer to current SSA out-dep
83 DependenceGraph* memDepGraph; // the core dependence graph
84 Dependence dep; // the "current" dependence
85 PDGIteratorFlags depFlags:8; // which deps are we enumerating?
86 IterStateFlags iterFlags:8; // marking where the iter stands
88 DepIterState(DependenceGraph* _memDepGraph,
91 PDGIteratorFlags whichDeps);
93 bool operator==(const DepIterState& S) {
94 assert(memDepGraph == S.memDepGraph &&
95 "Incompatible iterators! This is a probable sign of something BAD.");
96 return (iterFlags == S.iterFlags &&
97 dep == S.dep && depFlags == S.depFlags && depNode == S.depNode &&
98 memDepIter == S.memDepIter && ssaInEdgeIter == S.ssaInEdgeIter &&
99 ssaOutEdgeIter == S.ssaOutEdgeIter);
102 // Is the iteration completely done?
104 bool done() const { return iterFlags & AllDone; }
106 /// Next - Bump this iterator logically by 1 (to next dependence) and reset
107 /// the dep field to represent the new dependence if there is one.
108 /// Set done = true otherwise.
112 /// SetFirstMemoryDep - Find the first memory dependence for the current Mem
113 /// In/Out iterators. Sets dep to that dependence and returns true if one is
114 /// found. Returns false and leaves dep unchanged otherwise.
116 bool SetFirstMemoryDep();
118 /// SetFirstSSADep - Find the next valid data dependence for the current SSA
119 /// In/Out iterators. A valid data dependence is one that is to/from an
120 /// Instruction. E.g., an SSA edge from a formal parameter is not a valid
121 /// dependence. Sets dep to that dependence and returns true if a valid one is
122 /// found. Returns false and leaves dep unchanged otherwise.
124 bool SetFirstSSADep();
128 //---------------------------------------------------------------------------
129 /// PDGIterator Class - represents a pointer to a single dependence in the
130 /// program dependence graph. It is essentially like a pointer to an object of
131 /// class Dependence but it is much more efficient to retrieve information about
132 /// the dependence directly rather than constructing the equivalent Dependence
133 /// object (since that object is normally not constructed for SSA def-use
136 class PDGIterator: public forward_iterator<Dependence, ptrdiff_t> {
137 DepIterState* istate;
140 /*copy*/ PDGIterator (const PDGIterator& I); // do not implement!
141 PDGIterator& operator= (const PDGIterator& I); // do not implement!
143 /*copy*/ PDGIterator (PDGIterator& I) : istate(I.istate) {
144 I.istate = NULL; // ensure this is not deleted twice.
148 friend class PgmDependenceGraph;
151 typedef PDGIterator _Self;
153 PDGIterator(DepIterState* _istate) : istate(_istate) {}
154 ~PDGIterator() { delete istate; }
156 PDGIterator(const PDGIterator& I) :istate(new DepIterState(*I.istate)) {}
158 PDGIterator& operator=(const PDGIterator& I) {
159 if (istate) delete istate;
160 istate = new DepIterState(*I.istate);
164 /// fini - check if the iteration is complete
166 bool fini() const { return !istate || istate->done(); }
168 // Retrieve the underlying Dependence. Returns NULL if fini().
170 Dependence* operator*() const { return fini() ? NULL : &istate->dep; }
171 Dependence* operator->() const { assert(!fini()); return &istate->dep; }
173 // Increment the iterator
175 _Self& operator++() { if (!fini()) istate->Next(); return *this;}
176 _Self& operator++(int); // do not implement!
178 // Equality comparison: a "null" state should compare equal to done
179 // This is efficient for comparing with "end" or with itself, but could
180 // be quite inefficient for other cases.
182 bool operator==(const PDGIterator& I) const {
183 if (I.istate == NULL) // most common case: iter == end()
184 return (istate == NULL || istate->done());
186 return (I.istate == NULL || I.istate->done());
187 return (*istate == *I.istate);
189 bool operator!=(const PDGIterator& I) const {
190 return ! (*this == I);
195 ///---------------------------------------------------------------------------
196 /// class PgmDependenceGraph:
198 /// This pass enumerates dependences incident on each instruction in a function.
199 /// It can be made a FunctionPass once a Pass (such as Parallelize) is
200 /// allowed to use a FunctionPass such as this one.
201 ///---------------------------------------------------------------------------
203 class PgmDependenceGraph: public Pass {
205 /// Information about the function being analyzed.
207 DependenceGraph* memDepGraph;
209 // print helper function.
210 void printOutgoingSSADeps(Instruction& I, std::ostream &O);
212 /// MakeIterator - creates and initializes an iterator as specified.
214 PDGIterator MakeIterator(Instruction& I,
216 PDGIteratorFlags whichDeps);
218 /// MakeIterator - creates a null iterator representing end-of-iteration.
220 PDGIterator MakeIterator() { return PDGIterator(NULL); }
222 friend class PDGIterator;
223 friend class DepIterState;
226 typedef PDGIterator iterator;
227 /* typedef PDGIterator<const Dependence> const iterator; */
230 PgmDependenceGraph() : memDepGraph(NULL) {}
231 ~PgmDependenceGraph() {}
233 /// Iterators to enumerate the program dependence graph for a function.
234 /// Note that this does not provide "end" iterators to check for completion.
235 /// Instead, just use iterator::fini() or iterator::operator*() == NULL
237 iterator inDepBegin(Instruction& I, PDGIteratorFlags whichDeps = AllDeps) {
238 return MakeIterator(I, /*inDeps*/ true, whichDeps);
240 iterator inDepEnd (Instruction& I, PDGIteratorFlags whichDeps = AllDeps) {
241 return MakeIterator();
243 iterator outDepBegin(Instruction& I, PDGIteratorFlags whichDeps = AllDeps) {
244 return MakeIterator(I, /*inDeps*/ false, whichDeps);
246 iterator outDepEnd (Instruction& I, PDGIteratorFlags whichDeps = AllDeps) {
247 return MakeIterator();
250 //------------------------------------------------------------------------
251 /// TEMPORARY FUNCTIONS TO MAKE THIS A MODULE PASS ---
252 /// These functions will go away once this class becomes a FunctionPass.
254 /// Driver function to compute dependence graphs for every function.
256 bool run(Module& M) { return true; }
258 /// getGraph() -- Retrieve the pgm dependence graph for a function.
259 /// This is temporary and will go away once this is a FunctionPass.
260 /// At that point, this class itself will be the PgmDependenceGraph you want.
262 PgmDependenceGraph& getGraph(Function& F) {
268 void Visiting(Function& F) {
269 memDepGraph = &getAnalysis<MemoryDepAnalysis>().getGraph(F);
272 ///----END TEMPORARY FUNCTIONS---------------------------------------------
275 /// This initializes the program dependence graph iterator for a function.
277 bool runOnFunction(Function& func) {
282 /// getAnalysisUsage - This does not modify anything.
283 /// It uses the Memory Dependence Analysis pass.
284 /// It needs to use the PostDominanceFrontier pass, but cannot because
285 /// that is a FunctionPass. This means control dependence are not emumerated.
287 void getAnalysisUsage(AnalysisUsage &AU) const {
288 AU.setPreservesAll();
289 AU.addRequired<MemoryDepAnalysis>();
290 /* AU.addRequired<PostDominanceFrontier>(); */
293 /// Debugging support methods
295 void print(std::ostream &O) const;
299 } // End llvm namespace