aboutsummaryrefslogtreecommitdiffstats
path: root/lib/Analysis/DataStructure
diff options
context:
space:
mode:
Diffstat (limited to 'lib/Analysis/DataStructure')
-rw-r--r--lib/Analysis/DataStructure/DataStructure.cpp14
-rw-r--r--lib/Analysis/DataStructure/EliminateNodes.cpp61
-rw-r--r--lib/Analysis/DataStructure/FunctionRepBuilder.cpp15
-rw-r--r--lib/Analysis/DataStructure/FunctionRepBuilder.h14
-rw-r--r--lib/Analysis/DataStructure/NodeImpl.cpp35
5 files changed, 75 insertions, 64 deletions
diff --git a/lib/Analysis/DataStructure/DataStructure.cpp b/lib/Analysis/DataStructure/DataStructure.cpp
index 8d53b41..923bca5 100644
--- a/lib/Analysis/DataStructure/DataStructure.cpp
+++ b/lib/Analysis/DataStructure/DataStructure.cpp
@@ -8,6 +8,7 @@
#include "llvm/Module.h"
#include <fstream>
#include <algorithm>
+#include <iostream>
//===----------------------------------------------------------------------===//
// DataStructure Class Implementation
@@ -46,7 +47,7 @@ void DataStructure::print(std::ostream &O, Module *M) const {
getClosedDSGraph(I);
}
gettimeofday(&TV2, 0);
- cerr << "Analysis took "
+ std::cerr << "Analysis took "
<< (TV2.tv_sec-TV1.tv_sec)*1000000+(TV2.tv_usec-TV1.tv_usec)
<< " microseconds.\n";
}
@@ -54,9 +55,10 @@ void DataStructure::print(std::ostream &O, Module *M) const {
for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I)
if (!I->isExternal()) {
- string Filename = "ds." + I->getName() + ".dot";
+ std::string Filename = "ds." + I->getName() + ".dot";
O << "Writing '" << Filename << "'...";
- ofstream F(Filename.c_str());
+ std::ofstream F(Filename.c_str());
+
if (F.good()) {
F << "digraph DataStructures {\n"
<< "\tnode [shape=Mrecord];\n"
@@ -121,7 +123,7 @@ bool PointerValSet::operator<(const PointerValSet &PVS) const {
if (Vals.size() > PVS.Vals.size()) return false;
if (Vals.size() == 1) return Vals[0] < PVS.Vals[0]; // Most common case
- vector<PointerVal> S1(Vals), S2(PVS.Vals);
+ std::vector<PointerVal> S1(Vals), S2(PVS.Vals);
sort(S1.begin(), S1.end());
sort(S2.begin(), S2.end());
return S1 < S2;
@@ -131,7 +133,7 @@ bool PointerValSet::operator==(const PointerValSet &PVS) const {
if (Vals.size() != PVS.Vals.size()) return false;
if (Vals.size() == 1) return Vals[0] == PVS.Vals[0]; // Most common case...
- vector<PointerVal> S1(Vals), S2(PVS.Vals);
+ std::vector<PointerVal> S1(Vals), S2(PVS.Vals);
sort(S1.begin(), S1.end());
sort(S2.begin(), S2.end());
return S1 == S2;
@@ -150,7 +152,7 @@ bool PointerValSet::add(const PointerVal &PV, Value *Pointer) {
// removePointerTo - Remove a single pointer val that points to the specified
// node...
void PointerValSet::removePointerTo(DSNode *Node) {
- vector<PointerVal>::iterator I = std::find(Vals.begin(), Vals.end(), Node);
+ std::vector<PointerVal>::iterator I = std::find(Vals.begin(), Vals.end(), Node);
assert(I != Vals.end() && "Couldn't remove nonexistent edge!");
Vals.erase(I);
Node->removeReferrer(this);
diff --git a/lib/Analysis/DataStructure/EliminateNodes.cpp b/lib/Analysis/DataStructure/EliminateNodes.cpp
index 8a4ee82..06385d4 100644
--- a/lib/Analysis/DataStructure/EliminateNodes.cpp
+++ b/lib/Analysis/DataStructure/EliminateNodes.cpp
@@ -19,13 +19,14 @@
#include "llvm/Value.h"
#include "Support/STLExtras.h"
#include <algorithm>
+#include <iostream>
//#define DEBUG_NODE_ELIMINATE 1
static void DestroyFirstNodeOfPair(DSNode *N1, DSNode *N2) {
#ifdef DEBUG_NODE_ELIMINATE
- cerr << "Found Indistinguishable Node:\n";
- N1->print(cerr);
+ std::cerr << "Found Indistinguishable Node:\n";
+ N1->print(std::cerr);
#endif
// The nodes can be merged. Make sure that N2 contains all of the
@@ -177,16 +178,16 @@ bool FunctionDSGraph::UnlinkUndistinguishableNodes() {
}
static void MarkReferredNodesReachable(DSNode *N,
- vector<ShadowDSNode*> &ShadowNodes,
- vector<bool> &ReachableShadowNodes,
- vector<AllocDSNode*> &AllocNodes,
- vector<bool> &ReachableAllocNodes);
+ std::vector<ShadowDSNode*> &ShadowNodes,
+ std::vector<bool> &ReachableShadowNodes,
+ std::vector<AllocDSNode*> &AllocNodes,
+ std::vector<bool> &ReachableAllocNodes);
static inline void MarkReferredNodeSetReachable(const PointerValSet &PVS,
- vector<ShadowDSNode*> &ShadowNodes,
- vector<bool> &ReachableShadowNodes,
- vector<AllocDSNode*> &AllocNodes,
- vector<bool> &ReachableAllocNodes) {
+ std::vector<ShadowDSNode*> &ShadowNodes,
+ std::vector<bool> &ReachableShadowNodes,
+ std::vector<AllocDSNode*> &AllocNodes,
+ std::vector<bool> &ReachableAllocNodes) {
for (unsigned i = 0, e = PVS.size(); i != e; ++i)
if (isa<ShadowDSNode>(PVS[i].Node) || isa<AllocDSNode>(PVS[i].Node))
MarkReferredNodesReachable(PVS[i].Node, ShadowNodes, ReachableShadowNodes,
@@ -194,21 +195,21 @@ static inline void MarkReferredNodeSetReachable(const PointerValSet &PVS,
}
static void MarkReferredNodesReachable(DSNode *N,
- vector<ShadowDSNode*> &ShadowNodes,
- vector<bool> &ReachableShadowNodes,
- vector<AllocDSNode*> &AllocNodes,
- vector<bool> &ReachableAllocNodes) {
+ std::vector<ShadowDSNode*> &ShadowNodes,
+ std::vector<bool> &ReachableShadowNodes,
+ std::vector<AllocDSNode*> &AllocNodes,
+ std::vector<bool> &ReachableAllocNodes) {
assert(ShadowNodes.size() == ReachableShadowNodes.size());
assert(AllocNodes.size() == ReachableAllocNodes.size());
if (ShadowDSNode *Shad = dyn_cast<ShadowDSNode>(N)) {
- vector<ShadowDSNode*>::iterator I =
+ std::vector<ShadowDSNode*>::iterator I =
std::find(ShadowNodes.begin(), ShadowNodes.end(), Shad);
unsigned i = I-ShadowNodes.begin();
if (ReachableShadowNodes[i]) return; // Recursion detected, abort...
ReachableShadowNodes[i] = true;
} else if (AllocDSNode *Alloc = dyn_cast<AllocDSNode>(N)) {
- vector<AllocDSNode*>::iterator I =
+ std::vector<AllocDSNode*>::iterator I =
std::find(AllocNodes.begin(), AllocNodes.end(), Alloc);
unsigned i = I-AllocNodes.begin();
if (ReachableAllocNodes[i]) return; // Recursion detected, abort...
@@ -229,8 +230,8 @@ static void MarkReferredNodesReachable(DSNode *N,
}
void FunctionDSGraph::MarkEscapeableNodesReachable(
- vector<bool> &ReachableShadowNodes,
- vector<bool> &ReachableAllocNodes) {
+ std::vector<bool> &ReachableShadowNodes,
+ std::vector<bool> &ReachableAllocNodes) {
// Mark all shadow nodes that have edges from other nodes as reachable.
// Recursively mark any shadow nodes pointed to by the newly live shadow
// nodes as also alive.
@@ -260,8 +261,8 @@ bool FunctionDSGraph::RemoveUnreachableNodes() {
// Reachable*Nodes - Contains true if there is an edge from a reachable
// node to the numbered node...
//
- vector<bool> ReachableShadowNodes(ShadowNodes.size());
- vector<bool> ReachableAllocNodes (AllocNodes.size());
+ std::vector<bool> ReachableShadowNodes(ShadowNodes.size());
+ std::vector<bool> ReachableAllocNodes (AllocNodes.size());
MarkEscapeableNodesReachable(ReachableShadowNodes, ReachableAllocNodes);
@@ -282,8 +283,8 @@ bool FunctionDSGraph::RemoveUnreachableNodes() {
if (!ReachableShadowNodes[i]) {
// Track all unreachable nodes...
#if DEBUG_NODE_ELIMINATE
- cerr << "Unreachable node eliminated:\n";
- ShadowNodes[i]->print(cerr);
+ std::cerr << "Unreachable node eliminated:\n";
+ ShadowNodes[i]->print(std::cerr);
#endif
ShadowNodes[i]->removeAllIncomingEdges();
delete ShadowNodes[i];
@@ -299,8 +300,8 @@ bool FunctionDSGraph::RemoveUnreachableNodes() {
if (!ReachableAllocNodes[i]) {
// Track all unreachable nodes...
#if DEBUG_NODE_ELIMINATE
- cerr << "Unreachable node eliminated:\n";
- AllocNodes[i]->print(cerr);
+ std::cerr << "Unreachable node eliminated:\n";
+ AllocNodes[i]->print(std::cerr);
#endif
AllocNodes[i]->removeAllIncomingEdges();
delete AllocNodes[i];
@@ -346,9 +347,9 @@ bool FunctionDSGraph::RemoveUnreachableNodes() {
// getEscapingAllocations - Add all allocations that escape the current
// function to the specified vector.
//
-void FunctionDSGraph::getEscapingAllocations(vector<AllocDSNode*> &Allocs) {
- vector<bool> ReachableShadowNodes(ShadowNodes.size());
- vector<bool> ReachableAllocNodes (AllocNodes.size());
+void FunctionDSGraph::getEscapingAllocations(std::vector<AllocDSNode*> &Allocs) {
+ std::vector<bool> ReachableShadowNodes(ShadowNodes.size());
+ std::vector<bool> ReachableAllocNodes (AllocNodes.size());
MarkEscapeableNodesReachable(ReachableShadowNodes, ReachableAllocNodes);
@@ -360,9 +361,9 @@ void FunctionDSGraph::getEscapingAllocations(vector<AllocDSNode*> &Allocs) {
// getNonEscapingAllocations - Add all allocations that do not escape the
// current function to the specified vector.
//
-void FunctionDSGraph::getNonEscapingAllocations(vector<AllocDSNode*> &Allocs) {
- vector<bool> ReachableShadowNodes(ShadowNodes.size());
- vector<bool> ReachableAllocNodes (AllocNodes.size());
+void FunctionDSGraph::getNonEscapingAllocations(std::vector<AllocDSNode*> &Allocs) {
+ std::vector<bool> ReachableShadowNodes(ShadowNodes.size());
+ std::vector<bool> ReachableAllocNodes (AllocNodes.size());
MarkEscapeableNodesReachable(ReachableShadowNodes, ReachableAllocNodes);
diff --git a/lib/Analysis/DataStructure/FunctionRepBuilder.cpp b/lib/Analysis/DataStructure/FunctionRepBuilder.cpp
index 1282d7a..f90ab9b 100644
--- a/lib/Analysis/DataStructure/FunctionRepBuilder.cpp
+++ b/lib/Analysis/DataStructure/FunctionRepBuilder.cpp
@@ -15,6 +15,7 @@
#include "llvm/Constants.h"
#include "Support/STLExtras.h"
#include <algorithm>
+#include <iostream>
// synthesizeNode - Create a new shadow node that is to be linked into this
// chain..
@@ -32,8 +33,10 @@ ShadowDSNode *DSNode::synthesizeNode(const Type *Ty,
if (SynthNodes[i].first == Ty) return SynthNodes[i].second;
// No we haven't. Do so now and add it to our list of saved nodes...
+
ShadowDSNode *SN = Rep->makeSynthesizedShadow(Ty, this);
- SynthNodes.push_back(make_pair(Ty, SN));
+ SynthNodes.push_back(std::make_pair(Ty, SN));
+
return SN;
}
@@ -281,10 +284,10 @@ void FunctionRepBuilder::visitStoreInst(StoreInst &SI) {
PointerVal Dest = getIndexedPointerDest(PtrPVS[pi], SI);
#if 0
- cerr << "Setting Dest:\n";
- Dest.print(cerr);
- cerr << "to point to Src:\n";
- SrcPtr.print(cerr);
+ std::cerr << "Setting Dest:\n";
+ Dest.print(std::cerr);
+ std::cerr << "to point to Src:\n";
+ SrcPtr.print(std::cerr);
#endif
// Add SrcPtr into the Dest field...
@@ -338,7 +341,7 @@ FunctionDSGraph::FunctionDSGraph(Function *F) : Func(F) {
// at things. They can only point to their node, so there is no use keeping
// them.
//
- for (map<Value*, PointerValSet>::iterator I = ValueMap.begin(),
+ for (std::map<Value*, PointerValSet>::iterator I = ValueMap.begin(),
E = ValueMap.end(); I != E;)
if (isa<GlobalValue>(I->first)) {
#if MAP_DOESNT_HAVE_BROKEN_ERASE_MEMBER
diff --git a/lib/Analysis/DataStructure/FunctionRepBuilder.h b/lib/Analysis/DataStructure/FunctionRepBuilder.h
index 9eedf02..30e0bb2 100644
--- a/lib/Analysis/DataStructure/FunctionRepBuilder.h
+++ b/lib/Analysis/DataStructure/FunctionRepBuilder.h
@@ -10,6 +10,7 @@
#include "llvm/Analysis/DataStructure.h"
#include "llvm/Support/InstVisitor.h"
+#include <iostream>
// DEBUG_DATA_STRUCTURE_CONSTRUCTION - Define this to 1 if you want debug output
//#define DEBUG_DATA_STRUCTURE_CONSTRUCTION 1
@@ -48,12 +49,12 @@ class FunctionRepBuilder : InstVisitor<FunctionRepBuilder> {
// ValueMap - Mapping between values we are processing and the possible
// datastructures that they may point to...
- map<Value*, PointerValSet> ValueMap;
+ std::map<Value*, PointerValSet> ValueMap;
// CallMap - Keep track of which call nodes correspond to which call insns.
// The reverse mapping is stored in the CallDSNodes themselves.
//
- map<CallInst*, CallDSNode*> CallMap;
+ std::map<CallInst*, CallDSNode*> CallMap;
// Worklist - Vector of (pointer typed) instructions to process still...
std::vector<Instruction *> WorkList;
@@ -87,7 +88,7 @@ public:
const PointerValSet &getRetNode() const { return RetNode; }
- const map<Value*, PointerValSet> &getValueMap() const { return ValueMap; }
+ const std::map<Value*, PointerValSet> &getValueMap() const { return ValueMap; }
private:
static PointerVal getIndexedPointerDest(const PointerVal &InP,
const MemAccessInst &MAI);
@@ -97,15 +98,16 @@ private:
// While the worklist still has instructions to process, process them!
while (!WorkList.empty()) {
Instruction *I = WorkList.back(); WorkList.pop_back();
+
#ifdef DEBUG_DATA_STRUCTURE_CONSTRUCTION
- cerr << "Processing worklist inst: " << I;
+ std::cerr << "Processing worklist inst: " << I;
#endif
visit(*I); // Dispatch to a visitXXX function based on instruction type...
#ifdef DEBUG_DATA_STRUCTURE_CONSTRUCTION
if (I->hasName() && ValueMap.count(I)) {
- cerr << "Inst %" << I->getName() << " value is:\n";
- ValueMap[I].print(cerr);
+ std::cerr << "Inst %" << I->getName() << " value is:\n";
+ ValueMap[I].print(std::cerr);
}
#endif
}
diff --git a/lib/Analysis/DataStructure/NodeImpl.cpp b/lib/Analysis/DataStructure/NodeImpl.cpp
index bd279b6..b47b265 100644
--- a/lib/Analysis/DataStructure/NodeImpl.cpp
+++ b/lib/Analysis/DataStructure/NodeImpl.cpp
@@ -13,6 +13,9 @@
#include "Support/STLExtras.h"
#include <algorithm>
#include <sstream>
+#include <iostream>
+using std::map;
+using std::string;
bool AllocDSNode::isEquivalentTo(DSNode *Node) const {
if (AllocDSNode *N = dyn_cast<AllocDSNode>(Node))
@@ -28,7 +31,7 @@ void AllocDSNode::mergeInto(DSNode *Node) const {
}
bool GlobalDSNode::isEquivalentTo(DSNode *Node) const {
- if (GlobalDSNode *G = dyn_cast<GlobalDSNode>(Node)) {
+ if (const GlobalDSNode *G = dyn_cast<GlobalDSNode>(Node)) {
if (G->Val != Val) return false;
// Check that the outgoing links are identical...
@@ -124,8 +127,8 @@ DSNode::DSNode(enum NodeTy NT, const Type *T) : Ty(T), NodeType(NT) {
}
void DSNode::removeReferrer(PointerValSet *PVS) {
- vector<PointerValSet*>::iterator I = std::find(Referrers.begin(),
- Referrers.end(), PVS);
+ std::vector<PointerValSet*>::iterator I = std::find(Referrers.begin(),
+ Referrers.end(), PVS);
assert(I != Referrers.end() && "PVS not pointing to node!");
Referrers.erase(I);
}
@@ -175,14 +178,14 @@ static string escapeLabel(const string &In) {
return Label;
}
-void DSNode::dump() const { print(cerr); }
+void DSNode::dump() const { print(std::cerr); }
void DSNode::print(std::ostream &O) const {
string Caption = escapeLabel(getCaption());
O << "\t\tNode" << (void*)this << " [ label =\"{" << Caption;
- const vector<PointerValSet> *Links = getAuxLinks();
+ const std::vector<PointerValSet> *Links = getAuxLinks();
if (Links && !Links->empty()) {
O << "|{";
for (unsigned i = 0; i < Links->size(); ++i) {
@@ -237,7 +240,7 @@ bool AllocDSNode::isAllocaNode() const {
string AllocDSNode::getCaption() const {
- stringstream OS;
+ std::stringstream OS;
OS << (isMallocNode() ? "new " : "alloca ");
WriteTypeSymbolic(OS, getType(),
@@ -252,7 +255,7 @@ GlobalDSNode::GlobalDSNode(GlobalValue *V)
}
string GlobalDSNode::getCaption() const {
- stringstream OS;
+ std::stringstream OS;
if (isa<Function>(Val))
OS << "fn ";
else
@@ -275,7 +278,7 @@ ShadowDSNode::ShadowDSNode(const Type *Ty, Module *M, DSNode *ShadParent)
}
std::string ShadowDSNode::getCaption() const {
- stringstream OS;
+ std::stringstream OS;
OS << "shadow ";
WriteTypeSymbolic(OS, getType(), Mod);
return OS.str();
@@ -290,7 +293,7 @@ CallDSNode::CallDSNode(CallInst *ci) : DSNode(CallNode, ci->getType()), CI(ci) {
}
string CallDSNode::getCaption() const {
- stringstream OS;
+ std::stringstream OS;
if (const Function *CM = CI->getCalledFunction())
OS << "call " << CM->getName();
else
@@ -334,7 +337,7 @@ void FunctionDSGraph::printFunction(std::ostream &O,
for (std::map<Value*, PointerValSet>::const_iterator I = ValueMap.begin(),
E = ValueMap.end(); I != E; ++I) {
if (I->second.size()) { // Only output nodes with edges...
- stringstream OS;
+ std::stringstream OS;
WriteTypeSymbolic(OS, I->first->getType(), Func->getParent());
// Create node for I->first
@@ -357,7 +360,7 @@ void FunctionDSGraph::printFunction(std::ostream &O,
// graph...
//
FunctionDSGraph::FunctionDSGraph(const FunctionDSGraph &DSG) : Func(DSG.Func) {
- vector<PointerValSet> Args;
+ std::vector<PointerValSet> Args;
RetNode = cloneFunctionIntoSelf(DSG, true, Args);
}
@@ -370,7 +373,7 @@ FunctionDSGraph::FunctionDSGraph(const FunctionDSGraph &DSG) : Func(DSG.Func) {
//
PointerValSet FunctionDSGraph::cloneFunctionIntoSelf(const FunctionDSGraph &DSG,
bool CloneValueMap,
- vector<PointerValSet> &Args) {
+ std::vector<PointerValSet> &Args) {
map<const DSNode*, DSNode*> NodeMap; // Map from old graph to new graph...
unsigned StartAllocSize = AllocNodes.size();
AllocNodes.reserve(StartAllocSize+DSG.AllocNodes.size());
@@ -453,13 +456,13 @@ FunctionDSGraph::~FunctionDSGraph() {
RetNode.clear();
ValueMap.clear();
for_each(AllocNodes.begin(), AllocNodes.end(),
- mem_fun(&DSNode::dropAllReferences));
+ std::mem_fun(&DSNode::dropAllReferences));
for_each(ShadowNodes.begin(), ShadowNodes.end(),
- mem_fun(&DSNode::dropAllReferences));
+ std::mem_fun(&DSNode::dropAllReferences));
for_each(GlobalNodes.begin(), GlobalNodes.end(),
- mem_fun(&DSNode::dropAllReferences));
+ std::mem_fun(&DSNode::dropAllReferences));
for_each(CallNodes.begin(), CallNodes.end(),
- mem_fun(&DSNode::dropAllReferences));
+ std::mem_fun(&DSNode::dropAllReferences));
for_each(AllocNodes.begin(), AllocNodes.end(), deleter<DSNode>);
for_each(ShadowNodes.begin(), ShadowNodes.end(), deleter<DSNode>);
for_each(GlobalNodes.begin(), GlobalNodes.end(), deleter<DSNode>);
generated by cgit v1.1 at 2025-02-28 10:23:00 +0000