ROSE  0.9.10.135
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  // Attributes stored at each vertex and edge
31  std::vector<Attributes> vertexAttributes_;
32  std::vector<Attributes> edgeAttributes_;
33 
34 public:
36  CfgPath() {}
37 
39  explicit CfgPath(const ControlFlowGraph::ConstVertexIterator &vertex)
40  : frontVertex_(vertex), vertexAttributes_(1, Attributes()) {}
41 
43  explicit CfgPath(const ControlFlowGraph::ConstEdgeIterator &edge)
44  : frontVertex_(edge->source()), edges_(1, edge), vertexAttributes_(2, Attributes()), edgeAttributes_(1, Attributes()) {}
45 
47  void clear() {
48  frontVertex_ = Sawyer::Nothing();
49  edges_.clear();
50  vertexAttributes_.clear();
51  edgeAttributes_.clear();
52  }
53 
55  bool isEmpty() const {
56  return !frontVertex_;
57  }
58 
63  bool isConnected() const;
64 
68  size_t nEdges() const {
69  return edges_.size();
70  }
71 
75  size_t nVertices() const {
76  return isEmpty() ? 0 : (1+nEdges());
77  }
78 
82  ControlFlowGraph::ConstVertexIterator frontVertex() const {
83  ASSERT_forbid(isEmpty());
84  return *frontVertex_;
85  }
86 
90  ControlFlowGraph::ConstVertexIterator backVertex() const {
91  ASSERT_forbid(isEmpty());
92  return edges_.empty() ? *frontVertex_ : edges_.back()->target();
93  }
94 
98  const Edges& edges() const {
99  return edges_;
100  }
101 
106  Vertices vertices() const;
107 
111  void pushBack(const ControlFlowGraph::ConstEdgeIterator &edge);
112 
119  void pushFront(const ControlFlowGraph::ConstEdgeIterator &edge);
120 
126  void popBack();
127 
136  std::vector<ControlFlowGraph::ConstEdgeIterator> backtrack();
137 
146  Attributes& vertexAttributes(size_t);
147  const Attributes& vertexAttributes(size_t) const;
158  Attributes& edgeAttributes(size_t);
159  const Attributes& edgeAttributes(size_t) const;
163  size_t nVisits(const ControlFlowGraph::ConstVertexIterator &vertex) const;
164 
166  size_t nVisits(const ControlFlowGraph::ConstEdgeIterator &edge) const;
167 
172  size_t nCalls(const Function::Ptr &function = Function::Ptr()) const;
173 
178  size_t nReturns(const Function::Ptr &function = Function::Ptr()) const;
179 
186  ssize_t callDepth(const Function::Ptr &function = Function::Ptr()) const;
187 
193  size_t maxCallDepth(const Function::Ptr &function = Function::Ptr()) const;
194 
203  std::vector<ControlFlowGraph::ConstEdgeIterator> truncate(const ControlFlowGraph::ConstEdgeIterator&);
204  std::vector<ControlFlowGraph::ConstEdgeIterator> truncate(const CfgConstEdgeSet&);
208  void print(std::ostream &out) const;
209 };
210 
212 // Functions for operating on paths
214 
221 std::vector<bool>
222 findPathEdges(const ControlFlowGraph &graph,
223  const CfgConstVertexSet &beginVertices, const CfgConstVertexSet &endVertices,
224  const CfgConstVertexSet &avoidVertices = CfgConstVertexSet(),
225  const CfgConstEdgeSet &avoidEdges = CfgConstEdgeSet(), bool avoidCallsAndReturns = false);
226 
233  const CfgConstVertexSet &beginVertices, const CfgConstVertexSet &endVertices,
234  const CfgConstVertexSet &avoidVertices = CfgConstVertexSet(),
235  const CfgConstEdgeSet &avoidEdges = CfgConstEdgeSet(),
236  bool avoidCallsAndReturns = false);
237 
244  const CfgConstVertexSet &beginVertices, const CfgConstVertexSet &endVertices,
245  const CfgConstVertexSet &avoidVertices = CfgConstVertexSet(),
246  const CfgConstEdgeSet &avoidEdges = CfgConstEdgeSet(),
247  bool avoidCallsAndReturns = false);
248 
256 size_t
257 eraseUnreachablePaths(ControlFlowGraph &graph /*in,out*/, CfgConstVertexSet &beginVertices /*in,out*/,
258  CfgConstVertexSet &endVertices /*in,out*/, CfgVertexMap &vmap /*in,out*/, CfgPath &path /*in,out*/);
259 
275 void
276 findPaths(const ControlFlowGraph &srcCfg, ControlFlowGraph &paths /*out*/, CfgVertexMap &vmap /*out*/,
277  const CfgConstVertexSet &beginVertices, const CfgConstVertexSet &endVertices,
278  const CfgConstVertexSet &avoidVertices = CfgConstVertexSet(),
279  const CfgConstEdgeSet &avoidEdges = CfgConstEdgeSet(),
280  bool avoidCallsAndReturns = false);
281 
285 void
286 findFunctionPaths(const ControlFlowGraph &srcCfg, ControlFlowGraph &paths /*out*/, CfgVertexMap &vmap /*out*/,
287  const CfgConstVertexSet &beginVertices, const CfgConstVertexSet &endVertices,
288  const CfgConstVertexSet &avoidVertices = CfgConstVertexSet(),
289  const CfgConstEdgeSet &avoidEdges = CfgConstEdgeSet());
290 
296 void
297 findInterFunctionPaths(const ControlFlowGraph &srcCfg, ControlFlowGraph &paths /*out*/, CfgVertexMap &vmap /*out*/,
298  const CfgConstVertexSet &beginVertices, const CfgConstVertexSet &endVertices,
299  const CfgConstVertexSet &avoidVertices = CfgConstVertexSet(),
300  const CfgConstEdgeSet &avoidEdges = CfgConstEdgeSet());
301 
331 bool
332 inlineMultipleCallees(ControlFlowGraph &paths /*in,out*/, const ControlFlowGraph::ConstVertexIterator &pathsCallSite,
333  const ControlFlowGraph &cfg, const ControlFlowGraph::ConstVertexIterator &cfgCallSite,
334  const CfgConstVertexSet &cfgAvoidVertices = CfgConstVertexSet(),
335  const CfgConstEdgeSet &cfgAvoidEdges = CfgConstEdgeSet(),
336  std::vector<ControlFlowGraph::ConstVertexIterator> *newEdges = NULL);
337 bool
338 inlineOneCallee(ControlFlowGraph &paths /*in,out*/, const ControlFlowGraph::ConstVertexIterator &pathsCallSite,
339  const ControlFlowGraph &cfg, const ControlFlowGraph::ConstVertexIterator &cfgCallTarget,
340  const CfgConstVertexSet &cfgAvoidVertices, const CfgConstEdgeSet &cfgAvoidEdges,
341  std::vector<ControlFlowGraph::ConstVertexIterator> *newVertices = NULL);
359 class Inliner {
360 public:
361 
363  enum HowInline {
367  };
368 
373  size_t maxCallDepth_; // max depth for inlining
374  protected:
375  ShouldInline(): maxCallDepth_(100) {}
376  public:
377  virtual ~ShouldInline() {}
378 
381 
383  static Ptr instance() { return Ptr(new ShouldInline); }
384 
388  size_t maxCallDepth() const { return maxCallDepth_; }
389  void maxCallDepth(size_t n) { maxCallDepth_ = n; }
393  virtual HowInline operator()(const Partitioner&, const ControlFlowGraph::ConstEdgeIterator cfgCallEdge,
394  const ControlFlowGraph &paths, const ControlFlowGraph::ConstVertexIterator &pathsCallSite,
395  size_t callDepth);
396  };
397 
398 private:
399  struct CallSite {
400  ControlFlowGraph::ConstVertexIterator pathsVertex;
401  size_t callDepth;
402  CallSite(const ControlFlowGraph::ConstVertexIterator &pathsVertex, size_t callDepth)
403  : pathsVertex(pathsVertex), callDepth(callDepth) {}
404  };
405 
406  ControlFlowGraph paths_; // the resulting paths graph
407  CfgVertexMap vmap_; // relates CFG vertices to paths graph vertices
408  CfgConstVertexSet pathsBeginVertices_; // vertices where traversal starts
409  CfgConstVertexSet pathsEndVertices_; // vertices where traversal ends
410  std::list<CallSite> workList_; // call sites to be processed
411  ShouldInline::Ptr shouldInline_; // user predicate for whether to inline a call
412 
413 public:
418  : shouldInline_(ShouldInline::instance()) {}
419 
426  ShouldInline::Ptr shouldInline() const { return shouldInline_; }
427  void shouldInline(const ShouldInline::Ptr &p) { shouldInline_ = p; }
439  void inlinePaths(const Partitioner &partitioner, const CfgConstVertexSet &cfgBeginVertices,
440  const CfgConstVertexSet &cfgEndVertices, const CfgConstVertexSet &cfgAvoidVertices,
441  const CfgConstEdgeSet &cfgAvoidEdges);
442 
446  const ControlFlowGraph& paths() const { return paths_; }
447 
452  const CfgConstVertexSet& pathsBeginVertices() const { return pathsBeginVertices_; }
453 
458  const CfgConstVertexSet& pathsEndVertices() const { return pathsEndVertices_; }
459 
460 private:
461  void reset(const Partitioner &partitioner, const CfgConstVertexSet &cfgBeginVertices,
462  const CfgConstVertexSet &cfgEndVertices, const CfgConstVertexSet &cfgAvoidVertices,
463  const CfgConstEdgeSet &cfgAvoidEdges);
464 
465  // Returns true if pathVertex is a function call. Does so by consulting the corresponding vertex in the partitioner's
466  // global CFG.
467  static bool isFunctionCall(const Partitioner&, const ControlFlowGraph::ConstVertexIterator &pathVertex);
468 
469  // Convert a path vertex to the corresponding vertex in the partitioner's global CFG.
470  static ControlFlowGraph::ConstVertexIterator pathToCfg(const Partitioner &partitioner,
471  const ControlFlowGraph::ConstVertexIterator &pathVertex);
472 
473  // Convert global CFG vertices to paths graph vertices. */
474  static CfgConstVertexSet cfgToPaths(const CfgConstVertexSet &vertices, const CfgVertexMap &vmap);
475 };
476 
477 
478 
479 
480 std::ostream& operator<<(std::ostream &out, const CfgPath &path);
481 
482 } // namespace
483 } // namespace
484 } // namespace
485 
486 #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:383
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:39
HowInline
What action to take for inlining.
Definition: CfgPath.h:363
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:75
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:82
size_t nEdges() const
Number of edges in a path.
Definition: CfgPath.h:68
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:458
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:34
void clear()
Makes this path empty.
Definition: CfgPath.h:47
Predicate to determine whether inlining should be performed.
Definition: CfgPath.h:372
Do not inline anything for this call.
Definition: CfgPath.h:364
size_t maxCallDepth() const
Property: maximum call depth.
Definition: CfgPath.h:388
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.
ShouldInline::Ptr shouldInline() const
Property: inline predicate.
Definition: CfgPath.h:426
void shouldInline(const ShouldInline::Ptr &p)
Property: inline predicate.
Definition: CfgPath.h:427
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:452
Attributes & vertexAttributes(size_t)
User-defined attributes for the nth vertex.
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:90
Sawyer::SharedPointer< ShouldInline > Ptr
Shared ownership pointer to a predicate object.
Definition: CfgPath.h:380
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:43
void pushFront(const ControlFlowGraph::ConstEdgeIterator &edge)
Append a new edge to the front of the path.
CfgPath()
Construct an empty path.
Definition: CfgPath.h:36
std::vector< ControlFlowGraph::ConstEdgeIterator > backtrack()
Backtrack to next path.
Add a V_USER_DEFINED vertex for this call.
Definition: CfgPath.h:366
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:446
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:55
const Edges & edges() const
Returns all the edges in a path.
Definition: CfgPath.h:98
void maxCallDepth(size_t n)
Property: maximum call depth.
Definition: CfgPath.h:389