X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FDataStructure%2FDataStructure.cpp;h=1aad8cf69ee544cda6c2154747e16c4f75aca9e6;hb=088b639e3a168686f16bb292e08b952d01a25b7d;hp=432dbb0d5c970c85d588631aeb29201f9d3fa029;hpb=5190ce83744ceadeb0167330bbf83ff99de066ee;p=oota-llvm.git diff --git a/lib/Analysis/DataStructure/DataStructure.cpp b/lib/Analysis/DataStructure/DataStructure.cpp index 432dbb0d5c9..1aad8cf69ee 100644 --- a/lib/Analysis/DataStructure/DataStructure.cpp +++ b/lib/Analysis/DataStructure/DataStructure.cpp @@ -11,10 +11,8 @@ #include "llvm/Target/TargetData.h" #include "Support/STLExtras.h" #include "Support/Statistic.h" +#include "Support/Timer.h" #include -#include - -using std::vector; namespace { Statistic<> NumFolds ("dsnode", "Number of nodes completely folded"); @@ -26,29 +24,66 @@ namespace DS { // TODO: FIXME } using namespace DS; +DSNode *DSNodeHandle::HandleForwarding() const { + assert(!N->ForwardNH.isNull() && "Can only be invoked if forwarding!"); + + // Handle node forwarding here! + DSNode *Next = N->ForwardNH.getNode(); // Cause recursive shrinkage + Offset += N->ForwardNH.getOffset(); + + if (--N->NumReferrers == 0) { + // Removing the last referrer to the node, sever the forwarding link + N->stopForwarding(); + } + + N = Next; + N->NumReferrers++; + if (N->Size <= Offset) { + assert(N->Size <= 1 && "Forwarded to shrunk but not collapsed node?"); + Offset = 0; + } + return N; +} + //===----------------------------------------------------------------------===// // DSNode Implementation //===----------------------------------------------------------------------===// -DSNode::DSNode(enum NodeTy NT, const Type *T) - : Ty(Type::VoidTy), Size(0), NodeType(NT) { +DSNode::DSNode(unsigned NT, const Type *T, DSGraph *G) + : NumReferrers(0), Size(0), ParentGraph(G), Ty(Type::VoidTy), NodeType(NT) { // Add the type entry if it is specified... if (T) mergeTypeInfo(T, 0); + G->getNodes().push_back(this); } // DSNode copy constructor... do not copy over the referrers list! -DSNode::DSNode(const DSNode &N) - : Links(N.Links), Globals(N.Globals), Ty(N.Ty), Size(N.Size), - NodeType(N.NodeType) { +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) { + G->getNodes().push_back(this); +} + +void DSNode::assertOK() const { + assert((Ty != Type::VoidTy || + Ty == Type::VoidTy && (Size == 0 || + (NodeType & DSNode::Array))) && + "Node not OK!"); } -void DSNode::removeReferrer(DSNodeHandle *H) { - // Search backwards, because we depopulate the list from the back for - // efficiency (because it's a vector). - vector::reverse_iterator I = - std::find(Referrers.rbegin(), Referrers.rend(), H); - assert(I != Referrers.rend() && "Referrer not pointing to node!"); - Referrers.erase(I.base()-1); +/// forwardNode - Mark this node as being obsolete, and all references to it +/// should be forwarded to the specified node and offset. +/// +void DSNode::forwardNode(DSNode *To, unsigned Offset) { + assert(this != To && "Cannot forward a node to itself!"); + assert(ForwardNH.isNull() && "Already forwarding from this node!"); + if (To->Size <= 1) Offset = 0; + assert((Offset < To->Size || (Offset == To->Size && Offset == 0)) && + "Forwarded offset is wrong!"); + ForwardNH.setNode(To); + ForwardNH.setOffset(Offset); + NodeType = DEAD; + Size = 0; + Ty = Type::VoidTy; } // addGlobal - Add an entry for a global value to the Globals list. This also @@ -56,7 +91,7 @@ void DSNode::removeReferrer(DSNodeHandle *H) { // void DSNode::addGlobal(GlobalValue *GV) { // Keep the list sorted. - vector::iterator I = + std::vector::iterator I = std::lower_bound(Globals.begin(), Globals.end(), GV); if (I == Globals.end() || *I != GV) { @@ -72,24 +107,32 @@ void DSNode::addGlobal(GlobalValue *GV) { /// single byte with a single TypeEntry of "void". /// void DSNode::foldNodeCompletely() { - if (isNodeCompletelyFolded()) return; + assert(!hasNoReferrers() && + "Why would we collapse a node with no referrers?"); + if (isNodeCompletelyFolded()) return; // If this node is already folded... ++NumFolds; - // We are no longer typed at all... - Ty = DSTypeRec(Type::VoidTy, true); - Size = 1; - - // Loop over all of our referrers, making them point to our zero bytes of - // space. - for (vector::iterator I = Referrers.begin(), E=Referrers.end(); - I != E; ++I) - (*I)->setOffset(0); + // Create the node we are going to forward to... + DSNode *DestNode = new DSNode(NodeType|DSNode::Array, 0, ParentGraph); + DestNode->Ty = Type::VoidTy; + DestNode->Size = 1; + DestNode->Globals.swap(Globals); - // If we have links, merge all of our outgoing links together... - for (unsigned i = 1, e = Links.size(); i < e; ++i) - Links[0].mergeWith(Links[i]); - Links.resize(1); + // Start forwarding to the destination node... + forwardNode(DestNode, 0); + + if (Links.size()) { + DestNode->Links.push_back(Links[0]); + DSNodeHandle NH(DestNode); + + // 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]); + Links.clear(); + } else { + DestNode->Links.resize(1); + } } /// isNodeCompletelyFolded - Return true if this node has been completely @@ -97,7 +140,7 @@ void DSNode::foldNodeCompletely() { /// all of the field sensitivity that may be present in the node. /// bool DSNode::isNodeCompletelyFolded() const { - return getSize() == 1 && Ty.Ty == Type::VoidTy && Ty.isArray; + return getSize() == 1 && Ty == Type::VoidTy && isArray(); } @@ -109,7 +152,8 @@ bool DSNode::isNodeCompletelyFolded() const { /// /// This method returns true if the node is completely folded, otherwise false. /// -bool DSNode::mergeTypeInfo(const Type *NewTy, unsigned Offset) { +bool DSNode::mergeTypeInfo(const Type *NewTy, unsigned Offset, + bool FoldIfIncompatible) { // Check to make sure the Size member is up-to-date. Size can be one of the // following: // Size = 0, Ty = Void: Nothing is known about this node. @@ -117,15 +161,15 @@ bool DSNode::mergeTypeInfo(const Type *NewTy, unsigned Offset) { // Size = 1, Ty = Void, Array = 1: The node is collapsed // Otherwise, sizeof(Ty) = Size // - assert(((Size == 0 && Ty.Ty == Type::VoidTy && !Ty.isArray) || - (Size == 0 && !Ty.Ty->isSized() && !Ty.isArray) || - (Size == 1 && Ty.Ty == Type::VoidTy && Ty.isArray) || - (Size == 0 && !Ty.Ty->isSized() && !Ty.isArray) || - (TD.getTypeSize(Ty.Ty) == Size)) && + assert(((Size == 0 && Ty == Type::VoidTy && !isArray()) || + (Size == 0 && !Ty->isSized() && !isArray()) || + (Size == 1 && Ty == Type::VoidTy && isArray()) || + (Size == 0 && !Ty->isSized() && !isArray()) || + (TD.getTypeSize(Ty) == Size)) && "Size member of DSNode doesn't match the type structure!"); assert(NewTy != Type::VoidTy && "Cannot merge void type into DSNode!"); - if (Offset == 0 && NewTy == Ty.Ty) + if (Offset == 0 && NewTy == Ty) return false; // This should be a common case, handle it efficiently // Return true immediately if the node is completely folded. @@ -150,13 +194,14 @@ bool DSNode::mergeTypeInfo(const Type *NewTy, unsigned Offset) { // we can't, we fold the node completely, if we can, we potentially update our // internal state. // - if (Ty.Ty == Type::VoidTy) { + if (Ty == Type::VoidTy) { // If this is the first type that this node has seen, just accept it without // question.... assert(Offset == 0 && "Cannot have an offset into a void node!"); - assert(!Ty.isArray && "This shouldn't happen!"); - Ty.Ty = NewTy; - Ty.isArray = WillBeArray; + assert(!isArray() && "This shouldn't happen!"); + Ty = NewTy; + NodeType &= ~Array; + if (WillBeArray) NodeType |= Array; Size = NewTySize; // Calculate the number of outgoing links from this node. @@ -168,15 +213,15 @@ bool DSNode::mergeTypeInfo(const Type *NewTy, unsigned Offset) { if (Offset+NewTySize > Size) { // It is illegal to grow this node if we have treated it as an array of // objects... - if (Ty.isArray) { - foldNodeCompletely(); + if (isArray()) { + if (FoldIfIncompatible) foldNodeCompletely(); return true; } if (Offset) { // We could handle this case, but we don't for now... DEBUG(std::cerr << "UNIMP: Trying to merge a growth type into " << "offset != 0: Collapsing!\n"); - foldNodeCompletely(); + if (FoldIfIncompatible) foldNodeCompletely(); return true; } @@ -186,9 +231,10 @@ bool DSNode::mergeTypeInfo(const Type *NewTy, unsigned Offset) { // hit the other code path here. If the other code path decides it's not // ok, it will collapse the node as appropriate. // - const Type *OldTy = Ty.Ty; - Ty.Ty = NewTy; - Ty.isArray = WillBeArray; + const Type *OldTy = Ty; + Ty = NewTy; + NodeType &= ~Array; + if (WillBeArray) NodeType |= Array; Size = NewTySize; // Must grow links to be the appropriate size... @@ -202,11 +248,11 @@ bool DSNode::mergeTypeInfo(const Type *NewTy, unsigned Offset) { assert(Offset <= Size && "Cannot merge something into a part of our type that doesn't exist!"); - // Find the section of Ty.Ty that NewTy overlaps with... first we find the + // Find the section of Ty that NewTy overlaps with... first we find the // type that starts at offset Offset. // unsigned O = 0; - const Type *SubType = Ty.Ty; + const Type *SubType = Ty; while (O < Offset) { assert(Offset-O < TD.getTypeSize(SubType) && "Offset out of range!"); @@ -232,7 +278,8 @@ bool DSNode::mergeTypeInfo(const Type *NewTy, unsigned Offset) { break; } default: - assert(0 && "Unknown type!"); + if (FoldIfIncompatible) foldNodeCompletely(); + return true; } } @@ -247,17 +294,27 @@ bool DSNode::mergeTypeInfo(const Type *NewTy, unsigned Offset) { // composite type... // unsigned SubTypeSize = SubType->isSized() ? TD.getTypeSize(SubType) : 0; + unsigned PadSize = SubTypeSize; // Size, including pad memory which is ignored while (SubType != NewTy) { const Type *NextSubType = 0; unsigned NextSubTypeSize = 0; + unsigned NextPadSize = 0; switch (SubType->getPrimitiveID()) { - case Type::StructTyID: - NextSubType = cast(SubType)->getElementTypes()[0]; - NextSubTypeSize = TD.getTypeSize(SubType); + case Type::StructTyID: { + const StructType *STy = cast(SubType); + const StructLayout &SL = *TD.getStructLayout(STy); + if (SL.MemberOffsets.size() > 1) + NextPadSize = SL.MemberOffsets[1]; + else + NextPadSize = SubTypeSize; + NextSubType = STy->getElementTypes()[0]; + NextSubTypeSize = TD.getTypeSize(NextSubType); break; + } case Type::ArrayTyID: NextSubType = cast(SubType)->getElementType(); - NextSubTypeSize = TD.getTypeSize(SubType); + NextSubTypeSize = TD.getTypeSize(NextSubType); + NextPadSize = NextSubTypeSize; break; default: ; // fall out @@ -266,10 +323,11 @@ bool DSNode::mergeTypeInfo(const Type *NewTy, unsigned Offset) { if (NextSubType == 0) break; // In the default case, break out of the loop - if (NextSubTypeSize < NewTySize) + if (NextPadSize < NewTySize) break; // Don't allow shrinking to a smaller type than NewTySize SubType = NextSubType; SubTypeSize = NextSubTypeSize; + PadSize = NextPadSize; } // If we found the type exactly, return it... @@ -288,15 +346,18 @@ bool DSNode::mergeTypeInfo(const Type *NewTy, unsigned Offset) { if (SubType->isInteger() && isa(NewTy) || NewTy->isInteger() && isa(SubType)) return false; - + } else if (NewTySize > SubTypeSize && NewTySize <= PadSize) { + // We are accessing the field, plus some structure padding. Ignore the + // structure padding. + return false; } - DEBUG(std::cerr << "MergeTypeInfo Folding OrigTy: " << Ty.Ty + DEBUG(std::cerr << "MergeTypeInfo Folding OrigTy: " << Ty << "\n due to:" << NewTy << " @ " << Offset << "!\n" << "SubType: " << SubType << "\n\n"); - foldNodeCompletely(); + if (FoldIfIncompatible) foldNodeCompletely(); return true; } @@ -322,8 +383,8 @@ void DSNode::addEdgeTo(unsigned Offset, const DSNodeHandle &NH) { // duplicates are not allowed and both are sorted. This assumes that 'T's are // efficiently copyable and have sane comparison semantics. // -template -void MergeSortedVectors(vector &Dest, const vector &Src) { +static void MergeSortedVectors(std::vector &Dest, + const std::vector &Src) { // By far, the most common cases will be the simple ones. In these cases, // avoid having to allocate a temporary vector... // @@ -332,22 +393,22 @@ void MergeSortedVectors(vector &Dest, const vector &Src) { } else if (Dest.empty()) { // Just copy the result in... Dest = Src; } else if (Src.size() == 1) { // Insert a single element... - const T &V = Src[0]; - typename vector::iterator I = + const GlobalValue *V = Src[0]; + std::vector::iterator I = std::lower_bound(Dest.begin(), Dest.end(), V); if (I == Dest.end() || *I != Src[0]) // If not already contained... Dest.insert(I, Src[0]); } else if (Dest.size() == 1) { - T Tmp = Dest[0]; // Save value in temporary... + GlobalValue *Tmp = Dest[0]; // Save value in temporary... Dest = Src; // Copy over list... - typename vector::iterator I = + std::vector::iterator I = std::lower_bound(Dest.begin(), Dest.end(), Tmp); if (I == Dest.end() || *I != Tmp) // If not already contained... Dest.insert(I, Tmp); } else { // Make a copy to the side of Dest... - vector Old(Dest); + std::vector Old(Dest); // Make space for all of the type entries now... Dest.resize(Dest.size()+Src.size()); @@ -362,6 +423,95 @@ void MergeSortedVectors(vector &Dest, const vector &Src) { } +// MergeNodes() - Helper function for DSNode::mergeWith(). +// 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 +// automatically updated during merging, so will always provide access +// to the correct node after a merge. +// +void DSNode::MergeNodes(DSNodeHandle& CurNodeH, DSNodeHandle& NH) { + assert(CurNodeH.getOffset() >= NH.getOffset() && + "This should have been enforced in the caller."); + + // Now we know that Offset >= NH.Offset, so convert it so our "Offset" (with + // respect to NH.Offset) is now zero. NOffset is the distance from the base + // of our object that N starts from. + // + unsigned NOffset = CurNodeH.getOffset()-NH.getOffset(); + unsigned NSize = NH.getNode()->getSize(); + + // 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()->NodeType & DSNode::DEAD) == 0); + + // If we are merging a node with a completely folded node, then both nodes are + // now completely folded. + // + if (CurNodeH.getNode()->isNodeCompletelyFolded()) { + if (!NH.getNode()->isNodeCompletelyFolded()) { + NH.getNode()->foldNodeCompletely(); + assert(NH.getNode() && NH.getOffset() == 0 && + "folding did not make offset 0?"); + NOffset = NH.getOffset(); + NSize = NH.getNode()->getSize(); + assert(NOffset == 0 && NSize == 1); + } + } else if (NH.getNode()->isNodeCompletelyFolded()) { + CurNodeH.getNode()->foldNodeCompletely(); + assert(CurNodeH.getNode() && CurNodeH.getOffset() == 0 && + "folding did not make offset 0?"); + NOffset = NH.getOffset(); + NSize = NH.getNode()->getSize(); + assert(NOffset == 0 && NSize == 1); + } + + DSNode *N = NH.getNode(); + if (CurNodeH.getNode() == N || N == 0) return; + assert((CurNodeH.getNode()->NodeType & DSNode::DEAD) == 0); + + // Start forwarding to the new node! + CurNodeH.getNode()->NodeType |= N->NodeType; + N->forwardNode(CurNodeH.getNode(), NOffset); + assert((CurNodeH.getNode()->NodeType & DSNode::DEAD) == 0); + + // Make all of the outgoing links of N now be outgoing links of CurNodeH. + // + for (unsigned i = 0; i < N->getNumLinks(); ++i) { + DSNodeHandle &Link = N->getLink(i << DS::PointerShift); + if (Link.getNode()) { + // Compute the offset into the current node at which to + // merge this link. In the common case, this is a linear + // relation to the offset in the original node (with + // wrapping), but if the current node gets collapsed due to + // recursive merging, we must make sure to merge in all remaining + // links at offset zero. + unsigned MergeOffset = 0; + DSNode *CN = CurNodeH.getNode(); + if (CN->Size != 1) + MergeOffset = ((i << DS::PointerShift)+NOffset) % CN->getSize(); + CN->addEdgeTo(MergeOffset, Link); + } + } + + // Now that there are no outgoing edges, all of the Links are dead. + N->Links.clear(); + + // Merge the globals list... + if (!N->Globals.empty()) { + MergeSortedVectors(CurNodeH.getNode()->Globals, N->Globals); + + // Delete the globals from the old node... + std::vector().swap(N->Globals); + } +} + + // mergeWith - Merge this node and the specified node, moving all links to and // from the argument node into the current node, deleting the node argument. // Offset indicates what offset the specified node is to be merged into the @@ -399,92 +549,11 @@ void DSNode::mergeWith(const DSNodeHandle &NH, unsigned Offset) { return; } - // Now we know that Offset >= NH.Offset, so convert it so our "Offset" (with - // respect to NH.Offset) is now zero. NOffset is the distance from the base - // of our object that N starts from. - // - unsigned NOffset = Offset-NH.getOffset(); - unsigned NSize = N->getSize(); - - // Merge the type entries of the two nodes together... - if (N->Ty.Ty != Type::VoidTy) { - mergeTypeInfo(N->Ty.Ty, NOffset); - - // mergeTypeInfo can cause collapsing, which can cause this node to become - // dead. - if (hasNoReferrers()) return; - } - assert((NodeType & DSNode::DEAD) == 0); - - // If we are merging a node with a completely folded node, then both nodes are - // now completely folded. - // - if (isNodeCompletelyFolded()) { - if (!N->isNodeCompletelyFolded()) { - N->foldNodeCompletely(); - if (hasNoReferrers()) return; - NSize = N->getSize(); - } - } else if (N->isNodeCompletelyFolded()) { - foldNodeCompletely(); - if (hasNoReferrers()) return; - Offset = 0; - NOffset = NH.getOffset(); - NSize = N->getSize(); - } - N = NH.getNode(); - if (this == N || N == 0) return; - assert((NodeType & DSNode::DEAD) == 0); - -#if 0 - std::cerr << "\n\nMerging:\n"; - N->print(std::cerr, 0); - std::cerr << " and:\n"; - print(std::cerr, 0); -#endif - - // Remove all edges pointing at N, causing them to point to 'this' instead. - // Make sure to adjust their offset, not just the node pointer. - // - while (!N->Referrers.empty()) { - DSNodeHandle &Ref = *N->Referrers.back(); - Ref = DSNodeHandle(this, NOffset+Ref.getOffset()); - } - assert((NodeType & DSNode::DEAD) == 0); - - // Make all of the outgoing links of N now be outgoing links of this. This - // can cause recursive merging! - // - for (unsigned i = 0; i < NSize; i += DS::PointerSize) { - DSNodeHandle &Link = N->getLink(i); - if (Link.getNode()) { - addEdgeTo((i+NOffset) % getSize(), Link); - - // It's possible that after adding the new edge that some recursive - // merging just occured, causing THIS node to get merged into oblivion. - // If that happens, we must not try to merge any more edges into it! - // - if (Size == 0) return; - } - } - - // Now that there are no outgoing edges, all of the Links are dead. - N->Links.clear(); - N->Size = 0; - N->Ty.Ty = Type::VoidTy; - N->Ty.isArray = false; - - // Merge the node types - NodeType |= N->NodeType; - N->NodeType = DEAD; // N is now a dead node. - - // Merge the globals list... - if (!N->Globals.empty()) { - MergeSortedVectors(Globals, N->Globals); - - // Delete the globals from the old node... - N->Globals.clear(); - } + // Ok, now we can merge the two nodes. Use a static helper that works with + // two node handles, since "this" may get merged away at intermediate steps. + DSNodeHandle CurNodeH(this, Offset); + DSNodeHandle NHCopy(NH); + DSNode::MergeNodes(CurNodeH, NHCopy); } //===----------------------------------------------------------------------===// @@ -503,12 +572,12 @@ Function &DSCallSite::getCaller() const { DSGraph::DSGraph(const DSGraph &G) : Func(G.Func), GlobalsGraph(0) { PrintAuxCalls = false; - std::map NodeMap; + hash_map NodeMap; RetNode = cloneInto(G, ScalarMap, NodeMap); } DSGraph::DSGraph(const DSGraph &G, - std::map &NodeMap) + hash_map &NodeMap) : Func(G.Func), GlobalsGraph(0) { PrintAuxCalls = false; RetNode = cloneInto(G, ScalarMap, NodeMap); @@ -535,7 +604,7 @@ void DSGraph::dump() const { print(std::cerr); } /// remapLinks - Change all of the Links in the current node according to the /// specified mapping. /// -void DSNode::remapLinks(std::map &OldNodeMap) { +void DSNode::remapLinks(hash_map &OldNodeMap) { for (unsigned i = 0, e = Links.size(); i != e; ++i) { DSNodeHandle &H = OldNodeMap[Links[i].getNode()]; Links[i].setNode(H.getNode()); @@ -551,8 +620,8 @@ void DSNode::remapLinks(std::map &OldNodeMap) { // calling function's graph. // DSNodeHandle DSGraph::cloneInto(const DSGraph &G, - std::map &OldValMap, - std::map &OldNodeMap, + hash_map &OldValMap, + hash_map &OldNodeMap, unsigned CloneFlags) { assert(OldNodeMap.empty() && "Returned OldNodeMap should be empty!"); assert(&G != this && "Cannot clone graph into itself!"); @@ -561,38 +630,40 @@ DSNodeHandle DSGraph::cloneInto(const DSGraph &G, // Duplicate all of the nodes, populating the node map... Nodes.reserve(FN+G.Nodes.size()); + + // Remove alloca or mod/ref bits as specified... + unsigned clearBits = (CloneFlags & StripAllocaBit ? DSNode::AllocaNode : 0) + | (CloneFlags & StripModRefBits ? (DSNode::Modified | DSNode::Read) : 0); + clearBits |= DSNode::DEAD; // Clear dead flag... for (unsigned i = 0, e = G.Nodes.size(); i != e; ++i) { DSNode *Old = G.Nodes[i]; - DSNode *New = new DSNode(*Old); - New->NodeType &= ~DSNode::DEAD; // Clear dead flag... - Nodes.push_back(New); + DSNode *New = new DSNode(*Old, this); + New->NodeType &= ~clearBits; OldNodeMap[Old] = New; } +#ifndef NDEBUG + Timer::addPeakMemoryMeasurement(); +#endif + // Rewrite the links in the new nodes to point into the current graph now. for (unsigned i = FN, e = Nodes.size(); i != e; ++i) Nodes[i]->remapLinks(OldNodeMap); - // Remove alloca markers as specified - if (CloneFlags & StripAllocaBit) - for (unsigned i = FN, e = Nodes.size(); i != e; ++i) - Nodes[i]->NodeType &= ~DSNode::AllocaNode; - - // Copy the value map... and merge all of the global nodes... - for (std::map::const_iterator I = G.ScalarMap.begin(), + // Copy the scalar map... merging all of the global nodes... + for (hash_map::const_iterator I = G.ScalarMap.begin(), E = G.ScalarMap.end(); I != E; ++I) { DSNodeHandle &H = OldValMap[I->first]; DSNodeHandle &MappedNode = OldNodeMap[I->second.getNode()]; - H.setNode(MappedNode.getNode()); H.setOffset(I->second.getOffset()+MappedNode.getOffset()); + H.setNode(MappedNode.getNode()); if (isa(I->first)) { // Is this a global? - std::map::iterator GVI = ScalarMap.find(I->first); - if (GVI != ScalarMap.end()) { // Is the global value in this fn already? + hash_map::iterator GVI = ScalarMap.find(I->first); + if (GVI != ScalarMap.end()) // Is the global value in this fn already? GVI->second.mergeWith(H); - } else { + else ScalarMap[I->first] = H; // Add global pointer to this graph - } } } @@ -625,16 +696,16 @@ DSNodeHandle DSGraph::cloneInto(const DSGraph &G, /// void DSGraph::mergeInGraph(DSCallSite &CS, const DSGraph &Graph, unsigned CloneFlags) { - std::map OldValMap; + hash_map OldValMap; DSNodeHandle RetVal; - std::map *ScalarMap = &OldValMap; + hash_map *ScalarMap = &OldValMap; // If this is not a recursive call, clone the graph into this graph... if (&Graph != this) { // Clone the callee's graph into the current graph, keeping // track of where scalars in the old graph _used_ to point, // and of the new nodes matching nodes of the old graph. - std::map OldNodeMap; + hash_map OldNodeMap; // The clone call may invalidate any of the vectors in the data // structure graph. Strip locals and don't copy the list of callers @@ -651,51 +722,26 @@ void DSGraph::mergeInGraph(DSCallSite &CS, const DSGraph &Graph, // Resolve all of the function arguments... Function &F = Graph.getFunction(); Function::aiterator AI = F.abegin(); + for (unsigned i = 0, e = CS.getNumPtrArgs(); i != e; ++i, ++AI) { // Advance the argument iterator to the first pointer argument... - while (!isPointerType(AI->getType())) { + while (AI != F.aend() && !isPointerType(AI->getType())) { ++AI; #ifndef NDEBUG if (AI == F.aend()) std::cerr << "Bad call to Function: " << F.getName() << "\n"; #endif - assert(AI != F.aend() && "# Args provided is not # Args required!"); } + if (AI == F.aend()) break; // Add the link from the argument scalar to the provided value + assert(ScalarMap->count(AI) && "Argument not in scalar map?"); DSNodeHandle &NH = (*ScalarMap)[AI]; assert(NH.getNode() && "Pointer argument without scalarmap entry?"); NH.mergeWith(CS.getPtrArg(i)); } } -#if 0 -// cloneGlobalInto - Clone the given global node and all its target links -// (and all their llinks, recursively). -// -DSNode *DSGraph::cloneGlobalInto(const DSNode *GNode) { - if (GNode == 0 || GNode->getGlobals().size() == 0) return 0; - - // If a clone has already been created for GNode, return it. - DSNodeHandle& ValMapEntry = ScalarMap[GNode->getGlobals()[0]]; - if (ValMapEntry != 0) - return ValMapEntry; - - // Clone the node and update the ValMap. - DSNode* NewNode = new DSNode(*GNode); - ValMapEntry = NewNode; // j=0 case of loop below! - Nodes.push_back(NewNode); - for (unsigned j = 1, N = NewNode->getGlobals().size(); j < N; ++j) - ScalarMap[NewNode->getGlobals()[j]] = NewNode; - - // Rewrite the links in the new node to point into the current graph. - for (unsigned j = 0, e = GNode->getNumLinks(); j != e; ++j) - NewNode->setLink(j, cloneGlobalInto(GNode->getLink(j))); - - return NewNode; -} -#endif - // markIncompleteNodes - Mark the specified node as having contents that are not // known with the current analysis we have performed. Because a node makes all @@ -735,9 +781,9 @@ static void markIncomplete(DSCallSite &Call) { // scope of current analysis may have modified it), the 'Incomplete' flag is // added to the NodeType. // -void DSGraph::markIncompleteNodes(bool markFormalArgs) { +void DSGraph::markIncompleteNodes(unsigned Flags) { // Mark any incoming arguments as incomplete... - if (markFormalArgs && Func) + if ((Flags & DSGraph::MarkFormalArgs) && Func && Func->getName() != "main") for (Function::aiterator I = Func->abegin(), E = Func->aend(); I != E; ++I) if (isPointerType(I->getType()) && ScalarMap.find(I) != ScalarMap.end()) markIncompleteNode(ScalarMap[I].getNode()); @@ -751,42 +797,18 @@ void DSGraph::markIncompleteNodes(bool markFormalArgs) { markIncomplete(AuxFunctionCalls[i]); - // Mark all of the nodes pointed to by global nodes as incomplete... - for (unsigned i = 0, e = Nodes.size(); i != e; ++i) - if (Nodes[i]->NodeType & DSNode::GlobalNode) { - DSNode *N = Nodes[i]; - for (unsigned i = 0, e = N->getSize(); i < e; i += DS::PointerSize) - if (DSNode *DSN = N->getLink(i).getNode()) - markIncompleteNode(DSN); - } -} - -// removeRefsToGlobal - Helper function that removes globals from the -// ScalarMap so that the referrer count will go down to zero. -static void removeRefsToGlobal(DSNode* N, - std::map &ScalarMap) { - while (!N->getGlobals().empty()) { - GlobalValue *GV = N->getGlobals().back(); - N->getGlobals().pop_back(); - ScalarMap.erase(GV); - } -} - - -// isNodeDead - This method checks to see if a node is dead, and if it isn't, it -// checks to see if there are simple transformations that it can do to make it -// dead. -// -bool DSGraph::isNodeDead(DSNode *N) { - // Is it a trivially dead shadow node? - return N->getReferrers().empty() && (N->NodeType & ~DSNode::DEAD) == 0; + // Mark all global nodes as incomplete... + if ((Flags & DSGraph::IgnoreGlobals) == 0) + for (unsigned i = 0, e = Nodes.size(); i != e; ++i) + if (Nodes[i]->NodeType & DSNode::GlobalNode && Nodes[i]->getNumLinks()) + markIncompleteNode(Nodes[i]); } static inline void killIfUselessEdge(DSNodeHandle &Edge) { if (DSNode *N = Edge.getNode()) // Is there an edge? - if (N->getReferrers().size() == 1) // Does it point to a lonely node? + if (N->getNumReferrers() == 1) // Does it point to a lonely node? if ((N->NodeType & ~DSNode::Incomplete) == 0 && // No interesting info? - N->getType().Ty == Type::VoidTy && !N->isNodeCompletelyFolded()) + N->getType() == Type::VoidTy && !N->isNodeCompletelyFolded()) Edge.setNode(0); // Kill the edge! } @@ -798,14 +820,15 @@ static inline bool nodeContainsExternalFunction(const DSNode *N) { return false; } -static void removeIdenticalCalls(vector &Calls, +static void removeIdenticalCalls(std::vector &Calls, const std::string &where) { // Remove trivially identical function calls unsigned NumFns = Calls.size(); std::sort(Calls.begin(), Calls.end()); // Sort by callee as primary key! // Scan the call list cleaning it up as necessary... - DSNode *LastCalleeNode = 0; + DSNode *LastCalleeNode = 0; + Function *LastCalleeFunc = 0; unsigned NumDuplicateCalls = 0; bool LastCalleeContainsExternalFunction = false; for (unsigned i = 0; i != Calls.size(); ++i) { @@ -813,8 +836,9 @@ static void removeIdenticalCalls(vector &Calls, // If the Callee is a useless edge, this must be an unreachable call site, // eliminate it. - killIfUselessEdge(CS.getCallee()); - if (CS.getCallee().getNode() == 0) { + if (CS.isIndirectCall() && CS.getCalleeNode()->getNumReferrers() == 1 && + CS.getCalleeNode()->NodeType == 0) { // No useful info? + std::cerr << "WARNING: Useless call site found??\n"; CS.swap(Calls.back()); Calls.pop_back(); --i; @@ -832,11 +856,15 @@ static void removeIdenticalCalls(vector &Calls, // never be resolved. Merge the arguments of the call node because no // information will be lost. // - if (CS.getCallee().getNode() == LastCalleeNode) { + if ((CS.isDirectCall() && CS.getCalleeFunc() == LastCalleeFunc) || + (CS.isIndirectCall() && CS.getCalleeNode() == LastCalleeNode)) { ++NumDuplicateCalls; if (NumDuplicateCalls == 1) { - LastCalleeContainsExternalFunction = - nodeContainsExternalFunction(LastCalleeNode); + if (LastCalleeNode) + LastCalleeContainsExternalFunction = + nodeContainsExternalFunction(LastCalleeNode); + else + LastCalleeContainsExternalFunction = LastCalleeFunc->isExternal(); } if (LastCalleeContainsExternalFunction || @@ -853,7 +881,13 @@ static void removeIdenticalCalls(vector &Calls, OCS = CS; } } else { - LastCalleeNode = CS.getCallee().getNode(); + if (CS.isDirectCall()) { + LastCalleeFunc = CS.getCalleeFunc(); + LastCalleeNode = 0; + } else { + LastCalleeNode = CS.getCalleeNode(); + LastCalleeFunc = 0; + } NumDuplicateCalls = 0; } } @@ -880,283 +914,288 @@ void DSGraph::removeTriviallyDeadNodes() { removeIdenticalCalls(FunctionCalls, Func ? Func->getName() : ""); removeIdenticalCalls(AuxFunctionCalls, Func ? Func->getName() : ""); - for (unsigned i = 0; i != Nodes.size(); ++i) - if (isNodeDead(Nodes[i])) { // This node is dead! - delete Nodes[i]; // Free memory... - Nodes.erase(Nodes.begin()+i--); // Remove from node list... + for (unsigned i = 0; i != Nodes.size(); ++i) { + DSNode *Node = Nodes[i]; + if (!(Node->NodeType & ~(DSNode::Composition | DSNode::Array | + DSNode::DEAD))) { + // 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 + // context), and it has no incoming edges. If it is a global node it may + // have all of these properties and still have incoming edges, due to the + // scalar map, so we check those now. + // + if (Node->getNumReferrers() == Node->getGlobals().size()) { + std::vector &Globals = Node->getGlobals(); + + // 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!"); + } + + // Make sure numreferrers still agrees, if so, the node is truely dead. + if (Node->getNumReferrers() == Globals.size()) { + for (unsigned j = 0, e = Globals.size(); j != e; ++j) + ScalarMap.erase(Globals[j]); + + Globals.clear(); + assert(Node->hasNoReferrers() && "Shouldn't have refs now!"); + + Node->NodeType = DSNode::DEAD; + } + } } + + if ((Node->NodeType & ~DSNode::DEAD) == 0 && Node->hasNoReferrers()) { + // This node is dead! + delete Node; // Free memory... + Nodes[i--] = Nodes.back(); + Nodes.pop_back(); // Remove from node list... + } + } } -// markAlive - Simple graph walker that recursively traverses the graph, marking -// stuff to be alive. -// -static void markAlive(DSNode *N, std::set &Alive) { - if (N == 0) return; - std::set::iterator I = Alive.lower_bound(N); - if (I != Alive.end() && *I == N) return; // Already marked alive - Alive.insert(I, N); // Is alive now +/// markReachableNodes - This method recursively traverses the specified +/// DSNodes, marking any nodes which are reachable. All reachable nodes it adds +/// to the set, which allows it to only traverse visited nodes once. +/// +void DSNode::markReachableNodes(hash_set &ReachableNodes) { + if (this == 0) return; + assert(getForwardNode() == 0 && "Cannot mark a forwarded node!"); + if (ReachableNodes.count(this)) return; // Already marked reachable + ReachableNodes.insert(this); // Is reachable now + + for (unsigned i = 0, e = getSize(); i < e; i += DS::PointerSize) + getLink(i).getNode()->markReachableNodes(ReachableNodes); +} - for (unsigned i = 0, e = N->getSize(); i < e; i += DS::PointerSize) - markAlive(N->getLink(i).getNode(), Alive); +void DSCallSite::markReachableNodes(hash_set &Nodes) { + getRetVal().getNode()->markReachableNodes(Nodes); + if (isIndirectCall()) getCalleeNode()->markReachableNodes(Nodes); + + for (unsigned i = 0, e = getNumPtrArgs(); i != e; ++i) + getPtrArg(i).getNode()->markReachableNodes(Nodes); } -// markAliveIfCanReachAlive - Simple graph walker that recursively traverses the -// graph looking for a node that is marked alive. If the node is marked alive, -// the recursive unwind marks node alive that can point to the alive node. This -// is basically just a post-order traversal. -// -// This function returns true if the specified node is alive. +// CanReachAliveNodes - Simple graph walker that recursively traverses the graph +// looking for a node that is marked alive. If an alive node is found, return +// true, otherwise return false. If an alive node is reachable, this node is +// marked as alive... // -static bool markAliveIfCanReachAlive(DSNode *N, std::set &Alive, - std::set &Visited) { +static bool CanReachAliveNodes(DSNode *N, hash_set &Alive, + hash_set &Visited) { if (N == 0) return false; + assert(N->getForwardNode() == 0 && "Cannot mark a forwarded node!"); // If we know that this node is alive, return so! if (Alive.count(N)) return true; // Otherwise, we don't think the node is alive yet, check for infinite // recursion. - std::set::iterator VI = Visited.lower_bound(N); - if (VI != Visited.end() && *VI == N) return false; // Found a cycle - // No recursion, insert into Visited... - Visited.insert(VI, N); - - if (N->NodeType & DSNode::GlobalNode) - return false; // Global nodes will be marked on their own - - bool ChildrenAreAlive = false; + if (Visited.count(N)) return false; // Found a cycle + Visited.insert(N); // No recursion, insert into Visited... for (unsigned i = 0, e = N->getSize(); i < e; i += DS::PointerSize) - ChildrenAreAlive |= markAliveIfCanReachAlive(N->getLink(i).getNode(), - Alive, Visited); - if (ChildrenAreAlive) - markAlive(N, Alive); - return ChildrenAreAlive; + if (CanReachAliveNodes(N->getLink(i).getNode(), Alive, Visited)) { + N->markReachableNodes(Alive); + return true; + } + return false; } -static bool CallSiteUsesAliveArgs(DSCallSite &CS, std::set &Alive, - std::set &Visited) { - if (markAliveIfCanReachAlive(CS.getRetVal().getNode(), Alive, Visited) || - markAliveIfCanReachAlive(CS.getCallee().getNode(), Alive, Visited)) +// CallSiteUsesAliveArgs - Return true if the specified call site can reach any +// alive nodes. +// +static bool CallSiteUsesAliveArgs(DSCallSite &CS, hash_set &Alive, + hash_set &Visited) { + if (CanReachAliveNodes(CS.getRetVal().getNode(), Alive, Visited)) return true; - for (unsigned j = 0, e = CS.getNumPtrArgs(); j != e; ++j) - if (markAliveIfCanReachAlive(CS.getPtrArg(j).getNode(), Alive, Visited)) + if (CS.isIndirectCall() && + CanReachAliveNodes(CS.getCalleeNode(), Alive, Visited)) + return true; + for (unsigned i = 0, e = CS.getNumPtrArgs(); i != e; ++i) + if (CanReachAliveNodes(CS.getPtrArg(i).getNode(), Alive, Visited)) return true; return false; } -static void markAlive(DSCallSite &CS, std::set &Alive) { - markAlive(CS.getRetVal().getNode(), Alive); - markAlive(CS.getCallee().getNode(), Alive); - - for (unsigned j = 0, e = CS.getNumPtrArgs(); j != e; ++j) - markAlive(CS.getPtrArg(j).getNode(), Alive); -} - // removeDeadNodes - Use a more powerful reachability analysis to eliminate // subgraphs that are unreachable. This often occurs because the data // structure doesn't "escape" into it's caller, and thus should be eliminated // from the caller's graph entirely. This is only appropriate to use when // inlining graphs. // -void DSGraph::removeDeadNodes() { - // Reduce the amount of work we have to do... +void DSGraph::removeDeadNodes(unsigned Flags) { + // Reduce the amount of work we have to do... remove dummy nodes left over by + // merging... removeTriviallyDeadNodes(); // FIXME: Merge nontrivially identical call nodes... // Alive - a set that holds all nodes found to be reachable/alive. - std::set Alive; + hash_set Alive; std::vector > GlobalNodes; // Mark all nodes reachable by (non-global) scalar nodes as alive... - for (std::map::iterator I = ScalarMap.begin(), - E = ScalarMap.end(); I != E; ++I) - if (!isa(I->first)) // Don't mark globals! - markAlive(I->second.getNode(), Alive); - else // Keep track of global nodes + for (hash_map::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?"); GlobalNodes.push_back(std::make_pair(I->first, I->second.getNode())); + ++I; + } else { + // Check to see if this is a worthless node generated for non-pointer + // values, such as integers. Consider an addition of long types: A+B. + // Assuming we can track all uses of the value in this context, and it is + // NOT used as a pointer, we can delete the node. We will be able to + // detect this situation if the node pointed to ONLY has Unknown bit set + // in the node. In this case, the node is not incomplete, does not point + // to any other nodes (no mod/ref bits set), and is therefore + // uninteresting for data structure analysis. If we run across one of + // these, prune the scalar pointing to it. + // + DSNode *N = I->second.getNode(); + if (N->NodeType == DSNode::UnknownNode && !isa(I->first)) { + ScalarMap.erase(I++); + } else { + I->second.getNode()->markReachableNodes(Alive); + ++I; + } + } // The return value is alive as well... - markAlive(RetNode.getNode(), Alive); + RetNode.getNode()->markReachableNodes(Alive); - // If any global nodes points to a non-global that is "alive", the global is - // "alive" as well... - // - std::set Visited; - for (unsigned i = 0, e = GlobalNodes.size(); i != e; ++i) - markAliveIfCanReachAlive(GlobalNodes[i].second, Alive, Visited); - - std::vector FCallsAlive(FunctionCalls.size()); + // Mark any nodes reachable by primary calls as alive... for (unsigned i = 0, e = FunctionCalls.size(); i != e; ++i) - if (CallSiteUsesAliveArgs(FunctionCalls[i], Alive, Visited)) { - markAlive(FunctionCalls[i], Alive); - FCallsAlive[i] = true; - } - - std::vector AuxFCallsAlive(AuxFunctionCalls.size()); - for (unsigned i = 0, e = AuxFunctionCalls.size(); i != e; ++i) - if (CallSiteUsesAliveArgs(AuxFunctionCalls[i], Alive, Visited)) { - markAlive(AuxFunctionCalls[i], Alive); - AuxFCallsAlive[i] = true; - } + FunctionCalls[i].markReachableNodes(Alive); + + 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 + // "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; + } - // Remove all dead function calls... - unsigned CurIdx = 0; - for (unsigned i = 0, e = FunctionCalls.size(); i != e; ++i) - if (FCallsAlive[i]) - FunctionCalls[CurIdx++].swap(FunctionCalls[i]); - // Crop all the bad ones out... - FunctionCalls.erase(FunctionCalls.begin()+CurIdx, FunctionCalls.end()); + for (unsigned i = 0, e = AuxFunctionCalls.size(); i != e; ++i) + if (!AuxFCallsAlive[i] && + CallSiteUsesAliveArgs(AuxFunctionCalls[i], Alive, Visited)) { + AuxFunctionCalls[i].markReachableNodes(Alive); + AuxFCallsAlive[i] = true; + Iterate = true; + } + } while (Iterate); // Remove all dead aux function calls... - CurIdx = 0; + unsigned CurIdx = 0; for (unsigned i = 0, e = AuxFunctionCalls.size(); i != e; ++i) if (AuxFCallsAlive[i]) AuxFunctionCalls[CurIdx++].swap(AuxFunctionCalls[i]); - // Crop all the bad ones out... + 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()); + } + // Crop all the useless ones out... AuxFunctionCalls.erase(AuxFunctionCalls.begin()+CurIdx, AuxFunctionCalls.end()); - - // Remove all unreachable globals from the ScalarMap - for (unsigned i = 0, e = GlobalNodes.size(); i != e; ++i) - if (!Alive.count(GlobalNodes[i].second)) - ScalarMap.erase(GlobalNodes[i].first); - - // Loop over all unreachable nodes, dropping their references... - vector DeadNodes; - DeadNodes.reserve(Nodes.size()); // Only one allocation is allowed. + // 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 + // + std::vector DeadNodes; + DeadNodes.reserve(Nodes.size()); for (unsigned i = 0; i != Nodes.size(); ++i) if (!Alive.count(Nodes[i])) { DSNode *N = Nodes[i]; - Nodes.erase(Nodes.begin()+i--); // Erase node from alive list. - DeadNodes.push_back(N); // Add node to our list of dead nodes - N->dropAllReferences(); // Drop all outgoing edges + 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->NodeType & DSNode::GlobalNode) == 0 || + (Flags & DSGraph::RemoveUnreachableGlobals)) + && "Killing a global?"); + //std::cerr << "[" << i+1 << "/" << DeadNodes.size() + // << "] Node is dead: "; N->dump(); + DeadNodes.push_back(N); + N->dropAllReferences(); + } + } else { + assert(Nodes[i]->getForwardNode() == 0 && "Alive forwarded node?"); } - - // Delete all dead nodes... - std::for_each(DeadNodes.begin(), DeadNodes.end(), deleter); -} - -#if 0 -//===----------------------------------------------------------------------===// -// GlobalDSGraph Implementation -//===----------------------------------------------------------------------===// - -#if 0 -// Bits used in the next function -static const char ExternalTypeBits = DSNode::GlobalNode | DSNode::HeapNode; - -// GlobalDSGraph::cloneNodeInto - Clone a global node and all its externally -// visible target links (and recursively their such links) into this graph. -// NodeCache maps the node being cloned to its clone in the Globals graph, -// in order to track cycles. -// GlobalsAreFinal is a flag that says whether it is safe to assume that -// an existing global node is complete. This is important to avoid -// reinserting all globals when inserting Calls to functions. -// This is a helper function for cloneGlobals and cloneCalls. -// -DSNode* GlobalDSGraph::cloneNodeInto(DSNode *OldNode, - std::map &NodeCache, - bool GlobalsAreFinal) { - if (OldNode == 0) return 0; - - // The caller should check this is an external node. Just more efficient... - assert((OldNode->NodeType & ExternalTypeBits) && "Non-external node"); - - // If a clone has already been created for OldNode, return it. - DSNode*& CacheEntry = NodeCache[OldNode]; - if (CacheEntry != 0) - return CacheEntry; - - // The result value... - DSNode* NewNode = 0; - - // If nodes already exist for any of the globals of OldNode, - // merge all such nodes together since they are merged in OldNode. - // If ValueCacheIsFinal==true, look for an existing node that has - // an identical list of globals and return it if it exists. + // Now that the nodes have either been deleted or moved to the globals graph, + // loop over the scalarmap, updating the entries for globals... // - for (unsigned j = 0, N = OldNode->getGlobals().size(); j != N; ++j) - if (DSNode *PrevNode = ScalarMap[OldNode->getGlobals()[j]].getNode()) { - if (NewNode == 0) { - NewNode = PrevNode; // first existing node found - if (GlobalsAreFinal && j == 0) - if (OldNode->getGlobals() == PrevNode->getGlobals()) { - CacheEntry = NewNode; - return NewNode; - } - } - else if (NewNode != PrevNode) { // found another, different from prev - // update ValMap *before* merging PrevNode into NewNode - for (unsigned k = 0, NK = PrevNode->getGlobals().size(); k < NK; ++k) - ScalarMap[PrevNode->getGlobals()[k]] = NewNode; - NewNode->mergeWith(PrevNode); - } - } else if (NewNode != 0) { - ScalarMap[OldNode->getGlobals()[j]] = NewNode; // add the merged node + 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; + hash_map::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); } - // If no existing node was found, clone the node and update the ValMap. - if (NewNode == 0) { - NewNode = new DSNode(*OldNode); - Nodes.push_back(NewNode); - for (unsigned j = 0, e = NewNode->getNumLinks(); j != e; ++j) - NewNode->setLink(j, 0); - for (unsigned j = 0, N = NewNode->getGlobals().size(); j < N; ++j) - ScalarMap[NewNode->getGlobals()[j]] = NewNode; - } - else - NewNode->NodeType |= OldNode->NodeType; // Markers may be different! - - // Add the entry to NodeCache - CacheEntry = NewNode; - - // Rewrite the links in the new node to point into the current graph, - // but only for links to external nodes. Set other links to NULL. - for (unsigned j = 0, e = OldNode->getNumLinks(); j != e; ++j) { - DSNode* OldTarget = OldNode->getLink(j); - if (OldTarget && (OldTarget->NodeType & ExternalTypeBits)) { - DSNode* NewLink = this->cloneNodeInto(OldTarget, NodeCache); - if (NewNode->getLink(j)) - NewNode->getLink(j)->mergeWith(NewLink); - else - NewNode->setLink(j, NewLink); - } + // 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) + ScalarMap.erase(GlobalNodes[i].first); } - // Remove all local markers - NewNode->NodeType &= ~(DSNode::AllocaNode | DSNode::ScalarNode); + // Loop over all of the dead nodes now, deleting them since their referrer + // count is zero. + for (unsigned i = 0, e = DeadNodes.size(); i != e; ++i) + delete DeadNodes[i]; - return NewNode; + DEBUG(AssertGraphOK(); GlobalsGraph->AssertGraphOK()); } - -// GlobalDSGraph::cloneCalls - Clone function calls and their visible target -// links (and recursively their such links) into this graph. -// -void GlobalDSGraph::cloneCalls(DSGraph& Graph) { - std::map NodeCache; - vector& FromCalls =Graph.FunctionCalls; - - FunctionCalls.reserve(FunctionCalls.size() + FromCalls.size()); - - for (int i = 0, ei = FromCalls.size(); i < ei; ++i) { - DSCallSite& callCopy = FunctionCalls.back(); - callCopy.reserve(FromCalls[i].size()); - for (unsigned j = 0, ej = FromCalls[i].size(); j != ej; ++j) - callCopy.push_back - ((FromCalls[i][j] && (FromCalls[i][j]->NodeType & ExternalTypeBits)) - ? cloneNodeInto(FromCalls[i][j], NodeCache, true) - : 0); +void DSGraph::AssertGraphOK() const { + for (unsigned i = 0, e = Nodes.size(); i != e; ++i) + Nodes[i]->assertOK(); + return; // FIXME: remove + for (hash_map::const_iterator I = ScalarMap.begin(), + E = ScalarMap.end(); I != E; ++I) { + assert(I->second.getNode() && "Null node in scalarmap!"); + AssertNodeInGraph(I->second.getNode()); + if (GlobalValue *GV = dyn_cast(I->first)) { + assert((I->second.getNode()->NodeType & DSNode::GlobalNode) && + "Global points to node, but node isn't global?"); + AssertNodeContainsGlobal(I->second.getNode(), GV); + } } - - // remove trivially identical function calls - removeIdenticalCalls(FunctionCalls, "Globals Graph"); + AssertCallNodesInGraph(); + AssertAuxCallNodesInGraph(); } -#endif - -#endif