ROSE  0.11.145.0
ControlFlowGraph.h
1 #ifndef ROSE_BinaryAnalysis_Partitioner2_ControlFlowGraph_H
2 #define ROSE_BinaryAnalysis_Partitioner2_ControlFlowGraph_H
3 #include <featureTests.h>
4 #ifdef ROSE_ENABLE_BINARY_ANALYSIS
5 #include <Rose/BinaryAnalysis/Partitioner2/BasicTypes.h>
6 
7 #include <Rose/BinaryAnalysis/Partitioner2/Utility.h>
8 
9 #include <Sawyer/BiMap.h>
10 #include <Sawyer/Graph.h>
11 #include <Sawyer/GraphIteratorSet.h>
12 #include <Sawyer/GraphIteratorBiMap.h>
13 #include <Sawyer/HashMap.h>
14 #include <Sawyer/Map.h>
15 #include <Sawyer/Optional.h>
16 
17 #include <boost/serialization/access.hpp>
18 #include <list>
19 #include <ostream>
20 
21 namespace Rose {
22 namespace BinaryAnalysis {
23 namespace Partitioner2 {
24 
26 class CfgVertex {
27  VertexType type_; // type of vertex, special or not
28  rose_addr_t startVa_; // address of start of basic block
29  BasicBlockPtr bblock_; // basic block, or null if only a place holder
30  FunctionSet owningFunctions_; // functions to which vertex belongs
31 
32 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
33 private:
34  friend class boost::serialization::access;
35 
36  template<class S>
37  void serialize(S &s, const unsigned /*version*/) {
38  s & BOOST_SERIALIZATION_NVP(type_);
39  s & BOOST_SERIALIZATION_NVP(startVa_);
40  s & BOOST_SERIALIZATION_NVP(bblock_);
41  s & BOOST_SERIALIZATION_NVP(owningFunctions_);
42  }
43 #endif
44 
45 public:
46  // intentionally undocumented. Necessary for serialization of Sawyer::Container::Graph
47  CfgVertex();
48  ~CfgVertex();
49 
51  explicit CfgVertex(rose_addr_t startVa);
52 
54  explicit CfgVertex(const BasicBlockPtr &bb);
55 
57  /*implicit*/ CfgVertex(VertexType type);
58 
60  VertexType type() const;
61 
70  rose_addr_t address() const;
71  void address(rose_addr_t);
78 
84 
93 
101  const BasicBlockPtr& bblock() const;
102  void bblock(const BasicBlockPtr&);
108  bool insertOwningFunction(const FunctionPtr&);
109 
114  void eraseOwningFunction(const FunctionPtr&);
115 
119  bool isOwningFunction(const FunctionPtr&) const;
120 
122  size_t nOwningFunctions() const;
123 
131  const FunctionSet& owningFunctions() const;
138  FunctionPtr isEntryBlock() const;
139 
143  void nullify();
144 };
145 
147 class CfgEdge {
148 private:
149  EdgeType type_;
150  Confidence confidence_;
151 
152 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
153 private:
154  friend class boost::serialization::access;
155 
156  template<class S>
157  void serialize(S &s, const unsigned /*version*/) {
158  s & BOOST_SERIALIZATION_NVP(type_);
159  s & BOOST_SERIALIZATION_NVP(confidence_);
160  }
161 #endif
162 
163 public:
164  ~CfgEdge();
165 
167  CfgEdge();
168 
171 
173  EdgeType type() const;
174 
180  Confidence confidence() const;
181  void confidence(Confidence);
183 };
184 
186 bool sortEdgesBySrc(const ControlFlowGraph::ConstEdgeIterator&, const ControlFlowGraph::ConstEdgeIterator&);
187 
189 bool sortEdgesByDst(const ControlFlowGraph::ConstEdgeIterator&, const ControlFlowGraph::ConstEdgeIterator&);
190 
192 bool sortEdgesById(const ControlFlowGraph::ConstEdgeIterator&, const ControlFlowGraph::ConstEdgeIterator&);
193 
195 bool sortVerticesByAddress(const ControlFlowGraph::ConstVertexIterator&, const ControlFlowGraph::ConstVertexIterator&);
196 
198 bool sortVerticesById(const ControlFlowGraph::ConstVertexIterator&, const ControlFlowGraph::ConstVertexIterator&);
199 
201 std::ostream& operator<<(std::ostream&, const ControlFlowGraph::Vertex&);
202 
204 std::ostream& operator<<(std::ostream&, const ControlFlowGraph::Edge&);
205 
208 
212 typedef std::list<ControlFlowGraph::VertexIterator> CfgVertexList;
213 typedef std::list<ControlFlowGraph::ConstVertexIterator> CfgConstVertexList;
219 typedef std::list<ControlFlowGraph::EdgeIterator> CfgEdgeList;
220 typedef std::list<ControlFlowGraph::ConstEdgeIterator> CfgConstEdgeList;
238 typedef Sawyer::Container::GraphIteratorBiMap<ControlFlowGraph::ConstVertexIterator,
239  ControlFlowGraph::ConstVertexIterator> CfgVertexMap;
240 
248 public:
251 
261  rose_addr_t startVa;
263  AttachedBasicBlock(const PartitionerPtr&, rose_addr_t startVa, const BasicBlockPtr&);
265  };
266 
277  rose_addr_t startVa;
279  DetachedBasicBlock(const PartitionerPtr&, rose_addr_t startVa, const BasicBlockPtr&);
281  };
282 
284  virtual bool operator()(bool chain, const AttachedBasicBlock&) = 0;
285 
287  virtual bool operator()(bool chain, const DetachedBasicBlock&) = 0;
288 };
289 
291 // Control flow graph utility functions
293 
298 void insertCfg(ControlFlowGraph &dst, const ControlFlowGraph &src, CfgVertexMap &vmap /*out*/);
299 
304 CfgConstEdgeSet findBackEdges(const ControlFlowGraph &cfg, const ControlFlowGraph::ConstVertexIterator &begin);
305 
309 CfgConstEdgeSet findCallEdges(const ControlFlowGraph::ConstVertexIterator &callSite);
310 
314 CfgConstVertexSet findCalledFunctions(const ControlFlowGraph &cfg, const ControlFlowGraph::ConstVertexIterator &callSite);
315 
325 CfgConstEdgeSet findCallReturnEdges(const PartitionerConstPtr&, const ControlFlowGraph&);
326 CfgConstEdgeSet findCallReturnEdges(const ControlFlowGraph::ConstVertexIterator &callSite);
332 CfgConstVertexSet findFunctionReturns(const ControlFlowGraph &cfg, const ControlFlowGraph::ConstVertexIterator &beginVertex);
333 
351 void eraseEdges(ControlFlowGraph&, const CfgConstEdgeSet &toErase);
352 
354 CfgConstVertexSet findIncidentVertices(const CfgConstEdgeSet&);
355 
362 CfgConstVertexSet findDetachedVertices(const ControlFlowGraph&);
363 CfgConstVertexSet findDetachedVertices(const CfgConstVertexSet &vertices);
370 CfgConstVertexSet forwardMapped(const CfgConstVertexSet&, const CfgVertexMap&);
371 
376 CfgConstVertexSet reverseMapped(const CfgConstVertexSet&, const CfgVertexMap&);
377 
385 
401  ControlFlowGraph::VertexIterator &entry/*out*/);
402 
418  const ControlFlowGraph::ConstVertexIterator &gcfgEntry);
419 
420 } // namespace
421 } // namespace
422 } // namespace
423 
424 #endif
425 #endif
Sawyer::Optional< rose_addr_t > optionalAddress() const
Safe version of starting address.
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.
PartitionerConstPtr partitioner
Partitioner in which change occurred.
Sawyer::Container::GraphIteratorSet< ControlFlowGraph::VertexIterator > CfgVertexSet
Set of CFG vertex pointers.
bool sortVerticesById(const ControlFlowGraph::ConstVertexIterator &, const ControlFlowGraph::ConstVertexIterator &)
Sort vertices by vertex ID number.
bool isOwningFunction(const FunctionPtr &) const
Determines if a function owns this 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.
void eraseOwningFunction(const FunctionPtr &)
Remove a function from the list of functions that own this vertex.
VertexType
Partitioner control flow vertex types.
void expandFunctionReturnEdges(const PartitionerConstPtr &, ControlFlowGraph &cfg)
Rewrite function return edges.
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.
ControlFlowGraph functionCfgByReachability(const ControlFlowGraph &gcfg, const FunctionPtr &function, const ControlFlowGraph::ConstVertexIterator &gcfgEntry)
Generate a function control flow graph.
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.
bool insertOwningFunction(const FunctionPtr &)
Add a function to the list of functions that own this vertex.
rose_addr_t startVa
Starting address for basic block or placeholder.
BasicBlockPtr bblock
Optional basic block; otherwise a placeholder operation.
CfgConstEdgeSet findCallReturnEdges(const PartitionerConstPtr &, const ControlFlowGraph &)
Return outgoing call-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.
rose_addr_t startVa
Starting address for basic block or placeholder.
Sawyer::Container::GraphIteratorSet< ControlFlowGraph::EdgeIterator > CfgEdgeSet
Set of CFG edge pointers.
const PartitionerPtr partitioner
Partitioner in which change occurred.
const FunctionSet & owningFunctions() const
Property: Owning functions.
CfgEdge()
Construct a new normal edge.
void nullify()
Turns a basic block vertex into a placeholder.
ControlFlowGraph functionCfgByErasure(const ControlFlowGraph &gcfg, const FunctionPtr &function, ControlFlowGraph::VertexIterator &entry)
Generate a function control flow graph.
std::list< ControlFlowGraph::VertexIterator > CfgVertexList
List of CFG vertex pointers.
const BasicBlockPtr & bblock() const
Property: basic block.
CfgConstVertexSet forwardMapped(const CfgConstVertexSet &, const CfgVertexMap &)
Return corresponding iterators.
Sawyer::Container::Map< FunctionPtr, CfgConstEdgeSet > findFunctionReturnEdges(const PartitionerConstPtr &)
Find function return edges organized by function.
Base class for reference counted objects.
Definition: SharedObject.h:64
CfgConstVertexSet findIncidentVertices(const CfgConstEdgeSet &)
Vertices that are incident to specified edges.
Sawyer::Container::GraphIteratorBiMap< ControlFlowGraph::ConstVertexIterator, ControlFlowGraph::ConstVertexIterator > CfgVertexMap
Map vertices from one CFG to another CFG and vice versa.
CfgConstVertexSet findCalledFunctions(const ControlFlowGraph &cfg, const ControlFlowGraph::ConstVertexIterator &callSite)
Find called functions.
BasicBlockPtr bblock
Optional basic block; otherwise a placeholder operation.
Sawyer::Container::GraphIteratorSet< ControlFlowGraph::ConstEdgeIterator > CfgConstEdgeSet
Set of CFG edge pointers.
CfgConstEdgeSet findBackEdges(const ControlFlowGraph &cfg, const ControlFlowGraph::ConstVertexIterator &begin)
Find back edges.
void insertCfg(ControlFlowGraph &dst, const ControlFlowGraph &src, CfgVertexMap &vmap)
Insert one control flow graph into another.
Container associating values with keys.
Definition: Sawyer/Map.h:66
FunctionPtr isEntryBlock() const
Is block a function entry block?
virtual bool operator()(bool chain, const AttachedBasicBlock &)=0
Called when basic block is attached or placeholder inserted.
AddressIntervalSet addresses() const
Compute entire address set.