poolalloc/lib/DSA/CompleteBottomUp.cpp

//===- CompleteBottomUp.cpp - Complete Bottom-Up Data Structure Graphs ----===//
//
//                     The LLVM Compiler Infrastructure
//
// This file was developed by the LLVM research group and is distributed under
// the University of Illinois Open Source License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This is the exact same as the bottom-up graphs, but we use take a completed
// call graph and inline all indirect callees into their callers graphs, making
// the result more useful for things like pool allocation.
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "dsa-cbu"
#include "dsa/DataStructure.h"
#include "dsa/DSGraph.h"
#include "llvm/Module.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/FormattedStream.h"
using namespace llvm;

namespace {
  RegisterPass<CompleteBUDataStructures>
  X("dsa-cbu", "'Complete' Bottom-up Data Structure Analysis");
}

char CompleteBUDataStructures::ID;

//
// Method: runOnModule()
//
// Description:
//  Entry point for this pass.  Calculate the bottom up data structure graphs
//  for each function in the program.
//
// Return value:
//  true  - The module was modified.
//  false - The module was not modified.
//
bool
CompleteBUDataStructures::runOnModule (Module &M) {
  init(&getAnalysis<BUDataStructures>(), true, true, false, true);


  //
  // Make sure we have a DSGraph for all declared functions in the Module.
  // formGlobalECs assumes that DSInfo is populated with a list of
  // DSgraphs for all the functions.

  for (Module::iterator F = M.begin(); F != M.end(); ++F) {
    if (!(F->isDeclaration())){
      getOrCreateGraph(F);
    }
  }

  buildIndirectFunctionSets();
  formGlobalECs();
  for (Module::iterator F = M.begin(); F != M.end(); ++F) {
    if (!(F->isDeclaration())) {
      if (DSGraph * Graph = getOrCreateGraph(F)) {
        cloneIntoGlobals(Graph, DSGraph::DontCloneCallNodes |
                        DSGraph::DontCloneAuxCallNodes |
                        DSGraph::StripAllocaBit);
      }
    }
  }

  for (Module::iterator F = M.begin(); F != M.end(); ++F) {
    if (!(F->isDeclaration())) {
      if (DSGraph * Graph = getOrCreateGraph(F)) {
        cloneGlobalsInto(Graph, DSGraph::DontCloneCallNodes |
                        DSGraph::DontCloneAuxCallNodes);
      }
    }
  }

  //
  // Do bottom-up propagation.
  //
  bool modified = runOnModuleInternal(M);
  
  callgraph.buildSCCs();
  callgraph.buildRoots();
  
  return modified;
}

//
// Method: buildIndirectFunctionSets()
//
// Description:
//  For every indirect call site, ensure that every function target is
//  associated with a single DSNode.
//
void
CompleteBUDataStructures::buildIndirectFunctionSets (void) {
  //
  // Loop over all of the indirect calls in the program.  If a call site can
  // call multiple different functions, we need to unify all of the callees into
  // the same equivalence class.
  //
  DSGraph* G = getGlobalsGraph();
  DSGraph::ScalarMapTy& SM = G->getScalarMap();

  // Merge nodes in the global graph for these functions
  for (DSCallGraph::callee_key_iterator ii = callgraph.key_begin(),
       ee = callgraph.key_end(); ii != ee; ++ii) {

#ifndef NDEBUG
    // --Verify that for every callee of an indirect function call
    //   we have an entry in the GlobalsGraph

    // If any function in an SCC is a callee of an indirect function
    // call, the DScallgraph contains the leader of the SCC as the
    // callee of the indirect call.
    // The leasder of the SCC may not have an entry in the Globals
    // Graph, but at least one of the functions in the SCC
    // should have an entry in the GlobalsGraph

    Value *CalledValue = (*ii).getCalledValue()->stripPointerCasts();
    
    bool isIndirect = (!isa<Function>(CalledValue));
    if (isIndirect) {
      DSCallGraph::callee_iterator csii = callgraph.callee_begin(*ii),
                                   csee = callgraph.callee_end(*ii);

      for (; csii != csee; ++csii) {
        //
        // Declarations don't have to have entries.  Functions may be
        // equivalence classed already, so we have to check their equivalence
        // class leader instead of the global itself.
        //
        const Function * F = *csii;
        if (!(F->isDeclaration())){
          DSCallGraph::scc_iterator sccii = callgraph.scc_begin(F),
                                    sccee = callgraph.scc_end(F);
          bool flag = false;
          for(; sccii != sccee; ++sccii) {
            flag |= SM.count(SM.getLeaderForGlobal(*sccii));
          } 
          assert (flag &&
                  "Indirect function callee not in globals?");
         }
      }
    }
#endif

    //
    // Note: The code above and below is dealing with the fact that the targets
    // of *direct* function calls do not show up in the Scalar Map of the
    // globals graph.  The above assertion simply verifies that all targets of
    // indirect function calls show up in the Scalar Map of the globals graph,
    // and then the code below can just check the scalar map to see if the
    // call needs to be processed because it is an indirect function call.
    //
    // I suspect that this code is designed this way more for historical
    // reasons than for simplicity.  We should simplify the code is possible at
    // a future date.
    //
    // FIXME: Given the above is a valid assertion, we could probably replace
    // this code with something that *assumes* we have entries in the Scalar
    // Map.  However, because
    // I'm not convinced that we can just *skip* direct calls in this function
    // this code is careful to handle callees not existing in the globals graph
    // In other words what we have here should be correct, but might be overkill
    // that we can trim down later as needed.
    
    DSNodeHandle calleesNH;
   
    // When we build SCCs we remove any calls that are to functions in the 
    // same SCC. Hence, for every indirect call site we must assume that it
    // might call functions in its function's SCC that are address taken.
    const Function *F1 = (*ii).getInstruction()->getParent()->getParent();
    F1 = callgraph.sccLeader(&*F1);

    DSCallGraph::scc_iterator sccii = callgraph.scc_begin(F1),
                                sccee = callgraph.scc_end(F1);
    for(;sccii != sccee; ++sccii) {
      DSGraph::ScalarMapTy::const_iterator I = SM.find(SM.getLeaderForGlobal(*sccii));
      if (I != SM.end()) {
        calleesNH.mergeWith(I->second);
      }
    }

    DSCallGraph::callee_iterator csi = callgraph.callee_begin(*ii),
            cse = callgraph.callee_end(*ii);


    // We get all the callees, and then for all functions in that SCC, find the
    // ones that have entries in the GlobalsGraph.

    // We merge all the functions in the SCC that have entries, and then move
    // on to the next callee and repeat.

    // If an SCC has functions that have entries in the GlobalsGraph, and are
    // targets of an indirect function call site, they will be merged.

    // However, if an SCC has functions, that have entries in the GlobalsGraph,
    // bur are not the targets of an indirect function call site, they will not
    // be merged by CBU.

    // This NH starts off empty, but ends up merging them all together

    while(csi != cse) {
      const Function *F = *csi;
      DSCallGraph::scc_iterator sccii = callgraph.scc_begin(F),
                                sccee = callgraph.scc_end(F);
      for(;sccii != sccee; ++sccii) {
        DSGraph::ScalarMapTy::const_iterator I = SM.find(SM.getLeaderForGlobal(*sccii));
        if (I != SM.end()) {
          calleesNH.mergeWith(I->second);
        }
      }
      ++csi;
    }
  }
}