1 //===- CompleteBottomUp.cpp - Complete Bottom-Up Data Structure Graphs ----===//
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 is the exact same as the bottom-up graphs, but we use take a completed
11 // call graph and inline all indirect callees into their callers graphs, making
12 // the result more useful for things like pool allocation.
14 //===----------------------------------------------------------------------===//
16 #include "llvm/Analysis/DataStructure/DataStructure.h"
17 #include "llvm/Module.h"
18 #include "llvm/Analysis/DataStructure/DSGraph.h"
19 #include "llvm/Support/Debug.h"
20 #include "llvm/ADT/SCCIterator.h"
21 #include "llvm/ADT/Statistic.h"
22 #include "llvm/ADT/STLExtras.h"
26 RegisterAnalysis<CompleteBUDataStructures>
27 X("cbudatastructure", "'Complete' Bottom-up Data Structure Analysis");
28 Statistic<> NumCBUInlines("cbudatastructures", "Number of graphs inlined");
32 // run - Calculate the bottom up data structure graphs for each function in the
35 bool CompleteBUDataStructures::run(Module &M) {
36 BUDataStructures &BU = getAnalysis<BUDataStructures>();
37 GlobalsGraph = new DSGraph(BU.getGlobalsGraph());
38 GlobalsGraph->setPrintAuxCalls();
40 #if 1 // REMOVE ME EVENTUALLY
41 // FIXME: TEMPORARY (remove once finalization of indirect call sites in the
42 // globals graph has been implemented in the BU pass)
43 TDDataStructures &TD = getAnalysis<TDDataStructures>();
45 ActualCallees.clear();
47 // The call graph extractable from the TD pass is _much more complete_ and
48 // trustable than that generated by the BU pass so far. Until this is fixed,
49 // we hack it like this:
50 for (Module::iterator MI = M.begin(), ME = M.end(); MI != ME; ++MI) {
51 if (MI->isExternal()) continue;
52 const std::vector<DSCallSite> &CSs = TD.getDSGraph(*MI).getFunctionCalls();
54 for (unsigned CSi = 0, e = CSs.size(); CSi != e; ++CSi) {
55 Instruction *TheCall = CSs[CSi].getCallSite().getInstruction();
57 if (CSs[CSi].isIndirectCall()) { // indirect call: insert all callees
58 const std::vector<GlobalValue*> &Callees =
59 CSs[CSi].getCalleeNode()->getGlobals();
60 for (unsigned i = 0, e = Callees.size(); i != e; ++i)
61 if (Function *F = dyn_cast<Function>(Callees[i]))
62 ActualCallees.insert(std::make_pair(TheCall, F));
63 } else { // direct call: insert the single callee directly
64 ActualCallees.insert(std::make_pair(TheCall,
65 CSs[CSi].getCalleeFunc()));
70 // Our call graph is the same as the BU data structures call graph
71 ActualCallees = BU.getActualCallees();
74 std::vector<DSGraph*> Stack;
75 hash_map<DSGraph*, unsigned> ValMap;
78 if (Function *Main = M.getMainFunction()) {
79 if (!Main->isExternal())
80 calculateSCCGraphs(getOrCreateGraph(*Main), Stack, NextID, ValMap);
82 std::cerr << "CBU-DSA: No 'main' function found!\n";
85 for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
86 if (!I->isExternal() && !DSInfo.count(I))
87 calculateSCCGraphs(getOrCreateGraph(*I), Stack, NextID, ValMap);
89 GlobalsGraph->removeTriviallyDeadNodes();
93 DSGraph &CompleteBUDataStructures::getOrCreateGraph(Function &F) {
94 // Has the graph already been created?
95 DSGraph *&Graph = DSInfo[&F];
96 if (Graph) return *Graph;
98 // Copy the BU graph...
99 Graph = new DSGraph(getAnalysis<BUDataStructures>().getDSGraph(F));
100 Graph->setGlobalsGraph(GlobalsGraph);
101 Graph->setPrintAuxCalls();
103 // Make sure to update the DSInfo map for all of the functions currently in
105 for (DSGraph::ReturnNodesTy::iterator I = Graph->getReturnNodes().begin();
106 I != Graph->getReturnNodes().end(); ++I)
107 DSInfo[I->first] = Graph;
114 unsigned CompleteBUDataStructures::calculateSCCGraphs(DSGraph &FG,
115 std::vector<DSGraph*> &Stack,
117 hash_map<DSGraph*, unsigned> &ValMap) {
118 assert(!ValMap.count(&FG) && "Shouldn't revisit functions!");
119 unsigned Min = NextID++, MyID = Min;
121 Stack.push_back(&FG);
123 // The edges out of the current node are the call site targets...
124 for (unsigned i = 0, e = FG.getFunctionCalls().size(); i != e; ++i) {
125 Instruction *Call = FG.getFunctionCalls()[i].getCallSite().getInstruction();
127 // Loop over all of the actually called functions...
128 ActualCalleesTy::iterator I, E;
129 for (tie(I, E) = ActualCallees.equal_range(Call); I != E; ++I)
130 if (!I->second->isExternal()) {
131 DSGraph &Callee = getOrCreateGraph(*I->second);
133 // Have we visited the destination function yet?
134 hash_map<DSGraph*, unsigned>::iterator It = ValMap.find(&Callee);
135 if (It == ValMap.end()) // No, visit it now.
136 M = calculateSCCGraphs(Callee, Stack, NextID, ValMap);
137 else // Yes, get it's number.
139 if (M < Min) Min = M;
143 assert(ValMap[&FG] == MyID && "SCC construction assumption wrong!");
145 return Min; // This is part of a larger SCC!
147 // If this is a new SCC, process it now.
148 bool IsMultiNodeSCC = false;
149 while (Stack.back() != &FG) {
150 DSGraph *NG = Stack.back();
153 DSGraph::NodeMapTy NodeMap;
154 FG.cloneInto(*NG, FG.getScalarMap(), FG.getReturnNodes(), NodeMap);
156 // Update the DSInfo map and delete the old graph...
157 for (DSGraph::ReturnNodesTy::iterator I = NG->getReturnNodes().begin();
158 I != NG->getReturnNodes().end(); ++I)
159 DSInfo[I->first] = &FG;
163 IsMultiNodeSCC = true;
166 // Clean up the graph before we start inlining a bunch again...
168 FG.removeTriviallyDeadNodes();
177 /// processGraph - Process the BU graphs for the program in bottom-up order on
178 /// the SCC of the __ACTUAL__ call graph. This builds "complete" BU graphs.
179 void CompleteBUDataStructures::processGraph(DSGraph &G) {
180 hash_set<Instruction*> calls;
182 // The edges out of the current node are the call site targets...
183 for (unsigned i = 0, e = G.getFunctionCalls().size(); i != e; ++i) {
184 const DSCallSite &CS = G.getFunctionCalls()[i];
185 Instruction *TheCall = CS.getCallSite().getInstruction();
187 assert(calls.insert(TheCall).second &&
188 "Call instruction occurs multiple times in graph??");
191 // Loop over all of the potentially called functions...
192 // Inline direct calls as well as indirect calls because the direct
193 // callee may have indirect callees and so may have changed.
195 ActualCalleesTy::iterator I, E;
196 tie(I, E) = ActualCallees.equal_range(TheCall);
197 unsigned TNum = 0, Num = std::distance(I, E);
198 for (; I != E; ++I, ++TNum) {
199 Function *CalleeFunc = I->second;
200 if (!CalleeFunc->isExternal()) {
201 // Merge the callee's graph into this graph. This works for normal
202 // calls or for self recursion within an SCC.
203 DSGraph &GI = getOrCreateGraph(*CalleeFunc);
205 G.mergeInGraph(CS, *CalleeFunc, GI, DSGraph::KeepModRefBits |
206 DSGraph::StripAllocaBit | DSGraph::DontCloneCallNodes |
207 DSGraph::DontCloneAuxCallNodes);
208 DEBUG(std::cerr << " Inlining graph [" << i << "/" << e-1
209 << ":" << TNum << "/" << Num-1 << "] for "
210 << CalleeFunc->getName() << "["
211 << GI.getGraphSize() << "+" << GI.getAuxFunctionCalls().size()
212 << "] into '" /*<< G.getFunctionNames()*/ << "' ["
213 << G.getGraphSize() << "+" << G.getAuxFunctionCalls().size()
219 // Recompute the Incomplete markers
220 assert(G.getInlinedGlobals().empty());
221 G.maskIncompleteMarkers();
222 G.markIncompleteNodes(DSGraph::MarkFormalArgs);
224 // Delete dead nodes. Treat globals that are unreachable but that can
225 // reach live nodes as live.
226 G.removeDeadNodes(DSGraph::KeepUnreachableGlobals);