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
  26 // isIndistinguishableNode - A node is indistinguishable if some other node
  27 // has exactly the same incoming links to it and if the node considers itself
  28 // to be the same as the other node...
  29 //
  30 static bool isIndistinguishableNode(DSNode *DN) {
  31   if (DN->getReferrers().empty()) {       // No referrers...
  32     if (isa<ShadowDSNode>(DN) || isa<AllocDSNode>(DN))
  33       return true;  // Node is trivially dead
  34     else
  35       return false;
  36   }
  37
  38   // Pick a random referrer... Ptr is the things that the referrer points to.
  39   // Since DN is in the Ptr set, look through the set seeing if there are any
  40   // other nodes that are exactly equilivant to DN (with the exception of node
  41   // type), but are not DN.  If anything exists, then DN is indistinguishable.
  42   //
  43
  44   DSNode *IndFrom = 0;
  45   const std::vector<PointerValSet*> &Refs = DN->getReferrers();
  46   for (unsigned R = 0, RE = Refs.size(); R != RE; ++R) {
  47     const PointerValSet &Ptr = *Refs[R];
  48
  49     for (unsigned i = 0, e = Ptr.size(); i != e; ++i) {
  50       DSNode *N2 = Ptr[i].Node;
  51       if (Ptr[i].Index == 0 && N2 != cast<DSNode>(DN) &&
  52           DN->getType() == N2->getType() && DN->isEquivalentTo(N2)) {
  53
  54         IndFrom = N2;
  55         R = RE-1;
  56         break;
  57       }
  58     }
  59   }
  60
  61   // If we haven't found an equivalent node to merge with, see if one of the
  62   // nodes pointed to by this node is equivalent to this one...
  63   //
  64   if (IndFrom == 0) {
  65     unsigned NumOutgoing = DN->getNumOutgoingLinks();
  66     for (DSNode::iterator I = DN->begin(), E = DN->end(); I != E; ++I) {
  67       DSNode *Linked = *I;
  68       if (Linked != DN && Linked->getNumOutgoingLinks() == NumOutgoing &&
  69           DN->getType() == Linked->getType() && DN->isEquivalentTo(Linked)) {
  70 #if 0
  71         // Make sure the leftover node contains links to everything we do...
  72         for (unsigned i = 0, e = DN->getNumLinks(); i != e; ++i)
  73           Linked->getLink(i).add(DN->getLink(i));
  74 #endif
  75
  76         IndFrom = Linked;
  77         break;
  78       }
  79     }
  80   }
  81
  82
  83   // If DN is indistinguishable from some other node, merge them now...
  84   if (IndFrom == 0)
  85     return false;     // Otherwise, nothing found, perhaps next time....
  86
  87   // The nodes can be merged.  Make sure that IndFrom contains all of the
  88   // outgoing edges (fields) that DN does...
  89   //
  90   assert(DN->getNumLinks() == IndFrom->getNumLinks() &&
  91          "Same type, diff # fields?");
  92   for (unsigned i = 0, e = DN->getNumLinks(); i != e; ++i)
  93     IndFrom->getLink(i).add(DN->getLink(i));
  94
  95   // Now make sure that all of the nodes that point to the shadow node also
  96   // point to the node that we are merging it with...
  97   //
  98   for (unsigned i = 0, e = Refs.size(); i != e; ++i) {
  99     PointerValSet &PVS = *Refs[i];
 100
 101     bool RanOnce = false;
 102     for (unsigned j = 0, je = PVS.size(); j != je; ++j)
 103       if (PVS[j].Node == DN) {
 104         RanOnce = true;
 105         PVS.add(PointerVal(IndFrom, PVS[j].Index));
 106       }
 107
 108     assert(RanOnce && "Node on user set but cannot find the use!");
 109   }
 110   return true;
 111 }
 112
 113 template<typename NodeTy>
 114 static bool removeIndistinguishableNodes(std::vector<NodeTy*> &Nodes) {
 115   bool Changed = false;
 116   std::vector<NodeTy*>::iterator I = Nodes.begin();
 117   while (I != Nodes.end()) {
 118     if (isIndistinguishableNode(*I)) {
 119 #ifdef DEBUG_NODE_ELIMINATE
 120       cerr << "Found Indistinguishable Node:\n";
 121       (*I)->print(cerr);
 122 #endif
 123       (*I)->removeAllIncomingEdges();
 124       delete *I;
 125       I = Nodes.erase(I);
 126       Changed = true;
 127     } else {
 128       ++I;
 129     }
 130   }
 131   return Changed;
 132 }
 133
 134 template<typename NodeTy>
 135 static bool removeIndistinguishableNodePairs(std::vector<NodeTy*> &Nodes) {
 136   bool Changed = false;
 137   std::vector<NodeTy*>::iterator I = Nodes.begin();
 138   while (I != Nodes.end()) {
 139     NodeTy *N1 = *I++;
 140     for (std::vector<NodeTy*>::iterator I2 = I, I2E = Nodes.end();
 141          I2 != I2E; ++I2) {
 142       NodeTy *N2 = *I2;
 143       if (N1->isEquivalentTo(N2)) {
 144 #ifdef DEBUG_NODE_ELIMINATE
 145         cerr << "Found Indistinguishable Node:\n";
 146         N1->print(cerr);
 147 #endif
 148         N1->removeAllIncomingEdges();
 149         delete N1;
 150         --I;
 151         I = Nodes.erase(I);
 152         Changed = true;
 153         break;
 154       }
 155     }
 156   }
 157   return Changed;
 158 }
 159
 160
 161
 162 // UnlinkUndistinguishableNodes - Eliminate shadow nodes that are not
 163 // distinguishable from some other node in the graph...
 164 //
 165 bool FunctionDSGraph::UnlinkUndistinguishableNodes() {
 166   // Loop over all of the shadow nodes, checking to see if they are
 167   // indistinguishable from some other node.  If so, eliminate the node!
 168   //
 169   return
 170     removeIndistinguishableNodes(AllocNodes) |
 171     removeIndistinguishableNodes(ShadowNodes) |
 172     //FIXME: We cannot naively remove call nodes here because if there is a
 173     // shadow node that is the result of the call, we have to make sure to
 174     // merge the shadow node as well!!!
 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 = ArgNodes.size(); i != e; ++i)
 239     MarkReferredNodesReachable(ArgNodes[i],
 240                                ShadowNodes, ReachableShadowNodes,
 241                                AllocNodes, ReachableAllocNodes);
 242
 243   for (unsigned i = 0, e = GlobalNodes.size(); i != e; ++i)
 244     MarkReferredNodesReachable(GlobalNodes[i],
 245                                ShadowNodes, ReachableShadowNodes,
 246                                AllocNodes, ReachableAllocNodes);
 247
 248   for (unsigned i = 0, e = CallNodes.size(); i != e; ++i)
 249     MarkReferredNodesReachable(CallNodes[i],
 250                                ShadowNodes, ReachableShadowNodes,
 251                                AllocNodes, ReachableAllocNodes);
 252
 253   // Mark all nodes in the return set as being reachable...
 254   MarkReferredNodeSetReachable(RetNode,
 255                                ShadowNodes, ReachableShadowNodes,
 256                                AllocNodes, ReachableAllocNodes);
 257 }
 258
 259 bool FunctionDSGraph::RemoveUnreachableNodes() {
 260   bool Changed = false;
 261
 262   while (1) {
 263     // Reachable*Nodes - Contains true if there is an edge from a reachable
 264     // node to the numbered node...
 265     //
 266     vector<bool> ReachableShadowNodes(ShadowNodes.size());
 267     vector<bool> ReachableAllocNodes (AllocNodes.size());
 268
 269     MarkEscapeableNodesReachable(ReachableShadowNodes, ReachableAllocNodes);
 270
 271     // Mark all nodes in the value map as being reachable...
 272     for (std::map<Value*, PointerValSet>::iterator I = ValueMap.begin(),
 273            E = ValueMap.end(); I != E; ++I)
 274       MarkReferredNodeSetReachable(I->second,
 275                                    ShadowNodes, ReachableShadowNodes,
 276                                    AllocNodes, ReachableAllocNodes);
 277
 278     // At this point, all reachable shadow nodes have a true value in the
 279     // Reachable vector.  This means that any shadow nodes without an entry in
 280     // the reachable vector are not reachable and should be removed.  This is
 281     // a two part process, because we must drop all references before we delete
 282     // the shadow nodes [in case cycles exist].
 283     //
 284     bool LocalChange = false;
 285     for (unsigned i = 0; i != ShadowNodes.size(); ++i)
 286       if (!ReachableShadowNodes[i]) {
 287         // Track all unreachable nodes...
 288 #if DEBUG_NODE_ELIMINATE
 289         cerr << "Unreachable node eliminated:\n";
 290         ShadowNodes[i]->print(cerr);
 291 #endif
 292         ShadowNodes[i]->removeAllIncomingEdges();
 293         delete ShadowNodes[i];
 294
 295         // Remove from reachable...
 296         ReachableShadowNodes.erase(ReachableShadowNodes.begin()+i);
 297         ShadowNodes.erase(ShadowNodes.begin()+i);   // Remove node entry
 298         --i;  // Don't skip the next node.
 299         LocalChange = true;
 300       }
 301
 302     for (unsigned i = 0; i != AllocNodes.size(); ++i)
 303       if (!ReachableAllocNodes[i]) {
 304         // Track all unreachable nodes...
 305 #if DEBUG_NODE_ELIMINATE
 306         cerr << "Unreachable node eliminated:\n";
 307         AllocNodes[i]->print(cerr);
 308 #endif
 309         AllocNodes[i]->removeAllIncomingEdges();
 310         delete AllocNodes[i];
 311
 312         // Remove from reachable...
 313         ReachableAllocNodes.erase(ReachableAllocNodes.begin()+i);
 314         AllocNodes.erase(AllocNodes.begin()+i);   // Remove node entry
 315         --i;  // Don't skip the next node.
 316         LocalChange = true;
 317       }
 318
 319     if (!LocalChange) return Changed;      // No more dead nodes...
 320
 321     Changed = true;
 322   }
 323 }
 324
 325
 326
 327
 328 // getEscapingAllocations - Add all allocations that escape the current
 329 // function to the specified vector.
 330 //
 331 void FunctionDSGraph::getEscapingAllocations(vector<AllocDSNode*> &Allocs) {
 332   vector<bool> ReachableShadowNodes(ShadowNodes.size());
 333   vector<bool> ReachableAllocNodes (AllocNodes.size());
 334
 335   MarkEscapeableNodesReachable(ReachableShadowNodes, ReachableAllocNodes);
 336
 337   for (unsigned i = 0, e = AllocNodes.size(); i != e; ++i)
 338     if (ReachableAllocNodes[i])
 339       Allocs.push_back(AllocNodes[i]);
 340 }
 341
 342 // getNonEscapingAllocations - Add all allocations that do not escape the
 343 // current function to the specified vector.
 344 //
 345 void FunctionDSGraph::getNonEscapingAllocations(vector<AllocDSNode*> &Allocs) {
 346   vector<bool> ReachableShadowNodes(ShadowNodes.size());
 347   vector<bool> ReachableAllocNodes (AllocNodes.size());
 348
 349   MarkEscapeableNodesReachable(ReachableShadowNodes, ReachableAllocNodes);
 350
 351   for (unsigned i = 0, e = AllocNodes.size(); i != e; ++i)
 352     if (!ReachableAllocNodes[i])
 353       Allocs.push_back(AllocNodes[i]);
 354 }