BinaryControlFlow.h

Go to the documentation of this file.

#ifndef ROSE_BinaryAnalysis_ControlFlow_H
#define ROSE_BinaryAnalysis_ControlFlow_H

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/depth_first_search.hpp>

class SgNode;
class SgAsmBlock;

namespace BinaryAnalysis {

    class ControlFlow {
    public:
        ControlFlow()
            : vertex_filter(NULL), edge_filter(NULL)
            {}
        

        typedef boost::adjacency_list<boost::setS,                                  /* edges of each vertex in std::list */
                                      boost::vecS,                                  /* vertices in std::vector */
                                      boost::bidirectionalS,
                                      boost::property<boost::vertex_name_t, SgAsmBlock*> > Graph;

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

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

        class EdgeFilter {
        public:
            virtual ~EdgeFilter() {}
            virtual bool operator()(ControlFlow*, SgAsmBlock *source, SgAsmBlock *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(SgAsmBlock *block, VertexFilter *filter) { return filter && !(*filter)(this, block); }
        bool is_vertex_filtered(SgAsmBlock *block) { return is_vertex_filtered(block, vertex_filter); }
        bool is_edge_filtered(SgAsmBlock *src, SgAsmBlock *dst, EdgeFilter *filter) {
            return filter && !(*filter)(this, src, dst);
        }
        bool is_edge_filtered(SgAsmBlock *src, SgAsmBlock *dst) {
            return is_edge_filtered(src, dst, edge_filter);
        }
    protected:
        VertexFilter *vertex_filter;
        EdgeFilter *edge_filter;

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

        void clear_ast(SgNode *ast);

        template<class ControlFlowGraph>
        void apply_to_ast(const ControlFlowGraph&);

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

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

        template<class ControlFlowGraph>
        ControlFlowGraph build_cfg_from_ast(SgNode *root);

        template<class ControlFlowGraph>
        void build_cfg_from_ast(SgNode *root, ControlFlowGraph &cfg/*out*/);
        template<class ControlFlowGraph>
        ControlFlowGraph build_cg_from_ast(SgNode *root);

        template<class ControlFlowGraph>
        void build_cg_from_ast(SgNode *root, ControlFlowGraph &cfg/*out*/);
        template<class ControlFlowGraph>
        ControlFlowGraph copy(const ControlFlowGraph &src);

        template<class ControlFlowGraph>
        void copy(const ControlFlowGraph &src, ControlFlowGraph &dst/*out*/);
        /**********************************************************************************************************************
         *                                      Miscellaneous members
         **********************************************************************************************************************/

    private:
        /* Visitor used by flow_order().  Declaring this in function scope results in boost errors (boost-1.42, 2011-05). */
        template<class ControlFlowGraph>
        struct FlowOrder: public boost::default_dfs_visitor {
            typedef typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor Vertex;
            typedef std::vector<Vertex> VertexList;
            typedef std::vector<size_t> ReverseVertexList;
            VertexList *forward_order;
            FlowOrder(VertexList *forward_order): forward_order(forward_order) {}
            void compute(const ControlFlowGraph &g, Vertex v0, ReverseVertexList *reverse_order);
            void finish_vertex(Vertex v, ControlFlowGraph g);
        };
            
    public:
        template<class ControlFlowGraph>
        std::vector<typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor>
        flow_order(const ControlFlowGraph&,
                   typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor start,
                   std::vector<size_t> *reverse_order=NULL);

    private:
        /* Visitor used by return_blocks(). Declaring this in function scope results in boost errors (boost-1.42, 2011-05). */
        template<class ControlFlowGraph>
        struct ReturnBlocks: public boost::default_dfs_visitor {
            typedef typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor Vertex;
            typedef std::vector<Vertex> Vector;
            Vector &blocks;
            ReturnBlocks(Vector &blocks): blocks(blocks) {}
            void finish_vertex(Vertex v, ControlFlowGraph g);
        };

    public:
        template<class ControlFlowGraph>
        std::vector<typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor>
        return_blocks(const ControlFlowGraph &cfg,
                      typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor start);
    };
}





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

template<class ControlFlowGraph>
void
BinaryAnalysis::ControlFlow::apply_to_ast(const ControlFlowGraph &cfg)
{
    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);
        if (!block || is_vertex_filtered(block))
            continue;

