//===- TopDownClosure.cpp - Compute the top-down interprocedure 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 TDDataStructures class, which represents the
#include "llvm/Support/Debug.h"
#include "llvm/Support/Timer.h"
#include "llvm/ADT/Statistic.h"
+#include <iostream>
using namespace llvm;
#if 0
#endif
namespace {
- RegisterAnalysis<TDDataStructures> // Register the pass
+ RegisterPass<TDDataStructures> // Register the pass
Y("tddatastructure", "Top-down Data Structure Analysis");
Statistic<> NumTDInlines("tddatastructures", "Number of graphs inlined");
// 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
// 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");
for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
if (!I->isExternal())
getOrCreateDSGraph(*I);
+ return false;
}
-//return false;
#endif
// 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!
}
delete IndCallMap.begin()->second;
IndCallMap.erase(IndCallMap.begin());
}
-
+
ArgsRemainIncomplete.clear();
GlobalsGraph->removeTriviallyDeadNodes();
assert(G->getAuxFunctionCalls().empty() && "Cloned aux calls?");
G->setPrintAuxCalls();
G->setGlobalsGraph(GlobalsGraph);
+
+ // Note that this graph is the graph for ALL of the function in the SCC, not
+ // just F.
+ for (DSGraph::retnodes_iterator RI = G->retnodes_begin(),
+ E = G->retnodes_end(); RI != E; ++RI)
+ if (RI->first != &F)
+ DSInfo[RI->first] = G;
}
return *G;
}
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;
Visited.insert(&G);
-
+
// Recursively traverse all of the callee graphs.
- for (DSGraph::fc_iterator CI = G.fc_begin(), E = G.fc_end(); CI != E; ++CI) {
+ for (DSGraph::fc_iterator CI = G.fc_begin(), CE = G.fc_end(); CI != CE; ++CI){
Instruction *CallI = CI->getCallSite().getInstruction();
- std::pair<BUDataStructures::ActualCalleesTy::const_iterator,
- BUDataStructures::ActualCalleesTy::const_iterator>
- IP = ActualCallees.equal_range(CallI);
-
- for (BUDataStructures::ActualCalleesTy::const_iterator I = IP.first;
- I != IP.second; ++I)
- ComputePostOrder(*I->second, Visited, PostOrder, ActualCallees);
+ for (BUDataStructures::callee_iterator I = BUInfo->callee_begin(CallI),
+ E = BUInfo->callee_end(CallI); I != E; ++I)
+ ComputePostOrder(*I->second, Visited, PostOrder);
}
PostOrder.push_back(&G);
// sites that call into this graph.
std::vector<CallerCallEdge> EdgesFromCaller;
std::map<DSGraph*, std::vector<CallerCallEdge> >::iterator
- CEI = CallerEdges.find(&DSG);
+ CEI = CallerEdges.find(&DSG);
if (CEI != CallerEdges.end()) {
std::swap(CEI->second, EdgesFromCaller);
CallerEdges.erase(CEI);
}
-
+
// Sort the caller sites to provide a by-caller-graph ordering.
std::sort(EdgesFromCaller.begin(), EdgesFromCaller.end());
getParent()->getParent()->getName() << "'");
DEBUG(std::cerr << ": " << CF.getFunctionType()->getNumParams()
<< " args\n");
-
+
// Get the formal argument and return nodes for the called function and
// merge them with the cloned subgraph.
DSCallSite T1 = DSG.getCallSiteForArguments(CF);
// 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();
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::callee_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));
// 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());
// If we already have this graph, recycle it.
if (IndCallRecI != IndCallMap.end() && IndCallRecI->first == Callees) {
- std::cerr << " [TD] *** Reuse of indcall graph for " << Callees.size()
- << " callees!\n";
+ DEBUG(std::cerr << " [TD] *** Reuse of indcall graph for " << Callees.size()
+ << " callees!\n");
IndCallGraph = IndCallRecI->second;
} else {
// Otherwise, create a new DSGraph to represent this.
return;
}
- assert(!isa<GlobalVariable>(From) && "Do not know how to copy GV's yet!");
+ if (const Function *F = getFnForValue(To)) {
+ DSGraph &G = getDSGraph(*F);
+ G.getScalarMap().copyScalarIfExists(From, To);
+ return;
+ }
+
+ std::cerr << *From;
+ std::cerr << *To;
+ assert(0 && "Do not know how to copy this yet!");
+ abort();
}