<commit_before>//===- BottomUpClosure.cpp - Compute bottom-up interprocedural closure ----===//
//
// This file implements the BUDataStructures class, which represents the
// Bottom-Up Interprocedural closure of the data structure graph over the
// program.  This is useful for applications like pool allocation, but **not**
// applications like alias analysis.
//
//===----------------------------------------------------------------------===//

#include "llvm/Analysis/DataStructure.h"
#include "llvm/Analysis/DSGraph.h"
#include "llvm/Module.h"
//#include "llvm/DerivedTypes.h"
#include "Support/Statistic.h"
//#include <set>
using std::map;

static RegisterAnalysis<BUDataStructures>
X("budatastructure", "Bottom-up Data Structure Analysis Closure");

// TODO: FIXME
namespace DataStructureAnalysis {
  // isPointerType - Return true if this first class type is big enough to hold
  // a pointer.
  //
  bool isPointerType(const Type *Ty);
}
using namespace DataStructureAnalysis;


// releaseMemory - If the pass pipeline is done with this pass, we can release
// our memory... here...
//
void BUDataStructures::releaseMemory() {
  for (map<const Function*, DSGraph*>::iterator I = DSInfo.begin(),
         E = DSInfo.end(); I != E; ++I)
    delete I->second;

  // Empty map so next time memory is released, data structures are not
  // re-deleted.
  DSInfo.clear();
}

// run - Calculate the bottom up data structure graphs for each function in the
// program.
//
bool BUDataStructures::run(Module &M) {
  // Simply calculate the graphs for each function...
  for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
    if (!I->isExternal())
      calculateGraph(*I);
  return false;
}

// ResolveArguments - Resolve the formal and actual arguments for a function
// call.
//
static void ResolveArguments(std::vector<DSNodeHandle> &Call, Function &F,
                             map<Value*, DSNodeHandle> &ValueMap) {
  // Resolve all of the function arguments...
  Function::aiterator AI = F.abegin();
  for (unsigned i = 2, e = Call.size(); i != e; ++i) {
    // Advance the argument iterator to the first pointer argument...
    while (!isPointerType(AI->getType())) ++AI;
    
    // Add the link from the argument scalar to the provided value
    DSNodeHandle &NN = ValueMap[AI];
    NN.addEdgeTo(Call[i]);
    ++AI;
  }
}

// MergeGlobalNodes - Merge all existing global nodes with globals
// inlined from the callee or with globals from the GlobalsGraph.
//
static void MergeGlobalNodes(DSGraph &Graph,
                             map<Value*, DSNodeHandle> &OldValMap) {
  map<Value*, DSNodeHandle> &ValMap = Graph.getValueMap();
  for (map<Value*, DSNodeHandle>::iterator I = ValMap.begin(), E = ValMap.end();
       I != E; ++I)
    if (GlobalValue *GV = dyn_cast<GlobalValue>(I->first)) {
      map<Value*, DSNodeHandle>::iterator NHI = OldValMap.find(GV);
      if (NHI != OldValMap.end())       // was it inlined from the callee?
        I->second.mergeWith(NHI->second);
#if 0
      else                              // get it from the GlobalsGraph
        I->second.mergeWith(Graph.cloneGlobalInto(GV));
#endif
    }

  // Add unused inlined global nodes into the value map
  for (map<Value*, DSNodeHandle>::iterator I = OldValMap.begin(),
         E = OldValMap.end(); I != E; ++I)
    if (isa<GlobalValue>(I->first)) {
      DSNodeHandle &NH = ValMap[I->first];  // If global is not in ValMap...
      if (NH.getNode() == 0)
        NH = I->second;                     // Add the one just inlined.
    }

}

