ROSE  0.11.2.0
CfgPath.h
1 #ifndef ROSE_Partitioner2_CfgPath_H
2 #define ROSE_Partitioner2_CfgPath_H
3 
4 #include <rosePublicConfig.h>
5 #ifdef ROSE_BUILD_BINARY_ANALYSIS_SUPPORT
6 
7 #include <Partitioner2/ControlFlowGraph.h>
8 
9 namespace Rose {
10 namespace BinaryAnalysis {
11 namespace Partitioner2 {
12 
18 class CfgPath {
19 public:
21  typedef std::vector<ControlFlowGraph::ConstEdgeIterator> Edges;
22 
24  typedef std::vector<ControlFlowGraph::ConstVertexIterator> Vertices;
25 
28 
29 private:
31  Edges edges_;
32 
33  // Optional edge ordering information. This vector parallels, "edges_", although it can be smaller if default ordering is
34  // used. Assuming the vectors are the same size, then edgeOrder_[i] contains the back-tracking information for
35  // edges_[i]. If edges_[i] is popped during backtracking and edgeOrder_[i] exists and is not empty, then edges_[i] will be
36  // replaced by edgeOrders_[i].back() and that edge is popped from edgeOrders_[i].
37  std::vector<Edges> edgeOrders_;
38 
39  // Attributes stored at each vertex and edge
40  std::vector<Attributes> vertexAttributes_;
41  std::vector<Attributes> edgeAttributes_;
42 
43 public:
45  CfgPath() {}
46 
48  explicit CfgPath(const ControlFlowGraph::ConstVertexIterator &vertex)
49  : frontVertex_(vertex), vertexAttributes_(1, Attributes()) {}
50 
53  : frontVertex_(edge->source()), edges_(1, edge), vertexAttributes_(2, Attributes()), edgeAttributes_(1, Attributes()) {}
54 
56  void clear() {
57  frontVertex_ = Sawyer::Nothing();
58  edges_.clear();
59  edgeOrders_.clear();
60  vertexAttributes_.clear();
61  edgeAttributes_.clear();
62  }
63 
65  bool isEmpty() const {
66  return !frontVertex_;
67  }
68 
73  bool isConnected() const;
74 
78  size_t nEdges() const {
79  return edges_.size();
80  }
81 
85  size_t nVertices() const {
86  return isEmpty() ? 0 : (1+nEdges());
87  }
88 
92  ControlFlowGraph::ConstVertexIterator frontVertex() const {
93  ASSERT_forbid(isEmpty());
94  return *frontVertex_;
95  }
96 
100  ControlFlowGraph::ConstVertexIterator backVertex() const {
101  ASSERT_forbid(isEmpty());
102  return edges_.empty() ? *frontVertex_ : edges_.back()->target();
103  }
104 
108  const Edges& edges() const {
109  return edges_;
110  }
111 
116  Vertices vertices() const;
117 
123  void pushBack(ControlFlowGraph::ConstEdgeIterator edge);
124 
130  void pushBack(const std::vector<ControlFlowGraph::ConstEdgeIterator> &edges);
131 
140  void pushFront(ControlFlowGraph::ConstEdgeIterator edge);
141 
147  void pushFront(const std::vector<ControlFlowGraph::ConstEdgeIterator> &edges);
148 
154  void popBack();
155 
164  std::vector<ControlFlowGraph::ConstEdgeIterator> backtrack();
165 
174  Attributes& vertexAttributes(size_t);
175  const Attributes& vertexAttributes(size_t) const;
186  Attributes& edgeAttributes(size_t);
187  const Attributes& edgeAttributes(size_t) const;
191  size_t nVisits(const ControlFlowGraph::ConstVertexIterator &vertex) const;
192 
194  size_t nVisits(const ControlFlowGraph::ConstEdgeIterator &edge) const;
195 
200  size_t nCalls(const Function::Ptr &function = Function::Ptr()) const;
201 
206  size_t nReturns(const Function::Ptr &function = Function::Ptr()) const;
207 
214  ssize_t callDepth(const Function::Ptr &function = Function::Ptr()) const;
215 
221  size_t maxCallDepth(const Function::Ptr &function = Function::Ptr()) const;
222 
231  std::vector<ControlFlowGraph::ConstEdgeIterator> truncate(const ControlFlowGraph::ConstEdgeIterator&);
232  std::vector<ControlFlowGraph::ConstEdgeIterator> truncate(const CfgConstEdgeSet&);
241  std::pair<size_t /*vertex*/, size_t /*insn*/> lastInsnIndex(SgAsmInstruction*) const;
242 
247  uint64_t hash() const;
248 
254  uint64_t hash(SgAsmInstruction*) const;
255 
257  void print(std::ostream &out) const;
258 };
259 
261 // Functions for operating on paths
263 
272 std::vector<bool>
273 findPathEdges(const ControlFlowGraph &graph,
274  const CfgConstVertexSet &beginVertices,
275  const CfgConstVertexSet &avoidVertices = CfgConstVertexSet(),
276  const CfgConstEdgeSet &avoidEdges = CfgConstEdgeSet(), bool avoidCallsAndReturns = false);
277 std::vector<bool>
278 findPathEdges(const ControlFlowGraph &graph,
279  const CfgConstVertexSet &beginVertices, const CfgConstVertexSet &endVertices,
280  const CfgConstVertexSet &avoidVertices = CfgConstVertexSet(),
281  const CfgConstEdgeSet &avoidEdges = CfgConstEdgeSet(), bool avoidCallsAndReturns = false);
290  const CfgConstVertexSet &beginVertices, const CfgConstVertexSet &endVertices,
291  const CfgConstVertexSet &avoidVertices = CfgConstVertexSet(),
292  const CfgConstEdgeSet &avoidEdges = CfgConstEdgeSet(),
293  bool avoidCallsAndReturns = false);
294 
301  const CfgConstVertexSet &beginVertices, const CfgConstVertexSet &endVertices,
302  const CfgConstVertexSet &avoidVertices = CfgConstVertexSet(),
303  const CfgConstEdgeSet &avoidEdges = CfgConstEdgeSet(),
304  bool avoidCallsAndReturns = false);
305 
313 size_t
314 eraseUnreachablePaths(ControlFlowGraph &graph /*in,out*/, CfgConstVertexSet &beginVertices /*in,out*/,
315  CfgConstVertexSet &endVertices /*in,out*/, CfgVertexMap &vmap /*in,out*/, CfgPath &path /*in,out*/);
316 
332 void
333 findPaths(const ControlFlowGraph &srcCfg, ControlFlowGraph &paths /*out*/, CfgVertexMap &vmap /*out*/,
334  const CfgConstVertexSet &beginVertices, const CfgConstVertexSet &endVertices,
335  const CfgConstVertexSet &avoidVertices = CfgConstVertexSet(),
336  const CfgConstEdgeSet &avoidEdges = CfgConstEdgeSet(),
337  bool avoidCallsAndReturns = false);
338 
353 void
354 findPaths(const ControlFlowGraph &srcCfg, ControlFlowGraph &paths /*out*/, CfgVertexMap &vmap /*out*/,
355  const CfgConstVertexSet &beginVertices,
356  const CfgConstVertexSet &avoidVertices = CfgConstVertexSet(),
357  const CfgConstEdgeSet &avoidEdges = CfgConstEdgeSet(),
358  bool avoidCallsAndReturns = false);
359 
365 void
366 findFunctionPaths(const ControlFlowGraph &srcCfg, ControlFlowGraph &paths /*out*/, CfgVertexMap &vmap /*out*/,
367  const CfgConstVertexSet &beginVertices,
368  const CfgConstVertexSet &avoidVertices = CfgConstVertexSet(),
369  const CfgConstEdgeSet &avoidEdges = CfgConstEdgeSet());
370 void
371 findFunctionPaths(const ControlFlowGraph &srcCfg, ControlFlowGraph &paths /*out*/, CfgVertexMap &vmap /*out*/,
372  const CfgConstVertexSet &beginVertices, const CfgConstVertexSet &endVertices,
373  const CfgConstVertexSet &avoidVertices = CfgConstVertexSet(),
374  const CfgConstEdgeSet &avoidEdges = CfgConstEdgeSet());
384 void
385 findInterFunctionPaths(const ControlFlowGraph &srcCfg, ControlFlowGraph &paths /*out*/, CfgVertexMap &vmap /*out*/,
386  const CfgConstVertexSet &beginVertices,
387  const CfgConstVertexSet &avoidVertices = CfgConstVertexSet(),
388  const CfgConstEdgeSet &avoidEdges = CfgConstEdgeSet());
389 void
390 findInterFunctionPaths(const ControlFlowGraph &srcCfg, ControlFlowGraph &paths /*out*/, CfgVertexMap &vmap /*out*/,
391  const CfgConstVertexSet &beginVertices, const CfgConstVertexSet &endVertices,
392  const CfgConstVertexSet &avoidVertices = CfgConstVertexSet(),
393  const CfgConstEdgeSet &avoidEdges = CfgConstEdgeSet());
425 bool
426 inlineMultipleCallees(ControlFlowGraph &paths /*in,out*/, const ControlFlowGraph::ConstVertexIterator &pathsCallSite,
427  const ControlFlowGraph &cfg, const ControlFlowGraph::ConstVertexIterator &cfgCallSite,
428  const CfgConstVertexSet &cfgAvoidVertices = CfgConstVertexSet(),
429  const CfgConstEdgeSet &cfgAvoidEdges = CfgConstEdgeSet(),
430  std::vector<ControlFlowGraph::ConstVertexIterator> *newEdges = NULL);
431 bool
432 inlineOneCallee(ControlFlowGraph &paths /*in,out*/, const ControlFlowGraph::ConstVertexIterator &pathsCallSite,
433  const ControlFlowGraph &cfg, const ControlFlowGraph::ConstVertexIterator &cfgCallTarget,
434  const CfgConstVertexSet &cfgAvoidVertices, const CfgConstEdgeSet &cfgAvoidEdges,
435  std::vector<ControlFlowGraph::ConstVertexIterator> *newVertices = NULL);
453 class Inliner {
454 public:
455 
457  enum HowInline {
461  };
462 
467  size_t maxCallDepth_; // max depth for inlining
468  protected:
469  ShouldInline(): maxCallDepth_(100) {}
470  public:
471  virtual ~ShouldInline() {}
472 
475 
477  static Ptr instance() { return Ptr(new ShouldInline); }
478 
482  size_t maxCallDepth() const { return maxCallDepth_; }
483  void maxCallDepth(size_t n) { maxCallDepth_ = n; }
487  virtual HowInline operator()(const Partitioner&, const ControlFlowGraph::ConstEdgeIterator cfgCallEdge,
488  const ControlFlowGraph &paths, const ControlFlowGraph::ConstVertexIterator &pathsCallSite,
489  size_t callDepth);
490  };
491 
492 private:
493  struct CallSite {
494  ControlFlowGraph::ConstVertexIterator pathsVertex;
495  size_t callDepth;
496  CallSite(const ControlFlowGraph::ConstVertexIterator &pathsVertex, size_t callDepth)
497  : pathsVertex(pathsVertex), callDepth(callDepth) {}
498  };
499 
500  ControlFlowGraph paths_; // the resulting paths graph
501  CfgVertexMap vmap_; // relates CFG vertices to paths graph vertices
502  CfgConstVertexSet pathsBeginVertices_; // vertices where traversal starts
503  CfgConstVertexSet pathsEndVertices_; // vertices where traversal ends
504  std::list<CallSite> workList_; // call sites to be processed
505  ShouldInline::Ptr shouldInline_; // user predicate for whether to inline a call
506 
507 public:
512  : shouldInline_(ShouldInline::instance()) {}
513 
520  ShouldInline::Ptr shouldInline() const { return shouldInline_; }
521  void shouldInline(const ShouldInline::Ptr &p) { shouldInline_ = p; }
533  void inlinePaths(const Partitioner &partitioner, const CfgConstVertexSet &cfgBeginVertices,
534  const CfgConstVertexSet &cfgEndVertices, const CfgConstVertexSet &cfgAvoidVertices,
535  const CfgConstEdgeSet &cfgAvoidEdges);
536 
540  const ControlFlowGraph& paths() const { return paths_; }
541 
546  const CfgConstVertexSet& pathsBeginVertices() const { return pathsBeginVertices_; }
547 
552  const CfgConstVertexSet& pathsEndVertices() const { return pathsEndVertices_; }
553 
554 private:
555  void reset(const Partitioner &partitioner, const CfgConstVertexSet &cfgBeginVertices,
556  const CfgConstVertexSet &cfgEndVertices, const CfgConstVertexSet &cfgAvoidVertices,
557  const CfgConstEdgeSet &cfgAvoidEdges);
558 
559  // Returns true if pathVertex is a function call. Does so by consulting the corresponding vertex in the partitioner's
560  // global CFG.
561  static bool isFunctionCall(const Partitioner&, const ControlFlowGraph::ConstVertexIterator &pathVertex);
562 
563  // Convert a path vertex to the corresponding vertex in the partitioner's global CFG.
564  static ControlFlowGraph::ConstVertexIterator pathToCfg(const Partitioner &partitioner,
565  const ControlFlowGraph::ConstVertexIterator &pathVertex);
566 
567  // Convert global CFG vertices to paths graph vertices. */
568  static CfgConstVertexSet cfgToPaths(const CfgConstVertexSet &vertices, const CfgVertexMap &vmap);
569 };
570 
571 std::ostream& operator<<(std::ostream &out, const CfgPath &path);
572 
573 } // namespace
574 } // namespace
575 } // namespace
576 
577 #endif
578 #endif
std::vector< ControlFlowGraph::ConstVertexIterator > Vertices
Stack of vertices.
Definition: CfgPath.h:24
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:477
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:48
HowInline
What action to take for inlining.
Definition: CfgPath.h:457
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:85
ssize_t callDepth(const Function::Ptr &function=Function::Ptr()) const
Call depth.
ControlFlowGraph::ConstVertexIterator frontVertex() const
Returns the vertex where the path starts.
Definition: CfgPath.h:92
size_t nEdges() const
Number of edges in a path.
Definition: CfgPath.h:78
Base class for machine instructions.
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::vector< ControlFlowGraph::ConstEdgeIterator > Edges
Stack of inter-connected edges.
Definition: CfgPath.h:21
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:552
void popBack()
Erase the final edge from a path.
Main namespace for the ROSE library.
Sawyer::Container::GraphIteratorSet< ControlFlowGraph::ConstVertexIterator > CfgConstVertexSet
Set of CFG vertex pointers.
uint64_t hash() const
Hash the path.
std::vector< bool > findPathEdges(const ControlFlowGraph &graph, const CfgConstVertexSet &beginVertices, const CfgConstVertexSet &avoidVertices=CfgConstVertexSet(), const CfgConstEdgeSet &avoidEdges=CfgConstEdgeSet(), bool avoidCallsAndReturns=false)
Finds edges that can be part of some path.
Sawyer::Attribute::Storage< Sawyer::SingleThreadedTag > Attributes
Stores user-defined attributes.
Definition: CfgPath.h:27
void clear()
Makes this path empty.
Definition: CfgPath.h:56
std::pair< size_t, size_t > lastInsnIndex(SgAsmInstruction *) const
Find indices of last vertex and instruction.
Predicate to determine whether inlining should be performed.
Definition: CfgPath.h:466
Do not inline anything for this call.
Definition: CfgPath.h:458
size_t maxCallDepth() const
Property: maximum call depth.
Definition: CfgPath.h:482
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:18
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:520
void shouldInline(const ShouldInline::Ptr &p)
Property: inline predicate.
Definition: CfgPath.h:521
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:546
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:100
Sawyer::SharedPointer< ShouldInline > Ptr
Shared ownership pointer to a predicate object.
Definition: CfgPath.h:474
Bidirectional edge node iterator.
Definition: Graph.h:925
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:52
Sawyer::Container::GraphIteratorBiMap< ControlFlowGraph::ConstVertexIterator, ControlFlowGraph::ConstVertexIterator > CfgVertexMap
Map vertices from one CFG to another CFG and vice versa.
void findInterFunctionPaths(const ControlFlowGraph &srcCfg, ControlFlowGraph &paths, CfgVertexMap &vmap, const CfgConstVertexSet &beginVertices, const CfgConstVertexSet &avoidVertices=CfgConstVertexSet(), const CfgConstEdgeSet &avoidEdges=CfgConstEdgeSet())
Compute all paths across function calls and returns.
CfgPath()
Construct an empty path.
Definition: CfgPath.h:45
std::vector< ControlFlowGraph::ConstEdgeIterator > backtrack()
Backtrack to next path.
Add a V_USER_DEFINED vertex for this call.
Definition: CfgPath.h:460
Vertices vertices() const
Return all the vertices in a 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:540
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
Sawyer::Container::GraphIteratorSet< ControlFlowGraph::ConstEdgeIterator > CfgConstEdgeSet
Set of CFG edge pointers.
Partitions instructions into basic blocks and functions.
Definition: Partitioner.h:322
void findFunctionPaths(const ControlFlowGraph &srcCfg, ControlFlowGraph &paths, CfgVertexMap &vmap, const CfgConstVertexSet &beginVertices, const CfgConstVertexSet &avoidVertices=CfgConstVertexSet(), const CfgConstEdgeSet &avoidEdges=CfgConstEdgeSet())
Compute all paths within one function.
bool isEmpty() const
Determine if a path is empty.
Definition: CfgPath.h:65
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:108
void maxCallDepth(size_t n)
Property: maximum call depth.
Definition: CfgPath.h:483