BinaryFunctionCall.h

#ifndef ROSE_BinaryAnalysis_FunctionCall_H
#define ROSE_BinaryAnalysis_FunctionCall_H

#include <featureTests.h>
#ifdef ROSE_ENABLE_BINARY_ANALYSIS

#include "BinaryControlFlow.h"

class SgAsmFunction;

namespace Rose {
namespace BinaryAnalysis {

class FunctionCall {
public:

    FunctionCall()
        : vertex_filter(NULL), edge_filter(NULL)
        {}

    typedef boost::adjacency_list<boost::setS,                                  /* out-edges of each vertex in std::list */
                                  boost::vecS,                                  /* store vertices in std::vector */
                                  boost::bidirectionalS,                        /* call graph is directed */
                                  boost::property<boost::vertex_name_t, SgAsmFunction*>
                                 > Graph;


    /**********************************************************************************************************************
     *                                      Filters
     **********************************************************************************************************************/
public:

    class VertexFilter {
    public:
        virtual ~VertexFilter() {}
        virtual bool operator()(FunctionCall*, SgAsmFunction*) = 0;
    };

    class EdgeFilter {
    public:
        virtual ~EdgeFilter() {}
        virtual bool operator()(FunctionCall*, SgAsmFunction *source, SgAsmFunction *target) = 0;
    };

    void set_vertex_filter(VertexFilter *filter) { vertex_filter = filter; }
    VertexFilter *get_vertex_filter() const { return vertex_filter; }
    void set_edge_filter(EdgeFilter *filter) { edge_filter = filter; }
    EdgeFilter *get_edge_filter() const { return edge_filter; }
    bool is_vertex_filtered(SgAsmFunction *func, VertexFilter *filter) {
        return filter && !(*filter)(this, func);
    }
    bool is_vertex_filtered(SgAsmFunction *func) {
        return is_vertex_filtered(func, vertex_filter);
    }
    bool is_edge_filtered(SgAsmFunction *src, SgAsmFunction *dst, EdgeFilter *filter) {
        return filter && !(*filter)(this, src, dst);
    }
    bool is_edge_filtered(SgAsmFunction *src, SgAsmFunction *dst) {
        return is_edge_filtered(src, dst, edge_filter);
    }
protected:
    VertexFilter *vertex_filter;
    EdgeFilter *edge_filter;

    /**********************************************************************************************************************
     *                                      Methods that modify the AST
     **********************************************************************************************************************/
public:

    template<class FunctionCallGraph>
    void cache_vertex_descriptors(const FunctionCallGraph&);

    /**********************************************************************************************************************
     *                                      Graph construction methods
     **********************************************************************************************************************/
public:

    template<class FunctionCallGraph, class ControlFlowGraph>
    FunctionCallGraph build_cg_from_cfg(const ControlFlowGraph&);

    template<class ControlFlowGraph, class FunctionCallGraph>
    void build_cg_from_cfg(const ControlFlowGraph &cfg, FunctionCallGraph &cg/*out*/);
    template<class FunctionCallGraph>
    FunctionCallGraph build_cg_from_ast(SgNode *root);

