lib/Analysis/DataStructure/EquivClassGraphs.cpp

   1 //===- EquivClassGraphs.cpp - Merge equiv-class graphs & inline bottom-up -===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This pass is the same as the complete bottom-up graphs, but
  11 // with functions partitioned into equivalence classes and a single merged
  12 // DS graph for all functions in an equivalence class.  After this merging,
  13 // graphs are inlined bottom-up on the SCCs of the final (CBU) call graph.
  14 //
  15 //===----------------------------------------------------------------------===//
  16
  17 #define DEBUG_TYPE "ECGraphs"
  18 #include "EquivClassGraphs.h"
  19 #include "llvm/Module.h"
  20 #include "llvm/Pass.h"
  21 #include "llvm/Analysis/DataStructure/DSGraph.h"
  22 #include "llvm/Analysis/DataStructure/DataStructure.h"
  23 #include "llvm/Support/CallSite.h"
  24 #include "llvm/Support/Debug.h"
  25 #include "llvm/ADT/SCCIterator.h"
  26 #include "llvm/ADT/Statistic.h"
  27 #include "llvm/ADT/EquivalenceClasses.h"
  28 #include "llvm/ADT/STLExtras.h"
  29 using namespace llvm;
  30
  31 namespace {
  32   RegisterAnalysis<PA::EquivClassGraphs> X("equivdatastructure",
  33                     "Equivalence-class Bottom-up Data Structure Analysis");
  34   Statistic<> NumEquivBUInlines("equivdatastructures", "Number of graphs inlined");
  35   Statistic<> NumFoldGraphInlines("Inline equiv-class graphs bottom up",
  36                                   "Number of graphs inlined");
  37 }
  38
  39
  40 // getDSGraphForCallSite - Return the common data structure graph for
  41 // callees at the specified call site.
  42 //
  43 Function *PA::EquivClassGraphs::
  44 getSomeCalleeForCallSite(const CallSite &CS) const {
  45   Function *thisFunc = CS.getCaller();
  46   assert(thisFunc && "getDSGraphForCallSite(): Not a valid call site?");
  47   DSNode *calleeNode = CBU->getDSGraph(*thisFunc).
  48     getNodeForValue(CS.getCalledValue()).getNode();
  49   std::map<DSNode*, Function *>::const_iterator I =
  50     OneCalledFunction.find(calleeNode);
  51   return (I == OneCalledFunction.end())? NULL : I->second;
  52 }
  53
  54 // computeFoldedGraphs - Calculate the bottom up data structure
  55 // graphs for each function in the program.
  56 //
  57 void PA::EquivClassGraphs::computeFoldedGraphs(Module &M) {
  58   CBU = &getAnalysis<CompleteBUDataStructures>();
  59
  60   // Find equivalence classes of functions called from common call sites.
  61   // Fold the CBU graphs for all functions in an equivalence class.
  62   buildIndirectFunctionSets(M);
  63
  64   // Stack of functions used for Tarjan's SCC-finding algorithm.
  65   std::vector<Function*> Stack;
  66   hash_map<Function*, unsigned> ValMap;
  67   unsigned NextID = 1;
  68
  69   if (Function *Main = M.getMainFunction()) {
  70     if (!Main->isExternal())
  71       processSCC(getOrCreateGraph(*Main), *Main, Stack, NextID, ValMap);
  72   } else {
  73     std::cerr << "Fold Graphs: No 'main' function found!\n";
  74   }
  75
  76   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
  77     if (!I->isExternal() && !FoldedGraphsMap.count(I))
  78       processSCC(getOrCreateGraph(*I), *I, Stack, NextID, ValMap);
  79
  80   getGlobalsGraph().removeTriviallyDeadNodes();
  81 }
  82
  83
  84 // buildIndirectFunctionSets - Iterate over the module looking for indirect
  85 // calls to functions.  If a call site can invoke any functions [F1, F2... FN],
  86 // unify the N functions together in the FuncECs set.
  87 //
  88 void PA::EquivClassGraphs::buildIndirectFunctionSets(Module &M) {
  89   const ActualCalleesTy& AC = CBU->getActualCallees();
  90
  91   // Loop over all of the indirect calls in the program.  If a call site can
  92   // call multiple different functions, we need to unify all of the callees into
  93   // the same equivalence class.
  94   Instruction *LastInst = 0;
  95   Function *FirstFunc = 0;
  96   for (ActualCalleesTy::const_iterator I=AC.begin(), E=AC.end(); I != E; ++I) {
  97     if (I->second->isExternal())
  98       continue;                         // Ignore functions we cannot modify
  99
 100     CallSite CS = CallSite::get(I->first);
 101
 102     if (CS.getCalledFunction()) {       // Direct call:
 103       FuncECs.addElement(I->second);    // -- Make sure function has equiv class
 104       FirstFunc = I->second;            // -- First callee at this site
 105     } else {                            // Else indirect call
 106       // DEBUG(std::cerr << "CALLEE: " << I->second->getName()
 107       //       << " from : " << I->first);
 108       if (I->first != LastInst) {
 109         // This is the first callee from this call site.
 110         LastInst = I->first;
 111         FirstFunc = I->second;
 112         // Instead of storing the lastInst For Indirection call Sites we store
 113         // the DSNode for the function ptr arguemnt
 114         Function *thisFunc = LastInst->getParent()->getParent();
 115         DSGraph &TFG = CBU->getDSGraph(*thisFunc);
 116         DSNode *calleeNode = TFG.getNodeForValue(CS.getCalledValue()).getNode();
 117         OneCalledFunction[calleeNode] = FirstFunc;
 118         FuncECs.addElement(I->second);
 119       } else {
 120         // This is not the first possible callee from a particular call site.
 121         // Union the callee in with the other functions.
 122         FuncECs.unionSetsWith(FirstFunc, I->second);
 123 #ifndef NDEBUG
 124         Function *thisFunc = LastInst->getParent()->getParent();
 125         DSGraph &TFG = CBU->getDSGraph(*thisFunc);
 126         DSNode *calleeNode = TFG.getNodeForValue(CS.getCalledValue()).getNode();
 127         assert(OneCalledFunction.count(calleeNode) > 0 && "Missed a call?");
 128 #endif
 129       }
 130     }
 131
 132     // Now include all functions that share a graph with any function in the
 133     // equivalence class.  More precisely, if F is in the class, and G(F) is
 134     // its graph, then we include all other functions that are also in G(F).
 135     // Currently, that is just the functions in the same call-graph-SCC as F.
 136     //
 137     DSGraph& funcDSGraph = CBU->getDSGraph(*I->second);
 138     const DSGraph::ReturnNodesTy &RetNodes = funcDSGraph.getReturnNodes();
 139     for (DSGraph::ReturnNodesTy::const_iterator RI=RetNodes.begin(),
 140            RE=RetNodes.end(); RI != RE; ++RI)
 141       FuncECs.unionSetsWith(FirstFunc, RI->first);
 142   }
 143
 144   // Now that all of the equivalences have been built, merge the graphs for
 145   // each equivalence class.
 146   //
 147   std::set<Function*> &leaderSet = FuncECs.getLeaderSet();
 148   DEBUG(std::cerr << "\nIndirect Function Equivalence Sets:\n");
 149   for (std::set<Function*>::iterator LI = leaderSet.begin(),
 150          LE = leaderSet.end(); LI != LE; ++LI) {
 151
 152     Function* LF = *LI;
 153     const std::set<Function*>& EqClass = FuncECs.getEqClass(LF);
 154
 155 #ifndef NDEBUG
 156     if (EqClass.size() > 1) {
 157       DEBUG(std::cerr <<"  Equivalence set for leader " <<LF->getName()<<" = ");
 158       for (std::set<Function*>::const_iterator EqI = EqClass.begin(),
 159              EqEnd = EqClass.end(); EqI != EqEnd; ++EqI)
 160         DEBUG(std::cerr << " " << (*EqI)->getName() << ",");
 161       DEBUG(std::cerr << "\n");
 162     }
 163 #endif
 164
 165     if (EqClass.size() > 1) {
 166       // This equiv class has multiple functions: merge their graphs.
 167       // First, clone the CBU graph for the leader and make it the
 168       // common graph for the equivalence graph.
 169       DSGraph* mergedG = cloneGraph(*LF);
 170
 171       // Record the argument nodes for use in merging later below
 172       EquivClassGraphArgsInfo& GraphInfo = getECGraphInfo(mergedG);
 173       for (Function::aiterator AI1 = LF->abegin(); AI1 != LF->aend(); ++AI1)
 174         GraphInfo.argNodes.push_back(mergedG->getNodeForValue(AI1));
 175
 176       // Merge in the graphs of all other functions in this equiv. class.
 177       // Note that two or more functions may have the same graph, and it
 178       // only needs to be merged in once.  Use a set to find repetitions.
 179       std::set<DSGraph*> GraphsMerged;
 180       for (std::set<Function*>::const_iterator EqI = EqClass.begin(),
 181              EqEnd = EqClass.end(); EqI != EqEnd; ++EqI) {
 182         Function* F = *EqI;
 183         DSGraph*& FG = FoldedGraphsMap[F];
 184
 185         if (F == LF || FG == mergedG)
 186           continue;
 187
 188         // Record the "folded" graph for the function.
 189         FG = mergedG;
 190
 191         // Clone this member of the equivalence class into mergedG
 192         DSGraph* CBUGraph = &CBU->getDSGraph(*F);
 193         if (GraphsMerged.count(CBUGraph) > 0)
 194           continue;
 195
 196         GraphsMerged.insert(CBUGraph);
 197         DSGraph::NodeMapTy NodeMap;
 198
 199         mergedG->cloneInto(*CBUGraph, mergedG->getScalarMap(),
 200                            mergedG->getReturnNodes(), NodeMap, 0);
 201
 202         // Merge the return nodes of all functions together.
 203         mergedG->getReturnNodes()[LF].mergeWith(mergedG->getReturnNodes()[F]);
 204
 205         // Merge the function arguments with all argument nodes found so far.
 206         // If there are extra function args, add them to the vector of argNodes
 207         Function::aiterator AI2 = F->abegin(), AI2end = F->aend();
 208         for (unsigned arg=0, numArgs=GraphInfo.argNodes.size();
 209              arg != numArgs && AI2 != AI2end; ++AI2, ++arg)
 210           if (DS::isPointerType(AI2->getType()))
 211             GraphInfo.argNodes[arg].mergeWith(mergedG->getNodeForValue(AI2));
 212
 213         for ( ; AI2 != AI2end; ++AI2)
 214           if (DS::isPointerType(AI2->getType()))
 215             GraphInfo.argNodes.push_back(mergedG->getNodeForValue(AI2));
 216         DEBUG(mergedG->AssertGraphOK());
 217       }
 218     }
 219   }
 220   DEBUG(std::cerr << "\n");
 221 }
 222
 223
 224 DSGraph &PA::EquivClassGraphs::getOrCreateGraph(Function &F) {
 225   // Has the graph already been created?
 226   DSGraph *&Graph = FoldedGraphsMap[&F];
 227   if (Graph) return *Graph;
 228
 229   // Use the CBU graph directly without copying it.
 230   // This automatically updates the FoldedGraphsMap via the reference.
 231   Graph = &CBU->getDSGraph(F);
 232   return *Graph;
 233 }
 234
 235 DSGraph *PA::EquivClassGraphs::cloneGraph(Function &F) {
 236   DSGraph *&Graph = FoldedGraphsMap[&F];
 237   DSGraph &CBUGraph = CBU->getDSGraph(F);
 238   assert(Graph == NULL || Graph == &CBUGraph && "Cloning a graph twice?");
 239
 240   // Copy the CBU graph...
 241   Graph = new DSGraph(CBUGraph);           // updates the map via reference
 242   Graph->setGlobalsGraph(&getGlobalsGraph());
 243   Graph->setPrintAuxCalls();
 244
 245   // Make sure to update the FoldedGraphsMap map for all functions in the graph!
 246   for (DSGraph::ReturnNodesTy::iterator I = Graph->getReturnNodes().begin();
 247        I != Graph->getReturnNodes().end(); ++I)
 248     if (I->first != &F) {
 249       DSGraph*& FG = FoldedGraphsMap[I->first];
 250       assert(FG == NULL || FG == &CBU->getDSGraph(*I->first) &&
 251              "Merging function in SCC twice?");
 252       FG = Graph;
 253     }
 254
 255   return Graph;
 256 }
 257
 258
 259 unsigned PA::EquivClassGraphs::processSCC(DSGraph &FG, Function& F,
 260                                           std::vector<Function*> &Stack,
 261                                           unsigned &NextID,
 262                                           hash_map<Function*,unsigned> &ValMap){
 263   DEBUG(std::cerr << "    ProcessSCC for function " << F.getName() << "\n");
 264
 265   assert(!ValMap.count(&F) && "Shouldn't revisit functions!");
 266   unsigned Min = NextID++, MyID = Min;
 267   ValMap[&F] = Min;
 268   Stack.push_back(&F);
 269
 270   // The edges out of the current node are the call site targets...
 271   for (unsigned i = 0, e = FG.getFunctionCalls().size(); i != e; ++i) {
 272     Instruction *Call = FG.getFunctionCalls()[i].getCallSite().getInstruction();
 273
 274     // Loop over all of the actually called functions...
 275     ActualCalleesTy::const_iterator I, E;
 276     for (tie(I, E) = getActualCallees().equal_range(Call); I != E; ++I)
 277       if (!I->second->isExternal()) {
 278         DSGraph &CalleeG = getOrCreateGraph(*I->second);
 279
 280         // Have we visited the destination function yet?
 281         hash_map<Function*, unsigned>::iterator It = ValMap.find(I->second);
 282         unsigned M = (It == ValMap.end())  // No, visit it now.
 283           ? processSCC(CalleeG, *I->second, Stack, NextID, ValMap)
 284           : It->second;                    // Yes, get it's number.
 285
 286         if (M < Min) Min = M;
 287       }
 288   }
 289
 290   assert(ValMap[&F] == MyID && "SCC construction assumption wrong!");
 291   if (Min != MyID)
 292     return Min;         // This is part of a larger SCC!
 293
 294   // If this is a new SCC, process it now.
 295   bool IsMultiNodeSCC = false;
 296   while (Stack.back() != &F) {
 297     DSGraph *NG = &getOrCreateGraph(* Stack.back());
 298     ValMap[Stack.back()] = ~0U;
 299
 300     // Since all SCCs must be the same as those found in CBU, we do not need to
 301     // do any merging.  Make sure all functions in the SCC share the same graph.
 302     assert(NG == &FG &&
 303            "FoldGraphs: Functions in the same SCC have different graphs?");
 304
 305     Stack.pop_back();
 306     IsMultiNodeSCC = true;
 307   }
 308
 309   // Clean up the graph before we start inlining a bunch again...
 310   if (IsMultiNodeSCC)
 311     FG.removeTriviallyDeadNodes();
 312
 313   Stack.pop_back();
 314
 315   processGraph(FG, F);
 316   ValMap[&F] = ~0U;
 317   return MyID;
 318 }
 319
 320
 321 /// processGraph - Process the CBU graphs for the program in bottom-up order on
 322 /// the SCC of the __ACTUAL__ call graph.  This builds final folded CBU graphs.
 323 void PA::EquivClassGraphs::processGraph(DSGraph &G, Function &F) {
 324   DEBUG(std::cerr << "    ProcessGraph for function " << F.getName() << "\n");
 325
 326   hash_set<Instruction*> calls;
 327
 328   DSGraph* CallerGraph = sameAsCBUGraph(F) ? NULL : &getOrCreateGraph(F);
 329
 330   // If the function has not yet been cloned, let's check if any callees
 331   // need to be inlined before cloning it.
 332   //
 333   for (unsigned i=0, e=G.getFunctionCalls().size(); i!=e && !CallerGraph; ++i) {
 334     const DSCallSite &CS = G.getFunctionCalls()[i];
 335     Instruction *TheCall = CS.getCallSite().getInstruction();
 336
 337     // Loop over all potential callees to find the first non-external callee.
 338     // Some inlining is needed if there is such a callee and it has changed.
 339     ActualCalleesTy::const_iterator I, E;
 340     for (tie(I, E) = getActualCallees().equal_range(TheCall); I != E; ++I)
 341       if (!I->second->isExternal() && !sameAsCBUGraph(*I->second)) {
 342         // Ok, the caller does need to be cloned... go ahead and do it now.
 343         // clone the CBU graph for F now because we have not cloned it so far
 344         CallerGraph = cloneGraph(F);
 345         break;
 346       }
 347   }
 348
 349   if (!CallerGraph) {                   // No inlining is needed.
 350     DEBUG(std::cerr << "  --DONE ProcessGraph for function " << F.getName()
 351           << " (NO INLINING NEEDED)\n");
 352     return;
 353   }
 354
 355   // Else we need to inline some callee graph.  Visit all call sites.
 356   // The edges out of the current node are the call site targets...
 357   for (unsigned i=0, e = CallerGraph->getFunctionCalls().size(); i != e; ++i) {
 358     const DSCallSite &CS = CallerGraph->getFunctionCalls()[i];
 359     Instruction *TheCall = CS.getCallSite().getInstruction();
 360
 361     assert(calls.insert(TheCall).second &&
 362            "Call instruction occurs multiple times in graph??");
 363
 364     // Inline the common callee graph into the current graph, if the callee
 365     // graph has not changed.  Note that all callees should have the same
 366     // graph so we only need to do this once.
 367     //
 368     DSGraph* CalleeGraph = NULL;
 369     ActualCalleesTy::const_iterator I, E;
 370     tie(I, E) = getActualCallees().equal_range(TheCall);
 371     unsigned TNum, Num;
 372
 373     // Loop over all potential callees to find the first non-external callee.
 374     for (TNum = 0, Num = std::distance(I, E); I != E; ++I, ++TNum)
 375       if (!I->second->isExternal())
 376         break;
 377
 378     // Now check if the graph has changed and if so, clone and inline it.
 379     if (I != E && !sameAsCBUGraph(*I->second)) {
 380       Function *CalleeFunc = I->second;
 381
 382       // Merge the callee's graph into this graph, if not already the same.
 383       // Callees in the same equivalence class (which subsumes those
 384       // in the same SCCs) have the same graph.  Note that all recursion
 385       // including self-recursion have been folded in the equiv classes.
 386       //
 387       CalleeGraph = &getOrCreateGraph(*CalleeFunc);
 388       if (CalleeGraph != CallerGraph) {
 389         ++NumFoldGraphInlines;
 390         CallerGraph->mergeInGraph(CS, *CalleeFunc, *CalleeGraph,
 391                                   DSGraph::KeepModRefBits |
 392                                   DSGraph::StripAllocaBit |
 393                                   DSGraph::DontCloneCallNodes |
 394                                   DSGraph::DontCloneAuxCallNodes);
 395         DEBUG(std::cerr << "    Inlining graph [" << i << "/" << e-1
 396               << ":" << TNum << "/" << Num-1 << "] for "
 397               << CalleeFunc->getName() << "["
 398               << CalleeGraph->getGraphSize() << "+"
 399               << CalleeGraph->getAuxFunctionCalls().size()
 400               << "] into '" /*<< CallerGraph->getFunctionNames()*/ << "' ["
 401               << CallerGraph->getGraphSize() << "+"
 402               << CallerGraph->getAuxFunctionCalls().size()
 403               << "]\n");
 404       }
 405     }
 406
 407 #ifndef NDEBUG
 408     // Now loop over the rest of the callees and make sure they have the
 409     // same graph as the one inlined above.
 410     if (CalleeGraph)
 411       for (++I, ++TNum; I != E; ++I, ++TNum)
 412         if (!I->second->isExternal())
 413           assert(CalleeGraph == &getOrCreateGraph(*I->second) &&
 414                  "Callees at a call site have different graphs?");
 415 #endif
 416   }
 417
 418   // Recompute the Incomplete markers
 419   if (CallerGraph != NULL) {
 420     assert(CallerGraph->getInlinedGlobals().empty());
 421     CallerGraph->maskIncompleteMarkers();
 422     CallerGraph->markIncompleteNodes(DSGraph::MarkFormalArgs);
 423
 424     // Delete dead nodes.  Treat globals that are unreachable but that can
 425     // reach live nodes as live.
 426     CallerGraph->removeDeadNodes(DSGraph::KeepUnreachableGlobals);
 427   }
 428
 429   DEBUG(std::cerr << "  --DONE ProcessGraph for function "
 430                   << F.getName() << "\n");
 431 }