aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--lib/Analysis/DataStructure/BottomUpClosure.cpp11
-rw-r--r--lib/Analysis/DataStructure/CompleteBottomUp.cpp4
-rw-r--r--lib/Analysis/DataStructure/DataStructure.cpp42
-rw-r--r--lib/Analysis/DataStructure/EquivClassGraphs.cpp5
-rw-r--r--lib/Analysis/DataStructure/Local.cpp43
-rw-r--r--lib/Analysis/DataStructure/Steensgaard.cpp8
-rw-r--r--lib/Analysis/DataStructure/TopDownClosure.cpp7
7 files changed, 72 insertions, 48 deletions
diff --git a/lib/Analysis/DataStructure/BottomUpClosure.cpp b/lib/Analysis/DataStructure/BottomUpClosure.cpp
index 7ab7d80..1903008 100644
--- a/lib/Analysis/DataStructure/BottomUpClosure.cpp
+++ b/lib/Analysis/DataStructure/BottomUpClosure.cpp
@@ -37,7 +37,9 @@ using namespace DS;
//
bool BUDataStructures::runOnModule(Module &M) {
LocalDataStructures &LocalDSA = getAnalysis<LocalDataStructures>();
- GlobalsGraph = new DSGraph(LocalDSA.getGlobalsGraph());
+ GlobalECs = LocalDSA.getGlobalECs();
+
+ GlobalsGraph = new DSGraph(LocalDSA.getGlobalsGraph(), GlobalECs);
GlobalsGraph->setPrintAuxCalls();
IndCallGraphMap = new std::map<std::vector<Function*>,
@@ -112,7 +114,8 @@ DSGraph &BUDataStructures::getOrCreateGraph(Function *F) {
if (Graph) return *Graph;
// Copy the local version into DSInfo...
- Graph = new DSGraph(getAnalysis<LocalDataStructures>().getDSGraph(*F));
+ Graph = new DSGraph(getAnalysis<LocalDataStructures>().getDSGraph(*F),
+ GlobalECs);
Graph->setGlobalsGraph(GlobalsGraph);
Graph->setPrintAuxCalls();
@@ -379,7 +382,7 @@ void BUDataStructures::calculateGraph(DSGraph &Graph) {
E = CalledFuncs.end();
// Start with a copy of the first graph.
- GI = IndCallGraph.first = new DSGraph(getDSGraph(**I));
+ GI = IndCallGraph.first = new DSGraph(getDSGraph(**I), GlobalECs);
GI->setGlobalsGraph(Graph.getGlobalsGraph());
std::vector<DSNodeHandle> &Args = IndCallGraph.second;
@@ -498,7 +501,7 @@ void BUDataStructures::copyValue(Value *From, Value *To) {
if (Function *FromF = dyn_cast<Function>(From)) {
Function *ToF = cast<Function>(To);
assert(!DSInfo.count(ToF) && "New Function already exists!");
- DSGraph *NG = new DSGraph(getDSGraph(*FromF));
+ DSGraph *NG = new DSGraph(getDSGraph(*FromF), GlobalECs);
DSInfo[ToF] = NG;
assert(NG->getReturnNodes().size() == 1 && "Cannot copy SCC's yet!");
diff --git a/lib/Analysis/DataStructure/CompleteBottomUp.cpp b/lib/Analysis/DataStructure/CompleteBottomUp.cpp
index a70080a..16ea438 100644
--- a/lib/Analysis/DataStructure/CompleteBottomUp.cpp
+++ b/lib/Analysis/DataStructure/CompleteBottomUp.cpp
@@ -34,7 +34,7 @@ namespace {
//
bool CompleteBUDataStructures::runOnModule(Module &M) {
BUDataStructures &BU = getAnalysis<BUDataStructures>();
- GlobalsGraph = new DSGraph(BU.getGlobalsGraph());
+ GlobalsGraph = new DSGraph(BU.getGlobalsGraph(), GlobalECs);
GlobalsGraph->setPrintAuxCalls();
#if 1 // REMOVE ME EVENTUALLY
@@ -121,7 +121,7 @@ DSGraph &CompleteBUDataStructures::getOrCreateGraph(Function &F) {
if (Graph) return *Graph;
// Copy the BU graph...
- Graph = new DSGraph(getAnalysis<BUDataStructures>().getDSGraph(F));
+ Graph = new DSGraph(getAnalysis<BUDataStructures>().getDSGraph(F), GlobalECs);
Graph->setGlobalsGraph(GlobalsGraph);
Graph->setPrintAuxCalls();
diff --git a/lib/Analysis/DataStructure/DataStructure.cpp b/lib/Analysis/DataStructure/DataStructure.cpp
index 43170fd..5f8b3bf 100644
--- a/lib/Analysis/DataStructure/DataStructure.cpp
+++ b/lib/Analysis/DataStructure/DataStructure.cpp
@@ -115,7 +115,7 @@ void DSNode::assertOK() const {
assert(ParentGraph && "Node has no parent?");
const DSScalarMap &SM = ParentGraph->getScalarMap();
for (unsigned i = 0, e = Globals.size(); i != e; ++i) {
- assert(SM.count(Globals[i]));
+ assert(SM.global_count(Globals[i]));
assert(SM.find(Globals[i])->second.getNode() == this);
}
}
@@ -143,6 +143,10 @@ void DSNode::forwardNode(DSNode *To, unsigned Offset) {
// marks the node with the 'G' flag if it does not already have it.
//
void DSNode::addGlobal(GlobalValue *GV) {
+ // First, check to make sure this is the leader if the global is in an
+ // equivalence class.
+ GV = getParentGraph()->getScalarMap().getLeaderForGlobal(GV);
+
// Keep the list sorted.
std::vector<GlobalValue*>::iterator I =
std::lower_bound(Globals.begin(), Globals.end(), GV);
@@ -1091,14 +1095,16 @@ std::string DSGraph::getFunctionNames() const {
}
-DSGraph::DSGraph(const DSGraph &G) : GlobalsGraph(0), TD(G.TD) {
+DSGraph::DSGraph(const DSGraph &G, EquivalenceClasses<GlobalValue*> &ECs)
+ : GlobalsGraph(0), ScalarMap(ECs), TD(G.TD) {
PrintAuxCalls = false;
NodeMapTy NodeMap;
cloneInto(G, ScalarMap, ReturnNodes, NodeMap);
}
-DSGraph::DSGraph(const DSGraph &G, NodeMapTy &NodeMap)
- : GlobalsGraph(0), TD(G.TD) {
+DSGraph::DSGraph(const DSGraph &G, NodeMapTy &NodeMap,
+ EquivalenceClasses<GlobalValue*> &ECs)
+ : GlobalsGraph(0), ScalarMap(ECs), TD(G.TD) {
PrintAuxCalls = false;
cloneInto(G, ScalarMap, ReturnNodes, NodeMap);
}
@@ -1865,8 +1871,9 @@ void DSGraph::removeDeadNodes(unsigned Flags) {
DSGraph::StripIncompleteBit);
// Mark all nodes reachable by (non-global) scalar nodes as alive...
- { TIME_REGION(Y, "removeDeadNodes:scalarscan");
- for (DSScalarMap::iterator I = ScalarMap.begin(), E = ScalarMap.end(); I !=E;)
+{ TIME_REGION(Y, "removeDeadNodes:scalarscan");
+ for (DSScalarMap::iterator I = ScalarMap.begin(), E = ScalarMap.end();
+ I != E; ++I)
if (isa<GlobalValue>(I->first)) { // Keep track of global nodes
assert(!I->second.isNull() && "Null global node?");
assert(I->second.getNode()->isGlobalNode() && "Should be a global node!");
@@ -1881,29 +1888,10 @@ void DSGraph::removeDeadNodes(unsigned Flags) {
else
GGCloner.getClonedNH(I->second);
}
- ++I;
} else {
- DSNode *N = I->second.getNode();
-#if 0
- // Check to see if this is a worthless node generated for non-pointer
- // values, such as integers. Consider an addition of long types: A+B.
- // Assuming we can track all uses of the value in this context, and it is
- // NOT used as a pointer, we can delete the node. We will be able to
- // detect this situation if the node pointed to ONLY has Unknown bit set
- // in the node. In this case, the node is not incomplete, does not point
- // to any other nodes (no mod/ref bits set), and is therefore
- // uninteresting for data structure analysis. If we run across one of
- // these, prune the scalar pointing to it.
- //
- if (N->getNodeFlags() == DSNode::UnknownNode && !isa<Argument>(I->first))
- ScalarMap.erase(I++);
- else {
-#endif
- N->markReachableNodes(Alive);
- ++I;
- //}
+ I->second.getNode()->markReachableNodes(Alive);
}
- }
+}
// The return values are alive as well.
for (ReturnNodesTy::iterator I = ReturnNodes.begin(), E = ReturnNodes.end();
diff --git a/lib/Analysis/DataStructure/EquivClassGraphs.cpp b/lib/Analysis/DataStructure/EquivClassGraphs.cpp
index 02b7fb7..447b36d 100644
--- a/lib/Analysis/DataStructure/EquivClassGraphs.cpp
+++ b/lib/Analysis/DataStructure/EquivClassGraphs.cpp
@@ -72,9 +72,10 @@ Function *EquivClassGraphs::getSomeCalleeForCallSite(const CallSite &CS) const{
//
bool EquivClassGraphs::runOnModule(Module &M) {
CBU = &getAnalysis<CompleteBUDataStructures>();
+ GlobalECs = CBU->getGlobalECs();
DEBUG(CheckAllGraphs(&M, *CBU));
- GlobalsGraph = new DSGraph(CBU->getGlobalsGraph());
+ GlobalsGraph = new DSGraph(CBU->getGlobalsGraph(), GlobalECs);
GlobalsGraph->setPrintAuxCalls();
ActualCallees = CBU->getActualCallees();
@@ -305,7 +306,7 @@ DSGraph &EquivClassGraphs::getOrCreateGraph(Function &F) {
DSGraph &CBUGraph = CBU->getDSGraph(F);
// Copy the CBU graph...
- Graph = new DSGraph(CBUGraph); // updates the map via reference
+ Graph = new DSGraph(CBUGraph, GlobalECs); // updates the map via reference
Graph->setGlobalsGraph(&getGlobalsGraph());
Graph->setPrintAuxCalls();
diff --git a/lib/Analysis/DataStructure/Local.cpp b/lib/Analysis/DataStructure/Local.cpp
index 9cb899c..02b5b16 100644
--- a/lib/Analysis/DataStructure/Local.cpp
+++ b/lib/Analysis/DataStructure/Local.cpp
@@ -164,8 +164,9 @@ using namespace DS;
//===----------------------------------------------------------------------===//
// DSGraph constructor - Simply use the GraphBuilder to construct the local
// graph.
-DSGraph::DSGraph(const TargetData &td, Function &F, DSGraph *GG)
- : GlobalsGraph(GG), TD(td) {
+DSGraph::DSGraph(EquivalenceClasses<GlobalValue*> &ECs, const TargetData &td,
+ Function &F, DSGraph *GG)
+ : GlobalsGraph(GG), ScalarMap(ECs), TD(td) {
PrintAuxCalls = false;
DEBUG(std::cerr << " [Loc] Calculating graph for: " << F.getName() << "\n");
@@ -1071,21 +1072,49 @@ void GraphBuilder::mergeInGlobalInitializer(GlobalVariable *GV) {
bool LocalDataStructures::runOnModule(Module &M) {
const TargetData &TD = getAnalysis<TargetData>();
- GlobalsGraph = new DSGraph(TD);
-
+ // First step, build the globals graph.
+ GlobalsGraph = new DSGraph(GlobalECs, TD);
{
GraphBuilder GGB(*GlobalsGraph);
- // Add initializers for all of the globals to the globals graph...
- for (Module::global_iterator I = M.global_begin(), E = M.global_end(); I != E; ++I)
+ // Add initializers for all of the globals to the globals graph.
+ for (Module::global_iterator I = M.global_begin(), E = M.global_end();
+ I != E; ++I)
if (!I->isExternal())
GGB.mergeInGlobalInitializer(I);
}
+ // Next step, iterate through the nodes in the globals graph, unioning
+ // together the globals into equivalence classes.
+ for (DSGraph::node_iterator I = GlobalsGraph->node_begin(),
+ E = GlobalsGraph->node_end(); I != E; ++I)
+ if (I->getGlobals().size() > 1) {
+ // First, build up the equivalence set for this block of globals.
+ const std::vector<GlobalValue*> &GVs = I->getGlobals();
+ GlobalValue *First = GVs[0];
+ for (unsigned i = 1, e = GVs.size(); i != e; ++i)
+ GlobalECs.unionSets(First, GVs[i]);
+
+ // Next, get the leader element.
+ First = GlobalECs.getLeaderValue(First);
+
+ // Next, remove all globals from the scalar map that are not the leader.
+ DSScalarMap &SM = GlobalsGraph->getScalarMap();
+ for (unsigned i = 0, e = GVs.size(); i != e; ++i)
+ if (GVs[i] != First)
+ SM.erase(SM.find(GVs[i]));
+
+ // Finally, change the global node to only contain the leader.
+ I->clearGlobals();
+ I->addGlobal(First);
+ }
+ DEBUG(GlobalsGraph->AssertGraphOK());
+
// Calculate all of the graphs...
for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
if (!I->isExternal())
- DSInfo.insert(std::make_pair(I, new DSGraph(TD, *I, GlobalsGraph)));
+ DSInfo.insert(std::make_pair(I, new DSGraph(GlobalECs, TD, *I,
+ GlobalsGraph)));
GlobalsGraph->removeTriviallyDeadNodes();
GlobalsGraph->markIncompleteNodes(DSGraph::MarkFormalArgs);
diff --git a/lib/Analysis/DataStructure/Steensgaard.cpp b/lib/Analysis/DataStructure/Steensgaard.cpp
index dd07ee6..9ed65bb 100644
--- a/lib/Analysis/DataStructure/Steensgaard.cpp
+++ b/lib/Analysis/DataStructure/Steensgaard.cpp
@@ -26,6 +26,8 @@ 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() {
@@ -112,8 +114,8 @@ bool Steens::runOnModule(Module &M) {
LocalDataStructures &LDS = getAnalysis<LocalDataStructures>();
// Create a new, empty, graph...
- ResultGraph = new DSGraph(getTargetData());
- GlobalsGraph = new DSGraph(getTargetData());
+ ResultGraph = new DSGraph(GlobalECs, getTargetData());
+ GlobalsGraph = new DSGraph(GlobalECs, getTargetData());
ResultGraph->setGlobalsGraph(GlobalsGraph);
ResultGraph->setPrintAuxCalls();
@@ -128,7 +130,7 @@ bool Steens::runOnModule(Module &M) {
unsigned Count = 0;
for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
if (!I->isExternal()) {
- DSGraph::ScalarMapTy ValMap;
+ DSGraph::ScalarMapTy ValMap(GlobalECs);
{ // Scope to free NodeMap memory ASAP
DSGraph::NodeMapTy NodeMap;
const DSGraph &FDSG = LDS.getDSGraph(*I);
diff --git a/lib/Analysis/DataStructure/TopDownClosure.cpp b/lib/Analysis/DataStructure/TopDownClosure.cpp
index 580f228..9a661e2 100644
--- a/lib/Analysis/DataStructure/TopDownClosure.cpp
+++ b/lib/Analysis/DataStructure/TopDownClosure.cpp
@@ -53,7 +53,8 @@ void TDDataStructures::markReachableFunctionsExternallyAccessible(DSNode *N,
//
bool TDDataStructures::runOnModule(Module &M) {
BUDataStructures &BU = getAnalysis<BUDataStructures>();
- GlobalsGraph = new DSGraph(BU.getGlobalsGraph());
+ GlobalECs = BU.getGlobalECs();
+ GlobalsGraph = new DSGraph(BU.getGlobalsGraph(), GlobalECs);
GlobalsGraph->setPrintAuxCalls();
// Figure out which functions must not mark their arguments complete because
@@ -115,7 +116,7 @@ bool TDDataStructures::runOnModule(Module &M) {
DSGraph &TDDataStructures::getOrCreateDSGraph(Function &F) {
DSGraph *&G = DSInfo[&F];
if (G == 0) { // Not created yet? Clone BU graph...
- G = new DSGraph(getAnalysis<BUDataStructures>().getDSGraph(F));
+ G = new DSGraph(getAnalysis<BUDataStructures>().getDSGraph(F), GlobalECs);
G->getAuxFunctionCalls().clear();
G->setPrintAuxCalls();
G->setGlobalsGraph(GlobalsGraph);
@@ -324,7 +325,7 @@ void TDDataStructures::copyValue(Value *From, Value *To) {
if (Function *FromF = dyn_cast<Function>(From)) {
Function *ToF = cast<Function>(To);
assert(!DSInfo.count(ToF) && "New Function already exists!");
- DSGraph *NG = new DSGraph(getDSGraph(*FromF));
+ DSGraph *NG = new DSGraph(getDSGraph(*FromF), GlobalECs);
DSInfo[ToF] = NG;
assert(NG->getReturnNodes().size() == 1 && "Cannot copy SCC's yet!");
generated by cgit v1.1 at 2025-06-01 18:26:30 +0000