lib/Analysis/DataStructure/EliminateNodes.cpp

   1 //===- EliminateNodes.cpp - Prune unneccesary nodes in the graph ----------===//
   2 //
   3 // This file contains two node optimizations:
   4 //   1. UnlinkUndistinguishableNodes - Often, after unification, shadow
   5 //      nodes are left around that should not exist anymore.  An example is when
   6 //      a shadow gets unified with a 'new' node, the following graph gets
   7 //      generated:  %X -> Shadow, %X -> New.  Since all of the edges to the
   8 //      shadow node also all go to the New node, we can eliminate the shadow.
   9 //
  10 //   2. RemoveUnreachableNodes - Remove shadow and allocation nodes that are not
  11 //      reachable from some other node in the graph.  Unreachable nodes are left
  12 //      lying around often because a method only refers to some allocations with
  13 //      scalar values or an alloca, then when it is inlined, these references
  14 //      disappear and the nodes become homeless and prunable.
  15 //
  16 //===----------------------------------------------------------------------===//
  17
  18 #include "llvm/Analysis/DataStructureGraph.h"
  19 #include "llvm/Value.h"
  20 #include "Support/STLExtras.h"
  21 #include <algorithm>
  22
  23 //#define DEBUG_NODE_ELIMINATE 1
  24
  25 static void DestroyFirstNodeOfPair(DSNode *N1, DSNode *N2) {
  26 #ifdef DEBUG_NODE_ELIMINATE
  27   cerr << "Found Indistinguishable Node:\n";
  28   N1->print(cerr);
  29 #endif
  30
  31   // The nodes can be merged.  Make sure that N2 contains all of the
  32   // outgoing edges (fields) that N1 does...
  33   //
  34   assert(N1->getNumLinks() == N2->getNumLinks() &&
  35          "Same type, diff # fields?");
  36   for (unsigned i = 0, e = N1->getNumLinks(); i != e; ++i)
  37     N2->getLink(i).add(N1->getLink(i));
  38
  39   // Now make sure that all of the nodes that point to N1 also point to the node
  40   // that we are merging it with...
  41   //
  42   const std::vector<PointerValSet*> &Refs = N1->getReferrers();
  43   for (unsigned i = 0, e = Refs.size(); i != e; ++i) {
  44     PointerValSet &PVS = *Refs[i];
  45
  46     bool RanOnce = false;
  47     for (unsigned j = 0, je = PVS.size(); j != je; ++j)
  48       if (PVS[j].Node == N1) {
  49         RanOnce = true;
  50         PVS.add(PointerVal(N2, PVS[j].Index));
  51       }
  52
  53     assert(RanOnce && "Node on user set but cannot find the use!");
  54   }
  55
  56   N1->removeAllIncomingEdges();
  57   delete N1;
  58 }
  59
  60 // isIndistinguishableNode - A node is indistinguishable if some other node
  61 // has exactly the same incoming links to it and if the node considers itself
  62 // to be the same as the other node...
  63 //
  64 static bool isIndistinguishableNode(DSNode *DN) {
  65   if (DN->getReferrers().empty()) {       // No referrers...
  66     if (isa<ShadowDSNode>(DN) || isa<AllocDSNode>(DN))
  67       return true;  // Node is trivially dead
  68     else
  69       return false;
  70   }
  71
  72   // Pick a random referrer... Ptr is the things that the referrer points to.
  73   // Since DN is in the Ptr set, look through the set seeing if there are any
  74   // other nodes that are exactly equilivant to DN (with the exception of node
  75   // type), but are not DN.  If anything exists, then DN is indistinguishable.
  76   //
  77
  78   DSNode *IndFrom = 0;
  79   const std::vector<PointerValSet*> &Refs = DN->getReferrers();
  80   for (unsigned R = 0, RE = Refs.size(); R != RE; ++R) {
  81     const PointerValSet &Ptr = *Refs[R];
  82
  83     for (unsigned i = 0, e = Ptr.size(); i != e; ++i) {
  84       DSNode *N2 = Ptr[i].Node;
  85       if (Ptr[i].Index == 0 && N2 != cast<DSNode>(DN) &&
  86           DN->getType() == N2->getType() && DN->isEquivalentTo(N2)) {
  87
  88         IndFrom = N2;
  89         R = RE-1;
  90         break;
  91       }
  92     }
  93   }
  94
  95   // If we haven't found an equivalent node to merge with, see if one of the
  96   // nodes pointed to by this node is equivalent to this one...
  97   //
  98   if (IndFrom == 0) {
  99     unsigned NumOutgoing = DN->getNumOutgoingLinks();
 100     for (DSNode::iterator I = DN->begin(), E = DN->end(); I != E; ++I) {
 101       DSNode *Linked = *I;
 102       if (Linked != DN && Linked->getNumOutgoingLinks() == NumOutgoing &&
 103           DN->getType() == Linked->getType() && DN->isEquivalentTo(Linked)) {
 104 #if 0
 105         // Make sure the leftover node contains links to everything we do...
 106         for (unsigned i = 0, e = DN->getNumLinks(); i != e; ++i)
 107           Linked->getLink(i).add(DN->getLink(i));
 108 #endif
 109
 110         IndFrom = Linked;
 111         break;
 112       }
 113     }
 114   }
 115
 116
 117   // If DN is indistinguishable from some other node, merge them now...
 118   if (IndFrom == 0)
 119     return false;     // Otherwise, nothing found, perhaps next time....
 120
 121   DestroyFirstNodeOfPair(DN, IndFrom);
 122   return true;
 123 }
 124
 125 template<typename NodeTy>
 126 static bool removeIndistinguishableNodes(std::vector<NodeTy*> &Nodes) {
 127   bool Changed = false;
 128   std::vector<NodeTy*>::iterator I = Nodes.begin();
 129   while (I != Nodes.end()) {
 130     if (isIndistinguishableNode(*I)) {
 131       I = Nodes.erase(I);
 132       Changed = true;
 133     } else {
 134       ++I;
 135     }
 136   }
 137   return Changed;
 138 }
 139
 140 template<typename NodeTy>
 141 static bool removeIndistinguishableNodePairs(std::vector<NodeTy*> &Nodes) {
 142   bool Changed = false;
 143   std::vector<NodeTy*>::iterator I = Nodes.begin();
 144   while (I != Nodes.end()) {
 145     NodeTy *N1 = *I++;
 146     for (std::vector<NodeTy*>::iterator I2 = I, I2E = Nodes.end();
 147          I2 != I2E; ++I2) {
 148       NodeTy *N2 = *I2;
 149       if (N1->isEquivalentTo(N2)) {
 150         DestroyFirstNodeOfPair(N1, N2);
 151         --I;
 152         I = Nodes.erase(I);
 153         Changed = true;
 154         break;
 155       }
 156     }
 157   }
 158   return Changed;
 159 }
 160
 161
 162
 163 // UnlinkUndistinguishableNodes - Eliminate shadow nodes that are not
 164 // distinguishable from some other node in the graph...
 165 //
 166 bool FunctionDSGraph::UnlinkUndistinguishableNodes() {
 167   // Loop over all of the shadow nodes, checking to see if they are
 168   // indistinguishable from some other node.  If so, eliminate the node!
 169   //
 170   return
 171     removeIndistinguishableNodes(AllocNodes) |
 172     removeIndistinguishableNodes(ShadowNodes) |
 173     //FIXME: We cannot naively remove call nodes here because if there is a
 174     // shadow node that is the result of the call, we have to make sure to
 175     // merge the shadow node as well!!!
 176     //    removeIndistinguishableNodePairs(CallNodes) |
 177     removeIndistinguishableNodePairs(GlobalNodes);
 178 }
 179
 180 static void MarkReferredNodesReachable(DSNode *N,
 181                                        vector<ShadowDSNode*> &ShadowNodes,
 182                                        vector<bool> &ReachableShadowNodes,
 183                                        vector<AllocDSNode*>  &AllocNodes,
 184                                        vector<bool> &ReachableAllocNodes);
 185
 186 static inline void MarkReferredNodeSetReachable(const PointerValSet &PVS,
 187                                             vector<ShadowDSNode*> &ShadowNodes,
 188                                             vector<bool> &ReachableShadowNodes,
 189                                             vector<AllocDSNode*>  &AllocNodes,
 190                                             vector<bool> &ReachableAllocNodes) {
 191   for (unsigned i = 0, e = PVS.size(); i != e; ++i)
 192     if (isa<ShadowDSNode>(PVS[i].Node) || isa<AllocDSNode>(PVS[i].Node))
 193       MarkReferredNodesReachable(PVS[i].Node, ShadowNodes, ReachableShadowNodes,
 194                                  AllocNodes, ReachableAllocNodes);
 195 }
 196
 197 static void MarkReferredNodesReachable(DSNode *N,
 198                                        vector<ShadowDSNode*> &ShadowNodes,
 199                                        vector<bool> &ReachableShadowNodes,
 200                                        vector<AllocDSNode*>  &AllocNodes,
 201                                        vector<bool> &ReachableAllocNodes) {
 202   assert(ShadowNodes.size() == ReachableShadowNodes.size());
 203   assert(AllocNodes.size()  == ReachableAllocNodes.size());
 204
 205   if (ShadowDSNode *Shad = dyn_cast<ShadowDSNode>(N)) {
 206     vector<ShadowDSNode*>::iterator I =
 207       std::find(ShadowNodes.begin(), ShadowNodes.end(), Shad);
 208     unsigned i = I-ShadowNodes.begin();
 209     if (ReachableShadowNodes[i]) return;  // Recursion detected, abort...
 210     ReachableShadowNodes[i] = true;
 211   } else if (AllocDSNode *Alloc = dyn_cast<AllocDSNode>(N)) {
 212     vector<AllocDSNode*>::iterator I =
 213       std::find(AllocNodes.begin(), AllocNodes.end(), Alloc);
 214     unsigned i = I-AllocNodes.begin();
 215     if (ReachableAllocNodes[i]) return;  // Recursion detected, abort...
 216     ReachableAllocNodes[i] = true;
 217   }
 218
 219   for (unsigned i = 0, e = N->getNumLinks(); i != e; ++i)
 220     MarkReferredNodeSetReachable(N->getLink(i),
 221                                  ShadowNodes, ReachableShadowNodes,
 222                                  AllocNodes, ReachableAllocNodes);
 223
 224   const std::vector<PointerValSet> *Links = N->getAuxLinks();
 225   if (Links)
 226     for (unsigned i = 0, e = Links->size(); i != e; ++i)
 227       MarkReferredNodeSetReachable((*Links)[i],
 228                                    ShadowNodes, ReachableShadowNodes,
 229                                    AllocNodes, ReachableAllocNodes);
 230 }
 231
 232 void FunctionDSGraph::MarkEscapeableNodesReachable(
 233                                        vector<bool> &ReachableShadowNodes,
 234                                        vector<bool> &ReachableAllocNodes) {
 235   // Mark all shadow nodes that have edges from other nodes as reachable.
 236   // Recursively mark any shadow nodes pointed to by the newly live shadow
 237   // nodes as also alive.
 238   //
 239   for (unsigned i = 0, e = ArgNodes.size(); i != e; ++i)
 240     MarkReferredNodesReachable(ArgNodes[i],
 241                                ShadowNodes, ReachableShadowNodes,
 242                                AllocNodes, ReachableAllocNodes);
 243
 244   for (unsigned i = 0, e = GlobalNodes.size(); i != e; ++i)
 245     MarkReferredNodesReachable(GlobalNodes[i],
 246                                ShadowNodes, ReachableShadowNodes,
 247                                AllocNodes, ReachableAllocNodes);
 248
 249   for (unsigned i = 0, e = CallNodes.size(); i != e; ++i)
 250     MarkReferredNodesReachable(CallNodes[i],
 251                                ShadowNodes, ReachableShadowNodes,
 252                                AllocNodes, ReachableAllocNodes);
 253
 254   // Mark all nodes in the return set as being reachable...
 255   MarkReferredNodeSetReachable(RetNode,
 256                                ShadowNodes, ReachableShadowNodes,
 257                                AllocNodes, ReachableAllocNodes);
 258 }
 259
 260 bool FunctionDSGraph::RemoveUnreachableNodes() {
 261   bool Changed = false;
 262
 263   while (1) {
 264     // Reachable*Nodes - Contains true if there is an edge from a reachable
 265     // node to the numbered node...
 266     //
 267     vector<bool> ReachableShadowNodes(ShadowNodes.size());
 268     vector<bool> ReachableAllocNodes (AllocNodes.size());
 269
 270     MarkEscapeableNodesReachable(ReachableShadowNodes, ReachableAllocNodes);
 271
 272     // Mark all nodes in the value map as being reachable...
 273     for (std::map<Value*, PointerValSet>::iterator I = ValueMap.begin(),
 274            E = ValueMap.end(); I != E; ++I)
 275       MarkReferredNodeSetReachable(I->second,
 276                                    ShadowNodes, ReachableShadowNodes,
 277                                    AllocNodes, ReachableAllocNodes);
 278
 279     // At this point, all reachable shadow nodes have a true value in the
 280     // Reachable vector.  This means that any shadow nodes without an entry in
 281     // the reachable vector are not reachable and should be removed.  This is
 282     // a two part process, because we must drop all references before we delete
 283     // the shadow nodes [in case cycles exist].
 284     //
 285     bool LocalChange = false;
 286     for (unsigned i = 0; i != ShadowNodes.size(); ++i)
 287       if (!ReachableShadowNodes[i]) {
 288         // Track all unreachable nodes...
 289 #if DEBUG_NODE_ELIMINATE
 290         cerr << "Unreachable node eliminated:\n";
 291         ShadowNodes[i]->print(cerr);
 292 #endif
 293         ShadowNodes[i]->removeAllIncomingEdges();
 294         delete ShadowNodes[i];
 295
 296         // Remove from reachable...
 297         ReachableShadowNodes.erase(ReachableShadowNodes.begin()+i);
 298         ShadowNodes.erase(ShadowNodes.begin()+i);   // Remove node entry
 299         --i;  // Don't skip the next node.
 300         LocalChange = true;
 301       }
 302
 303     for (unsigned i = 0; i != AllocNodes.size(); ++i)
 304       if (!ReachableAllocNodes[i]) {
 305         // Track all unreachable nodes...
 306 #if DEBUG_NODE_ELIMINATE
 307         cerr << "Unreachable node eliminated:\n";
 308         AllocNodes[i]->print(cerr);
 309 #endif
 310         AllocNodes[i]->removeAllIncomingEdges();
 311         delete AllocNodes[i];
 312
 313         // Remove from reachable...
 314         ReachableAllocNodes.erase(ReachableAllocNodes.begin()+i);
 315         AllocNodes.erase(AllocNodes.begin()+i);   // Remove node entry
 316         --i;  // Don't skip the next node.
 317         LocalChange = true;
 318       }
 319
 320     if (!LocalChange) return Changed;      // No more dead nodes...
 321
 322     Changed = true;
 323   }
 324 }
 325
 326
 327
 328
 329 // getEscapingAllocations - Add all allocations that escape the current
 330 // function to the specified vector.
 331 //
 332 void FunctionDSGraph::getEscapingAllocations(vector<AllocDSNode*> &Allocs) {
 333   vector<bool> ReachableShadowNodes(ShadowNodes.size());
 334   vector<bool> ReachableAllocNodes (AllocNodes.size());
 335
 336   MarkEscapeableNodesReachable(ReachableShadowNodes, ReachableAllocNodes);
 337
 338   for (unsigned i = 0, e = AllocNodes.size(); i != e; ++i)
 339     if (ReachableAllocNodes[i])
 340       Allocs.push_back(AllocNodes[i]);
 341 }
 342
 343 // getNonEscapingAllocations - Add all allocations that do not escape the
 344 // current function to the specified vector.
 345 //
 346 void FunctionDSGraph::getNonEscapingAllocations(vector<AllocDSNode*> &Allocs) {
 347   vector<bool> ReachableShadowNodes(ShadowNodes.size());
 348   vector<bool> ReachableAllocNodes (AllocNodes.size());
 349
 350   MarkEscapeableNodesReachable(ReachableShadowNodes, ReachableAllocNodes);
 351
 352   for (unsigned i = 0, e = AllocNodes.size(); i != e; ++i)
 353     if (!ReachableAllocNodes[i])
 354       Allocs.push_back(AllocNodes[i]);
 355 }