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