From 72d29a4b0018e6f50b73c6f0f2e9a0d4d6741180 Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Tue, 11 Feb 2003 23:11:51 +0000 Subject: [PATCH] Implement a "union-findy" version of DS-Analysis, which eliminates the Referrers list on DSNodes. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5536 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/DSGraphTraits.h | 11 +- include/llvm/Analysis/DSNode.h | 141 ++++--- include/llvm/Analysis/DSSupport.h | 41 ++- .../Analysis/DataStructure/DSGraphTraits.h | 11 +- include/llvm/Analysis/DataStructure/DSNode.h | 141 ++++--- .../llvm/Analysis/DataStructure/DSSupport.h | 41 ++- lib/Analysis/DataStructure/DataStructure.cpp | 347 ++++++------------ lib/Analysis/DataStructure/Local.cpp | 3 +- lib/Analysis/DataStructure/Steensgaard.cpp | 2 + lib/Analysis/DataStructure/TopDownClosure.cpp | 12 +- 10 files changed, 388 insertions(+), 362 deletions(-) diff --git a/include/llvm/Analysis/DSGraphTraits.h b/include/llvm/Analysis/DSGraphTraits.h index 78e0b3bb612..34e0e825d28 100644 --- a/include/llvm/Analysis/DSGraphTraits.h +++ b/include/llvm/Analysis/DSGraphTraits.h @@ -23,9 +23,11 @@ class DSNodeIterator : public forward_iterator { typedef DSNodeIterator _Self; DSNodeIterator(NodeTy *N) : Node(N), Offset(0) {} // begin iterator - DSNodeIterator(NodeTy *N, bool) // Create end iterator - : Node(N) { + DSNodeIterator(NodeTy *N, bool) : Node(N) { // Create end iterator Offset = N->getNumLinks() << DS::PointerShift; + if (Offset == 0 && Node->getForwardNode() && + (Node->NodeType & DSNode::DEAD)) // Model Forward link + Offset += DS::PointerSize; } public: DSNodeIterator(const DSNodeHandle &NH) @@ -43,7 +45,10 @@ public: } pointer operator*() const { - return Node->getLink(Offset).getNode(); + if (Node->NodeType & DSNode::DEAD) + return Node->getForwardNode(); + else + return Node->getLink(Offset).getNode(); } pointer operator->() const { return operator*(); } diff --git a/include/llvm/Analysis/DSNode.h b/include/llvm/Analysis/DSNode.h index f5bd8186025..c7edc5547e9 100644 --- a/include/llvm/Analysis/DSNode.h +++ b/include/llvm/Analysis/DSNode.h @@ -19,22 +19,26 @@ class DSNodeIterator; // Data structure graph traversal iterator /// different types represented in this object. /// class DSNode { - /// Referrers - Keep track of all of the node handles that point to this - /// DSNode. These pointers may need to be updated to point to a different - /// node if this node gets merged with it. + /// NumReferrers - The number of DSNodeHandles pointing to this node... if + /// this is a forwarding node, then this is the number of node handles which + /// are still forwarding over us. /// - std::vector Referrers; + unsigned NumReferrers; - /// Links - Contains one entry for every sizeof(void*) bytes in this memory - /// object. Note that if the node is not a multiple of size(void*) bytes - /// large, that there is an extra entry for the "remainder" of the node as - /// well. For this reason, nodes of 1 byte in size do have one link. + /// ForwardNH - This NodeHandle contain the node (and offset into the node) + /// that this node really is. When nodes get folded together, the node to be + /// eliminated has these fields filled in, otherwise ForwardNH.getNode() is + /// null. + DSNodeHandle ForwardNH; + + /// Size - The current size of the node. This should be equal to the size of + /// the current type record. /// - std::vector Links; + unsigned Size; - /// Globals - The list of global values that are merged into this node. + /// ParentGraph - The graph this node is currently embedded into. /// - std::vector Globals; + DSGraph *ParentGraph; /// Ty - Keep track of the current outer most type of this object, in addition /// to whether or not it has been indexed like an array or not. If the @@ -42,12 +46,19 @@ class DSNode { /// const Type *Ty; // The type itself... - /// Size - The current size of the node. This should be equal to the size of - /// the current type record. + /// Links - Contains one entry for every sizeof(void*) bytes in this memory + /// object. Note that if the node is not a multiple of size(void*) bytes + /// large, that there is an extra entry for the "remainder" of the node as + /// well. For this reason, nodes of 1 byte in size do have one link. /// - unsigned Size; + std::vector Links; + + /// Globals - The list of global values that are merged into this node. + /// + std::vector Globals; void operator=(const DSNode &); // DO NOT IMPLEMENT + DSNode(const DSNode &); // DO NOT IMPLEMENT public: enum NodeTy { ShadowNode = 0, // Nothing is known about this node... @@ -73,8 +84,8 @@ public: /// unsigned short NodeType; - DSNode(enum NodeTy NT, const Type *T); - DSNode(const DSNode &); + DSNode(unsigned NodeTy, const Type *T, DSGraph *G); + DSNode(const DSNode &, DSGraph *G); ~DSNode() { dropAllReferences(); @@ -100,13 +111,14 @@ public: const Type *getType() const { return Ty; } bool isArray() const { return NodeType & Array; } - /// getReferrers - Return a list of the pointers to this node... - /// - const std::vector &getReferrers() const { return Referrers; } - /// hasNoReferrers - Return true if nothing is pointing to this node at all. /// - bool hasNoReferrers() const { return Referrers.empty(); } + bool hasNoReferrers() const { return getNumReferrers() == 0; } + + /// getNumReferrers - This method returns the number of referrers to the + /// current node. Note that if this node is a forwarding node, this will + /// return the number of nodes forwarding over the node! + unsigned getNumReferrers() const { return NumReferrers; } /// isModified - Return true if this node may be modified in this context /// @@ -116,6 +128,18 @@ public: /// bool isRead() const { return (NodeType & Read) != 0; } + DSGraph *getParentGraph() const { return ParentGraph; } + void setParentGraph(DSGraph *G) { ParentGraph = G; } + + + /// getForwardNode - This method returns the node that this node is forwarded + /// to, if any. + DSNode *getForwardNode() const { return ForwardNH.getNode(); } + void stopForwarding() { + assert(!ForwardNH.isNull() && + "Node isn't forwarding, cannot stopForwarding!"); + ForwardNH.setNode(0); + } /// hasLink - Return true if this memory object has a link in slot #LinkNo /// @@ -209,11 +233,20 @@ public: const std::vector &getGlobals() const { return Globals; } std::vector &getGlobals() { return Globals; } + /// forwardNode - Mark this node as being obsolete, and all references to it + /// should be forwarded to the specified node and offset. + /// + void forwardNode(DSNode *To, unsigned Offset); + void print(std::ostream &O, const DSGraph *G) const; void dump() const; + void assertOK() const; + void dropAllReferences() { Links.clear(); + if (!ForwardNH.isNull()) + ForwardNH.setNode(0); } /// remapLinks - Change all of the Links in the current node according to the @@ -229,10 +262,6 @@ public: private: friend class DSNodeHandle; - // addReferrer - Keep the referrer set up to date... - void addReferrer(DSNodeHandle *H) { Referrers.push_back(H); } - void removeReferrer(DSNodeHandle *H); - // static mergeNodes - Helper for mergeWith() static void MergeNodes(DSNodeHandle& CurNodeH, DSNodeHandle& NH); }; @@ -242,19 +271,50 @@ private: // Define inline DSNodeHandle functions that depend on the definition of DSNode // inline DSNode *DSNodeHandle::getNode() const { + assert((!N || Offset < N->Size || (N->Size == 0 && Offset == 0) || + !N->ForwardNH.isNull()) && "Node handle offset out of range!"); + if (!N || N->ForwardNH.isNull()) + return N; + + // 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; } inline void DSNodeHandle::setNode(DSNode *n) { - if (N) N->removeReferrer(this); + assert(!n || !n->getForwardNode() && "Cannot set node to a forwarded node!"); + if (N) N->NumReferrers--; N = n; - if (N) N->addReferrer(this); + if (N) { + N->NumReferrers++; + if (Offset >= N->Size) { + assert((Offset == 0 || N->Size == 1) && + "Pointer to non-collapsed node with invalid offset!"); + Offset = 0; + } + } assert(!N || ((N->NodeType & DSNode::DEAD) == 0)); + + assert((!N || Offset < N->Size || (N->Size == 0 && Offset == 0) || + !N->ForwardNH.isNull()) && "Node handle offset out of range!"); } inline bool DSNodeHandle::hasLink(unsigned Num) const { assert(N && "DSNodeHandle does not point to a node yet!"); - return N->hasLink(Num+Offset); + return getNode()->hasLink(Num+Offset); } @@ -263,16 +323,16 @@ inline bool DSNodeHandle::hasLink(unsigned Num) const { /// inline const DSNodeHandle &DSNodeHandle::getLink(unsigned Off) const { assert(N && "DSNodeHandle does not point to a node yet!"); - return N->getLink(Offset+Off); + return getNode()->getLink(Offset+Off); } inline DSNodeHandle &DSNodeHandle::getLink(unsigned Off) { assert(N && "DSNodeHandle does not point to a node yet!"); - return N->getLink(Off+Offset); + return getNode()->getLink(Off+Offset); } inline void DSNodeHandle::setLink(unsigned Off, const DSNodeHandle &NH) { assert(N && "DSNodeHandle does not point to a node yet!"); - N->setLink(Off+Offset, NH); + getNode()->setLink(Off+Offset, NH); } /// addEdgeTo - Add an edge from the current node to the specified node. This @@ -280,7 +340,7 @@ inline void DSNodeHandle::setLink(unsigned Off, const DSNodeHandle &NH) { /// inline void DSNodeHandle::addEdgeTo(unsigned Off, const DSNodeHandle &Node) { assert(N && "DSNodeHandle does not point to a node yet!"); - N->addEdgeTo(Off+Offset, Node); + getNode()->addEdgeTo(Off+Offset, Node); } /// mergeWith - Merge the logical node pointed to by 'this' with the node @@ -288,24 +348,9 @@ inline void DSNodeHandle::addEdgeTo(unsigned Off, const DSNodeHandle &Node) { /// inline void DSNodeHandle::mergeWith(const DSNodeHandle &Node) { if (N != 0) - N->mergeWith(Node, Offset); + getNode()->mergeWith(Node, Offset); else // No node to merge with, so just point to Node *this = Node; } -inline void DSNodeHandle::swap(DSNodeHandle &NH) { - std::swap(Offset, NH.Offset); - if (N != NH.N) { - if (N) { - N->removeReferrer(this); - N->addReferrer(&NH); - } - if (NH.N) { - N->removeReferrer(&NH); - N->addReferrer(this); - } - std::swap(N, NH.N); - } -} - #endif diff --git a/include/llvm/Analysis/DSSupport.h b/include/llvm/Analysis/DSSupport.h index 0daf4f1f92d..a36ce66b34c 100644 --- a/include/llvm/Analysis/DSSupport.h +++ b/include/llvm/Analysis/DSSupport.h @@ -45,38 +45,54 @@ namespace DS { // FIXME: After the paper, this should get cleaned up /// DSNodeHandle (and friends) in one file complicates things. /// class DSNodeHandle { - DSNode *N; - unsigned Offset; + mutable DSNode *N; + mutable unsigned Offset; void operator==(const DSNode *N); // DISALLOW, use to promote N to nodehandle public: // Allow construction, destruction, and assignment... DSNodeHandle(DSNode *n = 0, unsigned offs = 0) : N(0), Offset(offs) { setNode(n); } - DSNodeHandle(const DSNodeHandle &H) : N(0), Offset(H.Offset) { setNode(H.N); } + DSNodeHandle(const DSNodeHandle &H) : N(0), Offset(0) { + setNode(H.getNode()); + Offset = H.Offset; // Must read offset AFTER the getNode() + } ~DSNodeHandle() { setNode((DSNode*)0); } DSNodeHandle &operator=(const DSNodeHandle &H) { - setNode(H.N); Offset = H.Offset; + Offset = 0; setNode(H.getNode()); Offset = H.Offset; return *this; } bool operator<(const DSNodeHandle &H) const { // Allow sorting - return N < H.N || (N == H.N && Offset < H.Offset); + return getNode() < H.getNode() || (N == H.N && Offset < H.Offset); } bool operator>(const DSNodeHandle &H) const { return H < *this; } bool operator==(const DSNodeHandle &H) const { // Allow comparison - return N == H.N && Offset == H.Offset; + return getNode() == H.getNode() && Offset == H.Offset; } bool operator!=(const DSNodeHandle &H) const { return !operator==(H); } - inline void swap(DSNodeHandle &H); + inline void swap(DSNodeHandle &NH) { + std::swap(Offset, NH.Offset); + std::swap(N, NH.N); + } + + /// isNull - Check to see if getNode() == 0, without going through the trouble + /// of checking to see if we are forwarding... + bool isNull() const { return N == 0; } // Allow explicit conversion to DSNode... inline DSNode *getNode() const; // Defined inline in DSNode.h unsigned getOffset() const { return Offset; } inline void setNode(DSNode *N); // Defined inline in DSNode.h - void setOffset(unsigned O) { Offset = O; } + void setOffset(unsigned O) { + //assert((!N || Offset < N->Size || (N->Size == 0 && Offset == 0) || + // !N->ForwardNH.isNull()) && "Node handle offset out of range!"); + //assert((!N || O < N->Size || (N->Size == 0 && O == 0) || + // !N->ForwardNH.isNull()) && "Node handle offset out of range!"); + Offset = O; + } void addEdgeTo(unsigned LinkNo, const DSNodeHandle &N); void addEdgeTo(const DSNodeHandle &N) { addEdgeTo(0, N); } @@ -98,7 +114,9 @@ public: inline void setLink(unsigned Num, const DSNodeHandle &NH); }; -inline void swap(DSNodeHandle &NH1, DSNodeHandle &NH2) { NH1.swap(NH2); } +namespace std { + inline void swap(DSNodeHandle &NH1, DSNodeHandle &NH2) { NH1.swap(NH2); } +} //===----------------------------------------------------------------------===// /// DSCallSite - Representation of a call site via its call instruction, @@ -252,6 +270,7 @@ public: } }; -inline void swap(DSCallSite &CS1, DSCallSite &CS2) { CS1.swap(CS2); } - +namespace std { + inline void swap(DSCallSite &CS1, DSCallSite &CS2) { CS1.swap(CS2); } +} #endif diff --git a/include/llvm/Analysis/DataStructure/DSGraphTraits.h b/include/llvm/Analysis/DataStructure/DSGraphTraits.h index 78e0b3bb612..34e0e825d28 100644 --- a/include/llvm/Analysis/DataStructure/DSGraphTraits.h +++ b/include/llvm/Analysis/DataStructure/DSGraphTraits.h @@ -23,9 +23,11 @@ class DSNodeIterator : public forward_iterator { typedef DSNodeIterator _Self; DSNodeIterator(NodeTy *N) : Node(N), Offset(0) {} // begin iterator - DSNodeIterator(NodeTy *N, bool) // Create end iterator - : Node(N) { + DSNodeIterator(NodeTy *N, bool) : Node(N) { // Create end iterator Offset = N->getNumLinks() << DS::PointerShift; + if (Offset == 0 && Node->getForwardNode() && + (Node->NodeType & DSNode::DEAD)) // Model Forward link + Offset += DS::PointerSize; } public: DSNodeIterator(const DSNodeHandle &NH) @@ -43,7 +45,10 @@ public: } pointer operator*() const { - return Node->getLink(Offset).getNode(); + if (Node->NodeType & DSNode::DEAD) + return Node->getForwardNode(); + else + return Node->getLink(Offset).getNode(); } pointer operator->() const { return operator*(); } diff --git a/include/llvm/Analysis/DataStructure/DSNode.h b/include/llvm/Analysis/DataStructure/DSNode.h index f5bd8186025..c7edc5547e9 100644 --- a/include/llvm/Analysis/DataStructure/DSNode.h +++ b/include/llvm/Analysis/DataStructure/DSNode.h @@ -19,22 +19,26 @@ class DSNodeIterator; // Data structure graph traversal iterator /// different types represented in this object. /// class DSNode { - /// Referrers - Keep track of all of the node handles that point to this - /// DSNode. These pointers may need to be updated to point to a different - /// node if this node gets merged with it. + /// NumReferrers - The number of DSNodeHandles pointing to this node... if + /// this is a forwarding node, then this is the number of node handles which + /// are still forwarding over us. /// - std::vector Referrers; + unsigned NumReferrers; - /// Links - Contains one entry for every sizeof(void*) bytes in this memory - /// object. Note that if the node is not a multiple of size(void*) bytes - /// large, that there is an extra entry for the "remainder" of the node as - /// well. For this reason, nodes of 1 byte in size do have one link. + /// ForwardNH - This NodeHandle contain the node (and offset into the node) + /// that this node really is. When nodes get folded together, the node to be + /// eliminated has these fields filled in, otherwise ForwardNH.getNode() is + /// null. + DSNodeHandle ForwardNH; + + /// Size - The current size of the node. This should be equal to the size of + /// the current type record. /// - std::vector Links; + unsigned Size; - /// Globals - The list of global values that are merged into this node. + /// ParentGraph - The graph this node is currently embedded into. /// - std::vector Globals; + DSGraph *ParentGraph; /// Ty - Keep track of the current outer most type of this object, in addition /// to whether or not it has been indexed like an array or not. If the @@ -42,12 +46,19 @@ class DSNode { /// const Type *Ty; // The type itself... - /// Size - The current size of the node. This should be equal to the size of - /// the current type record. + /// Links - Contains one entry for every sizeof(void*) bytes in this memory + /// object. Note that if the node is not a multiple of size(void*) bytes + /// large, that there is an extra entry for the "remainder" of the node as + /// well. For this reason, nodes of 1 byte in size do have one link. /// - unsigned Size; + std::vector Links; + + /// Globals - The list of global values that are merged into this node. + /// + std::vector Globals; void operator=(const DSNode &); // DO NOT IMPLEMENT + DSNode(const DSNode &); // DO NOT IMPLEMENT public: enum NodeTy { ShadowNode = 0, // Nothing is known about this node... @@ -73,8 +84,8 @@ public: /// unsigned short NodeType; - DSNode(enum NodeTy NT, const Type *T); - DSNode(const DSNode &); + DSNode(unsigned NodeTy, const Type *T, DSGraph *G); + DSNode(const DSNode &, DSGraph *G); ~DSNode() { dropAllReferences(); @@ -100,13 +111,14 @@ public: const Type *getType() const { return Ty; } bool isArray() const { return NodeType & Array; } - /// getReferrers - Return a list of the pointers to this node... - /// - const std::vector &getReferrers() const { return Referrers; } - /// hasNoReferrers - Return true if nothing is pointing to this node at all. /// - bool hasNoReferrers() const { return Referrers.empty(); } + bool hasNoReferrers() const { return getNumReferrers() == 0; } + + /// getNumReferrers - This method returns the number of referrers to the + /// current node. Note that if this node is a forwarding node, this will + /// return the number of nodes forwarding over the node! + unsigned getNumReferrers() const { return NumReferrers; } /// isModified - Return true if this node may be modified in this context /// @@ -116,6 +128,18 @@ public: /// bool isRead() const { return (NodeType & Read) != 0; } + DSGraph *getParentGraph() const { return ParentGraph; } + void setParentGraph(DSGraph *G) { ParentGraph = G; } + + + /// getForwardNode - This method returns the node that this node is forwarded + /// to, if any. + DSNode *getForwardNode() const { return ForwardNH.getNode(); } + void stopForwarding() { + assert(!ForwardNH.isNull() && + "Node isn't forwarding, cannot stopForwarding!"); + ForwardNH.setNode(0); + } /// hasLink - Return true if this memory object has a link in slot #LinkNo /// @@ -209,11 +233,20 @@ public: const std::vector &getGlobals() const { return Globals; } std::vector &getGlobals() { return Globals; } + /// forwardNode - Mark this node as being obsolete, and all references to it + /// should be forwarded to the specified node and offset. + /// + void forwardNode(DSNode *To, unsigned Offset); + void print(std::ostream &O, const DSGraph *G) const; void dump() const; + void assertOK() const; + void dropAllReferences() { Links.clear(); + if (!ForwardNH.isNull()) + ForwardNH.setNode(0); } /// remapLinks - Change all of the Links in the current node according to the @@ -229,10 +262,6 @@ public: private: friend class DSNodeHandle; - // addReferrer - Keep the referrer set up to date... - void addReferrer(DSNodeHandle *H) { Referrers.push_back(H); } - void removeReferrer(DSNodeHandle *H); - // static mergeNodes - Helper for mergeWith() static void MergeNodes(DSNodeHandle& CurNodeH, DSNodeHandle& NH); }; @@ -242,19 +271,50 @@ private: // Define inline DSNodeHandle functions that depend on the definition of DSNode // inline DSNode *DSNodeHandle::getNode() const { + assert((!N || Offset < N->Size || (N->Size == 0 && Offset == 0) || + !N->ForwardNH.isNull()) && "Node handle offset out of range!"); + if (!N || N->ForwardNH.isNull()) + return N; + + // 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; } inline void DSNodeHandle::setNode(DSNode *n) { - if (N) N->removeReferrer(this); + assert(!n || !n->getForwardNode() && "Cannot set node to a forwarded node!"); + if (N) N->NumReferrers--; N = n; - if (N) N->addReferrer(this); + if (N) { + N->NumReferrers++; + if (Offset >= N->Size) { + assert((Offset == 0 || N->Size == 1) && + "Pointer to non-collapsed node with invalid offset!"); + Offset = 0; + } + } assert(!N || ((N->NodeType & DSNode::DEAD) == 0)); + + assert((!N || Offset < N->Size || (N->Size == 0 && Offset == 0) || + !N->ForwardNH.isNull()) && "Node handle offset out of range!"); } inline bool DSNodeHandle::hasLink(unsigned Num) const { assert(N && "DSNodeHandle does not point to a node yet!"); - return N->hasLink(Num+Offset); + return getNode()->hasLink(Num+Offset); } @@ -263,16 +323,16 @@ inline bool DSNodeHandle::hasLink(unsigned Num) const { /// inline const DSNodeHandle &DSNodeHandle::getLink(unsigned Off) const { assert(N && "DSNodeHandle does not point to a node yet!"); - return N->getLink(Offset+Off); + return getNode()->getLink(Offset+Off); } inline DSNodeHandle &DSNodeHandle::getLink(unsigned Off) { assert(N && "DSNodeHandle does not point to a node yet!"); - return N->getLink(Off+Offset); + return getNode()->getLink(Off+Offset); } inline void DSNodeHandle::setLink(unsigned Off, const DSNodeHandle &NH) { assert(N && "DSNodeHandle does not point to a node yet!"); - N->setLink(Off+Offset, NH); + getNode()->setLink(Off+Offset, NH); } /// addEdgeTo - Add an edge from the current node to the specified node. This @@ -280,7 +340,7 @@ inline void DSNodeHandle::setLink(unsigned Off, const DSNodeHandle &NH) { /// inline void DSNodeHandle::addEdgeTo(unsigned Off, const DSNodeHandle &Node) { assert(N && "DSNodeHandle does not point to a node yet!"); - N->addEdgeTo(Off+Offset, Node); + getNode()->addEdgeTo(Off+Offset, Node); } /// mergeWith - Merge the logical node pointed to by 'this' with the node @@ -288,24 +348,9 @@ inline void DSNodeHandle::addEdgeTo(unsigned Off, const DSNodeHandle &Node) { /// inline void DSNodeHandle::mergeWith(const DSNodeHandle &Node) { if (N != 0) - N->mergeWith(Node, Offset); + getNode()->mergeWith(Node, Offset); else // No node to merge with, so just point to Node *this = Node; } -inline void DSNodeHandle::swap(DSNodeHandle &NH) { - std::swap(Offset, NH.Offset); - if (N != NH.N) { - if (N) { - N->removeReferrer(this); - N->addReferrer(&NH); - } - if (NH.N) { - N->removeReferrer(&NH); - N->addReferrer(this); - } - std::swap(N, NH.N); - } -} - #endif diff --git a/include/llvm/Analysis/DataStructure/DSSupport.h b/include/llvm/Analysis/DataStructure/DSSupport.h index 0daf4f1f92d..a36ce66b34c 100644 --- a/include/llvm/Analysis/DataStructure/DSSupport.h +++ b/include/llvm/Analysis/DataStructure/DSSupport.h @@ -45,38 +45,54 @@ namespace DS { // FIXME: After the paper, this should get cleaned up /// DSNodeHandle (and friends) in one file complicates things. /// class DSNodeHandle { - DSNode *N; - unsigned Offset; + mutable DSNode *N; + mutable unsigned Offset; void operator==(const DSNode *N); // DISALLOW, use to promote N to nodehandle public: // Allow construction, destruction, and assignment... DSNodeHandle(DSNode *n = 0, unsigned offs = 0) : N(0), Offset(offs) { setNode(n); } - DSNodeHandle(const DSNodeHandle &H) : N(0), Offset(H.Offset) { setNode(H.N); } + DSNodeHandle(const DSNodeHandle &H) : N(0), Offset(0) { + setNode(H.getNode()); + Offset = H.Offset; // Must read offset AFTER the getNode() + } ~DSNodeHandle() { setNode((DSNode*)0); } DSNodeHandle &operator=(const DSNodeHandle &H) { - setNode(H.N); Offset = H.Offset; + Offset = 0; setNode(H.getNode()); Offset = H.Offset; return *this; } bool operator<(const DSNodeHandle &H) const { // Allow sorting - return N < H.N || (N == H.N && Offset < H.Offset); + return getNode() < H.getNode() || (N == H.N && Offset < H.Offset); } bool operator>(const DSNodeHandle &H) const { return H < *this; } bool operator==(const DSNodeHandle &H) const { // Allow comparison - return N == H.N && Offset == H.Offset; + return getNode() == H.getNode() && Offset == H.Offset; } bool operator!=(const DSNodeHandle &H) const { return !operator==(H); } - inline void swap(DSNodeHandle &H); + inline void swap(DSNodeHandle &NH) { + std::swap(Offset, NH.Offset); + std::swap(N, NH.N); + } + + /// isNull - Check to see if getNode() == 0, without going through the trouble + /// of checking to see if we are forwarding... + bool isNull() const { return N == 0; } // Allow explicit conversion to DSNode... inline DSNode *getNode() const; // Defined inline in DSNode.h unsigned getOffset() const { return Offset; } inline void setNode(DSNode *N); // Defined inline in DSNode.h - void setOffset(unsigned O) { Offset = O; } + void setOffset(unsigned O) { + //assert((!N || Offset < N->Size || (N->Size == 0 && Offset == 0) || + // !N->ForwardNH.isNull()) && "Node handle offset out of range!"); + //assert((!N || O < N->Size || (N->Size == 0 && O == 0) || + // !N->ForwardNH.isNull()) && "Node handle offset out of range!"); + Offset = O; + } void addEdgeTo(unsigned LinkNo, const DSNodeHandle &N); void addEdgeTo(const DSNodeHandle &N) { addEdgeTo(0, N); } @@ -98,7 +114,9 @@ public: inline void setLink(unsigned Num, const DSNodeHandle &NH); }; -inline void swap(DSNodeHandle &NH1, DSNodeHandle &NH2) { NH1.swap(NH2); } +namespace std { + inline void swap(DSNodeHandle &NH1, DSNodeHandle &NH2) { NH1.swap(NH2); } +} //===----------------------------------------------------------------------===// /// DSCallSite - Representation of a call site via its call instruction, @@ -252,6 +270,7 @@ public: } }; -inline void swap(DSCallSite &CS1, DSCallSite &CS2) { CS1.swap(CS2); } - +namespace std { + inline void swap(DSCallSite &CS1, DSCallSite &CS2) { CS1.swap(CS2); } +} #endif diff --git a/lib/Analysis/DataStructure/DataStructure.cpp b/lib/Analysis/DataStructure/DataStructure.cpp index dbe6623f010..80586de2f14 100644 --- a/lib/Analysis/DataStructure/DataStructure.cpp +++ b/lib/Analysis/DataStructure/DataStructure.cpp @@ -28,25 +28,41 @@ using namespace DS; // 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::removeReferrer(DSNodeHandle *H) { - // Search backwards, because we depopulate the list from the back for - // efficiency (because it's a vector). - std::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); +void DSNode::assertOK() const { + assert((Ty != Type::VoidTy || + Ty == Type::VoidTy && (Size == 0 || + (NodeType & DSNode::Array))) && + "Node not OK!"); +} + +/// 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 @@ -70,25 +86,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 = Type::VoidTy; - NodeType |= Array; - Size = 1; - - // Loop over all of our referrers, making them point to our zero bytes of - // space. - for (std::vector::iterator I = Referrers.begin(), - E = Referrers.end(); I != E; ++I) - (*I)->setOffset(0); - - // If we have links, merge all of our outgoing links together... - for (unsigned i = 1; i < Links.size(); ++i) - Links[0].mergeWith(Links[i]); - Links.resize(1); + // 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); + + // 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 @@ -401,9 +424,8 @@ void DSNode::MergeNodes(DSNodeHandle& CurNodeH, DSNodeHandle& NH) { unsigned NSize = NH.getNode()->getSize(); // Merge the type entries of the two nodes together... - if (NH.getNode()->Ty != Type::VoidTy) { + 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 @@ -412,42 +434,34 @@ void DSNode::MergeNodes(DSNodeHandle& CurNodeH, DSNodeHandle& NH) { if (CurNodeH.getNode()->isNodeCompletelyFolded()) { if (!NH.getNode()->isNodeCompletelyFolded()) { NH.getNode()->foldNodeCompletely(); - assert(NH.getOffset()==0 && "folding did not make offset 0?"); + 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.getOffset()==0 && "folding did not make offset 0?"); + assert(CurNodeH.getNode() && CurNodeH.getOffset() == 0 && + "folding did not make offset 0?"); NOffset = NH.getOffset(); NSize = NH.getNode()->getSize(); assert(NOffset == 0 && NSize == 1); } - if (CurNodeH.getNode() == NH.getNode() || NH.getNode() == 0) return; + DSNode *N = NH.getNode(); + if (CurNodeH.getNode() == N || N == 0) return; assert((CurNodeH.getNode()->NodeType & DSNode::DEAD) == 0); - // Remove all edges pointing at N, causing them to point to 'this' instead. - // Make sure to adjust their offset, not just the node pointer. - // Also, be careful to use the DSNode* rather than NH since NH is one of - // the referrers and once NH refers to CurNodeH.getNode() this will - // become an infinite loop. - DSNode* N = NH.getNode(); - unsigned OldNHOffset = NH.getOffset(); - while (!N->Referrers.empty()) { - DSNodeHandle &Ref = *N->Referrers.back(); - Ref = DSNodeHandle(CurNodeH.getNode(), NOffset+Ref.getOffset()); - } - NH = DSNodeHandle(N, OldNHOffset); // reset NH to point back to where it was - + // 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 *NH now be outgoing links of - // this. This can cause recursive merging! - // - for (unsigned i = 0; i < NH.getNode()->getSize(); i += DS::PointerSize) { - DSNodeHandle &Link = NH.getNode()->getLink(i); + // 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 @@ -456,27 +470,22 @@ void DSNode::MergeNodes(DSNodeHandle& CurNodeH, DSNodeHandle& NH) { // recursive merging, we must make sure to merge in all remaining // links at offset zero. unsigned MergeOffset = 0; - if (CurNodeH.getNode()->Size != 1) - MergeOffset = (i+NOffset) % CurNodeH.getNode()->getSize(); - CurNodeH.getNode()->addEdgeTo(MergeOffset, Link); + 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. - NH.getNode()->Links.clear(); - NH.getNode()->Size = 0; - NH.getNode()->Ty = Type::VoidTy; - - // Merge the node types - CurNodeH.getNode()->NodeType |= NH.getNode()->NodeType; - NH.getNode()->NodeType = DEAD; // NH is now a dead node. + N->Links.clear(); // Merge the globals list... - if (!NH.getNode()->Globals.empty()) { - MergeSortedVectors(CurNodeH.getNode()->Globals, NH.getNode()->Globals); + if (!N->Globals.empty()) { + MergeSortedVectors(CurNodeH.getNode()->Globals, N->Globals); // Delete the globals from the old node... - NH.getNode()->Globals.clear(); + std::vector().swap(N->Globals); } } @@ -606,9 +615,8 @@ DSNodeHandle DSGraph::cloneInto(const DSGraph &G, 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); + DSNode *New = new DSNode(*Old, this); New->NodeType &= ~clearBits; - Nodes.push_back(New); OldNodeMap[Old] = New; } @@ -625,8 +633,8 @@ DSNodeHandle DSGraph::cloneInto(const DSGraph &G, 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? hash_map::iterator GVI = ScalarMap.find(I->first); @@ -705,6 +713,7 @@ void DSGraph::mergeInGraph(DSCallSite &CS, const DSGraph &Graph, 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)); @@ -775,7 +784,7 @@ void DSGraph::markIncompleteNodes(unsigned Flags) { 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() == Type::VoidTy && !N->isNodeCompletelyFolded()) Edge.setNode(0); // Kill the edge! @@ -805,7 +814,7 @@ 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()->getReferrers().size() == 1 && + 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()); @@ -893,13 +902,26 @@ void DSGraph::removeTriviallyDeadNodes() { // have all of these properties and still have incoming edges, due to the // scalar map, so we check those now. // - if (Node->getReferrers().size() == Node->getGlobals().size()) { + if (Node->getNumReferrers() == Node->getGlobals().size()) { std::vector &Globals = Node->getGlobals(); - for (unsigned j = 0, e = Globals.size(); j != e; ++j) - ScalarMap.erase(Globals[j]); - Globals.clear(); + + // 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; + Node->NodeType = DSNode::DEAD; + } } } @@ -919,6 +941,7 @@ 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 @@ -942,6 +965,7 @@ void DSCallSite::markReachableNodes(hash_set &Nodes) { 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; @@ -1015,7 +1039,7 @@ void DSGraph::removeDeadNodes(unsigned Flags) { do { Visited.clear(); // If any global nodes points to a non-global that is "alive", the global is - // "alive" as well... Remov it from the GlobalNodes list so we only have + // "alive" as well... Remove it from the GlobalNodes list so we only have // unreachable globals in the list. // Iterate = false; @@ -1055,22 +1079,28 @@ void DSGraph::removeDeadNodes(unsigned Flags) { // 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]; - std::swap(Nodes[i--], Nodes.back()); // move node to end of vector - Nodes.pop_back(); // Erase node from alive list. + 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?"); - while (!N->hasNoReferrers()) // Rewrite referrers - N->getReferrers().back()->setNode(0); - delete N; // Usecount is zero + //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, @@ -1096,7 +1126,8 @@ void DSGraph::removeDeadNodes(unsigned Flags) { // Merging leaves behind silly nodes, we remove them to avoid polluting the // globals graph. - GlobalsGraph->removeTriviallyDeadNodes(); + if (!GlobalNodes.empty()) + GlobalsGraph->removeTriviallyDeadNodes(); } else { // If we are in the top-down pass, remove all unreachable globals from the // ScalarMap... @@ -1104,10 +1135,18 @@ void DSGraph::removeDeadNodes(unsigned Flags) { ScalarMap.erase(GlobalNodes[i].first); } + // 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]; + DEBUG(AssertGraphOK(); GlobalsGraph->AssertGraphOK()); } 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!"); @@ -1121,149 +1160,3 @@ void DSGraph::AssertGraphOK() const { AssertCallNodesInGraph(); AssertAuxCallNodesInGraph(); } - - -#if 0 -//===----------------------------------------------------------------------===// -// GlobalDSGraph Implementation -//===----------------------------------------------------------------------===// - -#if 0 -// Bits used in the next function -static const char ExternalTypeBits = DSNode::GlobalNode | DSNode::HeapNode; - -// 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; -} - -// 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, - hash_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. - // - 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 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); - } - } - - // Remove all local markers - NewNode->NodeType &= ~(DSNode::AllocaNode | DSNode::ScalarNode); - - return NewNode; -} - - -// GlobalDSGraph::cloneCalls - Clone function calls and their visible target -// links (and recursively their such links) into this graph. -// -void GlobalDSGraph::cloneCalls(DSGraph& Graph) { - hash_map NodeCache; - std::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); - } - - // remove trivially identical function calls - removeIdenticalCalls(FunctionCalls, "Globals Graph"); -} -#endif - -#endif diff --git a/lib/Analysis/DataStructure/Local.cpp b/lib/Analysis/DataStructure/Local.cpp index b54827699ed..32d7aea42fa 100644 --- a/lib/Analysis/DataStructure/Local.cpp +++ b/lib/Analysis/DataStructure/Local.cpp @@ -109,8 +109,7 @@ namespace { /// the graph. /// DSNode *createNode(DSNode::NodeTy NodeType, const Type *Ty = 0) { - DSNode *N = new DSNode(NodeType, Ty); // Create the node - Nodes.push_back(N); // Add node to nodes list + DSNode *N = new DSNode(NodeType, Ty, &G); // Create the node if (DisableFieldSensitivity) N->foldNodeCompletely(); return N; diff --git a/lib/Analysis/DataStructure/Steensgaard.cpp b/lib/Analysis/DataStructure/Steensgaard.cpp index 0458670e6fb..bd6a7e932a3 100644 --- a/lib/Analysis/DataStructure/Steensgaard.cpp +++ b/lib/Analysis/DataStructure/Steensgaard.cpp @@ -193,6 +193,8 @@ bool Steens::run(Module &M) { ++i; // Skip this call site... } + RetValMap.clear(); + // Update the "incomplete" markers on the nodes, ignoring unknownness due to // incoming arguments... ResultGraph->maskIncompleteMarkers(); diff --git a/lib/Analysis/DataStructure/TopDownClosure.cpp b/lib/Analysis/DataStructure/TopDownClosure.cpp index de6233d4c8e..def549226f2 100644 --- a/lib/Analysis/DataStructure/TopDownClosure.cpp +++ b/lib/Analysis/DataStructure/TopDownClosure.cpp @@ -183,16 +183,10 @@ void TDDataStructures::calculateGraph(Function &F) { for (unsigned i = 0, e = NewCS.getNumPtrArgs(); i != e && AI != Callee->aend(); ++i, ++AI) { // Advance the argument iterator to the first pointer argument... - while (!DS::isPointerType(AI->getType())) { + while (AI != Callee->aend() && !DS::isPointerType(AI->getType())) ++AI; -#ifndef NDEBUG - if (AI == Callee->aend()) - std::cerr << "Bad call to Func: " << Callee->getName() << "\n"; -#endif - assert(AI != Callee->aend() && - "# Args provided is not # Args required!"); - } - + if (AI == Callee->aend()) break; + // Add the link from the argument scalar to the provided value DSNodeHandle &NH = CG.getNodeForValue(AI); assert(NH.getNode() && "Pointer argument without scalarmap entry?"); -- 2.34.1