summaryrefslogtreecommitdiff
path: root/lib/Analysis
diff options
context:
space:
mode:
authorChris Lattner <sabre@nondot.org>2005-04-02 19:17:18 +0000
committerChris Lattner <sabre@nondot.org>2005-04-02 19:17:18 +0000
commit021decc82d843c69363d3d6ee1a202613911c61c (patch)
tree885dc36165581cd92ccdb404d81cba5c19f1ace2 /lib/Analysis
parentdf968b8b37d93c105ced41bea5d3231ee171a24e (diff)
Change the ActualCallees callgraph from hash_multimap<Instruction,Function>
to std::set<std::pair<Inst,Func>> to avoid duplicate entries. This speeds up the CompleteBU pass from 1.99s to .15s on povray and the eqgraph passes from 1.5s to .16s on the same. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21031 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib/Analysis')
-rw-r--r--lib/Analysis/DataStructure/CompleteBottomUp.cpp45
-rw-r--r--lib/Analysis/DataStructure/DataStructure.cpp2
-rw-r--r--lib/Analysis/DataStructure/EquivClassGraphs.cpp8
-rw-r--r--lib/Analysis/DataStructure/Steensgaard.cpp8
-rw-r--r--lib/Analysis/DataStructure/TopDownClosure.cpp55
5 files changed, 40 insertions, 78 deletions
diff --git a/lib/Analysis/DataStructure/CompleteBottomUp.cpp b/lib/Analysis/DataStructure/CompleteBottomUp.cpp
index 3cb0b6eb845..834ae9738f0 100644
--- a/lib/Analysis/DataStructure/CompleteBottomUp.cpp
+++ b/lib/Analysis/DataStructure/CompleteBottomUp.cpp
@@ -13,6 +13,7 @@
//
//===----------------------------------------------------------------------===//
+#define DEBUG_TYPE "cbudatastructure"
#include "llvm/Analysis/DataStructure/DataStructure.h"
#include "llvm/Module.h"
#include "llvm/Analysis/DataStructure/DSGraph.h"
@@ -37,39 +38,8 @@ bool CompleteBUDataStructures::runOnModule(Module &M) {
GlobalsGraph = new DSGraph(BU.getGlobalsGraph(), GlobalECs);
GlobalsGraph->setPrintAuxCalls();
-#if 1 // REMOVE ME EVENTUALLY
- // FIXME: TEMPORARY (remove once finalization of indirect call sites in the
- // globals graph has been implemented in the BU pass)
- TDDataStructures &TD = getAnalysis<TDDataStructures>();
-
- ActualCallees.clear();
-
- // The call graph extractable from the TD pass is _much more complete_ and
- // trustable than that generated by the BU pass so far. Until this is fixed,
- // we hack it like this:
- for (Module::iterator MI = M.begin(), ME = M.end(); MI != ME; ++MI) {
- if (MI->isExternal()) continue;
- const std::list<DSCallSite> &CSs = TD.getDSGraph(*MI).getFunctionCalls();
-
- for (std::list<DSCallSite>::const_iterator CSI = CSs.begin(), E = CSs.end();
- CSI != E; ++CSI) {
- Instruction *TheCall = CSI->getCallSite().getInstruction();
-
- if (CSI->isIndirectCall()) { // indirect call: insert all callees
- std::vector<Function*> Callees;
- CSI->getCalleeNode()->addFullFunctionList(Callees);
- for (unsigned i = 0, e = Callees.size(); i != e; ++i)
- ActualCallees.insert(std::make_pair(TheCall, Callees[i]));
- } else { // direct call: insert the single callee directly
- ActualCallees.insert(std::make_pair(TheCall,
- CSI->getCalleeFunc()));
- }
- }
- }
-#else
// Our call graph is the same as the BU data structures call graph
ActualCallees = BU.getActualCallees();
-#endif
std::vector<DSGraph*> Stack;
hash_map<DSGraph*, unsigned> ValMap;
@@ -150,8 +120,9 @@ unsigned CompleteBUDataStructures::calculateSCCGraphs(DSGraph &FG,
Instruction *Call = CI->getCallSite().getInstruction();
// Loop over all of the actually called functions...
- ActualCalleesTy::iterator I, E;
- for (tie(I, E) = ActualCallees.equal_range(Call); I != E; ++I)
+ ActualCalleesTy::iterator I = callee_begin(Call), E = callee_end(Call);
+ for (; I != E && I->first == Call; ++I) {
+ assert(I->first == Call && "Bad callee construction!");
if (!I->second->isExternal()) {
DSGraph &Callee = getOrCreateGraph(*I->second);
unsigned M;
@@ -163,6 +134,7 @@ unsigned CompleteBUDataStructures::calculateSCCGraphs(DSGraph &FG,
M = It->second;
if (M < Min) Min = M;
}
+ }
}
assert(ValMap[&FG] == MyID && "SCC construction assumption wrong!");
@@ -225,10 +197,11 @@ void CompleteBUDataStructures::processGraph(DSGraph &G) {
// Inline direct calls as well as indirect calls because the direct
// callee may have indirect callees and so may have changed.
//
- ActualCalleesTy::iterator I, E;
- tie(I, E) = ActualCallees.equal_range(TheCall);
- unsigned TNum = 0, Num = std::distance(I, E);
+ ActualCalleesTy::iterator I = callee_begin(TheCall),E = callee_end(TheCall);
+ unsigned TNum = 0, Num = 0;
+ DEBUG(Num = std::distance(I, E));
for (; I != E; ++I, ++TNum) {
+ assert(I->first == TheCall && "Bad callee construction!");
Function *CalleeFunc = I->second;
if (!CalleeFunc->isExternal()) {
// Merge the callee's graph into this graph. This works for normal
diff --git a/lib/Analysis/DataStructure/DataStructure.cpp b/lib/Analysis/DataStructure/DataStructure.cpp
index 7bad52ac3c9..cd16e993ad6 100644
--- a/lib/Analysis/DataStructure/DataStructure.cpp
+++ b/lib/Analysis/DataStructure/DataStructure.cpp
@@ -2055,7 +2055,7 @@ void DSGraph::removeDeadNodes(unsigned Flags) {
GlobalNodes.push_back(std::make_pair(I->first, I->second.getNode()));
// Make sure that all globals are cloned over as roots.
- if (!(Flags & DSGraph::RemoveUnreachableGlobals)) {
+ if (!(Flags & DSGraph::RemoveUnreachableGlobals) && GlobalsGraph) {
DSGraph::ScalarMapTy::iterator SMI =
GlobalsGraph->getScalarMap().find(I->first);
if (SMI != GlobalsGraph->getScalarMap().end())
diff --git a/lib/Analysis/DataStructure/EquivClassGraphs.cpp b/lib/Analysis/DataStructure/EquivClassGraphs.cpp
index 288f594926b..d3ffc5205bd 100644
--- a/lib/Analysis/DataStructure/EquivClassGraphs.cpp
+++ b/lib/Analysis/DataStructure/EquivClassGraphs.cpp
@@ -339,8 +339,8 @@ processSCC(DSGraph &FG, std::vector<DSGraph*> &Stack, unsigned &NextID,
Instruction *Call = CI->getCallSite().getInstruction();
// Loop over all of the actually called functions...
- ActualCalleesTy::const_iterator I, E;
- for (tie(I, E) = getActualCallees().equal_range(Call); I != E; ++I)
+ ActualCalleesTy::const_iterator I = callee_begin(Call),E = callee_end(Call);
+ for (; I != E; ++I)
if (!I->second->isExternal()) {
// Process the callee as necessary.
unsigned M = processSCC(getOrCreateGraph(*I->second),
@@ -414,8 +414,8 @@ void EquivClassGraphs::processGraph(DSGraph &G) {
// graph so we only need to do this once.
//
DSGraph* CalleeGraph = NULL;
- ActualCalleesTy::const_iterator I, E;
- tie(I, E) = getActualCallees().equal_range(TheCall);
+ ActualCalleesTy::const_iterator I = callee_begin(TheCall);
+ ActualCalleesTy::const_iterator E = callee_end(TheCall);
unsigned TNum, Num;
// Loop over all potential callees to find the first non-external callee.
diff --git a/lib/Analysis/DataStructure/Steensgaard.cpp b/lib/Analysis/DataStructure/Steensgaard.cpp
index 747ae2fc4b7..9f0574df1a3 100644
--- a/lib/Analysis/DataStructure/Steensgaard.cpp
+++ b/lib/Analysis/DataStructure/Steensgaard.cpp
@@ -25,11 +25,10 @@ using namespace llvm;
namespace {
class Steens : public ModulePass, public AliasAnalysis {
DSGraph *ResultGraph;
- DSGraph *GlobalsGraph; // FIXME: Eliminate globals graph stuff from DNE
EquivalenceClasses<GlobalValue*> GlobalECs; // Always empty
public:
- Steens() : ResultGraph(0), GlobalsGraph(0) {}
+ Steens() : ResultGraph(0) {}
~Steens() {
releaseMyMemory();
assert(ResultGraph == 0 && "releaseMemory not called?");
@@ -116,8 +115,7 @@ bool Steens::runOnModule(Module &M) {
// Create a new, empty, graph...
ResultGraph = new DSGraph(GlobalECs, getTargetData());
- GlobalsGraph = new DSGraph(GlobalECs, getTargetData());
- ResultGraph->setGlobalsGraph(GlobalsGraph);
+ ResultGraph->spliceFrom(LDS.getGlobalsGraph());
// Loop over the rest of the module, merging graphs for non-external functions
// into this graph.
@@ -186,7 +184,7 @@ bool Steens::runOnModule(Module &M) {
// Remove any nodes that are dead after all of the merging we have done...
// FIXME: We should be able to disable the globals graph for steens!
- ResultGraph->removeDeadNodes(DSGraph::KeepUnreachableGlobals);
+ //ResultGraph->removeDeadNodes(DSGraph::KeepUnreachableGlobals);
DEBUG(print(std::cerr, &M));
return false;
diff --git a/lib/Analysis/DataStructure/TopDownClosure.cpp b/lib/Analysis/DataStructure/TopDownClosure.cpp
index e44cea1d8e1..a169ceff1d5 100644
--- a/lib/Analysis/DataStructure/TopDownClosure.cpp
+++ b/lib/Analysis/DataStructure/TopDownClosure.cpp
@@ -58,9 +58,9 @@ void TDDataStructures::markReachableFunctionsExternallyAccessible(DSNode *N,
// program.
//
bool TDDataStructures::runOnModule(Module &M) {
- BUDataStructures &BU = getAnalysis<BUDataStructures>();
- GlobalECs = BU.getGlobalECs();
- GlobalsGraph = new DSGraph(BU.getGlobalsGraph(), GlobalECs);
+ BUInfo = &getAnalysis<BUDataStructures>();
+ GlobalECs = BUInfo->getGlobalECs();
+ GlobalsGraph = new DSGraph(BUInfo->getGlobalsGraph(), GlobalECs);
GlobalsGraph->setPrintAuxCalls();
// Figure out which functions must not mark their arguments complete because
@@ -95,8 +95,6 @@ bool TDDataStructures::runOnModule(Module &M) {
// calculate a post-order traversal, then reverse it.
hash_set<DSGraph*> VisitedGraph;
std::vector<DSGraph*> PostOrder;
- const BUDataStructures::ActualCalleesTy &ActualCallees =
- getAnalysis<BUDataStructures>().getActualCallees();
#if 0
{TIME_REGION(XXX, "td:Copy graphs");
@@ -114,11 +112,11 @@ bool TDDataStructures::runOnModule(Module &M) {
// Calculate top-down from main...
if (Function *F = M.getMainFunction())
- ComputePostOrder(*F, VisitedGraph, PostOrder, ActualCallees);
+ ComputePostOrder(*F, VisitedGraph, PostOrder);
// Next calculate the graphs for each unreachable function...
for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
- ComputePostOrder(*I, VisitedGraph, PostOrder, ActualCallees);
+ ComputePostOrder(*I, VisitedGraph, PostOrder);
VisitedGraph.clear(); // Release memory!
}
@@ -167,8 +165,7 @@ DSGraph &TDDataStructures::getOrCreateDSGraph(Function &F) {
void TDDataStructures::ComputePostOrder(Function &F,hash_set<DSGraph*> &Visited,
- std::vector<DSGraph*> &PostOrder,
- const BUDataStructures::ActualCalleesTy &ActualCallees) {
+ std::vector<DSGraph*> &PostOrder) {
if (F.isExternal()) return;
DSGraph &G = getOrCreateDSGraph(F);
if (Visited.count(&G)) return;
@@ -177,13 +174,11 @@ void TDDataStructures::ComputePostOrder(Function &F,hash_set<DSGraph*> &Visited,
// Recursively traverse all of the callee graphs.
for (DSGraph::fc_iterator CI = G.fc_begin(), E = G.fc_end(); CI != E; ++CI) {
Instruction *CallI = CI->getCallSite().getInstruction();
- std::pair<BUDataStructures::ActualCalleesTy::const_iterator,
- BUDataStructures::ActualCalleesTy::const_iterator>
- IP = ActualCallees.equal_range(CallI);
+ BUDataStructures::ActualCalleesTy::const_iterator I =
+ BUInfo->callee_begin(CallI), E = BUInfo->callee_end(CallI);
- for (BUDataStructures::ActualCalleesTy::const_iterator I = IP.first;
- I != IP.second; ++I)
- ComputePostOrder(*I->second, Visited, PostOrder, ActualCallees);
+ for (; I != E; ++I)
+ ComputePostOrder(*I->second, Visited, PostOrder);
}
PostOrder.push_back(&G);
@@ -315,9 +310,6 @@ void TDDataStructures::InlineCallersIntoGraph(DSGraph &DSG) {
// callee graphs.
if (DSG.fc_begin() == DSG.fc_end()) return;
- const BUDataStructures::ActualCalleesTy &ActualCallees =
- getAnalysis<BUDataStructures>().getActualCallees();
-
// Loop over all the call sites and all the callees at each call site, and add
// edges to the CallerEdges structure for each callee.
for (DSGraph::fc_iterator CI = DSG.fc_begin(), E = DSG.fc_end();
@@ -334,27 +326,26 @@ void TDDataStructures::InlineCallersIntoGraph(DSGraph &DSG) {
Instruction *CallI = CI->getCallSite().getInstruction();
// For each function in the invoked function list at this call site...
- std::pair<BUDataStructures::ActualCalleesTy::const_iterator,
- BUDataStructures::ActualCalleesTy::const_iterator>
- IP = ActualCallees.equal_range(CallI);
+ BUDataStructures::ActualCalleesTy::const_iterator IPI =
+ BUInfo->callee_begin(CallI), IPE = BUInfo->callee_end(CallI);
// Skip over all calls to this graph (SCC calls).
- while (IP.first != IP.second && &getDSGraph(*IP.first->second) == &DSG)
- ++IP.first;
+ while (IPI != IPE && &getDSGraph(*IPI->second) == &DSG)
+ ++IPI;
// All SCC calls?
- if (IP.first == IP.second) continue;
+ if (IPI == IPE) continue;
- Function *FirstCallee = IP.first->second;
- ++IP.first;
+ Function *FirstCallee = IPI->second;
+ ++IPI;
// Skip over more SCC calls.
- while (IP.first != IP.second && &getDSGraph(*IP.first->second) == &DSG)
- ++IP.first;
+ while (IPI != IPE && &getDSGraph(*IPI->second) == &DSG)
+ ++IPI;
// If there is exactly one callee from this call site, remember the edge in
// CallerEdges.
- if (IP.first == IP.second) {
+ if (IPI == IPE) {
if (!FirstCallee->isExternal())
CallerEdges[&getDSGraph(*FirstCallee)]
.push_back(CallerCallEdge(&DSG, &*CI, FirstCallee));
@@ -367,9 +358,9 @@ void TDDataStructures::InlineCallersIntoGraph(DSGraph &DSG) {
// so we build up a new, private, graph that represents the calls of all
// calls to this set of functions.
std::vector<Function*> Callees;
- IP = ActualCallees.equal_range(CallI);
- for (BUDataStructures::ActualCalleesTy::const_iterator I = IP.first;
- I != IP.second; ++I)
+ for (BUDataStructures::ActualCalleesTy::const_iterator I =
+ BUInfo->callee_begin(CallI), E = BUInfo->callee_end(CallI);
+ I != E; ++I)
if (!I->second->isExternal())
Callees.push_back(I->second);
std::sort(Callees.begin(), Callees.end());