cong_staticCFG.h

Go to the documentation of this file.

/* 
 * File:   staticCFG.h
 * Author: Cong Hou [hou_cong@gatech.edu]
 */

#ifndef ________CFG_H__________
#define ________CFG_H__________

#include <rose.h>
#include <filteredCFG.h>
#include <boost/function.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/shared_ptr.hpp>


// Pre-declaration.
class SgFunctionDefinition;


namespace StaticCFG
{

typedef boost::function<bool(const VirtualCFG::CFGNode&)> CFGNodeFilter;


typedef VirtualCFG::FilteredCFGNode<CFGNodeFilter> CFGNode;
typedef VirtualCFG::FilteredCFGEdge<CFGNodeFilter> CFGEdge;

typedef boost::shared_ptr<CFGNode> CFGNodePtr;
typedef boost::shared_ptr<CFGEdge> CFGEdgePtr;

struct DefaultFilter
{
    bool operator()(const VirtualCFG::CFGNode& cfgNode) const
    { return true; }
};

struct InterestingCFGNodeFilter
{
    bool operator()(const VirtualCFG::CFGNode& cfgNode) const
    { return cfgNode.isInteresting(); }
};


class ControlFlowGraph : public boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, 
CFGNodePtr, CFGEdgePtr>
{
    public:
        typedef boost::graph_traits<ControlFlowGraph>   GraphTraits;
        typedef GraphTraits::vertex_descriptor          Vertex;
        typedef GraphTraits::edge_descriptor            Edge;

        typedef std::map<Vertex, Vertex>                VertexVertexMap;
        typedef std::set<Vertex>                        Vertices;

    protected:

        SgFunctionDefinition* funcDef_;

        CFGNodeFilter filter_;

        Vertex entry_;

        Vertex exit_;

        std::map<CFGNode, Vertex> nodesToVertices_;

        mutable VertexVertexMap dominatorTree_;

        mutable VertexVertexMap postdominatorTree_;

    public:

        ControlFlowGraph()
            : funcDef_(NULL),
            filter_(DefaultFilter()),
            entry_(GraphTraits::null_vertex()),
            exit_(GraphTraits::null_vertex())
    {
    }

        explicit ControlFlowGraph(
                SgFunctionDefinition* funcDef, 
                const CFGNodeFilter& cfgNodeFilter = DefaultFilter())
            : funcDef_(funcDef),
            filter_(cfgNodeFilter),
            entry_(GraphTraits::null_vertex()),
            exit_(GraphTraits::null_vertex())
    {
        build(funcDef);
    }

        void build(SgFunctionDefinition* funcDef);

        SgFunctionDefinition* getFunctionDefinition() const
        { return funcDef_; }

        Vertex getEntry() const { return entry_; }

        Vertex getExit() const { return exit_; }

        void setEntry(Vertex entry) { entry_ = entry; }

        void setExit(Vertex exit) { exit_ = exit; }

        const VertexVertexMap& getDominatorTree() const;

        const VertexVertexMap& getPostdominatorTree() const;

        ControlFlowGraph makeReverseCopy() const;

        void toDot(const std::string& filename) const;

        std::vector<CFGNodePtr> getAllNodes() const;

        std::vector<CFGEdgePtr> getAllEdges() const;

        Vertex getVertexForNode(const CFGNode& node) const;

        bool isReducible() const { return true; }

        std::set<Edge> getAllBackEdges() const;

        Vertices getAllLoopHeaders() const;

        std::map<Vertex, Vertices> getAllLoops() const;

    protected:

        void buildCFG(const CFGNode& node,
                std::map<CFGNode, Vertex>& nodesAdded,
                std::set<CFGNode>& nodesProcessed);

        void setEntryAndExit();

        CFGNodePtr newCFGNode(const CFGNode& node)
        { return CFGNodePtr(new CFGNode(node)); }

        CFGEdgePtr newCFGEdge(const CFGEdge& edge)
        { return CFGEdgePtr(new CFGEdge(edge)); }

        void writeGraphNode(std::ostream& out, const Vertex& node) const;

        void writeGraphEdge(std::ostream& out, const Edge& edge) const;


    protected:
        struct VertexCopier
        {
            VertexCopier(const ControlFlowGraph& g1, ControlFlowGraph& g2)
                : cfg1(g1), cfg2(g2) {}

            void operator()(const Vertex& v1, Vertex& v2) const
            { cfg2[v2] = cfg1[v1]; }

            const ControlFlowGraph& cfg1;
            ControlFlowGraph& cfg2;
        };

        struct EdgeCopier
        {
            EdgeCopier(const ControlFlowGraph& g1, ControlFlowGraph& g2)
                : cfg1(g1), cfg2(g2) {}

            void operator()(const Edge& e1, Edge& e2) const
            { cfg2[e2] = cfg1[e1]; }

            const ControlFlowGraph& cfg1;
            ControlFlowGraph& cfg2;
        };
};


void writeCFGNode(std::ostream& out, const CFGNode& cfgNode);

void writeCFGEdge(std::ostream& out, const CFGEdge& e);


} // end of namespace StaticCFG


#endif /* ________CFG_H__________ */