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