        /* Delete old targets */
        const SgAsmIntegerValuePtrList &targets = block->get_successors();
        for (SgAsmIntegerValuePtrList::const_iterator ti=targets.begin(); ti!=targets.end(); ++ti)
            delete *ti;

        /* Add new targets */
        block->set_successors_complete(true);
        block->get_successors().clear();
        typename boost::graph_traits<ControlFlowGraph>::out_edge_iterator ei, ei_end;
        for (boost::tie(ei, ei_end)=out_edges(*vi, cfg); ei!=ei_end; ++ei) {
            SgAsmBlock *target_block = get(boost::vertex_name, cfg, target(*ei, cfg));
            if (target_block && !is_edge_filtered(block, target_block)) {
                SgAsmIntegerValueExpression *target = new SgAsmIntegerValueExpression(target_block->get_address());
                target->make_relative_to(target_block);
                target->set_parent(block);
                block->get_successors().push_back(target);
            }
        }
    }
}

template<class ControlFlowGraph>
void
BinaryAnalysis::ControlFlow::cache_vertex_descriptors(const ControlFlowGraph &cfg)
{
    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);
        if (block && !is_vertex_filtered(block))
            block->set_cached_vertex(*vi);
    }
}

template<class ControlFlowGraph>
void
BinaryAnalysis::ControlFlow::build_cfg_from_ast(SgNode *root, ControlFlowGraph &cfg)
{
    typedef typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor Vertex;
    typedef std::map<SgAsmBlock*, Vertex> BlockVertexMap;
    BlockVertexMap bv_map;

    cfg.clear();

    /* Define the vertices. Vertices are any SgAsmBlock that contains at least one SgAsmInstruction. */
    struct T1: public AstSimpleProcessing {
        ControlFlow *analyzer;
        ControlFlowGraph &cfg;
        BlockVertexMap &bv_map;
        T1(ControlFlow *analyzer, ControlFlowGraph &cfg, BlockVertexMap &bv_map)
            : analyzer(analyzer), cfg(cfg), bv_map(bv_map)
            {}
        void visit(SgNode *node) {
            SgAsmBlock *block = isSgAsmBlock(node);
            if (block && block->has_instructions() && !analyzer->is_vertex_filtered(block)) {
                Vertex vertex = add_vertex(cfg);
                bv_map[block] = vertex;
                put(boost::vertex_name, cfg, vertex, block);
            }
        }
    };
    T1(this, cfg, bv_map).traverse(root, preorder); /* preorder guarantees that the highest SgAsmBlock will be vertex zero */

    /* Add the edges. */
    typename boost::graph_traits<ControlFlowGraph>::vertex_iterator vi, vi_end;
    for (boost::tie(vi, vi_end)=vertices(cfg); vi!=vi_end; ++vi) {
        SgAsmBlock *source = boost::get(boost::vertex_name, cfg, *vi);
        const SgAsmIntegerValuePtrList &succs = source->get_successors();
        for (SgAsmIntegerValuePtrList::const_iterator si=succs.begin(); si!=succs.end(); ++si) {
            SgAsmBlock *target = isSgAsmBlock((*si)->get_base_node()); // might be null
            if (target && !is_edge_filtered(source, target)) {
                typename BlockVertexMap::iterator bvmi=bv_map.find(target);
                if (bvmi!=bv_map.end())
                    add_edge(*vi, bvmi->second, cfg);
            }
        }
    }
}

template<class ControlFlowGraph>
void
BinaryAnalysis::ControlFlow::build_cg_from_ast(SgNode *root, ControlFlowGraph &cfg/*out*/)
{
    struct T1: public EdgeFilter {
        EdgeFilter *parent;
        T1(EdgeFilter *parent): parent(parent) {}
        bool operator()(ControlFlow *analyzer, SgAsmBlock *src, SgAsmBlock *dst) {
            SgAsmFunction *func = dst ? dst->get_enclosing_function() : NULL;
            if (!func || dst!=func->get_entry_block())
                return false;
            if (parent)
                return (*parent)(analyzer, src, dst);
            return true;
        }
    };

    EdgeFilter *parent = get_edge_filter();
    T1 edge_filter(parent);
    try {
        set_edge_filter(&edge_filter);
        build_cfg_from_ast(root, cfg);
    } catch (...) {
        set_edge_filter(parent);
        throw;
    }
    set_edge_filter(parent);
}

