1 #ifndef ROSE_BinaryAnalysis_Partitioner2_CfgPath_H
2 #define ROSE_BinaryAnalysis_Partitioner2_CfgPath_H
3 #include <featureTests.h>
4 #ifdef ROSE_ENABLE_BINARY_ANALYSIS
6 #include <Rose/BinaryAnalysis/Partitioner2/ControlFlowGraph.h>
9 namespace BinaryAnalysis {
10 namespace Partitioner2 {
20 typedef std::vector<ControlFlowGraph::ConstEdgeIterator>
Edges;
23 typedef std::vector<ControlFlowGraph::ConstVertexIterator>
Vertices;
36 std::vector<Edges> edgeOrders_;
39 std::vector<Attributes> vertexAttributes_;
40 std::vector<Attributes> edgeAttributes_;
47 explicit CfgPath(
const ControlFlowGraph::ConstVertexIterator &vertex)
48 : frontVertex_(vertex), vertexAttributes_(1, Attributes()) {}
52 : frontVertex_(edge->source()), edges_(1, edge), vertexAttributes_(2, Attributes()), edgeAttributes_(1, Attributes()) {}
59 vertexAttributes_.clear();
60 edgeAttributes_.clear();
99 ControlFlowGraph::ConstVertexIterator
backVertex()
const {
101 return edges_.empty() ? *frontVertex_ : edges_.back()->target();
122 void pushBack(ControlFlowGraph::ConstEdgeIterator edge);
129 void pushBack(
const std::vector<ControlFlowGraph::ConstEdgeIterator> &
edges);
139 void pushFront(ControlFlowGraph::ConstEdgeIterator edge);
146 void pushFront(
const std::vector<ControlFlowGraph::ConstEdgeIterator> &
edges);
163 std::vector<ControlFlowGraph::ConstEdgeIterator>
backtrack();
190 size_t nVisits(
const ControlFlowGraph::ConstVertexIterator &vertex)
const;
193 size_t nVisits(
const ControlFlowGraph::ConstEdgeIterator &edge)
const;
246 std::vector<ControlFlowGraph::ConstEdgeIterator>
truncate(
const ControlFlowGraph::ConstEdgeIterator&);
262 uint64_t
hash()
const;
272 void print(std::ostream &out)
const;
308 bool avoidCallsAndReturns =
false);
319 bool avoidCallsAndReturns =
false);
352 bool avoidCallsAndReturns =
false);
373 bool avoidCallsAndReturns =
false);
442 const ControlFlowGraph &cfg,
const ControlFlowGraph::ConstVertexIterator &cfgCallSite,
445 std::vector<ControlFlowGraph::ConstVertexIterator> *newEdges =
nullptr);
448 const ControlFlowGraph &cfg,
const ControlFlowGraph::ConstVertexIterator &cfgCallTarget,
450 std::vector<ControlFlowGraph::ConstVertexIterator> *newVertices =
nullptr);
482 size_t maxCallDepth_;
503 const ControlFlowGraph &paths,
const ControlFlowGraph::ConstVertexIterator &pathsCallSite,
509 ControlFlowGraph::ConstVertexIterator pathsVertex;
511 CallSite(
const ControlFlowGraph::ConstVertexIterator &pathsVertex,
size_t callDepth)
512 : pathsVertex(pathsVertex), callDepth(callDepth) {}
519 std::list<CallSite> workList_;
575 static bool isFunctionCall(
const PartitionerConstPtr&,
const ControlFlowGraph::ConstVertexIterator &pathVertex);
578 static ControlFlowGraph::ConstVertexIterator pathToCfg(
const PartitionerConstPtr &partitioner,
579 const ControlFlowGraph::ConstVertexIterator &pathVertex);
585 std::ostream& operator<<(std::ostream &out,
const CfgPath &path);
std::vector< ControlFlowGraph::ConstVertexIterator > Vertices
Stack of vertices.
static Ptr instance()
Factory class method.
CfgPath(const ControlFlowGraph::ConstVertexIterator &vertex)
Construct a path having only a starting vertex.
HowInline
What action to take for inlining.
Inliner()
Default constructor.
size_t nVertices() const
Number of vertices in a path.
ControlFlowGraph::ConstVertexIterator frontVertex() const
Returns the vertex where the path starts.
size_t nEdges() const
Number of edges in a path.
Base class for machine instructions.
size_t maxCallDepth() const
Maximum call depth.
std::vector< ControlFlowGraph::ConstEdgeIterator > Edges
Stack of inter-connected edges.
Holds a value or nothing.
bool isConnected() const
Verify that path edges are connected.
size_t nVisits(const ControlFlowGraph::ConstVertexIterator &vertex) const
Number of times vertex appears in path.
Sawyer::Container::Graph< CfgVertex, CfgEdge > ControlFlowGraph
Control flow graph.
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=nullptr)
Inline a function at the specified call site.
const CfgConstVertexSet & pathsEndVertices() const
Paths end vertices.
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.
Normal inlining for this call.
void inlinePaths(const PartitionerConstPtr &partitioner, const CfgConstVertexSet &cfgBeginVertices, const CfgConstVertexSet &cfgEndVertices, const CfgConstVertexSet &cfgAvoidVertices, const CfgConstEdgeSet &cfgAvoidEdges)
Construct a CFG with inlined functions.
void clear()
Makes this path empty.
std::pair< size_t, size_t > lastInsnIndex(SgAsmInstruction *) const
Find indices of last vertex and instruction.
Predicate to determine whether inlining should be performed.
Do not inline anything for this call.
size_t maxCallDepth() const
Property: maximum call depth.
A path through a control flow graph.
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.
virtual HowInline operator()(const PartitionerConstPtr &, const ControlFlowGraph::ConstEdgeIterator cfgCallEdge, const ControlFlowGraph &paths, const ControlFlowGraph::ConstVertexIterator &pathsCallSite, size_t callDepth)
Whether to inline a function.
ShouldInline::Ptr shouldInline() const
Property: inline predicate.
void shouldInline(const ShouldInline::Ptr &p)
Property: inline predicate.
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.
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=nullptr)
Inline a function at the specified call site.
const CfgConstVertexSet & pathsBeginVertices() const
Paths begin vertices.
Attributes & vertexAttributes(size_t)
User-defined attributes for the nth vertex.
Base class for reference counted objects.
ControlFlowGraph::ConstVertexIterator backVertex() const
Returns the vertex where the path ends.
Sawyer::SharedPointer< ShouldInline > Ptr
Shared ownership pointer to a predicate object.
Bidirectional edge node iterator.
std::vector< ControlFlowGraph::ConstEdgeIterator > truncate(const ControlFlowGraph::ConstEdgeIterator &)
Truncate the path.
CfgPath(const ControlFlowGraph::ConstEdgeIterator &edge)
Construct a path given an initial edge.
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.
ssize_t callDepth() const
Call depth.
std::vector< ControlFlowGraph::ConstEdgeIterator > backtrack()
Backtrack to next path.
Add a V_USER_DEFINED vertex for this call.
Vertices vertices() const
Return all the vertices in a path.
size_t nCalls() const
Number of function calls.
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.
void print(std::ostream &out) const
Print the path.
const ControlFlowGraph & paths() const
Resulting paths graph.
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.
Sawyer::Container::GraphIteratorSet< ControlFlowGraph::ConstEdgeIterator > CfgConstEdgeSet
Set of CFG edge pointers.
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.
size_t nReturns() const
Number of function returns.
bool isEmpty() const
Determine if a path is empty.
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.
void maxCallDepth(size_t n)
Property: maximum call depth.