poolalloc/lib/rDSA/EquivClassGraphs.cpp

//===- EquivClassGraphs.cpp - Merge equiv-class graphs & inline bottom-up -===//
//
//                     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 pass is the same as the complete bottom-up graphs, but
// with functions partitioned into equivalence classes and a single merged
// DS graph for all functions in an equivalence class.  After this merging,
// graphs are inlined bottom-up on the SCCs of the final (CBU) call graph.
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "ECGraphs"
#include "rdsa/DataStructure.h"
#include "llvm/DerivedTypes.h"
#include "llvm/Module.h"
#include "llvm/Pass.h"
#include "rdsa/DSGraph.h"
#include "llvm/IR/CallSite.h"
#include "llvm/Support/Debug.h"
#include "llvm/ADT/SCCIterator.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/EquivalenceClasses.h"
#include "llvm/ADT/STLExtras.h"
using namespace llvm;

namespace {
  RegisterPass<EquivBUDataStructures> X("dsa-eq",
                    "Equivalence-class Bottom-up Data Structure Analysis");
}

char EquivBUDataStructures::ID = 0;

// runOnModule - Calculate the bottom up data structure graphs for each function
// in the program.
//
bool EquivBUDataStructures::runOnModule(Module &M) {
  init(&getAnalysis<CompleteBUDataStructures>(), false, true, false, true);

  //update the EQ class from indirect calls
  buildIndirectFunctionSets(M);

  mergeGraphsByGlobalECs();

  return runOnModuleInternal(M);
}


// Merge all graphs that are in the same equivalence class
// the ensures things like poolalloc only deal with one graph for a 
// call site
void EquivBUDataStructures::mergeGraphsByGlobalECs() {
  // Merge the graphs for each equivalence class.
  //
  for (EquivalenceClasses<const GlobalValue*>::iterator EQSI = GlobalECs.begin(), 
         EQSE = GlobalECs.end(); EQSI != EQSE; ++EQSI) {
    if (!EQSI->isLeader()) continue;
    DSGraph* BaseGraph = 0;
    std::vector<DSNodeHandle> Args;
    for (EquivalenceClasses<const GlobalValue*>::member_iterator MI = GlobalECs.member_begin(EQSI);
         MI != GlobalECs.member_end(); ++MI) {
      if (const Function* F = dyn_cast<Function>(*MI)) {
        if (!BaseGraph) {
          BaseGraph = getOrFetchDSGraph(F);
          BaseGraph->getFunctionArgumentsForCall(F, Args);
        } else if (BaseGraph->containsFunction(F)) {
          //already merged
        } else {
          std::vector<DSNodeHandle> NextArgs;
          BaseGraph->cloneInto(getOrFetchDSGraph(F));
          BaseGraph->getFunctionArgumentsForCall(F, NextArgs);
          unsigned i = 0, e = Args.size();
          for (; i != e; ++i) {
            if (i == NextArgs.size()) break;
            Args[i].mergeWith(NextArgs[i]);
          }
          for (e = NextArgs.size(); i != e; ++i)
            Args.push_back(NextArgs[i]);
          setDSGraph(F, BaseGraph);
        }       
      }
    }
  }
}