diff options
| -rw-r--r-- | lib/Analysis/DataStructure/CompleteBottomUp.cpp | 45 | ||||
| -rw-r--r-- | lib/Analysis/DataStructure/DataStructure.cpp | 2 | ||||
| -rw-r--r-- | lib/Analysis/DataStructure/EquivClassGraphs.cpp | 8 | ||||
| -rw-r--r-- | lib/Analysis/DataStructure/Steensgaard.cpp | 8 | ||||
| -rw-r--r-- | lib/Analysis/DataStructure/TopDownClosure.cpp | 55 |
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()); |