ROSE  0.11.54.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 
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>
10 
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>
18 
19 #include <boost/serialization/access.hpp>
20 #include <list>
21 #include <ostream>
22 
23 namespace Rose {
24 namespace BinaryAnalysis {
25 namespace Partitioner2 {
26 
28 class CfgVertex {
29  VertexType type_; // type of vertex, special or not
30  rose_addr_t startVa_; // address of start of basic block
31  BasicBlock::Ptr bblock_; // basic block, or null if only a place holder
32  FunctionSet owningFunctions_; // functions to which vertex belongs
33 
34 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
35 private:
36  friend class boost::serialization::access;
37 
38  template<class S>
39  void serialize(S &s, const unsigned /*version*/) {
40  s & BOOST_SERIALIZATION_NVP(type_);
41  s & BOOST_SERIALIZATION_NVP(startVa_);
42  s & BOOST_SERIALIZATION_NVP(bblock_);
43  s & BOOST_SERIALIZATION_NVP(owningFunctions_);
44  }
45 #endif
46 
47 public:
48  // intentionally undocumented. Necessary for serialization of Sawyer::Container::Graph
49  CfgVertex()
50  : type_(V_USER_DEFINED), startVa_(0) {}
51 
52 public:
54  explicit CfgVertex(rose_addr_t startVa): type_(V_BASIC_BLOCK), startVa_(startVa) {}
55 
57  explicit CfgVertex(const BasicBlock::Ptr &bb): type_(V_BASIC_BLOCK), bblock_(bb) {
58  ASSERT_not_null(bb);
59  startVa_ = bb->address();
60  }
61 
63  /*implicit*/ CfgVertex(VertexType type): type_(type), startVa_(0) {
64  ASSERT_forbid2(type==V_BASIC_BLOCK, "this constructor does not create basic block or placeholder vertices");
65  }
66 
68  VertexType type() const { return type_; }
69 
78  rose_addr_t address() const {
79  ASSERT_require(V_BASIC_BLOCK==type_ || V_USER_DEFINED==type_ || V_NONEXISTING==type_);
80  return startVa_;
81  }
82  void address(rose_addr_t va) {
83  ASSERT_require(V_BASIC_BLOCK==type_ || V_USER_DEFINED==type_ || V_NONEXISTING==type_);
84  startVa_ = va;
85  }
92 
98 
107 
115  const BasicBlock::Ptr& bblock() const {
116  return bblock_;
117  }
118  void bblock(const BasicBlock::Ptr &bb) {
119  ASSERT_require(V_BASIC_BLOCK==type_ || V_USER_DEFINED==type_);
120  bblock_ = bb;
121  }
127  bool insertOwningFunction(const Function::Ptr &function) {
128  ASSERT_require(V_BASIC_BLOCK==type_ || V_USER_DEFINED==type_ || V_NONEXISTING==type_);
129  ASSERT_not_null(function);
130  return owningFunctions_.insert(function);
131  }
132 
137  void eraseOwningFunction(const Function::Ptr &function) {
138  ASSERT_require(V_BASIC_BLOCK==type_ || V_USER_DEFINED==type_ || V_NONEXISTING==type_);
139  if (function != NULL)
140  owningFunctions_.erase(function);
141  }
142 
146  bool isOwningFunction(const Function::Ptr &function) const {
147  return owningFunctions_.exists(function);
148  }
149 
151  size_t nOwningFunctions() const {
152  return owningFunctions_.size();
153  }
154 
162  const FunctionSet& owningFunctions() const {
163  return owningFunctions_;
164  }
166  return owningFunctions_;
167  }
173  Function::Ptr isEntryBlock() const;
174 
178  void nullify() {
179  ASSERT_require(V_BASIC_BLOCK==type_);
180  bblock_ = BasicBlock::Ptr();
181  }
182 };
183 
185 class CfgEdge {
186 private:
187  EdgeType type_;
188  Confidence confidence_;
189 
190 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
191 private:
192  friend class boost::serialization::access;
193 
194  template<class S>
195  void serialize(S &s, const unsigned /*version*/) {
196  s & BOOST_SERIALIZATION_NVP(type_);
197  s & BOOST_SERIALIZATION_NVP(confidence_);
198  }
199 #endif
200 
201 public:
203  CfgEdge(): type_(E_NORMAL), confidence_(ASSUMED) {}
204 
206  /*implicit*/ CfgEdge(EdgeType type, Confidence confidence=ASSUMED): type_(type), confidence_(confidence) {}
207 
209  EdgeType type() const { return type_; }
210 
216  Confidence confidence() const { return confidence_; }
217  void confidence(Confidence c) { confidence_ = c; }
219 };
220 
223 
225 bool sortEdgesBySrc(const ControlFlowGraph::ConstEdgeIterator&, const ControlFlowGraph::ConstEdgeIterator&);
226 
228 bool sortEdgesByDst(const ControlFlowGraph::ConstEdgeIterator&, const ControlFlowGraph::ConstEdgeIterator&);
229 
231 bool sortEdgesById(const ControlFlowGraph::ConstEdgeIterator&, const ControlFlowGraph::ConstEdgeIterator&);
232 
234 bool sortVerticesByAddress(const ControlFlowGraph::ConstVertexIterator&, const ControlFlowGraph::ConstVertexIterator&);
235 
237 bool sortVerticesById(const ControlFlowGraph::ConstVertexIterator&, const ControlFlowGraph::ConstVertexIterator&);
238 
240 std::ostream& operator<<(std::ostream&, const ControlFlowGraph::Vertex&);
241 
243 std::ostream& operator<<(std::ostream&, const ControlFlowGraph::Edge&);
244 
247 
251 typedef std::list<ControlFlowGraph::VertexIterator> CfgVertexList;
252 typedef std::list<ControlFlowGraph::ConstVertexIterator> CfgConstVertexList;
258 typedef std::list<ControlFlowGraph::EdgeIterator> CfgEdgeList;
259 typedef std::list<ControlFlowGraph::ConstEdgeIterator> CfgConstEdgeList;
277 typedef Sawyer::Container::GraphIteratorBiMap<ControlFlowGraph::ConstVertexIterator,
278  ControlFlowGraph::ConstVertexIterator> CfgVertexMap;
279 
287 public:
290 
300  rose_addr_t startVa;
302  AttachedBasicBlock(Partitioner *partitioner, rose_addr_t startVa, const BasicBlock::Ptr &bblock)
303  : partitioner(partitioner), startVa(startVa), bblock(bblock) {}
304  };
305 
316  rose_addr_t startVa;
318  DetachedBasicBlock(Partitioner *partitioner, rose_addr_t startVa, const BasicBlock::Ptr &bblock)
319  : partitioner(partitioner), startVa(startVa), bblock(bblock) {}
320  };
321 
323  virtual bool operator()(bool chain, const AttachedBasicBlock&) = 0;
324 
326  virtual bool operator()(bool chain, const DetachedBasicBlock&) = 0;
327 };
328 
330 // Control flow graph utility functions
332 
337 void insertCfg(ControlFlowGraph &dst, const ControlFlowGraph &src, CfgVertexMap &vmap /*out*/);
338 
343 CfgConstEdgeSet findBackEdges(const ControlFlowGraph &cfg, const ControlFlowGraph::ConstVertexIterator &begin);
344 
348 CfgConstEdgeSet findCallEdges(const ControlFlowGraph::ConstVertexIterator &callSite);
349 
353 CfgConstVertexSet findCalledFunctions(const ControlFlowGraph &cfg, const ControlFlowGraph::ConstVertexIterator &callSite);
354 
364 CfgConstEdgeSet findCallReturnEdges(const Partitioner&, const ControlFlowGraph&);
365 CfgConstEdgeSet findCallReturnEdges(const ControlFlowGraph::ConstVertexIterator &callSite);
371 CfgConstVertexSet findFunctionReturns(const ControlFlowGraph &cfg, const ControlFlowGraph::ConstVertexIterator &beginVertex);
372 
384 Sawyer::Container::Map<Function::Ptr, CfgConstEdgeSet> findFunctionReturnEdges(const Partitioner&, const ControlFlowGraph&);
390 void eraseEdges(ControlFlowGraph&, const CfgConstEdgeSet &toErase);
391 
393 CfgConstVertexSet findIncidentVertices(const CfgConstEdgeSet&);
394 
401 CfgConstVertexSet findDetachedVertices(const ControlFlowGraph&);
402 CfgConstVertexSet findDetachedVertices(const CfgConstVertexSet &vertices);
409 CfgConstVertexSet forwardMapped(const CfgConstVertexSet&, const CfgVertexMap&);
410 
415 CfgConstVertexSet reverseMapped(const CfgConstVertexSet&, const CfgVertexMap&);
416 
423 void expandFunctionReturnEdges(const Partitioner&, ControlFlowGraph &cfg/*in,out*/);
424 
439 ControlFlowGraph functionCfgByErasure(const ControlFlowGraph &gcfg, const Function::Ptr &function,
440  ControlFlowGraph::VertexIterator &entry/*out*/);
441 
456 ControlFlowGraph functionCfgByReachability(const ControlFlowGraph &gcfg, const Function::Ptr &function,
457  const ControlFlowGraph::ConstVertexIterator &gcfgEntry);
458 
459 } // namespace
460 } // namespace
461 } // namespace
462 
463 #endif
464 #endif
CfgVertex(VertexType type)
Construct a special vertex.
size_t size() const
Size of the set.
Definition: Set.h:174
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.
Definition: Set.h:228
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.
Definition: Set.h:145
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.
A container holding a set of values.
Definition: IntervalSet.h:55
Sawyer::SharedPointer< CfgAdjustmentCallback > Ptr
Shared ownership pointer to CfgAdjustmentCallback.
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.
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.
Definition: Set.h:248
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.
Definition: BasicBlock.h:134
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.
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.
Definition: Partitioner.h:290
FunctionPtr Ptr
Shared-ownership pointer for function.
Definition: Function.h:51
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.
ControlFlowGraph functionCfgByReachability(const ControlFlowGraph &gcfg, const Function::Ptr &function, const ControlFlowGraph::ConstVertexIterator &gcfgEntry)
Generate a function control flow graph.
Container associating values with keys.
Definition: Sawyer/Map.h:66
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.