path: root/lib/Analysis/DataStructure/IPModRef.cpp

//===- IPModRef.cpp - Compute IP Mod/Ref information ------------*- C++ -*-===//
// 
//                     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.
// 
//===----------------------------------------------------------------------===//
//
// See high-level comments in IPModRef.h
// 
//===----------------------------------------------------------------------===//

#include "IPModRef.h"
#include "llvm/Analysis/DataStructure/DataStructure.h"
#include "llvm/Analysis/DataStructure/DSGraph.h"
#include "llvm/Module.h"
#include "llvm/Instructions.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/StringExtras.h"
#include <vector>

namespace llvm {

//----------------------------------------------------------------------------
// Private constants and data
//----------------------------------------------------------------------------

static RegisterAnalysis<IPModRef>
Z("ipmodref", "Interprocedural mod/ref analysis");


//----------------------------------------------------------------------------
// class ModRefInfo
//----------------------------------------------------------------------------

void ModRefInfo::print(std::ostream &O,
                       const std::string& sprefix) const
{
  O << sprefix << "Modified   nodes = " << modNodeSet;
  O << sprefix << "Referenced nodes = " << refNodeSet;
}

void ModRefInfo::dump() const
{
  print(std::cerr);
}

//----------------------------------------------------------------------------
// class FunctionModRefInfo
//----------------------------------------------------------------------------


// This constructor computes a node numbering for the TD graph.
// 
FunctionModRefInfo::FunctionModRefInfo(const Function& func,
                                       IPModRef& ipmro,
                                       DSGraph* tdgClone)
  : F(func), IPModRefObj(ipmro), 
    funcTDGraph(tdgClone),
    funcModRefInfo(tdgClone->getGraphSize())
{
  unsigned i = 0;
  for (DSGraph::node_iterator NI = funcTDGraph->node_begin(),
         E = funcTDGraph->node_end(); NI != E; ++NI)
    NodeIds[*NI] = i++;
}


FunctionModRefInfo::~FunctionModRefInfo()
{
  for(std::map<const Instruction*, ModRefInfo*>::iterator
        I=callSiteModRefInfo.begin(), E=callSiteModRefInfo.end(); I != E; ++I)
    delete(I->second);

  // Empty map just to make problems easier to track down
  callSiteModRefInfo.clear();

  delete funcTDGraph;
}

unsigned FunctionModRefInfo::getNodeId(const Value* value) const {
  return getNodeId(funcTDGraph->getNodeForValue(const_cast<Value*>(value))
                   .getNode());
}



// Compute Mod/Ref bit vectors for the entire function.
// These are simply copies of the Read/Write flags from the nodes of
// the top-down DS graph.
// 
void FunctionModRefInfo::computeModRef(const Function &func)
{
  // Mark all nodes in the graph that are marked MOD as being mod
  // and all those marked REF as being ref.
  unsigned i = 0;
  for (DSGraph::node_iterator NI = funcTDGraph->node_begin(),
         E = funcTDGraph->node_end(); NI != E; ++NI, ++i) {
    if ((*NI)->isModified()) funcModRefInfo.setNodeIsMod(i);
    if ((*NI)->isRead())     funcModRefInfo.setNodeIsRef(i);
  }

  // Compute the Mod/Ref info for all call sites within the function.
  // The call sites are recorded in the TD graph.
  const std::vector<DSCallSite>& callSites = funcTDGraph->getFunctionCalls();
  for (unsigned i = 0, N = callSites.size(); i < N; ++i)
    computeModRef(callSites[i].getCallSite());
}


// ResolveCallSiteModRefInfo - This method performs the following actions:
//
//  1. It clones the top-down graph for the current function
//  2. It clears all of the mod/ref bits in the cloned graph
//  3. It then merges the bottom-up graph(s) for the specified call-site into
//     the clone (bringing new mod/ref bits).
//  4. It returns the clone, and a mapping of nodes from the original TDGraph to
//     the cloned graph with Mod/Ref info for the callsite.
//
// NOTE: Because this clones a dsgraph and returns it, the caller is responsible
//       for deleting the returned graph!
// NOTE: This method may return a null pointer if it is unable to determine the
//       requested information (because the call site calls an external
//       function or we cannot determine the complete set of functions invoked).
//
DSGraph* FunctionModRefInfo::ResolveCallSiteModRefInfo(CallSite CS,
                               hash_map<const DSNode*, DSNodeHandle> &NodeMap)
{
  // Step #0: Quick check if we are going to fail anyway: avoid
  // all the graph cloning and map copying in steps #1 and #2.
  // 
  if (const Function *F = CS.getCalledFunction()) {
    if (F->isExternal())
      return 0;   // We cannot compute Mod/Ref info for this callsite...
  } else {
    // Eventually, should check here if any callee is external.
    // For now we are not handling this case anyway.
    std::cerr << "IP Mod/Ref indirect call not implemented yet: "
              << "Being conservative\n";
    return 0;   // We cannot compute Mod/Ref info for this callsite...
  }

  // Step #1: Clone the top-down graph...
  DSGraph *Result = new DSGraph(*funcTDGraph, NodeMap);

  // Step #2: Clear Mod/Ref information...
  Result->maskNodeTypes(~(DSNode::Modified | DSNode::Read));

  // Step #3: clone the bottom up graphs for the callees into the caller graph
  if (Function *F = CS.getCalledFunction())
    {
      assert(!F->isExternal());

      // Build up a DSCallSite for our invocation point here...

      // If the call returns a value, make sure to merge the nodes...
      DSNodeHandle RetVal;
      if (DS::isPointerType(CS.getInstruction()->getType()))
        RetVal = Result->getNodeForValue(CS.getInstruction());

      // Populate the arguments list...
      std::vector<DSNodeHandle> Args;
      for (CallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end();
           I != E; ++I)
        if (DS::isPointerType((*I)->getType()))
          Args.push_back(Result->getNodeForValue(*I));

      // Build the call site...
      DSCallSite NCS(CS, RetVal, F, Args);

      // Perform the merging now of the graph for the callee, which will
      // come with mod/ref bits set...
      Result->mergeInGraph(NCS, *F, IPModRefObj.getBUDSGraph(*F),
                           DSGraph::StripAllocaBit
                           | DSGraph::DontCloneCallNodes
                           | DSGraph::DontCloneAuxCallNodes);
    }
  else
    assert(0 && "See error message");

  // Remove dead nodes aggressively to match the caller's original graph.
  Result->removeDeadNodes(DSGraph::KeepUnreachableGlobals);

  // Step #4: Return the clone + the mapping (by ref)
  return Result;
}

// Compute Mod/Ref bit vectors for a single call site.
// These are copies of the Read/Write flags from the nodes of
// the graph produced by clearing all flags in the caller's TD graph
// and then inlining the callee's BU graph into the caller's TD graph.
// 
void
FunctionModRefInfo::computeModRef(CallSite CS)
{
  // Allocate the mod/ref info for the call site.  Bits automatically cleared.
  ModRefInfo* callModRefInfo = new ModRefInfo(funcTDGraph->getGraphSize());
  callSiteModRefInfo[CS.getInstruction()] = callModRefInfo;

  // Get a copy of the graph for the callee with the callee inlined
  hash_map<const DSNode*, DSNodeHandle> NodeMap;
  DSGraph* csgp = ResolveCallSiteModRefInfo(CS, NodeMap);
  if (!csgp)
    { // Callee's side effects are unknown: mark all nodes Mod and Ref.
      // Eventually this should only mark nodes visible to the callee, i.e.,
      // exclude stack variables not reachable from any outgoing argument
      // or any global.
      callModRefInfo->getModSet().set();
      callModRefInfo->getRefSet().set();
      return;
    }

  // For all nodes in the graph, extract the mod/ref information
  for (DSGraph::node_iterator NI = funcTDGraph->node_begin(),
         E = funcTDGraph->node_end(); NI != E; ++NI) { 
    DSNode* csgNode = NodeMap[*NI].getNode();
    assert(csgNode && "Inlined and original graphs do not correspond!");
    if (csgNode->isModified())
      callModRefInfo->setNodeIsMod(getNodeId(*NI));
    if (csgNode->isRead())
      callModRefInfo->setNodeIsRef(getNodeId(*NI));
  }

  // Drop nodemap before we delete the graph...
  NodeMap.clear();
  delete csgp;
}


class DSGraphPrintHelper {
  const DSGraph& tdGraph;
  std::vector<std::vector<const Value*> > knownValues; // identifiable objects

public:
  /*ctor*/ DSGraphPrintHelper(const FunctionModRefInfo& fmrInfo)
    : tdGraph(fmrInfo.getFuncGraph())
  {
    knownValues.resize(tdGraph.getGraphSize());

    // For every identifiable value, save Value pointer in knownValues[i]
    for (hash_map<Value*, DSNodeHandle>::const_iterator
           I = tdGraph.getScalarMap().begin(),
           E = tdGraph.getScalarMap().end(); I != E; ++I)
      if (isa<GlobalValue>(I->first) ||
          isa<Argument>(I->first) ||
          isa<LoadInst>(I->first) ||
          isa<AllocaInst>(I->first) ||
          isa<MallocInst>(I->first))
        {
          unsigned nodeId = fmrInfo.getNodeId(I->second.getNode());
          knownValues[nodeId].push_back(I->first);
        }
  }

