ControlFlowGraph.h

#ifndef ROSE_Partitioner2_ControlFlowGraph_H
#define ROSE_Partitioner2_ControlFlowGraph_H

#include <Partitioner2/BasicBlock.h>
#include <Partitioner2/BasicTypes.h>
#include <Partitioner2/Function.h>
#include <Partitioner2/Utility.h>

#include <Sawyer/BiMap.h>
#include <Sawyer/Graph.h>
#include <Sawyer/GraphIteratorSet.h>
#include <Sawyer/GraphIteratorBiMap.h>
#include <Sawyer/HashMap.h>
#include <Sawyer/Map.h>
#include <Sawyer/Optional.h>

#include <boost/serialization/access.hpp>
#include <list>
#include <ostream>

namespace Rose {
namespace BinaryAnalysis {
namespace Partitioner2 {

class CfgVertex {
    VertexType type_;                                   // type of vertex, special or not
    rose_addr_t startVa_;                               // address of start of basic block
    BasicBlock::Ptr bblock_;                            // basic block, or null if only a place holder
    FunctionSet owningFunctions_;                       // functions to which vertex belongs

#ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
private:
    friend class boost::serialization::access;

    template<class S>
    void serialize(S &s, const unsigned /*version*/) {
        s & BOOST_SERIALIZATION_NVP(type_);
        s & BOOST_SERIALIZATION_NVP(startVa_);
        s & BOOST_SERIALIZATION_NVP(bblock_);
        s & BOOST_SERIALIZATION_NVP(owningFunctions_);
    }
#endif

public:
    // intentionally undocumented. Necessary for serialization of Sawyer::Container::Graph
    CfgVertex()
        : type_(V_USER_DEFINED), startVa_(0) {}

public:
    explicit CfgVertex(rose_addr_t startVa): type_(V_BASIC_BLOCK), startVa_(startVa) {}

    explicit CfgVertex(const BasicBlock::Ptr &bb): type_(V_BASIC_BLOCK), bblock_(bb) {
        ASSERT_not_null(bb);
        startVa_ = bb->address();
    }

    /*implicit*/ CfgVertex(VertexType type): type_(type), startVa_(0) {
        ASSERT_forbid2(type==V_BASIC_BLOCK, "this constructor does not create basic block or placeholder vertices");
    }

    VertexType type() const { return type_; }

    rose_addr_t address() const {
        ASSERT_require(V_BASIC_BLOCK==type_ || V_USER_DEFINED==type_);
        return startVa_;
    }
    void address(rose_addr_t va) {
        ASSERT_require(V_BASIC_BLOCK==type_ || V_USER_DEFINED==type_);
        startVa_ = va;
    }
    Sawyer::Optional<rose_addr_t> optionalAddress() const;

    Sawyer::Optional<rose_addr_t> optionalLastAddress() const;

    AddressIntervalSet addresses() const;

    const BasicBlock::Ptr& bblock() const {
        ASSERT_require(V_BASIC_BLOCK==type_ || V_USER_DEFINED==type_);
        return bblock_;
    }
    void bblock(const BasicBlock::Ptr &bb) {
        ASSERT_require(V_BASIC_BLOCK==type_ || V_USER_DEFINED==type_);
        bblock_ = bb;
    }
    bool insertOwningFunction(const Function::Ptr &function) {
        ASSERT_require(V_BASIC_BLOCK==type_ || V_USER_DEFINED==type_);
        ASSERT_not_null(function);
        return owningFunctions_.insert(function);
    }

    void eraseOwningFunction(const Function::Ptr &function) {
        ASSERT_require(V_BASIC_BLOCK==type_ || V_USER_DEFINED==type_);
        if (function != NULL)
            owningFunctions_.erase(function);
    }

    bool isOwningFunction(const Function::Ptr &function) const {
        return owningFunctions_.exists(function);
    }

    size_t nOwningFunctions() const {
        return owningFunctions_.size();
    }

    const FunctionSet& owningFunctions() const {
        return owningFunctions_;
    }
    FunctionSet& owningFunctions() {
        return owningFunctions_;
    }
    Function::Ptr isEntryBlock() const;

    void nullify() {
        ASSERT_require(V_BASIC_BLOCK==type_);
        bblock_ = BasicBlock::Ptr();
    }
};

class CfgEdge {
private:
    EdgeType type_;
    Confidence confidence_;

#ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
private:
    friend class boost::serialization::access;

    template<class S>
    void serialize(S &s, const unsigned /*version*/) {
        s & BOOST_SERIALIZATION_NVP(type_);
        s & BOOST_SERIALIZATION_NVP(confidence_);
    }
#endif

public:
    CfgEdge(): type_(E_NORMAL), confidence_(ASSUMED) {}

    /*implicit*/ CfgEdge(EdgeType type, Confidence confidence=ASSUMED): type_(type), confidence_(confidence) {}

    EdgeType type() const { return type_; }

