X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FDataStructure%2FDataStructure.cpp;h=4e326545cc5cc588a25270f6b4ccb6ae8e73a0a5;hb=d74ea2bbd8bb630331f35ead42d385249bd42af8;hp=3d3b0d36cc6d735b6d880aae6e55bd3e38bead41;hpb=3bc703ba22e8e04b4120dad6dffdf63bb373083c;p=oota-llvm.git diff --git a/lib/Analysis/DataStructure/DataStructure.cpp b/lib/Analysis/DataStructure/DataStructure.cpp index 3d3b0d36cc6..4e326545cc5 100644 --- a/lib/Analysis/DataStructure/DataStructure.cpp +++ b/lib/Analysis/DataStructure/DataStructure.cpp @@ -1,10 +1,10 @@ //===- 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. @@ -23,8 +23,10 @@ #include "llvm/Support/Debug.h" #include "llvm/ADT/DepthFirstIterator.h" #include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/SCCIterator.h" #include "llvm/ADT/Statistic.h" #include "llvm/Support/Timer.h" +#include #include using namespace llvm; @@ -37,9 +39,13 @@ namespace { Statistic<> NumDNE ("dsa", "Number of nodes removed by reachability"); Statistic<> NumTrivialDNE ("dsa", "Number of nodes trivially removed"); Statistic<> NumTrivialGlobalDNE("dsa", "Number of globals trivially removed"); -}; + static cl::opt + DSAFieldLimit("dsa-field-limit", cl::Hidden, + cl::desc("Number of fields to track before collapsing a node"), + cl::init(256)); +} -#if 1 +#if 0 #define TIME_REGION(VARNAME, DESC) \ NamedRegionTimer VARNAME(DESC) #else @@ -94,7 +100,7 @@ DSNodeHandle &DSScalarMap::AddGlobal(GlobalValue *GV) { return I->second; } } - + // Okay, this is either not an equivalenced global or it is the leader, it // will be inserted into the scalar map now. GlobalSet.insert(GV); @@ -118,10 +124,9 @@ DSNode::DSNode(const Type *T, DSGraph *G) // DSNode copy constructor... do not copy over the referrers list! DSNode::DSNode(const DSNode &N, DSGraph *G, bool NullLinks) : NumReferrers(0), Size(N.Size), ParentGraph(G), - Ty(N.Ty), NodeType(N.NodeType) { + Ty(N.Ty), Globals(N.Globals), NodeType(N.NodeType) { if (!NullLinks) { Links = N.Links; - Globals = N.Globals; } else Links.resize(N.Links.size()); // Create the appropriate number of null links G->addNode(this); @@ -163,7 +168,7 @@ void DSNode::forwardNode(DSNode *To, unsigned Offset) { Ty = Type::VoidTy; // Remove this node from the parent graph's Nodes list. - ParentGraph->unlinkNode(this); + ParentGraph->unlinkNode(this); ParentGraph = 0; } @@ -221,16 +226,16 @@ void DSNode::foldNodeCompletely() { DestNode->Ty = Type::VoidTy; DestNode->Size = 1; DestNode->Globals.swap(Globals); - + // Start forwarding to the destination node... forwardNode(DestNode, 0); - + if (!Links.empty()) { DestNode->Links.reserve(1); - + DSNodeHandle NH(DestNode); DestNode->Links.push_back(Links[0]); - + // If we have links, merge all of our outgoing links together... for (unsigned i = Links.size()-1; i != 0; --i) NH.getNode()->Links[0].mergeWith(Links[i]); @@ -328,7 +333,7 @@ namespace { ++SS.Idx; if (SS.Idx != ST->getNumElements()) { const StructLayout *SL = TD.getStructLayout(ST); - SS.Offset += + SS.Offset += unsigned(SL->MemberOffsets[SS.Idx]-SL->MemberOffsets[SS.Idx-1]); return; } @@ -388,7 +393,7 @@ namespace { static bool ElementTypesAreCompatible(const Type *T1, const Type *T2, bool AllowLargerT1, const TargetData &TD){ TypeElementWalker T1W(T1, TD), T2W(T2, TD); - + while (!T1W.isDone() && !T2W.isDone()) { if (T1W.getCurrentOffset() != T2W.getCurrentOffset()) return false; @@ -397,11 +402,11 @@ static bool ElementTypesAreCompatible(const Type *T1, const Type *T2, const Type *T2 = T2W.getCurrentType(); if (T1 != T2 && !T1->isLosslesslyConvertibleTo(T2)) return false; - + T1W.StepToNextType(); T2W.StepToNextType(); } - + return AllowLargerT1 || T1W.isDone(); } @@ -467,7 +472,7 @@ bool DSNode::mergeTypeInfo(const Type *NewTy, unsigned Offset, // collapse it. This can occur for fortran common blocks, which have stupid // things like { [100000000 x double], [1000000 x double] }. unsigned NumFields = (NewTySize+DS::PointerSize-1) >> DS::PointerShift; - if (NumFields > 64) { + if (NumFields > DSAFieldLimit) { foldNodeCompletely(); return true; } @@ -491,13 +496,75 @@ bool DSNode::mergeTypeInfo(const Type *NewTy, unsigned Offset, return true; } - if (Offset) { // We could handle this case, but we don't for now... + // If this node would have to have an unreasonable number of fields, just + // collapse it. This can occur for fortran common blocks, which have stupid + // things like { [100000000 x double], [1000000 x double] }. + unsigned NumFields = (NewTySize+Offset+DS::PointerSize-1) >> DS::PointerShift; + if (NumFields > DSAFieldLimit) { + foldNodeCompletely(); + return true; + } + + if (Offset) { + //handle some common cases: + // Ty: struct { t1, t2, t3, t4, ..., tn} + // NewTy: struct { offset, stuff...} + // try merge with NewTy: struct {t1, t2, stuff...} if offset lands exactly on a field in Ty + if (isa(NewTy) && isa(Ty)) { + DEBUG(std::cerr << "Ty: " << *Ty << "\nNewTy: " << *NewTy << "@" << Offset << "\n"); + unsigned O = 0; + const StructType *STy = cast(Ty); + const StructLayout &SL = *TD.getStructLayout(STy); + unsigned i = SL.getElementContainingOffset(Offset); + //Either we hit it exactly or give up + if (SL.MemberOffsets[i] != Offset) { + if (FoldIfIncompatible) foldNodeCompletely(); + return true; + } + std::vector nt; + for (unsigned x = 0; x < i; ++x) + nt.push_back(STy->getElementType(x)); + STy = cast(NewTy); + nt.insert(nt.end(), STy->element_begin(), STy->element_end()); + //and merge + STy = StructType::get(nt); + DEBUG(std::cerr << "Trying with: " << *STy << "\n"); + return mergeTypeInfo(STy, 0); + } + + //Ty: struct { t1, t2, t3 ... tn} + //NewTy T offset x + //try merge with NewTy: struct : {t1, t2, T} if offset lands on a field in Ty + if (isa(Ty)) { + DEBUG(std::cerr << "Ty: " << *Ty << "\nNewTy: " << *NewTy << "@" << Offset << "\n"); + unsigned O = 0; + const StructType *STy = cast(Ty); + const StructLayout &SL = *TD.getStructLayout(STy); + unsigned i = SL.getElementContainingOffset(Offset); + //Either we hit it exactly or give up + if (SL.MemberOffsets[i] != Offset) { + if (FoldIfIncompatible) foldNodeCompletely(); + return true; + } + std::vector nt; + for (unsigned x = 0; x < i; ++x) + nt.push_back(STy->getElementType(x)); + nt.push_back(NewTy); + //and merge + STy = StructType::get(nt); + DEBUG(std::cerr << "Trying with: " << *STy << "\n"); + return mergeTypeInfo(STy, 0); + } + std::cerr << "UNIMP: Trying to merge a growth type into " << "offset != 0: Collapsing!\n"; + abort(); if (FoldIfIncompatible) foldNodeCompletely(); return true; + } + // Okay, the situation is nice and simple, we are trying to merge a type in // at offset 0 that is bigger than our current type. Implement this by // switching to the new type and then merge in the smaller one, which should @@ -505,15 +572,6 @@ bool DSNode::mergeTypeInfo(const Type *NewTy, unsigned Offset, // ok, it will collapse the node as appropriate. // - // If this node would have to have an unreasonable number of fields, just - // collapse it. This can occur for fortran common blocks, which have stupid - // things like { [100000000 x double], [1000000 x double] }. - unsigned NumFields = (NewTySize+DS::PointerSize-1) >> DS::PointerShift; - if (NumFields > 64) { - foldNodeCompletely(); - return true; - } - const Type *OldTy = Ty; Ty = NewTy; NodeType &= ~Array; @@ -573,13 +631,13 @@ bool DSNode::mergeTypeInfo(const Type *NewTy, unsigned Offset, if (isa(SubType) && isa(NewTy)) return false; - unsigned SubTypeSize = SubType->isSized() ? + unsigned SubTypeSize = SubType->isSized() ? (unsigned)TD.getTypeSize(SubType) : 0; // Ok, we are getting desperate now. Check for physical subtyping, where we // just require each element in the node to be compatible. if (NewTySize <= SubTypeSize && NewTySize && NewTySize < 256 && - SubTypeSize && SubTypeSize < 256 && + SubTypeSize && SubTypeSize < 256 && ElementTypesAreCompatible(NewTy, SubType, !isArray(), TD)) return false; @@ -611,7 +669,7 @@ bool DSNode::mergeTypeInfo(const Type *NewTy, unsigned Offset, NextPadSize = NextSubTypeSize; break; default: ; - // fall out + // fall out } if (NextSubType == 0) @@ -667,6 +725,9 @@ bool DSNode::mergeTypeInfo(const Type *NewTy, unsigned Offset, void DSNode::addEdgeTo(unsigned Offset, const DSNodeHandle &NH) { if (NH.isNull()) return; // Nothing to do + if (isNodeCompletelyFolded()) + Offset = 0; + DSNodeHandle &ExistingEdge = getLink(Offset); if (!ExistingEdge.isNull()) { // Merge the two nodes... @@ -707,14 +768,14 @@ static void MergeSortedVectors(std::vector &Dest, } else { // Make a copy to the side of Dest... std::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 + + // 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()); } @@ -728,7 +789,7 @@ void DSNode::mergeGlobals(const std::vector &RHS) { // This function does the hard work of merging two nodes, CurNodeH // and NH after filtering out trivial cases and making sure that // CurNodeH.offset >= NH.offset. -// +// // ***WARNING*** // Since merging may cause either node to go away, we must always // use the node-handles to refer to the nodes. These node handles are @@ -761,7 +822,7 @@ void DSNode::MergeNodes(DSNodeHandle& CurNodeH, DSNodeHandle& NH) { #endif } - // Merge the type entries of the two nodes together... + // Merge the type entries of the two nodes together... if (NH.getNode()->Ty != Type::VoidTy) CurNodeH.getNode()->mergeTypeInfo(NH.getNode()->Ty, NOffset); assert(!CurNodeH.getNode()->isDeadNode()); @@ -916,7 +977,7 @@ DSNodeHandle ReachabilityCloner::getClonedNH(const DSNodeHandle &SrcNH) { DSNode *DN = new DSNode(*SN, &Dest, true /* Null out all links */); DN->maskNodeTypes(BitsToKeep); NH = DN; - + // Next, recursively clone all outgoing links as necessary. Note that // adding these links can cause the node to collapse itself at any time, and // the current node may be merged with arbitrary other nodes. For this @@ -939,7 +1000,7 @@ DSNodeHandle ReachabilityCloner::getClonedNH(const DSNodeHandle &SrcNH) { CN->addEdgeTo(MergeOffset, DestEdge); } } - + // If this node contains any globals, make sure they end up in the scalar // map with the correct offset. for (DSNode::globals_iterator I = SN->globals_begin(), E = SN->globals_end(); @@ -977,7 +1038,7 @@ void ReachabilityCloner::merge(const DSNodeHandle &NH, SCNH.getOffset()+SrcNH.getOffset())); return; // Nothing to do! } - + // Okay, so the source node has not already been cloned. Instead of creating // a new DSNode, only to merge it into the one we already have, try to perform // the merge in-place. The only case we cannot handle here is when the offset @@ -1006,8 +1067,8 @@ void ReachabilityCloner::merge(const DSNodeHandle &NH, } #endif } - - // Merge the type entries of the two nodes together... + + // Merge the type entries of the two nodes together... if (SN->getType() != Type::VoidTy && !DN->isNodeCompletelyFolded()) { DN->mergeTypeInfo(SN->getType(), NH.getOffset()-SrcNH.getOffset()); DN = NH.getNode(); @@ -1015,7 +1076,7 @@ void ReachabilityCloner::merge(const DSNodeHandle &NH, } assert(!DN->isDeadNode()); - + // Merge the NodeType information. DN->mergeNodeFlags(SN->getNodeFlags() & BitsToKeep); @@ -1060,7 +1121,7 @@ void ReachabilityCloner::merge(const DSNodeHandle &NH, // sure it is known that this is the representative node for the src node. SCNH = DSNodeHandle(NH.getNode(), NH.getOffset()-SrcNH.getOffset()); - // If the source node contained any globals, make sure to create entries + // If the source node contained any globals, make sure to create entries // in the scalar map for them! for (DSNode::globals_iterator I = SN->globals_begin(), E = SN->globals_end(); I != E; ++I) { @@ -1092,7 +1153,7 @@ void ReachabilityCloner::merge(const DSNodeHandle &NH, DSNode *CN = SCNH.getNode(); unsigned MergeOffset = ((i << DS::PointerShift)+SCNH.getOffset()) % CN->getSize(); - + DSNodeHandle Tmp = CN->getLink(MergeOffset); if (!Tmp.isNull()) { // Perform the recursive merging. Make sure to create a temporary NH, @@ -1120,7 +1181,7 @@ void ReachabilityCloner::mergeCallSite(DSCallSite &DestCS, merge(DestCS.getRetVal(), SrcCS.getRetVal()); unsigned MinArgs = DestCS.getNumPtrArgs(); if (SrcCS.getNumPtrArgs() < MinArgs) MinArgs = SrcCS.getNumPtrArgs(); - + for (unsigned a = 0; a != MinArgs; ++a) merge(DestCS.getPtrArg(a), SrcCS.getPtrArg(a)); @@ -1253,11 +1314,11 @@ void DSGraph::cloneInto(const DSGraph &G, unsigned CloneFlags) { New->maskNodeTypes(~BitsToClear); OldNodeMap[I] = New; } - + #ifndef NDEBUG Timer::addPeakMemoryMeasurement(); #endif - + // Rewrite the links in the new nodes to point into the current graph now. // Note that we don't loop over the node's list to do this. The problem is // that remaping links can cause recursive merging to happen, which means @@ -1303,24 +1364,51 @@ void DSGraph::cloneInto(const DSGraph &G, unsigned CloneFlags) { } } -static bool PathExistsToClonedNode(const DSNode *N, ReachabilityCloner &RC) { - if (N) - for (df_iterator I = df_begin(N), E = df_end(N); I != E; ++I) - if (RC.hasClonedNode(*I)) - return true; - return false; +/// spliceFrom - Logically perform the operation of cloning the RHS graph into +/// this graph, then clearing the RHS graph. Instead of performing this as +/// two seperate operations, do it as a single, much faster, one. +/// +void DSGraph::spliceFrom(DSGraph &RHS) { + // Change all of the nodes in RHS to think we are their parent. + for (NodeListTy::iterator I = RHS.Nodes.begin(), E = RHS.Nodes.end(); + I != E; ++I) + I->setParentGraph(this); + // Take all of the nodes. + Nodes.splice(Nodes.end(), RHS.Nodes); + + // Take all of the calls. + FunctionCalls.splice(FunctionCalls.end(), RHS.FunctionCalls); + AuxFunctionCalls.splice(AuxFunctionCalls.end(), RHS.AuxFunctionCalls); + + // Take all of the return nodes. + if (ReturnNodes.empty()) { + ReturnNodes.swap(RHS.ReturnNodes); + } else { + ReturnNodes.insert(RHS.ReturnNodes.begin(), RHS.ReturnNodes.end()); + RHS.ReturnNodes.clear(); + } + + // Merge the scalar map in. + ScalarMap.spliceFrom(RHS.ScalarMap); } -static bool PathExistsToClonedNode(const DSCallSite &CS, - ReachabilityCloner &RC) { - if (PathExistsToClonedNode(CS.getRetVal().getNode(), RC)) - return true; - for (unsigned i = 0, e = CS.getNumPtrArgs(); i != e; ++i) - if (PathExistsToClonedNode(CS.getPtrArg(i).getNode(), RC)) - return true; - return false; +/// spliceFrom - Copy all entries from RHS, then clear RHS. +/// +void DSScalarMap::spliceFrom(DSScalarMap &RHS) { + // Special case if this is empty. + if (ValueMap.empty()) { + ValueMap.swap(RHS.ValueMap); + GlobalSet.swap(RHS.GlobalSet); + } else { + GlobalSet.insert(RHS.GlobalSet.begin(), RHS.GlobalSet.end()); + for (ValueMapTy::iterator I = RHS.ValueMap.begin(), E = RHS.ValueMap.end(); + I != E; ++I) + ValueMap[I->first].mergeWith(I->second); + RHS.ValueMap.clear(); + } } + /// getFunctionArgumentsForCall - Given a function that is currently in this /// graph, return the DSNodeHandles that correspond to the pointer-compatible /// function arguments. The vector is filled in with the return value (or @@ -1329,113 +1417,203 @@ static bool PathExistsToClonedNode(const DSCallSite &CS, void DSGraph::getFunctionArgumentsForCall(Function *F, std::vector &Args) const { Args.push_back(getReturnNodeFor(*F)); - for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); AI != E; ++AI) + for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); + AI != E; ++AI) if (isPointerType(AI->getType())) { Args.push_back(getNodeForValue(AI)); assert(!Args.back().isNull() && "Pointer argument w/o scalarmap entry!?"); } } +namespace { + // HackedGraphSCCFinder - This is used to find nodes that have a path from the + // node to a node cloned by the ReachabilityCloner object contained. To be + // extra obnoxious it ignores edges from nodes that are globals, and truncates + // search at RC marked nodes. This is designed as an object so that + // intermediate results can be memoized across invocations of + // PathExistsToClonedNode. + struct HackedGraphSCCFinder { + ReachabilityCloner &RC; + unsigned CurNodeId; + std::vector SCCStack; + std::map > NodeInfo; + + HackedGraphSCCFinder(ReachabilityCloner &rc) : RC(rc), CurNodeId(1) { + // Remove null pointer as a special case. + NodeInfo[0] = std::make_pair(0, false); + } + + std::pair &VisitForSCCs(const DSNode *N); + + bool PathExistsToClonedNode(const DSNode *N) { + return VisitForSCCs(N).second; + } + + bool PathExistsToClonedNode(const DSCallSite &CS) { + if (PathExistsToClonedNode(CS.getRetVal().getNode())) + return true; + for (unsigned i = 0, e = CS.getNumPtrArgs(); i != e; ++i) + if (PathExistsToClonedNode(CS.getPtrArg(i).getNode())) + return true; + return false; + } + }; +} + +std::pair &HackedGraphSCCFinder:: +VisitForSCCs(const DSNode *N) { + std::map >::iterator + NodeInfoIt = NodeInfo.lower_bound(N); + if (NodeInfoIt != NodeInfo.end() && NodeInfoIt->first == N) + return NodeInfoIt->second; + + unsigned Min = CurNodeId++; + unsigned MyId = Min; + std::pair &ThisNodeInfo = + NodeInfo.insert(NodeInfoIt, + std::make_pair(N, std::make_pair(MyId, false)))->second; + + // Base case: if we find a global, this doesn't reach the cloned graph + // portion. + if (N->isGlobalNode()) { + ThisNodeInfo.second = false; + return ThisNodeInfo; + } + + // Base case: if this does reach the cloned graph portion... it does. :) + if (RC.hasClonedNode(N)) { + ThisNodeInfo.second = true; + return ThisNodeInfo; + } + + SCCStack.push_back(N); + + // Otherwise, check all successors. + bool AnyDirectSuccessorsReachClonedNodes = false; + for (DSNode::const_edge_iterator EI = N->edge_begin(), EE = N->edge_end(); + EI != EE; ++EI) + if (DSNode *Succ = EI->getNode()) { + std::pair &SuccInfo = VisitForSCCs(Succ); + if (SuccInfo.first < Min) Min = SuccInfo.first; + AnyDirectSuccessorsReachClonedNodes |= SuccInfo.second; + } + + if (Min != MyId) + return ThisNodeInfo; // Part of a large SCC. Leave self on stack. + + if (SCCStack.back() == N) { // Special case single node SCC. + SCCStack.pop_back(); + ThisNodeInfo.second = AnyDirectSuccessorsReachClonedNodes; + return ThisNodeInfo; + } + + // Find out if any direct successors of any node reach cloned nodes. + if (!AnyDirectSuccessorsReachClonedNodes) + for (unsigned i = SCCStack.size()-1; SCCStack[i] != N; --i) + for (DSNode::const_edge_iterator EI = N->edge_begin(), EE = N->edge_end(); + EI != EE; ++EI) + if (DSNode *N = EI->getNode()) + if (NodeInfo[N].second) { + AnyDirectSuccessorsReachClonedNodes = true; + goto OutOfLoop; + } +OutOfLoop: + // If any successor reaches a cloned node, mark all nodes in this SCC as + // reaching the cloned node. + if (AnyDirectSuccessorsReachClonedNodes) + while (SCCStack.back() != N) { + NodeInfo[SCCStack.back()].second = true; + SCCStack.pop_back(); + } + SCCStack.pop_back(); + ThisNodeInfo.second = true; + return ThisNodeInfo; +} + /// mergeInCallFromOtherGraph - This graph merges in the minimal number of /// nodes from G2 into 'this' graph, merging the bindings specified by the /// call site (in this graph) with the bindings specified by the vector in G2. /// The two DSGraphs must be different. /// -void DSGraph::mergeInGraph(const DSCallSite &CS, +void DSGraph::mergeInGraph(const DSCallSite &CS, std::vector &Args, const DSGraph &Graph, unsigned CloneFlags) { TIME_REGION(X, "mergeInGraph"); - // If this is not a recursive call, clone the graph into this graph... - if (&Graph != this) { - // Clone the callee's graph into the current graph, keeping track of where - // scalars in the old graph _used_ to point, and of the new nodes matching - // nodes of the old graph. - ReachabilityCloner RC(*this, Graph, CloneFlags); - - // Map the return node pointer over. - if (!CS.getRetVal().isNull()) - RC.merge(CS.getRetVal(), Args[0]); - - // Map over all of the arguments. - for (unsigned i = 0, e = CS.getNumPtrArgs(); i != e; ++i) { - if (i == Args.size()-1) - break; - - // Add the link from the argument scalar to the provided value. - RC.merge(CS.getPtrArg(i), Args[i+1]); - } - - // If requested, copy all of the calls. - if (!(CloneFlags & DontCloneCallNodes)) { - // Copy the function calls list. - for (fc_iterator I = Graph.fc_begin(), E = Graph.fc_end(); I != E; ++I) - FunctionCalls.push_back(DSCallSite(*I, RC)); - } + assert((CloneFlags & DontCloneCallNodes) && + "Doesn't support copying of call nodes!"); - // If the user has us copying aux calls (the normal case), set up a data - // structure to keep track of which ones we've copied over. - std::set CopiedAuxCall; - - // Clone over all globals that appear in the caller and callee graphs. - hash_set NonCopiedGlobals; - for (DSScalarMap::global_iterator GI = Graph.getScalarMap().global_begin(), - E = Graph.getScalarMap().global_end(); GI != E; ++GI) - if (GlobalVariable *GV = dyn_cast(*GI)) - if (ScalarMap.count(GV)) - RC.merge(ScalarMap[GV], Graph.getNodeForValue(GV)); - else - NonCopiedGlobals.insert(GV); - - // If the global does not appear in the callers graph we generally don't - // want to copy the node. However, if there is a path from the node global - // node to a node that we did copy in the graph, we *must* copy it to - // maintain the connection information. Every time we decide to include a - // new global, this might make other globals live, so we must iterate - // unfortunately. - bool MadeChange = true; - while (MadeChange) { - MadeChange = false; - for (hash_set::iterator I = NonCopiedGlobals.begin(); - I != NonCopiedGlobals.end();) { - DSNode *GlobalNode = Graph.getNodeForValue(*I).getNode(); - if (RC.hasClonedNode(GlobalNode)) { - // Already cloned it, remove from set. - NonCopiedGlobals.erase(I++); - MadeChange = true; - } else if (PathExistsToClonedNode(GlobalNode, RC)) { - RC.getClonedNH(Graph.getNodeForValue(*I)); - NonCopiedGlobals.erase(I++); - MadeChange = true; - } else { - ++I; - } - } - - // If requested, copy any aux calls that can reach copied nodes. - if (!(CloneFlags & DontCloneAuxCallNodes)) { - for (afc_iterator I = Graph.afc_begin(), E = Graph.afc_end(); I!=E; ++I) - if (CopiedAuxCall.insert(&*I).second && - PathExistsToClonedNode(*I, RC)) { - AuxFunctionCalls.push_back(DSCallSite(*I, RC)); - MadeChange = true; - } - } - } - - } else { + // If this is not a recursive call, clone the graph into this graph... + if (&Graph == this) { // Merge the return value with the return value of the context. Args[0].mergeWith(CS.getRetVal()); - + // Resolve all of the function arguments. for (unsigned i = 0, e = CS.getNumPtrArgs(); i != e; ++i) { if (i == Args.size()-1) break; - + // Add the link from the argument scalar to the provided value. Args[i+1].mergeWith(CS.getPtrArg(i)); } + return; + } + + // Clone the callee's graph into the current graph, keeping track of where + // scalars in the old graph _used_ to point, and of the new nodes matching + // nodes of the old graph. + ReachabilityCloner RC(*this, Graph, CloneFlags); + + // Map the return node pointer over. + if (!CS.getRetVal().isNull()) + RC.merge(CS.getRetVal(), Args[0]); + + // Map over all of the arguments. + for (unsigned i = 0, e = CS.getNumPtrArgs(); i != e; ++i) { + if (i == Args.size()-1) + break; + + // Add the link from the argument scalar to the provided value. + RC.merge(CS.getPtrArg(i), Args[i+1]); } + + // We generally don't want to copy global nodes or aux calls from the callee + // graph to the caller graph. However, we have to copy them if there is a + // path from the node to a node we have already copied which does not go + // through another global. Compute the set of node that can reach globals and + // aux call nodes to copy over, then do it. + std::vector AuxCallToCopy; + std::vector GlobalsToCopy; + + // NodesReachCopiedNodes - Memoize results for efficiency. Contains a + // true/false value for every visited node that reaches a copied node without + // going through a global. + HackedGraphSCCFinder SCCFinder(RC); + + if (!(CloneFlags & DontCloneAuxCallNodes)) + for (afc_iterator I = Graph.afc_begin(), E = Graph.afc_end(); I!=E; ++I) + if (SCCFinder.PathExistsToClonedNode(*I)) + AuxCallToCopy.push_back(&*I); + + const DSScalarMap &GSM = Graph.getScalarMap(); + for (DSScalarMap::global_iterator GI = GSM.global_begin(), + E = GSM.global_end(); GI != E; ++GI) { + DSNode *GlobalNode = Graph.getNodeForValue(*GI).getNode(); + for (DSNode::edge_iterator EI = GlobalNode->edge_begin(), + EE = GlobalNode->edge_end(); EI != EE; ++EI) + if (SCCFinder.PathExistsToClonedNode(EI->getNode())) { + GlobalsToCopy.push_back(*GI); + break; + } + } + + // Copy aux calls that are needed. + for (unsigned i = 0, e = AuxCallToCopy.size(); i != e; ++i) + AuxFunctionCalls.push_back(DSCallSite(*AuxCallToCopy[i], RC)); + + // Copy globals that are needed. + for (unsigned i = 0, e = GlobalsToCopy.size(); i != e; ++i) + RC.getClonedNH(Graph.getNodeForValue(GlobalsToCopy[i])); } @@ -1540,7 +1718,8 @@ void DSGraph::markIncompleteNodes(unsigned Flags) { for (ReturnNodesTy::iterator FI = ReturnNodes.begin(), E =ReturnNodes.end(); FI != E; ++FI) { Function &F = *FI->first; - for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; ++I) + for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); + I != E; ++I) if (isPointerType(I->getType())) markIncompleteNode(getNodeForValue(I).getNode()); markIncompleteNode(FI->second.getNode()); @@ -1574,22 +1753,20 @@ static inline void killIfUselessEdge(DSNodeHandle &Edge) { Edge.setTo(0, 0); // Kill the edge! } -#if 0 static inline bool nodeContainsExternalFunction(const DSNode *N) { - const std::vector &Globals = N->getGlobals(); - for (unsigned i = 0, e = Globals.size(); i != e; ++i) - if (Globals[i]->isExternal() && isa(Globals[i])) - return true; + std::vector Funcs; + N->addFullFunctionList(Funcs); + for (unsigned i = 0, e = Funcs.size(); i != e; ++i) + if (Funcs[i]->isExternal()) return true; return false; } -#endif static void removeIdenticalCalls(std::list &Calls) { // Remove trivially identical function calls Calls.sort(); // Sort by callee as primary key! // Scan the call list cleaning it up as necessary... - DSNode *LastCalleeNode = 0; + DSNodeHandle LastCalleeNode; Function *LastCalleeFunc = 0; unsigned NumDuplicateCalls = 0; bool LastCalleeContainsExternalFunction = false; @@ -1600,17 +1777,41 @@ static void removeIdenticalCalls(std::list &Calls) { DSCallSite &CS = *I; std::list::iterator OldIt = I++; - // If the Callee is a useless edge, this must be an unreachable call site, - // eliminate it. - if (CS.isIndirectCall() && CS.getCalleeNode()->getNumReferrers() == 1 && - CS.getCalleeNode()->isComplete() && - CS.getCalleeNode()->getGlobalsList().empty()) { // No useful info? + if (!CS.isIndirectCall()) { + LastCalleeNode = 0; + } else { + DSNode *Callee = CS.getCalleeNode(); + + // If the Callee is a useless edge, this must be an unreachable call site, + // eliminate it. + if (Callee->getNumReferrers() == 1 && Callee->isComplete() && + Callee->getGlobalsList().empty()) { // No useful info? #ifndef NDEBUG - std::cerr << "WARNING: Useless call site found.\n"; + std::cerr << "WARNING: Useless call site found.\n"; #endif - Calls.erase(OldIt); - ++NumDeleted; - continue; + Calls.erase(OldIt); + ++NumDeleted; + continue; + } + + // If the last call site in the list has the same callee as this one, and + // if the callee contains an external function, it will never be + // resolvable, just merge the call sites. + if (!LastCalleeNode.isNull() && LastCalleeNode.getNode() == Callee) { + LastCalleeContainsExternalFunction = + nodeContainsExternalFunction(Callee); + + std::list::iterator PrevIt = OldIt; + --PrevIt; + PrevIt->mergeWith(CS); + + // No need to keep this call anymore. + Calls.erase(OldIt); + ++NumDeleted; + continue; + } else { + LastCalleeNode = Callee; + } } // If the return value or any arguments point to a void node with no @@ -1620,7 +1821,7 @@ static void removeIdenticalCalls(std::list &Calls) { killIfUselessEdge(CS.getRetVal()); for (unsigned a = 0, e = CS.getNumPtrArgs(); a != e; ++a) killIfUselessEdge(CS.getPtrArg(a)); - + #if 0 // If this call site calls the same function as the last call site, and if // the function pointer contains an external function, this node will @@ -1637,7 +1838,7 @@ static void removeIdenticalCalls(std::list &Calls) { else LastCalleeContainsExternalFunction = LastCalleeFunc->isExternal(); } - + // It is not clear why, but enabling this code makes DSA really // sensitive to node forwarding. Basically, with this enabled, DSA // performs different number of inlinings based on which nodes are @@ -1652,11 +1853,11 @@ static void removeIdenticalCalls(std::list &Calls) { NumDuplicateCalls > 20 #endif ) { - + std::list::iterator PrevIt = OldIt; --PrevIt; PrevIt->mergeWith(CS); - + // No need to keep this call anymore. Calls.erase(OldIt); ++NumDeleted; @@ -1676,6 +1877,7 @@ static void removeIdenticalCalls(std::list &Calls) { #endif if (I != Calls.end() && CS == *I) { + LastCalleeNode = 0; Calls.erase(OldIt); ++NumDeleted; continue; @@ -1817,7 +2019,7 @@ void DSNode::markReachableNodes(hash_set &ReachableNodes) const { void DSCallSite::markReachableNodes(hash_set &Nodes) const { getRetVal().getNode()->markReachableNodes(Nodes); if (isIndirectCall()) getCalleeNode()->markReachableNodes(Nodes); - + for (unsigned i = 0, e = getNumPtrArgs(); i != e; ++i) getPtrArg(i).getNode()->markReachableNodes(Nodes); } @@ -1914,8 +2116,8 @@ void DSGraph::removeDeadNodes(unsigned Flags) { GlobalNodes.push_back(std::make_pair(I->first, I->second.getNode())); // Make sure that all globals are cloned over as roots. - if (!(Flags & DSGraph::RemoveUnreachableGlobals)) { - DSGraph::ScalarMapTy::iterator SMI = + if (!(Flags & DSGraph::RemoveUnreachableGlobals) && GlobalsGraph) { + DSGraph::ScalarMapTy::iterator SMI = GlobalsGraph->getScalarMap().find(I->first); if (SMI != GlobalsGraph->getScalarMap().end()) GGCloner.merge(SMI->second, I->second); @@ -1939,7 +2141,7 @@ void DSGraph::removeDeadNodes(unsigned Flags) { // 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; hash_set AuxFCallsAlive; @@ -1952,7 +2154,7 @@ void DSGraph::removeDeadNodes(unsigned Flags) { Iterate = false; if (!(Flags & DSGraph::RemoveUnreachableGlobals)) for (unsigned i = 0; i != GlobalNodes.size(); ++i) - if (CanReachAliveNodes(GlobalNodes[i].second, Alive, Visited, + 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 @@ -1984,7 +2186,7 @@ void DSGraph::removeDeadNodes(unsigned Flags) { // Copy and merge global nodes and dead aux call nodes into the // GlobalsGraph, and all nodes reachable from those nodes. Update their // target pointers using the GGCloner. - // + // if (!(Flags & DSGraph::RemoveUnreachableGlobals)) GlobalsGraph->AuxFunctionCalls.push_back(DSCallSite(*CI, GGCloner)); @@ -2040,7 +2242,7 @@ void DSGraph::AssertCallSiteInGraph(const DSCallSite &CS) const { #if 0 if (CS.getNumPtrArgs() && CS.getCalleeNode() == CS.getPtrArg(0).getNode() && CS.getCalleeNode() && CS.getCalleeNode()->getGlobals().empty()) - std::cerr << "WARNING: WEIRD CALL SITE FOUND!\n"; + std::cerr << "WARNING: WEIRD CALL SITE FOUND!\n"; #endif } AssertNodeInGraph(CS.getRetVal().getNode()); @@ -2110,7 +2312,7 @@ void DSGraph::computeNodeMapping(const DSNodeHandle &NH1, } return; } - + Entry.setTo(N2, NH2.getOffset()-NH1.getOffset()); // Loop over all of the fields that N1 and N2 have in common, recursively @@ -2144,7 +2346,7 @@ void DSGraph::computeGToGGMapping(NodeMapTy &NodeMap) { E = SM.global_end(); I != E; ++I) DSGraph::computeNodeMapping(SM[*I], GG.getNodeForValue(*I), NodeMap); } - + /// computeGGToGMapping - Compute the mapping of nodes in the global graph to /// nodes in this graph. Note that any uses of this method are probably bugs, /// unless it is known that the globals graph has been merged into this graph! @@ -2158,7 +2360,7 @@ void DSGraph::computeGGToGMapping(InvNodeMapTy &InvNodeMap) { NodeMap.erase(NodeMap.begin()); } } - + /// computeCalleeCallerMapping - Given a call from a function in the current /// graph to the 'Callee' function (which lives in 'CalleeGraph'), compute the @@ -2169,7 +2371,7 @@ void DSGraph::computeCalleeCallerMapping(DSCallSite CS, const Function &Callee, DSCallSite CalleeArgs = CalleeGraph.getCallSiteForArguments(const_cast(Callee)); - + computeNodeMapping(CalleeArgs.getRetVal(), CS.getRetVal(), NodeMap); unsigned NumArgs = CS.getNumPtrArgs(); @@ -2178,18 +2380,18 @@ void DSGraph::computeCalleeCallerMapping(DSCallSite CS, const Function &Callee, for (unsigned i = 0; i != NumArgs; ++i) computeNodeMapping(CalleeArgs.getPtrArg(i), CS.getPtrArg(i), NodeMap); - + // Map the nodes that are pointed to by globals. DSScalarMap &CalleeSM = CalleeGraph.getScalarMap(); DSScalarMap &CallerSM = getScalarMap(); if (CalleeSM.global_size() >= CallerSM.global_size()) { - for (DSScalarMap::global_iterator GI = CallerSM.global_begin(), + for (DSScalarMap::global_iterator GI = CallerSM.global_begin(), E = CallerSM.global_end(); GI != E; ++GI) if (CalleeSM.global_count(*GI)) computeNodeMapping(CalleeSM[*GI], CallerSM[*GI], NodeMap); } else { - for (DSScalarMap::global_iterator GI = CalleeSM.global_begin(), + for (DSScalarMap::global_iterator GI = CalleeSM.global_begin(), E = CalleeSM.global_end(); GI != E; ++GI) if (CallerSM.global_count(*GI)) computeNodeMapping(CalleeSM[*GI], CallerSM[*GI], NodeMap);