ROSE  0.9.9.139
ControlFlowGraph.h
1 #ifndef ROSE_Partitioner2_ControlFlowGraph_H
2 #define ROSE_Partitioner2_ControlFlowGraph_H
3 
4 #include <Partitioner2/BasicBlock.h>
5 #include <Partitioner2/BasicTypes.h>
6 #include <Partitioner2/Function.h>
7 
8 #include <Sawyer/BiMap.h>
9 #include <Sawyer/Graph.h>
10 #include <Sawyer/Map.h>
11 
12 #include <boost/serialization/access.hpp>
13 #include <list>
14 #include <ostream>
15 
16 namespace Rose {
17 namespace BinaryAnalysis {
18 namespace Partitioner2 {
19 
21 class CfgVertex {
22  VertexType type_; // type of vertex, special or not
23  rose_addr_t startVa_; // address of start of basic block
24  BasicBlock::Ptr bblock_; // basic block, or null if only a place holder
25  FunctionSet owningFunctions_; // functions to which vertex belongs
26 
27 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
28 private:
29  friend class boost::serialization::access;
30 
31  template<class S>
32  void serialize(S &s, const unsigned version) {
33  s & BOOST_SERIALIZATION_NVP(type_);
34  s & BOOST_SERIALIZATION_NVP(startVa_);
35  s & BOOST_SERIALIZATION_NVP(bblock_);
36  s & BOOST_SERIALIZATION_NVP(owningFunctions_);
37  }
38 #endif
39 
40 public:
41  // intentionally undocumented. Necessary for serialization of Sawyer::Container::Graph
42  CfgVertex()
43  : type_(V_USER_DEFINED), startVa_(0) {}
44 
45 public:
47  explicit CfgVertex(rose_addr_t startVa): type_(V_BASIC_BLOCK), startVa_(startVa) {}
48 
50  explicit CfgVertex(const BasicBlock::Ptr &bb): type_(V_BASIC_BLOCK), bblock_(bb) {
51  ASSERT_not_null(bb);
52  startVa_ = bb->address();
53  }
54 
56  /*implicit*/ CfgVertex(VertexType type): type_(type), startVa_(0) {
57  ASSERT_forbid2(type==V_BASIC_BLOCK, "this constructor does not create basic block or placeholder vertices");
58  }
59 
61  VertexType type() const { return type_; }
62 
68  rose_addr_t address() const {
69  ASSERT_require(V_BASIC_BLOCK==type_ || V_USER_DEFINED==type_);
70  return startVa_;
71  }
72  void address(rose_addr_t va) {
73  ASSERT_require(V_BASIC_BLOCK==type_ || V_USER_DEFINED==type_);
74  startVa_ = va;
75  }
86 
93  const BasicBlock::Ptr& bblock() const {
94  ASSERT_require(V_BASIC_BLOCK==type_ || V_USER_DEFINED==type_);
95  return bblock_;
96  }
97  void bblock(const BasicBlock::Ptr &bb) {
98  ASSERT_require(V_BASIC_BLOCK==type_ || V_USER_DEFINED==type_);
99  bblock_ = bb;
100  }
106  bool insertOwningFunction(const Function::Ptr &function) {
107  ASSERT_require(V_BASIC_BLOCK==type_ || V_USER_DEFINED==type_);
108  ASSERT_not_null(function);
109  return owningFunctions_.insert(function);
110  }
111 
116  void eraseOwningFunction(const Function::Ptr &function) {
117  ASSERT_require(V_BASIC_BLOCK==type_ || V_USER_DEFINED==type_);
118  if (function != NULL)
119  owningFunctions_.erase(function);
120  }
121 
125  bool isOwningFunction(const Function::Ptr &function) const {
126  return owningFunctions_.exists(function);
127  }
128 
130  size_t nOwningFunctions() const {
131  return owningFunctions_.size();
132  }
133 
141  const FunctionSet& owningFunctions() const {
142  return owningFunctions_;
143  }
145  return owningFunctions_;
146  }
152  Function::Ptr isEntryBlock() const;
153 
157  void nullify() {
158  ASSERT_require(V_BASIC_BLOCK==type_);
159  bblock_ = BasicBlock::Ptr();
160  }
161 };
162 
164 class CfgEdge {
165 private:
166  EdgeType type_;
167  Confidence confidence_;
168 
169 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
170 private:
171  friend class boost::serialization::access;
172 
173  template<class S>
174  void serialize(S &s, const unsigned version) {
175  s & BOOST_SERIALIZATION_NVP(type_);
176  s & BOOST_SERIALIZATION_NVP(confidence_);
177  }
178 #endif
179 
180 public:
181  CfgEdge(): type_(E_NORMAL), confidence_(ASSUMED) {}
182  /*implicit*/ CfgEdge(EdgeType type, Confidence confidence=ASSUMED): type_(type), confidence_(confidence) {}
183  EdgeType type() const { return type_; }
184  Confidence confidence() const { return confidence_; }
185  void confidence(Confidence c) { confidence_ = c; }
186 };
187 
190 
193 
197 typedef std::list<ControlFlowGraph::VertexIterator> CfgVertexList;
198 typedef std::list<ControlFlowGraph::ConstVertexIterator> CfgConstVertexList;
204 typedef std::list<ControlFlowGraph::EdgeIterator> CfgEdgeList;
205 typedef std::list<ControlFlowGraph::ConstEdgeIterator> CfgConstEdgeList;
211 typedef std::set<ControlFlowGraph::VertexIterator> CfgVertexSet;
212 typedef std::set<ControlFlowGraph::ConstVertexIterator> CfgConstVertexSet;
218 typedef std::set<ControlFlowGraph::EdgeIterator> CfgEdgeSet;
219 typedef std::set<ControlFlowGraph::ConstEdgeIterator> CfgConstEdgeSet;
224 
225 
226 
227 
235 public:
238 
248  rose_addr_t startVa;
250  AttachedBasicBlock(Partitioner *partitioner, rose_addr_t startVa, const BasicBlock::Ptr &bblock)
251  : partitioner(partitioner), startVa(startVa), bblock(bblock) {}
252  };
253 
264  rose_addr_t startVa;
266  DetachedBasicBlock(Partitioner *partitioner, rose_addr_t startVa, const BasicBlock::Ptr &bblock)
267  : partitioner(partitioner), startVa(startVa), bblock(bblock) {}
268  };
269 
271  virtual bool operator()(bool chain, const AttachedBasicBlock&) = 0;
272 
274  virtual bool operator()(bool chain, const DetachedBasicBlock&) = 0;
275 };
276 
278 // Control flow graph utility functions
280 
285 void insertCfg(ControlFlowGraph &dst, const ControlFlowGraph &src, CfgVertexMap &vmap /*out*/);
286 
291 CfgConstEdgeSet findBackEdges(const ControlFlowGraph &cfg, const ControlFlowGraph::ConstVertexIterator &begin);
292 
296 CfgConstEdgeSet findCallEdges(const ControlFlowGraph::ConstVertexIterator &callSite);
297 
301 CfgConstVertexSet findCalledFunctions(const ControlFlowGraph &cfg, const ControlFlowGraph::ConstVertexIterator &callSite);
302 
307 CfgConstEdgeSet findCallReturnEdges(const ControlFlowGraph::ConstVertexIterator &callSite);
308 
312 CfgConstVertexSet findFunctionReturns(const ControlFlowGraph &cfg, const ControlFlowGraph::ConstVertexIterator &beginVertex);
313 
317 void eraseEdges(ControlFlowGraph&, const CfgConstEdgeSet &toErase);
318 
320 CfgConstVertexSet findIncidentVertices(const CfgConstEdgeSet&);
321 
328 CfgConstVertexSet findDetachedVertices(const ControlFlowGraph&);
329 CfgConstVertexSet findDetachedVertices(const CfgConstVertexSet &vertices);
336 CfgConstVertexSet forwardMapped(const CfgConstVertexSet&, const CfgVertexMap&);
337 
342 CfgConstVertexSet reverseMapped(const CfgConstVertexSet&, const CfgVertexMap&);
343 
344 } // namespace
345 } // namespace
346 } // namespace
347 
348 #endif
CfgVertex(VertexType type)
Construct a special vertex.
size_t size() const
Size of the set.
Definition: Set.h:168
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.
VertexType type() const
Returns the vertex type.
std::list< ControlFlowGraph::ConstVertexIterator > CfgConstVertexList
List of CFG vertex pointers.
EdgeType
Partitioner control flow edge types.
Definition: BasicTypes.h:30
void address(rose_addr_t va)
Property: starting address.
bool insert(const Value &value)
Insert a value.
Definition: Set.h:222
Sawyer::Container::Map< rose_addr_t, ControlFlowGraph::VertexIterator > CfgVertexIndex
Mapping from basic block starting address to CFG vertex.
std::set< ControlFlowGraph::ConstVertexIterator > CfgConstVertexSet
Set of CFG vertex pointers.
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:139
Sawyer::Container::Graph< CfgVertex, CfgEdge > ControlFlowGraph
Control flow graph.
CfgVertex(rose_addr_t startVa)
Construct a basic block placeholder vertex.
void eraseEdges(ControlFlowGraph &, const CfgConstEdgeSet &toErase)
Erase multiple edges.
size_t nOwningFunctions() const
Number of functions that own this vertex.
Main namespace for the ROSE library.
VertexType
Partitioner control flow vertex types.
Definition: BasicTypes.h:19
Sawyer::Container::BiMap< ControlFlowGraph::ConstVertexIterator, ControlFlowGraph::ConstVertexIterator > CfgVertexMap
Map vertices from one CFG to another CFG and vice versa.
CfgConstVertexSet findFunctionReturns(const ControlFlowGraph &cfg, const ControlFlowGraph::ConstVertexIterator &beginVertex)
Find function return vertices.
Sawyer::SharedPointer< CfgAdjustmentCallback > Ptr
Shared ownership pointer to CfgAdjustmentCallback.
std::list< ControlFlowGraph::ConstEdgeIterator > CfgConstEdgeList
List of CFG edge pointers.
CfgConstEdgeSet findCallEdges(const ControlFlowGraph::ConstVertexIterator &callSite)
Find function call edges.
CfgConstEdgeSet findCallReturnEdges(const ControlFlowGraph::ConstVertexIterator &callSite)
Return outgoing call-return edges.
std::list< ControlFlowGraph::EdgeIterator > CfgEdgeList
List of CFG edge pointers.
rose_addr_t startVa
Starting address for basic block or placeholder.
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.
Definition: BasicTypes.h:55
rose_addr_t address() const
Property: starting address.
Confidence
How sure are we of something.
Definition: BasicTypes.h:54
rose_addr_t startVa
Starting address for basic block or placeholder.
std::set< ControlFlowGraph::ConstEdgeIterator > CfgConstEdgeSet
Set of CFG edge pointers.
A basic block or placeholder for a basic block.
Definition: BasicTypes.h:20
Normal control flow edge, nothing special.
Definition: BasicTypes.h:31
const FunctionSet & owningFunctions() const
Property: Owning functions.
void nullify()
Turns a basic block vertex into a placeholder.
std::set< ControlFlowGraph::EdgeIterator > CfgEdgeSet
Set of CFG edge pointers.
bool erase(const Value &value)
Erase a value.
Definition: Set.h:242
std::list< ControlFlowGraph::VertexIterator > CfgVertexList
List of CFG vertex pointers.
BasicBlock::Ptr bblock
Optional basic block; otherwise a placeholder operation.
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:37
Base class for reference counted objects.
Definition: SharedObject.h:22
CfgConstVertexSet findIncidentVertices(const CfgConstEdgeSet &)
Vertices that are incident to specified edges.
Function::Ptr isEntryBlock() const
Is block a function entry block?
std::set< ControlFlowGraph::VertexIterator > CfgVertexSet
Set of CFG vertex pointers.
const Partitioner * partitioner
Partitioner in which change occurred.
CfgConstVertexSet findCalledFunctions(const ControlFlowGraph &cfg, const ControlFlowGraph::ConstVertexIterator &callSite)
Find called functions.
CfgConstEdgeSet findBackEdges(const ControlFlowGraph &cfg, const ControlFlowGraph::ConstVertexIterator &begin)
Find back edges.
Partitions instructions into basic blocks and functions.
Definition: Partitioner.h:290
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.
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.