Many changes
* Simplify a lot of the inlining stuff. There are still problems, but not
many
* Break up the Function representation to have a vector for every different
node type so it is fast to find nodes of a particular flavor.
* Do more intelligent merging of call values
* Allow elimination of unreachable shadow and allocation nodes
* Generalize indistinguishability testing to allow merging of identical calls.
* Increase shadow node merging power
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@2010 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/Analysis/DataStructure/EliminateNodes.cpp b/lib/Analysis/DataStructure/EliminateNodes.cpp
index 3d1319d..ca82ed1 100644
--- a/lib/Analysis/DataStructure/EliminateNodes.cpp
+++ b/lib/Analysis/DataStructure/EliminateNodes.cpp
@@ -21,157 +21,216 @@
//#define DEBUG_NODE_ELIMINATE 1
+bool AllocDSNode::isEquivalentTo(DSNode *Node) const {
+ if (AllocDSNode *N = dyn_cast<AllocDSNode>(Node))
+ return N->Allocation == Allocation;
+ return false;
+}
+
+bool GlobalDSNode::isEquivalentTo(DSNode *Node) const {
+ if (GlobalDSNode *G = dyn_cast<GlobalDSNode>(Node))
+ return G->Val == Val;
+ return false;
+}
+
+bool CallDSNode::isEquivalentTo(DSNode *Node) const {
+ if (CallDSNode *C = dyn_cast<CallDSNode>(Node))
+ return C->CI == CI && C->ArgLinks == ArgLinks;
+ return false;
+}
+
+bool ArgDSNode::isEquivalentTo(DSNode *Node) const {
+ return false;
+}
+
// NodesAreEquivalent - Check to see if the nodes are equivalent in all ways
// except node type. Since we know N1 is a shadow node, N2 is allowed to be
// any type.
//
-static bool NodesAreEquivalent(const ShadowDSNode *N1, const DSNode *N2) {
- assert(N1 != N2 && "A node is always equivalent to itself!");
-
- // Perform simple, fast checks first...
- if (N1->getType() != N2->getType() || // Must have same type...
- N1->isCriticalNode()) // Must not be a critical node...
- return false;
-
-#if 0
- return true;
-#else
-
- // The shadow node is considered equivalent if it has a subset of the incoming
- // edges that N2 does...
- if (N1->getReferrers().size() > N2->getReferrers().size()) return false;
-
- // Check to see if the referring (incoming) pointers are all the same...
- std::vector<PointerValSet*> N1R = N1->getReferrers();
- std::vector<PointerValSet*> N2R = N2->getReferrers();
- sort(N1R.begin(), N1R.end());
- sort(N2R.begin(), N2R.end());
-
- // The nodes are equivalent if the incoming edges to N1 are a subset of N2.
- unsigned i1 = 0, e1 = N1R.size();
- unsigned i2 = 0, e2 = N2R.size();
- for (; i1 != e1 && i2 < e2; ++i1, ++i2) {
- while (N1R[i1] > N2R[i2] && i2 < e2)
- ++i2;
-
- if (N1R[i1] < N2R[i2]) return false; // Error case...
- }
-
- return i1 == e1 && i2 <= e2;
-#endif
+bool ShadowDSNode::isEquivalentTo(DSNode *Node) const {
+ return !isCriticalNode(); // Must not be a critical node...
}
-// IndistinguishableShadowNode - A shadow node is indistinguishable if some
-// other node (shadow or otherwise) has exactly the same incoming and outgoing
-// links to it (or if there are no edges coming in, in which it is trivially
-// dead).
+
+
+// isIndistinguishableNode - A node is indistinguishable if some other node
+// has exactly the same incoming links to it and if the node considers itself
+// to be the same as the other node...
//
-static bool IndistinguishableShadowNode(const ShadowDSNode *SN) {
- if (SN->getReferrers().empty()) return true; // Node is trivially dead
-
+bool isIndistinguishableNode(DSNode *DN) {
+ if (DN->getReferrers().empty()) { // No referrers...
+ if (isa<ShadowDSNode>(DN) || isa<AllocDSNode>(DN))
+ return true; // Node is trivially dead
+ else
+ return false;
+ }
+
// Pick a random referrer... Ptr is the things that the referrer points to.
- // Since SN is in the Ptr set, look through the set seeing if there are any
- // other nodes that are exactly equilivant to SN (with the exception of node
- // type), but are not SN. If anything exists, then SN is indistinguishable.
+ // Since DN is in the Ptr set, look through the set seeing if there are any
+ // other nodes that are exactly equilivant to DN (with the exception of node
+ // type), but are not DN. If anything exists, then DN is indistinguishable.
//
- const PointerValSet &Ptr = *SN->getReferrers()[0];
+ const std::vector<PointerValSet*> &Refs = DN->getReferrers();
+ for (unsigned R = 0, RE = Refs.size(); R != RE; ++R) {
+ const PointerValSet &Ptr = *Refs[R];
- for (unsigned i = 0, e = Ptr.size(); i != e; ++i)
- if (Ptr[i].Index == 0 && Ptr[i].Node != cast<DSNode>(SN) &&
- NodesAreEquivalent(SN, Ptr[i].Node))
- return true;
+ for (unsigned i = 0, e = Ptr.size(); i != e; ++i) {
+ DSNode *N2 = Ptr[i].Node;
+ if (Ptr[i].Index == 0 && N2 != cast<DSNode>(DN) &&
+ DN->getType() == N2->getType() && DN->isEquivalentTo(N2)) {
+
+ // Otherwise, the nodes can be merged. Make sure that N2 contains all
+ // of the outgoing edges (fields) that DN does...
+ //
+ assert(DN->getNumLinks() == N2->getNumLinks() &&
+ "Same type, diff # fields?");
+ for (unsigned i = 0, e = DN->getNumLinks(); i != e; ++i)
+ N2->getLink(i).add(DN->getLink(i));
+
+ // Now make sure that all of the nodes that point to the shadow node
+ // also point to the node that we are merging it with...
+ //
+ const std::vector<PointerValSet*> &Refs = DN->getReferrers();
+ for (unsigned i = 0, e = Refs.size(); i != e; ++i) {
+ PointerValSet &PVS = *Refs[i];
+ // FIXME: this is incorrect if the referring pointer has index != 0
+ //
+ PVS.add(N2);
+ }
+ return true;
+ }
+ }
+ }
// Otherwise, nothing found, perhaps next time....
return false;
}
+template<typename NodeTy>
+bool removeIndistinguishableNode(std::vector<NodeTy*> &Nodes) {
+ bool Changed = false;
+ std::vector<NodeTy*>::iterator I = Nodes.begin();
+ while (I != Nodes.end()) {
+ if (isIndistinguishableNode(*I)) {
+#ifdef DEBUG_NODE_ELIMINATE
+ cerr << "Found Indistinguishable Node:\n";
+ (*I)->print(cerr);
+#endif
+ (*I)->removeAllIncomingEdges();
+ delete *I;
+ I = Nodes.erase(I);
+ Changed = true;
+ } else {
+ ++I;
+ }
+ }
+ return Changed;
+}
// UnlinkUndistinguishableShadowNodes - Eliminate shadow nodes that are not
// distinguishable from some other node in the graph...
//
bool FunctionDSGraph::UnlinkUndistinguishableShadowNodes() {
- bool Changed = false;
// Loop over all of the shadow nodes, checking to see if they are
// indistinguishable from some other node. If so, eliminate the node!
//
- for (vector<ShadowDSNode*>::iterator I = ShadowNodes.begin();
- I != ShadowNodes.end(); )
- if (IndistinguishableShadowNode(*I)) {
-#ifdef DEBUG_NODE_ELIMINATE
- cerr << "Found Indistinguishable Shadow Node:\n";
- (*I)->print(cerr);
-#endif
- (*I)->removeAllIncomingEdges();
- // Don't need to dropAllRefs, because nothing can point to it now
- delete *I;
-
- I = ShadowNodes.erase(I);
- Changed = true;
- } else {
- ++I;
- }
- return Changed;
+ return
+ removeIndistinguishableNode(AllocNodes) |
+ removeIndistinguishableNode(ShadowNodes) |
+ removeIndistinguishableNode(GlobalNodes);
}
-static void MarkReferredNodesReachable(DSNode *N, vector<ShadowDSNode*> &Nodes,
- vector<bool> &Reachable);
+static void MarkReferredNodesReachable(DSNode *N,
+ vector<ShadowDSNode*> &ShadowNodes,
+ vector<bool> &ReachableShadowNodes,
+ vector<AllocDSNode*> &AllocNodes,
+ vector<bool> &ReachableAllocNodes);
static inline void MarkReferredNodeSetReachable(const PointerValSet &PVS,
- vector<ShadowDSNode*> &Nodes,
- vector<bool> &Reachable) {
+ vector<ShadowDSNode*> &ShadowNodes,
+ vector<bool> &ReachableShadowNodes,
+ vector<AllocDSNode*> &AllocNodes,
+ vector<bool> &ReachableAllocNodes) {
for (unsigned i = 0, e = PVS.size(); i != e; ++i)
- if (ShadowDSNode *Shad = dyn_cast<ShadowDSNode>(PVS[i].Node))
- MarkReferredNodesReachable(Shad, Nodes, Reachable);
+ if (isa<ShadowDSNode>(PVS[i].Node) || isa<ShadowDSNode>(PVS[i].Node))
+ MarkReferredNodesReachable(PVS[i].Node, ShadowNodes, ReachableShadowNodes,
+ AllocNodes, ReachableAllocNodes);
}
-static void MarkReferredNodesReachable(DSNode *N, vector<ShadowDSNode*> &Nodes,
- vector<bool> &Reachable) {
- assert(Nodes.size() == Reachable.size());
- ShadowDSNode *Shad = dyn_cast<ShadowDSNode>(N);
+static void MarkReferredNodesReachable(DSNode *N,
+ vector<ShadowDSNode*> &ShadowNodes,
+ vector<bool> &ReachableShadowNodes,
+ vector<AllocDSNode*> &AllocNodes,
+ vector<bool> &ReachableAllocNodes) {
+ assert(ShadowNodes.size() == ReachableShadowNodes.size());
+ assert(AllocNodes.size() == ReachableAllocNodes.size());
- if (Shad) {
+ if (ShadowDSNode *Shad = dyn_cast<ShadowDSNode>(N)) {
vector<ShadowDSNode*>::iterator I =
- std::find(Nodes.begin(), Nodes.end(), Shad);
- unsigned i = I-Nodes.begin();
- if (Reachable[i]) return; // Recursion detected, abort...
- Reachable[i] = true;
+ std::find(ShadowNodes.begin(), ShadowNodes.end(), Shad);
+ unsigned i = I-ShadowNodes.begin();
+ if (ReachableShadowNodes[i]) return; // Recursion detected, abort...
+ ReachableShadowNodes[i] = true;
+ } else if (AllocDSNode *Alloc = dyn_cast<AllocDSNode>(N)) {
+ vector<AllocDSNode*>::iterator I =
+ std::find(AllocNodes.begin(), AllocNodes.end(), Alloc);
+ unsigned i = I-AllocNodes.begin();
+ if (ReachableAllocNodes[i]) return; // Recursion detected, abort...
+ ReachableAllocNodes[i] = true;
}
for (unsigned i = 0, e = N->getNumLinks(); i != e; ++i)
- MarkReferredNodeSetReachable(N->getLink(i), Nodes, Reachable);
+ MarkReferredNodeSetReachable(N->getLink(i),
+ ShadowNodes, ReachableShadowNodes,
+ AllocNodes, ReachableAllocNodes);
const std::vector<PointerValSet> *Links = N->getAuxLinks();
if (Links)
for (unsigned i = 0, e = Links->size(); i != e; ++i)
- MarkReferredNodeSetReachable((*Links)[i], Nodes, Reachable);
+ MarkReferredNodeSetReachable((*Links)[i],
+ ShadowNodes, ReachableShadowNodes,
+ AllocNodes, ReachableAllocNodes);
}
bool FunctionDSGraph::RemoveUnreachableShadowNodes() {
bool Changed = false;
while (1) {
-
- // Reachable - Contains true if there is an edge from a nonshadow node to
- // the numbered node...
+ // Reachable*Nodes - Contains true if there is an edge from a reachable
+ // node to the numbered node...
//
- vector<bool> Reachable(ShadowNodes.size());
+ vector<bool> ReachableShadowNodes(ShadowNodes.size());
+ vector<bool> ReachableAllocNodes (AllocNodes.size());
// Mark all shadow nodes that have edges from other nodes as reachable.
// Recursively mark any shadow nodes pointed to by the newly live shadow
// nodes as also alive.
//
- for (unsigned i = 0, e = Nodes.size(); i != e; ++i)
- // Loop over all of the nodes referred and mark them live if they are
- // shadow nodes...
- MarkReferredNodesReachable(Nodes[i], ShadowNodes, Reachable);
+ for (unsigned i = 0, e = ArgNodes.size(); i != e; ++i)
+ MarkReferredNodesReachable(ArgNodes[i],
+ ShadowNodes, ReachableShadowNodes,
+ AllocNodes, ReachableAllocNodes);
+
+ for (unsigned i = 0, e = GlobalNodes.size(); i != e; ++i)
+ MarkReferredNodesReachable(GlobalNodes[i],
+ ShadowNodes, ReachableShadowNodes,
+ AllocNodes, ReachableAllocNodes);
+
+ for (unsigned i = 0, e = CallNodes.size(); i != e; ++i)
+ MarkReferredNodesReachable(CallNodes[i],
+ ShadowNodes, ReachableShadowNodes,
+ AllocNodes, ReachableAllocNodes);
// Mark all nodes in the return set as being reachable...
- MarkReferredNodeSetReachable(RetNode, ShadowNodes, Reachable);
+ MarkReferredNodeSetReachable(RetNode,
+ ShadowNodes, ReachableShadowNodes,
+ AllocNodes, ReachableAllocNodes);
// Mark all nodes in the value map as being reachable...
for (std::map<Value*, PointerValSet>::iterator I = ValueMap.begin(),
E = ValueMap.end(); I != E; ++I)
- MarkReferredNodeSetReachable(I->second, ShadowNodes, Reachable);
-
+ MarkReferredNodeSetReachable(I->second,
+ ShadowNodes, ReachableShadowNodes,
+ AllocNodes, ReachableAllocNodes);
// At this point, all reachable shadow nodes have a true value in the
// Reachable vector. This means that any shadow nodes without an entry in
@@ -179,26 +238,43 @@
// a two part process, because we must drop all references before we delete
// the shadow nodes [in case cycles exist].
//
- vector<ShadowDSNode*> DeadNodes;
+ bool LocalChange = false;
for (unsigned i = 0; i != ShadowNodes.size(); ++i)
- if (!Reachable[i]) {
+ if (!ReachableShadowNodes[i]) {
// Track all unreachable nodes...
#if DEBUG_NODE_ELIMINATE
cerr << "Unreachable node eliminated:\n";
ShadowNodes[i]->print(cerr);
#endif
- DeadNodes.push_back(ShadowNodes[i]);
- ShadowNodes[i]->dropAllReferences(); // Drop references to other nodes
- Reachable.erase(Reachable.begin()+i); // Remove from reachable...
+ ShadowNodes[i]->removeAllIncomingEdges();
+ delete ShadowNodes[i];
+
+ // Remove from reachable...
+ ReachableShadowNodes.erase(ReachableShadowNodes.begin()+i);
ShadowNodes.erase(ShadowNodes.begin()+i); // Remove node entry
--i; // Don't skip the next node.
+ LocalChange = true;
}
- if (DeadNodes.empty()) return Changed; // No more dead nodes...
+ for (unsigned i = 0; i != AllocNodes.size(); ++i)
+ if (!ReachableAllocNodes[i]) {
+ // Track all unreachable nodes...
+#if DEBUG_NODE_ELIMINATE
+ cerr << "Unreachable node eliminated:\n";
+ AllocNodes[i]->print(cerr);
+#endif
+ AllocNodes[i]->removeAllIncomingEdges();
+ delete AllocNodes[i];
+
+ // Remove from reachable...
+ ReachableAllocNodes.erase(ReachableAllocNodes.begin()+i);
+ AllocNodes.erase(AllocNodes.begin()+i); // Remove node entry
+ --i; // Don't skip the next node.
+ LocalChange = true;
+ }
+
+ if (!LocalChange) return Changed; // No more dead nodes...
Changed = true;
-
- // All dead nodes are in the DeadNodes vector... delete them now.
- for_each(DeadNodes.begin(), DeadNodes.end(), deleter<DSNode>);
}
}