aboutsummaryrefslogtreecommitdiff
path: root/lib/Analysis/DataStructure/BottomUpClosure.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'lib/Analysis/DataStructure/BottomUpClosure.cpp')
-rw-r--r--lib/Analysis/DataStructure/BottomUpClosure.cpp121
1 files changed, 78 insertions, 43 deletions
diff --git a/lib/Analysis/DataStructure/BottomUpClosure.cpp b/lib/Analysis/DataStructure/BottomUpClosure.cpp
index c8b45b50cc..3ea7f0c96a 100644
--- a/lib/Analysis/DataStructure/BottomUpClosure.cpp
+++ b/lib/Analysis/DataStructure/BottomUpClosure.cpp
@@ -11,17 +11,18 @@
#include "llvm/Module.h"
#include "llvm/DerivedTypes.h"
#include "Support/StatisticReporter.h"
+#include <set>
using std::map;
static RegisterAnalysis<BUDataStructures>
-X("budatastructure", "Bottom-Up Data Structure Analysis Closure");
+X("budatastructure", "Bottom-up Data Structure Analysis Closure");
AnalysisID BUDataStructures::ID = X;
// releaseMemory - If the pass pipeline is done with this pass, we can release
// our memory... here...
//
void BUDataStructures::releaseMemory() {
- for (map<Function*, DSGraph*>::iterator I = DSInfo.begin(),
+ for (map<const Function*, DSGraph*>::iterator I = DSInfo.begin(),
E = DSInfo.end(); I != E; ++I)
delete I->second;
@@ -60,23 +61,29 @@ static void ResolveArguments(std::vector<DSNodeHandle> &Call, Function &F,
}
}
-// MergeGlobalNodes - Merge global value nodes in the inlined graph with the
-// global value nodes in the current graph if there are duplicates.
+// MergeGlobalNodes - Merge all existing global nodes with globals
+// inlined from the callee or with globals from the GlobalsGraph.
//
-static void MergeGlobalNodes(map<Value*, DSNodeHandle> &ValMap,
+static void MergeGlobalNodes(DSGraph& Graph,
map<Value*, DSNodeHandle> &OldValMap) {
- // Loop over all of the nodes inlined, if any of them are global variable
- // nodes, we must make sure they get properly added or merged with the ValMap.
- //
+ map<Value*, DSNodeHandle> &ValMap = Graph.getValueMap();
+ for (map<Value*, DSNodeHandle>::iterator I = ValMap.begin(), E = ValMap.end();
+ I != E; ++I)
+ if (GlobalValue* GV = dyn_cast<GlobalValue>(I->first)) {
+ map<Value*, DSNodeHandle>:: iterator NHI = OldValMap.find(GV);
+ if (NHI != OldValMap.end()) // was it inlined from the callee?
+ I->second->mergeWith(NHI->second);
+ else // get it from the GlobalsGraph
+ I->second->mergeWith(Graph.cloneGlobalInto(GV));
+ }
+
+ // Add unused inlined global nodes into the value map
for (map<Value*, DSNodeHandle>::iterator I = OldValMap.begin(),
E = OldValMap.end(); I != E; ++I)
if (isa<GlobalValue>(I->first)) {
- DSNodeHandle &NH = ValMap[I->first]; // Look up global in ValMap.
- if (NH == 0) { // No entry for the global yet?
- NH = I->second; // Add the one just inlined...
- } else {
- NH->mergeWith(I->second); // Merge the two globals together.
- }
+ DSNodeHandle &NH = ValMap[I->first]; // If global is not in ValMap...
+ if (NH == 0)
+ NH = I->second; // Add the one just inlined.
}
}
@@ -91,17 +98,29 @@ DSGraph &BUDataStructures::calculateGraph(Function &F) {
// Copy the local version into DSInfo...
Graph = new DSGraph(getAnalysis<LocalDataStructures>().getDSGraph(F));
+ // Populate the GlobalsGraph with globals from this one.
+ Graph->GlobalsGraph->cloneGlobals(*Graph, /*cloneCalls*/ false);
+
// Save a copy of the original call nodes for the top-down pass
Graph->saveOrigFunctionCalls();
-
+
// Start resolving calls...
std::vector<std::vector<DSNodeHandle> > &FCs = Graph->getFunctionCalls();
- DEBUG(std::cerr << "Inlining: " << F.getName() << "\n");
+ DEBUG(std::cerr << " [BU] Inlining: " << F.getName() << "\n");
+
+ // Add F to the PendingCallers list of each direct callee for use in the
+ // top-down pass so we don't have to compute this again. We don't want
+ // to do it for indirect callees inlined later, so remember which calls
+ // are in the original FCs set.
+ std::set<const DSNode*> directCallees;
+ for (unsigned i = 0; i < FCs.size(); ++i)
+ directCallees.insert(FCs[i][1]); // ptr to function node
bool Inlined;
do {
Inlined = false;
+
for (unsigned i = 0; i != FCs.size(); ++i) {
// Copy the call, because inlining graphs may invalidate the FCs vector.
std::vector<DSNodeHandle> Call = FCs[i];
@@ -111,17 +130,17 @@ DSGraph &BUDataStructures::calculateGraph(Function &F) {
// Start inlining all of the functions we can... some may not be
// inlinable if they are external...
//
- std::vector<GlobalValue*> Globals(Call[1]->getGlobals());
+ std::vector<GlobalValue*> Callees(Call[1]->getGlobals());
// Loop over the functions, inlining whatever we can...
- for (unsigned g = 0; g != Globals.size(); ++g) {
+ for (unsigned c = 0; c != Callees.size(); ++c) {
// Must be a function type, so this cast MUST succeed.
- Function &FI = cast<Function>(*Globals[g]);
+ Function &FI = cast<Function>(*Callees[c]);
if (&FI == &F) {
// Self recursion... simply link up the formal arguments with the
// actual arguments...
-
- DEBUG(std::cerr << "Self Inlining: " << F.getName() << "\n");
+
+ DEBUG(std::cerr << "\t[BU] Self Inlining: " << F.getName() << "\n");
if (Call[0]) // Handle the return value if present...
Graph->RetNode->mergeWith(Call[0]);
@@ -129,10 +148,10 @@ DSGraph &BUDataStructures::calculateGraph(Function &F) {
// Resolve the arguments in the call to the actual values...
ResolveArguments(Call, F, Graph->getValueMap());
- // Erase the entry in the globals vector
- Globals.erase(Globals.begin()+g--);
+ // Erase the entry in the callees vector
+ Callees.erase(Callees.begin()+c--);
} else if (!FI.isExternal()) {
- DEBUG(std::cerr << "In " << F.getName() << " inlining: "
+ DEBUG(std::cerr << "\t[BU] In " << F.getName() << " inlining: "
<< FI.getName() << "\n");
// Get the data structure graph for the called function, closing it
@@ -141,49 +160,54 @@ DSGraph &BUDataStructures::calculateGraph(Function &F) {
//
DSGraph &GI = calculateGraph(FI); // Graph to inline
- DEBUG(std::cerr << "Got graph for " << FI.getName() << " in: "
- << F.getName() << "\n");
-
- // Remember the callers for each callee for use in the top-down
- // pass so we don't have to compute this again
- GI.addCaller(F);
+ DEBUG(std::cerr << "\t\t[BU] Got graph for " << FI.getName()
+ << " in: " << F.getName() << "\n");
// Clone the callee's graph into the current graph, keeping
- // track of where scalars in the old graph _used_ to point
- // and of the new nodes matching nodes of the old graph ...
+ // track of where scalars in the old graph _used_ to point,
+ // and of the new nodes matching nodes of the old graph.
std::map<Value*, DSNodeHandle> OldValMap;
- std::map<const DSNode*, DSNode*> OldNodeMap; // unused
+ std::map<const DSNode*, DSNode*> OldNodeMap;
// The clone call may invalidate any of the vectors in the data
- // structure graph.
- DSNode *RetVal = Graph->cloneInto(GI, OldValMap, OldNodeMap);
+ // structure graph. Strip locals and don't copy the list of callers
+ DSNode *RetVal = Graph->cloneInto(GI, OldValMap, OldNodeMap,
+ /*StripScalars*/ true,
+ /*StripAllocas*/ true,
+ /*CopyCallers*/ false,
+ /*CopyOrigCalls*/ false);
ResolveArguments(Call, FI, OldValMap);
if (Call[0]) // Handle the return value if present
RetVal->mergeWith(Call[0]);
-
+
// Merge global value nodes in the inlined graph with the global
// value nodes in the current graph if there are duplicates.
//
- MergeGlobalNodes(Graph->getValueMap(), OldValMap);
+ MergeGlobalNodes(*Graph, OldValMap);
+
+ // If this was an original call, add F to the PendingCallers list
+ if (directCallees.find(Call[1]) != directCallees.end())
+ GI.addCaller(F);
+
+ // Erase the entry in the Callees vector
+ Callees.erase(Callees.begin()+c--);
- // Erase the entry in the globals vector
- Globals.erase(Globals.begin()+g--);
} else if (FI.getName() == "printf" || FI.getName() == "sscanf" ||
FI.getName() == "fprintf" || FI.getName() == "open" ||
FI.getName() == "sprintf") {
// Erase the entry in the globals vector
- Globals.erase(Globals.begin()+g--);
+ Callees.erase(Callees.begin()+c--);
}
}
- if (Globals.empty()) { // Inlined all of the function calls?
+ if (Callees.empty()) { // Inlined all of the function calls?
// Erase the call if it is resolvable...
FCs.erase(FCs.begin()+i--); // Don't skip a the next call...
Inlined = true;
- } else if (Globals.size() != Call[1]->getGlobals().size()) {
+ } else if (Callees.size() != Call[1]->getGlobals().size()) {
// Was able to inline SOME, but not all of the functions. Construct a
// new global node here.
//
@@ -198,9 +222,20 @@ DSGraph &BUDataStructures::calculateGraph(Function &F) {
if (Inlined) {
Graph->maskIncompleteMarkers();
Graph->markIncompleteNodes();
- Graph->removeDeadNodes();
+ Graph->removeDeadNodes(/*KeepAllGlobals*/ false, /*KeepCalls*/ true);
}
} while (Inlined && !FCs.empty());
+ // Copy any unresolved call nodes into the Globals graph and
+ // filter out unresolved call nodes inlined from the callee.
+ if (!FCs.empty())
+ Graph->GlobalsGraph->cloneCalls(*Graph);
+
+ Graph->maskIncompleteMarkers();
+ Graph->markIncompleteNodes();
+ Graph->removeDeadNodes(/*KeepAllGlobals*/ false, /*KeepCalls*/ false);
+
+ DEBUG(cerr << " [BU] Done inlining: " << F.getName() << "\n");
+
return *Graph;
}
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-05-01 10:42:29 +0000