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