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 RegisterAnalysis<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))
60 calculateSCCGraphs(getOrCreateGraph(*I), Stack, NextID, ValMap);
62 GlobalsGraph->removeTriviallyDeadNodes();
65 // Merge the globals variables (not the calls) from the globals graph back
66 // into the main function's graph so that the main function contains all of
67 // the information about global pools and GV usage in the program.
68 if (MainFunc && !MainFunc->isExternal()) {
69 DSGraph &MainGraph = getOrCreateGraph(*MainFunc);
70 const DSGraph &GG = *MainGraph.getGlobalsGraph();
71 ReachabilityCloner RC(MainGraph, GG,
72 DSGraph::DontCloneCallNodes |
73 DSGraph::DontCloneAuxCallNodes);
75 // Clone the global nodes into this graph.
76 for (DSScalarMap::global_iterator I = GG.getScalarMap().global_begin(),
77 E = GG.getScalarMap().global_end(); I != E; ++I)
78 if (isa<GlobalVariable>(*I))
79 RC.getClonedNH(GG.getNodeForValue(*I));
81 MainGraph.maskIncompleteMarkers();
82 MainGraph.markIncompleteNodes(DSGraph::MarkFormalArgs |
83 DSGraph::IgnoreGlobals);
89 DSGraph &CompleteBUDataStructures::getOrCreateGraph(Function &F) {
90 // Has the graph already been created?
91 DSGraph *&Graph = DSInfo[&F];
92 if (Graph) return *Graph;
94 // Copy the BU graph...
95 Graph = new DSGraph(getAnalysis<BUDataStructures>().getDSGraph(F), GlobalECs);
96 Graph->setGlobalsGraph(GlobalsGraph);
97 Graph->setPrintAuxCalls();
99 // Make sure to update the DSInfo map for all of the functions currently in
101 for (DSGraph::retnodes_iterator I = Graph->retnodes_begin();
102 I != Graph->retnodes_end(); ++I)
103 DSInfo[I->first] = Graph;
110 unsigned CompleteBUDataStructures::calculateSCCGraphs(DSGraph &FG,
111 std::vector<DSGraph*> &Stack,
113 hash_map<DSGraph*, unsigned> &ValMap) {
114 assert(!ValMap.count(&FG) && "Shouldn't revisit functions!");
115 unsigned Min = NextID++, MyID = Min;
117 Stack.push_back(&FG);
119 // The edges out of the current node are the call site targets...
120 for (DSGraph::fc_iterator CI = FG.fc_begin(), CE = FG.fc_end();
122 Instruction *Call = CI->getCallSite().getInstruction();
124 // Loop over all of the actually called functions...
125 callee_iterator I = callee_begin(Call), E = callee_end(Call);
126 for (; I != E && I->first == Call; ++I) {
127 assert(I->first == Call && "Bad callee construction!");
128 if (!I->second->isExternal()) {
129 DSGraph &Callee = getOrCreateGraph(*I->second);
131 // Have we visited the destination function yet?
132 hash_map<DSGraph*, unsigned>::iterator It = ValMap.find(&Callee);
133 if (It == ValMap.end()) // No, visit it now.
134 M = calculateSCCGraphs(Callee, Stack, NextID, ValMap);
135 else // Yes, get it's number.
137 if (M < Min) Min = M;
142 assert(ValMap[&FG] == MyID && "SCC construction assumption wrong!");
144 return Min; // This is part of a larger SCC!
146 // If this is a new SCC, process it now.
147 bool IsMultiNodeSCC = false;
148 while (Stack.back() != &FG) {
149 DSGraph *NG = Stack.back();
154 // Update the DSInfo map and delete the old graph...
155 for (DSGraph::retnodes_iterator I = NG->retnodes_begin();
156 I != NG->retnodes_end(); ++I)
157 DSInfo[I->first] = &FG;
159 // Remove NG from the ValMap since the pointer may get recycled.
164 IsMultiNodeSCC = true;
167 // Clean up the graph before we start inlining a bunch again...
169 FG.removeTriviallyDeadNodes();
178 /// processGraph - Process the BU graphs for the program in bottom-up order on
179 /// the SCC of the __ACTUAL__ call graph. This builds "complete" BU graphs.
180 void CompleteBUDataStructures::processGraph(DSGraph &G) {
181 hash_set<Instruction*> calls;
183 // The edges out of the current node are the call site targets...
185 for (DSGraph::fc_iterator CI = G.fc_begin(), CE = G.fc_end(); CI != CE;
187 const DSCallSite &CS = *CI;
188 Instruction *TheCall = CS.getCallSite().getInstruction();
190 assert(calls.insert(TheCall).second &&
191 "Call instruction occurs multiple times in graph??");
193 // Fast path for noop calls. Note that we don't care about merging globals
194 // in the callee with nodes in the caller here.
195 if (CS.getRetVal().isNull() && CS.getNumPtrArgs() == 0)
198 // Loop over all of the potentially called functions...
199 // Inline direct calls as well as indirect calls because the direct
200 // callee may have indirect callees and so may have changed.
202 callee_iterator I = callee_begin(TheCall),E = callee_end(TheCall);
203 unsigned TNum = 0, Num = 0;
204 DEBUG(Num = std::distance(I, E));
205 for (; I != E; ++I, ++TNum) {
206 assert(I->first == TheCall && "Bad callee construction!");
207 Function *CalleeFunc = I->second;
208 if (!CalleeFunc->isExternal()) {
209 // Merge the callee's graph into this graph. This works for normal
210 // calls or for self recursion within an SCC.
211 DSGraph &GI = getOrCreateGraph(*CalleeFunc);
213 G.mergeInGraph(CS, *CalleeFunc, GI,
214 DSGraph::StripAllocaBit | DSGraph::DontCloneCallNodes |
215 DSGraph::DontCloneAuxCallNodes);
216 DEBUG(std::cerr << " Inlining graph [" << i << "/"
217 << G.getFunctionCalls().size()-1
218 << ":" << TNum << "/" << Num-1 << "] for "
219 << CalleeFunc->getName() << "["
220 << GI.getGraphSize() << "+" << GI.getAuxFunctionCalls().size()
221 << "] into '" /*<< G.getFunctionNames()*/ << "' ["
222 << G.getGraphSize() << "+" << G.getAuxFunctionCalls().size()
228 // Recompute the Incomplete markers
229 G.maskIncompleteMarkers();
230 G.markIncompleteNodes(DSGraph::MarkFormalArgs);
232 // Delete dead nodes. Treat globals that are unreachable but that can
233 // reach live nodes as live.
234 G.removeDeadNodes(DSGraph::KeepUnreachableGlobals);