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 #define DEBUG_TYPE "cbudatastructure"
17 #include "llvm/Analysis/DataStructure/DataStructure.h"
18 #include "llvm/Module.h"
19 #include "llvm/Analysis/DataStructure/DSGraph.h"
20 #include "llvm/Support/Debug.h"
21 #include "llvm/ADT/SCCIterator.h"
22 #include "llvm/ADT/Statistic.h"
23 #include "llvm/ADT/STLExtras.h"
28 RegisterPass<CompleteBUDataStructures>
29 X("cbudatastructure", "'Complete' Bottom-up Data Structure Analysis");
30 Statistic<> NumCBUInlines("cbudatastructures", "Number of graphs inlined");
34 // run - Calculate the bottom up data structure graphs for each function in the
37 bool CompleteBUDataStructures::runOnModule(Module &M) {
38 BUDataStructures &BU = getAnalysis<BUDataStructures>();
39 GlobalECs = BU.getGlobalECs();
40 GlobalsGraph = new DSGraph(BU.getGlobalsGraph(), GlobalECs);
41 GlobalsGraph->setPrintAuxCalls();
43 // Our call graph is the same as the BU data structures call graph
44 ActualCallees = BU.getActualCallees();
46 std::vector<DSGraph*> Stack;
47 hash_map<DSGraph*, unsigned> ValMap;
50 Function *MainFunc = M.getMainFunction();
52 if (!MainFunc->isExternal())
53 calculateSCCGraphs(getOrCreateGraph(*MainFunc), Stack, NextID, ValMap);
55 std::cerr << "CBU-DSA: No 'main' function found!\n";
58 for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
59 if (!I->isExternal() && !DSInfo.count(I)) {
62 std::cerr << "*** CBU: Function unreachable from main: "
63 << I->getName() << "\n";
65 calculateSCCGraphs(getOrCreateGraph(*I), Stack, NextID, ValMap);
68 GlobalsGraph->removeTriviallyDeadNodes();
71 // Merge the globals variables (not the calls) from the globals graph back
72 // into the main function's graph so that the main function contains all of
73 // the information about global pools and GV usage in the program.
74 if (MainFunc && !MainFunc->isExternal()) {
75 DSGraph &MainGraph = getOrCreateGraph(*MainFunc);
76 const DSGraph &GG = *MainGraph.getGlobalsGraph();
77 ReachabilityCloner RC(MainGraph, GG,
78 DSGraph::DontCloneCallNodes |
79 DSGraph::DontCloneAuxCallNodes);
81 // Clone the global nodes into this graph.
82 for (DSScalarMap::global_iterator I = GG.getScalarMap().global_begin(),
83 E = GG.getScalarMap().global_end(); I != E; ++I)
84 if (isa<GlobalVariable>(*I))
85 RC.getClonedNH(GG.getNodeForValue(*I));
87 MainGraph.maskIncompleteMarkers();
88 MainGraph.markIncompleteNodes(DSGraph::MarkFormalArgs |
89 DSGraph::IgnoreGlobals);
95 DSGraph &CompleteBUDataStructures::getOrCreateGraph(Function &F) {
96 // Has the graph already been created?
97 DSGraph *&Graph = DSInfo[&F];
98 if (Graph) return *Graph;
100 // Copy the BU graph...
101 Graph = new DSGraph(getAnalysis<BUDataStructures>().getDSGraph(F), GlobalECs);
102 Graph->setGlobalsGraph(GlobalsGraph);
103 Graph->setPrintAuxCalls();
105 // Make sure to update the DSInfo map for all of the functions currently in
107 for (DSGraph::retnodes_iterator I = Graph->retnodes_begin();
108 I != Graph->retnodes_end(); ++I)
109 DSInfo[I->first] = Graph;
116 unsigned CompleteBUDataStructures::calculateSCCGraphs(DSGraph &FG,
117 std::vector<DSGraph*> &Stack,
119 hash_map<DSGraph*, unsigned> &ValMap) {
120 assert(!ValMap.count(&FG) && "Shouldn't revisit functions!");
121 unsigned Min = NextID++, MyID = Min;
123 Stack.push_back(&FG);
125 // The edges out of the current node are the call site targets...
126 for (DSGraph::fc_iterator CI = FG.fc_begin(), CE = FG.fc_end();
128 Instruction *Call = CI->getCallSite().getInstruction();
130 // Loop over all of the actually called functions...
131 callee_iterator I = callee_begin(Call), E = callee_end(Call);
132 for (; I != E && I->first == Call; ++I) {
133 assert(I->first == Call && "Bad callee construction!");
134 if (!I->second->isExternal()) {
135 DSGraph &Callee = getOrCreateGraph(*I->second);
137 // Have we visited the destination function yet?
138 hash_map<DSGraph*, unsigned>::iterator It = ValMap.find(&Callee);
139 if (It == ValMap.end()) // No, visit it now.
140 M = calculateSCCGraphs(Callee, Stack, NextID, ValMap);
141 else // Yes, get it's number.
143 if (M < Min) Min = M;
148 assert(ValMap[&FG] == MyID && "SCC construction assumption wrong!");
150 return Min; // This is part of a larger SCC!
152 // If this is a new SCC, process it now.
153 bool IsMultiNodeSCC = false;
154 while (Stack.back() != &FG) {
155 DSGraph *NG = Stack.back();
160 // Update the DSInfo map and delete the old graph...
161 for (DSGraph::retnodes_iterator I = NG->retnodes_begin();
162 I != NG->retnodes_end(); ++I)
163 DSInfo[I->first] = &FG;
165 // Remove NG from the ValMap since the pointer may get recycled.
170 IsMultiNodeSCC = true;
173 // Clean up the graph before we start inlining a bunch again...
175 FG.removeTriviallyDeadNodes();
184 /// processGraph - Process the BU graphs for the program in bottom-up order on
185 /// the SCC of the __ACTUAL__ call graph. This builds "complete" BU graphs.
186 void CompleteBUDataStructures::processGraph(DSGraph &G) {
187 hash_set<Instruction*> calls;
189 // The edges out of the current node are the call site targets...
191 for (DSGraph::fc_iterator CI = G.fc_begin(), CE = G.fc_end(); CI != CE;
193 const DSCallSite &CS = *CI;
194 Instruction *TheCall = CS.getCallSite().getInstruction();
196 assert(calls.insert(TheCall).second &&
197 "Call instruction occurs multiple times in graph??");
199 // Fast path for noop calls. Note that we don't care about merging globals
200 // in the callee with nodes in the caller here.
201 if (CS.getRetVal().isNull() && CS.getNumPtrArgs() == 0)
204 // Loop over all of the potentially called functions...
205 // Inline direct calls as well as indirect calls because the direct
206 // callee may have indirect callees and so may have changed.
208 callee_iterator I = callee_begin(TheCall),E = callee_end(TheCall);
209 unsigned TNum = 0, Num = 0;
210 DEBUG(Num = std::distance(I, E));
211 for (; I != E; ++I, ++TNum) {
212 assert(I->first == TheCall && "Bad callee construction!");
213 Function *CalleeFunc = I->second;
214 if (!CalleeFunc->isExternal()) {
215 // Merge the callee's graph into this graph. This works for normal
216 // calls or for self recursion within an SCC.
217 DSGraph &GI = getOrCreateGraph(*CalleeFunc);
219 G.mergeInGraph(CS, *CalleeFunc, GI,
220 DSGraph::StripAllocaBit | DSGraph::DontCloneCallNodes |
221 DSGraph::DontCloneAuxCallNodes);
222 DEBUG(std::cerr << " Inlining graph [" << i << "/"
223 << G.getFunctionCalls().size()-1
224 << ":" << TNum << "/" << Num-1 << "] for "
225 << CalleeFunc->getName() << "["
226 << GI.getGraphSize() << "+" << GI.getAuxFunctionCalls().size()
227 << "] into '" /*<< G.getFunctionNames()*/ << "' ["
228 << G.getGraphSize() << "+" << G.getAuxFunctionCalls().size()
234 // Recompute the Incomplete markers
235 G.maskIncompleteMarkers();
236 G.markIncompleteNodes(DSGraph::MarkFormalArgs);
238 // Delete dead nodes. Treat globals that are unreachable but that can
239 // reach live nodes as live.
240 G.removeDeadNodes(DSGraph::KeepUnreachableGlobals);