X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=blobdiff_plain;f=lib%2FAnalysis%2FDataStructure%2FDataStructure.cpp;h=b125b5d67f396ad67dd8a461ed8dbc7cc5116362;hp=94ed3487e84bb2728b238e83e1142dc6e7b84ff8;hb=b576c94c15af9a440f69d9d03c2afead7971118c;hpb=8d32767da44c6b06033fe305f3fd8e73ba042b4a diff --git a/lib/Analysis/DataStructure/DataStructure.cpp b/lib/Analysis/DataStructure/DataStructure.cpp index 94ed3487e84..b125b5d67f3 100644 --- a/lib/Analysis/DataStructure/DataStructure.cpp +++ b/lib/Analysis/DataStructure/DataStructure.cpp @@ -1,4 +1,11 @@ //===- DataStructure.cpp - Implement the core data structure analysis -----===// +// +// The LLVM Compiler Infrastructure +// +// This file was developed by the LLVM research group and is distributed under +// the University of Illinois Open Source License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// // // This file implements the core data structure functionality. // @@ -9,6 +16,8 @@ #include "llvm/iOther.h" #include "llvm/DerivedTypes.h" #include "llvm/Target/TargetData.h" +#include "llvm/Assembly/Writer.h" +#include "Support/Debug.h" #include "Support/STLExtras.h" #include "Support/Statistic.h" #include "Support/Timer.h" @@ -58,8 +67,8 @@ DSNode::DSNode(const Type *T, DSGraph *G) // DSNode copy constructor... do not copy over the referrers list! DSNode::DSNode(const DSNode &N, DSGraph *G) - : NumReferrers(0), Size(N.Size), ParentGraph(G), Ty(N.Ty), - Links(N.Links), Globals(N.Globals), NodeType(N.NodeType) { + : NumReferrers(0), Size(N.Size), ParentGraph(G), + Ty(N.Ty), Links(N.Links), Globals(N.Globals), NodeType(N.NodeType) { G->getNodes().push_back(this); } @@ -68,6 +77,13 @@ void DSNode::assertOK() const { Ty == Type::VoidTy && (Size == 0 || (NodeType & DSNode::Array))) && "Node not OK!"); + + assert(ParentGraph && "Node has no parent?"); + const DSGraph::ScalarMapTy &SM = ParentGraph->getScalarMap(); + for (unsigned i = 0, e = Globals.size(); i != e; ++i) { + assert(SM.find(Globals[i]) != SM.end()); + assert(SM.find(Globals[i])->second.getNode() == this); + } } /// forwardNode - Mark this node as being obsolete, and all references to it @@ -474,9 +490,14 @@ bool DSNode::mergeTypeInfo(const Type *NewTy, unsigned Offset, return false; } - DEBUG(std::cerr << "MergeTypeInfo Folding OrigTy: " << Ty - << "\n due to:" << NewTy << " @ " << Offset << "!\n" - << "SubType: " << SubType << "\n\n"); + Module *M = 0; + if (getParentGraph()->getReturnNodes().size()) + M = getParentGraph()->getReturnNodes().begin()->first->getParent(); + DEBUG(std::cerr << "MergeTypeInfo Folding OrigTy: "; + WriteTypeSymbolic(std::cerr, Ty, M) << "\n due to:"; + WriteTypeSymbolic(std::cerr, NewTy, M) << " @ " << Offset << "!\n" + << "SubType: "; + WriteTypeSymbolic(std::cerr, SubType, M) << "\n\n"); if (FoldIfIncompatible) foldNodeCompletely(); return true; @@ -695,7 +716,7 @@ void DSNode::mergeWith(const DSNodeHandle &NH, unsigned Offset) { // Define here to avoid including iOther.h and BasicBlock.h in DSGraph.h Function &DSCallSite::getCaller() const { - return *Inst->getParent()->getParent(); + return *Site.getInstruction()->getParent()->getParent(); } @@ -703,21 +724,41 @@ Function &DSCallSite::getCaller() const { // DSGraph Implementation //===----------------------------------------------------------------------===// +/// getFunctionNames - Return a space separated list of the name of the +/// functions in this graph (if any) +std::string DSGraph::getFunctionNames() const { + switch (getReturnNodes().size()) { + case 0: return "Globals graph"; + case 1: return getReturnNodes().begin()->first->getName(); + default: + std::string Return; + for (DSGraph::ReturnNodesTy::const_iterator I = getReturnNodes().begin(); + I != getReturnNodes().end(); ++I) + Return += I->first->getName() + " "; + Return.erase(Return.end()-1, Return.end()); // Remove last space character + return Return; + } +} + + DSGraph::DSGraph(const DSGraph &G) : GlobalsGraph(0) { PrintAuxCalls = false; NodeMapTy NodeMap; cloneInto(G, ScalarMap, ReturnNodes, NodeMap); + InlinedGlobals.clear(); // clear set of "up-to-date" globals } DSGraph::DSGraph(const DSGraph &G, NodeMapTy &NodeMap) : GlobalsGraph(0) { PrintAuxCalls = false; cloneInto(G, ScalarMap, ReturnNodes, NodeMap); + InlinedGlobals.clear(); // clear set of "up-to-date" globals } DSGraph::~DSGraph() { FunctionCalls.clear(); AuxFunctionCalls.clear(); + InlinedGlobals.clear(); ScalarMap.clear(); ReturnNodes.clear(); @@ -745,6 +786,126 @@ void DSNode::remapLinks(DSGraph::NodeMapTy &OldNodeMap) { } +/// cloneReachableNodes - Clone all reachable nodes from *Node into the +/// current graph. This is a recursive function. The map OldNodeMap is a +/// map from the original nodes to their clones. +/// +void DSGraph::cloneReachableNodes(const DSNode* Node, + unsigned BitsToClear, + NodeMapTy& OldNodeMap, + NodeMapTy& CompletedNodeMap) { + if (CompletedNodeMap.find(Node) != CompletedNodeMap.end()) + return; + + DSNodeHandle& NH = OldNodeMap[Node]; + if (NH.getNode() != NULL) + return; + + // else Node has not yet been cloned: clone it and clear the specified bits + NH = new DSNode(*Node, this); // enters in OldNodeMap + NH.getNode()->maskNodeTypes(~BitsToClear); + + // now recursively clone nodes pointed to by this node + for (unsigned i = 0, e = Node->getNumLinks(); i != e; ++i) { + const DSNodeHandle &Link = Node->getLink(i << DS::PointerShift); + if (const DSNode* nextNode = Link.getNode()) + cloneReachableNodes(nextNode, BitsToClear, OldNodeMap, CompletedNodeMap); + } +} + +void DSGraph::cloneReachableSubgraph(const DSGraph& G, + const hash_set& RootNodes, + NodeMapTy& OldNodeMap, + NodeMapTy& CompletedNodeMap, + unsigned CloneFlags) { + if (RootNodes.empty()) + return; + + assert(OldNodeMap.empty() && "Returned OldNodeMap should be empty!"); + assert(&G != this && "Cannot clone graph into itself!"); + assert((*RootNodes.begin())->getParentGraph() == &G && + "Root nodes do not belong to this graph!"); + + // Remove alloca or mod/ref bits as specified... + unsigned BitsToClear = ((CloneFlags & StripAllocaBit)? DSNode::AllocaNode : 0) + | ((CloneFlags & StripModRefBits)? (DSNode::Modified | DSNode::Read) : 0) + | ((CloneFlags & StripIncompleteBit)? DSNode::Incomplete : 0); + BitsToClear |= DSNode::DEAD; // Clear dead flag... + + // Clone all nodes reachable from each root node, using a recursive helper + for (hash_set::const_iterator I = RootNodes.begin(), + E = RootNodes.end(); I != E; ++I) + cloneReachableNodes(*I, BitsToClear, OldNodeMap, CompletedNodeMap); + + // Merge the map entries in OldNodeMap and CompletedNodeMap to remap links + NodeMapTy MergedMap(OldNodeMap); + MergedMap.insert(CompletedNodeMap.begin(), CompletedNodeMap.end()); + + // Rewrite the links in the newly created nodes (the nodes in OldNodeMap) + // to point into the current graph. MergedMap gives the full mapping. + for (NodeMapTy::iterator I=OldNodeMap.begin(), E=OldNodeMap.end(); I!= E; ++I) + I->second.getNode()->remapLinks(MergedMap); + + // Now merge cloned global nodes with their copies in the current graph + // Just look through OldNodeMap to find such nodes! + for (NodeMapTy::iterator I=OldNodeMap.begin(), E=OldNodeMap.end(); I!= E; ++I) + if (I->first->isGlobalNode()) { + DSNodeHandle &GClone = I->second; + assert(GClone.getNode() != NULL && "NULL node in OldNodeMap?"); + const std::vector &Globals = I->first->getGlobals(); + for (unsigned gi = 0, ge = Globals.size(); gi != ge; ++gi) { + DSNodeHandle &GH = ScalarMap[Globals[gi]]; + GH.mergeWith(GClone); + } + } +} + + +/// updateFromGlobalGraph - This function rematerializes global nodes and +/// nodes reachable from them from the globals graph into the current graph. +/// It invokes cloneReachableSubgraph, using the globals in the current graph +/// as the roots. It also uses the vector InlinedGlobals to avoid cloning and +/// merging globals that are already up-to-date in the current graph. In +/// practice, in the TD pass, this is likely to be a large fraction of the +/// live global nodes in each function (since most live nodes are likely to +/// have been brought up-to-date in at _some_ caller or callee). +/// +void DSGraph::updateFromGlobalGraph() { + + // Use a map to keep track of the mapping between nodes in the globals graph + // and this graph for up-to-date global nodes, which do not need to be cloned. + NodeMapTy CompletedMap; + + // Put the live, non-up-to-date global nodes into a set and the up-to-date + // ones in the map above, mapping node in GlobalsGraph to the up-to-date node. + hash_set GlobalNodeSet; + for (ScalarMapTy::const_iterator I = getScalarMap().begin(), + E = getScalarMap().end(); I != E; ++I) + if (GlobalValue* GV = dyn_cast(I->first)) { + DSNode* GNode = I->second.getNode(); + assert(GNode && "No node for live global in current Graph?"); + if (const DSNode* GGNode = GlobalsGraph->ScalarMap[GV].getNode()) + if (InlinedGlobals.count(GV) == 0) // GNode is not up-to-date + GlobalNodeSet.insert(GGNode); + else { // GNode is up-to-date + CompletedMap[GGNode] = I->second; + assert(GGNode->getNumLinks() == GNode->getNumLinks() && + "Links dont match in a node that is supposed to be up-to-date?" + "\nremapLinks() will not work if the links don't match!"); + } + } + + // Clone the subgraph reachable from the vector of nodes in GlobalNodes + // and merge the cloned global nodes with the corresponding ones, if any. + NodeMapTy OldNodeMap; + cloneReachableSubgraph(*GlobalsGraph, GlobalNodeSet, OldNodeMap,CompletedMap); + + // Merging global nodes leaves behind unused nodes: get rid of them now. + OldNodeMap.clear(); // remove references before dead node cleanup + CompletedMap.clear(); // remove references before dead node cleanup + removeTriviallyDeadNodes(); +} + /// cloneInto - Clone the specified DSGraph into the current graph. The /// translated ScalarMap for the old function is filled into the OldValMap /// member, and the translated ReturnNodes map is returned into ReturnNodes. @@ -763,8 +924,9 @@ void DSGraph::cloneInto(const DSGraph &G, ScalarMapTy &OldValMap, Nodes.reserve(FN+G.Nodes.size()); // Remove alloca or mod/ref bits as specified... - unsigned BitsToClear =((CloneFlags & StripAllocaBit) ? DSNode::AllocaNode : 0) - | ((CloneFlags & StripModRefBits) ? (DSNode::Modified | DSNode::Read) : 0); + unsigned BitsToClear = ((CloneFlags & StripAllocaBit)? DSNode::AllocaNode : 0) + | ((CloneFlags & StripModRefBits)? (DSNode::Modified | DSNode::Read) : 0) + | ((CloneFlags & StripIncompleteBit)? DSNode::Incomplete : 0); BitsToClear |= DSNode::DEAD; // Clear dead flag... for (unsigned i = 0, e = G.Nodes.size(); i != e; ++i) { DSNode *Old = G.Nodes[i]; @@ -784,17 +946,15 @@ void DSGraph::cloneInto(const DSGraph &G, ScalarMapTy &OldValMap, // Copy the scalar map... merging all of the global nodes... for (ScalarMapTy::const_iterator I = G.ScalarMap.begin(), E = G.ScalarMap.end(); I != E; ++I) { - DSNodeHandle &H = OldValMap[I->first]; DSNodeHandle &MappedNode = OldNodeMap[I->second.getNode()]; - H.setOffset(I->second.getOffset()+MappedNode.getOffset()); - H.setNode(MappedNode.getNode()); + DSNodeHandle &H = OldValMap[I->first]; + H.mergeWith(DSNodeHandle(MappedNode.getNode(), + I->second.getOffset()+MappedNode.getOffset())); - if (isa(I->first)) { // Is this a global? - ScalarMapTy::iterator GVI = ScalarMap.find(I->first); - if (GVI != ScalarMap.end()) // Is the global value in this fn already? - GVI->second.mergeWith(H); - else - ScalarMap[I->first] = H; // Add global pointer to this graph + // If this is a global, add the global to this fn or merge if already exists + if (GlobalValue* GV = dyn_cast(I->first)) { + ScalarMap[GV].mergeWith(H); + InlinedGlobals.insert(GV); } } @@ -807,7 +967,7 @@ void DSGraph::cloneInto(const DSGraph &G, ScalarMapTy &OldValMap, } if (!(CloneFlags & DontCloneAuxCallNodes)) { - // Copy the auxillary function calls list... + // Copy the auxiliary function calls list... unsigned FC = AuxFunctionCalls.size(); // FirstCall AuxFunctionCalls.reserve(FC+G.AuxFunctionCalls.size()); for (unsigned i = 0, ei = G.AuxFunctionCalls.size(); i != ei; ++i) @@ -830,10 +990,9 @@ void DSGraph::cloneInto(const DSGraph &G, ScalarMapTy &OldValMap, /// merges the nodes specified in the call site with the formal arguments in the /// graph. /// -void DSGraph::mergeInGraph(DSCallSite &CS, Function &F, const DSGraph &Graph, - unsigned CloneFlags) { - ScalarMapTy OldValMap; - ScalarMapTy *ScalarMap = &OldValMap; +void DSGraph::mergeInGraph(const DSCallSite &CS, Function &F, + const DSGraph &Graph, unsigned CloneFlags) { + ScalarMapTy OldValMap, *ScalarMap; DSNodeHandle RetVal; // If this is not a recursive call, clone the graph into this graph... @@ -847,6 +1006,9 @@ void DSGraph::mergeInGraph(DSCallSite &CS, Function &F, const DSGraph &Graph, // structure graph. Strip locals and don't copy the list of callers ReturnNodesTy OldRetNodes; cloneInto(Graph, OldValMap, OldRetNodes, OldNodeMap, CloneFlags); + + // We need to map the arguments for the function to the cloned nodes old + // argument values. Do this now. RetVal = OldRetNodes[&F]; ScalarMap = &OldValMap; } else { @@ -879,6 +1041,20 @@ void DSGraph::mergeInGraph(DSCallSite &CS, Function &F, const DSGraph &Graph, } } +/// getCallSiteForArguments - Get the arguments and return value bindings for +/// the specified function in the current graph. +/// +DSCallSite DSGraph::getCallSiteForArguments(Function &F) const { + std::vector Args; + + for (Function::aiterator I = F.abegin(), E = F.aend(); I != E; ++I) + if (isPointerType(I->getType())) + Args.push_back(getScalarMap().find(I)->second); + + return DSCallSite(CallSite(), getReturnNodeFor(F), &F, Args); +} + + // markIncompleteNodes - Mark the specified node as having contents that are not // known with the current analysis we have performed. Because a node makes all @@ -893,7 +1069,7 @@ static void markIncompleteNode(DSNode *N) { // Actually mark the node N->setIncompleteMarker(); - // Recusively process children... + // Recursively process children... for (unsigned i = 0, e = N->getSize(); i < e; i += DS::PointerSize) if (DSNode *DSN = N->getLink(i).getNode()) markIncompleteNode(DSN); @@ -965,6 +1141,7 @@ static inline bool nodeContainsExternalFunction(const DSNode *N) { } static void removeIdenticalCalls(std::vector &Calls) { + // Remove trivially identical function calls unsigned NumFns = Calls.size(); std::sort(Calls.begin(), Calls.end()); // Sort by callee as primary key! @@ -1010,6 +1187,7 @@ static void removeIdenticalCalls(std::vector &Calls) { LastCalleeContainsExternalFunction = LastCalleeFunc->isExternal(); } +#if 1 if (LastCalleeContainsExternalFunction || // This should be more than enough context sensitivity! // FIXME: Evaluate how many times this is tripped! @@ -1023,6 +1201,7 @@ static void removeIdenticalCalls(std::vector &Calls) { else if (CS.getNumPtrArgs() > OCS.getNumPtrArgs()) OCS = CS; } +#endif } else { if (CS.isDirectCall()) { LastCalleeFunc = CS.getCalleeFunc(); @@ -1056,8 +1235,30 @@ void DSGraph::removeTriviallyDeadNodes() { removeIdenticalCalls(FunctionCalls); removeIdenticalCalls(AuxFunctionCalls); + // Loop over all of the nodes in the graph, calling getNode on each field. + // This will cause all nodes to update their forwarding edges, causing + // forwarded nodes to be delete-able. + for (unsigned i = 0, e = Nodes.size(); i != e; ++i) { + DSNode *N = Nodes[i]; + for (unsigned l = 0, e = N->getNumLinks(); l != e; ++l) + N->getLink(l*N->getPointerSize()).getNode(); + } + + // Likewise, forward any edges from the scalar nodes... + for (ScalarMapTy::iterator I = ScalarMap.begin(), E = ScalarMap.end(); + I != E; ++I) + I->second.getNode(); + + bool isGlobalsGraph = !GlobalsGraph; + for (unsigned i = 0; i != Nodes.size(); ++i) { DSNode *Node = Nodes[i]; + + // Do not remove *any* global nodes in the globals graph. + // This is a special case because such nodes may not have I, M, R flags set. + if (Node->isGlobalNode() && isGlobalsGraph) + continue; + if (Node->isComplete() && !Node->isModified() && !Node->isRead()) { // This is a useless node if it has no mod/ref info (checked above), // outgoing edges (which it cannot, as it is not modified in this @@ -1082,6 +1283,32 @@ void DSGraph::removeTriviallyDeadNodes() { Node->makeNodeDead(); } } + +#ifdef SANER_CODE_FOR_CHECKING_IF_ALL_REFERRERS_ARE_FROM_SCALARMAP + // + // *** It seems to me that we should be able to simply check if + // *** there are fewer or equal #referrers as #globals and make + // *** sure that all those referrers are in the scalar map? + // + if (Node->getNumReferrers() <= Node->getGlobals().size()) { + const std::vector &Globals = Node->getGlobals(); + +#ifndef NDEBUG + // Loop through and make sure all of the globals are referring directly + // to the node... + for (unsigned j = 0, e = Globals.size(); j != e; ++j) { + DSNode *N = ScalarMap.find(Globals[j])->second.getNode(); + assert(N == Node && "ScalarMap doesn't match globals list!"); + } +#endif + + // Make sure NumReferrers still agrees. The node is truly dead. + assert(Node->getNumReferrers() == Globals.size()); + for (unsigned j = 0, e = Globals.size(); j != e; ++j) + ScalarMap.erase(Globals[j]); + Node->makeNodeDead(); + } +#endif } if (Node->getNodeFlags() == 0 && Node->hasNoReferrers()) { @@ -1122,10 +1349,15 @@ void DSCallSite::markReachableNodes(hash_set &Nodes) { // marked as alive... // static bool CanReachAliveNodes(DSNode *N, hash_set &Alive, - hash_set &Visited) { + hash_set &Visited, + bool IgnoreGlobals) { if (N == 0) return false; assert(N->getForwardNode() == 0 && "Cannot mark a forwarded node!"); + // If this is a global node, it will end up in the globals graph anyway, so we + // don't need to worry about it. + if (IgnoreGlobals && N->isGlobalNode()) return false; + // If we know that this node is alive, return so! if (Alive.count(N)) return true; @@ -1135,7 +1367,8 @@ static bool CanReachAliveNodes(DSNode *N, hash_set &Alive, Visited.insert(N); // No recursion, insert into Visited... for (unsigned i = 0, e = N->getSize(); i < e; i += DS::PointerSize) - if (CanReachAliveNodes(N->getLink(i).getNode(), Alive, Visited)) { + if (CanReachAliveNodes(N->getLink(i).getNode(), Alive, Visited, + IgnoreGlobals)) { N->markReachableNodes(Alive); return true; } @@ -1146,14 +1379,17 @@ static bool CanReachAliveNodes(DSNode *N, hash_set &Alive, // alive nodes. // static bool CallSiteUsesAliveArgs(DSCallSite &CS, hash_set &Alive, - hash_set &Visited) { - if (CanReachAliveNodes(CS.getRetVal().getNode(), Alive, Visited)) + hash_set &Visited, + bool IgnoreGlobals) { + if (CanReachAliveNodes(CS.getRetVal().getNode(), Alive, Visited, + IgnoreGlobals)) return true; if (CS.isIndirectCall() && - CanReachAliveNodes(CS.getCalleeNode(), Alive, Visited)) + CanReachAliveNodes(CS.getCalleeNode(), Alive, Visited, IgnoreGlobals)) return true; for (unsigned i = 0, e = CS.getNumPtrArgs(); i != e; ++i) - if (CanReachAliveNodes(CS.getPtrArg(i).getNode(), Alive, Visited)) + if (CanReachAliveNodes(CS.getPtrArg(i).getNode(), Alive, Visited, + IgnoreGlobals)) return true; return false; } @@ -1165,11 +1401,13 @@ static bool CallSiteUsesAliveArgs(DSCallSite &CS, hash_set &Alive, // inlining graphs. // void DSGraph::removeDeadNodes(unsigned Flags) { + DEBUG(AssertGraphOK(); GlobalsGraph->AssertGraphOK()); + // Reduce the amount of work we have to do... remove dummy nodes left over by // merging... removeTriviallyDeadNodes(); - // FIXME: Merge nontrivially identical call nodes... + // FIXME: Merge non-trivially identical call nodes... // Alive - a set that holds all nodes found to be reachable/alive. hash_set Alive; @@ -1179,6 +1417,7 @@ void DSGraph::removeDeadNodes(unsigned Flags) { for (ScalarMapTy::iterator I = ScalarMap.begin(), E = ScalarMap.end(); I !=E;) if (isa(I->first)) { // Keep track of global nodes assert(I->second.getNode() && "Null global node?"); + assert(I->second.getNode()->isGlobalNode() && "Should be a global node!"); GlobalNodes.push_back(std::make_pair(I->first, I->second.getNode())); ++I; } else { @@ -1193,7 +1432,7 @@ void DSGraph::removeDeadNodes(unsigned Flags) { // these, prune the scalar pointing to it. // DSNode *N = I->second.getNode(); - if (N->isUnknownNode() && !isa(I->first)) { + if (N->getNodeFlags() == DSNode::UnknownNode && !isa(I->first)){ ScalarMap.erase(I++); } else { I->second.getNode()->markReachableNodes(Alive); @@ -1210,51 +1449,111 @@ void DSGraph::removeDeadNodes(unsigned Flags) { for (unsigned i = 0, e = FunctionCalls.size(); i != e; ++i) FunctionCalls[i].markReachableNodes(Alive); + // Copy and merge all information about globals to the GlobalsGraph + // if this is not a final pass (where unreachable globals are removed) + NodeMapTy GlobalNodeMap; + hash_set GlobalNodeSet; + + for (std::vector >::const_iterator + I = GlobalNodes.begin(), E = GlobalNodes.end(); I != E; ++I) + GlobalNodeSet.insert(I->second); // put global nodes into a set + + // Now find globals and aux call nodes that are already live or reach a live + // value (which makes them live in turn), and continue till no more are found. + // bool Iterate; hash_set Visited; std::vector AuxFCallsAlive(AuxFunctionCalls.size()); do { Visited.clear(); - // If any global nodes points to a non-global that is "alive", the global is + // If any global node points to a non-global that is "alive", the global is // "alive" as well... Remove it from the GlobalNodes list so we only have // unreachable globals in the list. // Iterate = false; - for (unsigned i = 0; i != GlobalNodes.size(); ++i) - if (CanReachAliveNodes(GlobalNodes[i].second, Alive, Visited)) { - std::swap(GlobalNodes[i--], GlobalNodes.back()); // Move to end to erase - GlobalNodes.pop_back(); // Erase efficiently - Iterate = true; - } - + if (!(Flags & DSGraph::RemoveUnreachableGlobals)) + for (unsigned i = 0; i != GlobalNodes.size(); ++i) + if (CanReachAliveNodes(GlobalNodes[i].second, Alive, Visited, + Flags & DSGraph::RemoveUnreachableGlobals)) { + std::swap(GlobalNodes[i--], GlobalNodes.back()); // Move to end to... + GlobalNodes.pop_back(); // erase efficiently + Iterate = true; + } + + // Mark only unresolvable call nodes for moving to the GlobalsGraph since + // call nodes that get resolved will be difficult to remove from that graph. + // The final unresolved call nodes must be handled specially at the end of + // the BU pass (i.e., in main or other roots of the call graph). for (unsigned i = 0, e = AuxFunctionCalls.size(); i != e; ++i) if (!AuxFCallsAlive[i] && - CallSiteUsesAliveArgs(AuxFunctionCalls[i], Alive, Visited)) { + (AuxFunctionCalls[i].isIndirectCall() + || CallSiteUsesAliveArgs(AuxFunctionCalls[i], Alive, Visited, + Flags & DSGraph::RemoveUnreachableGlobals))) { AuxFunctionCalls[i].markReachableNodes(Alive); AuxFCallsAlive[i] = true; Iterate = true; } } while (Iterate); - // Remove all dead aux function calls... + // Move dead aux function calls to the end of the list unsigned CurIdx = 0; for (unsigned i = 0, e = AuxFunctionCalls.size(); i != e; ++i) if (AuxFCallsAlive[i]) AuxFunctionCalls[CurIdx++].swap(AuxFunctionCalls[i]); + + // Copy and merge all global nodes and dead aux call nodes into the + // GlobalsGraph, and all nodes reachable from those nodes + // + if (!(Flags & DSGraph::RemoveUnreachableGlobals)) { + + // First, add the dead aux call nodes to the set of root nodes for cloning + // -- return value at this call site, if any + // -- actual arguments passed at this call site + // -- callee node at this call site, if this is an indirect call + for (unsigned i = CurIdx, e = AuxFunctionCalls.size(); i != e; ++i) { + if (const DSNode* RetNode = AuxFunctionCalls[i].getRetVal().getNode()) + GlobalNodeSet.insert(RetNode); + for (unsigned j=0, N=AuxFunctionCalls[i].getNumPtrArgs(); j < N; ++j) + if (const DSNode* ArgTarget=AuxFunctionCalls[i].getPtrArg(j).getNode()) + GlobalNodeSet.insert(ArgTarget); + if (AuxFunctionCalls[i].isIndirectCall()) + GlobalNodeSet.insert(AuxFunctionCalls[i].getCalleeNode()); + } + + // There are no "pre-completed" nodes so use any empty map for those. + // Strip all alloca bits since the current function is only for the BU pass. + // Strip all incomplete bits since they are short-lived properties and they + // will be correctly computed when rematerializing nodes into the functions. + // + NodeMapTy CompletedMap; + GlobalsGraph->cloneReachableSubgraph(*this, GlobalNodeSet, + GlobalNodeMap, CompletedMap, + (DSGraph::StripAllocaBit | + DSGraph::StripIncompleteBit)); + } + + // Remove all dead aux function calls... if (!(Flags & DSGraph::RemoveUnreachableGlobals)) { assert(GlobalsGraph && "No globals graph available??"); - // Move the unreachable call nodes to the globals graph... - GlobalsGraph->AuxFunctionCalls.insert(GlobalsGraph->AuxFunctionCalls.end(), - AuxFunctionCalls.begin()+CurIdx, - AuxFunctionCalls.end()); + + // Copy the unreachable call nodes to the globals graph, updating + // their target pointers using the GlobalNodeMap + for (unsigned i = CurIdx, e = AuxFunctionCalls.size(); i != e; ++i) + GlobalsGraph->AuxFunctionCalls.push_back(DSCallSite(AuxFunctionCalls[i], + GlobalNodeMap)); } // Crop all the useless ones out... AuxFunctionCalls.erase(AuxFunctionCalls.begin()+CurIdx, AuxFunctionCalls.end()); - // At this point, any nodes which are visited, but not alive, are nodes which - // should be moved to the globals graph. Loop over all nodes, eliminating - // completely unreachable nodes, and moving visited nodes to the globals graph + // We are finally done with the GlobalNodeMap so we can clear it and + // then get rid of unused nodes in the GlobalsGraph produced by merging. + GlobalNodeMap.clear(); + GlobalsGraph->removeTriviallyDeadNodes(); + + // At this point, any nodes which are visited, but not alive, are nodes + // which can be removed. Loop over all nodes, eliminating completely + // unreachable nodes. // std::vector DeadNodes; DeadNodes.reserve(Nodes.size()); @@ -1263,57 +1562,23 @@ void DSGraph::removeDeadNodes(unsigned Flags) { DSNode *N = Nodes[i]; Nodes[i--] = Nodes.back(); // move node to end of vector Nodes.pop_back(); // Erase node from alive list. - if (!(Flags & DSGraph::RemoveUnreachableGlobals) && // Not in TD pass - Visited.count(N)) { // Visited but not alive? - GlobalsGraph->Nodes.push_back(N); // Move node to globals graph - N->setParentGraph(GlobalsGraph); - } else { // Otherwise, delete the node - assert((!N->isGlobalNode() || - (Flags & DSGraph::RemoveUnreachableGlobals)) - && "Killing a global?"); - //std::cerr << "[" << i+1 << "/" << DeadNodes.size() - // << "] Node is dead: "; N->dump(); - DeadNodes.push_back(N); - N->dropAllReferences(); - } + DeadNodes.push_back(N); + N->dropAllReferences(); } else { assert(Nodes[i]->getForwardNode() == 0 && "Alive forwarded node?"); } - // Now that the nodes have either been deleted or moved to the globals graph, - // loop over the scalarmap, updating the entries for globals... - // - if (!(Flags & DSGraph::RemoveUnreachableGlobals)) { // Not in the TD pass? - // In this array we start the remapping, which can cause merging. Because - // of this, the DSNode pointers in GlobalNodes may be invalidated, so we - // must always go through the ScalarMap (which contains DSNodeHandles [which - // cannot be invalidated by merging]). - // - for (unsigned i = 0, e = GlobalNodes.size(); i != e; ++i) { - Value *G = GlobalNodes[i].first; - ScalarMapTy::iterator I = ScalarMap.find(G); - assert(I != ScalarMap.end() && "Global not in scalar map anymore?"); - assert(I->second.getNode() && "Global not pointing to anything?"); - assert(!Alive.count(I->second.getNode()) && "Node is alive??"); - GlobalsGraph->ScalarMap[G].mergeWith(I->second); - assert(GlobalsGraph->ScalarMap[G].getNode() && - "Global not pointing to anything?"); - ScalarMap.erase(I); - } - - // Merging leaves behind silly nodes, we remove them to avoid polluting the - // globals graph. - if (!GlobalNodes.empty()) - GlobalsGraph->removeTriviallyDeadNodes(); - } else { - // If we are in the top-down pass, remove all unreachable globals from the - // ScalarMap... - for (unsigned i = 0, e = GlobalNodes.size(); i != e; ++i) + // Remove all unreachable globals from the ScalarMap. + // If flag RemoveUnreachableGlobals is set, GlobalNodes has only dead nodes. + // In either case, the dead nodes will not be in the set Alive. + for (unsigned i = 0, e = GlobalNodes.size(); i != e; ++i) { + assert(((Flags & DSGraph::RemoveUnreachableGlobals) || + !Alive.count(GlobalNodes[i].second)) && "huh? non-dead global"); + if (!Alive.count(GlobalNodes[i].second)) ScalarMap.erase(GlobalNodes[i].first); } - // Loop over all of the dead nodes now, deleting them since their referrer - // count is zero. + // Delete all dead nodes now since their referrer counts are zero. for (unsigned i = 0, e = DeadNodes.size(); i != e; ++i) delete DeadNodes[i]; @@ -1323,7 +1588,7 @@ void DSGraph::removeDeadNodes(unsigned Flags) { void DSGraph::AssertGraphOK() const { for (unsigned i = 0, e = Nodes.size(); i != e; ++i) Nodes[i]->assertOK(); - return; // FIXME: remove + for (ScalarMapTy::const_iterator I = ScalarMap.begin(), E = ScalarMap.end(); I != E; ++I) { assert(I->second.getNode() && "Null node in scalarmap!"); @@ -1337,3 +1602,32 @@ void DSGraph::AssertGraphOK() const { AssertCallNodesInGraph(); AssertAuxCallNodesInGraph(); } + +/// mergeInGlobalsGraph - This method is useful for clients to incorporate the +/// globals graph into the DS, BU or TD graph for a function. This code retains +/// all globals, i.e., does not delete unreachable globals after they are +/// inlined. +/// +void DSGraph::mergeInGlobalsGraph() { + NodeMapTy GlobalNodeMap; + ScalarMapTy OldValMap; + ReturnNodesTy OldRetNodes; + cloneInto(*GlobalsGraph, OldValMap, OldRetNodes, GlobalNodeMap, + DSGraph::KeepAllocaBit | DSGraph::DontCloneCallNodes | + DSGraph::DontCloneAuxCallNodes); + + // Now merge existing global nodes in the GlobalsGraph with their copies + for (ScalarMapTy::iterator I = ScalarMap.begin(), E = ScalarMap.end(); + I != E; ++I) + if (isa(I->first)) { // Found a global node + DSNodeHandle &GH = I->second; + DSNodeHandle &GGNodeH = GlobalsGraph->getScalarMap()[I->first]; + GH.mergeWith(GlobalNodeMap[GGNodeH.getNode()]); + } + + // Merging leaves behind unused nodes: get rid of them now. + GlobalNodeMap.clear(); + OldValMap.clear(); + OldRetNodes.clear(); + removeTriviallyDeadNodes(); +}