    template<class FunctionCallGraph>
    void build_cg_from_ast(SgNode *root, FunctionCallGraph &cg/*out*/);
    template<class FunctionCallGraph>
    FunctionCallGraph copy(const FunctionCallGraph &src);
    template<class FunctionCallGraph>
    void copy(const FunctionCallGraph &src, FunctionCallGraph &dst/*out*/);
};

/******************************************************************************************************************************
 *                                      Function template definitions
 ******************************************************************************************************************************/

template<class FunctionCallGraph>
void
FunctionCall::cache_vertex_descriptors(const FunctionCallGraph &cg)
{
    typename boost::graph_traits<FunctionCallGraph>::vertex_iterator vi, vi_end;
    for (boost::tie(vi, vi_end)=boost::vertices(cg); vi!=vi_end; ++vi) {
        SgAsmFunction *func = get_ast_node(cg, *vi);
        if (func && !is_vertex_filtered(func))
            func->set_cached_vertex(*vi);
    }
}

template<class ControlFlowGraph, class FunctionCallGraph>
void
FunctionCall::build_cg_from_cfg(const ControlFlowGraph &cfg, FunctionCallGraph &cg/*out*/)
{
    typedef typename boost::graph_traits<FunctionCallGraph>::vertex_descriptor CG_Vertex;
    typedef typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor CFG_Vertex;
    typedef std::map<SgAsmFunction*, CG_Vertex> FunctionVertexMap;

    cg.clear();

    /* Add CG vertices by collapsing CFG nodes that belong to a common function. */
    FunctionVertexMap fv_map;
    typename boost::graph_traits<const ControlFlowGraph>::vertex_iterator vi, vi_end;
    for (boost::tie(vi, vi_end)=boost::vertices(cfg); vi!=vi_end; ++vi) {
        SgAsmFunction *func = SageInterface::getEnclosingNode<SgAsmFunction>(get_ast_node(cfg, *vi));
        if (!is_vertex_filtered(func)) {
            typename FunctionVertexMap::iterator fi=fv_map.find(func);
            if (func && fi==fv_map.end()) {
                CG_Vertex v = boost::add_vertex(cg);
                put_ast_node(cg, v, func);
                fv_map[func] = v;
            }
        }
    }

    /* Add edges whose target is a function entry block. */
    typename boost::graph_traits<const ControlFlowGraph>::edge_iterator ei, ei_end;
    for (boost::tie(ei, ei_end)=boost::edges(cfg); ei!=ei_end; ++ei) {
        CFG_Vertex cfg_a = boost::source(*ei, cfg);
        CFG_Vertex cfg_b = boost::target(*ei, cfg);
        SgAsmBlock *block_a = SageInterface::getEnclosingNode<SgAsmBlock>(get_ast_node(cfg, cfg_a), true/* inc. self */);
        ASSERT_not_null(block_a);
        SgAsmBlock *block_b = SageInterface::getEnclosingNode<SgAsmBlock>(get_ast_node(cfg, cfg_b), true/* inc. self */);
        ASSERT_not_null(block_b);
        SgAsmFunction *func_a = block_a->get_enclosing_function();
        SgAsmFunction *func_b = block_b->get_enclosing_function();
        if (func_a && func_b && block_b==func_b->get_entry_block() && !is_edge_filtered(func_a, func_b)) {
            typename FunctionVertexMap::iterator fi_a = fv_map.find(func_a);
            if (fi_a!=fv_map.end()) {
                typename FunctionVertexMap::iterator fi_b = fv_map.find(func_b);
                if (fi_b!=fv_map.end())
                    boost::add_edge(fi_a->second, fi_b->second, cg);
            }
        }
    }
}

template<class FunctionCallGraph, class ControlFlowGraph>
FunctionCallGraph
FunctionCall::build_cg_from_cfg(const ControlFlowGraph &cfg)
{
    FunctionCallGraph cg;
    build_cg_from_cfg(cfg, cg);
    return cg;
}

template<class FunctionCallGraph>
void
FunctionCall::build_cg_from_ast(SgNode *root, FunctionCallGraph &cg/*out*/)
{
    typedef typename boost::graph_traits<FunctionCallGraph>::vertex_descriptor Vertex;
    typedef std::map<SgAsmFunction*, Vertex> FunctionVertexMap;
    FunctionVertexMap fv_map;

    cg.clear();

    /* Visiter that adds a vertex for each unique function. */
    struct VertexAdder: public AstSimpleProcessing {
        FunctionCall *analyzer;
        FunctionCallGraph &cg;
        FunctionVertexMap &fv_map;
        VertexAdder(FunctionCall *analyzer, FunctionCallGraph &cg, FunctionVertexMap &fv_map)
            : analyzer(analyzer), cg(cg), fv_map(fv_map)
            {}
        void visit(SgNode *node) {
            SgAsmFunction *func = isSgAsmFunction(node);
            if (func && !analyzer->is_vertex_filtered(func)) {
                Vertex vertex = boost::add_vertex(cg);
                fv_map[func] = vertex;
                put_ast_node(cg, vertex, func);
            }
        }
    };

    /* Visitor that adds edges for each vertex.  Traversal should be over one function at a time. */
    struct EdgeAdder: public AstSimpleProcessing {
        FunctionCall *analyzer;
        FunctionCallGraph &cg;
        FunctionVertexMap &fv_map;
        Vertex source_vertex;
        EdgeAdder(FunctionCall *analyzer, FunctionCallGraph &cg, FunctionVertexMap &fv_map, Vertex source_vertex)
            : analyzer(analyzer), cg(cg), fv_map(fv_map), source_vertex(source_vertex)
            {}
        SgAsmFunction *function_of(SgAsmBlock *block) {
            return block ? block->get_enclosing_function() : NULL;
        }
        void visit(SgNode *node) {
            SgAsmBlock *block_a = isSgAsmBlock(node); /* the calling block */
            SgAsmFunction *func_a = function_of(block_a); /* the calling function */
            if (!func_a)
                return;
            const SgAsmIntegerValuePtrList &succs = block_a->get_successors();
            for (SgAsmIntegerValuePtrList::const_iterator si=succs.begin(); si!=succs.end(); ++si) {
                SgAsmFunction *func_b = isSgAsmFunction((*si)->get_baseNode()); // the called function
                if (func_b == NULL) {
                    SgAsmBlock *block_b = isSgAsmBlock((*si)->get_baseNode()); /* the called block */
                    func_b = function_of(block_b); /* the called function */
                    if (func_b && func_b->get_entry_va() != block_b->get_address())
                        continue;
                }
                if (func_b && !analyzer->is_edge_filtered(func_a, func_b)) {
                    typename FunctionVertexMap::iterator fi_b = fv_map.find(func_b); /* find vertex for called function */
                    if (fi_b!=fv_map.end())
                        boost::add_edge(source_vertex, fi_b->second, cg);
                }
            }
        }
    };

    VertexAdder(this, cg, fv_map).traverse(root, preorder);
    typename boost::graph_traits<FunctionCallGraph>::vertex_iterator vi, vi_end;
    for (boost::tie(vi, vi_end)=boost::vertices(cg); vi!=vi_end; ++vi) {
        SgAsmFunction *source_func = get_ast_node(cg, *vi);
        EdgeAdder(this, cg, fv_map, *vi).traverse(source_func, preorder);
    }
}

template<class FunctionCallGraph>
FunctionCallGraph
FunctionCall::build_cg_from_ast(SgNode *root)
{
    FunctionCallGraph cg;
    build_cg_from_ast(root, cg);
    return cg;
}

template<class FunctionCallGraph>
void
FunctionCall::copy(const FunctionCallGraph &src, FunctionCallGraph &dst)
{
    typedef typename boost::graph_traits<FunctionCallGraph>::vertex_descriptor Vertex;
    Vertex NO_VERTEX = boost::graph_traits<FunctionCallGraph>::null_vertex();

    dst.clear();
    std::vector<Vertex> src_to_dst(boost::num_vertices(src), NO_VERTEX);

    typename boost::graph_traits<const FunctionCallGraph>::vertex_iterator vi, vi_end;
    for (boost::tie(vi, vi_end)=boost::vertices(src); vi!=vi_end; ++vi) {
        SgAsmFunction *func = get_ast_node(src, *vi);
        if (!is_vertex_filtered(func)) {
            src_to_dst[*vi] = boost::add_vertex(dst);
            put_ast_node(dst, src_to_dst[*vi], func);
        }
    }

    typename boost::graph_traits<const FunctionCallGraph>::edge_iterator ei, ei_end;
    for (boost::tie(ei, ei_end)=boost::edges(src); ei!=ei_end; ++ei) {
        if (NO_VERTEX!=src_to_dst[boost::source(*ei, src)] && NO_VERTEX!=src_to_dst[boost::target(*ei, src)]) {
            SgAsmFunction *func1 = get_ast_node(src, boost::source(*ei, src));
            SgAsmFunction *func2 = get_ast_node(src, boost::target(*ei, src));
            if (!is_edge_filtered(func1, func2))
                boost::add_edge(src_to_dst[boost::source(*ei, src)], src_to_dst[boost::target(*ei, src)], dst);
        }
    }
}

template<class FunctionCallGraph>
FunctionCallGraph
FunctionCall::copy(const FunctionCallGraph &src)
{
    FunctionCallGraph dst;
    copy(src, dst);
    return dst;
}

} // namespace
} // namespace

#endif
#endif