aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--include/llvm/Analysis/DSGraph.h14
-rw-r--r--include/llvm/Analysis/DSNode.h4
-rw-r--r--include/llvm/Analysis/DSSupport.h14
-rw-r--r--include/llvm/Analysis/DataStructure.h23
-rw-r--r--include/llvm/Analysis/DataStructure/DSGraph.h14
-rw-r--r--include/llvm/Analysis/DataStructure/DSNode.h4
-rw-r--r--include/llvm/Analysis/DataStructure/DSSupport.h14
-rw-r--r--include/llvm/Analysis/DataStructure/DataStructure.h23
-rw-r--r--include/llvm/Analysis/IPModRef.h3
-rw-r--r--lib/Analysis/DataStructure/BottomUpClosure.cpp17
-rw-r--r--lib/Analysis/DataStructure/DataStructure.cpp55
-rw-r--r--lib/Analysis/DataStructure/IPModRef.cpp6
-rw-r--r--lib/Analysis/DataStructure/Local.cpp8
-rw-r--r--lib/Analysis/DataStructure/Printer.cpp4
-rw-r--r--lib/Analysis/DataStructure/Steensgaard.cpp20
-rw-r--r--lib/Analysis/DataStructure/TopDownClosure.cpp6
-rw-r--r--lib/Analysis/IPA/IPModRef.cpp6
-rw-r--r--lib/Transforms/IPO/PoolAllocate.cpp12
18 files changed, 124 insertions, 123 deletions
diff --git a/include/llvm/Analysis/DSGraph.h b/include/llvm/Analysis/DSGraph.h
index 8e11dc010a..daab1195b3 100644
--- a/include/llvm/Analysis/DSGraph.h
+++ b/include/llvm/Analysis/DSGraph.h
@@ -19,7 +19,7 @@ class DSGraph {
DSNodeHandle RetNode; // The node that gets returned...
std::vector<DSNode*> Nodes;
- std::map<Value*, DSNodeHandle> ScalarMap;
+ hash_map<Value*, DSNodeHandle> ScalarMap;
// FunctionCalls - This vector maintains a single entry for each call
// instruction in the current graph. The first entry in the vector is the
@@ -49,7 +49,7 @@ public:
// method.
//
DSGraph(const DSGraph &DSG);
- DSGraph(const DSGraph &DSG, std::map<const DSNode*, DSNodeHandle> &NodeMap);
+ DSGraph(const DSGraph &DSG, hash_map<const DSNode*, DSNodeHandle> &NodeMap);
~DSGraph();
bool hasFunction() const { return Func != 0; }
@@ -76,8 +76,8 @@ public:
/// getScalarMap - Get a map that describes what the nodes the scalars in this
/// function point to...
///
- std::map<Value*, DSNodeHandle> &getScalarMap() { return ScalarMap; }
- const std::map<Value*, DSNodeHandle> &getScalarMap() const {return ScalarMap;}
+ hash_map<Value*, DSNodeHandle> &getScalarMap() { return ScalarMap; }
+ const hash_map<Value*, DSNodeHandle> &getScalarMap() const {return ScalarMap;}
/// getFunctionCalls - Return the list of call sites in the original local
/// graph...
@@ -102,7 +102,7 @@ public:
DSNodeHandle &getNodeForValue(Value *V) { return ScalarMap[V]; }
const DSNodeHandle &getNodeForValue(Value *V) const {
- std::map<Value*, DSNodeHandle>::const_iterator I = ScalarMap.find(V);
+ hash_map<Value*, DSNodeHandle>::const_iterator I = ScalarMap.find(V);
assert(I != ScalarMap.end() &&
"Use non-const lookup function if node may not be in the map");
return I->second;
@@ -168,8 +168,8 @@ public:
// being cloned.
//
DSNodeHandle cloneInto(const DSGraph &G,
- std::map<Value*, DSNodeHandle> &OldValMap,
- std::map<const DSNode*, DSNodeHandle> &OldNodeMap,
+ hash_map<Value*, DSNodeHandle> &OldValMap,
+ hash_map<const DSNode*, DSNodeHandle> &OldNodeMap,
unsigned CloneFlags = 0);
/// mergeInGraph - The method is used for merging graphs together. If the
diff --git a/include/llvm/Analysis/DSNode.h b/include/llvm/Analysis/DSNode.h
index 5edbd72f83..da8050cd9a 100644
--- a/include/llvm/Analysis/DSNode.h
+++ b/include/llvm/Analysis/DSNode.h
@@ -218,13 +218,13 @@ public:
/// remapLinks - Change all of the Links in the current node according to the
/// specified mapping.
- void remapLinks(std::map<const DSNode*, DSNodeHandle> &OldNodeMap);
+ void remapLinks(hash_map<const DSNode*, DSNodeHandle> &OldNodeMap);
/// markReachableNodes - This method recursively traverses the specified
/// DSNodes, marking any nodes which are reachable. All reachable nodes it
/// adds to the set, which allows it to only traverse visited nodes once.
///
- void markReachableNodes(std::set<DSNode*> &ReachableNodes);
+ void markReachableNodes(hash_set<DSNode*> &ReachableNodes);
private:
friend class DSNodeHandle;
diff --git a/include/llvm/Analysis/DSSupport.h b/include/llvm/Analysis/DSSupport.h
index f0f261e0b9..06bcb5eaa9 100644
--- a/include/llvm/Analysis/DSSupport.h
+++ b/include/llvm/Analysis/DSSupport.h
@@ -8,10 +8,10 @@
#define LLVM_ANALYSIS_DSSUPPORT_H
#include <vector>
-#include <map>
-#include <set>
#include <functional>
#include <string>
+#include "Support/HashExtras.h"
+#include "Support/hash_set"
class Function;
class CallInst;
@@ -118,9 +118,9 @@ class DSCallSite {
Function *ResolvingCaller; // See comments above
static void InitNH(DSNodeHandle &NH, const DSNodeHandle &Src,
- const std::map<const DSNode*, DSNode*> &NodeMap) {
+ const hash_map<const DSNode*, DSNode*> &NodeMap) {
if (DSNode *N = Src.getNode()) {
- std::map<const DSNode*, DSNode*>::const_iterator I = NodeMap.find(N);
+ hash_map<const DSNode*, DSNode*>::const_iterator I = NodeMap.find(N);
assert(I != NodeMap.end() && "Not not in mapping!");
NH.setOffset(Src.getOffset());
@@ -129,9 +129,9 @@ class DSCallSite {
}
static void InitNH(DSNodeHandle &NH, const DSNodeHandle &Src,
- const std::map<const DSNode*, DSNodeHandle> &NodeMap) {
+ const hash_map<const DSNode*, DSNodeHandle> &NodeMap) {
if (DSNode *N = Src.getNode()) {
- std::map<const DSNode*, DSNodeHandle>::const_iterator I = NodeMap.find(N);
+ hash_map<const DSNode*, DSNodeHandle>::const_iterator I = NodeMap.find(N);
assert(I != NodeMap.end() && "Not not in mapping!");
NH.setOffset(Src.getOffset()+I->second.getOffset());
@@ -219,7 +219,7 @@ public:
/// DSNodes, marking any nodes which are reachable. All reachable nodes it
/// adds to the set, which allows it to only traverse visited nodes once.
///
- void markReachableNodes(std::set<DSNode*> &Nodes);
+ void markReachableNodes(hash_set<DSNode*> &Nodes);
bool operator<(const DSCallSite &CS) const {
if (Callee < CS.Callee) return true; // This must sort by callee first!
diff --git a/include/llvm/Analysis/DataStructure.h b/include/llvm/Analysis/DataStructure.h
index 391f95a810..ddaf83a459 100644
--- a/include/llvm/Analysis/DataStructure.h
+++ b/include/llvm/Analysis/DataStructure.h
@@ -8,7 +8,8 @@
#define LLVM_ANALYSIS_DATA_STRUCTURE_H
#include "llvm/Pass.h"
-#include <set>
+#include "Support/HashExtras.h"
+#include "Support/hash_set"
class Type;
class DSGraph;
@@ -32,7 +33,7 @@ namespace DataStructureAnalysis {
//
class LocalDataStructures : public Pass {
// DSInfo, one graph for each function
- std::map<const Function*, DSGraph*> DSInfo;
+ hash_map<const Function*, DSGraph*> DSInfo;
DSGraph *GlobalsGraph;
public:
~LocalDataStructures() { releaseMemory(); }
@@ -45,7 +46,7 @@ public:
// getDSGraph - Return the data structure graph for the specified function.
DSGraph &getDSGraph(const Function &F) const {
- std::map<const Function*, DSGraph*>::const_iterator I = DSInfo.find(&F);
+ hash_map<const Function*, DSGraph*>::const_iterator I = DSInfo.find(&F);
assert(I != DSInfo.end() && "Function not in module!");
return *I->second;
}
@@ -71,7 +72,7 @@ public:
//
class BUDataStructures : public Pass {
// DSInfo, one graph for each function
- std::map<const Function*, DSGraph*> DSInfo;
+ hash_map<const Function*, DSGraph*> DSInfo;
DSGraph *GlobalsGraph;
public:
~BUDataStructures() { releaseMemory(); }
@@ -84,7 +85,7 @@ public:
// getDSGraph - Return the data structure graph for the specified function.
DSGraph &getDSGraph(const Function &F) const {
- std::map<const Function*, DSGraph*>::const_iterator I = DSInfo.find(&F);
+ hash_map<const Function*, DSGraph*>::const_iterator I = DSInfo.find(&F);
assert(I != DSInfo.end() && "Function not in module!");
return *I->second;
}
@@ -110,10 +111,10 @@ private:
// functions IN the SCC at all.
//
DSGraph &inlineNonSCCGraphs(Function &F,
- std::set<Function*> &SCCFunctions);
+ hash_set<Function*> &SCCFunctions);
DSGraph &calculateSCCGraph(Function &F,
- std::set<Function*> &InlinedSCCFunctions);
+ hash_set<Function*> &InlinedSCCFunctions);
void calculateReachableGraphs(Function *F);
@@ -121,7 +122,7 @@ private:
unsigned calculateGraphs(Function *F, std::vector<Function*> &Stack,
unsigned &NextID,
- std::map<Function*, unsigned> &ValMap);
+ hash_map<Function*, unsigned> &ValMap);
};
@@ -131,8 +132,8 @@ private:
//
class TDDataStructures : public Pass {
// DSInfo, one graph for each function
- std::map<const Function*, DSGraph*> DSInfo;
- std::set<const Function*> GraphDone;
+ hash_map<const Function*, DSGraph*> DSInfo;
+ hash_set<const Function*> GraphDone;
DSGraph *GlobalsGraph;
public:
~TDDataStructures() { releaseMemory(); }
@@ -145,7 +146,7 @@ public:
// getDSGraph - Return the data structure graph for the specified function.
DSGraph &getDSGraph(const Function &F) const {
- std::map<const Function*, DSGraph*>::const_iterator I = DSInfo.find(&F);
+ hash_map<const Function*, DSGraph*>::const_iterator I = DSInfo.find(&F);
assert(I != DSInfo.end() && "Function not in module!");
return *I->second;
}
diff --git a/include/llvm/Analysis/DataStructure/DSGraph.h b/include/llvm/Analysis/DataStructure/DSGraph.h
index 8e11dc010a..daab1195b3 100644
--- a/include/llvm/Analysis/DataStructure/DSGraph.h
+++ b/include/llvm/Analysis/DataStructure/DSGraph.h
@@ -19,7 +19,7 @@ class DSGraph {
DSNodeHandle RetNode; // The node that gets returned...
std::vector<DSNode*> Nodes;
- std::map<Value*, DSNodeHandle> ScalarMap;
+ hash_map<Value*, DSNodeHandle> ScalarMap;
// FunctionCalls - This vector maintains a single entry for each call
// instruction in the current graph. The first entry in the vector is the
@@ -49,7 +49,7 @@ public:
// method.
//
DSGraph(const DSGraph &DSG);
- DSGraph(const DSGraph &DSG, std::map<const DSNode*, DSNodeHandle> &NodeMap);
+ DSGraph(const DSGraph &DSG, hash_map<const DSNode*, DSNodeHandle> &NodeMap);
~DSGraph();
bool hasFunction() const { return Func != 0; }
@@ -76,8 +76,8 @@ public:
/// getScalarMap - Get a map that describes what the nodes the scalars in this
/// function point to...
///
- std::map<Value*, DSNodeHandle> &getScalarMap() { return ScalarMap; }
- const std::map<Value*, DSNodeHandle> &getScalarMap() const {return ScalarMap;}
+ hash_map<Value*, DSNodeHandle> &getScalarMap() { return ScalarMap; }
+ const hash_map<Value*, DSNodeHandle> &getScalarMap() const {return ScalarMap;}
/// getFunctionCalls - Return the list of call sites in the original local
/// graph...
@@ -102,7 +102,7 @@ public:
DSNodeHandle &getNodeForValue(Value *V) { return ScalarMap[V]; }
const DSNodeHandle &getNodeForValue(Value *V) const {
- std::map<Value*, DSNodeHandle>::const_iterator I = ScalarMap.find(V);
+ hash_map<Value*, DSNodeHandle>::const_iterator I = ScalarMap.find(V);
assert(I != ScalarMap.end() &&
"Use non-const lookup function if node may not be in the map");
return I->second;
@@ -168,8 +168,8 @@ public:
// being cloned.
//
DSNodeHandle cloneInto(const DSGraph &G,
- std::map<Value*, DSNodeHandle> &OldValMap,
- std::map<const DSNode*, DSNodeHandle> &OldNodeMap,
+ hash_map<Value*, DSNodeHandle> &OldValMap,
+ hash_map<const DSNode*, DSNodeHandle> &OldNodeMap,
unsigned CloneFlags = 0);
/// mergeInGraph - The method is used for merging graphs together. If the
diff --git a/include/llvm/Analysis/DataStructure/DSNode.h b/include/llvm/Analysis/DataStructure/DSNode.h
index 5edbd72f83..da8050cd9a 100644
--- a/include/llvm/Analysis/DataStructure/DSNode.h
+++ b/include/llvm/Analysis/DataStructure/DSNode.h
@@ -218,13 +218,13 @@ public:
/// remapLinks - Change all of the Links in the current node according to the
/// specified mapping.
- void remapLinks(std::map<const DSNode*, DSNodeHandle> &OldNodeMap);
+ void remapLinks(hash_map<const DSNode*, DSNodeHandle> &OldNodeMap);
/// markReachableNodes - This method recursively traverses the specified
/// DSNodes, marking any nodes which are reachable. All reachable nodes it
/// adds to the set, which allows it to only traverse visited nodes once.
///
- void markReachableNodes(std::set<DSNode*> &ReachableNodes);
+ void markReachableNodes(hash_set<DSNode*> &ReachableNodes);
private:
friend class DSNodeHandle;
diff --git a/include/llvm/Analysis/DataStructure/DSSupport.h b/include/llvm/Analysis/DataStructure/DSSupport.h
index f0f261e0b9..06bcb5eaa9 100644
--- a/include/llvm/Analysis/DataStructure/DSSupport.h
+++ b/include/llvm/Analysis/DataStructure/DSSupport.h
@@ -8,10 +8,10 @@
#define LLVM_ANALYSIS_DSSUPPORT_H
#include <vector>
-#include <map>
-#include <set>
#include <functional>
#include <string>
+#include "Support/HashExtras.h"
+#include "Support/hash_set"
class Function;
class CallInst;
@@ -118,9 +118,9 @@ class DSCallSite {
Function *ResolvingCaller; // See comments above
static void InitNH(DSNodeHandle &NH, const DSNodeHandle &Src,
- const std::map<const DSNode*, DSNode*> &NodeMap) {
+ const hash_map<const DSNode*, DSNode*> &NodeMap) {
if (DSNode *N = Src.getNode()) {
- std::map<const DSNode*, DSNode*>::const_iterator I = NodeMap.find(N);
+ hash_map<const DSNode*, DSNode*>::const_iterator I = NodeMap.find(N);
assert(I != NodeMap.end() && "Not not in mapping!");
NH.setOffset(Src.getOffset());
@@ -129,9 +129,9 @@ class DSCallSite {
}
static void InitNH(DSNodeHandle &NH, const DSNodeHandle &Src,
- const std::map<const DSNode*, DSNodeHandle> &NodeMap) {
+ const hash_map<const DSNode*, DSNodeHandle> &NodeMap) {
if (DSNode *N = Src.getNode()) {
- std::map<const DSNode*, DSNodeHandle>::const_iterator I = NodeMap.find(N);
+ hash_map<const DSNode*, DSNodeHandle>::const_iterator I = NodeMap.find(N);
assert(I != NodeMap.end() && "Not not in mapping!");
NH.setOffset(Src.getOffset()+I->second.getOffset());
@@ -219,7 +219,7 @@ public:
/// DSNodes, marking any nodes which are reachable. All reachable nodes it
/// adds to the set, which allows it to only traverse visited nodes once.
///
- void markReachableNodes(std::set<DSNode*> &Nodes);
+ void markReachableNodes(hash_set<DSNode*> &Nodes);
bool operator<(const DSCallSite &CS) const {
if (Callee < CS.Callee) return true; // This must sort by callee first!
diff --git a/include/llvm/Analysis/DataStructure/DataStructure.h b/include/llvm/Analysis/DataStructure/DataStructure.h
index 391f95a810..ddaf83a459 100644
--- a/include/llvm/Analysis/DataStructure/DataStructure.h
+++ b/include/llvm/Analysis/DataStructure/DataStructure.h
@@ -8,7 +8,8 @@
#define LLVM_ANALYSIS_DATA_STRUCTURE_H
#include "llvm/Pass.h"
-#include <set>
+#include "Support/HashExtras.h"
+#include "Support/hash_set"
class Type;
class DSGraph;
@@ -32,7 +33,7 @@ namespace DataStructureAnalysis {
//
class LocalDataStructures : public Pass {
// DSInfo, one graph for each function
- std::map<const Function*, DSGraph*> DSInfo;
+ hash_map<const Function*, DSGraph*> DSInfo;
DSGraph *GlobalsGraph;
public:
~LocalDataStructures() { releaseMemory(); }
@@ -45,7 +46,7 @@ public:
// getDSGraph - Return the data structure graph for the specified function.
DSGraph &getDSGraph(const Function &F) const {
- std::map<const Function*, DSGraph*>::const_iterator I = DSInfo.find(&F);
+ hash_map<const Function*, DSGraph*>::const_iterator I = DSInfo.find(&F);
assert(I != DSInfo.end() && "Function not in module!");
return *I->second;
}
@@ -71,7 +72,7 @@ public:
//
class BUDataStructures : public Pass {
// DSInfo, one graph for each function
- std::map<const Function*, DSGraph*> DSInfo;
+ hash_map<const Function*, DSGraph*> DSInfo;
DSGraph *GlobalsGraph;
public:
~BUDataStructures() { releaseMemory(); }
@@ -84,7 +85,7 @@ public:
// getDSGraph - Return the data structure graph for the specified function.
DSGraph &getDSGraph(const Function &F) const {
- std::map<const Function*, DSGraph*>::const_iterator I = DSInfo.find(&F);
+ hash_map<const Function*, DSGraph*>::const_iterator I = DSInfo.find(&F);
assert(I != DSInfo.end() && "Function not in module!");
return *I->second;
}
@@ -110,10 +111,10 @@ private:
// functions IN the SCC at all.
//
DSGraph &inlineNonSCCGraphs(Function &F,
- std::set<Function*> &SCCFunctions);
+ hash_set<Function*> &SCCFunctions);
DSGraph &calculateSCCGraph(Function &F,
- std::set<Function*> &InlinedSCCFunctions);
+ hash_set<Function*> &InlinedSCCFunctions);
void calculateReachableGraphs(Function *F);
@@ -121,7 +122,7 @@ private:
unsigned calculateGraphs(Function *F, std::vector<Function*> &Stack,
unsigned &NextID,
- std::map<Function*, unsigned> &ValMap);
+ hash_map<Function*, unsigned> &ValMap);
};
@@ -131,8 +132,8 @@ private:
//
class TDDataStructures : public Pass {
// DSInfo, one graph for each function
- std::map<const Function*, DSGraph*> DSInfo;
- std::set<const Function*> GraphDone;
+ hash_map<const Function*, DSGraph*> DSInfo;
+ hash_set<const Function*> GraphDone;
DSGraph *GlobalsGraph;
public:
~TDDataStructures() { releaseMemory(); }
@@ -145,7 +146,7 @@ public:
// getDSGraph - Return the data structure graph for the specified function.
DSGraph &getDSGraph(const Function &F) const {
- std::map<const Function*, DSGraph*>::const_iterator I = DSInfo.find(&F);
+ hash_map<const Function*, DSGraph*>::const_iterator I = DSInfo.find(&F);
assert(I != DSInfo.end() && "Function not in module!");
return *I->second;
}
diff --git a/include/llvm/Analysis/IPModRef.h b/include/llvm/Analysis/IPModRef.h
index 1b472e91f9..eed264f978 100644
--- a/include/llvm/Analysis/IPModRef.h
+++ b/include/llvm/Analysis/IPModRef.h
@@ -41,6 +41,7 @@
#include "llvm/Pass.h"
#include "Support/BitSetVector.h"
+#include "Support/hash_map"
class Module;
class Function;
@@ -125,7 +126,7 @@ class FunctionModRefInfo {
void computeModRef (const Function &func);
void computeModRef (const CallInst& callInst);
DSGraph *ResolveCallSiteModRefInfo(CallInst &CI,
- std::map<const DSNode*, DSNodeHandle> &NodeMap);
+ hash_map<const DSNode*, DSNodeHandle> &NodeMap);
public:
/* ctor */ FunctionModRefInfo (const Function& func,
diff --git a/lib/Analysis/DataStructure/BottomUpClosure.cpp b/lib/Analysis/DataStructure/BottomUpClosure.cpp
index 26b7813482..8fa331c92d 100644
--- a/lib/Analysis/DataStructure/BottomUpClosure.cpp
+++ b/lib/Analysis/DataStructure/BottomUpClosure.cpp
@@ -11,6 +11,7 @@
#include "llvm/Analysis/DSGraph.h"
#include "llvm/Module.h"
#include "Support/Statistic.h"
+#include "Support/hash_map"
namespace {
Statistic<> MaxSCC("budatastructure", "Maximum SCC Size in Call Graph");
@@ -128,7 +129,7 @@ bool BUDataStructures::run(Module &M) {
void BUDataStructures::calculateReachableGraphs(Function *F) {
std::vector<Function*> Stack;
- std::map<Function*, unsigned> ValMap;
+ hash_map<Function*, unsigned> ValMap;
unsigned NextID = 1;
calculateGraphs(F, Stack, NextID, ValMap);
}
@@ -152,7 +153,7 @@ DSGraph &BUDataStructures::getOrCreateGraph(Function *F) {
unsigned BUDataStructures::calculateGraphs(Function *F,
std::vector<Function*> &Stack,
unsigned &NextID,
- std::map<Function*, unsigned> &ValMap) {
+ hash_map<Function*, unsigned> &ValMap) {
assert(ValMap.find(F) == ValMap.end() && "Shouldn't revisit functions!");
unsigned Min = NextID++, MyID = Min;
ValMap[F] = Min;
@@ -173,7 +174,7 @@ unsigned BUDataStructures::calculateGraphs(Function *F,
Function *Callee = *I;
unsigned M;
// Have we visited the destination function yet?
- std::map<Function*, unsigned>::iterator It = ValMap.find(Callee);
+ hash_map<Function*, unsigned>::iterator It = ValMap.find(Callee);
if (It == ValMap.end()) // No, visit it now.
M = calculateGraphs(Callee, Stack, NextID, ValMap);
else // Yes, get it's number.
@@ -206,7 +207,7 @@ unsigned BUDataStructures::calculateGraphs(Function *F,
} else {
// SCCFunctions - Keep track of the functions in the current SCC
//
- std::set<Function*> SCCFunctions;
+ hash_set<Function*> SCCFunctions;
Function *NF;
std::vector<Function*>::iterator FirstInSCC = Stack.end();
@@ -283,7 +284,7 @@ unsigned BUDataStructures::calculateGraphs(Function *F,
// our memory... here...
//
void BUDataStructures::releaseMemory() {
- for (std::map<const Function*, DSGraph*>::iterator I = DSInfo.begin(),
+ for (hash_map<const Function*, DSGraph*>::iterator I = DSInfo.begin(),
E = DSInfo.end(); I != E; ++I)
delete I->second;
@@ -383,7 +384,7 @@ DSGraph &BUDataStructures::calculateGraph(Function &F) {
// IN the SCC at all.
//
DSGraph &BUDataStructures::inlineNonSCCGraphs(Function &F,
- std::set<Function*> &SCCFunctions){
+ hash_set<Function*> &SCCFunctions){
DSGraph &Graph = getDSGraph(F);
DEBUG(std::cerr << " [BU] Inlining Non-SCC graphs for: "
<< F.getName() << "\n");
@@ -452,12 +453,12 @@ DSGraph &BUDataStructures::inlineNonSCCGraphs(Function &F,
DSGraph &BUDataStructures::calculateSCCGraph(Function &F,
- std::set<Function*> &SCCFunctions){
+ hash_set<Function*> &SCCFunctions){
DSGraph &Graph = getDSGraph(F);
DEBUG(std::cerr << " [BU] Calculating SCC graph for: " << F.getName()<<"\n");
std::vector<DSCallSite> UnresolvableCalls;
- std::map<Function*, DSCallSite> SCCCallSiteMap;
+ hash_map<Function*, DSCallSite> SCCCallSiteMap;
std::vector<DSCallSite> &AuxCallsList = Graph.getAuxFunctionCalls();
while (1) { // Loop until we run out of resolvable call sites!
diff --git a/lib/Analysis/DataStructure/DataStructure.cpp b/lib/Analysis/DataStructure/DataStructure.cpp
index 797eb19a19..1dbabb7f1b 100644
--- a/lib/Analysis/DataStructure/DataStructure.cpp
+++ b/lib/Analysis/DataStructure/DataStructure.cpp
@@ -540,12 +540,12 @@ Function &DSCallSite::getCaller() const {
DSGraph::DSGraph(const DSGraph &G) : Func(G.Func), GlobalsGraph(0) {
PrintAuxCalls = false;
- std::map<const DSNode*, DSNodeHandle> NodeMap;
+ hash_map<const DSNode*, DSNodeHandle> NodeMap;
RetNode = cloneInto(G, ScalarMap, NodeMap);
}
DSGraph::DSGraph(const DSGraph &G,
- std::map<const DSNode*, DSNodeHandle> &NodeMap)
+ hash_map<const DSNode*, DSNodeHandle> &NodeMap)
: Func(G.Func), GlobalsGraph(0) {
PrintAuxCalls = false;
RetNode = cloneInto(G, ScalarMap, NodeMap);
@@ -572,7 +572,7 @@ void DSGraph::dump() const { print(std::cerr); }
/// remapLinks - Change all of the Links in the current node according to the
/// specified mapping.
///
-void DSNode::remapLinks(std::map<const DSNode*, DSNodeHandle> &OldNodeMap) {
+void DSNode::remapLinks(hash_map<const DSNode*, DSNodeHandle> &OldNodeMap) {
for (unsigned i = 0, e = Links.size(); i != e; ++i) {
DSNodeHandle &H = OldNodeMap[Links[i].getNode()];
Links[i].setNode(H.getNode());
@@ -588,8 +588,8 @@ void DSNode::remapLinks(std::map<const DSNode*, DSNodeHandle> &OldNodeMap) {
// calling function's graph.
//
DSNodeHandle DSGraph::cloneInto(const DSGraph &G,
- std::map<Value*, DSNodeHandle> &OldValMap,
- std::map<const DSNode*, DSNodeHandle> &OldNodeMap,
+ hash_map<Value*, DSNodeHandle> &OldValMap,
+ hash_map<const DSNode*, DSNodeHandle> &OldNodeMap,
unsigned CloneFlags) {
assert(OldNodeMap.empty() && "Returned OldNodeMap should be empty!");
assert(&G != this && "Cannot clone graph into itself!");
@@ -625,7 +625,7 @@ DSNodeHandle DSGraph::cloneInto(const DSGraph &G,
}
// Copy the value map... and merge all of the global nodes...
- for (std::map<Value*, DSNodeHandle>::const_iterator I = G.ScalarMap.begin(),
+ for (hash_map<Value*, DSNodeHandle>::const_iterator I = G.ScalarMap.begin(),
E = G.ScalarMap.end(); I != E; ++I) {
DSNodeHandle &H = OldValMap[I->first];
DSNodeHandle &MappedNode = OldNodeMap[I->second.getNode()];
@@ -633,7 +633,7 @@ DSNodeHandle DSGraph::cloneInto(const DSGraph &G,
H.setOffset(I->second.getOffset()+MappedNode.getOffset());
if (isa<GlobalValue>(I->first)) { // Is this a global?
- std::map<Value*, DSNodeHandle>::iterator GVI = ScalarMap.find(I->first);
+ hash_map<Value*, DSNodeHandle>::iterator GVI = ScalarMap.find(I->first);
if (GVI != ScalarMap.end()) { // Is the global value in this fn already?
GVI->second.mergeWith(H);
} else {
@@ -671,16 +671,16 @@ DSNodeHandle DSGraph::cloneInto(const DSGraph &G,
///
void DSGraph::mergeInGraph(DSCallSite &CS, const DSGraph &Graph,
unsigned CloneFlags) {
- std::map<Value*, DSNodeHandle> OldValMap;
+ hash_map<Value*, DSNodeHandle> OldValMap;
DSNodeHandle RetVal;
- std::map<Value*, DSNodeHandle> *ScalarMap = &OldValMap;
+ hash_map<Value*, DSNodeHandle> *ScalarMap = &OldValMap;
// If this is not a recursive call, clone the graph into this graph...
if (&Graph != this) {
// Clone the callee's graph into the current graph, keeping
// track of where scalars in the old graph _used_ to point,
// and of the new nodes matching nodes of the old graph.
- std::map<const DSNode*, DSNodeHandle> OldNodeMap;
+ hash_map<const DSNode*, DSNodeHandle> OldNodeMap;
// The clone call may invalidate any of the vectors in the data
// structure graph. Strip locals and don't copy the list of callers
@@ -811,7 +811,7 @@ void DSGraph::markIncompleteNodes(unsigned Flags) {
// removeRefsToGlobal - Helper function that removes globals from the
// ScalarMap so that the referrer count will go down to zero.
static void removeRefsToGlobal(DSNode* N,
- std::map<Value*, DSNodeHandle> &ScalarMap) {
+ hash_map<Value*, DSNodeHandle> &ScalarMap) {
while (!N->getGlobals().empty()) {
GlobalValue *GV = N->getGlobals().back();
N->getGlobals().pop_back();
@@ -939,18 +939,16 @@ void DSGraph::removeTriviallyDeadNodes() {
/// DSNodes, marking any nodes which are reachable. All reachable nodes it adds
/// to the set, which allows it to only traverse visited nodes once.
///
-void DSNode::markReachableNodes(std::set<DSNode*> &ReachableNodes) {
+void DSNode::markReachableNodes(hash_set<DSNode*> &ReachableNodes) {
if (this == 0) return;
- std::set<DSNode*>::iterator I = ReachableNodes.lower_bound(this);
- if (I != ReachableNodes.end() && *I == this)
- return; // Already marked reachable
- ReachableNodes.insert(I, this); // Is reachable now
+ if (ReachableNodes.count(this)) return; // Already marked reachable
+ ReachableNodes.insert(this); // Is reachable now
for (unsigned i = 0, e = getSize(); i < e; i += DS::PointerSize)
getLink(i).getNode()->markReachableNodes(ReachableNodes);
}
-void DSCallSite::markReachableNodes(std::set<DSNode*> &Nodes) {
+void DSCallSite::markReachableNodes(hash_set<DSNode*> &Nodes) {
getRetVal().getNode()->markReachableNodes(Nodes);
getCallee().getNode()->markReachableNodes(Nodes);
@@ -965,8 +963,8 @@ void DSCallSite::markReachableNodes(std::set<DSNode*> &Nodes) {
//
// This function returns true if the specified node is alive.
//
-static bool markAliveIfCanReachAlive(DSNode *N, std::set<DSNode*> &Alive,
- std::set<DSNode*> &Visited) {
+static bool markAliveIfCanReachAlive(DSNode *N, hash_set<DSNode*> &Alive,
+ hash_set<DSNode*> &Visited) {
if (N == 0) return false;
// If we know that this node is alive, return so!
@@ -974,10 +972,9 @@ static bool markAliveIfCanReachAlive(DSNode *N, std::set<DSNode*> &Alive,
// Otherwise, we don't think the node is alive yet, check for infinite
// recursion.
- std::set<DSNode*>::iterator VI = Visited.lower_bound(N);
- if (VI != Visited.end() && *VI == N) return false; // Found a cycle
+ if (Visited.count(N)) return false; // Found a cycle
// No recursion, insert into Visited...
- Visited.insert(VI, N);
+ Visited.insert(N);
if (N->NodeType & DSNode::GlobalNode)
return false; // Global nodes will be marked on their own
@@ -992,8 +989,8 @@ static bool markAliveIfCanReachAlive(DSNode *N, std::set<DSNode*> &Alive,
return ChildrenAreAlive;
}
-static bool CallSiteUsesAliveArgs(DSCallSite &CS, std::set<DSNode*> &Alive,
- std::set<DSNode*> &Visited) {
+static bool CallSiteUsesAliveArgs(DSCallSite &CS, hash_set<DSNode*> &Alive,
+ hash_set<DSNode*> &Visited) {
if (markAliveIfCanReachAlive(CS.getRetVal().getNode(), Alive, Visited) ||
markAliveIfCanReachAlive(CS.getCallee().getNode(), Alive, Visited))
return true;
@@ -1034,11 +1031,11 @@ void DSGraph::removeDeadNodes(unsigned Flags) {
// FIXME: Merge nontrivially identical call nodes...
// Alive - a set that holds all nodes found to be reachable/alive.
- std::set<DSNode*> Alive;
+ hash_set<DSNode*> Alive;
std::vector<std::pair<Value*, DSNode*> > GlobalNodes;
// Mark all nodes reachable by (non-global) scalar nodes as alive...
- for (std::map<Value*, DSNodeHandle>::iterator I = ScalarMap.begin(),
+ for (hash_map<Value*, DSNodeHandle>::iterator I = ScalarMap.begin(),
E = ScalarMap.end(); I != E; ++I)
if (!isa<GlobalValue>(I->first) ||
GlobalIsAlivenessRoot(I->second.getNode(), Flags))
@@ -1052,7 +1049,7 @@ void DSGraph::removeDeadNodes(unsigned Flags) {
// If any global nodes points to a non-global that is "alive", the global is
// "alive" as well...
//
- std::set<DSNode*> Visited;
+ hash_set<DSNode*> Visited;
for (unsigned i = 0, e = GlobalNodes.size(); i != e; ++i)
markAliveIfCanReachAlive(GlobalNodes[i].second, Alive, Visited);
@@ -1129,7 +1126,7 @@ static const char ExternalTypeBits = DSNode::GlobalNode | DSNode::HeapNode;
// This is a helper function for cloneGlobals and cloneCalls.
//
DSNode* GlobalDSGraph::cloneNodeInto(DSNode *OldNode,
- std::map<const DSNode*, DSNode*> &NodeCache,
+ hash_map<const DSNode*, DSNode*> &NodeCache,
bool GlobalsAreFinal) {
if (OldNode == 0) return 0;
@@ -1208,7 +1205,7 @@ DSNode* GlobalDSGraph::cloneNodeInto(DSNode *OldNode,
// links (and recursively their such links) into this graph.
//
void GlobalDSGraph::cloneCalls(DSGraph& Graph) {
- std::map<const DSNode*, DSNode*> NodeCache;
+ hash_map<const DSNode*, DSNode*> NodeCache;
std::vector<DSCallSite >& FromCalls =Graph.FunctionCalls;
FunctionCalls.reserve(FunctionCalls.size() + FromCalls.size());
diff --git a/lib/Analysis/DataStructure/IPModRef.cpp b/lib/Analysis/DataStructure/IPModRef.cpp
index 48452fe8b1..e04e109450 100644
--- a/lib/Analysis/DataStructure/IPModRef.cpp
+++ b/lib/Analysis/DataStructure/IPModRef.cpp
@@ -118,7 +118,7 @@ void FunctionModRefInfo::computeModRef(const Function &func)
// function or we cannot determine the complete set of functions invoked).
//
DSGraph* FunctionModRefInfo::ResolveCallSiteModRefInfo(CallInst &CI,
- std::map<const DSNode*, DSNodeHandle> &NodeMap)