graphTemplate.h

Go to the documentation of this file.

#ifndef BACKSTROKE_CFG_H
#define BACKSTROKE_CFG_H


#include <rose.h>
#include <boost/graph/adjacency_list.hpp>
#include <boost/bind.hpp>
#include <boost/foreach.hpp>
#include <boost/tuple/tuple.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/graph/dominator_tree.hpp>
#include <boost/graph/reverse_graph.hpp>
#include <boost/graph/transpose_graph.hpp>
#include <boost/algorithm/string.hpp>


namespace Backstroke
{

#define foreach BOOST_FOREACH


template <class CFGNodeType>
void writeCFGNode(std::ostream& out, const CFGNodeType& cfgNode)
{
        SgNode* node = cfgNode.getNode();
        ROSE_ASSERT(node);

        std::string nodeColor = "black";
        if (isSgStatement(node))
                nodeColor = "blue";
        else if (isSgExpression(node))
                nodeColor = "green";
        else if (isSgInitializedName(node))
                nodeColor = "red";

        std::string label;

        if (SgFunctionDefinition* funcDef = isSgFunctionDefinition(node))
        {
                std::string funcName = funcDef->get_declaration()->get_name().str();
                if (cfgNode.getIndex() == 0)
                        label = "Entry\\n" + funcName;
                else if (cfgNode.getIndex() == 3)
                        label = "Exit\\n" + funcName;
        }
        
        if (!isSgScopeStatement(node) && !isSgCaseOptionStmt(node) && !isSgDefaultOptionStmt(node))
        {
                std::string content = node->unparseToString();
                boost::replace_all(content, "\"", "\\\"");
                boost::replace_all(content, "\\n", "\\\\n");
                label += content;
        }
    else
                label += "<" + node->class_name() + ">";
    
    if (label == "")
                label += "<" + node->class_name() + ">";
        
        out << "[label=\""  << label << "\", color=\"" << nodeColor <<
                "\", style=\"" << (cfgNode.isInteresting()? "solid" : "dotted") << "\"]";
}


template <class CFGEdgeType>
void writeCFGEdge(std::ostream& out, const CFGEdgeType& e)
{
        out << "[label=\"" << escapeString(e.toString()) <<
                "\", style=\"" << "solid" << "\"]";
}


// Predeclaration of class CFG.
template <class CFGNodeFilter> class CFG;

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

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

typedef CFG<FullCFGNodeFilter> FullCFG;


typedef CFG<InterestingCFGNodeFilter> FilteredCFG;





/********************************************************************/
//      The concept required to be fulfilled by CFGNodeFilter is
//
//      struct CFGNodeFilter
//      {
//              bool operator()(const VirtualCFG::CFGNode& cfgNode) const;
//      };
//
/********************************************************************/

        
template <class CFGNodeFilter>
class CFG : public boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, 
                boost::shared_ptr<VirtualCFG::FilteredCFGNode<CFGNodeFilter> >,
                boost::shared_ptr<VirtualCFG::FilteredCFGEdge<CFGNodeFilter> > >
{
        typedef typename boost::graph_traits<CFG<CFGNodeFilter> > GraphTraits;

public:
    typedef VirtualCFG::FilteredCFGNode<CFGNodeFilter> CFGNodeType;
        typedef VirtualCFG::FilteredCFGEdge<CFGNodeFilter> CFGEdgeType;

        typedef boost::shared_ptr<CFGNodeType> CFGNodePtr;
        typedef boost::shared_ptr<CFGEdgeType> CFGEdgePtr;

    typedef typename GraphTraits::vertex_descriptor Vertex;
        typedef typename GraphTraits::edge_descriptor Edge;

        typedef std::map<Vertex, Vertex> VertexVertexMap;
        Vertex entry_;

        Vertex exit_;


protected:

        SgFunctionDefinition* funcDef_;


        std::map<CFGNodeType, Vertex> nodesToVertices_;

    VertexVertexMap dominatorTree_;

    VertexVertexMap postdominatorTree_;

public:
        std::map<CFGNodeType, Vertex> getNodeVert() {
            return nodesToVertices_;
        }

        CFG()
        :       funcDef_(NULL),
                entry_(GraphTraits::null_vertex()),
                exit_(GraphTraits::null_vertex())
        {
        }

        explicit CFG(SgFunctionDefinition* funcDef)
        :       funcDef_(funcDef),
                entry_(GraphTraits::null_vertex()),
                exit_(GraphTraits::null_vertex())
        {
                build(funcDef);
        }

        void build(SgFunctionDefinition* funcDef);

        SgFunctionDefinition* getFunctionDefinition() const
        { return funcDef_; }

        const Vertex& getEntry() const
        { return entry_; }

        const Vertex& getExit() const
        { return exit_; }

        const VertexVertexMap& getDominatorTree();

        const VertexVertexMap& getPostdominatorTree();

        CFG<CFGNodeFilter> makeReverseCopy() const;

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

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

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

        Vertex getVertexForNode(const CFGNodeType &node) const;

    bool isReducible() const { return true; }

    std::vector<Edge> getAllBackEdges();

    std::vector<Vertex> getAllLoopHeaders();

protected:

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

        void setEntryAndExit();

        void writeGraphNode(std::ostream& out, const Vertex& node) const
        {
                writeCFGNode(out, *(*this)[node]);
                //VirtualCFG::printNode(out, (*this)[node]);
        }

        void writeGraphEdge(std::ostream& out, const Edge& edge) const
        {
                writeCFGEdge(out, *(*this)[edge]);
                //VirtualCFG::printEdge(out, (*this)[edge], true);
        }

        struct VertexCopier
        {
                VertexCopier(const CFG<CFGNodeFilter>& g1, CFG<CFGNodeFilter>& g2)
                : cfg1(g1), cfg2(g2) {}

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

        struct EdgeCopier
        {
                EdgeCopier(const CFG<CFGNodeFilter>& g1, CFG<CFGNodeFilter>& g2)
                : cfg1(g1), cfg2(g2) {}

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

                const CFG<CFGNodeFilter>& cfg1;
                CFG<CFGNodeFilter>& cfg2;
        };
};



template <class CFGNodeFilter>
void CFG<CFGNodeFilter>::toDot(const std::string& filename) const
{
        std::ofstream ofile(filename.c_str(), std::ios::out);
        boost::write_graphviz(ofile, *this,
                        boost::bind(&CFG<CFGNodeFilter>::writeGraphNode, this, ::_1, ::_2),
                        boost::bind(&CFG<CFGNodeFilter>::writeGraphEdge, this, ::_1, ::_2));
}

template <class CFGNodeFilter>
void CFG<CFGNodeFilter>::build(SgFunctionDefinition* funcDef)
{
        ROSE_ASSERT(funcDef);
        funcDef_ = funcDef;

        // The following two variables are used to record the nodes traversed.
        nodesToVertices_.clear();
        std::set<CFGNodeType> nodesProcessed;

        // Remove all nodes and edges first.
        this->clear();
        entry_ = GraphTraits::null_vertex();
        exit_ = GraphTraits::null_vertex();

        buildCFG(CFGNodeType(funcDef->cfgForBeginning()), nodesToVertices_, nodesProcessed);

        // Find the entry and exit of this CFG.
        setEntryAndExit();

        ROSE_ASSERT(isSgFunctionDefinition((*this)[entry_]->getNode()));
        ROSE_ASSERT(isSgFunctionDefinition((*this)[exit_]->getNode()));
}

template <class CFGNodeFilter>
void CFG<CFGNodeFilter>::setEntryAndExit()
{
    foreach (Vertex v, boost::vertices(*this))
        {
                CFGNodePtr node = (*this)[v];
                if (isSgFunctionDefinition(node->getNode()))
                {
                        if (node->getIndex() == 0)
                                entry_ = v;
                        else if (node->getIndex() == 3)
                                exit_ = v;
                }
        }

        //In graphs with an infinite loop, we might never get to the end vertex
        //In those cases, we need to add it explicitly
        if (exit_ == GraphTraits::null_vertex())
        {
                std::cerr << "This function may contain an infinite loop "
                                "inside so that its CFG cannot be built" << std::endl;
                exit_ = add_vertex(*this);
                (*this)[exit_] = CFGNodePtr(new CFGNodeType(funcDef_->cfgForEnd()));
        }

        ROSE_ASSERT(entry_ != GraphTraits::null_vertex());
        ROSE_ASSERT(exit_ != GraphTraits::null_vertex());
}

template <class CFGNodeFilter>
void CFG<CFGNodeFilter>::buildCFG(
                const CFGNodeType& node,
                std::map<CFGNodeType, Vertex>& nodesAdded,
                std::set<CFGNodeType>& nodesProcessed)
{
        ROSE_ASSERT(node.getNode());

        if (nodesProcessed.count(node) > 0)
                return;
        nodesProcessed.insert(node);

        typename std::map<CFGNodeType, Vertex>::iterator iter;
        bool inserted;
        Vertex from, to;

        // Add the source node.
        const CFGNodeType& src = node;
        ROSE_ASSERT(src.getNode());

        boost::tie(iter, inserted) = nodesAdded.insert(std::make_pair(src, Vertex()));

        if (inserted)
        {
                from = add_vertex(*this);
                (*this)[from] = CFGNodePtr(new CFGNodeType(src));
                iter->second = from;
        }
        else
        {
                from = iter->second;
        }

        std::vector<CFGEdgeType> outEdges = node.outEdges();

        foreach(const CFGEdgeType& cfgEdge, outEdges)
        {
                // For each out edge, add the target node.
                CFGNodeType tar = cfgEdge.target();
                ROSE_ASSERT(tar.getNode());

                boost::tie(iter, inserted) = nodesAdded.insert(std::make_pair(tar, Vertex()));

                if (inserted)
                {
                        to = add_vertex(*this);
                        (*this)[to] = CFGNodePtr(new CFGNodeType(tar));
                        iter->second = to;
                }
                else
                {
                        to = iter->second;
                }

                // Add the edge.
                Edge edge = add_edge(from, to, *this).first;
                (*this)[edge] = CFGEdgePtr(new CFGEdgeType(cfgEdge));

                // Build the CFG recursively.
                buildCFG(tar, nodesAdded, nodesProcessed);
        }
}

template <class CFGNodeFilter>
const typename CFG<CFGNodeFilter>::VertexVertexMap& CFG<CFGNodeFilter>::getDominatorTree()
{
    if (!dominatorTree_.empty())
        return dominatorTree_;

        boost::associative_property_map<VertexVertexMap> domTreePredMap(dominatorTree_);

        // Here we use the algorithm in boost::graph to build a map from each node to its immediate dominator.
        boost::lengauer_tarjan_dominator_tree(*this, entry_, domTreePredMap);
        return dominatorTree_;
}

template <class CFGNodeFilter>
const typename CFG<CFGNodeFilter>::VertexVertexMap& CFG<CFGNodeFilter>::getPostdominatorTree()
{
    if (!postdominatorTree_.empty())
        return postdominatorTree_;
    
        boost::associative_property_map<VertexVertexMap> postdomTreePredMap(postdominatorTree_);

        // Here we use the algorithm in boost::graph to build an map from each node to its immediate dominator.
        boost::lengauer_tarjan_dominator_tree(boost::make_reverse_graph(*this), exit_, postdomTreePredMap);
        return postdominatorTree_;
}

template <class CFGNodeFilter>
CFG<CFGNodeFilter> CFG<CFGNodeFilter>::makeReverseCopy() const
{
        CFG<CFGNodeFilter> reverseCFG;
        // The following function makes a reverse CFG copy.
        boost::transpose_graph(*this, reverseCFG, 
                boost::vertex_copy(VertexCopier(*this, reverseCFG)).
                edge_copy(EdgeCopier(*this, reverseCFG)));

        // Swap entry and exit.
        reverseCFG.entry_ = this->exit_;
        reverseCFG.exit_ = this->entry_;
        return reverseCFG;
}


template <class CFGNodeFilter>
std::vector<typename CFG<CFGNodeFilter>::CFGNodePtr>
CFG<CFGNodeFilter>::getAllNodes() const
{
        std::vector<CFGNodePtr> allNodes;
    foreach (Vertex v, boost::vertices(*this))
                allNodes.push_back((*this)[v]);
        return allNodes;
}

/*
template <class CFGNodeFilter>
std::vector<typename CFG<CFGNodeFilter>::CFGNodeType>
CFG<CFGNodeFilter>::getAllNodesNoPtrs() const
{
        std::vector<CFGNodeType> allNodes;
    foreach (Vertex v, boost::vertices(*this))
                allNodes.push_back(&((*this)[v]));
        return allNodes;
}
*/

template <class CFGNodeFilter>
std::vector<typename CFG<CFGNodeFilter>::CFGEdgePtr>
CFG<CFGNodeFilter>::getAllEdges() const
{
        std::vector<CFGEdgePtr> allEdges;
    foreach (const Edge& e, boost::edges(*this))
                allEdges.push_back((*this)[e]);
        return allEdges;
}

template <class CFGNodeFilter>
typename CFG<CFGNodeFilter>::Vertex CFG<CFGNodeFilter>::getVertexForNode(const CFGNodeType &node) const
{
        typename std::map<CFGNodeType, Vertex>::const_iterator vertexIter = nodesToVertices_.find(node);
        if (vertexIter == nodesToVertices_.end())
                return GraphTraits::null_vertex();
        else
        {
                ROSE_ASSERT(*(*this)[vertexIter->second] == node);
                return vertexIter->second;
        }
}

template <class CFGNodeFilter>
std::vector<typename CFG<CFGNodeFilter>::Edge> CFG<CFGNodeFilter>::getAllBackEdges()
{
    std::vector<Edge> backEdges;

    // If the dominator tree is not built yet, build it now.
    getDominatorTree();

    foreach (const Edge& e, boost::edges(*this))
    {
        Vertex src = boost::source(e, *this);
        Vertex tar = boost::target(e, *this);

        //Vertex v = *(dominatorTree.find(src));
        typename VertexVertexMap::const_iterator iter = dominatorTree_.find(src);
        while (iter != dominatorTree_.end())
        {
            if (iter->second == tar)
            {
                backEdges.push_back(e);
                break; // break the while loop
            }
            iter = dominatorTree_.find(iter->second);
        }
    }

    return backEdges;
}

template <class CFGNodeFilter>
std::vector<typename CFG<CFGNodeFilter>::Vertex> CFG<CFGNodeFilter>::getAllLoopHeaders()
{
    std::vector<Edge> backEdges = getAllBackEdges();
    std::vector<Vertex> headers;
    foreach (Edge e, backEdges)
        headers.push_back(boost::target(e, *this));
    return headers;
}

#undef foreach

} // End of namespace Backstroke


#endif  /* BACKSTROKE_CFG_H */