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

1 files changed, 178 insertions, 102 deletions

diff --git a/lib/Analysis/DataStructure/EliminateNodes.cpp b/lib/Analysis/DataStructure/EliminateNodes.cpp
index 3d1319dcf2..ca82ed1cd9 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).
-//
-static bool IndistinguishableShadowNode(const ShadowDSNode *SN) {
-  if (SN->getReferrers().empty()) return true;  // Node 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...
+//
+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];
-
-  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;
+  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) {
+      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;
 }
 
-
-// UnlinkUndistinguishableShadowNodes - Eliminate shadow nodes that are not
-// distinguishable from some other node in the graph...
-//
-bool FunctionDSGraph::UnlinkUndistinguishableShadowNodes() {
+template<typename NodeTy>
+bool removeIndistinguishableNode(std::vector<NodeTy*> &Nodes) {
   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)) {
+  std::vector<NodeTy*>::iterator I = Nodes.begin();
+  while (I != Nodes.end()) {
+    if (isIndistinguishableNode(*I)) {
 #ifdef DEBUG_NODE_ELIMINATE
-      cerr << "Found Indistinguishable Shadow Node:\n";
+      cerr << "Found Indistinguishable 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);
+      I = Nodes.erase(I);
       Changed = true;
     } else {
       ++I;
     }
+  }
   return Changed;
 }
 
-static void MarkReferredNodesReachable(DSNode *N, vector<ShadowDSNode*> &Nodes,
-                                       vector<bool> &Reachable);
+// UnlinkUndistinguishableShadowNodes - Eliminate shadow nodes that are not
+// distinguishable from some other node in the graph...
+//
+bool FunctionDSGraph::UnlinkUndistinguishableShadowNodes() {
+  // Loop over all of the shadow nodes, checking to see if they are
+  // indistinguishable from some other node.  If so, eliminate the node!
+  //
+  return
+    removeIndistinguishableNode(AllocNodes) |
+    removeIndistinguishableNode(ShadowNodes) |
+    removeIndistinguishableNode(GlobalNodes);
+}
+
+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 @@ bool FunctionDSGraph::RemoveUnreachableShadowNodes() {
     // 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];
 
-    Changed = true;
+        // 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...
 
-    // All dead nodes are in the DeadNodes vector... delete them now.
-    for_each(DeadNodes.begin(), DeadNodes.end(), deleter<DSNode>);
+    Changed = true;
   }
 }