ROSE  0.9.9.139
CfgPath.h
1 #ifndef ROSE_Partitioner2_CfgPath_H
2 #define ROSE_Partitioner2_CfgPath_H
3 
4 #include <Partitioner2/ControlFlowGraph.h>
5 
6 namespace Rose {
7 namespace BinaryAnalysis {
8 namespace Partitioner2 {
9 
15 class CfgPath {
16 public:
18  typedef std::vector<ControlFlowGraph::ConstEdgeIterator> Edges;
19 
21  typedef std::vector<ControlFlowGraph::ConstVertexIterator> Vertices;
22 
23 private:
25  Edges edges_;
26 
27 public:
29  CfgPath() {}
30 
32  explicit CfgPath(const ControlFlowGraph::ConstVertexIterator &vertex): frontVertex_(vertex) {}
33 
35  explicit CfgPath(const ControlFlowGraph::ConstEdgeIterator &edge)
36  : frontVertex_(edge->source()), edges_(1, edge) {}
37 
39  void clear() {
40  frontVertex_ = Sawyer::Nothing();
41  edges_.clear();
42  }
43 
45  bool isEmpty() const {
46  return !frontVertex_;
47  }
48 
53  bool isConnected() const;
54 
58  size_t nEdges() const {
59  return edges_.size();
60  }
61 
65  size_t nVertices() const {
66  return isEmpty() ? 0 : (1+nEdges());
67  }
68 
72  ControlFlowGraph::ConstVertexIterator frontVertex() const {
73  ASSERT_forbid(isEmpty());
74  return *frontVertex_;
75  }
76 
80  ControlFlowGraph::ConstVertexIterator backVertex() const {
81  ASSERT_forbid(isEmpty());
82  return edges_.empty() ? *frontVertex_ : edges_.back()->target();
83  }
84 
88  const Edges& edges() const {
89  return edges_;
90  }
91 
96  Vertices vertices() const;
97 
101  void pushBack(const ControlFlowGraph::ConstEdgeIterator &edge);
102 
109  void pushFront(const ControlFlowGraph::ConstEdgeIterator &edge);
110 
116  void popBack();
117 
126  std::vector<ControlFlowGraph::ConstEdgeIterator> backtrack();
127 
129  size_t nVisits(const ControlFlowGraph::ConstVertexIterator &vertex) const;
130 
132  size_t nVisits(const ControlFlowGraph::ConstEdgeIterator &edge) const;
133 
138  size_t nCalls(const Function::Ptr &function = Function::Ptr()) const;
139 
144  size_t nReturns(const Function::Ptr &function = Function::Ptr()) const;
145 
152  ssize_t callDepth(const Function::Ptr &function = Function::Ptr()) const;
153 
159  size_t maxCallDepth(const Function::Ptr &function = Function::Ptr()) const;
160 
169  std::vector<ControlFlowGraph::ConstEdgeIterator> truncate(const ControlFlowGraph::ConstEdgeIterator&);
170  std::vector<ControlFlowGraph::ConstEdgeIterator> truncate(const CfgConstEdgeSet&);
174  void print(std::ostream &out) const;
175 };
176 
178 // Functions for operating on paths
180 
187 std::vector<bool>
188 findPathEdges(const ControlFlowGraph &graph,
189  const CfgConstVertexSet &beginVertices, const CfgConstVertexSet &endVertices,
190  const CfgConstVertexSet &avoidVertices = CfgConstVertexSet(),
191  const CfgConstEdgeSet &avoidEdges = CfgConstEdgeSet(), bool avoidCallsAndReturns = false);
192 
199  const CfgConstVertexSet &beginVertices, const CfgConstVertexSet &endVertices,
200  const CfgConstVertexSet &avoidVertices = CfgConstVertexSet(),
201  const CfgConstEdgeSet &avoidEdges = CfgConstEdgeSet(),
202  bool avoidCallsAndReturns = false);
203 
210  const CfgConstVertexSet &beginVertices, const CfgConstVertexSet &endVertices,
211  const CfgConstVertexSet &avoidVertices = CfgConstVertexSet(),
212  const CfgConstEdgeSet &avoidEdges = CfgConstEdgeSet(),
213  bool avoidCallsAndReturns = false);
214 
222 size_t
223 eraseUnreachablePaths(ControlFlowGraph &graph /*in,out*/, CfgConstVertexSet &beginVertices /*in,out*/,
224  CfgConstVertexSet &endVertices /*in,out*/, CfgVertexMap &vmap /*in,out*/, CfgPath &path /*in,out*/);
225 
241 void
242 findPaths(const ControlFlowGraph &srcCfg, ControlFlowGraph &paths /*out*/, CfgVertexMap &vmap /*out*/,
243  const CfgConstVertexSet &beginVertices, const CfgConstVertexSet &endVertices,
244  const CfgConstVertexSet &avoidVertices = CfgConstVertexSet(),
245  const CfgConstEdgeSet &avoidEdges = CfgConstEdgeSet(),
246  bool avoidCallsAndReturns = false);
247 
251 void
252 findFunctionPaths(const ControlFlowGraph &srcCfg, ControlFlowGraph &paths /*out*/, CfgVertexMap &vmap /*out*/,
253  const CfgConstVertexSet &beginVertices, const CfgConstVertexSet &endVertices,
254  const CfgConstVertexSet &avoidVertices = CfgConstVertexSet(),
255  const CfgConstEdgeSet &avoidEdges = CfgConstEdgeSet());
256 
262 void
263 findInterFunctionPaths(const ControlFlowGraph &srcCfg, ControlFlowGraph &paths /*out*/, CfgVertexMap &vmap /*out*/,
264  const CfgConstVertexSet &beginVertices, const CfgConstVertexSet &endVertices,
265  const CfgConstVertexSet &avoidVertices = CfgConstVertexSet(),
266  const CfgConstEdgeSet &avoidEdges = CfgConstEdgeSet());
267 
296 bool
297 insertCalleePaths(ControlFlowGraph &paths /*in,out*/, const ControlFlowGraph::ConstVertexIterator &pathsCallSite,
298  const ControlFlowGraph &cfg, const ControlFlowGraph::ConstVertexIterator &cfgCallSite,
299  const CfgConstVertexSet &cfgAvoidVertices = CfgConstVertexSet(),
300  const CfgConstEdgeSet &cfgAvoidEdges = CfgConstEdgeSet(),
301  std::vector<ControlFlowGraph::ConstVertexIterator> *newEdges = NULL);
302 bool
303 insertCalleePaths(ControlFlowGraph &paths /*in,out*/, const ControlFlowGraph::ConstVertexIterator &pathsCallSite,
304  const ControlFlowGraph &cfg, const ControlFlowGraph::ConstEdgeIterator &cfgCallEdge,
305  const CfgConstVertexSet &cfgAvoidVertices = CfgConstVertexSet(),
306  const CfgConstEdgeSet &cfgAvoidEdges = CfgConstEdgeSet(),
307  std::vector<ControlFlowGraph::ConstVertexIterator> *newEdges = NULL);
325 class Inliner {
326 public:
327 
329  enum HowInline {
333  };
334 
339  size_t maxCallDepth_; // max depth for inlining
340  protected:
341  ShouldInline(): maxCallDepth_(100) {}
342  public:
343  virtual ~ShouldInline() {}
344 
347 
349  static Ptr instance() { return Ptr(new ShouldInline); }
350 
354  size_t maxCallDepth() const { return maxCallDepth_; }
355  void maxCallDepth(size_t n) { maxCallDepth_ = n; }
359  virtual HowInline operator()(const Partitioner&, const ControlFlowGraph::ConstEdgeIterator cfgCallEdge,
360  const ControlFlowGraph &paths, const ControlFlowGraph::ConstVertexIterator &pathsCallSite,
361  size_t callDepth);
362  };
363 
364 private:
365  struct CallSite {
367  size_t callDepth;
368  CallSite(const ControlFlowGraph::ConstVertexIterator &pathsVertex, size_t callDepth)
369  : pathsVertex(pathsVertex), callDepth(callDepth) {}
370  };
371 
372  ControlFlowGraph paths_; // the resulting paths graph
373  CfgVertexMap vmap_; // relates CFG vertices to paths graph vertices
374  CfgConstVertexSet pathsBeginVertices_; // vertices where traversal starts
375  CfgConstVertexSet pathsEndVertices_; // vertices where traversal ends
376  std::list<CallSite> workList_; // call sites to be processed
377  ShouldInline::Ptr shouldInline_; // user predicate for whether to inline a call
378 
379 public:
384  : shouldInline_(ShouldInline::instance()) {}
385 
392  ShouldInline::Ptr shouldInline() const { return shouldInline_; }
393  void shouldInline(const ShouldInline::Ptr &p) { shouldInline_ = p; }
405  void inlinePaths(const Partitioner &partitioner, const CfgConstVertexSet &cfgBeginVertices,
406  const CfgConstVertexSet &cfgEndVertices, const CfgConstVertexSet &cfgAvoidVertices,
407  const CfgConstEdgeSet &cfgAvoidEdges);
408 
412  const ControlFlowGraph& paths() const { return paths_; }
413 
418  const CfgConstVertexSet& pathsBeginVertices() const { return pathsBeginVertices_; }
419 
424  const CfgConstVertexSet& pathsEndVertices() const { return pathsEndVertices_; }
425 
426 private:
427  void reset(const Partitioner &partitioner, const CfgConstVertexSet &cfgBeginVertices,
428  const CfgConstVertexSet &cfgEndVertices, const CfgConstVertexSet &cfgAvoidVertices,
429  const CfgConstEdgeSet &cfgAvoidEdges);
430 
431  // Returns true if pathVertex is a function call. Does so by consulting the corresponding vertex in the partitioner's
432  // global CFG.
433  static bool isFunctionCall(const Partitioner&, const ControlFlowGraph::ConstVertexIterator &pathVertex);
434 
435  // Convert a path vertex to the corresponding vertex in the partitioner's global CFG.
436  static ControlFlowGraph::ConstVertexIterator pathToCfg(const Partitioner &partitioner,
437  const ControlFlowGraph::ConstVertexIterator &pathVertex);
438 
439  // Convert global CFG vertices to paths graph vertices. */
440  static CfgConstVertexSet cfgToPaths(const CfgConstVertexSet &vertices, const CfgVertexMap &vmap);
441 };
442 
443 
444 
445 
446 std::ostream& operator<<(std::ostream &out, const CfgPath &path);
447 
448 } // namespace
449 } // namespace
450 } // namespace
451 
452 #endif
std::vector< ControlFlowGraph::ConstVertexIterator > Vertices
Stack of vertices.
Definition: CfgPath.h:21
void inlinePaths(const Partitioner &partitioner, const CfgConstVertexSet &cfgBeginVertices, const CfgConstVertexSet &cfgEndVertices, const CfgConstVertexSet &cfgAvoidVertices, const CfgConstEdgeSet &cfgAvoidEdges)
Construct a CFG with inlined functions.
size_t nCalls(const Function::Ptr &function=Function::Ptr()) const
Number of function calls.
static Ptr instance()
Factory class method.
Definition: CfgPath.h:349
size_t nReturns(const Function::Ptr &function=Function::Ptr()) const
Number of function returns.
CfgPath(const ControlFlowGraph::ConstVertexIterator &vertex)
Construct a path having only a starting vertex.
Definition: CfgPath.h:32
HowInline
What action to take for inlining.
Definition: CfgPath.h:329
size_t maxCallDepth(const Function::Ptr &function=Function::Ptr()) const
Maximum call depth.
size_t nVertices() const
Number of vertices in a path.
Definition: CfgPath.h:65
ssize_t callDepth(const Function::Ptr &function=Function::Ptr()) const
Call depth.
void findFunctionPaths(const ControlFlowGraph &srcCfg, ControlFlowGraph &paths, CfgVertexMap &vmap, const CfgConstVertexSet &beginVertices, const CfgConstVertexSet &endVertices, const CfgConstVertexSet &avoidVertices=CfgConstVertexSet(), const CfgConstEdgeSet &avoidEdges=CfgConstEdgeSet())
Compute all paths within one function.
ControlFlowGraph::ConstVertexIterator frontVertex() const
Returns the vertex where the path starts.
Definition: CfgPath.h:72
size_t nEdges() const
Number of edges in a path.
Definition: CfgPath.h:58
virtual HowInline operator()(const Partitioner &, const ControlFlowGraph::ConstEdgeIterator cfgCallEdge, const ControlFlowGraph &paths, const ControlFlowGraph::ConstVertexIterator &pathsCallSite, size_t callDepth)
Whether to inline a function.
std::set< ControlFlowGraph::ConstVertexIterator > CfgConstVertexSet
Set of CFG vertex pointers.
void findInterFunctionPaths(const ControlFlowGraph &srcCfg, ControlFlowGraph &paths, CfgVertexMap &vmap, const CfgConstVertexSet &beginVertices, const CfgConstVertexSet &endVertices, const CfgConstVertexSet &avoidVertices=CfgConstVertexSet(), const CfgConstEdgeSet &avoidEdges=CfgConstEdgeSet())
Compute all paths across function calls and returns.
std::vector< ControlFlowGraph::ConstEdgeIterator > Edges
Stack of inter-connected edges.
Definition: CfgPath.h:18
Holds a value or nothing.
Definition: Optional.h:49
Sawyer::Container::Graph< CfgVertex, CfgEdge > ControlFlowGraph
Control flow graph.
bool isConnected() const
Verify that path edges are connected.
size_t nVisits(const ControlFlowGraph::ConstVertexIterator &vertex) const
Number of times vertex appears in path.
const CfgConstVertexSet & pathsEndVertices() const
Paths end vertices.
Definition: CfgPath.h:424
void popBack()
Erase the final edge from a path.
Main namespace for the ROSE library.
Sawyer::Container::BiMap< ControlFlowGraph::ConstVertexIterator, ControlFlowGraph::ConstVertexIterator > CfgVertexMap
Map vertices from one CFG to another CFG and vice versa.
Bidirectional vertex node iterator.
Definition: Graph.h:1036
void clear()
Makes this path empty.
Definition: CfgPath.h:39
bool insertCalleePaths(ControlFlowGraph &paths, const ControlFlowGraph::ConstVertexIterator &pathsCallSite, const ControlFlowGraph &cfg, const ControlFlowGraph::ConstVertexIterator &cfgCallSite, const CfgConstVertexSet &cfgAvoidVertices=CfgConstVertexSet(), const CfgConstEdgeSet &cfgAvoidEdges=CfgConstEdgeSet(), std::vector< ControlFlowGraph::ConstVertexIterator > *newEdges=NULL)
Inline a function at the specified call site.
Predicate to determine whether inlining should be performed.
Definition: CfgPath.h:338
Do not inline anything for this call.
Definition: CfgPath.h:330
size_t maxCallDepth() const
Property: maximum call depth.
Definition: CfgPath.h:354
A path through a control flow graph.
Definition: CfgPath.h:15
std::set< ControlFlowGraph::ConstEdgeIterator > CfgConstEdgeSet
Set of CFG edge pointers.
ShouldInline::Ptr shouldInline() const
Property: inline predicate.
Definition: CfgPath.h:392
void shouldInline(const ShouldInline::Ptr &p)
Property: inline predicate.
Definition: CfgPath.h:393
void findPaths(const ControlFlowGraph &srcCfg, ControlFlowGraph &paths, CfgVertexMap &vmap, const CfgConstVertexSet &beginVertices, const CfgConstVertexSet &endVertices, const CfgConstVertexSet &avoidVertices=CfgConstVertexSet(), const CfgConstEdgeSet &avoidEdges=CfgConstEdgeSet(), bool avoidCallsAndReturns=false)
Compute all paths.
CfgConstEdgeSet findPathUnreachableEdges(const ControlFlowGraph &graph, const CfgConstVertexSet &beginVertices, const CfgConstVertexSet &endVertices, const CfgConstVertexSet &avoidVertices=CfgConstVertexSet(), const CfgConstEdgeSet &avoidEdges=CfgConstEdgeSet(), bool avoidCallsAndReturns=false)
Find edges that are unreachable.
const CfgConstVertexSet & pathsBeginVertices() const
Paths begin vertices.
Definition: CfgPath.h:418
void pushBack(const ControlFlowGraph::ConstEdgeIterator &edge)
Append a new edge to the end of the path.
Base class for reference counted objects.
Definition: SharedObject.h:22
ControlFlowGraph::ConstVertexIterator backVertex() const
Returns the vertex where the path ends.
Definition: CfgPath.h:80
Sawyer::SharedPointer< ShouldInline > Ptr
Shared ownership pointer to a predicate object.
Definition: CfgPath.h:346
std::vector< ControlFlowGraph::ConstEdgeIterator > truncate(const ControlFlowGraph::ConstEdgeIterator &)
Truncate the path.
CfgPath(const ControlFlowGraph::ConstEdgeIterator &edge)
Construct a path given an initial edge.
Definition: CfgPath.h:35
void pushFront(const ControlFlowGraph::ConstEdgeIterator &edge)
Append a new edge to the front of the path.
CfgPath()
Construct an empty path.
Definition: CfgPath.h:29
std::vector< ControlFlowGraph::ConstEdgeIterator > backtrack()
Backtrack to next path.
Add a V_USER_DEFINED vertex for this call.
Definition: CfgPath.h:332
Vertices vertices() const
Return all the vertices in a path.
std::vector< bool > findPathEdges(const ControlFlowGraph &graph, const CfgConstVertexSet &beginVertices, const CfgConstVertexSet &endVertices, const CfgConstVertexSet &avoidVertices=CfgConstVertexSet(), const CfgConstEdgeSet &avoidEdges=CfgConstEdgeSet(), bool avoidCallsAndReturns=false)
Finds edges that can be part of some path.
size_t eraseUnreachablePaths(ControlFlowGraph &graph, CfgConstVertexSet &beginVertices, CfgConstVertexSet &endVertices, CfgVertexMap &vmap, CfgPath &path)
Remove edges and vertices that cannot be on the paths.
void print(std::ostream &out) const
Print the path.
const ControlFlowGraph & paths() const
Resulting paths graph.
Definition: CfgPath.h:412
CfgConstEdgeSet findPathReachableEdges(const ControlFlowGraph &graph, const CfgConstVertexSet &beginVertices, const CfgConstVertexSet &endVertices, const CfgConstVertexSet &avoidVertices=CfgConstVertexSet(), const CfgConstEdgeSet &avoidEdges=CfgConstEdgeSet(), bool avoidCallsAndReturns=false)
Find edges that are reachable.
Represents no value.
Definition: Optional.h:32
Partitions instructions into basic blocks and functions.
Definition: Partitioner.h:290
bool isEmpty() const
Determine if a path is empty.
Definition: CfgPath.h:45
const Edges & edges() const
Returns all the edges in a path.
Definition: CfgPath.h:88
void maxCallDepth(size_t n)
Property: maximum call depth.
Definition: CfgPath.h:355