1 //===- TopDownClosure.cpp - Compute the top-down interprocedure closure ---===//
3 // This file implements the TDDataStructures class, which represents the
4 // Top-down Interprocedural closure of the data structure graph over the
5 // program. This is useful (but not strictly necessary?) for applications
6 // like pointer analysis.
8 //===----------------------------------------------------------------------===//
10 #include "llvm/Analysis/DataStructure.h"
11 #include "llvm/Analysis/DSGraph.h"
12 #include "llvm/Module.h"
13 #include "llvm/DerivedTypes.h"
14 #include "Support/Statistic.h"
17 RegisterAnalysis<TDDataStructures> // Register the pass
18 Y("tddatastructure", "Top-down Data Structure Analysis Closure");
21 // run - Calculate the top down data structure graphs for each function in the
24 bool TDDataStructures::run(Module &M) {
25 BUDataStructures &BU = getAnalysis<BUDataStructures>();
26 GlobalsGraph = new DSGraph();
28 // Calculate top-down from main...
29 if (Function *F = M.getMainFunction())
32 // Next calculate the graphs for each function unreachable function...
33 for (Module::reverse_iterator I = M.rbegin(), E = M.rend(); I != E; ++I)
37 GraphDone.clear(); // Free temporary memory...
41 // releaseMemory - If the pass pipeline is done with this pass, we can release
42 // our memory... here...
44 // FIXME: This should be releaseMemory and will work fine, except that LoadVN
45 // has no way to extend the lifetime of the pass, which screws up ds-aa.
47 void TDDataStructures::releaseMyMemory() {
48 for (hash_map<const Function*, DSGraph*>::iterator I = DSInfo.begin(),
49 E = DSInfo.end(); I != E; ++I)
52 // Empty map so next time memory is released, data structures are not
59 /// ResolveCallSite - This method is used to link the actual arguments together
60 /// with the formal arguments for a function call in the top-down closure. This
61 /// method assumes that the call site arguments have been mapped into nodes
62 /// local to the specified graph.
64 void TDDataStructures::ResolveCallSite(DSGraph &Graph,
65 const DSCallSite &CallSite) {
66 // Resolve all of the function formal arguments...
67 Function &F = Graph.getFunction();
68 Function::aiterator AI = F.abegin();
70 for (unsigned i = 0, e = CallSite.getNumPtrArgs(); i != e; ++i, ++AI) {
71 // Advance the argument iterator to the first pointer argument...
72 while (!DS::isPointerType(AI->getType())) ++AI;
74 // TD ...Merge the formal arg scalar with the actual arg node
75 DSNodeHandle &NodeForFormal = Graph.getNodeForValue(AI);
76 assert(NodeForFormal.getNode() && "Pointer argument has no dest node!");
77 NodeForFormal.mergeWith(CallSite.getPtrArg(i));
80 // Merge returned node in the caller with the "return" node in callee
81 if (CallSite.getRetVal().getNode() && Graph.getRetNode().getNode())
82 Graph.getRetNode().mergeWith(CallSite.getRetVal());
85 DSGraph &TDDataStructures::getOrCreateDSGraph(Function &F) {
86 DSGraph *&G = DSInfo[&F];
87 if (G == 0) { // Not created yet? Clone BU graph...
88 G = new DSGraph(getAnalysis<BUDataStructures>().getDSGraph(F));
89 G->getAuxFunctionCalls().clear();
90 G->setPrintAuxCalls();
91 G->setGlobalsGraph(GlobalsGraph);
96 void TDDataStructures::calculateGraph(Function &F) {
97 // Make sure this graph has not already been calculated, and that we don't get
98 // into an infinite loop with mutually recursive functions.
100 if (GraphDone.count(&F)) return;
101 GraphDone.insert(&F);
103 // Get the current functions graph...
104 DSGraph &Graph = getOrCreateDSGraph(F);
106 const std::vector<DSCallSite> &CallSites = Graph.getFunctionCalls();
107 if (CallSites.empty()) {
108 DEBUG(std::cerr << " [TD] No callees for: " << F.getName() << "\n");
110 // Loop over all of the call sites, building a multi-map from Callees to
111 // DSCallSite*'s. With this map we can then loop over each callee, cloning
112 // this graph once into it, then resolving arguments.
114 std::multimap<Function*, const DSCallSite*> CalleeSites;
115 for (unsigned i = 0, e = CallSites.size(); i != e; ++i) {
116 const DSCallSite &CS = CallSites[i];
117 if (CS.isDirectCall()) {
118 if (!CS.getCalleeFunc()->isExternal()) // If it's not external
119 CalleeSites.insert(std::make_pair(CS.getCalleeFunc(), &CS));// Keep it
121 const std::vector<GlobalValue*> &Callees =
122 CS.getCalleeNode()->getGlobals();
124 // Loop over all of the functions that this call may invoke...
125 for (unsigned c = 0, e = Callees.size(); c != e; ++c)
126 if (Function *F = dyn_cast<Function>(Callees[c]))// If this is a fn...
127 if (!F->isExternal()) // If it's not extern
128 CalleeSites.insert(std::make_pair(F, &CS)); // Keep track of it!
132 // Now that we have information about all of the callees, propagate the
133 // current graph into the callees.
135 DEBUG(std::cerr << " [TD] Inlining '" << F.getName() << "' into "
136 << CalleeSites.size() << " callees.\n");
138 // Loop over all the callees...
139 for (std::multimap<Function*, const DSCallSite*>::iterator
140 I = CalleeSites.begin(), E = CalleeSites.end(); I != E; )
141 if (I->first == &F) { // Bottom-up pass takes care of self loops!
144 // For each callee...
145 Function *Callee = I->first;
146 DSGraph &CG = getOrCreateDSGraph(*Callee); // Get the callee's graph...
148 DEBUG(std::cerr << "\t [TD] Inlining into callee '" << Callee->getName()
151 // Clone our current graph into the callee...
152 hash_map<Value*, DSNodeHandle> OldValMap;
153 hash_map<const DSNode*, DSNodeHandle> OldNodeMap;
154 CG.cloneInto(Graph, OldValMap, OldNodeMap,
155 DSGraph::StripModRefBits |
156 DSGraph::KeepAllocaBit | DSGraph::DontCloneCallNodes);
157 OldValMap.clear(); // We don't care about the ValMap
159 // Loop over all of the invocation sites of the callee, resolving
160 // arguments to our graph. This loop may iterate multiple times if the
161 // current function calls this callee multiple times with different
164 for (; I != E && I->first == Callee; ++I) {
165 // Map call site into callee graph
166 DSCallSite NewCS(*I->second, OldNodeMap);
168 // Resolve the return values...
169 NewCS.getRetVal().mergeWith(CG.getRetNode());
171 // Resolve all of the arguments...
172 Function::aiterator AI = Callee->abegin();
173 for (unsigned i = 0, e = NewCS.getNumPtrArgs();
174 i != e && AI != Callee->aend(); ++i, ++AI) {
175 // Advance the argument iterator to the first pointer argument...
176 while (!DS::isPointerType(AI->getType())) {
179 if (AI == Callee->aend())
180 std::cerr << "Bad call to Func: " << Callee->getName() << "\n";
182 assert(AI != Callee->aend() &&
183 "# Args provided is not # Args required!");
186 // Add the link from the argument scalar to the provided value
187 DSNodeHandle &NH = CG.getNodeForValue(AI);
188 assert(NH.getNode() && "Pointer argument without scalarmap entry?");
189 NH.mergeWith(NewCS.getPtrArg(i));
193 // Done with the nodemap...
196 // Recompute the Incomplete markers and eliminate unreachable nodes.
197 CG.maskIncompleteMarkers();
198 CG.markIncompleteNodes(DSGraph::MarkFormalArgs);
199 CG.removeDeadNodes(DSGraph::RemoveUnreachableGlobals);
202 DEBUG(std::cerr << " [TD] Done inlining into callees for: " << F.getName()
203 << " [" << Graph.getGraphSize() << "+"
204 << Graph.getFunctionCalls().size() << "]\n");
206 // Loop over all the callees... making sure they are all resolved now...
207 Function *LastFunc = 0;
208 for (std::multimap<Function*, const DSCallSite*>::iterator
209 I = CalleeSites.begin(), E = CalleeSites.end(); I != E; ++I)
210 if (I->first != LastFunc) { // Only visit each callee once...
212 calculateGraph(*I->first);
216 // Recompute the Incomplete markers and eliminate unreachable nodes.
217 Graph.maskIncompleteMarkers();
218 // FIXME: Need to check if all callers have been found, or rather if a
219 // funcpointer escapes!
220 unsigned Flags = F.hasInternalLinkage() ?
221 DSGraph::IgnoreFormalArgs : DSGraph::MarkFormalArgs;
222 Graph.markIncompleteNodes(Flags | DSGraph::IgnoreGlobals);
223 Graph.removeDeadNodes(DSGraph::RemoveUnreachableGlobals);