1 #ifndef ROSE_BinaryAnalysis_Partitioner2_ControlFlowGraph_H
2 #define ROSE_BinaryAnalysis_Partitioner2_ControlFlowGraph_H
3 #include <featureTests.h>
4 #ifdef ROSE_ENABLE_BINARY_ANALYSIS
6 #include <Rose/BinaryAnalysis/Partitioner2/BasicBlock.h>
7 #include <Rose/BinaryAnalysis/Partitioner2/BasicTypes.h>
8 #include <Rose/BinaryAnalysis/Partitioner2/Function.h>
9 #include <Rose/BinaryAnalysis/Partitioner2/Utility.h>
11 #include <Sawyer/BiMap.h>
12 #include <Sawyer/Graph.h>
13 #include <Sawyer/GraphIteratorSet.h>
14 #include <Sawyer/GraphIteratorBiMap.h>
15 #include <Sawyer/HashMap.h>
16 #include <Sawyer/Map.h>
17 #include <Sawyer/Optional.h>
19 #include <boost/serialization/access.hpp>
24 namespace BinaryAnalysis {
25 namespace Partitioner2 {
34 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
36 friend class boost::serialization::access;
39 void serialize(S &s,
const unsigned ) {
40 s & BOOST_SERIALIZATION_NVP(type_);
41 s & BOOST_SERIALIZATION_NVP(startVa_);
42 s & BOOST_SERIALIZATION_NVP(bblock_);
43 s & BOOST_SERIALIZATION_NVP(owningFunctions_);
59 startVa_ = bb->address();
64 ASSERT_forbid2(type==
V_BASIC_BLOCK,
"this constructor does not create basic block or placeholder vertices");
129 ASSERT_not_null(
function);
130 return owningFunctions_.
insert(
function);
139 if (
function != NULL)
140 owningFunctions_.
erase(
function);
147 return owningFunctions_.
exists(
function);
152 return owningFunctions_.
size();
163 return owningFunctions_;
166 return owningFunctions_;
190 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
192 friend class boost::serialization::access;
195 void serialize(S &s,
const unsigned ) {
196 s & BOOST_SERIALIZATION_NVP(type_);
197 s & BOOST_SERIALIZATION_NVP(confidence_);
225 bool sortEdgesBySrc(
const ControlFlowGraph::ConstEdgeIterator&,
const ControlFlowGraph::ConstEdgeIterator&);
228 bool sortEdgesByDst(
const ControlFlowGraph::ConstEdgeIterator&,
const ControlFlowGraph::ConstEdgeIterator&);
231 bool sortEdgesById(
const ControlFlowGraph::ConstEdgeIterator&,
const ControlFlowGraph::ConstEdgeIterator&);
234 bool sortVerticesByAddress(
const ControlFlowGraph::ConstVertexIterator&,
const ControlFlowGraph::ConstVertexIterator&);
237 bool sortVerticesById(
const ControlFlowGraph::ConstVertexIterator&,
const ControlFlowGraph::ConstVertexIterator&);
303 : partitioner(partitioner), startVa(startVa), bblock(bblock) {}
319 : partitioner(partitioner), startVa(startVa), bblock(bblock) {}
323 virtual bool operator()(
bool chain,
const AttachedBasicBlock&) = 0;
326 virtual bool operator()(
bool chain,
const DetachedBasicBlock&) = 0;
337 void insertCfg(ControlFlowGraph &dst,
const ControlFlowGraph &src, CfgVertexMap &vmap );
343 CfgConstEdgeSet
findBackEdges(
const ControlFlowGraph &cfg,
const ControlFlowGraph::ConstVertexIterator &begin);
348 CfgConstEdgeSet
findCallEdges(
const ControlFlowGraph::ConstVertexIterator &callSite);
353 CfgConstVertexSet
findCalledFunctions(
const ControlFlowGraph &cfg,
const ControlFlowGraph::ConstVertexIterator &callSite);
365 CfgConstEdgeSet
findCallReturnEdges(
const ControlFlowGraph::ConstVertexIterator &callSite);
371 CfgConstVertexSet
findFunctionReturns(
const ControlFlowGraph &cfg,
const ControlFlowGraph::ConstVertexIterator &beginVertex);
390 void eraseEdges(ControlFlowGraph&,
const CfgConstEdgeSet &toErase);
409 CfgConstVertexSet
forwardMapped(
const CfgConstVertexSet&,
const CfgVertexMap&);
415 CfgConstVertexSet
reverseMapped(
const CfgConstVertexSet&,
const CfgVertexMap&);
440 ControlFlowGraph::VertexIterator &entry);
457 const ControlFlowGraph::ConstVertexIterator &gcfgEntry);
CfgVertex(VertexType type)
Construct a special vertex.
size_t size() const
Size of the set.
Sawyer::Optional< rose_addr_t > optionalAddress() const
Safe version of starting address.
void eraseOwningFunction(const Function::Ptr &function)
Remove a function from the list of functions that own this vertex.
CfgVertex(const BasicBlock::Ptr &bb)
Construct a basic block vertex.
const BasicBlock::Ptr & bblock() const
Property: basic block.
Base class for CFG-adjustment callbacks.
EdgeType type() const
Return edge type.
VertexType type() const
Returns the vertex type.
std::list< ControlFlowGraph::ConstVertexIterator > CfgConstVertexList
List of CFG vertex pointers.
EdgeType
Partitioner control flow edge types.
CfgConstEdgeSet findCallReturnEdges(const Partitioner &, const ControlFlowGraph &)
Return outgoing call-return edges.
Sawyer::Container::GraphIteratorSet< ControlFlowGraph::VertexIterator > CfgVertexSet
Set of CFG vertex pointers.
void address(rose_addr_t va)
Property: starting address.
bool insert(const Value &value)
Insert a value.
bool sortVerticesById(const ControlFlowGraph::ConstVertexIterator &, const ControlFlowGraph::ConstVertexIterator &)
Sort vertices by vertex ID number.
bool isOwningFunction(const Function::Ptr &function) const
Determines if a function owns this vertex.
bool exists(const Value &value) const
Whether a value exists.
Sawyer::Container::Graph< CfgVertex, CfgEdge > ControlFlowGraph
Control flow graph.
CfgVertex(rose_addr_t startVa)
Construct a basic block placeholder vertex.
bool sortEdgesById(const ControlFlowGraph::ConstEdgeIterator &, const ControlFlowGraph::ConstEdgeIterator &)
Sort edges by edge ID number.
Set of graph edge or vertex pointers (iterators).
void eraseEdges(ControlFlowGraph &, const CfgConstEdgeSet &toErase)
Erase multiple edges.
Confidence confidence() const
Property: Confidence.
Sawyer::Optional< rose_addr_t > optionalLastAddress() const
Address of last item in the vertex.
size_t nOwningFunctions() const
Number of functions that own this vertex.
Sawyer::Container::HashMap< rose_addr_t, ControlFlowGraph::VertexIterator > CfgVertexIndex
Mapping from basic block starting address to CFG vertex.
Main namespace for the ROSE library.
Sawyer::Container::GraphIteratorSet< ControlFlowGraph::ConstVertexIterator > CfgConstVertexSet
Set of CFG vertex pointers.
VertexType
Partitioner control flow vertex types.
bool sortVerticesByAddress(const ControlFlowGraph::ConstVertexIterator &, const ControlFlowGraph::ConstVertexIterator &)
Sort vertices by address.
CfgConstVertexSet findFunctionReturns(const ControlFlowGraph &cfg, const ControlFlowGraph::ConstVertexIterator &beginVertex)
Find all function return vertices.
Sawyer::SharedPointer< CfgAdjustmentCallback > Ptr
Shared ownership pointer.
std::list< ControlFlowGraph::ConstEdgeIterator > CfgConstEdgeList
List of CFG edge pointers.
Bidirectional map of graph edge or vertex pointers.
CfgConstEdgeSet findCallEdges(const ControlFlowGraph::ConstVertexIterator &callSite)
Find function call edges.
std::list< ControlFlowGraph::EdgeIterator > CfgEdgeList
List of CFG edge pointers.
rose_addr_t startVa
Starting address for basic block or placeholder.
Arguments for attaching a basic block.
void expandFunctionReturnEdges(const Partitioner &, ControlFlowGraph &cfg)
Rewrite function return edges.
CfgConstVertexSet findDetachedVertices(const ControlFlowGraph &)
Find vertices that have zero degree.
CfgConstVertexSet reverseMapped(const CfgConstVertexSet &, const CfgVertexMap &)
Return corresponding iterators.
The value is an assumption without any proof.
rose_addr_t address() const
Property: starting address.
bool sortEdgesBySrc(const ControlFlowGraph::ConstEdgeIterator &, const ControlFlowGraph::ConstEdgeIterator &)
Sort edges by source vertex address.
bool sortEdgesByDst(const ControlFlowGraph::ConstEdgeIterator &, const ControlFlowGraph::ConstEdgeIterator &)
Sort edges by target vertex address.
Confidence
How sure are we of something.
rose_addr_t startVa
Starting address for basic block or placeholder.
Sawyer::Container::Map< Function::Ptr, CfgConstEdgeSet > findFunctionReturnEdges(const Partitioner &)
Find function return edges organized by function.
void confidence(Confidence c)
Property: Confidence.
Sawyer::Container::GraphIteratorSet< ControlFlowGraph::EdgeIterator > CfgEdgeSet
Set of CFG edge pointers.
A basic block or placeholder for a basic block.
Normal control flow edge, nothing special.
const FunctionSet & owningFunctions() const
Property: Owning functions.
CfgEdge()
Construct a new normal edge.
ControlFlowGraph functionCfgByErasure(const ControlFlowGraph &gcfg, const Function::Ptr &function, ControlFlowGraph::VertexIterator &entry)
Generate a function control flow graph.
void nullify()
Turns a basic block vertex into a placeholder.
bool erase(const Value &value)
Erase a value.
std::list< ControlFlowGraph::VertexIterator > CfgVertexList
List of CFG vertex pointers.
BasicBlock::Ptr bblock
Optional basic block; otherwise a placeholder operation.
CfgEdge(EdgeType type, Confidence confidence=ASSUMED)
Construct an edge with a specified type and confidence.
BasicBlock::Ptr bblock
Optional basic block; otherwise a placeholder operation.
CfgConstVertexSet forwardMapped(const CfgConstVertexSet &, const CfgVertexMap &)
Return corresponding iterators.
Sawyer::SharedPointer< BasicBlock > Ptr
Shared pointer to a basic block.
Base class for reference counted objects.
CfgConstVertexSet findIncidentVertices(const CfgConstEdgeSet &)
Vertices that are incident to specified edges.
Arguments for detaching a basic block.
Sawyer::Container::GraphIteratorBiMap< ControlFlowGraph::ConstVertexIterator, ControlFlowGraph::ConstVertexIterator > CfgVertexMap
Map vertices from one CFG to another CFG and vice versa.
Function::Ptr isEntryBlock() const
Is block a function entry block?
const Partitioner * partitioner
Partitioner in which change occurred.
CfgConstVertexSet findCalledFunctions(const ControlFlowGraph &cfg, const ControlFlowGraph::ConstVertexIterator &callSite)
Find called functions.
Special vertex destination for non-existing basic blocks.
Sawyer::Container::GraphIteratorSet< ControlFlowGraph::ConstEdgeIterator > CfgConstEdgeSet
Set of CFG edge pointers.
CfgConstEdgeSet findBackEdges(const ControlFlowGraph &cfg, const ControlFlowGraph::ConstVertexIterator &begin)
Find back edges.
Partitions instructions into basic blocks and functions.
FunctionPtr Ptr
Shared-ownership pointer for function.
const Partitioner * partitioner
Partitioner in which change occurred.
void insertCfg(ControlFlowGraph &dst, const ControlFlowGraph &src, CfgVertexMap &vmap)
Insert one control flow graph into another.
FunctionSet & owningFunctions()
Property: Owning functions.
void bblock(const BasicBlock::Ptr &bb)
Property: basic block.
Control flow graph vertex.
ControlFlowGraph functionCfgByReachability(const ControlFlowGraph &gcfg, const Function::Ptr &function, const ControlFlowGraph::ConstVertexIterator &gcfgEntry)
Generate a function control flow graph.
Container associating values with keys.
virtual bool operator()(bool chain, const AttachedBasicBlock &)=0
Called when basic block is attached or placeholder inserted.
bool insertOwningFunction(const Function::Ptr &function)
Add a function to the list of functions that own this vertex.
AddressIntervalSet addresses() const
Compute entire address set.