    Confidence confidence() const { return confidence_; }
    void confidence(Confidence c) { confidence_ = c; }
};

typedef Sawyer::Container::Graph<CfgVertex, CfgEdge> ControlFlowGraph;

bool sortEdgesBySrc(const ControlFlowGraph::ConstEdgeIterator&, const ControlFlowGraph::ConstEdgeIterator&);

bool sortEdgesByDst(const ControlFlowGraph::ConstEdgeIterator&, const ControlFlowGraph::ConstEdgeIterator&);

bool sortEdgesById(const ControlFlowGraph::ConstEdgeIterator&, const ControlFlowGraph::ConstEdgeIterator&);

bool sortVerticesByAddress(const ControlFlowGraph::ConstVertexIterator&, const ControlFlowGraph::ConstVertexIterator&);

bool sortVerticesById(const ControlFlowGraph::ConstVertexIterator&, const ControlFlowGraph::ConstVertexIterator&);

std::ostream& operator<<(std::ostream&, const ControlFlowGraph::Vertex&);

std::ostream& operator<<(std::ostream&, const ControlFlowGraph::Edge&);

typedef Sawyer::Container::HashMap<rose_addr_t, ControlFlowGraph::VertexIterator> CfgVertexIndex;

typedef std::list<ControlFlowGraph::VertexIterator> CfgVertexList;
typedef std::list<ControlFlowGraph::ConstVertexIterator> CfgConstVertexList;
typedef std::list<ControlFlowGraph::EdgeIterator> CfgEdgeList;
typedef std::list<ControlFlowGraph::ConstEdgeIterator> CfgConstEdgeList;
typedef Sawyer::Container::GraphIteratorSet<ControlFlowGraph::VertexIterator> CfgVertexSet;
typedef Sawyer::Container::GraphIteratorSet<ControlFlowGraph::ConstVertexIterator> CfgConstVertexSet;
typedef Sawyer::Container::GraphIteratorSet<ControlFlowGraph::EdgeIterator> CfgEdgeSet;
typedef Sawyer::Container::GraphIteratorSet<ControlFlowGraph::ConstEdgeIterator> CfgConstEdgeSet;
typedef Sawyer::Container::GraphIteratorBiMap<ControlFlowGraph::ConstVertexIterator,
                                              ControlFlowGraph::ConstVertexIterator> CfgVertexMap;

class CfgAdjustmentCallback: public Sawyer::SharedObject {
public:
    typedef Sawyer::SharedPointer<CfgAdjustmentCallback> Ptr;

    struct AttachedBasicBlock {
        const Partitioner *partitioner;             
        rose_addr_t startVa;                        
        BasicBlock::Ptr bblock;                     
        AttachedBasicBlock(Partitioner *partitioner, rose_addr_t startVa, const BasicBlock::Ptr &bblock)
            : partitioner(partitioner), startVa(startVa), bblock(bblock) {}
    };

    struct DetachedBasicBlock {
        const Partitioner *partitioner;             
        rose_addr_t startVa;                        
        BasicBlock::Ptr bblock;                     
        DetachedBasicBlock(Partitioner *partitioner, rose_addr_t startVa, const BasicBlock::Ptr &bblock)
            : partitioner(partitioner), startVa(startVa), bblock(bblock) {}
    };

    virtual bool operator()(bool chain, const AttachedBasicBlock&) = 0;

    virtual bool operator()(bool chain, const DetachedBasicBlock&) = 0;
};

//                                      Control flow graph utility functions

void insertCfg(ControlFlowGraph &dst, const ControlFlowGraph &src, CfgVertexMap &vmap /*out*/);

CfgConstEdgeSet findBackEdges(const ControlFlowGraph &cfg, const ControlFlowGraph::ConstVertexIterator &begin);

CfgConstEdgeSet findCallEdges(const ControlFlowGraph::ConstVertexIterator &callSite);

CfgConstVertexSet findCalledFunctions(const ControlFlowGraph &cfg, const ControlFlowGraph::ConstVertexIterator &callSite);

CfgConstEdgeSet findCallReturnEdges(const Partitioner&, const ControlFlowGraph&);
CfgConstEdgeSet findCallReturnEdges(const ControlFlowGraph::ConstVertexIterator &callSite);
CfgConstVertexSet findFunctionReturns(const ControlFlowGraph &cfg, const ControlFlowGraph::ConstVertexIterator &beginVertex);

Sawyer::Container::Map<Function::Ptr, CfgConstEdgeSet> findFunctionReturnEdges(const Partitioner&);
Sawyer::Container::Map<Function::Ptr, CfgConstEdgeSet> findFunctionReturnEdges(const Partitioner&, const ControlFlowGraph&);
void eraseEdges(ControlFlowGraph&, const CfgConstEdgeSet &toErase);

CfgConstVertexSet findIncidentVertices(const CfgConstEdgeSet&);

CfgConstVertexSet findDetachedVertices(const ControlFlowGraph&);
CfgConstVertexSet findDetachedVertices(const CfgConstVertexSet &vertices);
CfgConstVertexSet forwardMapped(const CfgConstVertexSet&, const CfgVertexMap&);

CfgConstVertexSet reverseMapped(const CfgConstVertexSet&, const CfgVertexMap&);

void expandFunctionReturnEdges(const Partitioner&, ControlFlowGraph &cfg/*in,out*/);

ControlFlowGraph functionCfgByErasure(const ControlFlowGraph &gcfg, const Function::Ptr &function,
                                      ControlFlowGraph::VertexIterator &entry/*out*/);

ControlFlowGraph functionCfgByReachability(const ControlFlowGraph &gcfg, const Function::Ptr &function,
                                           const ControlFlowGraph::ConstVertexIterator &gcfgEntry);

} // namespace
} // namespace
} // namespace

#endif