ControlFlowGraph.h

#ifndef ROSE_BinaryAnalysis_Partitioner2_ControlFlowGraph_H
#define ROSE_BinaryAnalysis_Partitioner2_ControlFlowGraph_H
#include <featureTests.h>
#ifdef ROSE_ENABLE_BINARY_ANALYSIS
#include <Rose/BinaryAnalysis/Partitioner2/BasicTypes.h>

#include <Rose/BinaryAnalysis/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
    BasicBlockPtr 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();
    ~CfgVertex();

    explicit CfgVertex(rose_addr_t startVa);

    explicit CfgVertex(const BasicBlockPtr &bb);

    /*implicit*/ CfgVertex(VertexType type);

    VertexType type() const;

    rose_addr_t address() const;
    void address(rose_addr_t);
    Sawyer::Optional<rose_addr_t> optionalAddress() const;

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

    AddressIntervalSet addresses() const;

    const BasicBlockPtr& bblock() const;
    void bblock(const BasicBlockPtr&);
    bool insertOwningFunction(const FunctionPtr&);

    void eraseOwningFunction(const FunctionPtr&);

    bool isOwningFunction(const FunctionPtr&) const;

    size_t nOwningFunctions() const;

    const FunctionSet& owningFunctions() const;
    FunctionSet& owningFunctions();
    FunctionPtr isEntryBlock() const;

    void nullify();
};

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();

    CfgEdge();

    /*implicit*/ CfgEdge(EdgeType type, Confidence confidence = ASSUMED);

    EdgeType type() const;

    Confidence confidence() const;
    void confidence(Confidence);
};

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 PartitionerPtr partitioner;               
        rose_addr_t startVa;                            
        BasicBlockPtr bblock;                           
        AttachedBasicBlock(const PartitionerPtr&, rose_addr_t startVa, const BasicBlockPtr&);
        ~AttachedBasicBlock();
    };

    struct DetachedBasicBlock {
        PartitionerConstPtr partitioner;                
        rose_addr_t startVa;                            
        BasicBlockPtr bblock;                           
        DetachedBasicBlock(const PartitionerPtr&, rose_addr_t startVa, const BasicBlockPtr&);
        ~DetachedBasicBlock();
    };

    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 PartitionerConstPtr&, const ControlFlowGraph&);
CfgConstEdgeSet findCallReturnEdges(const ControlFlowGraph::ConstVertexIterator &callSite);
CfgConstVertexSet findFunctionReturns(const ControlFlowGraph &cfg, const ControlFlowGraph::ConstVertexIterator &beginVertex);

Sawyer::Container::Map<FunctionPtr, CfgConstEdgeSet> findFunctionReturnEdges(const PartitionerConstPtr&);
Sawyer::Container::Map<FunctionPtr, CfgConstEdgeSet> findFunctionReturnEdges(const PartitionerConstPtr&, 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 PartitionerConstPtr&, ControlFlowGraph &cfg/*in,out*/);

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

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

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

#endif
#endif