lib/Analysis/DataStructure/ComputeClosure.cpp

   1 //===- ComputeClosure.cpp - Implement interprocedural closing of graphs ---===//
   2 //
   3 // Compute the interprocedural closure of a data structure graph
   4 //
   5 //===----------------------------------------------------------------------===//
   6
   7 // DEBUG_IP_CLOSURE - Define this to debug the act of linking up graphs
   8 //#define DEBUG_IP_CLOSURE 1
   9
  10 #include "llvm/Analysis/DataStructure.h"
  11 #include "llvm/Function.h"
  12 #include "llvm/iOther.h"
  13 #include "Support/STLExtras.h"
  14 #include <algorithm>
  15
  16 // Make all of the pointers that point to Val also point to N.
  17 //
  18 static void copyEdgesFromTo(PointerVal Val, DSNode *N) {
  19   unsigned ValIdx = Val.Index;
  20   unsigned NLinks = N->getNumLinks();
  21
  22   const vector<PointerValSet*> &PVSsToUpdate(Val.Node->getReferrers());
  23   for (unsigned i = 0, e = PVSsToUpdate.size(); i != e; ++i) {
  24     // Loop over all of the pointers pointing to Val...
  25     PointerValSet &PVS = *PVSsToUpdate[i];
  26     for (unsigned j = 0, je = PVS.size(); j != je; ++j) {
  27       if (PVS[j].Node == Val.Node && PVS[j].Index >= ValIdx &&
  28           PVS[j].Index < ValIdx+NLinks)
  29         PVS.add(PointerVal(N, PVS[j].Index-ValIdx));
  30     }
  31   }
  32 }
  33
  34 static void ResolveNodesTo(const PointerValSet &FromVals,
  35                            const PointerValSet &ToVals) {
  36   // Only resolve the first pointer, although there many be many pointers here.
  37   // The problem is that the inlined function might return one of the arguments
  38   // to the function, and if so, extra values can be added to the arg or call
  39   // node that point to what the other one got resolved to.  Since these will
  40   // be added to the end of the PVS pointed in, we just ignore them.
  41   //
  42   assert(!FromVals.empty() && "From should have at least a shadow node!");
  43   const PointerVal &FromPtr = FromVals[0];
  44
  45   assert(FromPtr.Index == 0 &&
  46          "Resolved node return pointer should be index 0!");
  47   DSNode *N = FromPtr.Node;
  48
  49   // Make everything that pointed to the shadow node also point to the values in
  50   // ToVals...
  51   //
  52   for (unsigned i = 0, e = ToVals.size(); i != e; ++i)
  53     copyEdgesFromTo(ToVals[i], N);
  54
  55   // Make everything that pointed to the shadow node now also point to the
  56   // values it is equivalent to...
  57   const vector<PointerValSet*> &PVSToUpdate(N->getReferrers());
  58   for (unsigned i = 0, e = PVSToUpdate.size(); i != e; ++i)
  59     PVSToUpdate[i]->add(ToVals);
  60 }
  61
  62
  63 // ResolveNodeTo - The specified node is now known to point to the set of values
  64 // in ToVals, instead of the old shadow node subgraph that it was pointing to.
  65 //
  66 static void ResolveNodeTo(DSNode *Node, const PointerValSet &ToVals) {
  67   assert(Node->getNumLinks() == 1 && "Resolved node can only be a scalar!!");
  68
  69   const PointerValSet &PVS = Node->getLink(0);
  70   ResolveNodesTo(PVS, ToVals);
  71 }
  72
  73 // isResolvableCallNode - Return true if node is a call node and it is a call
  74 // node that we can inline...
  75 //
  76 static bool isResolvableCallNode(CallDSNode *CN) {
  77   // Only operate on call nodes with direct function calls
  78   if (CN->getArgValues(0).size() == 1 &&
  79       isa<GlobalDSNode>(CN->getArgValues(0)[0].Node)) {
  80     GlobalDSNode *GDN = cast<GlobalDSNode>(CN->getArgValues(0)[0].Node);
  81     Function *F = cast<Function>(GDN->getGlobal());
  82
  83     // Only work on call nodes with direct calls to methods with bodies.
  84     return !F->isExternal();
  85   }
  86   return false;
  87 }
  88
  89 #include "Support/CommandLine.h"
  90 static cl::Int InlineLimit("dsinlinelimit", "Max number of graphs to inline when computing ds closure", cl::Hidden, 100);
  91
  92 // computeClosure - Replace all of the resolvable call nodes with the contents
  93 // of their corresponding method data structure graph...
  94 //
  95 void FunctionDSGraph::computeClosure(const DataStructure &DS) {
  96   // Note that this cannot be a real vector because the keys will be changing
  97   // as nodes are eliminated!
  98   //
  99   typedef pair<vector<PointerValSet>, CallInst *> CallDescriptor;
 100   vector<pair<CallDescriptor, PointerValSet> > CallMap;
 101
 102   unsigned NumInlines = 0;
 103
 104   // Loop over the resolvable call nodes...
 105   vector<CallDSNode*>::iterator NI;
 106   NI = std::find_if(CallNodes.begin(), CallNodes.end(), isResolvableCallNode);
 107   while (NI != CallNodes.end()) {
 108     CallDSNode *CN = *NI;
 109     GlobalDSNode *FGDN = cast<GlobalDSNode>(CN->getArgValues(0)[0].Node);
 110     Function *F = cast<Function>(FGDN->getGlobal());
 111
 112     if ((int)NumInlines++ == InlineLimit) {      // CUTE hack huh?
 113       cerr << "Infinite (?) recursion halted\n";
 114       cerr << "Not inlining: " << F->getName() << "\n";
 115       CN->dump();
 116
 117       return;
 118     }
 119
 120     CallNodes.erase(NI);                 // Remove the call node from the graph
 121
 122     unsigned CallNodeOffset = NI-CallNodes.begin();
 123
 124     // Find out if we have already incorporated this node... if so, it will be
 125     // in the CallMap...
 126     //
 127
 128 #if 0
 129     cerr << "\nSearching for: " << (void*)CN->getCall() << ": ";
 130     for (unsigned X = 0; X != CN->getArgs().size(); ++X) {
 131       cerr << " " << X << " is\n";
 132       CN->getArgs().first[X].print(cerr);
 133     }
 134 #endif
 135
 136     const vector<PointerValSet> &Args = CN->getArgs();
 137     PointerValSet *CMI = 0;
 138     for (unsigned i = 0, e = CallMap.size(); i != e; ++i) {
 139 #if 0
 140       cerr << "Found: " << (void*)CallMap[i].first.second << ": ";
 141       for (unsigned X = 0; X != CallMap[i].first.first.size(); ++X) {
 142         cerr << " " << X << " is\n"; CallMap[i].first.first[X].print(cerr);
 143       }
 144 #endif
 145
 146       // Look to see if the function call takes a superset of the values we are
 147       // providing as input
 148       //
 149       CallDescriptor &CD = CallMap[i].first;
 150       if (CD.second == CN->getCall() && CD.first.size() == Args.size()) {
 151         bool FoundMismatch = false;
 152         for (unsigned j = 0, je = Args.size(); j != je; ++j) {
 153           PointerValSet ArgSet = CD.first[j];
 154           if (ArgSet.add(Args[j])) {
 155             FoundMismatch = true; break;
 156           }
 157         }
 158
 159         if (!FoundMismatch) { CMI = &CallMap[i].second; break; }
 160       }
 161     }
 162
 163     // Hold the set of values that correspond to the incorporated methods
 164     // return set.
 165     //
 166     PointerValSet RetVals;
 167
 168     if (CMI) {
 169       // We have already inlined an identical function call!
 170       RetVals = *CMI;
 171     } else {
 172       // Get the datastructure graph for the new method.  Note that we are not
 173       // allowed to modify this graph because it will be the cached graph that
 174       // is returned by other users that want the local datastructure graph for
 175       // a method.
 176       //
 177       const FunctionDSGraph &NewFunction = DS.getDSGraph(F);
 178
 179       // StartNode - The first node of the incorporated graph, last node of the
 180       // preexisting data structure graph...
 181       //
 182       unsigned StartAllocNode = AllocNodes.size();
 183
 184       // Incorporate a copy of the called function graph into the current graph,
 185       // allowing us to do local transformations to local graph to link
 186       // arguments to call values, and call node to return value...
 187       //
 188       vector<PointerValSet> Args;
 189       RetVals = cloneFunctionIntoSelf(NewFunction, false, Args);
 190       CallMap.push_back(make_pair(CallDescriptor(CN->getArgs(), CN->getCall()),
 191                                   RetVals));
 192
 193       // If the call node has arguments, process them now!
 194       assert(Args.size() == CN->getNumArgs()-1 &&
 195              "Call node doesn't match function?");
 196
 197       for (unsigned i = 0, e = Args.size(); i != e; ++i) {
 198         // Now we make all of the nodes inside of the incorporated method
 199         // point to the real arguments values, not to the shadow nodes for the
 200         // argument.
 201         ResolveNodesTo(Args[i], CN->getArgValues(i+1));
 202       }
 203
 204       // Loop through the nodes, deleting alloca nodes in the inlined function.
 205       // Since the memory has been released, we cannot access their pointer
 206       // fields (with defined results at least), so it is not possible to use
 207       // any pointers to the alloca.  Drop them now, and remove the alloca's
 208       // since they are dead (we just removed all links to them).
 209       //
 210       for (unsigned i = StartAllocNode; i != AllocNodes.size(); ++i)
 211         if (AllocNodes[i]->isAllocaNode()) {
 212           AllocDSNode *NDS = AllocNodes[i];
 213           NDS->removeAllIncomingEdges();          // These edges are invalid now
 214           delete NDS;                             // Node is dead
 215           AllocNodes.erase(AllocNodes.begin()+i); // Remove slot in Nodes array
 216           --i;                                    // Don't skip the next node
 217         }
 218     }
 219
 220     // If the function returns a pointer value...  Resolve values pointing to
 221     // the shadow nodes pointed to by CN to now point the values in RetVals...
 222     //
 223     if (CN->getNumLinks()) ResolveNodeTo(CN, RetVals);
 224
 225     // Now the call node is completely destructable.  Eliminate it now.
 226     delete CN;
 227
 228     bool Changed = true;
 229     while (Changed) {
 230       // Eliminate shadow nodes that are not distinguishable from some other
 231       // node in the graph...
 232       //
 233       Changed = UnlinkUndistinguishableNodes();
 234
 235       // Eliminate shadow nodes that are now extraneous due to linking...
 236       Changed |= RemoveUnreachableNodes();
 237     }
 238
 239     //if (F == Func) return;  // Only do one self inlining
 240
 241     // Move on to the next call node...
 242     NI = std::find_if(CallNodes.begin(), CallNodes.end(), isResolvableCallNode);
 243   }
 244
 245   // Drop references to globals...
 246   CallMap.clear();
 247
 248   bool Changed = true;
 249   while (Changed) {
 250     // Eliminate shadow nodes that are not distinguishable from some other
 251     // node in the graph...
 252     //
 253     Changed = UnlinkUndistinguishableNodes();
 254
 255     // Eliminate shadow nodes that are now extraneous due to linking...
 256     Changed |= RemoveUnreachableNodes();
 257   }
 258 }