  void printValuesInBitVec(std::ostream &O, const BitSetVector& bv) const
  {
    assert(bv.size() == knownValues.size());

    if (bv.none())
      { // No bits are set: just say so and return
        O << "\tNONE.\n";
        return;
      }

    if (bv.all())
      { // All bits are set: just say so and return
        O << "\tALL GRAPH NODES.\n";
        return;
      }

    for (unsigned i=0, N=bv.size(); i < N; ++i)
      if (bv.test(i))
        {
          O << "\tNode# " << i << " : ";
          if (! knownValues[i].empty())
            for (unsigned j=0, NV=knownValues[i].size(); j < NV; j++)
              {
                const Value* V = knownValues[i][j];

                if      (isa<GlobalValue>(V))  O << "(Global) ";
                else if (isa<Argument>(V))     O << "(Target of FormalParm) ";
                else if (isa<LoadInst>(V))     O << "(Target of LoadInst  ) ";
                else if (isa<AllocaInst>(V))   O << "(Target of AllocaInst) ";
                else if (isa<MallocInst>(V))   O << "(Target of MallocInst) ";

                if (V->hasName())             O << V->getName();
                else if (isa<Instruction>(V)) O << *V;
                else                          O << "(Value*) 0x" << (void*) V;

                O << std::string((j < NV-1)? "; " : "\n");
              }
#if 0
          else
            tdGraph.getNodes()[i]->print(O, /*graph*/ NULL);
#endif
        }
  }
};


// Print the results of the pass.
// Currently this just prints bit-vectors and is not very readable.
// 
void FunctionModRefInfo::print(std::ostream &O) const
{
  DSGraphPrintHelper DPH(*this);

  O << "========== Mod/ref information for function "
    << F.getName() << "========== \n\n";

  // First: Print Globals and Locals modified anywhere in the function.
  // 
  O << "  -----Mod/Ref in the body of function " << F.getName()<< ":\n";

  O << "    --Objects modified in the function body:\n";
  DPH.printValuesInBitVec(O, funcModRefInfo.getModSet());

  O << "    --Objects referenced in the function body:\n";
  DPH.printValuesInBitVec(O, funcModRefInfo.getRefSet());

  O << "    --Mod and Ref vectors for the nodes listed above:\n";
  funcModRefInfo.print(O, "\t");

  O << "\n";

  // Second: Print Globals and Locals modified at each call site in function
  // 
  for (std::map<const Instruction *, ModRefInfo*>::const_iterator
         CI = callSiteModRefInfo.begin(), CE = callSiteModRefInfo.end();
       CI != CE; ++CI)
    {
      O << "  ----Mod/Ref information for call site\n" << *CI->first;

      O << "    --Objects modified at call site:\n";
      DPH.printValuesInBitVec(O, CI->second->getModSet());

      O << "    --Objects referenced at call site:\n";
      DPH.printValuesInBitVec(O, CI->second->getRefSet());

      O << "    --Mod and Ref vectors for the nodes listed above:\n";
      CI->second->print(O, "\t");

      O << "\n";
    }

  O << "\n";
}

void FunctionModRefInfo::dump() const
{
  print(std::cerr);
}


//----------------------------------------------------------------------------
// class IPModRef: An interprocedural pass that computes IP Mod/Ref info.
//----------------------------------------------------------------------------

// Free the FunctionModRefInfo objects cached in funcToModRefInfoMap.
// 
void IPModRef::releaseMemory()
{
  for(std::map<const Function*, FunctionModRefInfo*>::iterator
        I=funcToModRefInfoMap.begin(), E=funcToModRefInfoMap.end(); I != E; ++I)
    delete(I->second);

  // Clear map so memory is not re-released if we are called again
  funcToModRefInfoMap.clear();
}

// Run the "interprocedural" pass on each function.  This needs to do
// NO real interprocedural work because all that has been done the
// data structure analysis.
// 
bool IPModRef::run(Module &theModule)
{
  M = &theModule;

  for (Module::const_iterator FI = M->begin(), FE = M->end(); FI != FE; ++FI)
    if (! FI->isExternal())
      getFuncInfo(*FI, /*computeIfMissing*/ true);
  return true;
}


FunctionModRefInfo& IPModRef::getFuncInfo(const Function& func,
                                          bool computeIfMissing)
{
  FunctionModRefInfo*& funcInfo = funcToModRefInfoMap[&func];
  assert (funcInfo != NULL || computeIfMissing);
  if (funcInfo == NULL)
    { // Create a new FunctionModRefInfo object.
      // Clone the top-down graph and remove any dead nodes first, because
      // otherwise original and merged graphs will not match.
      // The memory for this graph clone will be freed by FunctionModRefInfo.
      DSGraph* funcTDGraph =
        new DSGraph(getAnalysis<TDDataStructures>().getDSGraph(func));
      funcTDGraph->removeDeadNodes(DSGraph::KeepUnreachableGlobals);

      funcInfo = new FunctionModRefInfo(func, *this, funcTDGraph); //auto-insert
      funcInfo->computeModRef(func);  // computes the mod/ref info
    }
  return *funcInfo;
}

/// getBUDSGraph - This method returns the BU data structure graph for F through
/// the use of the BUDataStructures object.
///
const DSGraph &IPModRef::getBUDSGraph(const Function &F) {
  return getAnalysis<BUDataStructures>().getDSGraph(F);
}


// getAnalysisUsage - This pass requires top-down data structure graphs.
// It modifies nothing.
// 
void IPModRef::getAnalysisUsage(AnalysisUsage &AU) const {
  AU.setPreservesAll();
  AU.addRequired<LocalDataStructures>();
  AU.addRequired<BUDataStructures>();
  AU.addRequired<TDDataStructures>();
}


void IPModRef::print(std::ostream &O) const
{
  O << "\nRESULTS OF INTERPROCEDURAL MOD/REF ANALYSIS:\n\n";
  
  for (std::map<const Function*, FunctionModRefInfo*>::const_iterator
         mapI = funcToModRefInfoMap.begin(), mapE = funcToModRefInfoMap.end();
       mapI != mapE; ++mapI)
    mapI->second->print(O);

  O << "\n";
}


void IPModRef::dump() const
{
  print(std::cerr);
}

} // End llvm namespace