blob: 58327016dc4ef20b6516ec6f078b821c5a0d9588 [file] [log] [blame]
Chris Lattner95724a42003-11-13 01:43:00 +00001//===- CompleteBottomUp.cpp - Complete Bottom-Up Data Structure Graphs ----===//
2//
3// The LLVM Compiler Infrastructure
4//
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.
7//
8//===----------------------------------------------------------------------===//
9//
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.
13//
14//===----------------------------------------------------------------------===//
15
16#include "llvm/Analysis/DataStructure.h"
17#include "llvm/Module.h"
18#include "llvm/Analysis/DSGraph.h"
Chris Lattner79390d42003-11-13 05:05:41 +000019#include "Support/SCCIterator.h"
20#include "Support/STLExtras.h"
Chris Lattner95724a42003-11-13 01:43:00 +000021using namespace llvm;
22
23namespace {
24 RegisterAnalysis<CompleteBUDataStructures>
25 X("cbudatastructure", "'Complete' Bottom-up Data Structure Analysis");
26}
27
Chris Lattner95724a42003-11-13 01:43:00 +000028
29// run - Calculate the bottom up data structure graphs for each function in the
30// program.
31//
32bool CompleteBUDataStructures::run(Module &M) {
33 BUDataStructures &BU = getAnalysis<BUDataStructures>();
34 GlobalsGraph = new DSGraph(BU.getGlobalsGraph());
35 GlobalsGraph->setPrintAuxCalls();
36
37 // Our call graph is the same as the BU data structures call graph
38 ActualCallees = BU.getActualCallees();
39
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>();
44
45 // The call graph extractable from the TD pass is _much more complete_ and
46 // trustable than that generated by the BU pass so far. Until this is fixed,
47 // we hack it like this:
48 for (Module::iterator MI = M.begin(), ME = M.end(); MI != ME; ++MI) {
49 if (MI->isExternal()) continue;
50 const std::vector<DSCallSite> &CSs = TD.getDSGraph(*MI).getFunctionCalls();
51
52 for (unsigned CSi = 0, e = CSs.size(); CSi != e; ++CSi) {
53 if (CSs[CSi].isIndirectCall()) {
54 Instruction *TheCall = CSs[CSi].getCallSite().getInstruction();
55
56 const std::vector<GlobalValue*> &Callees =
57 CSs[CSi].getCalleeNode()->getGlobals();
58 for (unsigned i = 0, e = Callees.size(); i != e; ++i)
59 if (Function *F = dyn_cast<Function>(Callees[i]))
60 ActualCallees.insert(std::make_pair(TheCall, F));
61 }
62 }
63 }
64#endif
65
Chris Lattner79390d42003-11-13 05:05:41 +000066 std::vector<DSGraph*> Stack;
67 hash_map<DSGraph*, unsigned> ValMap;
68 unsigned NextID = 1;
Chris Lattner95724a42003-11-13 01:43:00 +000069
Chris Lattner79390d42003-11-13 05:05:41 +000070 if (Function *Main = M.getMainFunction()) {
71 calculateSCCGraphs(getOrCreateGraph(*Main), Stack, NextID, ValMap);
72 } else {
73 std::cerr << "CBU-DSA: No 'main' function found!\n";
74 }
75
76 for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
77 if (!I->isExternal() && !DSInfo.count(I))
78 calculateSCCGraphs(getOrCreateGraph(*I), Stack, NextID, ValMap);
Chris Lattner95724a42003-11-13 01:43:00 +000079
80 return false;
81}
Chris Lattner79390d42003-11-13 05:05:41 +000082
83DSGraph &CompleteBUDataStructures::getOrCreateGraph(Function &F) {
84 // Has the graph already been created?
85 DSGraph *&Graph = DSInfo[&F];
86 if (Graph) return *Graph;
87
88 // Copy the BU graph...
89 Graph = new DSGraph(getAnalysis<BUDataStructures>().getDSGraph(F));
90 Graph->setGlobalsGraph(GlobalsGraph);
91 Graph->setPrintAuxCalls();
92
93 // Make sure to update the DSInfo map for all of the functions currently in
94 // this graph!
95 for (DSGraph::ReturnNodesTy::iterator I = Graph->getReturnNodes().begin();
96 I != Graph->getReturnNodes().end(); ++I)
97 DSInfo[I->first] = Graph;
98
99 return *Graph;
100}
101
102
103
104unsigned CompleteBUDataStructures::calculateSCCGraphs(DSGraph &FG,
105 std::vector<DSGraph*> &Stack,
106 unsigned &NextID,
107 hash_map<DSGraph*, unsigned> &ValMap) {
108 assert(!ValMap.count(&FG) && "Shouldn't revisit functions!");
109 unsigned Min = NextID++, MyID = Min;
110 ValMap[&FG] = Min;
111 Stack.push_back(&FG);
112
113 // The edges out of the current node are the call site targets...
114 for (unsigned i = 0, e = FG.getFunctionCalls().size(); i != e; ++i) {
115 Instruction *Call = FG.getFunctionCalls()[i].getCallSite().getInstruction();
116
117 // Loop over all of the actually called functions...
118 ActualCalleesTy::iterator I, E;
Chris Lattnera366c982003-11-13 18:48:11 +0000119 for (tie(I, E) = ActualCallees.equal_range(Call); I != E; ++I)
120 if (!I->second->isExternal()) {
121 DSGraph &Callee = getOrCreateGraph(*I->second);
122 unsigned M;
123 // Have we visited the destination function yet?
124 hash_map<DSGraph*, unsigned>::iterator It = ValMap.find(&Callee);
125 if (It == ValMap.end()) // No, visit it now.
126 M = calculateSCCGraphs(Callee, Stack, NextID, ValMap);
127 else // Yes, get it's number.
128 M = It->second;
129 if (M < Min) Min = M;
130 }
Chris Lattner79390d42003-11-13 05:05:41 +0000131 }
132
133 assert(ValMap[&FG] == MyID && "SCC construction assumption wrong!");
134 if (Min != MyID)
135 return Min; // This is part of a larger SCC!
136
137 // If this is a new SCC, process it now.
138 bool IsMultiNodeSCC = false;
139 while (Stack.back() != &FG) {
140 DSGraph *NG = Stack.back();
141 ValMap[NG] = ~0U;
142
143 DSGraph::NodeMapTy NodeMap;
Chris Lattner825a02a2004-01-27 21:50:41 +0000144 FG.cloneInto(*NG, FG.getScalarMap(), FG.getReturnNodes(), NodeMap);
Chris Lattner79390d42003-11-13 05:05:41 +0000145
146 // Update the DSInfo map and delete the old graph...
147 for (DSGraph::ReturnNodesTy::iterator I = NG->getReturnNodes().begin();
148 I != NG->getReturnNodes().end(); ++I)
149 DSInfo[I->first] = &FG;
150 delete NG;
151
152 Stack.pop_back();
153 IsMultiNodeSCC = true;
154 }
155
156 // Clean up the graph before we start inlining a bunch again...
157 if (IsMultiNodeSCC)
158 FG.removeTriviallyDeadNodes();
159
160 Stack.pop_back();
161 processGraph(FG);
162 ValMap[&FG] = ~0U;
163 return MyID;
164}
165
166
167/// processGraph - Process the BU graphs for the program in bottom-up order on
168/// the SCC of the __ACTUAL__ call graph. This builds "complete" BU graphs.
169void CompleteBUDataStructures::processGraph(DSGraph &G) {
170 // The edges out of the current node are the call site targets...
171 for (unsigned i = 0, e = G.getFunctionCalls().size(); i != e; ++i) {
172 const DSCallSite &CS = G.getFunctionCalls()[i];
173 Instruction *TheCall = CS.getCallSite().getInstruction();
174
175 // The Normal BU pass will have taken care of direct calls well already,
176 // don't worry about them.
177 if (!CS.getCallSite().getCalledFunction()) {
178 // Loop over all of the actually called functions...
179 ActualCalleesTy::iterator I, E;
180 for (tie(I, E) = ActualCallees.equal_range(TheCall); I != E; ++I) {
181 Function *CalleeFunc = I->second;
182 if (!CalleeFunc->isExternal()) {
183 // Merge the callee's graph into this graph. This works for normal
184 // calls or for self recursion within an SCC.
185 G.mergeInGraph(CS, *CalleeFunc, getOrCreateGraph(*CalleeFunc),
186 DSGraph::KeepModRefBits |
187 DSGraph::StripAllocaBit |
188 DSGraph::DontCloneCallNodes);
189 }
190 }
191 }
192 }
193
194 // Re-materialize nodes from the globals graph.
195 // Do not ignore globals inlined from callees -- they are not up-to-date!
Chris Lattner825a02a2004-01-27 21:50:41 +0000196 assert(G.getInlinedGlobals().empty());
Chris Lattner79390d42003-11-13 05:05:41 +0000197 G.updateFromGlobalGraph();
198
199 // Recompute the Incomplete markers
200 G.maskIncompleteMarkers();
201 G.markIncompleteNodes(DSGraph::MarkFormalArgs);
202
203 // Delete dead nodes. Treat globals that are unreachable but that can
204 // reach live nodes as live.
205 G.removeDeadNodes(DSGraph::KeepUnreachableGlobals);
206}