X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FDataStructure%2FDataStructure.cpp;h=de34265f2abc0dccd12f3a761bde188103941245;hb=551ccae044b0ff658fe629dd67edd5ffe75d10e8;hp=94ed3487e84bb2728b238e83e1142dc6e7b84ff8;hpb=8d32767da44c6b06033fe305f3fd8e73ba042b4a;p=oota-llvm.git diff --git a/lib/Analysis/DataStructure/DataStructure.cpp b/lib/Analysis/DataStructure/DataStructure.cpp index 94ed3487e84..de34265f2ab 100644 --- a/lib/Analysis/DataStructure/DataStructure.cpp +++ b/lib/Analysis/DataStructure/DataStructure.cpp @@ -1,31 +1,52 @@ //===- 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. // //===----------------------------------------------------------------------===// -#include "llvm/Analysis/DSGraph.h" +#include "llvm/Analysis/DataStructure/DSGraphTraits.h" #include "llvm/Function.h" -#include "llvm/iOther.h" +#include "llvm/GlobalVariable.h" +#include "llvm/Instructions.h" #include "llvm/DerivedTypes.h" #include "llvm/Target/TargetData.h" -#include "Support/STLExtras.h" -#include "Support/Statistic.h" -#include "Support/Timer.h" +#include "llvm/Assembly/Writer.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/Debug.h" +#include "llvm/ADT/DepthFirstIterator.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/Statistic.h" +#include "llvm/Support/Timer.h" #include +using namespace llvm; namespace { - Statistic<> NumFolds ("dsnode", "Number of nodes completely folded"); - Statistic<> NumCallNodesMerged("dsnode", "Number of call nodes merged"); + Statistic<> NumFolds ("dsa", "Number of nodes completely folded"); + Statistic<> NumCallNodesMerged("dsa", "Number of call nodes merged"); + Statistic<> NumNodeAllocated ("dsa", "Number of nodes allocated"); + 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"); }; -namespace DS { // TODO: FIXME - extern TargetData TD; -} +#if 1 +#define TIME_REGION(VARNAME, DESC) \ + NamedRegionTimer VARNAME(DESC) +#else +#define TIME_REGION(VARNAME, DESC) +#endif + using namespace DS; DSNode *DSNodeHandle::HandleForwarding() const { - assert(!N->ForwardNH.isNull() && "Can only be invoked if forwarding!"); + assert(N->isForwarding() && "Can only be invoked if forwarding!"); // Handle node forwarding here! DSNode *Next = N->ForwardNH.getNode(); // Cause recursive shrinkage @@ -53,14 +74,27 @@ DSNode::DSNode(const Type *T, DSGraph *G) : NumReferrers(0), Size(0), ParentGraph(G), Ty(Type::VoidTy), NodeType(0) { // Add the type entry if it is specified... if (T) mergeTypeInfo(T, 0); - G->getNodes().push_back(this); + if (G) G->addNode(this); + ++NumNodeAllocated; } // 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) { - G->getNodes().push_back(this); +DSNode::DSNode(const DSNode &N, DSGraph *G, bool NullLinks) + : NumReferrers(0), Size(N.Size), ParentGraph(G), + Ty(N.Ty), 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); + ++NumNodeAllocated; +} + +/// getTargetData - Get the target data object used to construct this node. +/// +const TargetData &DSNode::getTargetData() const { + return ParentGraph->getTargetData(); } void DSNode::assertOK() const { @@ -68,6 +102,13 @@ void DSNode::assertOK() const { Ty == Type::VoidTy && (Size == 0 || (NodeType & DSNode::Array))) && "Node not OK!"); + + assert(ParentGraph && "Node has no parent?"); + const DSScalarMap &SM = ParentGraph->getScalarMap(); + for (unsigned i = 0, e = Globals.size(); i != e; ++i) { + assert(SM.count(Globals[i])); + assert(SM.find(Globals[i])->second.getNode() == this); + } } /// forwardNode - Mark this node as being obsolete, and all references to it @@ -79,11 +120,14 @@ void DSNode::forwardNode(DSNode *To, unsigned Offset) { 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); + ForwardNH.setTo(To, Offset); NodeType = DEAD; Size = 0; Ty = Type::VoidTy; + + // Remove this node from the parent graph's Nodes list. + ParentGraph->unlinkNode(this); + ParentGraph = 0; } // addGlobal - Add an entry for a global value to the Globals list. This also @@ -111,26 +155,40 @@ void DSNode::foldNodeCompletely() { ++NumFolds; - // Create the node we are going to forward to... - DSNode *DestNode = new DSNode(0, ParentGraph); - DestNode->NodeType = NodeType|DSNode::Array; - DestNode->Ty = Type::VoidTy; - DestNode->Size = 1; - DestNode->Globals.swap(Globals); - - // 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(); + // If this node has a size that is <= 1, we don't need to create a forwarding + // node. + if (getSize() <= 1) { + NodeType |= DSNode::Array; + Ty = Type::VoidTy; + Size = 1; + assert(Links.size() <= 1 && "Size is 1, but has more links?"); + Links.resize(1); } else { - DestNode->Links.resize(1); + // Create the node we are going to forward to. This is required because + // some referrers may have an offset that is > 0. By forcing them to + // forward, the forwarder has the opportunity to correct the offset. + DSNode *DestNode = new DSNode(0, ParentGraph); + DestNode->NodeType = NodeType|DSNode::Array; + 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]); + Links.clear(); + } else { + DestNode->Links.resize(1); + } } } @@ -142,7 +200,6 @@ bool DSNode::isNodeCompletelyFolded() const { return getSize() == 1 && Ty == Type::VoidTy && isArray(); } - namespace { /// TypeElementWalker Class - Used for implementation of physical subtyping... /// @@ -156,8 +213,9 @@ namespace { }; std::vector Stack; + const TargetData &TD; public: - TypeElementWalker(const Type *T) { + TypeElementWalker(const Type *T, const TargetData &td) : TD(td) { Stack.push_back(T); StepToLeaf(); } @@ -181,7 +239,7 @@ namespace { StackState &SS = Stack.back(); if (const StructType *ST = dyn_cast(SS.Ty)) { ++SS.Idx; - if (SS.Idx != ST->getElementTypes().size()) { + if (SS.Idx != ST->getNumElements()) { const StructLayout *SL = TD.getStructLayout(ST); SS.Offset += SL->MemberOffsets[SS.Idx]-SL->MemberOffsets[SS.Idx-1]; return; @@ -206,14 +264,14 @@ namespace { while (!Stack.empty() && !Stack.back().Ty->isFirstClassType()) { StackState &SS = Stack.back(); if (const StructType *ST = dyn_cast(SS.Ty)) { - if (ST->getElementTypes().empty()) { + if (ST->getNumElements() == 0) { assert(SS.Idx == 0); PopStackAndAdvance(); } else { // Step into the structure... - assert(SS.Idx < ST->getElementTypes().size()); + assert(SS.Idx < ST->getNumElements()); const StructLayout *SL = TD.getStructLayout(ST); - Stack.push_back(StackState(ST->getElementTypes()[SS.Idx], + Stack.push_back(StackState(ST->getElementType(SS.Idx), SS.Offset+SL->MemberOffsets[SS.Idx])); } } else { @@ -232,14 +290,16 @@ namespace { } } }; -} +} // end anonymous namespace /// ElementTypesAreCompatible - Check to see if the specified types are /// "physically" compatible. If so, return true, else return false. We only -/// have to check the fields in T1: T2 may be larger than T1. +/// have to check the fields in T1: T2 may be larger than T1. If AllowLargerT1 +/// is true, then we also allow a larger T1. /// -static bool ElementTypesAreCompatible(const Type *T1, const Type *T2) { - TypeElementWalker T1W(T1), T2W(T2); +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()) @@ -254,7 +314,7 @@ static bool ElementTypesAreCompatible(const Type *T1, const Type *T2) { T2W.StepToNextType(); } - return T1W.isDone(); + return AllowLargerT1 || T1W.isDone(); } @@ -268,6 +328,7 @@ static bool ElementTypesAreCompatible(const Type *T1, const Type *T2) { /// bool DSNode::mergeTypeInfo(const Type *NewTy, unsigned Offset, bool FoldIfIncompatible) { + const TargetData &TD = getTargetData(); // 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. @@ -311,8 +372,8 @@ bool DSNode::mergeTypeInfo(const Type *NewTy, unsigned Offset, 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(!isArray() && "This shouldn't happen!"); + assert(Offset == 0 && !isArray() && + "Cannot have an offset into a void node!"); Ty = NewTy; NodeType &= ~Array; if (WillBeArray) NodeType |= Array; @@ -370,7 +431,7 @@ bool DSNode::mergeTypeInfo(const Type *NewTy, unsigned Offset, while (O < Offset) { assert(Offset-O < TD.getTypeSize(SubType) && "Offset out of range!"); - switch (SubType->getPrimitiveID()) { + switch (SubType->getTypeID()) { case Type::StructTyID: { const StructType *STy = cast(SubType); const StructLayout &SL = *TD.getStructLayout(STy); @@ -380,7 +441,7 @@ bool DSNode::mergeTypeInfo(const Type *NewTy, unsigned Offset, /* empty */; // The offset we are looking for must be in the i'th element... - SubType = STy->getElementTypes()[i]; + SubType = STy->getElementType(i); O += SL.MemberOffsets[i]; break; } @@ -402,13 +463,18 @@ bool DSNode::mergeTypeInfo(const Type *NewTy, unsigned Offset, // If we found our type exactly, early exit if (SubType == NewTy) return false; + // Differing function types don't require us to merge. They are not values + // anyway. + if (isa(SubType) && + isa(NewTy)) return false; + unsigned SubTypeSize = SubType->isSized() ? 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 && - ElementTypesAreCompatible(NewTy, SubType)) + ElementTypesAreCompatible(NewTy, SubType, !isArray(), TD)) return false; // Okay, so we found the leader type at the offset requested. Search the list @@ -421,7 +487,7 @@ bool DSNode::mergeTypeInfo(const Type *NewTy, unsigned Offset, const Type *NextSubType = 0; unsigned NextSubTypeSize = 0; unsigned NextPadSize = 0; - switch (SubType->getPrimitiveID()) { + switch (SubType->getTypeID()) { case Type::StructTyID: { const StructType *STy = cast(SubType); const StructLayout &SL = *TD.getStructLayout(STy); @@ -429,7 +495,7 @@ bool DSNode::mergeTypeInfo(const Type *NewTy, unsigned Offset, NextPadSize = SL.MemberOffsets[1]; else NextPadSize = SubTypeSize; - NextSubType = STy->getElementTypes()[0]; + NextSubType = STy->getElementType(0); NextSubTypeSize = TD.getTypeSize(NextSubType); break; } @@ -474,9 +540,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; @@ -484,14 +555,14 @@ bool DSNode::mergeTypeInfo(const Type *NewTy, unsigned Offset, -// addEdgeTo - Add an edge from the current node to the specified node. This -// can cause merging of nodes in the graph. -// +/// addEdgeTo - Add an edge from the current node to the specified node. This +/// can cause merging of nodes in the graph. +/// void DSNode::addEdgeTo(unsigned Offset, const DSNodeHandle &NH) { - if (NH.getNode() == 0) return; // Nothing to do + if (NH.isNull()) return; // Nothing to do DSNodeHandle &ExistingEdge = getLink(Offset); - if (ExistingEdge.getNode()) { + if (!ExistingEdge.isNull()) { // Merge the two nodes... ExistingEdge.mergeWith(NH); } else { // No merging to perform... @@ -500,10 +571,10 @@ void DSNode::addEdgeTo(unsigned Offset, const DSNodeHandle &NH) { } -// MergeSortedVectors - Efficiently merge a vector into another vector where -// duplicates are not allowed and both are sorted. This assumes that 'T's are -// efficiently copyable and have sane comparison semantics. -// +/// MergeSortedVectors - Efficiently merge a vector into another vector where +/// duplicates are not allowed and both are sorted. This assumes that 'T's are +/// efficiently copyable and have sane comparison semantics. +/// static void MergeSortedVectors(std::vector &Dest, const std::vector &Src) { // By far, the most common cases will be the simple ones. In these cases, @@ -543,8 +614,11 @@ static void MergeSortedVectors(std::vector &Dest, } } +void DSNode::mergeGlobals(const std::vector &RHS) { + MergeSortedVectors(Globals, RHS); +} -// MergeNodes() - Helper function for DSNode::mergeWith(). +// 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. @@ -558,6 +632,8 @@ static void MergeSortedVectors(std::vector &Dest, void DSNode::MergeNodes(DSNodeHandle& CurNodeH, DSNodeHandle& NH) { assert(CurNodeH.getOffset() >= NH.getOffset() && "This should have been enforced in the caller."); + assert(CurNodeH.getNode()->getParentGraph()==NH.getNode()->getParentGraph() && + "Cannot merge two nodes that are not in the same graph!"); // 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 @@ -607,7 +683,7 @@ void DSNode::MergeNodes(DSNodeHandle& CurNodeH, DSNodeHandle& NH) { if (CurNodeH.getNode() == N || N == 0) return; assert(!CurNodeH.getNode()->isDeadNode()); - // Merge the NodeType information... + // Merge the NodeType information. CurNodeH.getNode()->NodeType |= N->NodeType; // Start forwarding to the new node! @@ -638,7 +714,7 @@ void DSNode::MergeNodes(DSNodeHandle& CurNodeH, DSNodeHandle& NH) { // Merge the globals list... if (!N->Globals.empty()) { - MergeSortedVectors(CurNodeH.getNode()->Globals, N->Globals); + CurNodeH.getNode()->mergeGlobals(N->Globals); // Delete the globals from the old node... std::vector().swap(N->Globals); @@ -646,18 +722,25 @@ void DSNode::MergeNodes(DSNodeHandle& CurNodeH, DSNodeHandle& NH) { } -// mergeWith - Merge this node and the specified node, moving all links to and -// from the argument node into the current node, deleting the node argument. -// Offset indicates what offset the specified node is to be merged into the -// current node. -// -// The specified node may be a null pointer (in which case, nothing happens). -// +/// mergeWith - Merge this node and the specified node, moving all links to and +/// from the argument node into the current node, deleting the node argument. +/// Offset indicates what offset the specified node is to be merged into the +/// current node. +/// +/// The specified node may be a null pointer (in which case, we update it to +/// point to this node). +/// void DSNode::mergeWith(const DSNodeHandle &NH, unsigned Offset) { DSNode *N = NH.getNode(); - if (N == 0 || (N == this && NH.getOffset() == Offset)) + if (N == this && NH.getOffset() == Offset) return; // Noop + // If the RHS is a null node, make it point to this node! + if (N == 0) { + NH.mergeWith(DSNodeHandle(this, Offset)); + return; + } + assert(!N->isDeadNode() && !isDeadNode()); assert(!hasNoReferrers() && "Should not try to fold a useless node!"); @@ -689,28 +772,299 @@ void DSNode::mergeWith(const DSNodeHandle &NH, unsigned Offset) { DSNode::MergeNodes(CurNodeH, NHCopy); } + +//===----------------------------------------------------------------------===// +// ReachabilityCloner Implementation +//===----------------------------------------------------------------------===// + +DSNodeHandle ReachabilityCloner::getClonedNH(const DSNodeHandle &SrcNH) { + if (SrcNH.isNull()) return DSNodeHandle(); + const DSNode *SN = SrcNH.getNode(); + + DSNodeHandle &NH = NodeMap[SN]; + if (!NH.isNull()) // Node already mapped? + return DSNodeHandle(NH.getNode(), NH.getOffset()+SrcNH.getOffset()); + + // If SrcNH has globals and the destination graph has one of the same globals, + // merge this node with the destination node, which is much more efficient. + if (SN->global_begin() != SN->global_end()) { + DSScalarMap &DestSM = Dest.getScalarMap(); + for (DSNode::global_iterator I = SN->global_begin(), E = SN->global_end(); + I != E; ++I) { + GlobalValue *GV = *I; + DSScalarMap::iterator GI = DestSM.find(GV); + if (GI != DestSM.end() && !GI->second.isNull()) { + // We found one, use merge instead! + merge(GI->second, Src.getNodeForValue(GV)); + assert(!NH.isNull() && "Didn't merge node!"); + return DSNodeHandle(NH.getNode(), NH.getOffset()+SrcNH.getOffset()); + } + } + } + + 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 + // reason, we must always go through NH. + DN = 0; + for (unsigned i = 0, e = SN->getNumLinks(); i != e; ++i) { + const DSNodeHandle &SrcEdge = SN->getLink(i << DS::PointerShift); + if (!SrcEdge.isNull()) { + const DSNodeHandle &DestEdge = getClonedNH(SrcEdge); + // 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 = NH.getNode(); + if (CN->getSize() != 1) + MergeOffset = ((i << DS::PointerShift)+NH.getOffset()) % CN->getSize(); + 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::global_iterator I = SN->global_begin(), E = SN->global_end(); + I != E; ++I) { + GlobalValue *GV = *I; + const DSNodeHandle &SrcGNH = Src.getNodeForValue(GV); + DSNodeHandle &DestGNH = NodeMap[SrcGNH.getNode()]; + assert(DestGNH.getNode() == NH.getNode() &&"Global mapping inconsistent"); + Dest.getNodeForValue(GV).mergeWith(DSNodeHandle(DestGNH.getNode(), + DestGNH.getOffset()+SrcGNH.getOffset())); + + if (CloneFlags & DSGraph::UpdateInlinedGlobals) + Dest.getInlinedGlobals().insert(GV); + } + NH.getNode()->mergeGlobals(SN->getGlobals()); + + return DSNodeHandle(NH.getNode(), NH.getOffset()+SrcNH.getOffset()); +} + +void ReachabilityCloner::merge(const DSNodeHandle &NH, + const DSNodeHandle &SrcNH) { + if (SrcNH.isNull()) return; // Noop + if (NH.isNull()) { + // If there is no destination node, just clone the source and assign the + // destination node to be it. + NH.mergeWith(getClonedNH(SrcNH)); + return; + } + + // Okay, at this point, we know that we have both a destination and a source + // node that need to be merged. Check to see if the source node has already + // been cloned. + const DSNode *SN = SrcNH.getNode(); + DSNodeHandle &SCNH = NodeMap[SN]; // SourceClonedNodeHandle + if (!SCNH.isNull()) { // Node already cloned? + NH.mergeWith(DSNodeHandle(SCNH.getNode(), + 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 + // into the existing node is less than the offset into the virtual node we are + // merging in. In this case, we have to extend the existing node, which + // requires an allocation anyway. + DSNode *DN = NH.getNode(); // Make sure the Offset is up-to-date + if (NH.getOffset() >= SrcNH.getOffset()) { + if (!DN->isNodeCompletelyFolded()) { + // Make sure the destination node is folded if the source node is folded. + if (SN->isNodeCompletelyFolded()) { + DN->foldNodeCompletely(); + DN = NH.getNode(); + } else if (SN->getSize() != DN->getSize()) { + // If the two nodes are of different size, and the smaller node has the + // array bit set, collapse! + if (SN->getSize() < DN->getSize()) { + if (SN->isArray()) { + DN->foldNodeCompletely(); + DN = NH.getNode(); + } + } else if (DN->isArray()) { + DN->foldNodeCompletely(); + DN = NH.getNode(); + } + } + + // 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(); + } + } + + assert(!DN->isDeadNode()); + + // Merge the NodeType information. + DN->mergeNodeFlags(SN->getNodeFlags() & BitsToKeep); + + // Before we start merging outgoing links and updating the scalar map, make + // sure it is known that this is the representative node for the src node. + SCNH = DSNodeHandle(DN, NH.getOffset()-SrcNH.getOffset()); + + // If the source node contains any globals, make sure they end up in the + // scalar map with the correct offset. + if (SN->global_begin() != SN->global_end()) { + // Update the globals in the destination node itself. + DN->mergeGlobals(SN->getGlobals()); + + // Update the scalar map for the graph we are merging the source node + // into. + for (DSNode::global_iterator I = SN->global_begin(), E = SN->global_end(); + I != E; ++I) { + GlobalValue *GV = *I; + const DSNodeHandle &SrcGNH = Src.getNodeForValue(GV); + DSNodeHandle &DestGNH = NodeMap[SrcGNH.getNode()]; + assert(DestGNH.getNode()==NH.getNode() &&"Global mapping inconsistent"); + Dest.getNodeForValue(GV).mergeWith(DSNodeHandle(DestGNH.getNode(), + DestGNH.getOffset()+SrcGNH.getOffset())); + + if (CloneFlags & DSGraph::UpdateInlinedGlobals) + Dest.getInlinedGlobals().insert(GV); + } + NH.getNode()->mergeGlobals(SN->getGlobals()); + } + } else { + // We cannot handle this case without allocating a temporary node. Fall + // back on being simple. + DSNode *NewDN = new DSNode(*SN, &Dest, true /* Null out all links */); + NewDN->maskNodeTypes(BitsToKeep); + + unsigned NHOffset = NH.getOffset(); + NH.mergeWith(DSNodeHandle(NewDN, SrcNH.getOffset())); + + assert(NH.getNode() && + (NH.getOffset() > NHOffset || + (NH.getOffset() == 0 && NH.getNode()->isNodeCompletelyFolded())) && + "Merging did not adjust the offset!"); + + // Before we start merging outgoing links and updating the scalar map, make + // 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 + // in the scalar map for them! + for (DSNode::global_iterator I = SN->global_begin(), E = SN->global_end(); + I != E; ++I) { + GlobalValue *GV = *I; + const DSNodeHandle &SrcGNH = Src.getNodeForValue(GV); + DSNodeHandle &DestGNH = NodeMap[SrcGNH.getNode()]; + assert(DestGNH.getNode()==NH.getNode() &&"Global mapping inconsistent"); + assert(SrcGNH.getNode() == SN && "Global mapping inconsistent"); + Dest.getNodeForValue(GV).mergeWith(DSNodeHandle(DestGNH.getNode(), + DestGNH.getOffset()+SrcGNH.getOffset())); + + if (CloneFlags & DSGraph::UpdateInlinedGlobals) + Dest.getInlinedGlobals().insert(GV); + } + } + + + // Next, recursively merge all outgoing links as necessary. Note that + // adding these links can cause the destination node to collapse itself at + // any time, and the current node may be merged with arbitrary other nodes. + // For this reason, we must always go through NH. + DN = 0; + for (unsigned i = 0, e = SN->getNumLinks(); i != e; ++i) { + const DSNodeHandle &SrcEdge = SN->getLink(i << DS::PointerShift); + if (!SrcEdge.isNull()) { + // 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. + 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, + // because the Link can disappear in the process of recursive merging. + merge(Tmp, SrcEdge); + } else { + Tmp.mergeWith(getClonedNH(SrcEdge)); + // Merging this could cause all kinds of recursive things to happen, + // culminating in the current node being eliminated. Since this is + // possible, make sure to reaquire the link from 'CN'. + + unsigned MergeOffset = 0; + CN = SCNH.getNode(); + MergeOffset = ((i << DS::PointerShift)+SCNH.getOffset()) %CN->getSize(); + CN->getLink(MergeOffset).mergeWith(Tmp); + } + } + } +} + +/// mergeCallSite - Merge the nodes reachable from the specified src call +/// site into the nodes reachable from DestCS. +void ReachabilityCloner::mergeCallSite(const DSCallSite &DestCS, + const DSCallSite &SrcCS) { + 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)); +} + + //===----------------------------------------------------------------------===// // DSCallSite Implementation //===----------------------------------------------------------------------===// // 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(); } +void DSCallSite::InitNH(DSNodeHandle &NH, const DSNodeHandle &Src, + ReachabilityCloner &RC) { + NH = RC.getClonedNH(Src); +} //===----------------------------------------------------------------------===// // DSGraph Implementation //===----------------------------------------------------------------------===// -DSGraph::DSGraph(const DSGraph &G) : GlobalsGraph(0) { +/// 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), TD(G.TD) { PrintAuxCalls = false; NodeMapTy NodeMap; cloneInto(G, ScalarMap, ReturnNodes, NodeMap); } DSGraph::DSGraph(const DSGraph &G, NodeMapTy &NodeMap) - : GlobalsGraph(0) { + : GlobalsGraph(0), TD(G.TD) { PrintAuxCalls = false; cloneInto(G, ScalarMap, ReturnNodes, NodeMap); } @@ -718,15 +1072,16 @@ DSGraph::DSGraph(const DSGraph &G, NodeMapTy &NodeMap) DSGraph::~DSGraph() { FunctionCalls.clear(); AuxFunctionCalls.clear(); + InlinedGlobals.clear(); ScalarMap.clear(); ReturnNodes.clear(); // Drop all intra-node references, so that assertions don't fail... - std::for_each(Nodes.begin(), Nodes.end(), - std::mem_fun(&DSNode::dropAllReferences)); + for (node_iterator NI = node_begin(), E = node_end(); NI != E; ++NI) + (*NI)->dropAllReferences(); - // Delete all of the nodes themselves... - std::for_each(Nodes.begin(), Nodes.end(), deleter); + // Free all of the nodes. + Nodes.clear(); } // dump - Allow inspection of graph in a debugger. @@ -737,13 +1092,36 @@ void DSGraph::dump() const { print(std::cerr); } /// specified mapping. /// void DSNode::remapLinks(DSGraph::NodeMapTy &OldNodeMap) { - for (unsigned i = 0, e = Links.size(); i != e; ++i) { - DSNodeHandle &H = OldNodeMap[Links[i].getNode()]; - Links[i].setNode(H.getNode()); - Links[i].setOffset(Links[i].getOffset()+H.getOffset()); - } + for (unsigned i = 0, e = Links.size(); i != e; ++i) + if (DSNode *N = Links[i].getNode()) { + DSGraph::NodeMapTy::const_iterator ONMI = OldNodeMap.find(N); + if (ONMI != OldNodeMap.end()) + Links[i].setTo(ONMI->second.getNode(), + Links[i].getOffset()+ONMI->second.getOffset()); + } } +/// updateFromGlobalGraph - This function rematerializes global nodes and +/// nodes reachable from them from the globals graph into the current graph. +/// It 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() { + TIME_REGION(X, "updateFromGlobalGraph"); + ReachabilityCloner RC(*this, *GlobalsGraph, 0); + + // Clone the non-up-to-date global nodes into this graph. + for (DSScalarMap::global_iterator I = getScalarMap().global_begin(), + E = getScalarMap().global_end(); I != E; ++I) + if (InlinedGlobals.count(*I) == 0) { // GNode is not up-to-date + DSScalarMap::iterator It = GlobalsGraph->ScalarMap.find(*I); + if (It != GlobalsGraph->ScalarMap.end()) + RC.merge(getNodeForValue(*I), It->second); + } +} /// cloneInto - Clone the specified DSGraph into the current graph. The /// translated ScalarMap for the old function is filled into the OldValMap @@ -751,50 +1129,55 @@ void DSNode::remapLinks(DSGraph::NodeMapTy &OldNodeMap) { /// /// The CloneFlags member controls various aspects of the cloning process. /// -void DSGraph::cloneInto(const DSGraph &G, ScalarMapTy &OldValMap, +void DSGraph::cloneInto(const DSGraph &G, DSScalarMap &OldValMap, ReturnNodesTy &OldReturnNodes, NodeMapTy &OldNodeMap, unsigned CloneFlags) { + TIME_REGION(X, "cloneInto"); assert(OldNodeMap.empty() && "Returned OldNodeMap should be empty!"); assert(&G != this && "Cannot clone graph into itself!"); - unsigned FN = Nodes.size(); // First new node... - - // Duplicate all of the nodes, populating the node map... - 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]; - DSNode *New = new DSNode(*Old, this); + + for (node_iterator I = G.node_begin(), E = G.node_end(); I != E; ++I) { + assert(!(*I)->isForwarding() && + "Forward nodes shouldn't be in node list!"); + DSNode *New = new DSNode(**I, this); New->maskNodeTypes(~BitsToClear); - OldNodeMap[Old] = New; + OldNodeMap[*I] = 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); + // 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 + // that node_iterator's can get easily invalidated! Because of this, we + // loop over the OldNodeMap, which contains all of the new nodes as the + // .second element of the map elements. Also note that if we remap a node + // more than once, we won't break anything. + for (NodeMapTy::iterator I = OldNodeMap.begin(), E = OldNodeMap.end(); + I != E; ++I) + I->second.getNode()->remapLinks(OldNodeMap); // Copy the scalar map... merging all of the global nodes... - for (ScalarMapTy::const_iterator I = G.ScalarMap.begin(), + for (DSScalarMap::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()); - - 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 + DSNodeHandle &H = OldValMap[I->first]; + H.mergeWith(DSNodeHandle(MappedNode.getNode(), + I->second.getOffset()+MappedNode.getOffset())); + + // 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); + if (CloneFlags & DSGraph::UpdateInlinedGlobals) + InlinedGlobals.insert(GV); } } @@ -807,7 +1190,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) @@ -825,60 +1208,196 @@ void DSGraph::cloneInto(const DSGraph &G, ScalarMapTy &OldValMap, } } +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; +} + +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; +} + /// mergeInGraph - The method is used for merging graphs together. If the /// argument graph is not *this, it makes a clone of the specified graph, then /// 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; - DSNodeHandle RetVal; +void DSGraph::mergeInGraph(const DSCallSite &CS, Function &F, + const DSGraph &Graph, unsigned CloneFlags) { + TIME_REGION(X, "mergeInGraph"); + + // Fastpath for a noop inline. + if (CS.getNumPtrArgs() == 0 && CS.getRetVal().isNull()) + return; // 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. - NodeMapTy OldNodeMap; + // 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); - // The clone call may invalidate any of the vectors in the data - // structure graph. Strip locals and don't copy the list of callers - ReturnNodesTy OldRetNodes; - cloneInto(Graph, OldValMap, OldRetNodes, OldNodeMap, CloneFlags); - RetVal = OldRetNodes[&F]; - ScalarMap = &OldValMap; - } else { - RetVal = getReturnNodeFor(F); - ScalarMap = &getScalarMap(); - } + // Set up argument bindings + 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 (AI != F.aend() && !isPointerType(AI->getType())) { + ++AI; +#ifndef NDEBUG // FIXME: We should merge vararg arguments! + if (AI == F.aend() && !F.getFunctionType()->isVarArg()) + std::cerr << "Bad call to Function: " << F.getName() << "\n"; +#endif + } + if (AI == F.aend()) break; + + // Add the link from the argument scalar to the provided value. + RC.merge(CS.getPtrArg(i), Graph.getNodeForValue(AI)); + } + + // Map the return node pointer over. + if (!CS.getRetVal().isNull()) + RC.merge(CS.getRetVal(), Graph.getReturnNodeFor(F)); + + // If requested, copy all of the calls. + if (!(CloneFlags & DontCloneCallNodes)) { + // Copy the function calls list... + FunctionCalls.reserve(FunctionCalls.size()+Graph.FunctionCalls.size()); + for (unsigned i = 0, ei = Graph.FunctionCalls.size(); i != ei; ++i) + FunctionCalls.push_back(DSCallSite(Graph.FunctionCalls[i], RC)); + } - // Merge the return value with the return value of the context... - RetVal.mergeWith(CS.getRetVal()); + // 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::vector CopiedAuxCall; + if (!(CloneFlags & DontCloneAuxCallNodes)) { + AuxFunctionCalls.reserve(AuxFunctionCalls.size()+ + Graph.AuxFunctionCalls.size()); + CopiedAuxCall.resize(Graph.AuxFunctionCalls.size()); + } + + // 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 (unsigned i = 0, ei = Graph.AuxFunctionCalls.size(); i != ei; ++i) + if (!CopiedAuxCall[i] && + PathExistsToClonedNode(Graph.AuxFunctionCalls[i], RC)) { + AuxFunctionCalls.push_back(DSCallSite(Graph.AuxFunctionCalls[i], + RC)); + CopiedAuxCall[i] = true; + MadeChange = true; + } + } + } - // Resolve all of the function arguments... - Function::aiterator AI = F.abegin(); + } else { + DSNodeHandle RetVal = getReturnNodeFor(F); - for (unsigned i = 0, e = CS.getNumPtrArgs(); i != e; ++i, ++AI) { - // Advance the argument iterator to the first pointer argument... - while (AI != F.aend() && !isPointerType(AI->getType())) { - ++AI; -#ifndef NDEBUG - if (AI == F.aend()) - std::cerr << "Bad call to Function: " << F.getName() << "\n"; + // Merge the return value with the return value of the context... + RetVal.mergeWith(CS.getRetVal()); + + // Resolve all of the function arguments... + 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 (AI != F.aend() && !isPointerType(AI->getType())) { + ++AI; +#ifndef NDEBUG // FIXME: We should merge varargs arguments!! + if (AI == F.aend() && !F.getFunctionType()->isVarArg()) + std::cerr << "Bad call to Function: " << F.getName() << "\n"; #endif + } + if (AI == F.aend()) break; + + // Add the link from the argument scalar to the provided value + DSNodeHandle &NH = getNodeForValue(AI); + assert(NH.getNode() && "Pointer argument without scalarmap entry?"); + NH.mergeWith(CS.getPtrArg(i)); } - 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)); } } +/// 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(getNodeForValue(I)); + + return DSCallSite(CallSite(), getReturnNodeFor(F), &F, Args); +} + +/// getDSCallSiteForCallSite - Given an LLVM CallSite object that is live in +/// the context of this graph, return the DSCallSite for it. +DSCallSite DSGraph::getDSCallSiteForCallSite(CallSite CS) const { + DSNodeHandle RetVal; + Instruction *I = CS.getInstruction(); + if (isPointerType(I->getType())) + RetVal = getNodeForValue(I); + + std::vector Args; + Args.reserve(CS.arg_end()-CS.arg_begin()); + + // Calculate the arguments vector... + for (CallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end(); I != E; ++I) + if (isPointerType((*I)->getType())) + Args.push_back(getNodeForValue(*I)); + + // Add a new function call entry... + if (Function *F = CS.getCalledFunction()) + return DSCallSite(CS, RetVal, F, Args); + else + return DSCallSite(CS, RetVal, + getNodeForValue(CS.getCalledValue()).getNode(), 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 +1412,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); @@ -926,9 +1445,8 @@ void DSGraph::markIncompleteNodes(unsigned Flags) { Function &F = *FI->first; if (F.getName() != "main") for (Function::aiterator I = F.abegin(), E = F.aend(); I != E; ++I) - if (isPointerType(I->getType()) && - ScalarMap.find(I) != ScalarMap.end()) - markIncompleteNode(ScalarMap[I].getNode()); + if (isPointerType(I->getType())) + markIncompleteNode(getNodeForValue(I).getNode()); } // Mark stuff passed into functions calls as being incomplete... @@ -942,9 +1460,11 @@ void DSGraph::markIncompleteNodes(unsigned Flags) { // Mark all global nodes as incomplete... if ((Flags & DSGraph::IgnoreGlobals) == 0) - for (unsigned i = 0, e = Nodes.size(); i != e; ++i) - if (Nodes[i]->isGlobalNode() && Nodes[i]->getNumLinks()) - markIncompleteNode(Nodes[i]); + for (DSScalarMap::global_iterator I = ScalarMap.global_begin(), + E = ScalarMap.global_end(); I != E; ++I) + if (GlobalVariable *GV = dyn_cast(*I)) + if (!GV->isConstant() || !GV->hasInitializer()) + markIncompleteNode(ScalarMap[GV].getNode()); } static inline void killIfUselessEdge(DSNodeHandle &Edge) { @@ -953,7 +1473,7 @@ static inline void killIfUselessEdge(DSNodeHandle &Edge) { // No interesting info? if ((N->getNodeFlags() & ~DSNode::Incomplete) == 0 && N->getType() == Type::VoidTy && !N->isNodeCompletelyFolded()) - Edge.setNode(0); // Kill the edge! + Edge.setTo(0, 0); // Kill the edge! } static inline bool nodeContainsExternalFunction(const DSNode *N) { @@ -969,6 +1489,7 @@ static void removeIdenticalCalls(std::vector &Calls) { unsigned NumFns = Calls.size(); std::sort(Calls.begin(), Calls.end()); // Sort by callee as primary key! +#if 1 // Scan the call list cleaning it up as necessary... DSNode *LastCalleeNode = 0; Function *LastCalleeFunc = 0; @@ -980,8 +1501,11 @@ static void removeIdenticalCalls(std::vector &Calls) { // 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()->getNodeFlags() == 0) { // No useful info? - std::cerr << "WARNING: Useless call site found??\n"; + CS.getCalleeNode()->isComplete() && + CS.getCalleeNode()->getGlobals().empty()) { // No useful info? +#ifndef NDEBUG + std::cerr << "WARNING: Useless call site found.\n"; +#endif CS.swap(Calls.back()); Calls.pop_back(); --i; @@ -1009,11 +1533,21 @@ static void removeIdenticalCalls(std::vector &Calls) { else LastCalleeContainsExternalFunction = LastCalleeFunc->isExternal(); } - - if (LastCalleeContainsExternalFunction || + + // 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 + // forwarding or not. This is clearly a problem, so this code is + // disabled until this can be resolved. +#if 1 + if (LastCalleeContainsExternalFunction +#if 0 + || // This should be more than enough context sensitivity! // FIXME: Evaluate how many times this is tripped! - NumDuplicateCalls > 20) { + NumDuplicateCalls > 20 +#endif + ) { DSCallSite &OCS = Calls[i-1]; OCS.mergeWith(CS); @@ -1023,6 +1557,7 @@ static void removeIdenticalCalls(std::vector &Calls) { else if (CS.getNumPtrArgs() > OCS.getNumPtrArgs()) OCS = CS; } +#endif } else { if (CS.isDirectCall()) { LastCalleeFunc = CS.getCalleeFunc(); @@ -1035,9 +1570,8 @@ static void removeIdenticalCalls(std::vector &Calls) { } } } - - Calls.erase(std::unique(Calls.begin(), Calls.end()), - Calls.end()); +#endif + Calls.erase(std::unique(Calls.begin(), Calls.end()), Calls.end()); // Track the number of call nodes merged away... NumCallNodesMerged += NumFns-Calls.size(); @@ -1053,44 +1587,87 @@ static void removeIdenticalCalls(std::vector &Calls) { // we don't have to perform any non-trivial analysis here. // void DSGraph::removeTriviallyDeadNodes() { - removeIdenticalCalls(FunctionCalls); - removeIdenticalCalls(AuxFunctionCalls); + TIME_REGION(X, "removeTriviallyDeadNodes"); + +#if 0 + /// NOTE: This code is disabled. This slows down DSA on 177.mesa + /// substantially! + + // 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. + { TIME_REGION(X, "removeTriviallyDeadNodes:node_iterate"); + for (node_iterator NI = node_begin(), E = node_end(); NI != E; ++NI) { + DSNode *N = *NI; + for (unsigned l = 0, e = N->getNumLinks(); l != e; ++l) + N->getLink(l*N->getPointerSize()).getNode(); + } + } + + // NOTE: This code is disabled. Though it should, in theory, allow us to + // remove more nodes down below, the scan of the scalar map is incredibly + // expensive for certain programs (with large SCCs). In the future, if we can + // make the scalar map scan more efficient, then we can reenable this. + { TIME_REGION(X, "removeTriviallyDeadNodes:scalarmap"); + + // Likewise, forward any edges from the scalar nodes. While we are at it, + // clean house a bit. + for (DSScalarMap::iterator I = ScalarMap.begin(),E = ScalarMap.end();I != E;){ + I->second.getNode(); + ++I; + } + } +#endif + bool isGlobalsGraph = !GlobalsGraph; - for (unsigned i = 0; i != Nodes.size(); ++i) { - DSNode *Node = Nodes[i]; - if (Node->isComplete() && !Node->isModified() && !Node->isRead()) { + for (NodeListTy::iterator NI = Nodes.begin(), E = Nodes.end(); NI != E; ) { + DSNode &Node = *NI; + + // 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) { + ++NI; + 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 // 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()) { - const std::vector &Globals = Node->getGlobals(); + if (Node.getNumReferrers() == Node.getGlobals().size()) { + const 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!"); + DSNode *N = getNodeForValue(Globals[j]).getNode(); + assert(N == &Node && "ScalarMap doesn't match globals list!"); } // Make sure NumReferrers still agrees, if so, the node is truly dead. - if (Node->getNumReferrers() == Globals.size()) { + if (Node.getNumReferrers() == Globals.size()) { for (unsigned j = 0, e = Globals.size(); j != e; ++j) ScalarMap.erase(Globals[j]); - Node->makeNodeDead(); + Node.makeNodeDead(); + ++NumTrivialGlobalDNE; } } } - if (Node->getNodeFlags() == 0 && Node->hasNoReferrers()) { + if (Node.getNodeFlags() == 0 && Node.hasNoReferrers()) { // This node is dead! - delete Node; // Free memory... - Nodes[i--] = Nodes.back(); - Nodes.pop_back(); // Remove from node list... + NI = Nodes.erase(NI); // Erase & remove from node list. + ++NumTrivialDNE; + } else { + ++NI; } } + + removeIdenticalCalls(FunctionCalls); + removeIdenticalCalls(AuxFunctionCalls); } @@ -1101,11 +1678,9 @@ void DSGraph::removeTriviallyDeadNodes() { 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); + if (ReachableNodes.insert(this).second) // Is newly reachable? + for (unsigned i = 0, e = getSize(); i < e; i += DS::PointerSize) + getLink(i).getNode()->markReachableNodes(ReachableNodes); } void DSCallSite::markReachableNodes(hash_set &Nodes) { @@ -1122,10 +1697,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 +1715,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 +1727,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,23 +1749,51 @@ static bool CallSiteUsesAliveArgs(DSCallSite &CS, hash_set &Alive, // inlining graphs. // void DSGraph::removeDeadNodes(unsigned Flags) { + DEBUG(AssertGraphOK(); if (GlobalsGraph) 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... + TIME_REGION(X, "removeDeadNodes"); + + // FIXME: Merge non-trivially identical call nodes... // Alive - a set that holds all nodes found to be reachable/alive. hash_set Alive; std::vector > GlobalNodes; + // Copy and merge all information about globals to the GlobalsGraph if this is + // not a final pass (where unreachable globals are removed). + // + // 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. + // + ReachabilityCloner GGCloner(*GlobalsGraph, *this, DSGraph::StripAllocaBit | + DSGraph::StripIncompleteBit); + // Mark all nodes reachable by (non-global) scalar nodes as alive... - for (ScalarMapTy::iterator I = ScalarMap.begin(), E = ScalarMap.end(); I !=E;) + { TIME_REGION(Y, "removeDeadNodes:scalarscan"); + for (DSScalarMap::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())); + + // Make sure that all globals are cloned over as roots. + if (!(Flags & DSGraph::RemoveUnreachableGlobals)) { + DSGraph::ScalarMapTy::iterator SMI = + GlobalsGraph->getScalarMap().find(I->first); + if (SMI != GlobalsGraph->getScalarMap().end()) + GGCloner.merge(SMI->second, I->second); + else + GGCloner.getClonedNH(I->second); + } ++I; } else { + DSNode *N = I->second.getNode(); +#if 0 // 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 @@ -1192,16 +1804,17 @@ void DSGraph::removeDeadNodes(unsigned Flags) { // 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->isUnknownNode() && !isa(I->first)) { + if (N->getNodeFlags() == DSNode::UnknownNode && !isa(I->first)) ScalarMap.erase(I++); - } else { - I->second.getNode()->markReachableNodes(Alive); + else { +#endif + N->markReachableNodes(Alive); ++I; - } + //} } + } - // The return value is alive as well... + // The return values are alive as well. for (ReturnNodesTy::iterator I = ReturnNodes.begin(), E = ReturnNodes.end(); I != E; ++I) I->second.getNode()->markReachableNodes(Alive); @@ -1210,120 +1823,129 @@ void DSGraph::removeDeadNodes(unsigned Flags) { for (unsigned i = 0, e = FunctionCalls.size(); i != e; ++i) FunctionCalls[i].markReachableNodes(Alive); + + // 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)) { - 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 GGCloner + for (unsigned i = CurIdx, e = AuxFunctionCalls.size(); i != e; ++i) + GlobalsGraph->AuxFunctionCalls.push_back(DSCallSite(AuxFunctionCalls[i], + GGCloner)); } // 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 GGCloner so we can destroy it. + GGCloner.destroy(); + + // 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()); - for (unsigned i = 0; i != Nodes.size(); ++i) - if (!Alive.count(Nodes[i])) { - 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(); - } - } 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); + for (NodeListTy::iterator NI = Nodes.begin(), E = Nodes.end(); NI != E;) { + DSNode *N = NI++; + assert(!N->isForwarding() && "Forwarded node in nodes list?"); + + if (!Alive.count(N)) { + Nodes.remove(N); + assert(!N->isForwarding() && "Cannot remove a forwarding node!"); + DeadNodes.push_back(N); + N->dropAllReferences(); + ++NumDNE; } + } - // 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) + if (!Alive.count(GlobalNodes[i].second)) ScalarMap.erase(GlobalNodes[i].first); - } + else + assert((Flags & DSGraph::RemoveUnreachableGlobals) && "non-dead global"); - // 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]; DEBUG(AssertGraphOK(); GlobalsGraph->AssertGraphOK()); } +void DSGraph::AssertCallSiteInGraph(const DSCallSite &CS) const { + if (CS.isIndirectCall()) { + AssertNodeInGraph(CS.getCalleeNode()); +#if 0 + if (CS.getNumPtrArgs() && CS.getCalleeNode() == CS.getPtrArg(0).getNode() && + CS.getCalleeNode() && CS.getCalleeNode()->getGlobals().empty()) + std::cerr << "WARNING: WIERD CALL SITE FOUND!\n"; +#endif + } + AssertNodeInGraph(CS.getRetVal().getNode()); + for (unsigned j = 0, e = CS.getNumPtrArgs(); j != e; ++j) + AssertNodeInGraph(CS.getPtrArg(j).getNode()); +} + +void DSGraph::AssertCallNodesInGraph() const { + for (unsigned i = 0, e = FunctionCalls.size(); i != e; ++i) + AssertCallSiteInGraph(FunctionCalls[i]); +} +void DSGraph::AssertAuxCallNodesInGraph() const { + for (unsigned i = 0, e = AuxFunctionCalls.size(); i != e; ++i) + AssertCallSiteInGraph(AuxFunctionCalls[i]); +} + void DSGraph::AssertGraphOK() const { - for (unsigned i = 0, e = Nodes.size(); i != e; ++i) - Nodes[i]->assertOK(); - return; // FIXME: remove + for (node_iterator NI = node_begin(), E = node_end(); NI != E; ++NI) + (*NI)->assertOK(); + for (ScalarMapTy::const_iterator I = ScalarMap.begin(), E = ScalarMap.end(); I != E; ++I) { assert(I->second.getNode() && "Null node in scalarmap!"); @@ -1337,3 +1959,39 @@ void DSGraph::AssertGraphOK() const { AssertCallNodesInGraph(); AssertAuxCallNodesInGraph(); } + +/// computeNodeMapping - Given roots in two different DSGraphs, traverse the +/// nodes reachable from the two graphs, computing the mapping of nodes from +/// the first to the second graph. +/// +void DSGraph::computeNodeMapping(const DSNodeHandle &NH1, + const DSNodeHandle &NH2, NodeMapTy &NodeMap, + bool StrictChecking) { + DSNode *N1 = NH1.getNode(), *N2 = NH2.getNode(); + if (N1 == 0 || N2 == 0) return; + + DSNodeHandle &Entry = NodeMap[N1]; + if (Entry.getNode()) { + // Termination of recursion! + if (StrictChecking) { + assert(Entry.getNode() == N2 && "Inconsistent mapping detected!"); + assert((Entry.getOffset() == (NH2.getOffset()-NH1.getOffset()) || + Entry.getNode()->isNodeCompletelyFolded()) && + "Inconsistent mapping detected!"); + } + return; + } + + Entry.setTo(N2, NH2.getOffset()-NH1.getOffset()); + + // Loop over all of the fields that N1 and N2 have in common, recursively + // mapping the edges together now. + int N2Idx = NH2.getOffset()-NH1.getOffset(); + unsigned N2Size = N2->getSize(); + for (unsigned i = 0, e = N1->getSize(); i < e; i += DS::PointerSize) + if (unsigned(N2Idx)+i < N2Size) + computeNodeMapping(N1->getLink(i), N2->getLink(N2Idx+i), NodeMap); + else + computeNodeMapping(N1->getLink(i), + N2->getLink(unsigned(N2Idx+i) % N2Size), NodeMap); +}