DSGraph &BUDataStructures::calculateGraph(Function &F) {
  // Make sure this graph has not already been calculated, or that we don't get
  // into an infinite loop with mutually recursive functions.
  //
  DSGraph *&Graph = DSInfo[&F];
  if (Graph) return *Graph;

  // Copy the local version into DSInfo...
  Graph = new DSGraph(getAnalysis<LocalDataStructures>().getDSGraph(F));

#if 0
  // Populate the GlobalsGraph with globals from this one.
  Graph->GlobalsGraph->cloneGlobals(*Graph, /*cloneCalls*/ false);

  // Save a copy of the original call nodes for the top-down pass
  Graph->saveOrigFunctionCalls();
#endif

  // Start resolving calls...
  std::vector<std::vector<DSNodeHandle> > &FCs = Graph->getFunctionCalls();

  DEBUG(std::cerr << "  [BU] Inlining: " << F.getName() << "\n");

#if 0
  // Add F to the PendingCallers list of each direct callee for use in the
  // top-down pass so we don't have to compute this again.  We don't want
  // to do it for indirect callees inlined later, so remember which calls
  // are in the original FCs set.
  std::set<const DSNode*> directCallees;
  for (unsigned i = 0; i < FCs.size(); ++i)
    directCallees.insert(FCs[i][1]); // ptr to function node
#endif

  bool Inlined;
  do {
    Inlined = false;

    for (unsigned i = 0; i != FCs.size(); ++i) {
      // Copy the call, because inlining graphs may invalidate the FCs vector.
      std::vector<DSNodeHandle> Call = FCs[i];

      // If the function list is complete...
      if ((Call[1].getNode()->NodeType & DSNode::Incomplete) == 0) {
        // Start inlining all of the functions we can... some may not be
        // inlinable if they are external...
        //
        std::vector<GlobalValue*> Callees(Call[1].getNode()->getGlobals());

        // Loop over the functions, inlining whatever we can...
        for (unsigned c = 0; c != Callees.size(); ++c) {
          // Must be a function type, so this cast MUST succeed.
          Function &FI = cast<Function>(*Callees[c]);
          if (&FI == &F) {
            // Self recursion... simply link up the formal arguments with the
            // actual arguments...

            DEBUG(std::cerr << "\t[BU] Self Inlining: " << F.getName() << "\n");

            if (Call[0].getNode()) // Handle the return value if present...
              Graph->getRetNode().mergeWith(Call[0]);

            // Resolve the arguments in the call to the actual values...
            ResolveArguments(Call, F, Graph->getValueMap());

            // Erase the entry in the callees vector
            Callees.erase(Callees.begin()+c--);
          } else if (!FI.isExternal()) {
            DEBUG(std::cerr << "\t[BU] In " << F.getName() << " inlining: "
                  << FI.getName() << "\n");
            
            // Get the data structure graph for the called function, closing it
            // if possible (which is only impossible in the case of mutual
            // recursion...
            //
            DSGraph &GI = calculateGraph(FI);  // Graph to inline

            DEBUG(std::cerr << "\t\t[BU] Got graph for " << FI.getName()<commit_msg>  * Add data structures and code to track the call sites for each function<commit_after>//===- BottomUpClosure.cpp - Compute bottom-up interprocedural closure ----===//
//
// This file implements the BUDataStructures class, which represents the
// Bottom-Up Interprocedural closure of the data structure graph over the
// program.  This is useful for applications like pool allocation, but **not**
// applications like alias analysis.
//
//===----------------------------------------------------------------------===//

#include "llvm/Analysis/DataStructure.h"
#include "llvm/Analysis/DSGraph.h"
#include "llvm/Module.h"
#include "Support/Statistic.h"
using std::map;

static RegisterAnalysis<BUDataStructures>
X("budatastructure", "Bottom-up Data Structure Analysis Closure");

// TODO: FIXME
namespace DataStructureAnalysis {
  // isPointerType - Return true if this first class type is big enough to hold
  // a pointer.
  //
  bool isPointerType(const Type *Ty);
}
using namespace DataStructureAnalysis;


// releaseMemory - If the pass pipeline is done with this pass, we can release
// our memory... here...
//
void BUDataStructures::releaseMemory() {
  // Delete all call site information
  CallSites.clear();

  for (map<const Function*, DSGraph*>::iterator I = DSInfo.begin(),
         E = DSInfo.end(); I != E; ++I)
    delete I->second;

  // Empty map so next time memory is released, data structures are not
  // re-deleted.
  DSInfo.clear();
}

// run - Calculate the bottom up data structure graphs for each function in the
// program.
//
bool BUDataStructures::run(Module &M) {
  // Simply calculate the graphs for each function...
  for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
    if (!I->isExternal())
      calculateGraph(*I);
  return false;
}

// ResolveArguments - Resolve the formal and actual arguments for a function
// call.
//
static void ResolveArguments(std::vector<DSNodeHandle> &Call, Function &F,
                             map<Value*, DSNodeHandle> &ValueMap) {
  // Resolve all of the function arguments...
  Function::aiterator AI = F.abegin();
  for (unsigned i = 2, e = Call.size(); i != e; ++i) {
    // Advance the argument iterator to the first pointer argument...
    while (!isPointerType(AI->getType())) ++AI;
    
    // Add the link from the argument scalar to the provided value
    DSNodeHandle &NN = ValueMap[AI];
    NN.addEdgeTo(Call[i]);
    ++AI;
  }
}

// MergeGlobalNodes - Merge all existing global nodes with globals
// inlined from the callee or with globals from the GlobalsGraph.
//
static void MergeGlobalNodes(DSGraph &Graph,
                             map<Value*, DSNodeHandle> &OldValMap) {
  map<Value*, DSNodeHandle> &ValMap = Graph.getValueMap();
  for (map<Value*, DSNodeHandle>::iterator I = ValMap.begin(), E = ValMap.end();
       I != E; ++I)
    if (GlobalValue *GV = dyn_cast<GlobalValue>(I->first)) {
      map<Value*, DSNodeHandle>::iterator NHI = OldValMap.find(GV);
      if (NHI != OldValMap.end())       // was it inlined from the callee?
        I->second.mergeWith(NHI->second);
#if 0
      else                              // get it from the GlobalsGraph
        I->second.mergeWith(Graph.cloneGlobalInto(GV));
#endif
    }

  // Add unused inlined global nodes into the value map
  for (map<Value*, DSNodeHandle>::iterator I = OldValMap.begin(),
         E = OldValMap.end(); I != E; ++I)
    if (isa<GlobalValue>(I->first)) {
      DSNodeHandle &NH = ValMap[I->first];  // If global is not in ValMap...
      if (NH.getNode() == 0)
        NH = I->second;                     // Add the one just inlined.
    }

}

DSGraph &BUDataStructures::calculateGraph(Function &F) {
  // Make sure this graph has not already been calculated, or that we don't get
  // into an infinite loop with mutually recursive functions.
  //
  DSGraph *&Graph = DSInfo[&F];
  if (Graph) return *Graph;

  // Copy the local version into DSInfo...
  Graph = new DSGraph(getAnalysis<LocalDataStructures>().getDSGraph(F));

#if 0
  // Populate the GlobalsGraph with globals from this one.
  Graph->GlobalsGraph->cloneGlobals(*Graph, /*cloneCalls*/ false);

  // Save a copy of the original call nodes for the top-down pass
  Graph->saveOrigFunctionCalls();
#endif

  // Start resolving calls...
  std::vector<std::vector<DSNodeHandle> > &FCs = Graph->getFunctionCalls();

  DEBUG(std::cerr << "  [BU] Inlining: " << F.getName() << "\n");

#if 0
  // Add F to the PendingCallers list of each direct callee for use in the
  // top-down pass so we don't have to compute this again.  We don't want
  // to do it for indirect callees inlined later, so remember which calls
  // are in the original FCs set.
  std::set<const DSNode*> directCallees;
  for (unsigned i = 0; i < FCs.size(); ++i)
    directCallees.insert(FCs[i][1]); // ptr to function node
#endif

  bool Inlined;
  do {
    Inlined = false;

    for (unsigned i = 0; i != FCs.size(); ++i) {
      // Copy the call, because inlining graphs may invalidate the FCs vector.
      std::vector<DSNodeHandle> Call = FCs[i];

      // If the function list is complete...
      if ((Call[1].getNode()->NodeType & DSNode::Incomplete) == 0) {
        // Start inlining all of the functions we can... some may not be
        // inlinable if they are external...
        //
        std::vector<GlobalValue*> Callees(Call[1].getNode()->getGlobals());

        // Loop over the functions, inlining whatever we can...
        for (unsigned c = 0; c != Callees.size(); ++c) {
          // Must be a function type, so this cast MUST succeed.
          Function &FI = cast<Function>(*Callees[c]);

          // Record that this is a call site of FI.
          CallSites[&FI].push_back(CallSite(F, Call));

          if (&FI == &F) {
            // Self recursion... simply link up the formal arguments with the
            // actual arguments...

            DEBUG(std::cerr << "\t[BU] Self Inlining: " << F.getName() << "\n");

            if (Call[0].getNode()) // Handle the return value if present...
              Graph->getRetNode().mergeWith(Call[0]);

            // Resolve the arguments in the call to the actual values...
            ResolveArguments(Call, F, Graph->getValueMap());

            // Erase the entry in the callees vector
            Callees.erase(Callees.begin()+c--);

          } else if (!FI.isExternal()) {
            DEBUG(std::cerr << "\t[BU] In " << F.getName() << " inlining: "
                  << FI.getName() << "\n");
            
            // Get the data structure graph for the called function, closing it
            // if possible (which is only impossible in the case of mutual
            // recursion...
            //
            DSGraph &GI = calculateGraph(FI);  // Graph to inline

            DEBUG(std::cerr << "\t\t[BU] Got graph for " << FI.getName()
{'fraction_non_alphanumeric': 0.14617496475476738, 'fraction_numerical': 0.002077613712250501, 'mean_word_length': 2.4935199585277346, 'pattern_counts': {'":': 0, '<': 94, '<?xml version=': 0, '>': 76, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1553242', 'n_tokens_mistral': 4018, 'n_tokens_neox': 3910, 'n_words': 1355}