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->mergeInto(N2);
  57   N1->removeAllIncomingEdges();
  58   delete N1;
  59 }
  60
  61 // isIndistinguishableNode - A node is indistinguishable if some other node
  62 // has exactly the same incoming links to it and if the node considers itself
  63 // to be the same as the other node...
  64 //
  65 static bool isIndistinguishableNode(DSNode *DN) {
  66   if (DN->getReferrers().empty()) {       // No referrers...
  67     if (isa<ShadowDSNode>(DN) || isa<AllocDSNode>(DN)) {
  68       delete DN;
  69       return true;  // Node is trivially dead
  70     } else
  71       return false;
  72   }
  73
  74   // Pick a random referrer... Ptr is the things that the referrer points to.
  75   // Since DN is in the Ptr set, look through the set seeing if there are any
  76   // other nodes that are exactly equilivant to DN (with the exception of node
  77   // type), but are not DN.  If anything exists, then DN is indistinguishable.
  78   //
  79
  80   DSNode *IndFrom = 0;
  81   const std::vector<PointerValSet*> &Refs = DN->getReferrers();
  82   for (unsigned R = 0, RE = Refs.size(); R != RE; ++R) {
  83     const PointerValSet &Ptr = *Refs[R];
  84
  85     for (unsigned i = 0, e = Ptr.size(); i != e; ++i) {
  86       DSNode *N2 = Ptr[i].Node;
  87       if (Ptr[i].Index == 0 && N2 != cast<DSNode>(DN) &&
  88           DN->getType() == N2->getType() && DN->isEquivalentTo(N2)) {
  89
  90         IndFrom = N2;
  91         R = RE-1;
  92         break;
  93       }
  94     }
  95   }
  96
  97   // If we haven't found an equivalent node to merge with, see if one of the
  98   // nodes pointed to by this node is equivalent to this one...
  99   //
 100   if (IndFrom == 0) {
 101     unsigned NumOutgoing = DN->getNumOutgoingLinks();
 102     for (DSNode::iterator I = DN->begin(), E = DN->end(); I != E; ++I) {
 103       DSNode *Linked = *I;
 104       if (Linked != DN && Linked->getNumOutgoingLinks() == NumOutgoing &&
 105           DN->getType() == Linked->getType() && DN->isEquivalentTo(Linked)) {
 106 #if 0
 107         // Make sure the leftover node contains links to everything we do...
 108         for (unsigned i = 0, e = DN->getNumLinks(); i != e; ++i)
 109           Linked->getLink(i).add(DN->getLink(i));
 110 #endif
 111
 112         IndFrom = Linked;
 113         break;
 114       }
 115     }
 116   }
 117
 118
 119   // If DN is indistinguishable from some other node, merge them now...
 120   if (IndFrom == 0)
 121     return false;     // Otherwise, nothing found, perhaps next time....
 122
 123   DestroyFirstNodeOfPair(DN, IndFrom);
 124   return true;
 125 }
 126
 127 template<typename NodeTy>
 128 static bool removeIndistinguishableNodes(std::vector<NodeTy*> &Nodes) {
 129   bool Changed = false;
 130   std::vector<NodeTy*>::iterator I = Nodes.begin();
 131   while (I != Nodes.end()) {
 132     if (isIndistinguishableNode(*I)) {
 133       I = Nodes.erase(I);
 134       Changed = true;
 135     } else {
 136       ++I;
 137     }
 138   }
 139   return Changed;
 140 }
 141
 142 template<typename NodeTy>
 143 static bool removeIndistinguishableNodePairs(std::vector<NodeTy*> &Nodes) {
 144   bool Changed = false;
 145   std::vector<NodeTy*>::iterator I = Nodes.begin();
 146   while (I != Nodes.end()) {
 147     NodeTy *N1 = *I++;
 148     for (std::vector<NodeTy*>::iterator I2 = I, I2E = Nodes.end();
 149          I2 != I2E; ++I2) {
 150       NodeTy *N2 = *I2;
 151       if (N1->isEquivalentTo(N2)) {
 152         DestroyFirstNodeOfPair(N1, N2);
 153         --I;
 154         I = Nodes.erase(I);
 155         Changed = true;
 156         break;
 157       }
 158     }
 159   }
 160   return Changed;
 161 }
 162
 163
 164
 165 // UnlinkUndistinguishableNodes - Eliminate shadow nodes that are not
 166 // distinguishable from some other node in the graph...
 167 //
 168 bool FunctionDSGraph::UnlinkUndistinguishableNodes() {
 169   // Loop over all of the shadow nodes, checking to see if they are
 170   // indistinguishable from some other node.  If so, eliminate the node!
 171   //
 172   return
 173     removeIndistinguishableNodes(AllocNodes) |
 174     removeIndistinguishableNodes(ShadowNodes) |
 175     removeIndistinguishableNodePairs(CallNodes) |
 176     removeIndistinguishableNodePairs(GlobalNodes);
 177 }
 178
 179 static void MarkReferredNodesReachable(DSNode *N,
 180                                        vector<ShadowDSNode*> &ShadowNodes,
 181                                        vector<bool> &ReachableShadowNodes,
 182                                        vector<AllocDSNode*>  &AllocNodes,
 183                                        vector<bool> &ReachableAllocNodes);
 184
 185 static inline void MarkReferredNodeSetReachable(const PointerValSet &PVS,
 186                                             vector<ShadowDSNode*> &ShadowNodes,
 187                                             vector<bool> &ReachableShadowNodes,
 188                                             vector<AllocDSNode*>  &AllocNodes,
 189                                             vector<bool> &ReachableAllocNodes) {
 190   for (unsigned i = 0, e = PVS.size(); i != e; ++i)
 191     if (isa<ShadowDSNode>(PVS[i].Node) || isa<AllocDSNode>(PVS[i].Node))
 192       MarkReferredNodesReachable(PVS[i].Node, ShadowNodes, ReachableShadowNodes,
 193                                  AllocNodes, ReachableAllocNodes);
 194 }
 195
 196 static void MarkReferredNodesReachable(DSNode *N,
 197                                        vector<ShadowDSNode*> &ShadowNodes,
 198                                        vector<bool> &ReachableShadowNodes,
 199                                        vector<AllocDSNode*>  &AllocNodes,
 200                                        vector<bool> &ReachableAllocNodes) {
 201   assert(ShadowNodes.size() == ReachableShadowNodes.size());
 202   assert(AllocNodes.size()  == ReachableAllocNodes.size());
 203
 204   if (ShadowDSNode *Shad = dyn_cast<ShadowDSNode>(N)) {
 205     vector<ShadowDSNode*>::iterator I =
 206       std::find(ShadowNodes.begin(), ShadowNodes.end(), Shad);
 207     unsigned i = I-ShadowNodes.begin();
 208     if (ReachableShadowNodes[i]) return;  // Recursion detected, abort...
 209     ReachableShadowNodes[i] = true;
 210   } else if (AllocDSNode *Alloc = dyn_cast<AllocDSNode>(N)) {
 211     vector<AllocDSNode*>::iterator I =
 212       std::find(AllocNodes.begin(), AllocNodes.end(), Alloc);
 213     unsigned i = I-AllocNodes.begin();
 214     if (ReachableAllocNodes[i]) return;  // Recursion detected, abort...
 215     ReachableAllocNodes[i] = true;
 216   }
 217
 218   for (unsigned i = 0, e = N->getNumLinks(); i != e; ++i)
 219     MarkReferredNodeSetReachable(N->getLink(i),
 220                                  ShadowNodes, ReachableShadowNodes,
 221                                  AllocNodes, ReachableAllocNodes);
 222
 223   const std::vector<PointerValSet> *Links = N->getAuxLinks();
 224   if (Links)
 225     for (unsigned i = 0, e = Links->size(); i != e; ++i)
 226       MarkReferredNodeSetReachable((*Links)[i],
 227                                    ShadowNodes, ReachableShadowNodes,
 228                                    AllocNodes, ReachableAllocNodes);
 229 }
 230
 231 void FunctionDSGraph::MarkEscapeableNodesReachable(
 232                                        vector<bool> &ReachableShadowNodes,
 233                                        vector<bool> &ReachableAllocNodes) {
 234   // Mark all shadow nodes that have edges from other nodes as reachable.
 235   // Recursively mark any shadow nodes pointed to by the newly live shadow
 236   // nodes as also alive.
 237   //
 238   for (unsigned i = 0, e = GlobalNodes.size(); i != e; ++i)
 239     MarkReferredNodesReachable(GlobalNodes[i],
 240                                ShadowNodes, ReachableShadowNodes,
 241                                AllocNodes, ReachableAllocNodes);
 242
 243   for (unsigned i = 0, e = CallNodes.size(); i != e; ++i)
 244     MarkReferredNodesReachable(CallNodes[i],
 245                                ShadowNodes, ReachableShadowNodes,
 246                                AllocNodes, ReachableAllocNodes);
 247
 248   // Mark all nodes in the return set as being reachable...
 249   MarkReferredNodeSetReachable(RetNode,
 250                                ShadowNodes, ReachableShadowNodes,
 251                                AllocNodes, ReachableAllocNodes);
 252 }
 253
 254 bool FunctionDSGraph::RemoveUnreachableNodes() {
 255   bool Changed = false;
 256   bool LocalChange = true;
 257
 258   while (LocalChange) {
 259     LocalChange = false;
 260     // Reachable*Nodes - Contains true if there is an edge from a reachable
 261     // node to the numbered node...
 262     //
 263     vector<bool> ReachableShadowNodes(ShadowNodes.size());
 264     vector<bool> ReachableAllocNodes (AllocNodes.size());
 265
 266     MarkEscapeableNodesReachable(ReachableShadowNodes, ReachableAllocNodes);
 267
 268     // Mark all nodes in the value map as being reachable...
 269     for (std::map<Value*, PointerValSet>::iterator I = ValueMap.begin(),
 270            E = ValueMap.end(); I != E; ++I)
 271       MarkReferredNodeSetReachable(I->second,
 272                                    ShadowNodes, ReachableShadowNodes,
 273                                    AllocNodes, ReachableAllocNodes);
 274
 275     // At this point, all reachable shadow nodes have a true value in the
 276     // Reachable vector.  This means that any shadow nodes without an entry in
 277     // the reachable vector are not reachable and should be removed.  This is
 278     // a two part process, because we must drop all references before we delete
 279     // the shadow nodes [in case cycles exist].
 280     //
 281     for (unsigned i = 0; i != ShadowNodes.size(); ++i)
 282       if (!ReachableShadowNodes[i]) {
 283         // Track all unreachable nodes...
 284 #if DEBUG_NODE_ELIMINATE
 285         cerr << "Unreachable node eliminated:\n";
 286         ShadowNodes[i]->print(cerr);
 287 #endif
 288         ShadowNodes[i]->removeAllIncomingEdges();
 289         delete ShadowNodes[i];
 290
 291         // Remove from reachable...
 292         ReachableShadowNodes.erase(ReachableShadowNodes.begin()+i);
 293         ShadowNodes.erase(ShadowNodes.begin()+i);   // Remove node entry
 294         --i;  // Don't skip the next node.
 295         LocalChange = Changed = true;
 296       }
 297
 298     for (unsigned i = 0; i != AllocNodes.size(); ++i)
 299       if (!ReachableAllocNodes[i]) {
 300         // Track all unreachable nodes...
 301 #if DEBUG_NODE_ELIMINATE
 302         cerr << "Unreachable node eliminated:\n";
 303         AllocNodes[i]->print(cerr);
 304 #endif
 305         AllocNodes[i]->removeAllIncomingEdges();
 306         delete AllocNodes[i];
 307
 308         // Remove from reachable...
 309         ReachableAllocNodes.erase(ReachableAllocNodes.begin()+i);
 310         AllocNodes.erase(AllocNodes.begin()+i);   // Remove node entry
 311         --i;  // Don't skip the next node.
 312         LocalChange = Changed = true;
 313       }
 314   }
 315
 316   // Loop over the global nodes, removing nodes that have no edges into them or
 317   // out of them.
 318   //
 319   for (std::vector<GlobalDSNode*>::iterator I = GlobalNodes.begin();
 320        I != GlobalNodes.end(); )
 321     if ((*I)->getReferrers().empty()) {
 322       GlobalDSNode *GDN = *I;
 323       bool NoLinks = true;    // Make sure there are no outgoing links...
 324       for (unsigned i = 0, e = GDN->getNumLinks(); i != e; ++i)
 325         if (!GDN->getLink(i).empty()) {
 326           NoLinks = false;
 327           break;
 328         }
 329       if (NoLinks) {
 330         delete GDN;
 331         I = GlobalNodes.erase(I);                     // Remove the node...
 332         Changed = true;
 333       } else {
 334         ++I;
 335       }
 336     } else {
 337       ++I;
 338     }
 339
 340   return Changed;
 341 }
 342
 343
 344
 345
 346 // getEscapingAllocations - Add all allocations that escape the current
 347 // function to the specified vector.
 348 //
 349 void FunctionDSGraph::getEscapingAllocations(vector<AllocDSNode*> &Allocs) {
 350   vector<bool> ReachableShadowNodes(ShadowNodes.size());
 351   vector<bool> ReachableAllocNodes (AllocNodes.size());
 352
 353   MarkEscapeableNodesReachable(ReachableShadowNodes, ReachableAllocNodes);
 354
 355   for (unsigned i = 0, e = AllocNodes.size(); i != e; ++i)
 356     if (ReachableAllocNodes[i])
 357       Allocs.push_back(AllocNodes[i]);
 358 }
 359
 360 // getNonEscapingAllocations - Add all allocations that do not escape the
 361 // current function to the specified vector.
 362 //
 363 void FunctionDSGraph::getNonEscapingAllocations(vector<AllocDSNode*> &Allocs) {
 364   vector<bool> ReachableShadowNodes(ShadowNodes.size());
 365   vector<bool> ReachableAllocNodes (AllocNodes.size());
 366
 367   MarkEscapeableNodesReachable(ReachableShadowNodes, ReachableAllocNodes);
 368
 369   for (unsigned i = 0, e = AllocNodes.size(); i != e; ++i)
 370     if (!ReachableAllocNodes[i])
 371       Allocs.push_back(AllocNodes[i]);
 372 }