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