boostGraphCFG.h

#pragma once
 
 
// DQ (10/5/2014): This is more strict now that we include rose_config.h in the sage3basic.h.
// #include "rose.h"
// rose.h and sage3basic.h should not be included in librose header files. [Robb P. Matzke 2014-10-15]
// #include "sage3basic.h"
 
#include <boost/graph/adjacency_list.hpp>
#include <boost/bind/bind.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 ssa_private
{
 
template <class CFGNodeT, class CFGEdgeT>
class CFG : public boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, 
        boost::shared_ptr<CFGNodeT>, boost::shared_ptr<CFGEdgeT> >
{
public:
    typedef typename boost::graph_traits<CFG<CFGNodeT, CFGEdgeT> > GraphTraits;
 
 
    typedef CFGNodeT CFGNodeType;
    typedef CFGEdgeT 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;
 
protected:
 
    SgFunctionDefinition* funcDef_;
 
    Vertex entry_;
 
    Vertex exit_;
 
    std::map<CFGNodeType, Vertex> nodesToVertices_;
 
    VertexVertexMap dominatorTree_;
 
    VertexVertexMap postdominatorTree_;
 
public:
 
    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<CFGNodeT, CFGEdgeT> makeReverseCopy() const;
 
    std::vector<CFGNodePtr> getAllNodes() const;
 
    std::vector<CFGEdgePtr> getAllEdges() const;
 
    Vertex getVertexForNode(const CFGNodeType &node) const;
 
    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();
 
    struct VertexCopier
    {
        VertexCopier(const CFG<CFGNodeT, CFGEdgeT>& g1, CFG<CFGNodeT, CFGEdgeT>& g2)
        : cfg1(g1), cfg2(g2) {}
 
        void operator()(const Vertex& v1, Vertex& v2) const
        { cfg2[v2] = cfg1[v1]; }
        
        const CFG<CFGNodeT, CFGEdgeT>& cfg1;
        CFG<CFGNodeT, CFGEdgeT>& cfg2;
    };
 
    struct EdgeCopier
    {
        EdgeCopier(const CFG<CFGNodeT, CFGEdgeT>& g1, CFG<CFGNodeT, CFGEdgeT>& g2)
        : cfg1(g1), cfg2(g2) {}
 
        void operator()(const Edge& e1, Edge& e2) const
        { cfg2[e2] = cfg1[e1]; }
 
        const CFG<CFGNodeT, CFGEdgeT>& cfg1;
        CFG<CFGNodeT, CFGEdgeT>& cfg2;
    };
};
 
 
 
 
 
template <class CFGNodeT, class CFGEdgeT>
void CFG<CFGNodeT, CFGEdgeT>::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 CFGNodeT, class CFGEdgeT>
void CFG<CFGNodeT, CFGEdgeT>::setEntryAndExit()
{
    BOOST_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 CFGNodeT, class CFGEdgeT>
void CFG<CFGNodeT, CFGEdgeT>::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();
 
    BOOST_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 CFGNodeT, class CFGEdgeT>
const typename CFG<CFGNodeT, CFGEdgeT>::VertexVertexMap& CFG<CFGNodeT, CFGEdgeT>::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 CFGNodeT, class CFGEdgeT>
const typename CFG<CFGNodeT, CFGEdgeT>::VertexVertexMap& CFG<CFGNodeT, CFGEdgeT>::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 CFGNodeT, class CFGEdgeT>
CFG<CFGNodeT, CFGEdgeT> CFG<CFGNodeT, CFGEdgeT>::makeReverseCopy() const
{
    CFG<CFGNodeT, CFGEdgeT> 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 CFGNodeT, class CFGEdgeT>
std::vector<typename CFG<CFGNodeT, CFGEdgeT>::CFGNodePtr>
CFG<CFGNodeT, CFGEdgeT>::getAllNodes() const
{
    std::vector<CFGNodePtr> allNodes;
    BOOST_FOREACH (Vertex v, boost::vertices(*this))
        allNodes.push_back((*this)[v]);
    return allNodes;
}
 
template <class CFGNodeT, class CFGEdgeT>
std::vector<typename CFG<CFGNodeT, CFGEdgeT>::CFGEdgePtr>
CFG<CFGNodeT, CFGEdgeT>::getAllEdges() const
{
    std::vector<CFGEdgePtr> allEdges;
    BOOST_FOREACH (const Edge& e, boost::edges(*this))
        allEdges.push_back((*this)[e]);
    return allEdges;
}
 
template <class CFGNodeT, class CFGEdgeT>
typename CFG<CFGNodeT, CFGEdgeT>::Vertex CFG<CFGNodeT, CFGEdgeT>::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 CFGNodeT, class CFGEdgeT>
std::vector<typename CFG<CFGNodeT, CFGEdgeT>::Edge> CFG<CFGNodeT, CFGEdgeT>::getAllBackEdges()
{
    std::vector<Edge> backEdges;
 
    // If the dominator tree is not built yet, build it now.
    getDominatorTree();
 
    BOOST_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 CFGNodeT, class CFGEdgeT>
std::vector<typename CFG<CFGNodeT, CFGEdgeT>::Vertex> CFG<CFGNodeT, CFGEdgeT>::getAllLoopHeaders()
{
    std::vector<Edge> backEdges = getAllBackEdges();
    std::vector<Vertex> headers;
    BOOST_FOREACH (Edge e, backEdges)
        headers.push_back(boost::target(e, *this));
    return headers;
}
 
}