BinaryFunctionCall.h

Go to the documentation of this file.

#ifndef ROSE_BinaryAnalysis_FunctionCall_H
#define ROSE_BinaryAnalysis_FunctionCall_H

#include "BinaryControlFlow.h"

class SgAsmFunction;

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
BinaryAnalysis::FunctionCall::cache_vertex_descriptors(const FunctionCallGraph &cg)
{
    typename boost::graph_traits<FunctionCallGraph>::vertex_iterator vi, vi_end;
    for (boost::tie(vi, vi_end)=vertices(cg); vi!=vi_end; ++vi) {
        SgAsmFunction *func = get(boost::vertex_name, cg, *vi);
        if (func && !is_vertex_filtered(func))
            func->set_cached_vertex(*vi);
    }
}

template<class ControlFlowGraph, class FunctionCallGraph>
void
BinaryAnalysis::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<ControlFlowGraph>::vertex_iterator vi, vi_end;
    for (boost::tie(vi, vi_end)=vertices(cfg); vi!=vi_end; ++vi) {
        SgAsmBlock *block = get(boost::vertex_name, cfg, *vi);
        SgAsmFunction *func = block->get_enclosing_function();
        if (!is_vertex_filtered(func)) {
            typename FunctionVertexMap::iterator fi=fv_map.find(func);
            if (func && fi==fv_map.end()) {
                CG_Vertex v = add_vertex(cg);
                put(boost::vertex_name, cg, v, func);
                fv_map[func] = v;
            }
        }
    }

    /* Add edges whose target is a function entry block. */
    typename boost::graph_traits<ControlFlowGraph>::edge_iterator ei, ei_end;
    for (boost::tie(ei, ei_end)=edges(cfg); ei!=ei_end; ++ei) {
        CFG_Vertex cfg_a = source(*ei, cfg);
        CFG_Vertex cfg_b = target(*ei, cfg);
        SgAsmBlock *block_a = get(boost::vertex_name, cfg, cfg_a);
        SgAsmBlock *block_b = get(boost::vertex_name, cfg, cfg_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())
                    add_edge(fi_a->second, fi_b->second, cg);
            }
        }
    }
}

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

template<class FunctionCallGraph>
void
BinaryAnalysis::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 = add_vertex(cg);
                fv_map[func] = vertex;
                put(boost::vertex_name, 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) {
                SgAsmBlock *block_b = isSgAsmBlock((*si)->get_base_node()); /* the called block */
                SgAsmFunction *func_b = function_of(block_b); /* the called function */
                if (func_b && block_b==func_b->get_entry_block() && !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())
                        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)=vertices(cg); vi!=vi_end; ++vi) {
        SgAsmFunction *source_func = get(boost::vertex_name, cg, *vi);
        EdgeAdder(this, cg, fv_map, *vi).traverse(source_func, preorder);
    }
}

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

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

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

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

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

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



#endif

---