From 2b0f739d57f7c0a7158c8621b6c58c57777d3576 Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Wed, 10 Jul 2002 22:36:26 +0000 Subject: [PATCH] Reimplement data structure analysis git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@2868 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Analysis/DataStructure/ComputeClosure.cpp | 258 ---------- lib/Analysis/DataStructure/EliminateNodes.cpp | 373 -------------- .../DataStructure/FunctionRepBuilder.cpp | 365 -------------- .../DataStructure/FunctionRepBuilder.h | 135 ----- lib/Analysis/DataStructure/NodeImpl.cpp | 470 ------------------ 5 files changed, 1601 deletions(-) delete mode 100644 lib/Analysis/DataStructure/ComputeClosure.cpp delete mode 100644 lib/Analysis/DataStructure/EliminateNodes.cpp delete mode 100644 lib/Analysis/DataStructure/FunctionRepBuilder.cpp delete mode 100644 lib/Analysis/DataStructure/FunctionRepBuilder.h delete mode 100644 lib/Analysis/DataStructure/NodeImpl.cpp diff --git a/lib/Analysis/DataStructure/ComputeClosure.cpp b/lib/Analysis/DataStructure/ComputeClosure.cpp deleted file mode 100644 index 0f94b9141c8..00000000000 --- a/lib/Analysis/DataStructure/ComputeClosure.cpp +++ /dev/null @@ -1,258 +0,0 @@ -//===- ComputeClosure.cpp - Implement interprocedural closing of graphs ---===// -// -// Compute the interprocedural closure of a data structure graph -// -//===----------------------------------------------------------------------===// - -// DEBUG_IP_CLOSURE - Define this to debug the act of linking up graphs -//#define DEBUG_IP_CLOSURE 1 - -#include "llvm/Analysis/DataStructure.h" -#include "llvm/Function.h" -#include "llvm/iOther.h" -#include "Support/STLExtras.h" -#include -using std::cerr; - -// Make all of the pointers that point to Val also point to N. -// -static void copyEdgesFromTo(PointerVal Val, DSNode *N) { - unsigned ValIdx = Val.Index; - unsigned NLinks = N->getNumLinks(); - - const std::vector &PVSsToUpdate(Val.Node->getReferrers()); - for (unsigned i = 0, e = PVSsToUpdate.size(); i != e; ++i) { - // Loop over all of the pointers pointing to Val... - PointerValSet &PVS = *PVSsToUpdate[i]; - for (unsigned j = 0, je = PVS.size(); j != je; ++j) { - if (PVS[j].Node == Val.Node && PVS[j].Index >= ValIdx && - PVS[j].Index < ValIdx+NLinks) - PVS.add(PointerVal(N, PVS[j].Index-ValIdx)); - } - } -} - -static void ResolveNodesTo(const PointerValSet &FromVals, - const PointerValSet &ToVals) { - // Only resolve the first pointer, although there many be many pointers here. - // The problem is that the inlined function might return one of the arguments - // to the function, and if so, extra values can be added to the arg or call - // node that point to what the other one got resolved to. Since these will - // be added to the end of the PVS pointed in, we just ignore them. - // - assert(!FromVals.empty() && "From should have at least a shadow node!"); - const PointerVal &FromPtr = FromVals[0]; - - assert(FromPtr.Index == 0 && - "Resolved node return pointer should be index 0!"); - DSNode *N = FromPtr.Node; - - // Make everything that pointed to the shadow node also point to the values in - // ToVals... - // - for (unsigned i = 0, e = ToVals.size(); i != e; ++i) - copyEdgesFromTo(ToVals[i], N); - - // Make everything that pointed to the shadow node now also point to the - // values it is equivalent to... - const std::vector &PVSToUpdate(N->getReferrers()); - for (unsigned i = 0, e = PVSToUpdate.size(); i != e; ++i) - PVSToUpdate[i]->add(ToVals); -} - - -// ResolveNodeTo - The specified node is now known to point to the set of values -// in ToVals, instead of the old shadow node subgraph that it was pointing to. -// -static void ResolveNodeTo(DSNode *Node, const PointerValSet &ToVals) { - assert(Node->getNumLinks() == 1 && "Resolved node can only be a scalar!!"); - - const PointerValSet &PVS = Node->getLink(0); - ResolveNodesTo(PVS, ToVals); -} - -// isResolvableCallNode - Return true if node is a call node and it is a call -// node that we can inline... -// -static bool isResolvableCallNode(CallDSNode *CN) { - // Only operate on call nodes with direct function calls - if (CN->getArgValues(0).size() == 1 && - isa(CN->getArgValues(0)[0].Node)) { - GlobalDSNode *GDN = cast(CN->getArgValues(0)[0].Node); - Function *F = cast(GDN->getGlobal()); - - // Only work on call nodes with direct calls to methods with bodies. - return !F->isExternal(); - } - return false; -} - -#include "Support/CommandLine.h" -static cl::Int InlineLimit("dsinlinelimit", "Max number of graphs to inline when computing ds closure", cl::Hidden, 100); - -// computeClosure - Replace all of the resolvable call nodes with the contents -// of their corresponding method data structure graph... -// -void FunctionDSGraph::computeClosure(const DataStructure &DS) { - // Note that this cannot be a real vector because the keys will be changing - // as nodes are eliminated! - // - typedef std::pair, CallInst *> CallDescriptor; - std::vector > CallMap; - - unsigned NumInlines = 0; - - // Loop over the resolvable call nodes... - std::vector::iterator NI; - NI = std::find_if(CallNodes.begin(), CallNodes.end(), isResolvableCallNode); - while (NI != CallNodes.end()) { - CallDSNode *CN = *NI; - GlobalDSNode *FGDN = cast(CN->getArgValues(0)[0].Node); - Function *F = cast(FGDN->getGlobal()); - - if ((int)NumInlines++ == InlineLimit) { // CUTE hack huh? - cerr << "Infinite (?) recursion halted\n"; - cerr << "Not inlining: " << F->getName() << "\n"; - CN->dump(); - return; - } - - CallNodes.erase(NI); // Remove the call node from the graph - - unsigned CallNodeOffset = NI-CallNodes.begin(); - - // Find out if we have already incorporated this node... if so, it will be - // in the CallMap... - // - -#if 0 - cerr << "\nSearching for: " << (void*)CN->getCall() << ": "; - for (unsigned X = 0; X != CN->getArgs().size(); ++X) { - cerr << " " << X << " is\n"; - CN->getArgs().first[X].print(cerr); - } -#endif - - const std::vector &Args = CN->getArgs(); - PointerValSet *CMI = 0; - for (unsigned i = 0, e = CallMap.size(); i != e; ++i) { -#if 0 - cerr << "Found: " << (void*)CallMap[i].first.second << ": "; - for (unsigned X = 0; X != CallMap[i].first.first.size(); ++X) { - cerr << " " << X << " is\n"; CallMap[i].first.first[X].print(cerr); - } -#endif - - // Look to see if the function call takes a superset of the values we are - // providing as input - // - CallDescriptor &CD = CallMap[i].first; - if (CD.second == CN->getCall() && CD.first.size() == Args.size()) { - bool FoundMismatch = false; - for (unsigned j = 0, je = Args.size(); j != je; ++j) { - PointerValSet ArgSet = CD.first[j]; - if (ArgSet.add(Args[j])) { - FoundMismatch = true; break; - } - } - - if (!FoundMismatch) { CMI = &CallMap[i].second; break; } - } - } - - // Hold the set of values that correspond to the incorporated methods - // return set. - // - PointerValSet RetVals; - - if (CMI) { - // We have already inlined an identical function call! - RetVals = *CMI; - } else { - // Get the datastructure graph for the new method. Note that we are not - // allowed to modify this graph because it will be the cached graph that - // is returned by other users that want the local datastructure graph for - // a method. - // - const FunctionDSGraph &NewFunction = DS.getDSGraph(F); - - // StartNode - The first node of the incorporated graph, last node of the - // preexisting data structure graph... - // - unsigned StartAllocNode = AllocNodes.size(); - - // Incorporate a copy of the called function graph into the current graph, - // allowing us to do local transformations to local graph to link - // arguments to call values, and call node to return value... - // - std::vector Args; - RetVals = cloneFunctionIntoSelf(NewFunction, false, Args); - CallMap.push_back(make_pair(CallDescriptor(CN->getArgs(), CN->getCall()), - RetVals)); - - // If the call node has arguments, process them now! - assert(Args.size() == CN->getNumArgs()-1 && - "Call node doesn't match function?"); - - for (unsigned i = 0, e = Args.size(); i != e; ++i) { - // Now we make all of the nodes inside of the incorporated method - // point to the real arguments values, not to the shadow nodes for the - // argument. - ResolveNodesTo(Args[i], CN->getArgValues(i+1)); - } - - // Loop through the nodes, deleting alloca nodes in the inlined function. - // Since the memory has been released, we cannot access their pointer - // fields (with defined results at least), so it is not possible to use - // any pointers to the alloca. Drop them now, and remove the alloca's - // since they are dead (we just removed all links to them). - // - for (unsigned i = StartAllocNode; i != AllocNodes.size(); ++i) - if (AllocNodes[i]->isAllocaNode()) { - AllocDSNode *NDS = AllocNodes[i]; - NDS->removeAllIncomingEdges(); // These edges are invalid now - delete NDS; // Node is dead - AllocNodes.erase(AllocNodes.begin()+i); // Remove slot in Nodes array - --i; // Don't skip the next node - } - } - - // If the function returns a pointer value... Resolve values pointing to - // the shadow nodes pointed to by CN to now point the values in RetVals... - // - if (CN->getNumLinks()) ResolveNodeTo(CN, RetVals); - - // Now the call node is completely destructable. Eliminate it now. - delete CN; - - bool Changed = true; - while (Changed) { - // Eliminate shadow nodes that are not distinguishable from some other - // node in the graph... - // - Changed = UnlinkUndistinguishableNodes(); - - // Eliminate shadow nodes that are now extraneous due to linking... - Changed |= RemoveUnreachableNodes(); - } - - //if (F == Func) return; // Only do one self inlining - - // Move on to the next call node... - NI = std::find_if(CallNodes.begin(), CallNodes.end(), isResolvableCallNode); - } - - // Drop references to globals... - CallMap.clear(); - - bool Changed = true; - while (Changed) { - // Eliminate shadow nodes that are not distinguishable from some other - // node in the graph... - // - Changed = UnlinkUndistinguishableNodes(); - - // Eliminate shadow nodes that are now extraneous due to linking... - Changed |= RemoveUnreachableNodes(); - } -} diff --git a/lib/Analysis/DataStructure/EliminateNodes.cpp b/lib/Analysis/DataStructure/EliminateNodes.cpp deleted file mode 100644 index 7d8eb9b251e..00000000000 --- a/lib/Analysis/DataStructure/EliminateNodes.cpp +++ /dev/null @@ -1,373 +0,0 @@ -//===- EliminateNodes.cpp - Prune unneccesary nodes in the graph ----------===// -// -// This file contains two node optimizations: -// 1. UnlinkUndistinguishableNodes - Often, after unification, shadow -// nodes are left around that should not exist anymore. An example is when -// a shadow gets unified with a 'new' node, the following graph gets -// generated: %X -> Shadow, %X -> New. Since all of the edges to the -// shadow node also all go to the New node, we can eliminate the shadow. -// -// 2. RemoveUnreachableNodes - Remove shadow and allocation nodes that are not -// reachable from some other node in the graph. Unreachable nodes are left -// lying around often because a method only refers to some allocations with -// scalar values or an alloca, then when it is inlined, these references -// disappear and the nodes become homeless and prunable. -// -//===----------------------------------------------------------------------===// - -#include "llvm/Analysis/DataStructureGraph.h" -#include "llvm/Value.h" -#include "Support/STLExtras.h" -#include -using std::vector; - -//#define DEBUG_NODE_ELIMINATE 1 - -static void DestroyFirstNodeOfPair(DSNode *N1, DSNode *N2) { -#ifdef DEBUG_NODE_ELIMINATE - std::cerr << "Found Indistinguishable Node:\n"; - N1->print(std::cerr); -#endif - - // The nodes can be merged. Make sure that N2 contains all of the - // outgoing edges (fields) that N1 does... - // - assert(N1->getNumLinks() == N2->getNumLinks() && - "Same type, diff # fields?"); - for (unsigned i = 0, e = N1->getNumLinks(); i != e; ++i) - N2->getLink(i).add(N1->getLink(i)); - - // Now make sure that all of the nodes that point to N1 also point to the node - // that we are merging it with... - // - const vector &Refs = N1->getReferrers(); - for (unsigned i = 0, e = Refs.size(); i != e; ++i) { - PointerValSet &PVS = *Refs[i]; - - bool RanOnce = false; - for (unsigned j = 0, je = PVS.size(); j != je; ++j) - if (PVS[j].Node == N1) { - RanOnce = true; - PVS.add(PointerVal(N2, PVS[j].Index)); - } - - assert(RanOnce && "Node on user set but cannot find the use!"); - } - - N1->mergeInto(N2); - N1->removeAllIncomingEdges(); - delete N1; -} - -// isIndistinguishableNode - A node is indistinguishable if some other node -// has exactly the same incoming links to it and if the node considers itself -// to be the same as the other node... -// -static bool isIndistinguishableNode(DSNode *DN) { - if (DN->getReferrers().empty()) { // No referrers... - if (isa(DN) || isa(DN)) { - delete DN; - return true; // Node is trivially dead - } else - return false; - } - - // Pick a random referrer... Ptr is the things that the referrer points to. - // Since DN is in the Ptr set, look through the set seeing if there are any - // other nodes that are exactly equilivant to DN (with the exception of node - // type), but are not DN. If anything exists, then DN is indistinguishable. - // - - DSNode *IndFrom = 0; - const vector &Refs = DN->getReferrers(); - for (unsigned R = 0, RE = Refs.size(); R != RE; ++R) { - const PointerValSet &Ptr = *Refs[R]; - - for (unsigned i = 0, e = Ptr.size(); i != e; ++i) { - DSNode *N2 = Ptr[i].Node; - if (Ptr[i].Index == 0 && N2 != cast(DN) && - DN->getType() == N2->getType() && DN->isEquivalentTo(N2)) { - - IndFrom = N2; - R = RE-1; - break; - } - } - } - - // If we haven't found an equivalent node to merge with, see if one of the - // nodes pointed to by this node is equivalent to this one... - // - if (IndFrom == 0) { - unsigned NumOutgoing = DN->getNumOutgoingLinks(); - for (DSNode::iterator I = DN->begin(), E = DN->end(); I != E; ++I) { - DSNode *Linked = *I; - if (Linked != DN && Linked->getNumOutgoingLinks() == NumOutgoing && - DN->getType() == Linked->getType() && DN->isEquivalentTo(Linked)) { -#if 0 - // Make sure the leftover node contains links to everything we do... - for (unsigned i = 0, e = DN->getNumLinks(); i != e; ++i) - Linked->getLink(i).add(DN->getLink(i)); -#endif - - IndFrom = Linked; - break; - } - } - } - - - // If DN is indistinguishable from some other node, merge them now... - if (IndFrom == 0) - return false; // Otherwise, nothing found, perhaps next time.... - - DestroyFirstNodeOfPair(DN, IndFrom); - return true; -} - -template -static bool removeIndistinguishableNodes(vector &Nodes) { - bool Changed = false; - vector::iterator I = Nodes.begin(); - while (I != Nodes.end()) { - if (isIndistinguishableNode(*I)) { - I = Nodes.erase(I); - Changed = true; - } else { - ++I; - } - } - return Changed; -} - -template -static bool removeIndistinguishableNodePairs(vector &Nodes) { - bool Changed = false; - vector::iterator I = Nodes.begin(); - while (I != Nodes.end()) { - NodeTy *N1 = *I++; - for (vector::iterator I2 = I, I2E = Nodes.end(); - I2 != I2E; ++I2) { - NodeTy *N2 = *I2; - if (N1->isEquivalentTo(N2)) { - DestroyFirstNodeOfPair(N1, N2); - --I; - I = Nodes.erase(I); - Changed = true; - break; - } - } - } - return Changed; -} - - - -// UnlinkUndistinguishableNodes - Eliminate shadow nodes that are not -// distinguishable from some other node in the graph... -// -bool FunctionDSGraph::UnlinkUndistinguishableNodes() { - // Loop over all of the shadow nodes, checking to see if they are - // indistinguishable from some other node. If so, eliminate the node! - // - return - removeIndistinguishableNodes(AllocNodes) | - removeIndistinguishableNodes(ShadowNodes) | - removeIndistinguishableNodePairs(CallNodes) | - removeIndistinguishableNodePairs(GlobalNodes); -} - -static void MarkReferredNodesReachable(DSNode *N, - vector &ShadowNodes, - vector &ReachableShadowNodes, - vector &AllocNodes, - vector &ReachableAllocNodes); - -static inline void MarkReferredNodeSetReachable(const PointerValSet &PVS, - vector &ShadowNodes, - vector &ReachableShadowNodes, - vector &AllocNodes, - vector &ReachableAllocNodes) { - for (unsigned i = 0, e = PVS.size(); i != e; ++i) - if (isa(PVS[i].Node) || isa(PVS[i].Node)) - MarkReferredNodesReachable(PVS[i].Node, ShadowNodes, ReachableShadowNodes, - AllocNodes, ReachableAllocNodes); -} - -static void MarkReferredNodesReachable(DSNode *N, - vector &ShadowNodes, - vector &ReachableShadowNodes, - vector &AllocNodes, - vector &ReachableAllocNodes) { - assert(ShadowNodes.size() == ReachableShadowNodes.size()); - assert(AllocNodes.size() == ReachableAllocNodes.size()); - - if (ShadowDSNode *Shad = dyn_cast(N)) { - vector::iterator I = - std::find(ShadowNodes.begin(), ShadowNodes.end(), Shad); - unsigned i = I-ShadowNodes.begin(); - if (ReachableShadowNodes[i]) return; // Recursion detected, abort... - ReachableShadowNodes[i] = true; - } else if (AllocDSNode *Alloc = dyn_cast(N)) { - vector::iterator I = - std::find(AllocNodes.begin(), AllocNodes.end(), Alloc); - unsigned i = I-AllocNodes.begin(); - if (ReachableAllocNodes[i]) return; // Recursion detected, abort... - ReachableAllocNodes[i] = true; - } - - for (unsigned i = 0, e = N->getNumLinks(); i != e; ++i) - MarkReferredNodeSetReachable(N->getLink(i), - ShadowNodes, ReachableShadowNodes, - AllocNodes, ReachableAllocNodes); - - const vector *Links = N->getAuxLinks(); - if (Links) - for (unsigned i = 0, e = Links->size(); i != e; ++i) - MarkReferredNodeSetReachable((*Links)[i], - ShadowNodes, ReachableShadowNodes, - AllocNodes, ReachableAllocNodes); -} - -void FunctionDSGraph::MarkEscapeableNodesReachable( - vector &ReachableShadowNodes, - vector &ReachableAllocNodes) { - // Mark all shadow nodes that have edges from other nodes as reachable. - // Recursively mark any shadow nodes pointed to by the newly live shadow - // nodes as also alive. - // - for (unsigned i = 0, e = GlobalNodes.size(); i != e; ++i) - MarkReferredNodesReachable(GlobalNodes[i], - ShadowNodes, ReachableShadowNodes, - AllocNodes, ReachableAllocNodes); - - for (unsigned i = 0, e = CallNodes.size(); i != e; ++i) - MarkReferredNodesReachable(CallNodes[i], - ShadowNodes, ReachableShadowNodes, - AllocNodes, ReachableAllocNodes); - - // Mark all nodes in the return set as being reachable... - MarkReferredNodeSetReachable(RetNode, - ShadowNodes, ReachableShadowNodes, - AllocNodes, ReachableAllocNodes); -} - -bool FunctionDSGraph::RemoveUnreachableNodes() { - bool Changed = false; - bool LocalChange = true; - - while (LocalChange) { - LocalChange = false; - // Reachable*Nodes - Contains true if there is an edge from a reachable - // node to the numbered node... - // - vector ReachableShadowNodes(ShadowNodes.size()); - vector ReachableAllocNodes (AllocNodes.size()); - - MarkEscapeableNodesReachable(ReachableShadowNodes, ReachableAllocNodes); - - // Mark all nodes in the value map as being reachable... - for (std::map::iterator I = ValueMap.begin(), - E = ValueMap.end(); I != E; ++I) - MarkReferredNodeSetReachable(I->second, - ShadowNodes, ReachableShadowNodes, - AllocNodes, ReachableAllocNodes); - - // At this point, all reachable shadow nodes have a true value in the - // Reachable vector. This means that any shadow nodes without an entry in - // the reachable vector are not reachable and should be removed. This is - // a two part process, because we must drop all references before we delete - // the shadow nodes [in case cycles exist]. - // - for (unsigned i = 0; i != ShadowNodes.size(); ++i) - if (!ReachableShadowNodes[i]) { - // Track all unreachable nodes... -#if DEBUG_NODE_ELIMINATE - std::cerr << "Unreachable node eliminated:\n"; - ShadowNodes[i]->print(std::cerr); -#endif - ShadowNodes[i]->removeAllIncomingEdges(); - delete ShadowNodes[i]; - - // Remove from reachable... - ReachableShadowNodes.erase(ReachableShadowNodes.begin()+i); - ShadowNodes.erase(ShadowNodes.begin()+i); // Remove node entry - --i; // Don't skip the next node. - LocalChange = Changed = true; - } - - for (unsigned i = 0; i != AllocNodes.size(); ++i) - if (!ReachableAllocNodes[i]) { - // Track all unreachable nodes... -#if DEBUG_NODE_ELIMINATE - std::cerr << "Unreachable node eliminated:\n"; - AllocNodes[i]->print(std::cerr); -#endif - AllocNodes[i]->removeAllIncomingEdges(); - delete AllocNodes[i]; - - // Remove from reachable... - ReachableAllocNodes.erase(ReachableAllocNodes.begin()+i); - AllocNodes.erase(AllocNodes.begin()+i); // Remove node entry - --i; // Don't skip the next node. - LocalChange = Changed = true; - } - } - - // Loop over the global nodes, removing nodes that have no edges into them or - // out of them. - // - for (vector::iterator I = GlobalNodes.begin(); - I != GlobalNodes.end(); ) - if ((*I)->getReferrers().empty()) { - GlobalDSNode *GDN = *I; - bool NoLinks = true; // Make sure there are no outgoing links... - for (unsigned i = 0, e = GDN->getNumLinks(); i != e; ++i) - if (!GDN->getLink(i).empty()) { - NoLinks = false; - break; - } - if (NoLinks) { - delete GDN; - I = GlobalNodes.erase(I); // Remove the node... - Changed = true; - } else { - ++I; - } - } else { - ++I; - } - - return Changed; -} - - - - -// getEscapingAllocations - Add all allocations that escape the current -// function to the specified vector. -// -void FunctionDSGraph::getEscapingAllocations(vector &Allocs) { - vector ReachableShadowNodes(ShadowNodes.size()); - vector ReachableAllocNodes (AllocNodes.size()); - - MarkEscapeableNodesReachable(ReachableShadowNodes, ReachableAllocNodes); - - for (unsigned i = 0, e = AllocNodes.size(); i != e; ++i) - if (ReachableAllocNodes[i]) - Allocs.push_back(AllocNodes[i]); -} - -// getNonEscapingAllocations - Add all allocations that do not escape the -// current function to the specified vector. -// -void FunctionDSGraph::getNonEscapingAllocations(vector &Allocs) { - vector ReachableShadowNodes(ShadowNodes.size()); - vector ReachableAllocNodes (AllocNodes.size()); - - MarkEscapeableNodesReachable(ReachableShadowNodes, ReachableAllocNodes); - - for (unsigned i = 0, e = AllocNodes.size(); i != e; ++i) - if (!ReachableAllocNodes[i]) - Allocs.push_back(AllocNodes[i]); -} diff --git a/lib/Analysis/DataStructure/FunctionRepBuilder.cpp b/lib/Analysis/DataStructure/FunctionRepBuilder.cpp deleted file mode 100644 index be49eec177d..00000000000 --- a/lib/Analysis/DataStructure/FunctionRepBuilder.cpp +++ /dev/null @@ -1,365 +0,0 @@ -//===- FunctionRepBuilder.cpp - Build the local datastructure graph -------===// -// -// Build the local datastructure graph for a single method. -// -//===----------------------------------------------------------------------===// - -#include "FunctionRepBuilder.h" -#include "llvm/Function.h" -#include "llvm/BasicBlock.h" -#include "llvm/iMemory.h" -#include "llvm/iPHINode.h" -#include "llvm/iOther.h" -#include "llvm/iTerminators.h" -#include "llvm/DerivedTypes.h" -#include "llvm/Constants.h" -#include "Support/STLExtras.h" -#include - -// synthesizeNode - Create a new shadow node that is to be linked into this -// chain.. -// FIXME: This should not take a FunctionRepBuilder as an argument! -// -ShadowDSNode *DSNode::synthesizeNode(const Type *Ty, - FunctionRepBuilder *Rep) { - // If we are a derived shadow node, defer to our parent to synthesize the node - if (ShadowDSNode *Th = dyn_cast(this)) - if (Th->getShadowParent()) - return Th->getShadowParent()->synthesizeNode(Ty, Rep); - - // See if we have already synthesized a node of this type... - for (unsigned i = 0, e = SynthNodes.size(); i != e; ++i) - if (SynthNodes[i].first == Ty) return SynthNodes[i].second; - - // No we haven't. Do so now and add it to our list of saved nodes... - - ShadowDSNode *SN = Rep->makeSynthesizedShadow(Ty, this); - SynthNodes.push_back(std::make_pair(Ty, SN)); - - return SN; -} - -ShadowDSNode *FunctionRepBuilder::makeSynthesizedShadow(const Type *Ty, - DSNode *Parent) { - ShadowDSNode *Result = new ShadowDSNode(Ty, F->getFunction()->getParent(), - Parent); - ShadowNodes.push_back(Result); - return Result; -} - - - -// visitOperand - If the specified instruction operand is a global value, add -// a node for it... -// -void InitVisitor::visitOperand(Value *V) { - if (!Rep->ValueMap.count(V)) // Only process it once... - if (GlobalValue *GV = dyn_cast(V)) { - GlobalDSNode *N = new GlobalDSNode(GV); - Rep->GlobalNodes.push_back(N); - Rep->ValueMap[V].add(N); - Rep->addAllUsesToWorkList(GV); - - // FIXME: If the global variable has fields, we should add critical - // shadow nodes to represent them! - } -} - - -// visitCallInst - Create a call node for the callinst, and create as shadow -// node if the call returns a pointer value. Check to see if the call node -// uses any global variables... -// -void InitVisitor::visitCallInst(CallInst &CI) { - CallDSNode *C = new CallDSNode(&CI); - Rep->CallNodes.push_back(C); - Rep->CallMap[&CI] = C; - - if (const PointerType *PT = dyn_cast(CI.getType())) { - // Create a critical shadow node to represent the memory object that the - // return value points to... - ShadowDSNode *Shad = new ShadowDSNode(PT->getElementType(), - Func->getParent()); - Rep->ShadowNodes.push_back(Shad); - - // The return value of the function is a pointer to the shadow value - // just created... - // - C->getLink(0).add(Shad); - - // The call instruction returns a pointer to the shadow block... - Rep->ValueMap[&CI].add(Shad, &CI); - - // If the call returns a value with pointer type, add all of the users - // of the call instruction to the work list... - Rep->addAllUsesToWorkList(&CI); - } - - // Loop over all of the operands of the call instruction (except the first - // one), to look for global variable references... - // - for_each(CI.op_begin(), CI.op_end(), - bind_obj(this, &InitVisitor::visitOperand)); -} - - -// visitAllocationInst - Create an allocation node for the allocation. Since -// allocation instructions do not take pointer arguments, they cannot refer to -// global vars... -// -void InitVisitor::visitAllocationInst(AllocationInst &AI) { - AllocDSNode *N = new AllocDSNode(&AI); - Rep->AllocNodes.push_back(N); - - Rep->ValueMap[&AI].add(N, &AI); - - // Add all of the users of the malloc instruction to the work list... - Rep->addAllUsesToWorkList(&AI); -} - - -// Visit all other instruction types. Here we just scan, looking for uses of -// global variables... -// -void InitVisitor::visitInstruction(Instruction &I) { - for_each(I.op_begin(), I.op_end(), - bind_obj(this, &InitVisitor::visitOperand)); -} - - -// addAllUsesToWorkList - Add all of the instructions users of the specified -// value to the work list for further processing... -// -void FunctionRepBuilder::addAllUsesToWorkList(Value *V) { - //cerr << "Adding all uses of " << V << "\n"; - for (Value::use_iterator I = V->use_begin(), E = V->use_end(); I != E; ++I) { - Instruction *Inst = cast(*I); - // When processing global values, it's possible that the instructions on - // the use list are not all in this method. Only add the instructions - // that _are_ in this method. - // - if (Inst->getParent()->getParent() == F->getFunction()) - // Only let an instruction occur on the work list once... - if (std::find(WorkList.begin(), WorkList.end(), Inst) == WorkList.end()) - WorkList.push_back(Inst); - } -} - - - - -void FunctionRepBuilder::initializeWorkList(Function *Func) { - // Add all of the arguments to the method to the graph and add all users to - // the worklists... - // - for (Function::aiterator I = Func->abegin(), E = Func->aend(); I != E; ++I) { - // Only process arguments that are of pointer type... - if (const PointerType *PT = dyn_cast(I->getType())) { - // Add a shadow value for it to represent what it is pointing to and add - // this to the value map... - ShadowDSNode *Shad = new ShadowDSNode(PT->getElementType(), - Func->getParent()); - ShadowNodes.push_back(Shad); - ValueMap[I].add(PointerVal(Shad), I); - - // Make sure that all users of the argument are processed... - addAllUsesToWorkList(I); - } - } - - // Iterate over the instructions in the method. Create nodes for malloc and - // call instructions. Add all uses of these to the worklist of instructions - // to process. - // - InitVisitor IV(this, Func); - IV.visit(Func); -} - - - - -PointerVal FunctionRepBuilder::getIndexedPointerDest(const PointerVal &InP, - const MemAccessInst &MAI) { - unsigned Index = InP.Index; - const Type *SrcTy = MAI.getPointerOperand()->getType(); - - for (MemAccessInst::const_op_iterator I = MAI.idx_begin(), - E = MAI.idx_end(); I != E; ++I) - if ((*I)->getType() == Type::UByteTy) { // Look for struct indices... - const StructType *STy = cast(SrcTy); - unsigned StructIdx = cast(I->get())->getValue(); - for (unsigned i = 0; i != StructIdx; ++i) - Index += countPointerFields(STy->getContainedType(i)); - - // Advance SrcTy to be the new element type... - SrcTy = STy->getContainedType(StructIdx); - } else { - // Otherwise, stepping into array or initial pointer, just increment type - SrcTy = cast(SrcTy)->getElementType(); - } - - return PointerVal(InP.Node, Index); -} - -static PointerValSet &getField(const PointerVal &DestPtr) { - assert(DestPtr.Node != 0); - return DestPtr.Node->getLink(DestPtr.Index); -} - - -// Reprocessing a GEP instruction is the result of the pointer operand -// changing. This means that the set of possible values for the GEP -// needs to be expanded. -// -void FunctionRepBuilder::visitGetElementPtrInst(GetElementPtrInst &GEP) { - PointerValSet &GEPPVS = ValueMap[&GEP]; // PointerValSet to expand - - // Get the input pointer val set... - const PointerValSet &SrcPVS = ValueMap[GEP.getOperand(0)]; - - bool Changed = false; // Process each input value... propogating it. - for (unsigned i = 0, e = SrcPVS.size(); i != e; ++i) { - // Calculate where the resulting pointer would point based on an - // input of 'Val' as the pointer type... and add it to our outgoing - // value set. Keep track of whether or not we actually changed - // anything. - // - Changed |= GEPPVS.add(getIndexedPointerDest(SrcPVS[i], GEP)); - } - - // If our current value set changed, notify all of the users of our - // value. - // - if (Changed) addAllUsesToWorkList(&GEP); -} - -void FunctionRepBuilder::visitReturnInst(ReturnInst &RI) { - RetNode.add(ValueMap[RI.getOperand(0)]); -} - -void FunctionRepBuilder::visitLoadInst(LoadInst &LI) { - // Only loads that return pointers are interesting... - const PointerType *DestTy = dyn_cast(LI.getType()); - if (DestTy == 0) return; - - const PointerValSet &SrcPVS = ValueMap[LI.getOperand(0)]; - PointerValSet &LIPVS = ValueMap[&LI]; - - bool Changed = false; - for (unsigned si = 0, se = SrcPVS.size(); si != se; ++si) { - PointerVal Ptr = getIndexedPointerDest(SrcPVS[si], LI); - PointerValSet &Field = getField(Ptr); - - if (Field.size()) { // Field loaded wasn't null? - Changed |= LIPVS.add(Field); - } else { - // If we are loading a null field out of a shadow node, we need to - // synthesize a new shadow node and link it in... - // - ShadowDSNode *SynthNode = - Ptr.Node->synthesizeNode(DestTy->getElementType(), this); - Field.add(SynthNode); - - Changed |= LIPVS.add(Field); - } - } - - if (Changed) addAllUsesToWorkList(&LI); -} - -void FunctionRepBuilder::visitStoreInst(StoreInst &SI) { - // The only stores that are interesting are stores the store pointers - // into data structures... - // - if (!isa(SI.getOperand(0)->getType())) return; - if (!ValueMap.count(SI.getOperand(0))) return; // Src scalar has no values! - - const PointerValSet &SrcPVS = ValueMap[SI.getOperand(0)]; - const PointerValSet &PtrPVS = ValueMap[SI.getOperand(1)]; - - for (unsigned si = 0, se = SrcPVS.size(); si != se; ++si) { - const PointerVal &SrcPtr = SrcPVS[si]; - for (unsigned pi = 0, pe = PtrPVS.size(); pi != pe; ++pi) { - PointerVal Dest = getIndexedPointerDest(PtrPVS[pi], SI); - -#if 0 - std::cerr << "Setting Dest:\n"; - Dest.print(std::cerr); - std::cerr << "to point to Src:\n"; - SrcPtr.print(std::cerr); -#endif - - // Add SrcPtr into the Dest field... - if (getField(Dest).add(SrcPtr)) { - // If we modified the dest field, then invalidate everyone that points - // to Dest. - const std::vector &Ptrs = Dest.Node->getPointers(); - for (unsigned i = 0, e = Ptrs.size(); i != e; ++i) - addAllUsesToWorkList(Ptrs[i]); - } - } - } -} - -void FunctionRepBuilder::visitCallInst(CallInst &CI) { - CallDSNode *DSN = CallMap[&CI]; - unsigned PtrNum = 0; - for (unsigned i = 0, e = CI.getNumOperands(); i != e; ++i) - if (isa(CI.getOperand(i)->getType())) - DSN->addArgValue(PtrNum++, ValueMap[CI.getOperand(i)]); -} - -void FunctionRepBuilder::visitPHINode(PHINode &PN) { - assert(isa(PN.getType()) && "Should only update ptr phis"); - - PointerValSet &PN_PVS = ValueMap[&PN]; - bool Changed = false; - for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) - Changed |= PN_PVS.add(ValueMap[PN.getIncomingValue(i)], - PN.getIncomingValue(i)); - - if (Changed) addAllUsesToWorkList(&PN); -} - - - - -// FunctionDSGraph constructor - Perform the global analysis to determine -// what the data structure usage behavior or a method looks like. -// -FunctionDSGraph::FunctionDSGraph(Function *F) : Func(F) { - FunctionRepBuilder Builder(this); - AllocNodes = Builder.getAllocNodes(); - ShadowNodes = Builder.getShadowNodes(); - GlobalNodes = Builder.getGlobalNodes(); - CallNodes = Builder.getCallNodes(); - RetNode = Builder.getRetNode(); - ValueMap = Builder.getValueMap(); - - // Remove all entries in the value map that consist of global values pointing - // at things. They can only point to their node, so there is no use keeping - // them. - // - for (std::map::iterator I = ValueMap.begin(), - E = ValueMap.end(); I != E;) - if (isa(I->first)) { -#if MAP_DOESNT_HAVE_BROKEN_ERASE_MEMBER - I = ValueMap.erase(I); -#else - ValueMap.erase(I); // This is really lame. - I = ValueMap.begin(); // GCC's stdc++ lib doesn't return an it! -#endif - } else - ++I; - - bool Changed = true; - while (Changed) { - // Eliminate shadow nodes that are not distinguishable from some other - // node in the graph... - // - Changed = UnlinkUndistinguishableNodes(); - - // Eliminate shadow nodes that are now extraneous due to linking... - Changed |= RemoveUnreachableNodes(); - } -} diff --git a/lib/Analysis/DataStructure/FunctionRepBuilder.h b/lib/Analysis/DataStructure/FunctionRepBuilder.h deleted file mode 100644 index 9965759fec4..00000000000 --- a/lib/Analysis/DataStructure/FunctionRepBuilder.h +++ /dev/null @@ -1,135 +0,0 @@ -//===- FunctionRepBuilder.h - Structures for graph building ------*- C++ -*--=// -// -// This file defines the FunctionRepBuilder and InitVisitor classes that are -// used to build the local data structure graph for a method. -// -//===----------------------------------------------------------------------===// - -#ifndef DATA_STRUCTURE_METHOD_REP_BUILDER_H -#define DATA_STRUCTURE_METHOD_REP_BUILDER_H - -#include "llvm/Analysis/DataStructure.h" -#include "llvm/Support/InstVisitor.h" - -// DEBUG_DATA_STRUCTURE_CONSTRUCTION - Define this to 1 if you want debug output -//#define DEBUG_DATA_STRUCTURE_CONSTRUCTION 1 - -class FunctionRepBuilder; - -// InitVisitor - Used to initialize the worklists for data structure analysis. -// Iterate over the instructions in the method, creating nodes for malloc and -// call instructions. Add all uses of these to the worklist of instructions -// to process. -// -class InitVisitor : public InstVisitor { - FunctionRepBuilder *Rep; - Function *Func; -public: - InitVisitor(FunctionRepBuilder *R, Function *F) : Rep(R), Func(F) {} - - void visitCallInst(CallInst &CI); - void visitAllocationInst(AllocationInst &AI); - void visitInstruction(Instruction &I); - - // visitOperand - If the specified instruction operand is a global value, add - // a node for it... - // - void visitOperand(Value *V); -}; - - -// FunctionRepBuilder - This builder object creates the datastructure graph for -// a method. -// -class FunctionRepBuilder : InstVisitor { - friend class InitVisitor; - FunctionDSGraph *F; - PointerValSet RetNode; - - // ValueMap - Mapping between values we are processing and the possible - // datastructures that they may point to... - std::map ValueMap; - - // CallMap - Keep track of which call nodes correspond to which call insns. - // The reverse mapping is stored in the CallDSNodes themselves. - // - std::map CallMap; - - // Worklist - Vector of (pointer typed) instructions to process still... - std::vector WorkList; - - // Nodes - Keep track of all of the resultant nodes, because there may not - // be edges connecting these to anything. - // - std::vector AllocNodes; - std::vector ShadowNodes; - std::vector GlobalNodes; - std::vector CallNodes; - - // addAllUsesToWorkList - Add all of the instructions users of the specified - // value to the work list for further processing... - // - void addAllUsesToWorkList(Value *V); - -public: - FunctionRepBuilder(FunctionDSGraph *f) : F(f) { - initializeWorkList(F->getFunction()); - processWorkList(); - } - - const std::vector &getAllocNodes() const { return AllocNodes; } - const std::vector &getShadowNodes() const {return ShadowNodes;} - const std::vector &getGlobalNodes() const {return GlobalNodes;} - const std::vector &getCallNodes() const { return CallNodes; } - - - ShadowDSNode *makeSynthesizedShadow(const Type *Ty, DSNode *Parent); - - const PointerValSet &getRetNode() const { return RetNode; } - - const std::map &getValueMap() const { return ValueMap; } -private: - static PointerVal getIndexedPointerDest(const PointerVal &InP, - const MemAccessInst &MAI); - - void initializeWorkList(Function *Func); - void processWorkList() { - // While the worklist still has instructions to process, process them! - while (!WorkList.empty()) { - Instruction *I = WorkList.back(); WorkList.pop_back(); - -#ifdef DEBUG_DATA_STRUCTURE_CONSTRUCTION - std::cerr << "Processing worklist inst: " << I; -#endif - - visit(*I); // Dispatch to a visitXXX function based on instruction type... -#ifdef DEBUG_DATA_STRUCTURE_CONSTRUCTION - if (I->hasName() && ValueMap.count(I)) { - std::cerr << "Inst %" << I->getName() << " value is:\n"; - ValueMap[I].print(std::cerr); - } -#endif - } - } - - //===--------------------------------------------------------------------===// - // Functions used to process the worklist of instructions... - // - // Allow the visitor base class to invoke these methods... - friend class InstVisitor; - - void visitGetElementPtrInst(GetElementPtrInst &GEP); - void visitReturnInst(ReturnInst &RI); - void visitLoadInst(LoadInst &LI); - void visitStoreInst(StoreInst &SI); - void visitCallInst(CallInst &CI); - void visitPHINode(PHINode &PN); - void visitSetCondInst(SetCondInst &SCI) {} // SetEQ & friends are ignored - void visitFreeInst(FreeInst &FI) {} // Ignore free instructions - void visitInstruction(Instruction &I) { - std::cerr << "\n\n\nUNKNOWN INSTRUCTION type: " << I << "\n\n\n"; - assert(0 && "Cannot proceed"); - } -}; - -#endif diff --git a/lib/Analysis/DataStructure/NodeImpl.cpp b/lib/Analysis/DataStructure/NodeImpl.cpp deleted file mode 100644 index 1b3fb76505e..00000000000 --- a/lib/Analysis/DataStructure/NodeImpl.cpp +++ /dev/null @@ -1,470 +0,0 @@ -//===- NodeImpl.cpp - Implement the data structure analysis nodes ---------===// -// -// Implement the LLVM data structure analysis library. -// -//===----------------------------------------------------------------------===// - -#include "llvm/Analysis/DataStructureGraph.h" -#include "llvm/Assembly/Writer.h" -#include "llvm/DerivedTypes.h" -#include "llvm/Function.h" -#include "llvm/iMemory.h" -#include "llvm/iOther.h" -#include "Support/STLExtras.h" -#include -#include -using std::map; -using std::string; - -bool AllocDSNode::isEquivalentTo(DSNode *Node) const { - if (AllocDSNode *N = dyn_cast(Node)) - return getType() == Node->getType(); - //&& isAllocaNode() == N->isAllocaNode(); - return false; -} - -void AllocDSNode::mergeInto(DSNode *Node) const { - // Make sure the merged node is variable size if this node is var size - AllocDSNode *N = cast(Node); - N->isVarSize |= isVarSize; -} - -bool GlobalDSNode::isEquivalentTo(DSNode *Node) const { - if (const GlobalDSNode *G = dyn_cast(Node)) { - if (G->Val != Val) return false; - - // Check that the outgoing links are identical... - assert(getNumLinks() == G->getNumLinks() && "Not identical shape?"); - for (unsigned i = 0, e = getNumLinks(); i != e; ++i) - if (getLink(i) != G->getLink(i)) // Check links - return false; - return true; - } - return false; -} - -// Call node equivalency - Two call nodes are identical if all of the outgoing -// links are the same, AND if all of the incoming links are identical. -// -bool CallDSNode::isEquivalentTo(DSNode *Node) const { - if (CallDSNode *C = dyn_cast(Node)) { - if (getReferrers().size() != C->getReferrers().size() || - C->getType() != getType()) - return false; // Quick check... - - // Check that the outgoing links are identical... - assert(getNumLinks() == C->getNumLinks() && "Not identical shape?"); - for (unsigned i = 0, e = getNumLinks(); i != e; ++i) - if (getLink(i) != C->getLink(i)) // Check links - return false; - - - std::vector Refs1 = C->getReferrers(); - std::vector Refs2 = getReferrers(); - - sort(Refs1.begin(), Refs1.end()); - sort(Refs2.begin(), Refs2.end()); - if (Refs1 != Refs2) return false; // Incoming edges different? - - // Check that all outgoing links are the same... - return C->ArgLinks == ArgLinks; // Check that the arguments are identical - } - return false; -} - -// NodesAreEquivalent - Check to see if the nodes are equivalent in all ways -// except node type. Since we know N1 is a shadow node, N2 is allowed to be -// any type. -// -bool ShadowDSNode::isEquivalentTo(DSNode *Node) const { - return getType() == Node->getType(); -} - - - - -//===----------------------------------------------------------------------===// -// DSNode Class Implementation -// - -static void MapPVS(PointerValSet &PVSOut, const PointerValSet &PVSIn, - map &NodeMap, bool ReinitOk = false){ - assert((ReinitOk || PVSOut.empty()) && "Value set already initialized!"); - - for (unsigned i = 0, e = PVSIn.size(); i != e; ++i) - PVSOut.add(PointerVal(NodeMap[PVSIn[i].Node], PVSIn[i].Index)); -} - - - -unsigned countPointerFields(const Type *Ty) { - switch (Ty->getPrimitiveID()) { - case Type::StructTyID: { - const StructType *ST = cast(Ty); - unsigned Sum = 0; - for (unsigned i = 0, e = ST->getNumContainedTypes(); i != e; ++i) - Sum += countPointerFields(ST->getContainedType(i)); - - return Sum; - } - - case Type::ArrayTyID: - // All array elements are folded together... - return countPointerFields(cast(Ty)->getElementType()); - - case Type::PointerTyID: - return 1; - - default: // Some other type, just treat it like a scalar - return 0; - } -} - -DSNode::DSNode(enum NodeTy NT, const Type *T) : Ty(T), NodeType(NT) { - // Create field entries for all of the values in this type... - FieldLinks.resize(countPointerFields(getType())); -} - -void DSNode::removeReferrer(PointerValSet *PVS) { - std::vector::iterator I = std::find(Referrers.begin(), - Referrers.end(), PVS); - assert(I != Referrers.end() && "PVS not pointing to node!"); - Referrers.erase(I); -} - - -// removeAllIncomingEdges - Erase all edges in the graph that point to this node -void DSNode::removeAllIncomingEdges() { - while (!Referrers.empty()) - Referrers.back()->removePointerTo(this); -} - - -static void replaceIn(std::string &S, char From, const std::string &To) { - for (unsigned i = 0; i < S.size(); ) - if (S[i] == From) { - S.replace(S.begin()+i, S.begin()+i+1, - To.begin(), To.end()); - i += To.size(); - } else { - ++i; - } -} - -static void writeEdges(std::ostream &O, const void *SrcNode, - const char *SrcNodePortName, int SrcNodeIdx, - const PointerValSet &VS, const string &EdgeAttr = "") { - for (unsigned j = 0, je = VS.size(); j != je; ++j) { - O << "\t\tNode" << SrcNode << SrcNodePortName; - if (SrcNodeIdx != -1) O << SrcNodeIdx; - - O << " -> Node" << VS[j].Node; - if (VS[j].Index) - O << ":g" << VS[j].Index; - - if (!EdgeAttr.empty()) - O << "[" << EdgeAttr << "]"; - O << ";\n"; - } -} - -static string escapeLabel(const string &In) { - string Label(In); - replaceIn(Label, '\\', "\\\\\\\\"); // Escape caption... - replaceIn(Label, ' ', "\\ "); - replaceIn(Label, '{', "\\{"); - replaceIn(Label, '}', "\\}"); - return Label; -} - -void DSNode::dump() const { print(std::cerr); } - -void DSNode::print(std::ostream &O) const { - string Caption = escapeLabel(getCaption()); - - O << "\t\tNode" << (void*)this << " [ label =\"{" << Caption; - - const std::vector *Links = getAuxLinks(); - if (Links && !Links->empty()) { - O << "|{"; - for (unsigned i = 0; i < Links->size(); ++i) { - if (i) O << "|"; - O << ""; - } - O << "}"; - } - - if (!FieldLinks.empty()) { - O << "|{"; - for (unsigned i = 0; i < FieldLinks.size(); ++i) { - if (i) O << "|"; - O << ""; - } - O << "}"; - } - O << "}\"];\n"; - - if (Links) - for (unsigned i = 0; i < Links->size(); ++i) - writeEdges(O, this, ":f", i, (*Links)[i]); - for (unsigned i = 0; i < FieldLinks.size(); ++i) - writeEdges(O, this, ":g", i, FieldLinks[i]); -} - -void DSNode::mapNode(map &NodeMap, const DSNode *Old) { - assert(FieldLinks.size() == Old->FieldLinks.size() && - "Cloned nodes do not have the same number of links!"); - for (unsigned j = 0, je = FieldLinks.size(); j != je; ++j) - MapPVS(FieldLinks[j], Old->FieldLinks[j], NodeMap); - - // Map our SynthNodes... - assert(SynthNodes.empty() && "Synthnodes already mapped?"); - SynthNodes.reserve(Old->SynthNodes.size()); - for (unsigned i = 0, e = Old->SynthNodes.size(); i != e; ++i) - SynthNodes.push_back(std::make_pair(Old->SynthNodes[i].first, - (ShadowDSNode*)NodeMap[Old->SynthNodes[i].second])); -} - -AllocDSNode::AllocDSNode(AllocationInst *V, bool isvarsize) - : DSNode(NewNode, V->getType()->getElementType()), Allocation(V) { - - // Is variable size if incoming flag says so, or if allocation is var size - // already. - isVarSize = isvarsize || !isa(V->getArraySize()); -} - -bool AllocDSNode::isAllocaNode() const { - return isa(Allocation); -} - - -string AllocDSNode::getCaption() const { - std::stringstream OS; - OS << (isMallocNode() ? "new " : "alloca "); - - WriteTypeSymbolic(OS, getType(), - Allocation->getParent()->getParent()->getParent()); - if (isVarSize) - OS << "[ ]"; - return OS.str(); -} - -GlobalDSNode::GlobalDSNode(GlobalValue *V) - : DSNode(GlobalNode, V->getType()->getElementType()), Val(V) { -} - -string GlobalDSNode::getCaption() const { - std::stringstream OS; - if (isa(Val)) - OS << "fn "; - else - OS << "global "; - - WriteTypeSymbolic(OS, getType(), Val->getParent()); - return OS.str() + " %" + Val->getName(); -} - - -ShadowDSNode::ShadowDSNode(const Type *Ty, Module *M) : DSNode(ShadowNode, Ty) { - Mod = M; - ShadowParent = 0; -} - -ShadowDSNode::ShadowDSNode(const Type *Ty, Module *M, DSNode *ShadParent) - : DSNode(ShadowNode, Ty) { - Mod = M; - ShadowParent = ShadParent; -} - -std::string ShadowDSNode::getCaption() const { - std::stringstream OS; - OS << "shadow "; - WriteTypeSymbolic(OS, getType(), Mod); - return OS.str(); -} - -CallDSNode::CallDSNode(CallInst *ci) : DSNode(CallNode, ci->getType()), CI(ci) { - unsigned NumPtrs = 0; - for (unsigned i = 0, e = ci->getNumOperands(); i != e; ++i) - if (isa(ci->getOperand(i)->getType())) - NumPtrs++; - ArgLinks.resize(NumPtrs); -} - -string CallDSNode::getCaption() const { - std::stringstream OS; - if (const Function *CM = CI->getCalledFunction()) - OS << "call " << CM->getName(); - else - OS << "call "; - OS << ": "; - WriteTypeSymbolic(OS, getType(), - CI->getParent()->getParent()->getParent()); - return OS.str(); -} - -void CallDSNode::mapNode(map &NodeMap, - const DSNode *O) { - const CallDSNode *Old = cast(O); - DSNode::mapNode(NodeMap, Old); // Map base portions first... - - assert(ArgLinks.size() == Old->ArgLinks.size() && "# Arguments changed!?"); - for (unsigned i = 0, e = Old->ArgLinks.size(); i != e; ++i) - MapPVS(ArgLinks[i], Old->ArgLinks[i], NodeMap); -} - -void FunctionDSGraph::printFunction(std::ostream &O, - const char *Label) const { - O << "\tsubgraph cluster_" << Label << "_Function" << (void*)this << " {\n"; - O << "\t\tlabel=\"" << Label << " Function\\ " << Func->getName() << "\";\n"; - for (unsigned i = 0, e = AllocNodes.size(); i != e; ++i) - AllocNodes[i]->print(O); - for (unsigned i = 0, e = ShadowNodes.size(); i != e; ++i) - ShadowNodes[i]->print(O); - for (unsigned i = 0, e = GlobalNodes.size(); i != e; ++i) - GlobalNodes[i]->print(O); - for (unsigned i = 0, e = CallNodes.size(); i != e; ++i) - CallNodes[i]->print(O); - - if (RetNode.size()) { - O << "\t\tNode" << (void*)this << Label - << " [shape=\"ellipse\", label=\"Returns\"];\n"; - writeEdges(O, this, Label, -1, RetNode); - } - - O << "\n"; - for (std::map::const_iterator I = ValueMap.begin(), - E = ValueMap.end(); I != E; ++I) { - if (I->second.size()) { // Only output nodes with edges... - std::stringstream OS; - WriteTypeSymbolic(OS, I->first->getType(), Func->getParent()); - - // Create node for I->first - O << "\t\tNode" << (void*)I->first << Label << " [shape=\"" - << (isa(I->first) ? "ellipse" : "box") << "\", label=\"" - << escapeLabel(OS.str()) << "\\n%" << escapeLabel(I->first->getName()) - << "\",fontsize=\"12.0\",color=\"gray70\"];\n"; - - // add edges from I->first to all pointers in I->second - writeEdges(O, I->first, Label, -1, I->second, - "weight=\"0.9\",color=\"gray70\""); - } - } - - O << "\t}\n"; -} - -// Copy constructor - Since we copy the nodes over, we have to be sure to go -// through and fix pointers to point into the new graph instead of into the old -// graph... -// -FunctionDSGraph::FunctionDSGraph(const FunctionDSGraph &DSG) : Func(DSG.Func) { - std::vector Args; - RetNode = cloneFunctionIntoSelf(DSG, true, Args); -} - - -// cloneFunctionIntoSelf - Clone the specified method graph into the current -// method graph, returning the Return's set of the graph. If ValueMap is set -// to true, the ValueMap of the function is cloned into this function as well -// as the data structure graph itself. Regardless, the arguments value sets -// of DSG are copied into Args. -// -PointerValSet FunctionDSGraph::cloneFunctionIntoSelf(const FunctionDSGraph &DSG, - bool CloneValueMap, - std::vector &Args) { - map NodeMap; // Map from old graph to new graph... - unsigned StartAllocSize = AllocNodes.size(); - AllocNodes.reserve(StartAllocSize+DSG.AllocNodes.size()); - unsigned StartShadowSize = ShadowNodes.size(); - ShadowNodes.reserve(StartShadowSize+DSG.ShadowNodes.size()); - unsigned StartGlobalSize = GlobalNodes.size(); - GlobalNodes.reserve(StartGlobalSize+DSG.GlobalNodes.size()); - unsigned StartCallSize = CallNodes.size(); - CallNodes.reserve(StartCallSize+DSG.CallNodes.size()); - - // Clone all of the alloc nodes similarly... - for (unsigned i = 0, e = DSG.AllocNodes.size(); i != e; ++i) { - AllocDSNode *New = cast(DSG.AllocNodes[i]->clone()); - NodeMap[DSG.AllocNodes[i]] = New; - AllocNodes.push_back(New); - } - - // Clone all of the shadow nodes similarly... - for (unsigned i = 0, e = DSG.ShadowNodes.size(); i != e; ++i) { - ShadowDSNode *New = cast(DSG.ShadowNodes[i]->clone()); - NodeMap[DSG.ShadowNodes[i]] = New; - ShadowNodes.push_back(New); - } - - // Clone all of the global nodes... - for (unsigned i = 0, e = DSG.GlobalNodes.size(); i != e; ++i) { - GlobalDSNode *New = cast(DSG.GlobalNodes[i]->clone()); - NodeMap[DSG.GlobalNodes[i]] = New; - GlobalNodes.push_back(New); - } - - // Clone all of the call nodes... - for (unsigned i = 0, e = DSG.CallNodes.size(); i != e; ++i) { - CallDSNode *New = cast(DSG.CallNodes[i]->clone()); - NodeMap[DSG.CallNodes[i]] = New; - CallNodes.push_back(New); - } - - // Convert all of the links over in the nodes now that the map has been filled - // in all the way... - // - for (unsigned i = 0, e = DSG.AllocNodes.size(); i != e; ++i) - AllocNodes[i+StartAllocSize]->mapNode(NodeMap, DSG.AllocNodes[i]); - for (unsigned i = 0, e = DSG.ShadowNodes.size(); i != e; ++i) - ShadowNodes[i+StartShadowSize]->mapNode(NodeMap, DSG.ShadowNodes[i]); - for (unsigned i = 0, e = DSG.GlobalNodes.size(); i != e; ++i) - GlobalNodes[i+StartGlobalSize]->mapNode(NodeMap, DSG.GlobalNodes[i]); - for (unsigned i = 0, e = DSG.CallNodes.size(); i != e; ++i) - CallNodes[i+StartCallSize]->mapNode(NodeMap, DSG.CallNodes[i]); - - // Convert over the arguments... - Function *OF = DSG.getFunction(); - for (Function::aiterator I = OF->abegin(), E = OF->aend(); I != E; ++I) - if (isa(I->getType())) { - PointerValSet ArgPVS; - assert(DSG.getValueMap().find(I) != DSG.getValueMap().end()); - MapPVS(ArgPVS, DSG.getValueMap().find(I)->second, NodeMap); - assert(!ArgPVS.empty() && "Argument has no links!"); - Args.push_back(ArgPVS); - } - - - if (CloneValueMap) { - // Convert value map... the values themselves stay the same, just the nodes - // have to change... - // - for (std::map::const_iterator I =DSG.ValueMap.begin(), - E = DSG.ValueMap.end(); I != E; ++I) - MapPVS(ValueMap[I->first], I->second, NodeMap, true); - } - - // Convert over return node... - PointerValSet RetVals; - MapPVS(RetVals, DSG.RetNode, NodeMap); - return RetVals; -} - - -FunctionDSGraph::~FunctionDSGraph() { - RetNode.clear(); - ValueMap.clear(); - for_each(AllocNodes.begin(), AllocNodes.end(), - std::mem_fun(&DSNode::dropAllReferences)); - for_each(ShadowNodes.begin(), ShadowNodes.end(), - std::mem_fun(&DSNode::dropAllReferences)); - for_each(GlobalNodes.begin(), GlobalNodes.end(), - std::mem_fun(&DSNode::dropAllReferences)); - for_each(CallNodes.begin(), CallNodes.end(), - std::mem_fun(&DSNode::dropAllReferences)); - for_each(AllocNodes.begin(), AllocNodes.end(), deleter); - for_each(ShadowNodes.begin(), ShadowNodes.end(), deleter); - for_each(GlobalNodes.begin(), GlobalNodes.end(), deleter); - for_each(CallNodes.begin(), CallNodes.end(), deleter); -} - -- 2.34.1