From 41c04f730b4fdce98b35603d1b02a1dc6b81e589 Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Sat, 1 Feb 2003 04:52:08 +0000 Subject: [PATCH] Change DSGraph stuff to use hash_(set|map) instead of std::(set|map) This change provides a small (3%) but consistent speedup git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5460 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/DSGraph.h | 14 ++--- include/llvm/Analysis/DSNode.h | 4 +- include/llvm/Analysis/DSSupport.h | 14 ++--- include/llvm/Analysis/DataStructure.h | 23 ++++---- include/llvm/Analysis/DataStructure/DSGraph.h | 14 ++--- include/llvm/Analysis/DataStructure/DSNode.h | 4 +- .../llvm/Analysis/DataStructure/DSSupport.h | 14 ++--- .../Analysis/DataStructure/DataStructure.h | 23 ++++---- include/llvm/Analysis/IPModRef.h | 3 +- .../DataStructure/BottomUpClosure.cpp | 17 +++--- lib/Analysis/DataStructure/DataStructure.cpp | 55 +++++++++---------- lib/Analysis/DataStructure/IPModRef.cpp | 6 +- lib/Analysis/DataStructure/Local.cpp | 8 +-- lib/Analysis/DataStructure/Printer.cpp | 4 +- lib/Analysis/DataStructure/Steensgaard.cpp | 20 +++---- lib/Analysis/DataStructure/TopDownClosure.cpp | 6 +- lib/Analysis/IPA/IPModRef.cpp | 6 +- lib/Transforms/IPO/PoolAllocate.cpp | 12 ++-- 18 files changed, 124 insertions(+), 123 deletions(-) diff --git a/include/llvm/Analysis/DSGraph.h b/include/llvm/Analysis/DSGraph.h index 8e11dc010aa..daab1195b36 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 Nodes; - std::map ScalarMap; + hash_map 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 &NodeMap); + DSGraph(const DSGraph &DSG, hash_map &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 &getScalarMap() { return ScalarMap; } - const std::map &getScalarMap() const {return ScalarMap;} + hash_map &getScalarMap() { return ScalarMap; } + const hash_map &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::const_iterator I = ScalarMap.find(V); + hash_map::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 &OldValMap, - std::map &OldNodeMap, + hash_map &OldValMap, + hash_map &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 5edbd72f830..da8050cd9aa 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 &OldNodeMap); + void remapLinks(hash_map &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 &ReachableNodes); + void markReachableNodes(hash_set &ReachableNodes); private: friend class DSNodeHandle; diff --git a/include/llvm/Analysis/DSSupport.h b/include/llvm/Analysis/DSSupport.h index f0f261e0b9e..06bcb5eaa9f 100644 --- a/include/llvm/Analysis/DSSupport.h +++ b/include/llvm/Analysis/DSSupport.h @@ -8,10 +8,10 @@ #define LLVM_ANALYSIS_DSSUPPORT_H #include -#include -#include #include #include +#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 &NodeMap) { + const hash_map &NodeMap) { if (DSNode *N = Src.getNode()) { - std::map::const_iterator I = NodeMap.find(N); + hash_map::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 &NodeMap) { + const hash_map &NodeMap) { if (DSNode *N = Src.getNode()) { - std::map::const_iterator I = NodeMap.find(N); + hash_map::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 &Nodes); + void markReachableNodes(hash_set &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 391f95a8102..ddaf83a4592 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 +#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 DSInfo; + hash_map 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_iterator I = DSInfo.find(&F); + hash_map::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 DSInfo; + hash_map 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_iterator I = DSInfo.find(&F); + hash_map::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 &SCCFunctions); + hash_set &SCCFunctions); DSGraph &calculateSCCGraph(Function &F, - std::set &InlinedSCCFunctions); + hash_set &InlinedSCCFunctions); void calculateReachableGraphs(Function *F); @@ -121,7 +122,7 @@ private: unsigned calculateGraphs(Function *F, std::vector &Stack, unsigned &NextID, - std::map &ValMap); + hash_map &ValMap); }; @@ -131,8 +132,8 @@ private: // class TDDataStructures : public Pass { // DSInfo, one graph for each function - std::map DSInfo; - std::set GraphDone; + hash_map DSInfo; + hash_set 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_iterator I = DSInfo.find(&F); + hash_map::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 8e11dc010aa..daab1195b36 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 Nodes; - std::map ScalarMap; + hash_map 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 &NodeMap); + DSGraph(const DSGraph &DSG, hash_map &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 &getScalarMap() { return ScalarMap; } - const std::map &getScalarMap() const {return ScalarMap;} + hash_map &getScalarMap() { return ScalarMap; } + const hash_map &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::const_iterator I = ScalarMap.find(V); + hash_map::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 &OldValMap, - std::map &OldNodeMap, + hash_map &OldValMap, + hash_map &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 5edbd72f830..da8050cd9aa 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 &OldNodeMap); + void remapLinks(hash_map &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 &ReachableNodes); + void markReachableNodes(hash_set &ReachableNodes); private: friend class DSNodeHandle; diff --git a/include/llvm/Analysis/DataStructure/DSSupport.h b/include/llvm/Analysis/DataStructure/DSSupport.h index f0f261e0b9e..06bcb5eaa9f 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 -#include -#include #include #include +#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 &NodeMap) { + const hash_map &NodeMap) { if (DSNode *N = Src.getNode()) { - std::map::const_iterator I = NodeMap.find(N); + hash_map::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 &NodeMap) { + const hash_map &NodeMap) { if (DSNode *N = Src.getNode()) { - std::map::const_iterator I = NodeMap.find(N); + hash_map::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 &Nodes); + void markReachableNodes(hash_set &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 391f95a8102..ddaf83a4592 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 +#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 DSInfo; + hash_map 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_iterator I = DSInfo.find(&F); + hash_map::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 DSInfo; + hash_map 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_iterator I = DSInfo.find(&F); + hash_map::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 &SCCFunctions); + hash_set &SCCFunctions); DSGraph &calculateSCCGraph(Function &F, - std::set &InlinedSCCFunctions); + hash_set &InlinedSCCFunctions); void calculateReachableGraphs(Function *F); @@ -121,7 +122,7 @@ private: unsigned calculateGraphs(Function *F, std::vector &Stack, unsigned &NextID, - std::map &ValMap); + hash_map &ValMap); }; @@ -131,8 +132,8 @@ private: // class TDDataStructures : public Pass { // DSInfo, one graph for each function - std::map DSInfo; - std::set GraphDone; + hash_map DSInfo; + hash_set 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_iterator I = DSInfo.find(&F); + hash_map::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 1b472e91f9e..eed264f9785 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 &NodeMap); + hash_map &NodeMap); public: /* ctor */ FunctionModRefInfo (const Function& func, diff --git a/lib/Analysis/DataStructure/BottomUpClosure.cpp b/lib/Analysis/DataStructure/BottomUpClosure.cpp index 26b7813482e..8fa331c92d1 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 Stack; - std::map ValMap; + hash_map 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 &Stack, unsigned &NextID, - std::map &ValMap) { + hash_map &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::iterator It = ValMap.find(Callee); + hash_map::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 SCCFunctions; + hash_set SCCFunctions; Function *NF; std::vector::iterator FirstInSCC = Stack.end(); @@ -283,7 +284,7 @@ unsigned BUDataStructures::calculateGraphs(Function *F, // our memory... here... // void BUDataStructures::releaseMemory() { - for (std::map::iterator I = DSInfo.begin(), + for (hash_map::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 &SCCFunctions){ + hash_set &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 &SCCFunctions){ + hash_set &SCCFunctions){ DSGraph &Graph = getDSGraph(F); DEBUG(std::cerr << " [BU] Calculating SCC graph for: " << F.getName()<<"\n"); std::vector UnresolvableCalls; - std::map SCCCallSiteMap; + hash_map SCCCallSiteMap; std::vector &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 797eb19a19b..1dbabb7f1b5 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 NodeMap; + hash_map NodeMap; RetNode = cloneInto(G, ScalarMap, NodeMap); } DSGraph::DSGraph(const DSGraph &G, - std::map &NodeMap) + hash_map &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 &OldNodeMap) { +void DSNode::remapLinks(hash_map &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 &OldNodeMap) { // calling function's graph. // DSNodeHandle DSGraph::cloneInto(const DSGraph &G, - std::map &OldValMap, - std::map &OldNodeMap, + hash_map &OldValMap, + hash_map &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::const_iterator I = G.ScalarMap.begin(), + for (hash_map::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(I->first)) { // Is this a global? - std::map::iterator GVI = ScalarMap.find(I->first); + hash_map::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 OldValMap; + hash_map OldValMap; DSNodeHandle RetVal; - std::map *ScalarMap = &OldValMap; + hash_map *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 OldNodeMap; + hash_map 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 &ScalarMap) { + hash_map &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 &ReachableNodes) { +void DSNode::markReachableNodes(hash_set &ReachableNodes) { if (this == 0) return; - std::set::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 &Nodes) { +void DSCallSite::markReachableNodes(hash_set &Nodes) { getRetVal().getNode()->markReachableNodes(Nodes); getCallee().getNode()->markReachableNodes(Nodes); @@ -965,8 +963,8 @@ void DSCallSite::markReachableNodes(std::set &Nodes) { // // This function returns true if the specified node is alive. // -static bool markAliveIfCanReachAlive(DSNode *N, std::set &Alive, - std::set &Visited) { +static bool markAliveIfCanReachAlive(DSNode *N, hash_set &Alive, + hash_set &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 &Alive, // Otherwise, we don't think the node is alive yet, check for infinite // recursion. - std::set::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 &Alive, return ChildrenAreAlive; } -static bool CallSiteUsesAliveArgs(DSCallSite &CS, std::set &Alive, - std::set &Visited) { +static bool CallSiteUsesAliveArgs(DSCallSite &CS, hash_set &Alive, + hash_set &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 Alive; + hash_set Alive; std::vector > GlobalNodes; // Mark all nodes reachable by (non-global) scalar nodes as alive... - for (std::map::iterator I = ScalarMap.begin(), + for (hash_map::iterator I = ScalarMap.begin(), E = ScalarMap.end(); I != E; ++I) if (!isa(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 Visited; + hash_set 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 &NodeCache, + hash_map &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 NodeCache; + hash_map NodeCache; std::vector& FromCalls =Graph.FunctionCalls; FunctionCalls.reserve(FunctionCalls.size() + FromCalls.size()); diff --git a/lib/Analysis/DataStructure/IPModRef.cpp b/lib/Analysis/DataStructure/IPModRef.cpp index 48452fe8b16..e04e1094500 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 &NodeMap) + hash_map &NodeMap) { // Step #0: Quick check if we are going to fail anyway: avoid // all the graph cloning and map copying in steps #1 and #2. @@ -194,7 +194,7 @@ FunctionModRefInfo::computeModRef(const CallInst& callInst) callSiteModRefInfo[&callInst] = callModRefInfo; // Get a copy of the graph for the callee with the callee inlined - std::map NodeMap; + hash_map NodeMap; DSGraph* csgp = ResolveCallSiteModRefInfo(const_cast(callInst), NodeMap); if (!csgp) @@ -238,7 +238,7 @@ public: knownValues.resize(tdGraph.getGraphSize()); // For every identifiable value, save Value pointer in knownValues[i] - for (std::map::const_iterator + for (hash_map::const_iterator I = tdGraph.getScalarMap().begin(), E = tdGraph.getScalarMap().end(); I != E; ++I) if (isa(I->first) || diff --git a/lib/Analysis/DataStructure/Local.cpp b/lib/Analysis/DataStructure/Local.cpp index b6e468c87c3..3308fd195bb 100644 --- a/lib/Analysis/DataStructure/Local.cpp +++ b/lib/Analysis/DataStructure/Local.cpp @@ -56,12 +56,12 @@ namespace { DSGraph &G; std::vector &Nodes; DSNodeHandle &RetNode; // Node that gets returned... - std::map &ScalarMap; + hash_map &ScalarMap; std::vector &FunctionCalls; public: GraphBuilder(DSGraph &g, std::vector &nodes, DSNodeHandle &retNode, - std::map &SM, + hash_map &SM, std::vector &fc) : G(g), Nodes(nodes), RetNode(retNode), ScalarMap(SM), FunctionCalls(fc) { @@ -166,7 +166,7 @@ DSNodeHandle GraphBuilder::getValueDest(Value &Val) { return NH = getValueDest(*CE->getOperand(0)); if (CE->getOpcode() == Instruction::GetElementPtr) { visitGetElementPtrInst(*CE); - std::map::iterator I = ScalarMap.find(CE); + hash_map::iterator I = ScalarMap.find(CE); assert(I != ScalarMap.end() && "GEP didn't get processed right?"); return NH = I->second; } @@ -431,7 +431,7 @@ bool LocalDataStructures::run(Module &M) { // our memory... here... // void LocalDataStructures::releaseMemory() { - for (std::map::iterator I = DSInfo.begin(), + for (hash_map::iterator I = DSInfo.begin(), E = DSInfo.end(); I != E; ++I) delete I->second; diff --git a/lib/Analysis/DataStructure/Printer.cpp b/lib/Analysis/DataStructure/Printer.cpp index e9b5a179728..baff12bac02 100644 --- a/lib/Analysis/DataStructure/Printer.cpp +++ b/lib/Analysis/DataStructure/Printer.cpp @@ -87,8 +87,8 @@ struct DOTGraphTraits : public DefaultDOTGraphTraits { static void addCustomGraphFeatures(const DSGraph *G, GraphWriter &GW) { // Add scalar nodes to the graph... - const std::map &VM = G->getScalarMap(); - for (std::map::const_iterator I = VM.begin(); + const hash_map &VM = G->getScalarMap(); + for (hash_map::const_iterator I = VM.begin(); I != VM.end(); ++I) if (!isa(I->first)) { std::stringstream OS; diff --git a/lib/Analysis/DataStructure/Steensgaard.cpp b/lib/Analysis/DataStructure/Steensgaard.cpp index b6497c50722..88ebdb72b97 100644 --- a/lib/Analysis/DataStructure/Steensgaard.cpp +++ b/lib/Analysis/DataStructure/Steensgaard.cpp @@ -89,7 +89,7 @@ void Steens::ResolveFunctionCall(Function *F, const DSCallSite &Call, DSNodeHandle &RetVal) { assert(ResultGraph != 0 && "Result graph not allocated!"); - std::map &ValMap = ResultGraph->getScalarMap(); + hash_map &ValMap = ResultGraph->getScalarMap(); // Handle the return value of the function... if (Call.getRetVal().getNode() && RetVal.getNode()) @@ -98,7 +98,7 @@ void Steens::ResolveFunctionCall(Function *F, // Loop over all pointer arguments, resolving them to their provided pointers unsigned PtrArgIdx = 0; for (Function::aiterator AI = F->abegin(), AE = F->aend(); AI != AE; ++AI) { - std::map::iterator I = ValMap.find(AI); + hash_map::iterator I = ValMap.find(AI); if (I != ValMap.end()) // If its a pointer argument... I->second.addEdgeTo(Call.getPtrArg(PtrArgIdx++)); } @@ -120,16 +120,16 @@ bool Steens::run(Module &M) { // RetValMap - Keep track of the return values for all functions that return // valid pointers. // - std::map RetValMap; + hash_map RetValMap; // Loop over the rest of the module, merging graphs for non-external functions // into this graph. // for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) if (!I->isExternal()) { - std::map ValMap; + hash_map ValMap; { // Scope to free NodeMap memory ASAP - std::map NodeMap; + hash_map NodeMap; const DSGraph &FDSG = LDS.getDSGraph(*I); DSNodeHandle RetNode = ResultGraph->cloneInto(FDSG, ValMap, NodeMap); @@ -142,11 +142,11 @@ bool Steens::run(Module &M) { // Incorporate the inlined Function's ScalarMap into the global // ScalarMap... - std::map &GVM = ResultGraph->getScalarMap(); + hash_map &GVM = ResultGraph->getScalarMap(); while (!ValMap.empty()) { // Loop over value map, moving entries over... const std::pair &DSN = *ValMap.begin(); - std::map::iterator I = GVM.find(DSN.first); + hash_map::iterator I = GVM.find(DSN.first); if (I == GVM.end()) GVM[DSN.first] = DSN.second; else @@ -209,12 +209,12 @@ bool Steens::run(Module &M) { AliasAnalysis::Result Steens::alias(const Value *V1, const Value *V2) { assert(ResultGraph && "Result graph has not been computed yet!"); - std::map &GVM = ResultGraph->getScalarMap(); + hash_map &GVM = ResultGraph->getScalarMap(); - std::map::iterator I = GVM.find(const_cast(V1)); + hash_map::iterator I = GVM.find(const_cast(V1)); if (I != GVM.end() && I->second.getNode()) { DSNodeHandle &V1H = I->second; - std::map::iterator J=GVM.find(const_cast(V2)); + hash_map::iterator J=GVM.find(const_cast(V2)); if (J != GVM.end() && J->second.getNode()) { DSNodeHandle &V2H = J->second; // If the two pointers point to different data structure graph nodes, they diff --git a/lib/Analysis/DataStructure/TopDownClosure.cpp b/lib/Analysis/DataStructure/TopDownClosure.cpp index b867f7edff8..367f6a1d270 100644 --- a/lib/Analysis/DataStructure/TopDownClosure.cpp +++ b/lib/Analysis/DataStructure/TopDownClosure.cpp @@ -40,7 +40,7 @@ bool TDDataStructures::run(Module &M) { // our memory... here... // void TDDataStructures::releaseMemory() { - for (std::map::iterator I = DSInfo.begin(), + for (hash_map::iterator I = DSInfo.begin(), E = DSInfo.end(); I != E; ++I) delete I->second; @@ -140,8 +140,8 @@ void TDDataStructures::calculateGraph(Function &F) { << "'\n"); // Clone our current graph into the callee... - std::map OldValMap; - std::map OldNodeMap; + hash_map OldValMap; + hash_map OldNodeMap; CG.cloneInto(Graph, OldValMap, OldNodeMap, DSGraph::StripModRefBits | DSGraph::KeepAllocaBit | DSGraph::DontCloneCallNodes); diff --git a/lib/Analysis/IPA/IPModRef.cpp b/lib/Analysis/IPA/IPModRef.cpp index 48452fe8b16..e04e1094500 100644 --- a/lib/Analysis/IPA/IPModRef.cpp +++ b/lib/Analysis/IPA/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 &NodeMap) + hash_map &NodeMap) { // Step #0: Quick check if we are going to fail anyway: avoid // all the graph cloning and map copying in steps #1 and #2. @@ -194,7 +194,7 @@ FunctionModRefInfo::computeModRef(const CallInst& callInst) callSiteModRefInfo[&callInst] = callModRefInfo; // Get a copy of the graph for the callee with the callee inlined - std::map NodeMap; + hash_map NodeMap; DSGraph* csgp = ResolveCallSiteModRefInfo(const_cast(callInst), NodeMap); if (!csgp) @@ -238,7 +238,7 @@ public: knownValues.resize(tdGraph.getGraphSize()); // For every identifiable value, save Value pointer in knownValues[i] - for (std::map::const_iterator + for (hash_map::const_iterator I = tdGraph.getScalarMap().begin(), E = tdGraph.getScalarMap().end(); I != E; ++I) if (isa(I->first) || diff --git a/lib/Transforms/IPO/PoolAllocate.cpp b/lib/Transforms/IPO/PoolAllocate.cpp index 6857c6ec965..371c5a00937 100644 --- a/lib/Transforms/IPO/PoolAllocate.cpp +++ b/lib/Transforms/IPO/PoolAllocate.cpp @@ -43,7 +43,7 @@ namespace { /// MarkedNodes - The set of nodes which are not locally pool allocatable in /// the current function. /// - std::set MarkedNodes; + hash_set MarkedNodes; /// Clone - The cloned version of the function, if applicable. Function *Clone; @@ -204,7 +204,7 @@ Function *PA::MakeFunctionClone(Function &F) { // Find DataStructure nodes which are allocated in pools non-local to the // current function. This set will contain all of the DSNodes which require // pools to be passed in from outside of the function. - std::set &MarkedNodes = FI.MarkedNodes; + hash_set &MarkedNodes = FI.MarkedNodes; // Mark globals and incomplete nodes as live... (this handles arguments) if (F.getName() != "main") @@ -225,7 +225,7 @@ Function *PA::MakeFunctionClone(Function &F) { ArgTys.reserve(OldFuncTy->getParamTypes().size() + MarkedNodes.size()); FI.ArgNodes.reserve(MarkedNodes.size()); - for (std::set::iterator I = MarkedNodes.begin(), + for (hash_set::iterator I = MarkedNodes.begin(), E = MarkedNodes.end(); I != E; ++I) if ((*I)->NodeType & DSNode::Incomplete) { ArgTys.push_back(PoolDescPtr); // Add the appropriate # of pool descs @@ -289,7 +289,7 @@ void PA::ProcessFunctionBody(Function &F, Function &NewF) { if (Nodes.empty()) return; // Quick exit if nothing to do... FuncInfo &FI = FunctionInfo[&F]; // Get FuncInfo for F - std::set &MarkedNodes = FI.MarkedNodes; + hash_set &MarkedNodes = FI.MarkedNodes; DEBUG(std::cerr << "[" << F.getName() << "] Pool Allocate: "); @@ -414,8 +414,8 @@ void FuncTransform::visitMallocInst(MallocInst &MI) { // Remove old malloc instruction MI.getParent()->getInstList().erase(&MI); - std::map &SM = G.getScalarMap(); - std::map::iterator MII = SM.find(&MI); + hash_map &SM = G.getScalarMap(); + hash_map::iterator MII = SM.find(&MI); // If we are modifying the original function, update the DSGraph... if (MII != SM.end()) { -- 2.34.1