From fccd06fceac144c8c7825d41cefc55f8754a53f8 Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Tue, 1 Oct 2002 22:33:50 +0000 Subject: [PATCH] Checkin some major reworks of data structure analysis. This is not done, nor does it work very well, but I need to get it checked in before I break the tree unintentionally. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@3996 91177308-0d34-0410-b5e6-96231b3b80d8 --- .../DataStructure/BottomUpClosure.cpp | 5 +- lib/Analysis/DataStructure/DataStructure.cpp | 426 +++++++++++------- lib/Analysis/DataStructure/Local.cpp | 350 ++++++++------ lib/Analysis/DataStructure/Printer.cpp | 90 ++-- lib/Analysis/DataStructure/TopDownClosure.cpp | 4 +- 5 files changed, 522 insertions(+), 353 deletions(-) diff --git a/lib/Analysis/DataStructure/BottomUpClosure.cpp b/lib/Analysis/DataStructure/BottomUpClosure.cpp index 2ab97442d18..c3d19d4bc22 100644 --- a/lib/Analysis/DataStructure/BottomUpClosure.cpp +++ b/lib/Analysis/DataStructure/BottomUpClosure.cpp @@ -10,10 +10,12 @@ #include "llvm/Analysis/DataStructure.h" #include "llvm/Module.h" #include "llvm/DerivedTypes.h" -#include "Support/StatisticReporter.h" +#include "Support/Statistic.h" #include using std::map; +#if 0 + static RegisterAnalysis X("budatastructure", "Bottom-up Data Structure Analysis Closure"); @@ -240,3 +242,4 @@ DSGraph &BUDataStructures::calculateGraph(Function &F) { return *Graph; } +#endif diff --git a/lib/Analysis/DataStructure/DataStructure.cpp b/lib/Analysis/DataStructure/DataStructure.cpp index dd936266b11..683fe46b4c9 100644 --- a/lib/Analysis/DataStructure/DataStructure.cpp +++ b/lib/Analysis/DataStructure/DataStructure.cpp @@ -4,35 +4,43 @@ // //===----------------------------------------------------------------------===// -#include "llvm/Analysis/DataStructure.h" -#include "llvm/Module.h" +#include "llvm/Analysis/DSGraph.h" +#include "llvm/Function.h" #include "llvm/DerivedTypes.h" #include "Support/STLExtras.h" -#include "Support/StatisticReporter.h" -#include "Support/STLExtras.h" +#include "Support/Statistic.h" +#include "llvm/Target/TargetData.h" #include +#include using std::vector; +// TODO: FIXME +namespace DataStructureAnalysis { + // isPointerType - Return true if this first class type is big enough to hold + // a pointer. + // + bool isPointerType(const Type *Ty); + extern TargetData TD; +} +using namespace DataStructureAnalysis; + //===----------------------------------------------------------------------===// // DSNode Implementation //===----------------------------------------------------------------------===// -DSNode::DSNode(enum NodeTy NT, const Type *T) : Ty(T), NodeType(NT) { - // If this node has any fields, allocate them now, but leave them null. - switch (T->getPrimitiveID()) { - case Type::PointerTyID: Links.resize(1); break; - case Type::ArrayTyID: Links.resize(1); break; - case Type::StructTyID: - Links.resize(cast(T)->getNumContainedTypes()); - break; - default: break; - } +DSNode::DSNode(enum NodeTy NT, const Type *T) : NodeType(NT) { + // If this node is big enough to have pointer fields, add space for them now. + if (T != Type::VoidTy && !isa(T)) // Avoid TargetData assert's + LinkIndex.resize(TD.getTypeSize(T), -1); + + TypeEntries.push_back(std::make_pair(T, 0)); } // DSNode copy constructor... do not copy over the referrers list! DSNode::DSNode(const DSNode &N) - : Ty(N.Ty), Links(N.Links), Globals(N.Globals), NodeType(N.NodeType) { + : Links(N.Links), LinkIndex(N.LinkIndex), + TypeEntries(N.TypeEntries), Globals(N.Globals), NodeType(N.NodeType) { } void DSNode::removeReferrer(DSNodeHandle *H) { @@ -53,7 +61,7 @@ void DSNode::addGlobal(GlobalValue *GV) { std::lower_bound(Globals.begin(), Globals.end(), GV); if (I == Globals.end() || *I != GV) { - assert(GV->getType()->getElementType() == Ty); + //assert(GV->getType()->getElementType() == Ty); Globals.insert(I, GV); NodeType |= GlobalNode; } @@ -63,58 +71,154 @@ void DSNode::addGlobal(GlobalValue *GV) { // addEdgeTo - Add an edge from the current node to the specified node. This // can cause merging of nodes in the graph. // -void DSNode::addEdgeTo(unsigned LinkNo, DSNode *N) { - assert(LinkNo < Links.size() && "LinkNo out of range!"); - if (N == 0 || Links[LinkNo] == N) return; // Nothing to do - if (Links[LinkNo] == 0) { // No merging to perform - Links[LinkNo] = N; +void DSNode::addEdgeTo(unsigned Offset, const DSNodeHandle &NH) { + assert(Offset < LinkIndex.size() && "Offset out of range!"); + if (NH.getNode() == 0) return; // Nothing to do + + if (LinkIndex[Offset] == -1) { // No merging to perform... + LinkIndex[Offset] = Links.size(); // Allocate a new link... + Links.push_back(NH); + return; + } + + unsigned Idx = (unsigned)LinkIndex[Offset]; + if (!Links[Idx].getNode()) { // No merging to perform + Links[Idx] = NH; return; } // Merge the two nodes... - Links[LinkNo]->mergeWith(N); + Links[Idx].mergeWith(NH); } -// mergeWith - Merge this node into the specified node, moving all links to and -// from the argument node into the current node. The specified node may be a -// null pointer (in which case, nothing happens). +// MergeSortedVectors - Efficiently merge a vector into another vector where +// duplicates are not allowed and both are sorted. This assumes that 'T's are +// efficiently copyable and have sane comparison semantics. // -void DSNode::mergeWith(DSNode *N) { - if (N == 0 || N == this) return; // Noop - assert(N->Ty == Ty && N->Links.size() == Links.size() && - "Cannot merge nodes of two different types!"); +template +void MergeSortedVectors(vector &Dest, const vector &Src) { + // By far, the most common cases will be the simple ones. In these cases, + // avoid having to allocate a temporary vector... + // + if (Src.empty()) { // Nothing to merge in... + return; + } else if (Dest.empty()) { // Just copy the result in... + Dest = Src; + } else if (Src.size() == 1) { // Insert a single element... + const T &V = Src[0]; + typename vector::iterator I = + std::lower_bound(Dest.begin(), Dest.end(), V); + if (I == Dest.end() || *I != Src[0]) // If not already contained... + Dest.insert(I, Src[0]); + } else if (Dest.size() == 1) { + T Tmp = Dest[0]; // Save value in temporary... + Dest = Src; // Copy over list... + typename vector::iterator I = + std::lower_bound(Dest.begin(), Dest.end(),Tmp); + if (I == Dest.end() || *I != Src[0]) // If not already contained... + Dest.insert(I, Src[0]); + + } else { + // Make a copy to the side of Dest... + vector Old(Dest); + + // Make space for all of the type entries now... + Dest.resize(Dest.size()+Src.size()); + + // Merge the two sorted ranges together... into Dest. + std::merge(Old.begin(), Old.end(), Src.begin(), Src.end(), Dest.begin()); + + // Now erase any duplicate entries that may have accumulated into the + // vectors (because they were in both of the input sets) + Dest.erase(std::unique(Dest.begin(), Dest.end()), Dest.end()); + } +} + + +// mergeWith - Merge this node and the specified node, moving all links to and +// from the argument node into the current node, deleting the node argument. +// Offset indicates what offset the specified node is to be merged into the +// current node. +// +// The specified node may be a null pointer (in which case, nothing happens). +// +void DSNode::mergeWith(const DSNodeHandle &NH, unsigned Offset) { + DSNode *N = NH.getNode(); + if (N == 0 || (N == this && NH.getOffset() == Offset)) + return; // Noop + + assert(NH.getNode() != this && + "Cannot merge two portions of the same node yet!"); + + // If both nodes are not at offset 0, make sure that we are merging the node + // at an later offset into the node with the zero offset. + // + if (Offset > NH.getOffset()) { + N->mergeWith(DSNodeHandle(this, Offset), NH.getOffset()); + return; + } + +#if 0 + std::cerr << "\n\nMerging:\n"; + N->print(std::cerr, 0); + std::cerr << " and:\n"; + print(std::cerr, 0); +#endif + + // Now we know that Offset <= NH.Offset, so convert it so our "Offset" (with + // respect to NH.Offset) is now zero. + // + unsigned NOffset = NH.getOffset()-Offset; // Remove all edges pointing at N, causing them to point to 'this' instead. - while (!N->Referrers.empty()) - *N->Referrers.back() = this; + // Make sure to adjust their offset, not just the node pointer. + // + while (!N->Referrers.empty()) { + DSNodeHandle &Ref = *N->Referrers.back(); + Ref = DSNodeHandle(this, NOffset+Ref.getOffset()); + } // Make all of the outgoing links of N now be outgoing links of this. This // can cause recursive merging! // - for (unsigned i = 0, e = Links.size(); i != e; ++i) { - addEdgeTo(i, N->Links[i]); - N->Links[i] = 0; // Reduce unneccesary edges in graph. N is dead - } + for (unsigned i = 0, e = N->LinkIndex.size(); i != e; ++i) + if (N->LinkIndex[i] != -1) { + addEdgeTo(i+NOffset, N->Links[N->LinkIndex[i]]); + N->LinkIndex[i] = -1; // Reduce unneccesary edges in graph. N is dead + } + + // Now that there are no outgoing edges, all of the Links are dead. + N->Links.clear(); // Merge the node types NodeType |= N->NodeType; N->NodeType = 0; // N is now a dead node. - // Merge the globals list... - if (!N->Globals.empty()) { - // Save the current globals off to the side... - vector OldGlobals(Globals); + // If this merging into node has more than just void nodes in it, merge! + assert(!N->TypeEntries.empty() && "TypeEntries is empty for a node?"); + if (N->TypeEntries.size() != 1 || N->TypeEntries[0].first != Type::VoidTy) { + // If the current node just has a Void entry in it, remove it. + if (TypeEntries.size() == 1 && TypeEntries[0].first == Type::VoidTy) + TypeEntries.clear(); + + // Adjust all of the type entries we are merging in by the offset... and add + // them to the TypeEntries list. + // + if (NOffset != 0) { // This case is common enough to optimize for + // Offset all of the TypeEntries in N with their new offset + for (unsigned i = 0, e = N->TypeEntries.size(); i != e; ++i) + N->TypeEntries[i].second += NOffset; + } - // Resize the globals vector to be big enough to hold both of them... - Globals.resize(Globals.size()+N->Globals.size()); + MergeSortedVectors(TypeEntries, N->TypeEntries); - // Merge the two sorted globals lists together... - std::merge(OldGlobals.begin(), OldGlobals.end(), - N->Globals.begin(), N->Globals.end(), Globals.begin()); + N->TypeEntries.clear(); + } - // Erase duplicate entries from the globals list... - Globals.erase(std::unique(Globals.begin(), Globals.end()), Globals.end()); + // Merge the globals list... + if (!N->Globals.empty()) { + MergeSortedVectors(Globals, N->Globals); // Delete the globals from the old node... N->Globals.clear(); @@ -125,16 +229,13 @@ void DSNode::mergeWith(DSNode *N) { // DSGraph Implementation //===----------------------------------------------------------------------===// -DSGraph::DSGraph(const DSGraph &G) : Func(G.Func), GlobalsGraph(G.GlobalsGraph){ - GlobalsGraph->addReference(this); - std::map NodeMap; // ignored +DSGraph::DSGraph(const DSGraph &G) : Func(G.Func) { + std::map NodeMap; RetNode = cloneInto(G, ValueMap, NodeMap); } DSGraph::~DSGraph() { - GlobalsGraph->removeReference(this); FunctionCalls.clear(); - OrigFunctionCalls.clear(); ValueMap.clear(); RetNode = 0; @@ -151,24 +252,31 @@ DSGraph::~DSGraph() { // dump - Allow inspection of graph in a debugger. void DSGraph::dump() const { print(std::cerr); } - // Helper function used to clone a function list. -// Each call really shd have an explicit representation as a separate class. -void -CopyFunctionCallsList(const std::vector >& fromCalls, - std::vector >& toCalls, - std::map& NodeMap) { - +// +static void CopyFunctionCallsList(const vector >&fromCalls, + vector > &toCalls, + std::map &NodeMap) { + unsigned FC = toCalls.size(); // FirstCall toCalls.reserve(FC+fromCalls.size()); for (unsigned i = 0, ei = fromCalls.size(); i != ei; ++i) { - toCalls.push_back(std::vector()); - toCalls[FC+i].reserve(fromCalls[i].size()); + toCalls.push_back(vector()); + + const vector &CurCall = fromCalls[i]; + toCalls.back().reserve(CurCall.size()); for (unsigned j = 0, ej = fromCalls[i].size(); j != ej; ++j) - toCalls[FC+i].push_back(NodeMap[fromCalls[i][j]]); + toCalls[FC+i].push_back(DSNodeHandle(NodeMap[CurCall[j].getNode()], + CurCall[j].getOffset())); } } +/// remapLinks - Change all of the Links in the current node according to the +/// specified mapping. +void DSNode::remapLinks(std::map &OldNodeMap) { + for (unsigned i = 0, e = Links.size(); i != e; ++i) + Links[i].setNode(OldNodeMap[Links[i].getNode()]); +} // cloneInto - Clone the specified DSGraph into the current graph, returning the // Return node of the graph. The translated ValueMap for the old function is @@ -176,62 +284,61 @@ CopyFunctionCallsList(const std::vector >& fromCalls, // Alloca markers are removed from the graph, as the graph is being cloned into // a calling function's graph. // -DSNode *DSGraph::cloneInto(const DSGraph &G, - std::map &OldValMap, - std::map &OldNodeMap, - bool StripScalars, bool StripAllocas, - bool CopyCallers, bool CopyOrigCalls) { - - assert(OldNodeMap.size()==0 && "Return arg. OldNodeMap shd be empty"); - - OldNodeMap[0] = 0; // Null pointer maps to null +DSNodeHandle DSGraph::cloneInto(const DSGraph &G, + std::map &OldValMap, + std::map &OldNodeMap, + bool StripScalars, bool StripAllocas, + bool CopyCallers, bool CopyOrigCalls) { + assert(OldNodeMap.empty() && "Returned OldNodeMap should be empty!"); unsigned FN = Nodes.size(); // First new node... // Duplicate all of the nodes, populating the node map... Nodes.reserve(FN+G.Nodes.size()); for (unsigned i = 0, e = G.Nodes.size(); i != e; ++i) { - DSNode *Old = G.Nodes[i], *New = new DSNode(*Old); + DSNode *Old = G.Nodes[i]; + DSNode *New = new DSNode(*Old); Nodes.push_back(New); OldNodeMap[Old] = New; } // Rewrite the links in the new nodes to point into the current graph now. for (unsigned i = FN, e = Nodes.size(); i != e; ++i) - for (unsigned j = 0, e = Nodes[i]->getNumLinks(); j != e; ++j) - Nodes[i]->setLink(j, OldNodeMap.find(Nodes[i]->getLink(j))->second); + Nodes[i]->remapLinks(OldNodeMap); // Remove local markers as specified - if (StripScalars || StripAllocas) { - char keepBits = ~((StripScalars? DSNode::ScalarNode : 0) | - (StripAllocas? DSNode::AllocaNode : 0)); + unsigned char StripBits = (StripScalars ? DSNode::ScalarNode : 0) | + (StripAllocas ? DSNode::AllocaNode : 0); + if (StripBits) for (unsigned i = FN, e = Nodes.size(); i != e; ++i) - Nodes[i]->NodeType &= keepBits; - } + Nodes[i]->NodeType &= ~StripBits; // Copy the value map... for (std::map::const_iterator I = G.ValueMap.begin(), E = G.ValueMap.end(); I != E; ++I) - OldValMap[I->first] = OldNodeMap[I->second]; - + OldValMap[I->first] = DSNodeHandle(OldNodeMap[I->second.getNode()], + I->second.getOffset()); // Copy the function calls list... CopyFunctionCallsList(G.FunctionCalls, FunctionCalls, OldNodeMap); + +#if 0 if (CopyOrigCalls) CopyFunctionCallsList(G.OrigFunctionCalls, OrigFunctionCalls, OldNodeMap); // Copy the list of unresolved callers if (CopyCallers) PendingCallers.insert(G.PendingCallers.begin(), G.PendingCallers.end()); +#endif // Return the returned node pointer... - return OldNodeMap[G.RetNode]; + return DSNodeHandle(OldNodeMap[G.RetNode.getNode()], G.RetNode.getOffset()); } - +#if 0 // cloneGlobalInto - Clone the given global node and all its target links // (and all their llinks, recursively). // -DSNode* DSGraph::cloneGlobalInto(const DSNode* GNode) { +DSNode *DSGraph::cloneGlobalInto(const DSNode *GNode) { if (GNode == 0 || GNode->getGlobals().size() == 0) return 0; // If a clone has already been created for GNode, return it. @@ -252,6 +359,7 @@ DSNode* DSGraph::cloneGlobalInto(const DSNode* GNode) { return NewNode; } +#endif // markIncompleteNodes - Mark the specified node as having contents that are not @@ -268,8 +376,9 @@ static void markIncompleteNode(DSNode *N) { N->NodeType |= DSNode::Incomplete; // Recusively process children... - for (unsigned i = 0, e = N->getNumLinks(); i != e; ++i) - markIncompleteNode(N->getLink(i)); + for (unsigned i = 0, e = N->getSize(); i != e; ++i) + if (DSNodeHandle *DSNH = N->getLink(i)) + markIncompleteNode(DSNH->getNode()); } @@ -285,37 +394,41 @@ static void markIncompleteNode(DSNode *N) { // void DSGraph::markIncompleteNodes(bool markFormalArgs) { // Mark any incoming arguments as incomplete... - if (markFormalArgs) - for (Function::aiterator I = Func.abegin(), E = Func.aend(); I != E; ++I) - if (isa(I->getType())) - markIncompleteNode(ValueMap[I]->getLink(0)); + if (markFormalArgs && Func) + for (Function::aiterator I = Func->abegin(), E = Func->aend(); I != E; ++I) + if (isPointerType(I->getType()) && ValueMap.find(I) != ValueMap.end()) { + DSNodeHandle &INH = ValueMap[I]; + if (INH.getNode() && INH.hasLink(0)) + markIncompleteNode(ValueMap[I].getLink(0)->getNode()); + } // Mark stuff passed into functions calls as being incomplete... for (unsigned i = 0, e = FunctionCalls.size(); i != e; ++i) { vector &Args = FunctionCalls[i]; // Then the return value is certainly incomplete! - markIncompleteNode(Args[0]); + markIncompleteNode(Args[0].getNode()); // The call does not make the function argument incomplete... // All arguments to the function call are incomplete though! for (unsigned i = 2, e = Args.size(); i != e; ++i) - markIncompleteNode(Args[i]); + markIncompleteNode(Args[i].getNode()); } // Mark all of the nodes pointed to by global or cast nodes as incomplete... for (unsigned i = 0, e = Nodes.size(); i != e; ++i) - if (Nodes[i]->NodeType & (DSNode::GlobalNode | DSNode::CastNode)) { + if (Nodes[i]->NodeType & DSNode::GlobalNode) { DSNode *N = Nodes[i]; - for (unsigned i = 0, e = N->getNumLinks(); i != e; ++i) - markIncompleteNode(N->getLink(i)); + for (unsigned i = 0, e = N->getSize(); i != e; ++i) + if (DSNodeHandle *DSNH = N->getLink(i)) + markIncompleteNode(DSNH->getNode()); } } // removeRefsToGlobal - Helper function that removes globals from the // ValueMap so that the referrer count will go down to zero. -static void -removeRefsToGlobal(DSNode* N, std::map& ValueMap) { +static void removeRefsToGlobal(DSNode* N, + std::map &ValueMap) { while (!N->getGlobals().empty()) { GlobalValue *GV = N->getGlobals().back(); N->getGlobals().pop_back(); @@ -336,7 +449,7 @@ bool DSGraph::isNodeDead(DSNode *N) { // Is it a function node or some other trivially unused global? if (N->NodeType != 0 && (N->NodeType & ~DSNode::GlobalNode) == 0 && - N->getNumLinks() == 0 && + N->getSize() == 0 && N->getReferrers().size() == N->getGlobals().size()) { // Remove the globals from the valuemap, so that the referrer count will go @@ -349,7 +462,7 @@ bool DSGraph::isNodeDead(DSNode *N) { return false; } -static void removeIdenticalCalls(std::vector > &Calls, +static void removeIdenticalCalls(vector > &Calls, const std::string &where) { // Remove trivially identical function calls unsigned NumFns = Calls.size(); @@ -375,38 +488,44 @@ void DSGraph::removeTriviallyDeadNodes(bool KeepAllGlobals) { Nodes.erase(Nodes.begin()+i--); // Remove from node list... } - removeIdenticalCalls(FunctionCalls, Func.getName()); + removeIdenticalCalls(FunctionCalls, Func ? Func->getName() : ""); } -// markAlive - Simple graph traverser that recursively walks the graph marking +// markAlive - Simple graph walker that recursively traverses the graph, marking // stuff to be alive. // static void markAlive(DSNode *N, std::set &Alive) { if (N == 0) return; Alive.insert(N); - for (unsigned i = 0, e = N->getNumLinks(); i != e; ++i) - if (N->getLink(i) && !Alive.count(N->getLink(i))) - markAlive(N->getLink(i), Alive); + for (unsigned i = 0, e = N->getSize(); i != e; ++i) + if (DSNodeHandle *DSNH = N->getLink(i)) + if (!Alive.count(DSNH->getNode())) + markAlive(DSNH->getNode(), Alive); } static bool checkGlobalAlive(DSNode *N, std::set &Alive, std::set &Visiting) { if (N == 0) return false; - if (Visiting.count(N) > 0) return false; // terminate recursion on a cycle + if (Visiting.count(N)) return false; // terminate recursion on a cycle Visiting.insert(N); // If any immediate successor is alive, N is alive - for (unsigned i = 0, e = N->getNumLinks(); i != e; ++i) - if (N->getLink(i) && Alive.count(N->getLink(i))) - { Visiting.erase(N); return true; } + for (unsigned i = 0, e = N->getSize(); i != e; ++i) + if (DSNodeHandle *DSNH = N->getLink(i)) + if (Alive.count(DSNH->getNode())) { + Visiting.erase(N); + return true; + } // Else if any successor reaches a live node, N is alive - for (unsigned i = 0, e = N->getNumLinks(); i != e; ++i) - if (N->getLink(i) && checkGlobalAlive(N->getLink(i), Alive, Visiting)) - { Visiting.erase(N); return true; } + for (unsigned i = 0, e = N->getSize(); i != e; ++i) + if (DSNodeHandle *DSNH = N->getLink(i)) + if (checkGlobalAlive(DSNH->getNode(), Alive, Visiting)) { + Visiting.erase(N); return true; + } Visiting.erase(N); return false; @@ -418,7 +537,7 @@ static bool checkGlobalAlive(DSNode *N, std::set &Alive, // the simple iterative loop in the first few lines below suffice. // static void markGlobalsIteration(std::set& GlobalNodes, - std::vector > &Calls, + vector > &Calls, std::set &Alive, bool FilterCalls) { @@ -444,16 +563,17 @@ static void markGlobalsIteration(std::set& GlobalNodes, for (int i = 0, ei = Calls.size(); i < ei; ++i) { bool CallIsDead = true, CallHasDeadArg = false; for (unsigned j = 0, ej = Calls[i].size(); j != ej; ++j) { - bool argIsDead = Calls[i][j] == 0 || Alive.count(Calls[i][j]) == 0; - CallHasDeadArg = CallHasDeadArg || (Calls[i][j] != 0 && argIsDead); - CallIsDead = CallIsDead && argIsDead; + bool argIsDead = Calls[i][j].getNode() == 0 || + Alive.count(Calls[i][j].getNode()) == 0; + CallHasDeadArg |= (Calls[i][j].getNode() != 0 && argIsDead); + CallIsDead &= argIsDead; } if (!CallIsDead && CallHasDeadArg) { // Some node in this call is live and another is dead. // Mark all nodes of call as live and iterate once more. recurse = true; for (unsigned j = 0, ej = Calls[i].size(); j != ej; ++j) - markAlive(Calls[i][j], Alive); + markAlive(Calls[i][j].getNode(), Alive); } } if (recurse) @@ -466,21 +586,21 @@ static void markGlobalsIteration(std::set& GlobalNodes, // can reach any other live node. Since this can produce new live nodes, // we use a simple iterative algorithm. // -static void markGlobalsAlive(DSGraph& G, std::set &Alive, +static void markGlobalsAlive(DSGraph &G, std::set &Alive, bool FilterCalls) { // Add global and cast nodes to a set so we don't walk all nodes every time std::set GlobalNodes; for (unsigned i = 0, e = G.getNodes().size(); i != e; ++i) - if (G.getNodes()[i]->NodeType & (DSNode::CastNode | DSNode::GlobalNode)) + if (G.getNodes()[i]->NodeType & DSNode::GlobalNode) GlobalNodes.insert(G.getNodes()[i]); // Add all call nodes to the same set - std::vector > &Calls = G.getFunctionCalls(); + vector > &Calls = G.getFunctionCalls(); if (FilterCalls) { for (unsigned i = 0, e = Calls.size(); i != e; ++i) for (unsigned j = 0, e = Calls[i].size(); j != e; ++j) - if (Calls[i][j]) - GlobalNodes.insert(Calls[i][j]); + if (Calls[i][j].getNode()) + GlobalNodes.insert(Calls[i][j].getNode()); } // Iterate and recurse until no new live node are discovered. @@ -497,8 +617,8 @@ static void markGlobalsAlive(DSGraph& G, std::set &Alive, if (FilterCalls) for (int ei = Calls.size(), i = ei-1; i >= 0; --i) { bool CallIsDead = true; - for (unsigned j = 0, ej= Calls[i].size(); CallIsDead && j != ej; ++j) - CallIsDead = (Alive.count(Calls[i][j]) == 0); + for (unsigned j = 0, ej = Calls[i].size(); CallIsDead && j != ej; ++j) + CallIsDead = Alive.count(Calls[i][j].getNode()) == 0; if (CallIsDead) Calls.erase(Calls.begin() + i); // remove the call entirely } @@ -526,21 +646,24 @@ void DSGraph::removeDeadNodes(bool KeepAllGlobals, bool KeepCalls) { if (KeepCalls) for (unsigned i = 0, e = FunctionCalls.size(); i != e; ++i) for (unsigned j = 0, e = FunctionCalls[i].size(); j != e; ++j) - markAlive(FunctionCalls[i][j], Alive); + markAlive(FunctionCalls[i][j].getNode(), Alive); +#if 0 for (unsigned i = 0, e = OrigFunctionCalls.size(); i != e; ++i) for (unsigned j = 0, e = OrigFunctionCalls[i].size(); j != e; ++j) - markAlive(OrigFunctionCalls[i][j], Alive); + markAlive(OrigFunctionCalls[i][j].getNode(), Alive); +#endif // Mark all nodes reachable by scalar nodes (and global nodes, if // keeping them was specified) as alive... - char keepBits = DSNode::ScalarNode | (KeepAllGlobals? DSNode::GlobalNode : 0); + unsigned char keepBits = DSNode::ScalarNode | + (KeepAllGlobals ? DSNode::GlobalNode : 0); for (unsigned i = 0, e = Nodes.size(); i != e; ++i) if (Nodes[i]->NodeType & keepBits) markAlive(Nodes[i], Alive); // The return value is alive as well... - markAlive(RetNode, Alive); + markAlive(RetNode.getNode(), Alive); // Mark all globals or cast nodes that can reach a live node as alive. // This also marks all nodes reachable from such nodes as alive. @@ -549,7 +672,7 @@ void DSGraph::removeDeadNodes(bool KeepAllGlobals, bool KeepCalls) { markGlobalsAlive(*this, Alive, ! KeepCalls); // Loop over all unreachable nodes, dropping their references... - std::vector DeadNodes; + vector DeadNodes; DeadNodes.reserve(Nodes.size()); // Only one allocation is allowed. for (unsigned i = 0; i != Nodes.size(); ++i) if (!Alive.count(Nodes[i])) { @@ -574,6 +697,7 @@ void DSGraph::maskNodeTypes(unsigned char Mask) { } +#if 0 //===----------------------------------------------------------------------===// // GlobalDSGraph Implementation //===----------------------------------------------------------------------===// @@ -601,10 +725,9 @@ void GlobalDSGraph::removeReference(const DSGraph* referrer) { } // Bits used in the next function -static const char ExternalTypeBits = (DSNode::GlobalNode | DSNode::NewNode | - DSNode::SubElement | DSNode::CastNode); - +static const char ExternalTypeBits = DSNode::GlobalNode | DSNode::NewNode; +#if 0 // GlobalDSGraph::cloneNodeInto - Clone a global node and all its externally // visible target links (and recursively their such links) into this graph. // NodeCache maps the node being cloned to its clone in the Globals graph, @@ -635,8 +758,8 @@ DSNode* GlobalDSGraph::cloneNodeInto(DSNode *OldNode, // If ValueCacheIsFinal==true, look for an existing node that has // an identical list of globals and return it if it exists. // - for (unsigned j = 0, N = OldNode->getGlobals().size(); j < N; ++j) - if (DSNode* PrevNode = ValueMap[OldNode->getGlobals()[j]]) { + for (unsigned j = 0, N = OldNode->getGlobals().size(); j != N; ++j) + if (DSNode *PrevNode = ValueMap[OldNode->getGlobals()[j]].getNode()) { if (NewNode == 0) { NewNode = PrevNode; // first existing node found if (GlobalsAreFinal && j == 0) @@ -695,14 +818,15 @@ DSNode* GlobalDSGraph::cloneNodeInto(DSNode *OldNode, // void GlobalDSGraph::cloneGlobals(DSGraph& Graph, bool CloneCalls) { std::map NodeCache; +#if 0 for (unsigned i = 0, N = Graph.Nodes.size(); i < N; ++i) if (Graph.Nodes[i]->NodeType & DSNode::GlobalNode) GlobalsGraph->cloneNodeInto(Graph.Nodes[i], NodeCache, false); - if (CloneCalls) GlobalsGraph->cloneCalls(Graph); GlobalsGraph->removeDeadNodes(/*KeepAllGlobals*/ true, /*KeepCalls*/ true); +#endif } @@ -711,12 +835,12 @@ void GlobalDSGraph::cloneGlobals(DSGraph& Graph, bool CloneCalls) { // void GlobalDSGraph::cloneCalls(DSGraph& Graph) { std::map NodeCache; - std::vector >& FromCalls =Graph.FunctionCalls; + vector >& FromCalls =Graph.FunctionCalls; FunctionCalls.reserve(FunctionCalls.size() + FromCalls.size()); for (int i = 0, ei = FromCalls.size(); i < ei; ++i) { - FunctionCalls.push_back(std::vector()); + FunctionCalls.push_back(vector()); FunctionCalls.back().reserve(FromCalls[i].size()); for (unsigned j = 0, ej = FromCalls[i].size(); j != ej; ++j) FunctionCalls.back().push_back @@ -728,34 +852,6 @@ void GlobalDSGraph::cloneCalls(DSGraph& Graph) { // remove trivially identical function calls removeIdenticalCalls(FunctionCalls, "Globals Graph"); } +#endif - -//===----------------------------------------------------------------------===// -// LocalDataStructures Implementation -//===----------------------------------------------------------------------===// - -// releaseMemory - If the pass pipeline is done with this pass, we can release -// our memory... here... -// -void LocalDataStructures::releaseMemory() { - for (std::map::iterator I = DSInfo.begin(), - E = DSInfo.end(); I != E; ++I) - delete I->second; - - // Empty map so next time memory is released, data structures are not - // re-deleted. - DSInfo.clear(); -} - -bool LocalDataStructures::run(Module &M) { - // Create a globals graph for the module. Deleted when all graphs go away. - GlobalDSGraph* GG = new GlobalDSGraph; - - // 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(*I, GG))); - - return false; -} - +#endif diff --git a/lib/Analysis/DataStructure/Local.cpp b/lib/Analysis/DataStructure/Local.cpp index e561aca2105..509825172ed 100644 --- a/lib/Analysis/DataStructure/Local.cpp +++ b/lib/Analysis/DataStructure/Local.cpp @@ -1,4 +1,4 @@ -//===- ComputeLocal.cpp - Compute a local data structure graph for a fn ---===// +//===- Local.cpp - Compute a local data structure graph for a function ----===// // // Compute the local version of the data structure graph for a function. The // external interface to this file is the DSGraph constructor. @@ -6,30 +6,55 @@ //===----------------------------------------------------------------------===// #include "llvm/Analysis/DataStructure.h" -#include "llvm/Function.h" #include "llvm/iMemory.h" #include "llvm/iTerminators.h" #include "llvm/iPHINode.h" #include "llvm/iOther.h" #include "llvm/Constants.h" -#include "llvm/GlobalVariable.h" #include "llvm/DerivedTypes.h" +#include "llvm/Function.h" +#include "llvm/GlobalVariable.h" #include "llvm/Support/InstVisitor.h" +#include "llvm/Target/TargetData.h" +#include "Support/Statistic.h" + +// FIXME: This should eventually be a FunctionPass that is automatically +// aggregated into a Pass. +// +#include "llvm/Module.h" + using std::map; using std::vector; static RegisterAnalysis X("datastructure", "Local Data Structure Analysis"); -//===----------------------------------------------------------------------===// -// GraphBuilder Class -//===----------------------------------------------------------------------===// -// -// This class is the builder class that constructs the local data structure -// graph by performing a single pass over the function in question. -// +using namespace DataStructureAnalysis; + +namespace DataStructureAnalysis { + // FIXME: Do something smarter with target data! + TargetData TD("temp-td"); + unsigned PointerSize(TD.getPointerSize()); + + // isPointerType - Return true if this type is big enough to hold a pointer. + bool isPointerType(const Type *Ty) { + if (isa(Ty)) + return true; + else if (Ty->isPrimitiveType() && Ty->isInteger()) + return Ty->getPrimitiveSize() >= PointerSize; + return false; + } +} + namespace { + //===--------------------------------------------------------------------===// + // GraphBuilder Class + //===--------------------------------------------------------------------===// + // + /// This class is the builder class that constructs the local data structure + /// graph by performing a single pass over the function in question. + /// class GraphBuilder : InstVisitor { DSGraph &G; vector &Nodes; @@ -46,8 +71,8 @@ namespace { // Create scalar nodes for all pointer arguments... for (Function::aiterator I = G.getFunction().abegin(), E = G.getFunction().aend(); I != E; ++I) - if (isa(I->getType())) - getValueNode(*I); + if (isPointerType(I->getType())) + getValueDest(*I); visit(G.getFunction()); // Single pass over the function @@ -71,51 +96,51 @@ namespace { void visitCallInst(CallInst &CI); void visitSetCondInst(SetCondInst &SCI) {} // SetEQ & friends are ignored void visitFreeInst(FreeInst &FI) {} // Ignore free instructions - void visitInstruction(Instruction &I); // Visit unsafe ptr instruction + void visitCastInst(CastInst &CI); + void visitInstruction(Instruction &I) {} private: // Helper functions used to implement the visitation functions... - // createNode - Create a new DSNode, ensuring that it is properly added to - // the graph. - // + /// createNode - Create a new DSNode, ensuring that it is properly added to + /// the graph. + /// DSNode *createNode(DSNode::NodeTy NodeType, const Type *Ty); - // getValueNode - Return a DSNode that corresponds the the specified LLVM - // value. This either returns the already existing node, or creates a new - // one and adds it to the graph, if none exists. - // - DSNode *getValueNode(Value &V); - - // getGlobalNode - Just like getValueNode, except the global node itself is - // returned, not a scalar node pointing to a global. - // - DSNode *getGlobalNode(GlobalValue &V); - - // getLink - This method is used to either return the specified link in the - // specified node if one exists. If a link does not already exist (it's - // null), then we create a new node, link it, then return it. - // - DSNode *getLink(DSNode *Node, unsigned Link); - - // getSubscriptedNode - Perform the basic getelementptr functionality that - // must be factored out of gep, load and store while they are all MAI's. - // - DSNode *getSubscriptedNode(GetElementPtrInst &GEP, DSNode *Ptr); + /// getValueNode - Return a DSNode that corresponds the the specified LLVM + /// value. This either returns the already existing node, or creates a new + /// one and adds it to the graph, if none exists. + /// + DSNodeHandle getValueNode(Value &V); + + /// getValueDest - Return the DSNode that the actual value points to. This + /// is basically the same thing as: getLink(getValueNode(V), 0) + /// + DSNodeHandle &getValueDest(Value &V); + + /// getGlobalNode - Just like getValueNode, except the global node itself is + /// returned, not a scalar node pointing to a global. + /// + DSNodeHandle &getGlobalNode(GlobalValue &V); + + /// getLink - This method is used to return the specified link in the + /// specified node if one exists. If a link does not already exist (it's + /// null), then we create a new node, link it, then return it. We must + /// specify the type of the Node field we are accessing so that we know what + /// type should be linked to if we need to create a new node. + /// + DSNodeHandle &getLink(const DSNodeHandle &Node, unsigned Link, + const Type *FieldTy); }; } //===----------------------------------------------------------------------===// // DSGraph constructor - Simply use the GraphBuilder to construct the local // graph. -DSGraph::DSGraph(Function &F, GlobalDSGraph* GlobalsG) - : Func(F), RetNode(0), GlobalsGraph(GlobalsG) { - if (GlobalsGraph != this) { - GlobalsGraph->addReference(this); - // Use the graph builder to construct the local version of the graph - GraphBuilder B(*this, Nodes, RetNode, ValueMap, FunctionCalls); - markIncompleteNodes(); - } +DSGraph::DSGraph(Function &F) : Func(&F) { + // Use the graph builder to construct the local version of the graph + GraphBuilder B(*this, Nodes, RetNode, ValueMap, FunctionCalls); + markIncompleteNodes(); } @@ -137,9 +162,9 @@ DSNode *GraphBuilder::createNode(DSNode::NodeTy NodeType, const Type *Ty) { // getGlobalNode - Just like getValueNode, except the global node itself is // returned, not a scalar node pointing to a global. // -DSNode *GraphBuilder::getGlobalNode(GlobalValue &V) { +DSNodeHandle &GraphBuilder::getGlobalNode(GlobalValue &V) { DSNodeHandle &NH = ValueMap[&V]; - if (NH) return NH; // Already have a node? Just return it... + if (NH.getNode()) return NH; // Already have a node? Just return it... // Create a new global node for this global variable... DSNode *G = createNode(DSNode::GlobalNode, V.getType()->getElementType()); @@ -149,8 +174,8 @@ DSNode *GraphBuilder::getGlobalNode(GlobalValue &V) { // each use. For functions and other global variables, this is unneccesary, // so avoid excessive merging by cloning these nodes on demand. // - NH = G; - return G; + NH.setNode(G); + return NH; } @@ -158,126 +183,145 @@ DSNode *GraphBuilder::getGlobalNode(GlobalValue &V) { // This either returns the already existing node, or creates a new one and adds // it to the graph, if none exists. // -DSNode *GraphBuilder::getValueNode(Value &V) { - assert(isa(V.getType()) && "Should only use pointer scalars!"); - if (!isa(V)) { - DSNodeHandle &NH = ValueMap[&V]; - if (NH) return NH; // Already have a node? Just return it... - } +DSNodeHandle GraphBuilder::getValueNode(Value &V) { + assert(isPointerType(V.getType()) && "Should only use pointer scalars!"); + // Do not share the pointer value to globals... this would cause way too much + // false merging. + // + DSNodeHandle &NH = ValueMap[&V]; + if (!isa(V) && NH.getNode()) + return NH; // Already have a node? Just return it... // Otherwise we need to create a new scalar node... DSNode *N = createNode(DSNode::ScalarNode, V.getType()); // If this is a global value, create the global pointed to. if (GlobalValue *GV = dyn_cast(&V)) { - DSNode *G = getGlobalNode(*GV); - N->addEdgeTo(G); + N->addEdgeTo(0, getGlobalNode(*GV)); + return DSNodeHandle(N, 0); } else { - ValueMap[&V] = N; + NH.setOffset(0); + NH.setNode(N); } - return N; + return NH; } +/// getValueDest - Return the DSNode that the actual value points to. This +/// is basically the same thing as: getLink(getValueNode(V), 0) +/// +DSNodeHandle &GraphBuilder::getValueDest(Value &V) { + return getLink(getValueNode(V), 0, V.getType()); +} -// getLink - This method is used to either return the specified link in the -// specified node if one exists. If a link does not already exist (it's -// null), then we create a new node, link it, then return it. -// -DSNode *GraphBuilder::getLink(DSNode *Node, unsigned Link) { - assert(Link < Node->getNumLinks() && "Link accessed out of range!"); - if (Node->getLink(Link) == 0) { - DSNode::NodeTy NT; - const Type *Ty; - - switch (Node->getType()->getPrimitiveID()) { - case Type::PointerTyID: - Ty = cast(Node->getType())->getElementType(); - NT = DSNode::ShadowNode; - break; - case Type::ArrayTyID: - Ty = cast(Node->getType())->getElementType(); - NT = DSNode::SubElement; - break; - case Type::StructTyID: - Ty = cast(Node->getType())->getContainedType(Link); - NT = DSNode::SubElement; - break; - default: - assert(0 && "Unexpected type to dereference!"); - abort(); - } - - DSNode *New = createNode(NT, Ty); - Node->addEdgeTo(Link, New); - } - return Node->getLink(Link); -} -// getSubscriptedNode - Perform the basic getelementptr functionality that must -// be factored out of gep, load and store while they are all MAI's. -// -DSNode *GraphBuilder::getSubscriptedNode(GetElementPtrInst &GEP, DSNode *Ptr) { - for (unsigned i = 1, e = GEP.getNumOperands(); i != e; ++i) - if (GEP.getOperand(i)->getType() == Type::UIntTy) - Ptr = getLink(Ptr, 0); - else if (GEP.getOperand(i)->getType() == Type::UByteTy) - Ptr = getLink(Ptr, cast(GEP.getOperand(i))->getValue()); +/// getLink - This method is used to return the specified link in the +/// specified node if one exists. If a link does not already exist (it's +/// null), then we create a new node, link it, then return it. We must +/// specify the type of the Node field we are accessing so that we know what +/// type should be linked to if we need to create a new node. +/// +DSNodeHandle &GraphBuilder::getLink(const DSNodeHandle &node, + unsigned LinkNo, const Type *FieldTy) { + DSNodeHandle &Node = const_cast(node); - if (GEP.getNumOperands() == 1) - Ptr = getLink(Ptr, 0); // All GEP's have an implicit 0 if nothing else. + DSNodeHandle *Link = Node.getLink(LinkNo); + if (Link) return *Link; + + // If the link hasn't been created yet, make and return a new shadow node of + // the appropriate type for FieldTy... + // - return Ptr; + // If we are indexing with a typed pointer, then the thing we are pointing + // to is of the pointed type. If we are pointing to it with an integer + // (because of cast to an integer), we represent it with a void type. + // + const Type *ReqTy; + if (const PointerType *Ptr = dyn_cast(FieldTy)) + ReqTy = Ptr->getElementType(); + else + ReqTy = Type::VoidTy; + + DSNode *N = createNode(DSNode::ShadowNode, ReqTy); + Node.setLink(LinkNo, N); + return *Node.getLink(LinkNo); } + //===----------------------------------------------------------------------===// // Specific instruction type handler implementations... // -// Alloca & Malloc instruction implementation - Simply create a new memory -// object, pointing the scalar to it. -// +/// Alloca & Malloc instruction implementation - Simply create a new memory +/// object, pointing the scalar to it. +/// void GraphBuilder::handleAlloc(AllocationInst &AI, DSNode::NodeTy NodeType) { - DSNode *Scalar = getValueNode(AI); DSNode *New = createNode(NodeType, AI.getAllocatedType()); - Scalar->addEdgeTo(New); // Make the scalar point to the new node... + + // Make the scalar point to the new node... + getValueNode(AI).addEdgeTo(New); } // PHINode - Make the scalar for the PHI node point to all of the things the // incoming values point to... which effectively causes them to be merged. // void GraphBuilder::visitPHINode(PHINode &PN) { - if (!isa(PN.getType())) return; // Only pointer PHIs + if (!isPointerType(PN.getType())) return; // Only pointer PHIs - DSNode *Scalar = getValueNode(PN); - DSNode *ScalarDest = getLink(Scalar, 0); + DSNodeHandle &ScalarDest = getValueDest(PN); for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) - ScalarDest->mergeWith(getLink(getValueNode(*PN.getIncomingValue(i)), 0)); + if (!isa(PN.getIncomingValue(i))) + ScalarDest.mergeWith(getValueDest(*PN.getIncomingValue(i))); } void GraphBuilder::visitGetElementPtrInst(GetElementPtrInst &GEP) { - DSNode *Ptr = getSubscriptedNode(GEP, getValueNode(*GEP.getOperand(0))); - getValueNode(GEP)->addEdgeTo(Ptr); + DSNodeHandle Value = getValueDest(*GEP.getOperand(0)); + + unsigned Offset = 0; + const Type *CurTy = GEP.getOperand(0)->getType(); + + for (unsigned i = 1, e = GEP.getNumOperands(); i != e; ++i) + if (GEP.getOperand(i)->getType() == Type::LongTy) { + if (GEP.getOperand(i) != Constant::getNullValue(Type::LongTy)) { + std::cerr << "Array indexing not handled yet!\n"; + } + CurTy = cast(CurTy)->getElementType(); + } else if (GEP.getOperand(i)->getType() == Type::UByteTy) { + unsigned FieldNo = cast(GEP.getOperand(i))->getValue(); + const StructType *STy = cast(CurTy); + Offset += TD.getStructLayout(STy)->MemberOffsets[FieldNo]; + CurTy = STy->getContainedType(FieldNo); + } + + // Add in the offset calculated... + Value.setOffset(Value.getOffset()+Offset); + + // Value is now the pointer we want to GEP to be... + getValueNode(GEP).addEdgeTo(Value); } void GraphBuilder::visitLoadInst(LoadInst &LI) { - DSNode *Ptr = getValueNode(*LI.getOperand(0)); - if (!isa(LI.getType())) return; // only loads OF pointers - getValueNode(LI)->addEdgeTo(getLink(Ptr, 0)); + DSNodeHandle &Ptr = getValueDest(*LI.getOperand(0)); + if (isPointerType(LI.getType())) + getValueNode(LI).addEdgeTo(getLink(Ptr, 0, LI.getType())); } void GraphBuilder::visitStoreInst(StoreInst &SI) { - DSNode *DestPtr = getValueNode(*SI.getOperand(1)); - if (!isa(SI.getOperand(0)->getType())) return; - DSNode *Value = getValueNode(*SI.getOperand(0)); - DestPtr->addEdgeTo(getLink(Value, 0)); + DSNodeHandle &Dest = getValueDest(*SI.getOperand(1)); + + // Avoid adding edges from null, or processing non-"pointer" stores + if (isPointerType(SI.getOperand(0)->getType()) && + !isa(SI.getOperand(0))) { + Dest.addEdgeTo(getValueDest(*SI.getOperand(0))); + } } void GraphBuilder::visitReturnInst(ReturnInst &RI) { - if (RI.getNumOperands() && isa(RI.getOperand(0)->getType())) { - DSNode *Value = getLink(getValueNode(*RI.getOperand(0)), 0); - Value->mergeWith(RetNode); + if (RI.getNumOperands() && isPointerType(RI.getOperand(0)->getType()) && + !isa(RI.getOperand(0))) { + DSNodeHandle &Value = getValueDest(*RI.getOperand(0)); + Value.mergeWith(RetNode); RetNode = Value; } } @@ -288,13 +332,13 @@ void GraphBuilder::visitCallInst(CallInst &CI) { vector &Args = FunctionCalls.back(); // Set up the return value... - if (isa(CI.getType())) - Args.push_back(getLink(getValueNode(CI), 0)); + if (isPointerType(CI.getType())) + Args.push_back(getLink(getValueNode(CI), 0, CI.getType())); else - Args.push_back(0); + Args.push_back(DSNodeHandle()); unsigned Start = 0; - // Special case for direct call, avoid creating spurious scalar node... + // Special case for a direct call, avoid creating spurious scalar node... if (GlobalValue *GV = dyn_cast(CI.getOperand(0))) { Args.push_back(getGlobalNode(*GV)); Start = 1; @@ -302,21 +346,43 @@ void GraphBuilder::visitCallInst(CallInst &CI) { // Pass the arguments in... for (unsigned i = Start, e = CI.getNumOperands(); i != e; ++i) - if (isa(CI.getOperand(i)->getType())) - Args.push_back(getLink(getValueNode(*CI.getOperand(i)), 0)); + if (isPointerType(CI.getOperand(i)->getType())) + Args.push_back(getLink(getValueNode(*CI.getOperand(i)), 0, + CI.getOperand(i)->getType())); } -// visitInstruction - All safe instructions have been processed above, this case -// is where unsafe ptr instructions land. +/// Handle casts... +void GraphBuilder::visitCastInst(CastInst &CI) { + if (isPointerType(CI.getType()) && isPointerType(CI.getOperand(0)->getType())) + getValueNode(CI).addEdgeTo(getLink(getValueNode(*CI.getOperand(0)), 0, + CI.getOperand(0)->getType())); +} + + + + +//===----------------------------------------------------------------------===// +// LocalDataStructures Implementation +//===----------------------------------------------------------------------===// + +// releaseMemory - If the pass pipeline is done with this pass, we can release +// our memory... here... // -void GraphBuilder::visitInstruction(Instruction &I) { - // If the return type is a pointer, mark the pointed node as being a cast node - if (isa(I.getType())) - getLink(getValueNode(I), 0)->NodeType |= DSNode::CastNode; - - // If any operands are pointers, mark the pointed nodes as being a cast node - for (Instruction::op_iterator i = I.op_begin(), E = I.op_end(); i!=E; ++i) - if (isa(i->get()->getType())) - getLink(getValueNode(*i->get()), 0)->NodeType |= DSNode::CastNode; +void LocalDataStructures::releaseMemory() { + for (std::map::iterator I = DSInfo.begin(), + E = DSInfo.end(); I != E; ++I) + delete I->second; + + // Empty map so next time memory is released, data structures are not + // re-deleted. + DSInfo.clear(); +} + +bool LocalDataStructures::run(Module &M) { + // 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(*I))); + return false; } diff --git a/lib/Analysis/DataStructure/Printer.cpp b/lib/Analysis/DataStructure/Printer.cpp index 986c28d0a88..f6c36e42c2d 100644 --- a/lib/Analysis/DataStructure/Printer.cpp +++ b/lib/Analysis/DataStructure/Printer.cpp @@ -14,35 +14,37 @@ using std::string; void DSNode::dump() const { print(std::cerr, 0); } -string DSNode::getCaption(const DSGraph *G) const { +static string getCaption(const DSNode *N, const DSGraph *G) { std::stringstream OS; - Module *M = G && &G->getFunction()? G->getFunction().getParent() : 0; - WriteTypeSymbolic(OS, getType(), M); - - OS << " "; - if (NodeType & ScalarNode) OS << "S"; - if (NodeType & AllocaNode) OS << "A"; - if (NodeType & NewNode ) OS << "N"; - if (NodeType & GlobalNode) OS << "G"; - if (NodeType & SubElement) OS << "E"; - if (NodeType & CastNode ) OS << "C"; - if (NodeType & Incomplete) OS << "I"; - - for (unsigned i = 0, e = Globals.size(); i != e; ++i) { + Module *M = G && &G->getFunction() ? G->getFunction().getParent() : 0; + + for (unsigned i = 0, e = N->getTypeEntries().size(); i != e; ++i) { + WriteTypeSymbolic(OS, N->getTypeEntries()[i].first, M); + if (N->getTypeEntries()[i].second) + OS << "@" << N->getTypeEntries()[i].second; + OS << "\n"; + } + + if (N->NodeType & DSNode::ScalarNode) OS << "S"; + if (N->NodeType & DSNode::AllocaNode) OS << "A"; + if (N->NodeType & DSNode::NewNode ) OS << "N"; + if (N->NodeType & DSNode::GlobalNode) OS << "G"; + if (N->NodeType & DSNode::Incomplete) OS << "I"; + + for (unsigned i = 0, e = N->getGlobals().size(); i != e; ++i) { + WriteAsOperand(OS, N->getGlobals()[i], false, true, M); OS << "\n"; - WriteAsOperand(OS, Globals[i], false, true, M); } - if ((NodeType & ScalarNode) && G) { + if ((N->NodeType & DSNode::ScalarNode) && G) { const std::map &VM = G->getValueMap(); for (std::map::const_iterator I = VM.begin(), E = VM.end(); I != E; ++I) - if (I->second == this) { - OS << "\n"; + if (I->second.getNode() == N) { WriteAsOperand(OS, I->first, false, true, M); + OS << "\n"; } } - return OS.str(); } @@ -77,10 +79,12 @@ static std::string escapeLabel(const std::string &In) { static void writeEdge(std::ostream &O, const void *SrcNode, const char *SrcNodePortName, int SrcNodeIdx, - const DSNode *VS, const std::string &EdgeAttr = "") { + const DSNodeHandle &VS, + const std::string &EdgeAttr = "") { O << "\tNode" << SrcNode << SrcNodePortName; if (SrcNodeIdx != -1) O << SrcNodeIdx; - O << " -> Node" << (void*)VS; + O << " -> Node" << (void*)VS.getNode(); + if (VS.getOffset()) O << ":g" << VS.getOffset(); if (!EdgeAttr.empty()) O << "[" << EdgeAttr << "]"; @@ -88,13 +92,13 @@ static void writeEdge(std::ostream &O, const void *SrcNode, } void DSNode::print(std::ostream &O, const DSGraph *G) const { - std::string Caption = escapeLabel(getCaption(G)); + std::string Caption = escapeLabel(getCaption(this, G)); O << "\tNode" << (void*)this << " [ label =\"{" << Caption; - if (!Links.empty()) { + if (getSize() != 0) { O << "|{"; - for (unsigned i = 0; i < Links.size(); ++i) { + for (unsigned i = 0; i < getSize(); ++i) { if (i) O << "|"; O << ""; } @@ -102,9 +106,9 @@ void DSNode::print(std::ostream &O, const DSGraph *G) const { } O << "}\"];\n"; - for (unsigned i = 0; i < Links.size(); ++i) - if (Links[i]) - writeEdge(O, this, ":g", i, Links[i]); + for (unsigned i = 0; i != getSize(); ++i) + if (const DSNodeHandle *DSN = getLink(i)) + writeEdge(O, this, ":g", i, *DSN); } void DSGraph::print(std::ostream &O) const { @@ -114,10 +118,8 @@ void DSGraph::print(std::ostream &O) const { << "\tsize=\"10,7.5\";\n" << "\trotate=\"90\";\n"; - if (&Func != 0) - O << "\tlabel=\"Function\\ " << Func.getName() << "\";\n\n"; - else - O << "\tlabel=\"Global Graph\";\n\n"; + if (Func != 0) + O << "\tlabel=\"Function\\ " << Func->getName() << "\";\n\n"; // Output all of the nodes... for (unsigned i = 0, e = Nodes.size(); i != e; ++i) @@ -143,7 +145,7 @@ void DSGraph::print(std::ostream &O) const { O << "}}\"];\n"; for (unsigned j = 0, e = Call.size(); j != e; ++j) - if (Call[j]) + if (Call[j].getNode()) writeEdge(O, &Call, ":g", j, Call[j], "color=gray63"); } @@ -152,16 +154,14 @@ void DSGraph::print(std::ostream &O) const { } -static void printGraph(const DSGraph &Graph, std::ostream &O, - const string &GraphName, const string &Prefix) { - string Filename = Prefix + "." + GraphName + ".dot"; +void DSGraph::writeGraphToFile(std::ostream &O, const string &GraphName) { + string Filename = GraphName + ".dot"; O << "Writing '" << Filename << "'..."; std::ofstream F(Filename.c_str()); if (F.good()) { - Graph.print(F); - O << " [" << Graph.getGraphSize() << "+" - << Graph.getFunctionCalls().size() << "]\n"; + print(F); + O << " [" << getGraphSize() << "+" << getFunctionCalls().size() << "]\n"; } else { O << " error opening file for writing!\n"; } @@ -179,31 +179,33 @@ static void printCollection(const Collection &C, std::ostream &O, for (Module::const_iterator I = M->begin(), E = M->end(); I != E; ++I) if (!I->isExternal() && (I->getName() == "main" || !OnlyPrintMain)) - printGraph(C.getDSGraph((Function&)*I), O, I->getName(), Prefix); + C.getDSGraph((Function&)*I).writeGraphToFile(O, Prefix+I->getName()); } // print - Print out the analysis results... void LocalDataStructures::print(std::ostream &O, const Module *M) const { - printCollection(*this, O, M, "ds"); + printCollection(*this, O, M, "ds."); } +#if 0 void BUDataStructures::print(std::ostream &O, const Module *M) const { - printCollection(*this, O, M, "bu"); + printCollection(*this, O, M, "bu."); for (Module::const_iterator I = M->begin(), E = M->end(); I != E; ++I) if (!I->isExternal()) { - printGraph(*getDSGraph(*I).GlobalsGraph, O, "program", "gg"); + (*getDSGraph(*I).GlobalsGraph)->writeGraphToFile(O, "gg.program"); break; } } void TDDataStructures::print(std::ostream &O, const Module *M) const { - printCollection(*this, O, M, "td"); + printCollection(*this, O, M, "td."); for (Module::const_iterator I = M->begin(), E = M->end(); I != E; ++I) if (!I->isExternal()) { - printGraph(*getDSGraph(*I).GlobalsGraph, O, "program", "gg"); + (*getDSGraph(*I).GlobalsGraph)->writeGraphToFile(O, "gg.program"); break; } } +#endif diff --git a/lib/Analysis/DataStructure/TopDownClosure.cpp b/lib/Analysis/DataStructure/TopDownClosure.cpp index ca4828d1d4b..863dd5ab515 100644 --- a/lib/Analysis/DataStructure/TopDownClosure.cpp +++ b/lib/Analysis/DataStructure/TopDownClosure.cpp @@ -10,9 +10,10 @@ #include "llvm/Analysis/DataStructure.h" #include "llvm/Module.h" #include "llvm/DerivedTypes.h" -#include "Support/StatisticReporter.h" +#include "Support/Statistic.h" using std::map; +#if 0 static RegisterAnalysis Y("tddatastructure", "Top-down Data Structure Analysis Closure"); @@ -223,3 +224,4 @@ DSGraph &TDDataStructures::calculateGraph(Function &F) { return *Graph; } +#endif -- 2.34.1