//===- DSCallGaph.h - Build call graphs -------------------------*- 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.
//
//===----------------------------------------------------------------------===//
//
// Implement a detailed call graph for DSA.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_DSCALLGRAPH_H
#define	LLVM_DSCALLGRAPH_H

#include "dsa/svset.h"
#include "dsa/keyiterator.h"
#include <map>

//Fix in 2.8, EQC includes cassert
#include <cassert>
#include "llvm/ADT/EquivalenceClasses.h"
#include "llvm/Support/CallSite.h"


class DSCallGraph {
public:
  typedef svset<const llvm::Function*> FuncSet;
  typedef std::map<llvm::CallSite, FuncSet> ActualCalleesTy;
  typedef std::map<const llvm::Function*, FuncSet> SimpleCalleesTy;

private:
  //ActualCallees contains CallSite -> Function mappings
  ActualCalleesTy ActualCallees;
  //SimpleCallees contains Function -> Function mappings
  SimpleCalleesTy SimpleCallees;

  //These are used for returning empty sets when the caller has no callees
  FuncSet EmptyActual;
  FuncSet EmptySimple;

  //An equivalence class is exactly an SCC
  llvm::EquivalenceClasses<const llvm::Function*> SCCs;

  //Functions we know about that aren't called
  svset<const llvm::Function*> knownRoots;

  svset<llvm::CallSite> completeCS;

  //Types for SCC construction
  typedef std::map<const llvm::Function*, unsigned> TFMap;
  typedef std::vector<const llvm::Function*> TFStack;

  // Tarjan's SCC algorithm
  unsigned tarjan_rec(const llvm::Function* F, TFStack& Stack, unsigned &NextID,
                      TFMap& ValMap);

  void removeECFunctions();

public:

  DSCallGraph() {}

  typedef ActualCalleesTy::mapped_type::const_iterator callee_iterator;
  typedef KeyIterator<ActualCalleesTy::const_iterator> callee_key_iterator;
  typedef SimpleCalleesTy::mapped_type::const_iterator flat_iterator;
  typedef KeyIterator<SimpleCalleesTy::const_iterator> flat_key_iterator;
  typedef FuncSet::const_iterator                      root_iterator;
  typedef llvm::EquivalenceClasses<const llvm::Function*>::member_iterator scc_iterator;

  void insert(llvm::CallSite CS, const llvm::Function* F);

  void insureEntry(const llvm::Function* F);

  template<class Iterator>
  void insert(llvm::CallSite CS, Iterator _begin, Iterator _end) {
    for (; _begin != _end; ++_begin)
      insert(CS, *_begin);
  }

  callee_iterator callee_begin(llvm::CallSite CS) const {
    ActualCalleesTy::const_iterator ii = ActualCallees.find(CS);
    if (ii == ActualCallees.end())
      return EmptyActual.end();
    return ii->second.begin();
  }

  callee_iterator callee_end(llvm::CallSite CS) const {
    ActualCalleesTy::const_iterator ii = ActualCallees.find(CS);
    if (ii == ActualCallees.end())
      return EmptyActual.end();
    return ii->second.end();
  }

  callee_key_iterator key_begin() const {
    return callee_key_iterator(ActualCallees.begin());
  }

  callee_key_iterator key_end() const {
    return callee_key_iterator(ActualCallees.end());
  }

  flat_iterator flat_callee_begin(const llvm::Function* F) const {
    SimpleCalleesTy::const_iterator ii = SimpleCallees.find(F);
    if (ii == SimpleCallees.end())
      return EmptySimple.end();
    return ii->second.begin();
  }

  flat_iterator flat_callee_end(const llvm::Function* F) const {
    SimpleCalleesTy::const_iterator ii = SimpleCallees.find(F);
    if (ii == SimpleCallees.end())
      return EmptySimple.end();
    return ii->second.end();
  }

  flat_key_iterator flat_key_begin() const {
    return flat_key_iterator(SimpleCallees.begin());
  }

  flat_key_iterator flat_key_end() const {
    return flat_key_iterator(SimpleCallees.end());
  }

  root_iterator root_begin() const {
    return knownRoots.begin();
  }

  root_iterator root_end() const {
    return knownRoots.end();
  }

  scc_iterator scc_begin(const llvm::Function* F) const {
    assert(F == SCCs.getLeaderValue(F) && "Requested non-leader");
    return SCCs.member_begin(SCCs.findValue(F));
  }

  scc_iterator scc_end(const llvm::Function* F) const {
    assert(F == SCCs.getLeaderValue(F) && "Requested non-leader");
    return SCCs.member_end();
  }


  unsigned callee_size(llvm::CallSite CS) const {
    ActualCalleesTy::const_iterator ii = ActualCallees.find(CS);
    if (ii == ActualCallees.end())
      return 0;
    return ii->second.size();
  }

  void callee_mark_complete(llvm::CallSite CS) {
    completeCS.insert(CS);
  }

  bool callee_is_complete(llvm::CallSite CS) const {
    return completeCS.find(CS) != completeCS.end();
  }

  unsigned size() const {
    unsigned sum = 0;
    for (ActualCalleesTy::const_iterator ii = ActualCallees.begin(),
            ee = ActualCallees.end(); ii != ee; ++ii)
      sum += ii->second.size();
    return sum;
  }

  unsigned flat_size() const {
    return SimpleCallees.size();
  }

  void buildSCCs();

  void buildRoots();

  void dump();

  void assertSCCRoot(const llvm::Function* F) {
    assert(F == SCCs.getLeaderValue(F) && "Not Leader?");
  }

  //common helper, no good reason for it to be here rather than elsewhere
  static bool hasPointers(const llvm::Function* F);
  static bool hasPointers(llvm::CallSite& CS);

};

#endif	/* LLVM_DSCALLGRAPH_H */