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/iOther.h"
  12 #include "Support/STLExtras.h"
  13 #include <algorithm>
  14 #ifdef DEBUG_IP_CLOSURE
  15 #include "llvm/Assembly/Writer.h"
  16 #endif
  17
  18 // copyEdgesFromTo - Make a copy of all of the edges to Node to also point
  19 // PV.  If there are edges out of Node, the edges are added to the subgraph
  20 // starting at PV.
  21 //
  22 static void copyEdgesFromTo(DSNode *Node, const PointerValSet &PVS) {
  23   // Make all of the pointers that pointed to Node now also point to PV...
  24   const vector<PointerValSet*> &PVSToUpdate(Node->getReferrers());
  25   for (unsigned i = 0, e = PVSToUpdate.size(); i != e; ++i)
  26     for (unsigned pn = 0, pne = PVS.size(); pn != pne; ++pn)
  27       PVSToUpdate[i]->add(PVS[pn]);
  28 }
  29
  30 static void CalculateNodeMapping(ShadowDSNode *Shadow, DSNode *Node,
  31                               multimap<ShadowDSNode *, DSNode *> &NodeMapping) {
  32 #ifdef DEBUG_IP_CLOSURE
  33   cerr << "Mapping " << (void*)Shadow << " to " << (void*)Node << "\n";
  34   cerr << "Type = '" << Shadow->getType() << "' and '"
  35        << Node->getType() << "'\n";
  36   cerr << "Shadow Node:\n";
  37   Shadow->print(cerr);
  38   cerr << "\nMapped Node:\n";
  39   Node->print(cerr);
  40 #endif
  41   assert(Shadow->getType() == Node->getType() &&
  42          "Shadow and mapped nodes disagree about type!");
  43
  44   multimap<ShadowDSNode *, DSNode *>::iterator
  45     NI = NodeMapping.lower_bound(Shadow),
  46     NE = NodeMapping.upper_bound(Shadow);
  47
  48   for (; NI != NE; ++NI)
  49     if (NI->second == Node) return;       // Already processed node, return.
  50
  51   NodeMapping.insert(make_pair(Shadow, Node));   // Add a mapping...
  52
  53   // Loop over all of the outgoing links in the shadow node...
  54   //
  55   assert(Node->getNumLinks() == Shadow->getNumLinks() &&
  56          "Same type, but different number of links?");
  57   for (unsigned i = 0, e = Shadow->getNumLinks(); i != e; ++i) {
  58     PointerValSet &Link = Shadow->getLink(i);
  59
  60     // Loop over all of the values coming out of this pointer...
  61     for (unsigned l = 0, le = Link.size(); l != le; ++l) {
  62       // If the outgoing node points to a shadow node, map the shadow node to
  63       // all of the outgoing values in Node.
  64       //
  65       if (ShadowDSNode *ShadOut = dyn_cast<ShadowDSNode>(Link[l].Node)) {
  66         PointerValSet &NLink = Node->getLink(i);
  67         for (unsigned ol = 0, ole = NLink.size(); ol != ole; ++ol)
  68           CalculateNodeMapping(ShadOut, NLink[ol].Node, NodeMapping);
  69       }
  70     }
  71   }
  72 }
  73
  74
  75 static void ResolveNodesTo(const PointerVal &FromPtr,
  76                            const PointerValSet &ToVals) {
  77   assert(FromPtr.Index == 0 &&
  78          "Resolved node return pointer should be index 0!");
  79   if (!isa<ShadowDSNode>(FromPtr.Node)) return;
  80
  81   ShadowDSNode *Shadow = cast<ShadowDSNode>(FromPtr.Node);
  82
  83   typedef multimap<ShadowDSNode *, DSNode *> ShadNodeMapTy;
  84   ShadNodeMapTy NodeMapping;
  85   for (unsigned i = 0, e = ToVals.size(); i != e; ++i)
  86     CalculateNodeMapping(Shadow, ToVals[i].Node, NodeMapping);
  87
  88   copyEdgesFromTo(Shadow, ToVals);
  89
  90   // Now loop through the shadow node graph, mirroring the edges in the shadow
  91   // graph onto the realized graph...
  92   //
  93   for (ShadNodeMapTy::iterator I = NodeMapping.begin(),
  94          E = NodeMapping.end(); I != E; ++I) {
  95     DSNode *Node = I->second;
  96     ShadowDSNode *ShadNode = I->first;
  97
  98     // Must loop over edges in the shadow graph, adding edges in the real graph
  99     // that correspond to to the edges, but are mapped into real values by the
 100     // NodeMapping.
 101     //
 102     for (unsigned i = 0, e = Node->getNumLinks(); i != e; ++i) {
 103       const PointerValSet &ShadLinks = ShadNode->getLink(i);
 104       PointerValSet &NewLinks = Node->getLink(i);
 105
 106       // Add a link to all of the nodes pointed to by the shadow field...
 107       for (unsigned l = 0, le = ShadLinks.size(); l != le; ++l) {
 108         DSNode *ShadLink = ShadLinks[l].Node;
 109
 110         if (ShadowDSNode *SL = dyn_cast<ShadowDSNode>(ShadLink)) {
 111           // Loop over all of the values in the range
 112           ShadNodeMapTy::iterator St = NodeMapping.lower_bound(SL),
 113                                   En = NodeMapping.upper_bound(SL);
 114           if (St != En) {
 115             for (; St != En; ++St)
 116               NewLinks.add(PointerVal(St->second, ShadLinks[l].Index));
 117           } else {
 118             // We must retain the shadow node...
 119             NewLinks.add(ShadLinks[l]);
 120           }
 121         } else {
 122           // Otherwise, add a direct link to the data structure pointed to by
 123           // the shadow node...
 124           NewLinks.add(ShadLinks[l]);
 125         }
 126       }
 127     }
 128   }
 129 }
 130
 131
 132 // ResolveNodeTo - The specified node is now known to point to the set of values
 133 // in ToVals, instead of the old shadow node subgraph that it was pointing to.
 134 //
 135 static void ResolveNodeTo(DSNode *Node, const PointerValSet &ToVals) {
 136   assert(Node->getNumLinks() == 1 && "Resolved node can only be a scalar!!");
 137
 138   PointerValSet PVS = Node->getLink(0);
 139
 140   for (unsigned i = 0, e = PVS.size(); i != e; ++i)
 141     ResolveNodesTo(PVS[i], ToVals);
 142 }
 143
 144 // isResolvableCallNode - Return true if node is a call node and it is a call
 145 // node that we can inline...
 146 //
 147 static bool isResolvableCallNode(DSNode *N) {
 148   // Only operate on call nodes...
 149   CallDSNode *CN = dyn_cast<CallDSNode>(N);
 150   if (CN == 0) return false;
 151
 152   // Only operate on call nodes with direct method calls
 153   Function *F = CN->getCall()->getCalledFunction();
 154   if (F == 0) return false;
 155
 156   // Only work on call nodes with direct calls to methods with bodies.
 157   return !F->isExternal();
 158 }
 159
 160
 161 // computeClosure - Replace all of the resolvable call nodes with the contents
 162 // of their corresponding method data structure graph...
 163 //
 164 void FunctionDSGraph::computeClosure(const DataStructure &DS) {
 165   vector<DSNode*>::iterator NI = std::find_if(Nodes.begin(), Nodes.end(),
 166                                               isResolvableCallNode);
 167
 168   map<Function*, unsigned> InlineCount; // FIXME
 169
 170   // Loop over the resolvable call nodes...
 171   while (NI != Nodes.end()) {
 172     CallDSNode *CN = cast<CallDSNode>(*NI);
 173     Function *F = CN->getCall()->getCalledFunction();
 174     //if (F == Func) return;  // Do not do self inlining
 175
 176     // FIXME: Gross hack to prevent explosions when inlining a recursive func.
 177     if (InlineCount[F]++ > 2) return;
 178
 179     Nodes.erase(NI);                     // Remove the call node from the graph
 180
 181     unsigned CallNodeOffset = NI-Nodes.begin();
 182
 183     // StartNode - The first node of the incorporated graph, last node of the
 184     // preexisting data structure graph...
 185     //
 186     unsigned StartNode = Nodes.size();
 187
 188     // Hold the set of values that correspond to the incorporated methods
 189     // return set.
 190     //
 191     PointerValSet RetVals;
 192
 193     if (F != Func) {  // If this is not a recursive call...
 194       // Get the datastructure graph for the new method.  Note that we are not
 195       // allowed to modify this graph because it will be the cached graph that
 196       // is returned by other users that want the local datastructure graph for
 197       // a method.
 198       //
 199       const FunctionDSGraph &NewFunction = DS.getDSGraph(F);
 200
 201       // Incorporate a copy of the called function graph into the current graph,
 202       // allowing us to do local transformations to local graph to link
 203       // arguments to call values, and call node to return value...
 204       //
 205       RetVals = cloneFunctionIntoSelf(NewFunction, false);
 206
 207     } else {     // We are looking at a recursive function!
 208       StartNode = 0;  // Arg nodes start at 0 now...
 209       RetVals = RetNode;
 210     }
 211
 212     // If the function returns a pointer value...  Resolve values pointing to
 213     // the shadow nodes pointed to by CN to now point the values in RetVals...
 214     //
 215     if (CN->getNumLinks()) ResolveNodeTo(CN, RetVals);
 216
 217     // If the call node has arguments, process them now!
 218     if (CN->getNumArgs()) {
 219       // The ArgNodes of the incorporated graph should be the nodes starting at
 220       // StartNode, ordered the same way as the call arguments.  The arg nodes
 221       // are seperated by a single shadow node, but that shadow node might get
 222       // eliminated in the process of optimization.
 223       //
 224       unsigned ArgOffset = StartNode;
 225       for (unsigned i = 0, e = CN->getNumArgs(); i != e; ++i) {
 226         // Get the arg node of the incorporated method...
 227         while (!isa<ArgDSNode>(Nodes[ArgOffset]))  // Scan for next arg node
 228           ArgOffset++;
 229         ArgDSNode *ArgNode = cast<ArgDSNode>(Nodes[ArgOffset]);
 230
 231         // Now we make all of the nodes inside of the incorporated method point
 232         // to the real arguments values, not to the shadow nodes for the
 233         // argument.
 234         //
 235         ResolveNodeTo(ArgNode, CN->getArgValues(i));
 236
 237         if (StartNode) {        // Not Self recursion?
 238           // Remove the argnode from the set of nodes in this method...
 239           Nodes.erase(Nodes.begin()+ArgOffset);
 240
 241           // ArgNode is no longer useful, delete now!
 242           delete ArgNode;
 243         }
 244       }
 245     }
 246
 247     // Now the call node is completely destructable.  Eliminate it now.
 248     delete CN;
 249
 250     bool Changed = true;
 251     while (Changed) {
 252       // Eliminate shadow nodes that are not distinguishable from some other
 253       // node in the graph...
 254       //
 255       Changed = UnlinkUndistinguishableShadowNodes();
 256
 257       // Eliminate shadow nodes that are now extraneous due to linking...
 258       Changed |= RemoveUnreachableShadowNodes();
 259     }
 260
 261     //if (F == Func) return;  // Only do one self inlining
 262
 263     // Move on to the next call node...
 264     NI = std::find_if(Nodes.begin(), Nodes.end(), isResolvableCallNode);
 265   }
 266 }