ROSE  0.9.11.30
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 
25 
26 private:
28  Edges edges_;
29 
30  // Optional edge ordering information. This vector parallels, "edges_", although it can be smaller if default ordering is
31  // used. Assuming the vectors are the same size, then edgeOrder_[i] contains the back-tracking information for
32  // edges_[i]. If edges_[i] is popped during backtracking and edgeOrder_[i] exists and is not empty, then edges_[i] will be
33  // replaced by edgeOrders_[i].back() and that edge is popped from edgeOrders_[i].
34  std::vector<Edges> edgeOrders_;
35 
36  // Attributes stored at each vertex and edge
37  std::vector<Attributes> vertexAttributes_;
38  std::vector<Attributes> edgeAttributes_;
39 
40 public:
42  CfgPath() {}
43 
45  explicit CfgPath(const ControlFlowGraph::ConstVertexIterator &vertex)
46  : frontVertex_(vertex), vertexAttributes_(1, Attributes()) {}
47 
50  : frontVertex_(edge->source()), edges_(1, edge), vertexAttributes_(2, Attributes()), edgeAttributes_(1, Attributes()) {}
51 
53  void clear() {
54  frontVertex_ = Sawyer::Nothing();
55  edges_.clear();
56  edgeOrders_.clear();
57  vertexAttributes_.clear();
58  edgeAttributes_.clear();
59  }
60 
62  bool isEmpty() const {
63  return !frontVertex_;
64  }
65 
70  bool isConnected() const;
71 
75  size_t nEdges() const {
76  return edges_.size();
77  }
78 
82  size_t nVertices() const {
83  return isEmpty() ? 0 : (1+nEdges());
84  }
85 
89  ControlFlowGraph::ConstVertexIterator frontVertex() const {
90  ASSERT_forbid(isEmpty());
91  return *frontVertex_;
92  }
93 
97  ControlFlowGraph::ConstVertexIterator backVertex() const {
98  ASSERT_forbid(isEmpty());
99  return edges_.empty() ? *frontVertex_ : edges_.back()->target();
100  }
101 
105  const Edges& edges() const {
106  return edges_;
107  }
108 
113  Vertices vertices() const;
114 
120  void pushBack(ControlFlowGraph::ConstEdgeIterator edge);
121 
127  void pushBack(const std::vector<ControlFlowGraph::ConstEdgeIterator> &edges);
128 
137  void pushFront(ControlFlowGraph::ConstEdgeIterator edge);
138 
144  void pushFront(const std::vector<ControlFlowGraph::ConstEdgeIterator> &edges);
145 
151  void popBack();
152 
161  std::vector<ControlFlowGraph::ConstEdgeIterator> backtrack();
162 
171  Attributes& vertexAttributes(size_t);
172  const Attributes& vertexAttributes(size_t) const;
183  Attributes& edgeAttributes(size_t);
184  const Attributes& edgeAttributes(size_t) const;
188  size_t nVisits(const ControlFlowGraph::ConstVertexIterator &vertex) const;
189 
191  size_t nVisits(const ControlFlowGraph::ConstEdgeIterator &edge) const;
192 
197  size_t nCalls(const Function::Ptr &function = Function::Ptr()) const;
198 
203  size_t nReturns(const Function::Ptr &function = Function::Ptr()) const;
204 
211  ssize_t callDepth(const Function::Ptr &function = Function::Ptr()) const;
212 
218  size_t maxCallDepth(const Function::Ptr &function = Function::Ptr()) const;
219 
228  std::vector<ControlFlowGraph::ConstEdgeIterator> truncate(const ControlFlowGraph::ConstEdgeIterator&);
229  std::vector<ControlFlowGraph::ConstEdgeIterator> truncate(const CfgConstEdgeSet&);
233  void print(std::ostream &out) const;
234 };
235 
237 // Functions for operating on paths
239 
246 std::vector<bool>
247 findPathEdges(const ControlFlowGraph &graph,
248  const CfgConstVertexSet &beginVertices, const CfgConstVertexSet &endVertices,
249  const CfgConstVertexSet &avoidVertices = CfgConstVertexSet(),
250  const CfgConstEdgeSet &avoidEdges = CfgConstEdgeSet(), bool avoidCallsAndReturns = false);
251 
258  const CfgConstVertexSet &beginVertices, const CfgConstVertexSet &endVertices,
259  const CfgConstVertexSet &avoidVertices = CfgConstVertexSet(),
260  const CfgConstEdgeSet &avoidEdges = CfgConstEdgeSet(),
261  bool avoidCallsAndReturns = false);
262 
269  const CfgConstVertexSet &beginVertices, const CfgConstVertexSet &endVertices,
270  const CfgConstVertexSet &avoidVertices = CfgConstVertexSet(),
271  const CfgConstEdgeSet &avoidEdges = CfgConstEdgeSet(),
272  bool avoidCallsAndReturns = false);
273 
281 size_t
282 eraseUnreachablePaths(ControlFlowGraph &graph /*in,out*/, CfgConstVertexSet &beginVertices /*in,out*/,
283  CfgConstVertexSet &endVertices /*in,out*/, CfgVertexMap &vmap /*in,out*/, CfgPath &path /*in,out*/);
284 
300 void
301 findPaths(const ControlFlowGraph &srcCfg, ControlFlowGraph &paths /*out*/, CfgVertexMap &vmap /*out*/,
302  const CfgConstVertexSet &beginVertices, const CfgConstVertexSet &endVertices,
303  const CfgConstVertexSet &avoidVertices = CfgConstVertexSet(),
304  const CfgConstEdgeSet &avoidEdges = CfgConstEdgeSet(),
305  bool avoidCallsAndReturns = false);
306 
310 void
311 findFunctionPaths(const ControlFlowGraph &srcCfg, ControlFlowGraph &paths /*out*/, CfgVertexMap &vmap /*out*/,
312  const CfgConstVertexSet &beginVertices, const CfgConstVertexSet &endVertices,
313  const CfgConstVertexSet &avoidVertices = CfgConstVertexSet(),
314  const CfgConstEdgeSet &avoidEdges = CfgConstEdgeSet());
315 
321 void
322 findInterFunctionPaths(const ControlFlowGraph &srcCfg, ControlFlowGraph &paths /*out*/, CfgVertexMap &vmap /*out*/,
323  const CfgConstVertexSet &beginVertices, const CfgConstVertexSet &endVertices,
324  const CfgConstVertexSet &avoidVertices = CfgConstVertexSet(),
325  const CfgConstEdgeSet &avoidEdges = CfgConstEdgeSet());
326 
356 bool
357 inlineMultipleCallees(ControlFlowGraph &paths /*in,out*/, const ControlFlowGraph::ConstVertexIterator &pathsCallSite,
358  const ControlFlowGraph &cfg, const ControlFlowGraph::ConstVertexIterator &cfgCallSite,
359  const CfgConstVertexSet &cfgAvoidVertices = CfgConstVertexSet(),
360  const CfgConstEdgeSet &cfgAvoidEdges = CfgConstEdgeSet(),
361  std::vector<ControlFlowGraph::ConstVertexIterator> *newEdges = NULL);
362 bool
363 inlineOneCallee(ControlFlowGraph &paths /*in,out*/, const ControlFlowGraph::ConstVertexIterator &pathsCallSite,
364  const ControlFlowGraph &cfg, const ControlFlowGraph::ConstVertexIterator &cfgCallTarget,
365  const CfgConstVertexSet &cfgAvoidVertices, const CfgConstEdgeSet &cfgAvoidEdges,
366  std::vector<ControlFlowGraph::ConstVertexIterator> *newVertices = NULL);
384 class Inliner {
385 public:
386 
388  enum HowInline {
392  };
393 
398  size_t maxCallDepth_; // max depth for inlining
399  protected:
400  ShouldInline(): maxCallDepth_(100) {}
401  public:
402  virtual ~ShouldInline() {}
403 
406 
408  static Ptr instance() { return Ptr(new ShouldInline); }
409 
413  size_t maxCallDepth() const { return maxCallDepth_; }
414  void maxCallDepth(size_t n) { maxCallDepth_ = n; }
418  virtual HowInline operator()(const Partitioner&, const ControlFlowGraph::ConstEdgeIterator cfgCallEdge,
419  const ControlFlowGraph &paths, const ControlFlowGraph::ConstVertexIterator &pathsCallSite,
420  size_t callDepth);
421  };
422 
423 private:
424  struct CallSite {
425  ControlFlowGraph::ConstVertexIterator pathsVertex;
426  size_t callDepth;
427  CallSite(const ControlFlowGraph::ConstVertexIterator &pathsVertex, size_t callDepth)
428  : pathsVertex(pathsVertex), callDepth(callDepth) {}
429  };
430 
431  ControlFlowGraph paths_; // the resulting paths graph
432  CfgVertexMap vmap_; // relates CFG vertices to paths graph vertices
433  CfgConstVertexSet pathsBeginVertices_; // vertices where traversal starts
434  CfgConstVertexSet pathsEndVertices_; // vertices where traversal ends
435  std::list<CallSite> workList_; // call sites to be processed
436  ShouldInline::Ptr shouldInline_; // user predicate for whether to inline a call
437 
438 public:
443  : shouldInline_(ShouldInline::instance()) {}
444 
451  ShouldInline::Ptr shouldInline() const { return shouldInline_; }
452  void shouldInline(const ShouldInline::Ptr &p) { shouldInline_ = p; }
464  void inlinePaths(const Partitioner &partitioner, const CfgConstVertexSet &cfgBeginVertices,
465  const CfgConstVertexSet &cfgEndVertices, const CfgConstVertexSet &cfgAvoidVertices,
466  const CfgConstEdgeSet &cfgAvoidEdges);
467 
471  const ControlFlowGraph& paths() const { return paths_; }
472 
477  const CfgConstVertexSet& pathsBeginVertices() const { return pathsBeginVertices_; }
478 
483  const CfgConstVertexSet& pathsEndVertices() const { return pathsEndVertices_; }
484 
485 private:
486  void reset(const Partitioner &partitioner, const CfgConstVertexSet &cfgBeginVertices,
487  const CfgConstVertexSet &cfgEndVertices, const CfgConstVertexSet &cfgAvoidVertices,
488  const CfgConstEdgeSet &cfgAvoidEdges);
489 
490  // Returns true if pathVertex is a function call. Does so by consulting the corresponding vertex in the partitioner's
491  // global CFG.
492  static bool isFunctionCall(const Partitioner&, const ControlFlowGraph::ConstVertexIterator &pathVertex);
493 
494  // Convert a path vertex to the corresponding vertex in the partitioner's global CFG.
495  static ControlFlowGraph::ConstVertexIterator pathToCfg(const Partitioner &partitioner,
496  const ControlFlowGraph::ConstVertexIterator &pathVertex);
497 
498  // Convert global CFG vertices to paths graph vertices. */
499  static CfgConstVertexSet cfgToPaths(const CfgConstVertexSet &vertices, const CfgVertexMap &vmap);
500 };
501 
502 std::ostream& operator<<(std::ostream &out, const CfgPath &path);
503 
504 } // namespace
505 } // namespace
506 } // namespace
507 
508 #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:408
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:45
HowInline
What action to take for inlining.
Definition: CfgPath.h:388
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:82
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:89
size_t nEdges() const
Number of edges in a path.
Definition: CfgPath.h:75
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.
bool inlineOneCallee(ControlFlowGraph &paths, const ControlFlowGraph::ConstVertexIterator &pathsCallSite, const ControlFlowGraph &cfg, const ControlFlowGraph::ConstVertexIterator &cfgCallTarget, const CfgConstVertexSet &cfgAvoidVertices, const CfgConstEdgeSet &cfgAvoidEdges, std::vector< ControlFlowGraph::ConstVertexIterator > *newVertices=NULL)
Inline a function at the specified call site.
const CfgConstVertexSet & pathsEndVertices() const
Paths end vertices.
Definition: CfgPath.h:483
void popBack()
Erase the final edge from a path.
Main namespace for the ROSE library.
Sawyer::Attribute::Storage< Sawyer::SingleThreadedTag > Attributes
Stores user-defined attributes.
Definition: CfgPath.h:24
Sawyer::Container::BiMap< ControlFlowGraph::ConstVertexIterator, ControlFlowGraph::ConstVertexIterator > CfgVertexMap
Map vertices from one CFG to another CFG and vice versa.
Reference-counting smart pointer.
Definition: SharedPointer.h:67
void clear()
Makes this path empty.
Definition: CfgPath.h:53
Predicate to determine whether inlining should be performed.
Definition: CfgPath.h:397
Do not inline anything for this call.
Definition: CfgPath.h:389
size_t maxCallDepth() const
Property: maximum call depth.
Definition: CfgPath.h:413
bool inlineMultipleCallees(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.
A path through a control flow graph.
Definition: CfgPath.h:15
std::set< ControlFlowGraph::ConstEdgeIterator > CfgConstEdgeSet
Set of CFG edge pointers.
Attributes & edgeAttributes(size_t)
User-defined attributes for the nth edge.
void pushBack(ControlFlowGraph::ConstEdgeIterator edge)
Append a new edge to the end of the path.
ShouldInline::Ptr shouldInline() const
Property: inline predicate.
Definition: CfgPath.h:451
void shouldInline(const ShouldInline::Ptr &p)
Property: inline predicate.
Definition: CfgPath.h:452
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:477
Attributes & vertexAttributes(size_t)
User-defined attributes for the nth vertex.
Base class for reference counted objects.
Definition: SharedObject.h:64
ControlFlowGraph::ConstVertexIterator backVertex() const
Returns the vertex where the path ends.
Definition: CfgPath.h:97
Sawyer::SharedPointer< ShouldInline > Ptr
Shared ownership pointer to a predicate object.
Definition: CfgPath.h:405
Bidirectional edge node iterator.
Definition: Graph.h:945
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:49
CfgPath()
Construct an empty path.
Definition: CfgPath.h:42
std::vector< ControlFlowGraph::ConstEdgeIterator > backtrack()
Backtrack to next path.
Add a V_USER_DEFINED vertex for this call.
Definition: CfgPath.h:391
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.
API and storage for attributes.
Definition: Attribute.h:208
void print(std::ostream &out) const
Print the path.
const ControlFlowGraph & paths() const
Resulting paths graph.
Definition: CfgPath.h:471
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:293
bool isEmpty() const
Determine if a path is empty.
Definition: CfgPath.h:62
void pushFront(ControlFlowGraph::ConstEdgeIterator edge)
Insert a new edge to the front of the path.
const Edges & edges() const
Returns all the edges in a path.
Definition: CfgPath.h:105
void maxCallDepth(size_t n)
Property: maximum call depth.
Definition: CfgPath.h:414