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>
 
#ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
#include <boost/serialization/access.hpp>
#endif
 
#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&, unsigned version);
#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&, unsigned version);
#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