1 //===- PgmDependenceGraph.cpp - Enumerate 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.
26 //===----------------------------------------------------------------------===//
28 #include "llvm/Analysis/PgmDependenceGraph.h"
29 #include "llvm/Analysis/MemoryDepAnalysis.h"
30 #include "llvm/Analysis/PostDominators.h"
31 #include "llvm/Function.h"
34 //----------------------------------------------------------------------------
36 //----------------------------------------------------------------------------
38 const DepIterState::IterStateFlags DepIterState::NoFlag = 0x0;
39 const DepIterState::IterStateFlags DepIterState::MemDone = 0x1;
40 const DepIterState::IterStateFlags DepIterState::SSADone = 0x2;
41 const DepIterState::IterStateFlags DepIterState::AllDone = 0x4;
42 const DepIterState::IterStateFlags DepIterState::FirstTimeFlag= 0x8;
44 // Find the first memory dependence for the current Mem In/Out iterators.
45 // Find the first memory dependence for the current Mem In/Out iterators.
46 // Sets dep to that dependence and returns true if one is found.
48 bool DepIterState::SetFirstMemoryDep()
50 if (! (depFlags & MemoryDeps))
53 bool doIncomingDeps = dep.getDepType() & IncomingFlag;
55 if (( doIncomingDeps && memDepIter == memDepGraph->inDepEnd( *depNode)) ||
56 (!doIncomingDeps && memDepIter == memDepGraph->outDepEnd(*depNode)))
62 dep = *memDepIter; // simple copy from dependence in memory DepGraph
68 // Find the first valid data dependence for the current SSA In/Out iterators.
69 // A valid data dependence is one that is to/from an Instruction.
70 // E.g., an SSA edge from a formal parameter is not a valid dependence.
71 // Sets dep to that dependence and returns true if a valid one is found.
72 // Returns false and leaves dep unchanged otherwise.
74 bool DepIterState::SetFirstSSADep()
76 if (! (depFlags & SSADeps))
79 bool doIncomingDeps = dep.getDepType() & IncomingFlag;
80 Instruction* firstTarget = NULL;
82 // Increment the In or Out iterator till it runs out or we find a valid dep
84 for (Instruction::op_iterator E = depNode->getInstr().op_end();
86 (firstTarget = dyn_cast<Instruction>(ssaInEdgeIter))== NULL; )
89 for (Value::use_iterator E = depNode->getInstr().use_end();
90 ssaOutEdgeIter != E &&
91 (firstTarget = dyn_cast<Instruction>(*ssaOutEdgeIter)) == NULL; )
94 // If the iterator ran out before we found a valid dep, there isn't one.
101 // Create a simple dependence object to represent this SSA dependence.
102 dep = Dependence(memDepGraph->getNode(*firstTarget, /*create*/ true),
103 TrueDependence, doIncomingDeps);
109 DepIterState::DepIterState(DependenceGraph* _memDepGraph,
112 PDGIteratorFlags whichDeps)
113 : memDepGraph(_memDepGraph),
117 depNode = memDepGraph->getNode(I, /*create*/ true);
121 if (whichDeps & MemoryDeps) memDepIter= memDepGraph->inDepBegin(*depNode);
122 if (whichDeps & SSADeps) ssaInEdgeIter = I.op_begin();
123 /* Initialize control dependence iterator here. */
127 if (whichDeps & MemoryDeps) memDepIter=memDepGraph->outDepBegin(*depNode);
128 if (whichDeps & SSADeps) ssaOutEdgeIter = I.use_begin();
129 /* Initialize control dependence iterator here. */
132 // Set the dependence to the first of a memory dep or an SSA dep
133 // and set the done flag if either is found. Otherwise, set the
134 // init flag to indicate that the iterators have just been initialized.
136 if (!SetFirstMemoryDep() && !SetFirstSSADep())
137 iterFlags |= AllDone;
139 iterFlags |= FirstTimeFlag;
143 // Helper function for ++ operator that bumps iterator by 1 (to next
144 // dependence) and resets the dep field to represent the new dependence.
146 void DepIterState::Next()
148 // firstMemDone and firstSsaDone are used to indicate when the memory or
149 // SSA iterators just ran out, or when this is the very first increment.
150 // In either case, the next iterator (if any) should not be incremented.
152 bool firstMemDone = iterFlags & FirstTimeFlag;
153 bool firstSsaDone = iterFlags & FirstTimeFlag;
154 bool doIncomingDeps = dep.getDepType() & IncomingFlag;
156 if (depFlags & MemoryDeps && ! (iterFlags & MemDone))
158 iterFlags &= ~FirstTimeFlag; // clear "firstTime" flag
160 if (SetFirstMemoryDep())
162 firstMemDone = true; // flags that we _just_ rolled over
165 if (depFlags & SSADeps && ! (iterFlags & SSADone))
167 // Don't increment the SSA iterator if we either just rolled over from
168 // the memory dep iterator, or if the SSA iterator is already done.
169 iterFlags &= ~FirstTimeFlag; // clear "firstTime" flag
171 if (doIncomingDeps) ++ssaInEdgeIter;
172 else ++ssaOutEdgeIter;
173 if (SetFirstSSADep())
175 firstSsaDone = true; // flags if we just rolled over
178 if (depFlags & ControlDeps != 0)
180 assert(0 && "Cannot handle control deps");
181 // iterFlags &= ~FirstTimeFlag; // clear "firstTime" flag
184 // This iterator is now complete.
185 iterFlags |= AllDone;
189 //----------------------------------------------------------------------------
190 // class PgmDependenceGraph
191 //----------------------------------------------------------------------------
194 // MakeIterator -- Create and initialize an iterator as specified.
196 PDGIterator PgmDependenceGraph::MakeIterator(Instruction& I,
198 PDGIteratorFlags whichDeps)
200 assert(memDepGraph && "Function not initialized!");
201 return PDGIterator(new DepIterState(memDepGraph, I, incomingDeps, whichDeps));
205 void PgmDependenceGraph::printOutgoingSSADeps(Instruction& I,
208 iterator SI = this->outDepBegin(I, SSADeps);
209 iterator SE = this->outDepEnd(I, SSADeps);
213 O << "\n Outgoing SSA dependences:\n";
214 for ( ; SI != SE; ++SI)
218 O << " to instruction:";
219 O << SI->getSink()->getInstr();
224 void PgmDependenceGraph::print(std::ostream &O) const
226 MemoryDepAnalysis& graphSet = getAnalysis<MemoryDepAnalysis>();
229 for (hash_map<Function*, DependenceGraph*>::iterator
230 I = graphSet.funcMap.begin(), E = graphSet.funcMap.end();
233 Function* func = I->first;
234 DependenceGraph* depGraph = I->second;
235 const_cast<PgmDependenceGraph*>(this)->runOnFunction(*func);
237 O << "DEPENDENCE GRAPH FOR FUNCTION " << func->getName() << ":\n";
238 for (Function::iterator BB=func->begin(), FE=func->end(); BB != FE; ++BB)
239 for (BasicBlock::iterator II=BB->begin(), IE=BB->end(); II !=IE; ++II)
241 DepGraphNode* dgNode = depGraph->getNode(*II, /*create*/ true);
243 const_cast<PgmDependenceGraph*>(this)->printOutgoingSSADeps(*II, O);
245 } // END TEMPORARY LOOP
249 void PgmDependenceGraph::dump() const
251 this->print(std::cerr);
254 static RegisterAnalysis<PgmDependenceGraph>
255 Z("pgmdep", "Enumerate Program Dependence Graph (data and control)");