template<class ControlFlowGraph>
void
BinaryAnalysis::ControlFlow::copy(const ControlFlowGraph &src, ControlFlowGraph &dst/*out*/)
{
    typedef typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor Vertex;
    Vertex NO_VERTEX = boost::graph_traits<ControlFlowGraph>::null_vertex();

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

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

    typename boost::graph_traits<ControlFlowGraph>::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)]) {
            SgAsmBlock *block1 = get(boost::vertex_name, src, source(*ei, src));
            SgAsmBlock *block2 = get(boost::vertex_name, src, target(*ei, src));
            if (!is_edge_filtered(block1, block2))
                add_edge(src_to_dst[source(*ei, src)], src_to_dst[target(*ei, src)], dst);
        }
    }
}

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

template<class ControlFlowGraph>
void
BinaryAnalysis::ControlFlow::FlowOrder<ControlFlowGraph>::compute(const ControlFlowGraph &g, Vertex v0,
                                                                  ReverseVertexList *reverse_order) {
    forward_order->clear();
    std::vector<boost::default_color_type> colors(num_vertices(g), boost::white_color);
    depth_first_visit(g, v0, *this, &(colors[0]));
    assert(!forward_order->empty()); /* it should at least contain v0 */
    std::reverse(forward_order->begin(), forward_order->end());
    if (reverse_order) {
        reverse_order->clear();
        reverse_order->resize(num_vertices(g), (size_t)(-1));
        for (size_t i=0; i<forward_order->size(); i++)
            (*reverse_order)[(*forward_order)[i]] = i;
    }
}

template<class ControlFlowGraph>
void
BinaryAnalysis::ControlFlow::FlowOrder<ControlFlowGraph>::finish_vertex(Vertex v, ControlFlowGraph g) {
    forward_order->push_back(v);
}

template<class ControlFlowGraph>
std::vector<typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor>
BinaryAnalysis::ControlFlow::flow_order(const ControlFlowGraph &cfg,
                                        typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor start,
                                        std::vector<size_t> *reverse_order/*=NULL*/)
{
    std::vector<typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor> forward_order;
    FlowOrder<ControlFlowGraph>(&forward_order).compute(cfg, start, reverse_order);
    return forward_order;
}

template<class ControlFlowGraph>
void
BinaryAnalysis::ControlFlow::ReturnBlocks<ControlFlowGraph>::finish_vertex(Vertex v, ControlFlowGraph g)
{
    typename boost::graph_traits<ControlFlowGraph>::out_edge_iterator ei, ei_end;
    boost::tie(ei, ei_end) = out_edges(v, g);
    if (ei==ei_end)
        blocks.push_back(v);
}
    
template<class ControlFlowGraph>
std::vector<typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor>
BinaryAnalysis::ControlFlow::return_blocks(const ControlFlowGraph &cfg,
                                           typename boost::graph_traits<ControlFlowGraph>::vertex_descriptor start)
{
    typename ReturnBlocks<ControlFlowGraph>::Vector result;
    ReturnBlocks<ControlFlowGraph> visitor(result);
    std::vector<boost::default_color_type> colors(num_vertices(cfg), boost::white_color);
    depth_first_visit(cfg, start, visitor, &(colors[0]));
    return result;
}

template<class ControlFlowGraph>
ControlFlowGraph
BinaryAnalysis::ControlFlow::build_cfg_from_ast(SgNode *root)
{
    ControlFlowGraph cfg;
    build_cfg_from_ast(root, cfg);
    return cfg;
}

template<class ControlFlowGraph>
ControlFlowGraph
BinaryAnalysis::ControlFlow::build_cg_from_ast(SgNode *root)
{
    ControlFlowGraph cfg;
    build_cg_from_ast(root, cfg);
    return cfg;
}

#endif

---