//===- DSNodeEquivs.cpp -  Build DSNode equivalence classes ---------------===//
//
//                     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 file implements a pass to compute DSNode equivalence classes across
// DSGraphs.
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "dsnodeequivs"

#include "assistDS/DSNodeEquivs.h"

#include "llvm/IR/Constants.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/InstIterator.h"
#include "llvm/ADT/SmallSet.h"

#include <deque>

namespace llvm {

char DSNodeEquivs::ID = 0;

static RegisterPass<DSNodeEquivs>
X("dsnodeequivs", "Compute DSNode equivalence classes");

// Build equivalence classes of DSNodes that are mapped between graphs.
void DSNodeEquivs::buildDSNodeEquivs(Module &M) {
  TDDataStructures &TDDS = getAnalysis<TDDataStructures>();

  Module::iterator FuncIt = M.begin(), FuncItEnd = M.end();
  for (; FuncIt != FuncItEnd; ++FuncIt) {
    Function &F = *FuncIt;

    if (!TDDS.hasDSGraph(F))
      continue;

    inst_iterator InstIt = inst_begin(F), InstItEnd = inst_end(F);
    for (; InstIt != InstItEnd; ++InstIt) {
      if (CallInst *Call = dyn_cast<CallInst>(&*InstIt)) {
        equivNodesThroughCallsite(Call);
      }
    }

    DSGraph *Graph = TDDS.getDSGraph(F);

    // Ensure all nodes from this function's graph are in an equivalence class.
    addNodesFromGraph(Graph);

    equivNodesToGlobals(Graph);
  }

  // Ensure all nodes from the globals graph are in an equivalence class.
  addNodesFromGraph(TDDS.getGlobalsGraph());
}

// Add nodes from the given graph into the equivalence classes.
void DSNodeEquivs::addNodesFromGraph(DSGraph *Graph) {
  DSGraph::node_iterator NodeIt = Graph->node_begin();
  DSGraph::node_iterator NodeItEnd = Graph->node_end();
  for (; NodeIt != NodeItEnd; ++NodeIt)
    Classes.insert(&*NodeIt);
}

FunctionList DSNodeEquivs::getCallees(CallSite &CS) {
  const Function *CalledFunc = CS.getCalledFunction();

  // If the called function is casted from one function type to another, peer
  // into the cast instruction and pull out the actual function being called.
  if (ConstantExpr *CExpr = dyn_cast<ConstantExpr>(CS.getCalledValue())) {
    if (CExpr->getOpcode() == Instruction::BitCast &&
        isa<Function>(CExpr->getOperand(0)))
      CalledFunc = cast<Function>(CExpr->getOperand(0));
  }

  FunctionList Callees;

  // Direct calls are simple.
  if (CalledFunc) {
    Callees.push_back(CalledFunc);
    return Callees;
  }

  // Okay, indirect call.
  // Ask the DSCallGraph what this calls...

  TDDataStructures &TDDS = getAnalysis<TDDataStructures>();
  const DSCallGraph &DSCG = TDDS.getCallGraph();

  DSCallGraph::callee_iterator CalleeIt = DSCG.callee_begin(CS);
  DSCallGraph::callee_iterator CalleeItEnd = DSCG.callee_end(CS);
  for (; CalleeIt != CalleeItEnd; ++CalleeIt)
    Callees.push_back(*CalleeIt);

  // If the callgraph doesn't give us what we want, query the DSGraph
  // ourselves.
  if (Callees.empty()) {
    Instruction *Inst = CS.getInstruction();
    Function *Parent = Inst->getParent()->getParent();
    Value *CalledValue = CS.getCalledValue();
    DSNodeHandle &NH = TDDS.getDSGraph(*Parent)->getNodeForValue(CalledValue);

    if (!NH.isNull()) {
      DSNode *Node = NH.getNode();
      Node->addFullFunctionList(Callees);
    }
  }

  // For debugging, dump out the callsites we are unable to get callees for.
  DEBUG(
  if (Callees.empty()) {
    errs() << "Failed to get callees for callsite:\n";
    CS.getInstruction()->dump();
  });

  return Callees;
}

// Compute mappings through the given call site.
void DSNodeEquivs::equivNodesThroughCallsite(CallInst *CI) {
  TDDataStructures &TDDS = getAnalysis<TDDataStructures>();
  DSGraph &Graph = *TDDS.getDSGraph(*CI->getParent()->getParent());
  CallSite CS(CI);
  FunctionList Callees = getCallees(CS);

  FunctionList_it CalleeIt = Callees.begin(), CalleeItEnd = Callees.end();
  for (; CalleeIt != CalleeItEnd; ++CalleeIt) {
    const Function &Callee = **CalleeIt;

    // We can't merge through graphs that don't exist.
    if (!TDDS.hasDSGraph(Callee))
      continue;
    
    DSGraph &CalleeGraph = *TDDS.getDSGraph(Callee);
    DSGraph::NodeMapTy NodeMap;

    // Heavily lifted/inspired by PA code

    // Map arguments
    Function::const_arg_iterator FArgIt = Callee.arg_begin();
    Function::const_arg_iterator FArgItEnd = Callee.arg_end();
    CallSite::arg_iterator ArgIt = CS.arg_begin(), ArgItEnd = CS.arg_end();
    for (; FArgIt != FArgItEnd && ArgIt != ArgItEnd; ++FArgIt, ++ArgIt) {
      if (isa<Constant>(*ArgIt))
        continue;

      DSNodeHandle &CalleeArgNH = CalleeGraph.getNodeForValue(FArgIt);
      DSNodeHandle &CSArgNH = Graph.getNodeForValue(*ArgIt);
      DSGraph::computeNodeMapping(CalleeArgNH, CSArgNH, NodeMap, false);
    }

    // Map return value
    if (isa<PointerType>(CI->getType())) {
      DSNodeHandle &CalleeRetNH = CalleeGraph.getReturnNodeFor(Callee);
      DSNodeHandle &CINH = Graph.getNodeForValue(CI);
      DSGraph::computeNodeMapping(CalleeRetNH, CINH, NodeMap, false);
    }

    // Merge information from the computed node mapping into the equivalence
    // classes.
    equivNodeMapping(NodeMap);
  }
}

// Compute mappings with the globals graph.
void DSNodeEquivs::equivNodesToGlobals(DSGraph *G) {
  DSGraph *GlobalsGr = G->getGlobalsGraph();
  DSGraph::NodeMapTy NodeMap;
  DSScalarMap &ScalarMap = GlobalsGr->getScalarMap();

  DSScalarMap::global_iterator GlobalIt = ScalarMap.global_begin();
  DSScalarMap::global_iterator GlobalItEnd = ScalarMap.global_end();
  for (; GlobalIt != GlobalItEnd; ++GlobalIt) {
    const GlobalValue *Global = *GlobalIt;

    DSNode *LocalNode = G->getNodeForValue(Global).getNode();

    // It's quite possible this (local) graph doesn't have this global.
    // If that's the case, there's nothing to do here.
    if (!LocalNode) continue;

    DSNode *GlobalNode = GlobalsGr->getNodeForValue(Global).getNode();
    assert(GlobalNode && "No node for global in global scalar map?");

    // Map the two together and all reachable from each...
    NodeMap.clear();
    DSGraph::computeNodeMapping(LocalNode, GlobalNode, NodeMap, false);

    // Build EC's with this mapping.
    equivNodeMapping(NodeMap);
  }
}

// Utility function to put nodes that map together into equivalence classes.
void DSNodeEquivs::equivNodeMapping(DSGraph::NodeMapTy &NodeMap) {
  DSGraph::NodeMapTy::iterator NodeMapIt = NodeMap.begin();
  DSGraph::NodeMapTy::iterator NodeMapItEnd = NodeMap.end();
  for (; NodeMapIt != NodeMapItEnd; ++NodeMapIt) {
    DSNodeHandle &NH = NodeMapIt->second;
    if (NH.isNull())
      continue;

    const DSNode *N1 = NodeMapIt->first;
    const DSNode *N2 = NH.getNode();

    Classes.unionSets(N1, N2);
  }
}

bool DSNodeEquivs::runOnModule(Module &M) {
  buildDSNodeEquivs(M);
  // Does not modify module.
  return false;
}

// Returns the computed equivalence classes.
const EquivalenceClasses<const DSNode *> &
DSNodeEquivs::getEquivalenceClasses() {
  return Classes;
}

// Returns a DSNode for the specified value.
// Returns null for a node that was not found.
const DSNode *DSNodeEquivs::getMemberForValue(const Value *V) {
  TDDataStructures &TDDS = getAnalysis<TDDataStructures>();
  DSNodeHandle *NHForV = 0;

  if (isa<GlobalValue>(V)) {
    NHForV = &TDDS.getGlobalsGraph()->getNodeForValue(V);
  } else if (isa<Instruction>(V)) {
    const Function *Parent = cast<Instruction>(V)->getParent()->getParent();
    NHForV = &TDDS.getDSGraph(*Parent)->getNodeForValue(V);
  } else if (isa<Argument>(V)) {
    const Function *Parent = cast<Argument>(V)->getParent();
    NHForV = &TDDS.getDSGraph(*Parent)->getNodeForValue(V);
  } else {
    //
    // Iterate over the users to attempt to discover a DSNode that the value
    // maps to.
    //
    std::deque<const User *> WL;
    SmallSet<const User *, 8> Visited;

    WL.insert(WL.end(), V->user_begin(), V->user_end());
    do {
      const User *TheUser = WL.front();
      WL.pop_front();

      if (!Visited.insert(TheUser))
        continue;

      //
      // If the use is a global variable or instruction, then the value should
      // be in the corresponding DSGraph.
      //
      // TODO: Is it possible for a value to belong to some DSGraph and never
      // be relied upon by a GlobalValue or Instruction?
      //
      if (const Instruction *I = dyn_cast<Instruction>(TheUser)) {
        const Function *Parent = I->getParent()->getParent();
        NHForV = &TDDS.getDSGraph(*Parent)->getNodeForValue(V);
        break;
      } else if (isa<GlobalValue>(TheUser)) {
        NHForV = &TDDS.getGlobalsGraph()->getNodeForValue(V);
        break;
      } else {
        //
        // If this use is of some other nature, look at the users of this use.
        //
        WL.insert(WL.end(), TheUser->user_begin(), TheUser->user_end());
      }
    } while (!WL.empty());
  }

  assert(NHForV && "Unable to find node handle for given value!");

  return NHForV->getNode();
}

}