lib/Analysis/DataStructure/EliminateNodes.cpp

   1 //===- ShadowNodeEliminate.cpp - Optimize away shadow nodes ---------------===//
   2 //
   3 // This file contains two shadow node optimizations:
   4 //   1. UnlinkUndistinguishableShadowNodes - 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. RemoveUnreachableShadowNodes - Remove shadow nodes that are not
  11 //      reachable from some other node in the graph.  Unreachable shadow nodes
  12 //      are left lying around because other transforms don't go to the trouble
  13 //      or removing them, since this pass exists.
  14 //
  15 //===----------------------------------------------------------------------===//
  16
  17 #include "llvm/Analysis/DataStructure.h"
  18 #include "llvm/Value.h"
  19 #include "Support/STLExtras.h"
  20 #include <algorithm>
  21
  22 //#define DEBUG_NODE_ELIMINATE 1
  23
  24 bool AllocDSNode::isEquivalentTo(DSNode *Node) const {
  25   if (AllocDSNode *N = dyn_cast<AllocDSNode>(Node))
  26     return N->Allocation == Allocation;
  27   return false;
  28 }
  29
  30 bool GlobalDSNode::isEquivalentTo(DSNode *Node) const {
  31   if (GlobalDSNode *G = dyn_cast<GlobalDSNode>(Node))
  32     return G->Val == Val;
  33   return false;
  34 }
  35
  36 bool CallDSNode::isEquivalentTo(DSNode *Node) const {
  37   if (CallDSNode *C = dyn_cast<CallDSNode>(Node))
  38     return C->CI == CI && C->ArgLinks == ArgLinks;
  39   return false;
  40 }
  41
  42 bool ArgDSNode::isEquivalentTo(DSNode *Node) const {
  43   return false;
  44 }
  45
  46 // NodesAreEquivalent - Check to see if the nodes are equivalent in all ways
  47 // except node type.  Since we know N1 is a shadow node, N2 is allowed to be
  48 // any type.
  49 //
  50 bool ShadowDSNode::isEquivalentTo(DSNode *Node) const {
  51   return !isCriticalNode();              // Must not be a critical node...
  52 }
  53
  54
  55
  56 // isIndistinguishableNode - A node is indistinguishable if some other node
  57 // has exactly the same incoming links to it and if the node considers itself
  58 // to be the same as the other node...
  59 //
  60 bool isIndistinguishableNode(DSNode *DN) {
  61   if (DN->getReferrers().empty()) {       // No referrers...
  62     if (isa<ShadowDSNode>(DN) || isa<AllocDSNode>(DN))
  63       return true;  // Node is trivially dead
  64     else
  65       return false;
  66   }
  67
  68   // Pick a random referrer... Ptr is the things that the referrer points to.
  69   // Since DN is in the Ptr set, look through the set seeing if there are any
  70   // other nodes that are exactly equilivant to DN (with the exception of node
  71   // type), but are not DN.  If anything exists, then DN is indistinguishable.
  72   //
  73   const std::vector<PointerValSet*> &Refs = DN->getReferrers();
  74   for (unsigned R = 0, RE = Refs.size(); R != RE; ++R) {
  75     const PointerValSet &Ptr = *Refs[R];
  76
  77     for (unsigned i = 0, e = Ptr.size(); i != e; ++i) {
  78       DSNode *N2 = Ptr[i].Node;
  79       if (Ptr[i].Index == 0 && N2 != cast<DSNode>(DN) &&
  80           DN->getType() == N2->getType() && DN->isEquivalentTo(N2)) {
  81
  82         // Otherwise, the nodes can be merged.  Make sure that N2 contains all
  83         // of the  outgoing edges (fields) that DN does...
  84         //
  85         assert(DN->getNumLinks() == N2->getNumLinks() &&
  86                "Same type, diff # fields?");
  87         for (unsigned i = 0, e = DN->getNumLinks(); i != e; ++i)
  88           N2->getLink(i).add(DN->getLink(i));
  89
  90         // Now make sure that all of the nodes that point to the shadow node
  91         // also  point to the node that we are merging it with...
  92         //
  93         const std::vector<PointerValSet*> &Refs = DN->getReferrers();
  94         for (unsigned i = 0, e = Refs.size(); i != e; ++i) {
  95           PointerValSet &PVS = *Refs[i];
  96           // FIXME: this is incorrect if the referring pointer has index != 0
  97           //
  98           PVS.add(N2);
  99         }
 100         return true;
 101       }
 102     }
 103   }
 104
 105   // Otherwise, nothing found, perhaps next time....
 106   return false;
 107 }
 108
 109 template<typename NodeTy>
 110 bool removeIndistinguishableNode(std::vector<NodeTy*> &Nodes) {
 111   bool Changed = false;
 112   std::vector<NodeTy*>::iterator I = Nodes.begin();
 113   while (I != Nodes.end()) {
 114     if (isIndistinguishableNode(*I)) {
 115 #ifdef DEBUG_NODE_ELIMINATE
 116       cerr << "Found Indistinguishable Node:\n";
 117       (*I)->print(cerr);
 118 #endif
 119       (*I)->removeAllIncomingEdges();
 120       delete *I;
 121       I = Nodes.erase(I);
 122       Changed = true;
 123     } else {
 124       ++I;
 125     }
 126   }
 127   return Changed;
 128 }
 129
 130 // UnlinkUndistinguishableShadowNodes - Eliminate shadow nodes that are not
 131 // distinguishable from some other node in the graph...
 132 //
 133 bool FunctionDSGraph::UnlinkUndistinguishableShadowNodes() {
 134   // Loop over all of the shadow nodes, checking to see if they are
 135   // indistinguishable from some other node.  If so, eliminate the node!
 136   //
 137   return
 138     removeIndistinguishableNode(AllocNodes) |
 139     removeIndistinguishableNode(ShadowNodes) |
 140     removeIndistinguishableNode(GlobalNodes);
 141 }
 142
 143 static void MarkReferredNodesReachable(DSNode *N,
 144                                        vector<ShadowDSNode*> &ShadowNodes,
 145                                        vector<bool> &ReachableShadowNodes,
 146                                        vector<AllocDSNode*>  &AllocNodes,
 147                                        vector<bool> &ReachableAllocNodes);
 148
 149 static inline void MarkReferredNodeSetReachable(const PointerValSet &PVS,
 150                                             vector<ShadowDSNode*> &ShadowNodes,
 151                                             vector<bool> &ReachableShadowNodes,
 152                                             vector<AllocDSNode*>  &AllocNodes,
 153                                             vector<bool> &ReachableAllocNodes) {
 154   for (unsigned i = 0, e = PVS.size(); i != e; ++i)
 155     if (isa<ShadowDSNode>(PVS[i].Node) || isa<ShadowDSNode>(PVS[i].Node))
 156       MarkReferredNodesReachable(PVS[i].Node, ShadowNodes, ReachableShadowNodes,
 157                                  AllocNodes, ReachableAllocNodes);
 158 }
 159
 160 static void MarkReferredNodesReachable(DSNode *N,
 161                                        vector<ShadowDSNode*> &ShadowNodes,
 162                                        vector<bool> &ReachableShadowNodes,
 163                                        vector<AllocDSNode*>  &AllocNodes,
 164                                        vector<bool> &ReachableAllocNodes) {
 165   assert(ShadowNodes.size() == ReachableShadowNodes.size());
 166   assert(AllocNodes.size()  == ReachableAllocNodes.size());
 167
 168   if (ShadowDSNode *Shad = dyn_cast<ShadowDSNode>(N)) {
 169     vector<ShadowDSNode*>::iterator I =
 170       std::find(ShadowNodes.begin(), ShadowNodes.end(), Shad);
 171     unsigned i = I-ShadowNodes.begin();
 172     if (ReachableShadowNodes[i]) return;  // Recursion detected, abort...
 173     ReachableShadowNodes[i] = true;
 174   } else if (AllocDSNode *Alloc = dyn_cast<AllocDSNode>(N)) {
 175     vector<AllocDSNode*>::iterator I =
 176       std::find(AllocNodes.begin(), AllocNodes.end(), Alloc);
 177     unsigned i = I-AllocNodes.begin();
 178     if (ReachableAllocNodes[i]) return;  // Recursion detected, abort...
 179     ReachableAllocNodes[i] = true;
 180   }
 181
 182   for (unsigned i = 0, e = N->getNumLinks(); i != e; ++i)
 183     MarkReferredNodeSetReachable(N->getLink(i),
 184                                  ShadowNodes, ReachableShadowNodes,
 185                                  AllocNodes, ReachableAllocNodes);
 186
 187   const std::vector<PointerValSet> *Links = N->getAuxLinks();
 188   if (Links)
 189     for (unsigned i = 0, e = Links->size(); i != e; ++i)
 190       MarkReferredNodeSetReachable((*Links)[i],
 191                                    ShadowNodes, ReachableShadowNodes,
 192                                    AllocNodes, ReachableAllocNodes);
 193 }
 194
 195 bool FunctionDSGraph::RemoveUnreachableShadowNodes() {
 196   bool Changed = false;
 197   while (1) {
 198     // Reachable*Nodes - Contains true if there is an edge from a reachable
 199     // node to the numbered node...
 200     //
 201     vector<bool> ReachableShadowNodes(ShadowNodes.size());
 202     vector<bool> ReachableAllocNodes (AllocNodes.size());
 203
 204     // Mark all shadow nodes that have edges from other nodes as reachable.
 205     // Recursively mark any shadow nodes pointed to by the newly live shadow
 206     // nodes as also alive.
 207     //
 208     for (unsigned i = 0, e = ArgNodes.size(); i != e; ++i)
 209       MarkReferredNodesReachable(ArgNodes[i],
 210                                  ShadowNodes, ReachableShadowNodes,
 211                                  AllocNodes, ReachableAllocNodes);
 212
 213     for (unsigned i = 0, e = GlobalNodes.size(); i != e; ++i)
 214       MarkReferredNodesReachable(GlobalNodes[i],
 215                                  ShadowNodes, ReachableShadowNodes,
 216                                  AllocNodes, ReachableAllocNodes);
 217
 218     for (unsigned i = 0, e = CallNodes.size(); i != e; ++i)
 219       MarkReferredNodesReachable(CallNodes[i],
 220                                  ShadowNodes, ReachableShadowNodes,
 221                                  AllocNodes, ReachableAllocNodes);
 222
 223     // Mark all nodes in the return set as being reachable...
 224     MarkReferredNodeSetReachable(RetNode,
 225                                  ShadowNodes, ReachableShadowNodes,
 226                                  AllocNodes, ReachableAllocNodes);
 227
 228     // Mark all nodes in the value map as being reachable...
 229     for (std::map<Value*, PointerValSet>::iterator I = ValueMap.begin(),
 230            E = ValueMap.end(); I != E; ++I)
 231       MarkReferredNodeSetReachable(I->second,
 232                                    ShadowNodes, ReachableShadowNodes,
 233                                    AllocNodes, ReachableAllocNodes);
 234
 235     // At this point, all reachable shadow nodes have a true value in the
 236     // Reachable vector.  This means that any shadow nodes without an entry in
 237     // the reachable vector are not reachable and should be removed.  This is
 238     // a two part process, because we must drop all references before we delete
 239     // the shadow nodes [in case cycles exist].
 240     //
 241     bool LocalChange = false;
 242     for (unsigned i = 0; i != ShadowNodes.size(); ++i)
 243       if (!ReachableShadowNodes[i]) {
 244         // Track all unreachable nodes...
 245 #if DEBUG_NODE_ELIMINATE
 246         cerr << "Unreachable node eliminated:\n";
 247         ShadowNodes[i]->print(cerr);
 248 #endif
 249         ShadowNodes[i]->removeAllIncomingEdges();
 250         delete ShadowNodes[i];
 251
 252         // Remove from reachable...
 253         ReachableShadowNodes.erase(ReachableShadowNodes.begin()+i);
 254         ShadowNodes.erase(ShadowNodes.begin()+i);   // Remove node entry
 255         --i;  // Don't skip the next node.
 256         LocalChange = true;
 257       }
 258
 259     for (unsigned i = 0; i != AllocNodes.size(); ++i)
 260       if (!ReachableAllocNodes[i]) {
 261         // Track all unreachable nodes...
 262 #if DEBUG_NODE_ELIMINATE
 263         cerr << "Unreachable node eliminated:\n";
 264         AllocNodes[i]->print(cerr);
 265 #endif
 266         AllocNodes[i]->removeAllIncomingEdges();
 267         delete AllocNodes[i];
 268
 269         // Remove from reachable...
 270         ReachableAllocNodes.erase(ReachableAllocNodes.begin()+i);
 271         AllocNodes.erase(AllocNodes.begin()+i);   // Remove node entry
 272         --i;  // Don't skip the next node.
 273         LocalChange = true;
 274       }
 275
 276     if (!LocalChange) return Changed;      // No more dead nodes...
 277
 278     Changed = true;
 279   }
 280 }