LLVM API Documentation

EquivClassGraphs.cpp

Go to the documentation of this file.
00001 //===- EquivClassGraphs.cpp - Merge equiv-class graphs & inline bottom-up -===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This pass is the same as the complete bottom-up graphs, but
00011 // with functions partitioned into equivalence classes and a single merged
00012 // DS graph for all functions in an equivalence class.  After this merging,
00013 // graphs are inlined bottom-up on the SCCs of the final (CBU) call graph.
00014 //
00015 //===----------------------------------------------------------------------===//
00016 
00017 #define DEBUG_TYPE "ECGraphs"
00018 #include "llvm/Analysis/DataStructure/DataStructure.h"
00019 #include "llvm/DerivedTypes.h"
00020 #include "llvm/Module.h"
00021 #include "llvm/Pass.h"
00022 #include "llvm/Analysis/DataStructure/DSGraph.h"
00023 #include "llvm/Support/CallSite.h"
00024 #include "llvm/Support/Debug.h"
00025 #include "llvm/ADT/SCCIterator.h"
00026 #include "llvm/ADT/Statistic.h"
00027 #include "llvm/ADT/EquivalenceClasses.h"
00028 #include "llvm/ADT/STLExtras.h"
00029 #include <iostream>
00030 using namespace llvm;
00031 
00032 namespace {
00033   RegisterAnalysis<EquivClassGraphs> X("eqdatastructure",
00034                     "Equivalence-class Bottom-up Data Structure Analysis");
00035   Statistic<> NumEquivBUInlines("equivdatastructures",
00036                                 "Number of graphs inlined");
00037   Statistic<> NumFoldGraphInlines("Inline equiv-class graphs bottom up",
00038                                   "Number of graphs inlined");
00039 }
00040 
00041 #ifndef NDEBUG
00042 template<typename GT>
00043 static void CheckAllGraphs(Module *M, GT &ECGraphs) {
00044   DSGraph &GG = ECGraphs.getGlobalsGraph();
00045 
00046   for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I)
00047     if (!I->isExternal()) {
00048       DSGraph &G = ECGraphs.getDSGraph(*I);
00049       if (G.retnodes_begin()->first != I)
00050         continue;  // Only check a graph once.
00051 
00052       DSGraph::NodeMapTy GlobalsGraphNodeMapping;
00053       G.computeGToGGMapping(GlobalsGraphNodeMapping);
00054     }
00055 }
00056 #endif
00057 
00058 // getSomeCalleeForCallSite - Return any one callee function at a call site.
00059 //
00060 Function *EquivClassGraphs::getSomeCalleeForCallSite(const CallSite &CS) const{
00061   Function *thisFunc = CS.getCaller();
00062   assert(thisFunc && "getSomeCalleeForCallSite(): Not a valid call site?");
00063   DSGraph &DSG = getDSGraph(*thisFunc);
00064   DSNode *calleeNode = DSG.getNodeForValue(CS.getCalledValue()).getNode();
00065   std::map<DSNode*, Function *>::const_iterator I =
00066     OneCalledFunction.find(calleeNode);
00067   return (I == OneCalledFunction.end())? NULL : I->second;
00068 }
00069 
00070 // runOnModule - Calculate the bottom up data structure graphs for each function
00071 // in the program.
00072 //
00073 bool EquivClassGraphs::runOnModule(Module &M) {
00074   CBU = &getAnalysis<CompleteBUDataStructures>();
00075   GlobalECs = CBU->getGlobalECs();
00076   DEBUG(CheckAllGraphs(&M, *CBU));
00077 
00078   GlobalsGraph = new DSGraph(CBU->getGlobalsGraph(), GlobalECs);
00079   GlobalsGraph->setPrintAuxCalls();
00080 
00081   ActualCallees = CBU->getActualCallees();
00082 
00083   // Find equivalence classes of functions called from common call sites.
00084   // Fold the CBU graphs for all functions in an equivalence class.
00085   buildIndirectFunctionSets(M);
00086 
00087   // Stack of functions used for Tarjan's SCC-finding algorithm.
00088   std::vector<DSGraph*> Stack;
00089   std::map<DSGraph*, unsigned> ValMap;
00090   unsigned NextID = 1;
00091 
00092   Function *MainFunc = M.getMainFunction();
00093   if (MainFunc && !MainFunc->isExternal()) {
00094     processSCC(getOrCreateGraph(*MainFunc), Stack, NextID, ValMap);
00095   } else {
00096     std::cerr << "Fold Graphs: No 'main' function found!\n";
00097   }
00098 
00099   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
00100     if (!I->isExternal())
00101       processSCC(getOrCreateGraph(*I), Stack, NextID, ValMap);
00102 
00103   DEBUG(CheckAllGraphs(&M, *this));
00104 
00105   getGlobalsGraph().removeTriviallyDeadNodes();
00106   getGlobalsGraph().markIncompleteNodes(DSGraph::IgnoreGlobals);
00107 
00108   // Merge the globals variables (not the calls) from the globals graph back
00109   // into the main function's graph so that the main function contains all of
00110   // the information about global pools and GV usage in the program.
00111   if (MainFunc && !MainFunc->isExternal()) {
00112     DSGraph &MainGraph = getOrCreateGraph(*MainFunc);
00113     const DSGraph &GG = *MainGraph.getGlobalsGraph();
00114     ReachabilityCloner RC(MainGraph, GG,
00115                           DSGraph::DontCloneCallNodes |
00116                           DSGraph::DontCloneAuxCallNodes);
00117 
00118     // Clone the global nodes into this graph.
00119     for (DSScalarMap::global_iterator I = GG.getScalarMap().global_begin(),
00120            E = GG.getScalarMap().global_end(); I != E; ++I)
00121       if (isa<GlobalVariable>(*I))
00122         RC.getClonedNH(GG.getNodeForValue(*I));
00123 
00124     MainGraph.maskIncompleteMarkers();
00125     MainGraph.markIncompleteNodes(DSGraph::MarkFormalArgs |
00126                                   DSGraph::IgnoreGlobals);
00127   }
00128 
00129   // Final processing.  Note that dead node elimination may actually remove
00130   // globals from a function graph that are immediately used.  If there are no
00131   // scalars pointing to the node (e.g. because the only use is a direct store
00132   // to a scalar global) we have to make sure to rematerialize the globals back
00133   // into the graphs here, or clients will break!
00134   for (Module::global_iterator GI = M.global_begin(), E = M.global_end();
00135        GI != E; ++GI)
00136     // This only happens to first class typed globals.
00137     if (GI->getType()->getElementType()->isFirstClassType())
00138       for (Value::use_iterator UI = GI->use_begin(), E = GI->use_end();
00139            UI != E; ++UI)
00140         // This only happens to direct uses by instructions.
00141         if (Instruction *User = dyn_cast<Instruction>(*UI)) {
00142           DSGraph &DSG = getOrCreateGraph(*User->getParent()->getParent());
00143           if (!DSG.getScalarMap().count(GI)) {
00144             // If this global does not exist in the graph, but it is immediately
00145             // used by an instruction in the graph, clone it over from the
00146             // globals graph.
00147             ReachabilityCloner RC(DSG, *GlobalsGraph, 0);
00148             RC.getClonedNH(GlobalsGraph->getNodeForValue(GI));
00149           }
00150         }
00151 
00152   return false;
00153 }
00154 
00155 
00156 // buildIndirectFunctionSets - Iterate over the module looking for indirect
00157 // calls to functions.  If a call site can invoke any functions [F1, F2... FN],
00158 // unify the N functions together in the FuncECs set.
00159 //
00160 void EquivClassGraphs::buildIndirectFunctionSets(Module &M) {
00161   const ActualCalleesTy& AC = CBU->getActualCallees();
00162 
00163   // Loop over all of the indirect calls in the program.  If a call site can
00164   // call multiple different functions, we need to unify all of the callees into
00165   // the same equivalence class.
00166   Instruction *LastInst = 0;
00167   Function *FirstFunc = 0;
00168   for (ActualCalleesTy::const_iterator I=AC.begin(), E=AC.end(); I != E; ++I) {
00169     if (I->second->isExternal())
00170       continue;                         // Ignore functions we cannot modify
00171 
00172     CallSite CS = CallSite::get(I->first);
00173 
00174     if (CS.getCalledFunction()) {       // Direct call:
00175       FuncECs.insert(I->second);        // -- Make sure function has equiv class
00176       FirstFunc = I->second;            // -- First callee at this site
00177     } else {                            // Else indirect call
00178       // DEBUG(std::cerr << "CALLEE: " << I->second->getName()
00179       //       << " from : " << I->first);
00180       if (I->first != LastInst) {
00181         // This is the first callee from this call site.
00182         LastInst = I->first;
00183         FirstFunc = I->second;
00184         // Instead of storing the lastInst For Indirection call Sites we store
00185         // the DSNode for the function ptr arguemnt
00186         Function *thisFunc = LastInst->getParent()->getParent();
00187         DSGraph &TFG = CBU->getDSGraph(*thisFunc);
00188         DSNode *calleeNode = TFG.getNodeForValue(CS.getCalledValue()).getNode();
00189         OneCalledFunction[calleeNode] = FirstFunc;
00190         FuncECs.insert(I->second);
00191       } else {
00192         // This is not the first possible callee from a particular call site.
00193         // Union the callee in with the other functions.
00194         FuncECs.unionSets(FirstFunc, I->second);
00195 #ifndef NDEBUG
00196         Function *thisFunc = LastInst->getParent()->getParent();
00197         DSGraph &TFG = CBU->getDSGraph(*thisFunc);
00198         DSNode *calleeNode = TFG.getNodeForValue(CS.getCalledValue()).getNode();
00199         assert(OneCalledFunction.count(calleeNode) > 0 && "Missed a call?");
00200 #endif
00201       }
00202     }
00203 
00204     // Now include all functions that share a graph with any function in the
00205     // equivalence class.  More precisely, if F is in the class, and G(F) is
00206     // its graph, then we include all other functions that are also in G(F).
00207     // Currently, that is just the functions in the same call-graph-SCC as F.
00208     //
00209     DSGraph& funcDSGraph = CBU->getDSGraph(*I->second);
00210     for (DSGraph::retnodes_iterator RI = funcDSGraph.retnodes_begin(),
00211            RE = funcDSGraph.retnodes_end(); RI != RE; ++RI)
00212       FuncECs.unionSets(FirstFunc, RI->first);
00213   }
00214 
00215   // Now that all of the equivalences have been built, merge the graphs for
00216   // each equivalence class.
00217   //
00218   DEBUG(std::cerr << "\nIndirect Function Equivalence Sets:\n");
00219   for (EquivalenceClasses<Function*>::iterator EQSI = FuncECs.begin(), E =
00220          FuncECs.end(); EQSI != E; ++EQSI) {
00221     if (!EQSI->isLeader()) continue;
00222 
00223     EquivalenceClasses<Function*>::member_iterator SI =
00224       FuncECs.member_begin(EQSI);
00225     assert(SI != FuncECs.member_end() && "Empty equiv set??");
00226     EquivalenceClasses<Function*>::member_iterator SN = SI;
00227     ++SN;
00228     if (SN == FuncECs.member_end())
00229       continue;   // Single function equivalence set, no merging to do.
00230 
00231     Function* LF = *SI;
00232 
00233 #ifndef NDEBUG
00234     DEBUG(std::cerr <<"  Equivalence set for leader " << LF->getName() <<" = ");
00235     for (SN = SI; SN != FuncECs.member_end(); ++SN)
00236       DEBUG(std::cerr << " " << (*SN)->getName() << "," );
00237     DEBUG(std::cerr << "\n");
00238 #endif
00239 
00240     // This equiv class has multiple functions: merge their graphs.  First,
00241     // clone the CBU graph for the leader and make it the common graph for the
00242     // equivalence graph.
00243     DSGraph &MergedG = getOrCreateGraph(*LF);
00244 
00245     // Record the argument nodes for use in merging later below.
00246     std::vector<DSNodeHandle> ArgNodes;
00247 
00248     for (Function::arg_iterator AI = LF->arg_begin(), E = LF->arg_end();
00249          AI != E; ++AI)
00250       if (DS::isPointerType(AI->getType()))
00251         ArgNodes.push_back(MergedG.getNodeForValue(AI));
00252 
00253     // Merge in the graphs of all other functions in this equiv. class.  Note
00254     // that two or more functions may have the same graph, and it only needs
00255     // to be merged in once.
00256     std::set<DSGraph*> GraphsMerged;
00257     GraphsMerged.insert(&CBU->getDSGraph(*LF));
00258 
00259     for (++SI; SI != FuncECs.member_end(); ++SI) {
00260       Function *F = *SI;
00261       DSGraph *&FG = DSInfo[F];
00262 
00263       DSGraph &CBUGraph = CBU->getDSGraph(*F);
00264       if (GraphsMerged.insert(&CBUGraph).second) {
00265         // Record the "folded" graph for the function.
00266         for (DSGraph::retnodes_iterator I = CBUGraph.retnodes_begin(),
00267                E = CBUGraph.retnodes_end(); I != E; ++I) {
00268           assert(DSInfo[I->first] == 0 && "Graph already exists for Fn!");
00269           DSInfo[I->first] = &MergedG;
00270         }
00271 
00272         // Clone this member of the equivalence class into MergedG.
00273         MergedG.cloneInto(CBUGraph);
00274       }
00275 
00276       // Merge the return nodes of all functions together.
00277       MergedG.getReturnNodes()[LF].mergeWith(MergedG.getReturnNodes()[F]);
00278 
00279       // Merge the function arguments with all argument nodes found so far.
00280       // If there are extra function args, add them to the vector of argNodes
00281       Function::arg_iterator AI2 = F->arg_begin(), AI2end = F->arg_end();
00282       for (unsigned arg = 0, numArgs = ArgNodes.size();
00283            arg != numArgs && AI2 != AI2end; ++AI2, ++arg)
00284         if (DS::isPointerType(AI2->getType()))
00285           ArgNodes[arg].mergeWith(MergedG.getNodeForValue(AI2));
00286 
00287       for ( ; AI2 != AI2end; ++AI2)
00288         if (DS::isPointerType(AI2->getType()))
00289           ArgNodes.push_back(MergedG.getNodeForValue(AI2));
00290       DEBUG(MergedG.AssertGraphOK());
00291     }
00292   }
00293   DEBUG(std::cerr << "\n");
00294 }
00295 
00296 
00297 DSGraph &EquivClassGraphs::getOrCreateGraph(Function &F) {
00298   // Has the graph already been created?
00299   DSGraph *&Graph = DSInfo[&F];
00300   if (Graph) return *Graph;
00301 
00302   DSGraph &CBUGraph = CBU->getDSGraph(F);
00303 
00304   // Copy the CBU graph...
00305   Graph = new DSGraph(CBUGraph, GlobalECs);   // updates the map via reference
00306   Graph->setGlobalsGraph(&getGlobalsGraph());
00307   Graph->setPrintAuxCalls();
00308 
00309   // Make sure to update the DSInfo map for all functions in the graph!
00310   for (DSGraph::retnodes_iterator I = Graph->retnodes_begin();
00311        I != Graph->retnodes_end(); ++I)
00312     if (I->first != &F) {
00313       DSGraph *&FG = DSInfo[I->first];
00314       assert(FG == 0 && "Merging function in SCC twice?");
00315       FG = Graph;
00316     }
00317 
00318   return *Graph;
00319 }
00320 
00321 
00322 unsigned EquivClassGraphs::
00323 processSCC(DSGraph &FG, std::vector<DSGraph*> &Stack, unsigned &NextID,
00324            std::map<DSGraph*, unsigned> &ValMap) {
00325   std::map<DSGraph*, unsigned>::iterator It = ValMap.lower_bound(&FG);
00326   if (It != ValMap.end() && It->first == &FG)
00327     return It->second;
00328 
00329   DEBUG(std::cerr << "    ProcessSCC for function " << FG.getFunctionNames()
00330                   << "\n");
00331 
00332   unsigned Min = NextID++, MyID = Min;
00333   ValMap[&FG] = Min;
00334   Stack.push_back(&FG);
00335 
00336   // The edges out of the current node are the call site targets...
00337   for (DSGraph::fc_iterator CI = FG.fc_begin(), CE = FG.fc_end();
00338        CI != CE; ++CI) {
00339     Instruction *Call = CI->getCallSite().getInstruction();
00340 
00341     // Loop over all of the actually called functions...
00342     for (callee_iterator I = callee_begin(Call), E = callee_end(Call);
00343          I != E; ++I)
00344       if (!I->second->isExternal()) {
00345         // Process the callee as necessary.
00346         unsigned M = processSCC(getOrCreateGraph(*I->second),
00347                                 Stack, NextID, ValMap);
00348         if (M < Min) Min = M;
00349       }
00350   }
00351 
00352   assert(ValMap[&FG] == MyID && "SCC construction assumption wrong!");
00353   if (Min != MyID)
00354     return Min;         // This is part of a larger SCC!
00355 
00356   // If this is a new SCC, process it now.
00357   bool MergedGraphs = false;
00358   while (Stack.back() != &FG) {
00359     DSGraph *NG = Stack.back();
00360     ValMap[NG] = ~0U;
00361 
00362     // If the SCC found is not the same as those found in CBU, make sure to
00363     // merge the graphs as appropriate.
00364     FG.cloneInto(*NG);
00365 
00366     // Update the DSInfo map and delete the old graph...
00367     for (DSGraph::retnodes_iterator I = NG->retnodes_begin();
00368          I != NG->retnodes_end(); ++I)
00369       DSInfo[I->first] = &FG;
00370 
00371     // Remove NG from the ValMap since the pointer may get recycled.
00372     ValMap.erase(NG);
00373     delete NG;
00374     MergedGraphs = true;
00375     Stack.pop_back();
00376   }
00377 
00378   // Clean up the graph before we start inlining a bunch again.
00379   if (MergedGraphs)
00380     FG.removeTriviallyDeadNodes();
00381 
00382   Stack.pop_back();
00383 
00384   processGraph(FG);
00385   ValMap[&FG] = ~0U;
00386   return MyID;
00387 }
00388 
00389 
00390 /// processGraph - Process the CBU graphs for the program in bottom-up order on
00391 /// the SCC of the __ACTUAL__ call graph.  This builds final folded CBU graphs.
00392 void EquivClassGraphs::processGraph(DSGraph &G) {
00393   DEBUG(std::cerr << "    ProcessGraph for function "
00394                   << G.getFunctionNames() << "\n");
00395 
00396   hash_set<Instruction*> calls;
00397 
00398   // Else we need to inline some callee graph.  Visit all call sites.
00399   // The edges out of the current node are the call site targets...
00400   unsigned i = 0;
00401   for (DSGraph::fc_iterator CI = G.fc_begin(), CE = G.fc_end(); CI != CE;
00402        ++CI, ++i) {
00403     const DSCallSite &CS = *CI;
00404     Instruction *TheCall = CS.getCallSite().getInstruction();
00405 
00406     assert(calls.insert(TheCall).second &&
00407            "Call instruction occurs multiple times in graph??");
00408 
00409     if (CS.getRetVal().isNull() && CS.getNumPtrArgs() == 0)
00410       continue;
00411 
00412     // Inline the common callee graph into the current graph, if the callee
00413     // graph has not changed.  Note that all callees should have the same
00414     // graph so we only need to do this once.
00415     //
00416     DSGraph* CalleeGraph = NULL;
00417     callee_iterator I = callee_begin(TheCall), E = callee_end(TheCall);
00418     unsigned TNum, Num;
00419 
00420     // Loop over all potential callees to find the first non-external callee.
00421     for (TNum = 0, Num = std::distance(I, E); I != E; ++I, ++TNum)
00422       if (!I->second->isExternal())
00423         break;
00424 
00425     // Now check if the graph has changed and if so, clone and inline it.
00426     if (I != E) {
00427       Function *CalleeFunc = I->second;
00428 
00429       // Merge the callee's graph into this graph, if not already the same.
00430       // Callees in the same equivalence class (which subsumes those
00431       // in the same SCCs) have the same graph.  Note that all recursion
00432       // including self-recursion have been folded in the equiv classes.
00433       //
00434       CalleeGraph = &getOrCreateGraph(*CalleeFunc);
00435       if (CalleeGraph != &G) {
00436         ++NumFoldGraphInlines;
00437         G.mergeInGraph(CS, *CalleeFunc, *CalleeGraph,
00438                        DSGraph::StripAllocaBit |
00439                        DSGraph::DontCloneCallNodes |
00440                        DSGraph::DontCloneAuxCallNodes);
00441         DEBUG(std::cerr << "    Inlining graph [" << i << "/"
00442               << G.getFunctionCalls().size()-1
00443               << ":" << TNum << "/" << Num-1 << "] for "
00444               << CalleeFunc->getName() << "["
00445               << CalleeGraph->getGraphSize() << "+"
00446               << CalleeGraph->getAuxFunctionCalls().size()
00447               << "] into '" /*<< G.getFunctionNames()*/ << "' ["
00448               << G.getGraphSize() << "+" << G.getAuxFunctionCalls().size()
00449               << "]\n");
00450       }
00451     }
00452 
00453 #ifndef NDEBUG
00454     // Now loop over the rest of the callees and make sure they have the
00455     // same graph as the one inlined above.
00456     if (CalleeGraph)
00457       for (++I, ++TNum; I != E; ++I, ++TNum)
00458         if (!I->second->isExternal())
00459           assert(CalleeGraph == &getOrCreateGraph(*I->second) &&
00460                  "Callees at a call site have different graphs?");
00461 #endif
00462   }
00463 
00464   // Recompute the Incomplete markers.
00465   G.maskIncompleteMarkers();
00466   G.markIncompleteNodes(DSGraph::MarkFormalArgs);
00467 
00468   // Delete dead nodes.  Treat globals that are unreachable but that can
00469   // reach live nodes as live.
00470   G.removeDeadNodes(DSGraph::KeepUnreachableGlobals);
00471 
00472   // When this graph is finalized, clone the globals in the graph into the
00473   // globals graph to make sure it has everything, from all graphs.
00474   ReachabilityCloner RC(*G.getGlobalsGraph(), G, DSGraph::StripAllocaBit);
00475 
00476   // Clone everything reachable from globals in the function graph into the
00477   // globals graph.
00478   DSScalarMap &MainSM = G.getScalarMap();
00479   for (DSScalarMap::global_iterator I = MainSM.global_begin(),
00480          E = MainSM.global_end(); I != E; ++I)
00481     RC.getClonedNH(MainSM[*I]);
00482 
00483   DEBUG(std::cerr << "  -- DONE ProcessGraph for function "
00484                   << G.getFunctionNames() << "\n");
00485 }