ROSE  0.11.59.0
CfgPath.h
1 #ifndef ROSE_BinaryAnalysis_Partitioner2_CfgPath_H
2 #define ROSE_BinaryAnalysis_Partitioner2_CfgPath_H
3 #include <featureTests.h>
4 #ifdef ROSE_ENABLE_BINARY_ANALYSIS
5 
6 #include <Rose/BinaryAnalysis/Partitioner2/ControlFlowGraph.h>
7 
8 namespace Rose {
9 namespace BinaryAnalysis {
10 namespace Partitioner2 {
11 
17 class CfgPath {
18 public:
20  typedef std::vector<ControlFlowGraph::ConstEdgeIterator> Edges;
21 
23  typedef std::vector<ControlFlowGraph::ConstVertexIterator> Vertices;
24 
27 
28 private:
30  Edges edges_;
31 
32  // Optional edge ordering information. This vector parallels, "edges_", although it can be smaller if default ordering is
33  // used. Assuming the vectors are the same size, then edgeOrder_[i] contains the back-tracking information for
34  // edges_[i]. If edges_[i] is popped during backtracking and edgeOrder_[i] exists and is not empty, then edges_[i] will be
35  // replaced by edgeOrders_[i].back() and that edge is popped from edgeOrders_[i].
36  std::vector<Edges> edgeOrders_;
37 
38  // Attributes stored at each vertex and edge
39  std::vector<Attributes> vertexAttributes_;
40  std::vector<Attributes> edgeAttributes_;
41 
42 public:
44  CfgPath() {}
45 
47  explicit CfgPath(const ControlFlowGraph::ConstVertexIterator &vertex)
48  : frontVertex_(vertex), vertexAttributes_(1, Attributes()) {}
49 
52  : frontVertex_(edge->source()), edges_(1, edge), vertexAttributes_(2, Attributes()), edgeAttributes_(1, Attributes()) {}
53 
55  void clear() {
56  frontVertex_ = Sawyer::Nothing();
57  edges_.clear();
58  edgeOrders_.clear();
59  vertexAttributes_.clear();
60  edgeAttributes_.clear();
61  }
62 
64  bool isEmpty() const {
65  return !frontVertex_;
66  }
67 
72  bool isConnected() const;
73 
77  size_t nEdges() const {
78  return edges_.size();
79  }
80 
84  size_t nVertices() const {
85  return isEmpty() ? 0 : (1+nEdges());
86  }
87 
91  ControlFlowGraph::ConstVertexIterator frontVertex() const {
92  ASSERT_forbid(isEmpty());
93  return *frontVertex_;
94  }
95 
99  ControlFlowGraph::ConstVertexIterator backVertex() const {
100  ASSERT_forbid(isEmpty());
101  return edges_.empty() ? *frontVertex_ : edges_.back()->target();
102  }
103 
107  const Edges& edges() const {
108  return edges_;
109  }
110 
115  Vertices vertices() const;
116 
122  void pushBack(ControlFlowGraph::ConstEdgeIterator edge);
123 
129  void pushBack(const std::vector<ControlFlowGraph::ConstEdgeIterator> &edges);
130 
139  void pushFront(ControlFlowGraph::ConstEdgeIterator edge);
140 
146  void pushFront(const std::vector<ControlFlowGraph::ConstEdgeIterator> &edges);
147 
153  void popBack();
154 
163  std::vector<ControlFlowGraph::ConstEdgeIterator> backtrack();
164 
173  Attributes& vertexAttributes(size_t);
174  const Attributes& vertexAttributes(size_t) const;
185  Attributes& edgeAttributes(size_t);
186  const Attributes& edgeAttributes(size_t) const;
190  size_t nVisits(const ControlFlowGraph::ConstVertexIterator &vertex) const;
191 
193  size_t nVisits(const ControlFlowGraph::ConstEdgeIterator &edge) const;
194 
199  size_t nCalls(const Function::Ptr &function = Function::Ptr()) const;
200 
205  size_t nReturns(const Function::Ptr &function = Function::Ptr()) const;
206 
213  ssize_t callDepth(const Function::Ptr &function = Function::Ptr()) const;
214 
220  size_t maxCallDepth(const Function::Ptr &function = Function::Ptr()) const;
221 
230  std::vector<ControlFlowGraph::ConstEdgeIterator> truncate(const ControlFlowGraph::ConstEdgeIterator&);
231  std::vector<ControlFlowGraph::ConstEdgeIterator> truncate(const CfgConstEdgeSet&);
240  std::pair<size_t /*vertex*/, size_t /*insn*/> lastInsnIndex(SgAsmInstruction*) const;
241 
246  uint64_t hash() const;
247 
253  uint64_t hash(SgAsmInstruction*) const;
254 
256  void print(std::ostream &out) const;
257 };
258 
260 // Functions for operating on paths
262 
271 std::vector<bool>
272 findPathEdges(const ControlFlowGraph &graph,
273  const CfgConstVertexSet &beginVertices,
274  const CfgConstVertexSet &avoidVertices = CfgConstVertexSet(),
275  const CfgConstEdgeSet &avoidEdges = CfgConstEdgeSet(), bool avoidCallsAndReturns = false);
276 std::vector<bool>
277 findPathEdges(const ControlFlowGraph &graph,
278  const CfgConstVertexSet &beginVertices, const CfgConstVertexSet &endVertices,
279  const CfgConstVertexSet &avoidVertices = CfgConstVertexSet(),
280  const CfgConstEdgeSet &avoidEdges = CfgConstEdgeSet(), bool avoidCallsAndReturns = false);
289  const CfgConstVertexSet &beginVertices, const CfgConstVertexSet &endVertices,
290  const CfgConstVertexSet &avoidVertices = CfgConstVertexSet(),
291  const CfgConstEdgeSet &avoidEdges = CfgConstEdgeSet(),
292  bool avoidCallsAndReturns = false);
293 
300  const CfgConstVertexSet &beginVertices, const CfgConstVertexSet &endVertices,
301  const CfgConstVertexSet &avoidVertices = CfgConstVertexSet(),
302  const CfgConstEdgeSet &avoidEdges = CfgConstEdgeSet(),
303  bool avoidCallsAndReturns = false);
304 
312 size_t
313 eraseUnreachablePaths(ControlFlowGraph &graph /*in,out*/, CfgConstVertexSet &beginVertices /*in,out*/,
314  CfgConstVertexSet &endVertices /*in,out*/, CfgVertexMap &vmap /*in,out*/, CfgPath &path /*in,out*/);
315 
331 void
332 findPaths(const ControlFlowGraph &srcCfg, ControlFlowGraph &paths /*out*/, CfgVertexMap &vmap /*out*/,
333  const CfgConstVertexSet &beginVertices, const CfgConstVertexSet &endVertices,
334  const CfgConstVertexSet &avoidVertices = CfgConstVertexSet(),
335  const CfgConstEdgeSet &avoidEdges = CfgConstEdgeSet(),
336  bool avoidCallsAndReturns = false);
337 
352 void
353 findPaths(const ControlFlowGraph &srcCfg, ControlFlowGraph &paths /*out*/, CfgVertexMap &vmap /*out*/,
354  const CfgConstVertexSet &beginVertices,
355  const CfgConstVertexSet &avoidVertices = CfgConstVertexSet(),
356  const CfgConstEdgeSet &avoidEdges = CfgConstEdgeSet(),
357  bool avoidCallsAndReturns = false);
358 
364 void
365 findFunctionPaths(const ControlFlowGraph &srcCfg, ControlFlowGraph &paths /*out*/, CfgVertexMap &vmap /*out*/,
366  const CfgConstVertexSet &beginVertices,
367  const CfgConstVertexSet &avoidVertices = CfgConstVertexSet(),
368  const CfgConstEdgeSet &avoidEdges = CfgConstEdgeSet());
369 void
370 findFunctionPaths(const ControlFlowGraph &srcCfg, ControlFlowGraph &paths /*out*/, CfgVertexMap &vmap /*out*/,
371  const CfgConstVertexSet &beginVertices, const CfgConstVertexSet &endVertices,
372  const CfgConstVertexSet &avoidVertices = CfgConstVertexSet(),
373  const CfgConstEdgeSet &avoidEdges = CfgConstEdgeSet());
383 void
384 findInterFunctionPaths(const ControlFlowGraph &srcCfg, ControlFlowGraph &paths /*out*/, CfgVertexMap &vmap /*out*/,
385  const CfgConstVertexSet &beginVertices,
386  const CfgConstVertexSet &avoidVertices = CfgConstVertexSet(),
387  const CfgConstEdgeSet &avoidEdges = CfgConstEdgeSet());
388 void
389 findInterFunctionPaths(const ControlFlowGraph &srcCfg, ControlFlowGraph &paths /*out*/, CfgVertexMap &vmap /*out*/,
390  const CfgConstVertexSet &beginVertices, const CfgConstVertexSet &endVertices,
391  const CfgConstVertexSet &avoidVertices = CfgConstVertexSet(),
392  const CfgConstEdgeSet &avoidEdges = CfgConstEdgeSet());
424 bool
425 inlineMultipleCallees(ControlFlowGraph &paths /*in,out*/, const ControlFlowGraph::ConstVertexIterator &pathsCallSite,
426  const ControlFlowGraph &cfg, const ControlFlowGraph::ConstVertexIterator &cfgCallSite,
427  const CfgConstVertexSet &cfgAvoidVertices = CfgConstVertexSet(),
428  const CfgConstEdgeSet &cfgAvoidEdges = CfgConstEdgeSet(),
429  std::vector<ControlFlowGraph::ConstVertexIterator> *newEdges = NULL);
430 bool
431 inlineOneCallee(ControlFlowGraph &paths /*in,out*/, const ControlFlowGraph::ConstVertexIterator &pathsCallSite,
432  const ControlFlowGraph &cfg, const ControlFlowGraph::ConstVertexIterator &cfgCallTarget,
433  const CfgConstVertexSet &cfgAvoidVertices, const CfgConstEdgeSet &cfgAvoidEdges,
434  std::vector<ControlFlowGraph::ConstVertexIterator> *newVertices = NULL);
452 class Inliner {
453 public:
454 
456  enum HowInline {
460  };
461 
466  size_t maxCallDepth_; // max depth for inlining
467  protected:
468  ShouldInline(): maxCallDepth_(100) {}
469  public:
470  virtual ~ShouldInline() {}
471 
474 
476  static Ptr instance() { return Ptr(new ShouldInline); }
477 
481  size_t maxCallDepth() const { return maxCallDepth_; }
482  void maxCallDepth(size_t n) { maxCallDepth_ = n; }
486  virtual HowInline operator()(const Partitioner&, const ControlFlowGraph::ConstEdgeIterator cfgCallEdge,
487  const ControlFlowGraph &paths, const ControlFlowGraph::ConstVertexIterator &pathsCallSite,
488  size_t callDepth);
489  };
490 
491 private:
492  struct CallSite {
493  ControlFlowGraph::ConstVertexIterator pathsVertex;
494  size_t callDepth;
495  CallSite(const ControlFlowGraph::ConstVertexIterator &pathsVertex, size_t callDepth)
496  : pathsVertex(pathsVertex), callDepth(callDepth) {}
497  };
498 
499  ControlFlowGraph paths_; // the resulting paths graph
500  CfgVertexMap vmap_; // relates CFG vertices to paths graph vertices
501  CfgConstVertexSet pathsBeginVertices_; // vertices where traversal starts
502  CfgConstVertexSet pathsEndVertices_; // vertices where traversal ends
503  std::list<CallSite> workList_; // call sites to be processed
504  ShouldInline::Ptr shouldInline_; // user predicate for whether to inline a call
505 
506 public:
511  : shouldInline_(ShouldInline::instance()) {}
512 
519  ShouldInline::Ptr shouldInline() const { return shouldInline_; }
520  void shouldInline(const ShouldInline::Ptr &p) { shouldInline_ = p; }
532  void inlinePaths(const Partitioner &partitioner, const CfgConstVertexSet &cfgBeginVertices,
533  const CfgConstVertexSet &cfgEndVertices, const CfgConstVertexSet &cfgAvoidVertices,
534  const CfgConstEdgeSet &cfgAvoidEdges);
535 
539  const ControlFlowGraph& paths() const { return paths_; }
540 
545  const CfgConstVertexSet& pathsBeginVertices() const { return pathsBeginVertices_; }
546 
551  const CfgConstVertexSet& pathsEndVertices() const { return pathsEndVertices_; }
552 
553 private:
554  void reset(const Partitioner &partitioner, const CfgConstVertexSet &cfgBeginVertices,
555  const CfgConstVertexSet &cfgEndVertices, const CfgConstVertexSet &cfgAvoidVertices,
556  const CfgConstEdgeSet &cfgAvoidEdges);
557 
558  // Returns true if pathVertex is a function call. Does so by consulting the corresponding vertex in the partitioner's
559  // global CFG.
560  static bool isFunctionCall(const Partitioner&, const ControlFlowGraph::ConstVertexIterator &pathVertex);
561 
562  // Convert a path vertex to the corresponding vertex in the partitioner's global CFG.
563  static ControlFlowGraph::ConstVertexIterator pathToCfg(const Partitioner &partitioner,
564  const ControlFlowGraph::ConstVertexIterator &pathVertex);
565 
566  // Convert global CFG vertices to paths graph vertices. */
567  static CfgConstVertexSet cfgToPaths(const CfgConstVertexSet &vertices, const CfgVertexMap &vmap);
568 };
569 
570 std::ostream& operator<<(std::ostream &out, const CfgPath &path);
571 
572 } // namespace
573 } // namespace
574 } // namespace
575 
576 #endif
577 #endif
std::vector< ControlFlowGraph::ConstVertexIterator > Vertices
Stack of vertices.
Definition: CfgPath.h:23
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:476
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:47
HowInline
What action to take for inlining.
Definition: CfgPath.h:456
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:84
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:91
size_t nEdges() const
Number of edges in a path.
Definition: CfgPath.h:77
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:20
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:551
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:26
void clear()
Makes this path empty.
Definition: CfgPath.h:55
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:465
Do not inline anything for this call.
Definition: CfgPath.h:457
size_t maxCallDepth() const
Property: maximum call depth.
Definition: CfgPath.h:481
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:17
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:519
void shouldInline(const ShouldInline::Ptr &p)
Property: inline predicate.
Definition: CfgPath.h:520
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:545
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:99
Sawyer::SharedPointer< ShouldInline > Ptr
Shared ownership pointer to a predicate object.
Definition: CfgPath.h:473
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:51
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:44
std::vector< ControlFlowGraph::ConstEdgeIterator > backtrack()
Backtrack to next path.
Add a V_USER_DEFINED vertex for this call.
Definition: CfgPath.h:459
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:539
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:289
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:64
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:107
void maxCallDepth(size_t n)
Property: maximum call depth.
Definition: CfgPath.h:482