//===- BottomUpClosure.cpp - Compute bottom-up interprocedural closure ----===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
//
// This file implements the BUDataStructures class, which represents the
// Bottom-Up Interprocedural closure of the data structure graph over the
//
//===----------------------------------------------------------------------===//
-#include "DSCallSiteIterator.h"
#include "llvm/Analysis/DataStructure.h"
#include "llvm/Module.h"
#include "Support/Statistic.h"
+#include "Support/Debug.h"
+#include "DSCallSiteIterator.h"
+using namespace llvm;
namespace {
Statistic<> MaxSCC("budatastructure", "Maximum SCC Size in Call Graph");
+ Statistic<> NumBUInlines("budatastructures", "Number of graphs inlined");
+ Statistic<> NumCallEdges("budatastructures", "Number of 'actual' call edges");
RegisterAnalysis<BUDataStructures>
X("budatastructure", "Bottom-up Data Structure Analysis");
// Calculate the graphs for any functions that are unreachable from main...
for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
- if (!I->isExternal() && DSInfo.find(I) == DSInfo.end()) {
+ if (!I->isExternal() && !DSInfo.count(I)) {
#ifndef NDEBUG
if (MainFunc)
std::cerr << "*** Function unreachable from main: "
#endif
calculateReachableGraphs(I); // Calculate all graphs...
}
+
+ NumCallEdges += ActualCallees.size();
+
+ // At the end of the bottom-up pass, the globals graph becomes complete.
+ // FIXME: This is not the right way to do this, but it is sorta better than
+ // nothing! In particular, externally visible globals and unresolvable call
+ // nodes at the end of the BU phase should make things that they point to
+ // incomplete in the globals graph.
+ //
+ GlobalsGraph->maskIncompleteMarkers();
return false;
}
std::vector<Function*> &Stack,
unsigned &NextID,
hash_map<Function*, unsigned> &ValMap) {
- assert(ValMap.find(F) == ValMap.end() && "Shouldn't revisit functions!");
+ assert(!ValMap.count(F) && "Shouldn't revisit functions!");
unsigned Min = NextID++, MyID = Min;
ValMap[F] = Min;
Stack.push_back(F);
}
}
+ // Clean up the graph before we start inlining a bunch again...
+ SCCGraph->removeTriviallyDeadNodes();
+
// Now that we have one big happy family, resolve all of the call sites in
// the graph...
calculateGraph(*SCCGraph);
// Resolve the current call...
Function *Callee = *I;
- const DSCallSite &CS = I.getCallSite();
+ DSCallSite CS = I.getCallSite();
if (Callee->isExternal()) {
// Ignore this case, simple varargs functions we cannot stub out!
- } else if (ReturnNodes.find(Callee) != ReturnNodes.end()) {
+ } else if (ReturnNodes.count(Callee)) {
// Self recursion... simply link up the formal arguments with the
// actual arguments...
DEBUG(std::cerr << " Self Inlining: " << Callee->getName() << "\n");
Graph.mergeInGraph(CS, *Callee, Graph, 0);
} else {
+ ActualCallees.insert(std::make_pair(CS.getCallSite().getInstruction(),
+ Callee));
+
// Get the data structure graph for the called function.
//
DSGraph &GI = getDSGraph(*Callee); // Graph to inline
DEBUG(std::cerr << " Inlining graph for " << Callee->getName()
<< "[" << GI.getGraphSize() << "+"
- << GI.getAuxFunctionCalls().size() << "] into ["
- << Graph.getGraphSize() << "+"
+ << GI.getAuxFunctionCalls().size() << "] into '"
+ << Graph.getFunctionNames() << "' [" << Graph.getGraphSize() << "+"
<< Graph.getAuxFunctionCalls().size() << "]\n");
// Handle self recursion by resolving the arguments and return value
Graph.mergeInGraph(CS, *Callee, GI,
DSGraph::KeepModRefBits |
DSGraph::StripAllocaBit | DSGraph::DontCloneCallNodes);
+ ++NumBUInlines;
#if 0
Graph.writeGraphToFile(std::cerr, "bu_" + F.getName() + "_after_" +
TempFCs.clear();
- // Recompute the Incomplete markers. If there are any function calls left
- // now that are complete, we must loop!
+ // Re-materialize nodes from the globals graph.
+ // Do not ignore globals inlined from callees -- they are not up-to-date!
+ Graph.getInlinedGlobals().clear();
+ Graph.updateFromGlobalGraph();
+
+ // Recompute the Incomplete markers
Graph.maskIncompleteMarkers();
Graph.markIncompleteNodes(DSGraph::MarkFormalArgs);
- // FIXME: materialize nodes from the globals graph as neccesary...
+
+ // Delete dead nodes. Treat globals that are unreachable but that can
+ // reach live nodes as live.
Graph.removeDeadNodes(DSGraph::KeepUnreachableGlobals);
//Graph.writeGraphToFile(std::cerr, "bu_" + F.getName());
}
-