CfgPath.h

#ifndef ROSE_BinaryAnalysis_Partitioner2_CfgPath_H
#define ROSE_BinaryAnalysis_Partitioner2_CfgPath_H
#include <featureTests.h>
#ifdef ROSE_ENABLE_BINARY_ANALYSIS
 
#include <Rose/BinaryAnalysis/Partitioner2/ControlFlowGraph.h>
 
namespace Rose {
namespace BinaryAnalysis {
namespace Partitioner2 {
 
class CfgPath {
public:
    typedef std::vector<ControlFlowGraph::ConstEdgeIterator> Edges;
 
    typedef std::vector<ControlFlowGraph::ConstVertexIterator> Vertices;
 
    typedef Sawyer::Attribute::Storage<Sawyer::SingleThreadedTag> Attributes;
 
private:
    Sawyer::Optional<ControlFlowGraph::ConstVertexIterator> frontVertex_;
    Edges edges_;
 
    // Optional edge ordering information. This vector parallels, "edges_", although it can be smaller if default ordering is
    // used. Assuming the vectors are the same size, then edgeOrder_[i] contains the back-tracking information for
    // edges_[i]. If edges_[i] is popped during backtracking and edgeOrder_[i] exists and is not empty, then edges_[i] will be
    // replaced by edgeOrders_[i].back() and that edge is popped from edgeOrders_[i].
    std::vector<Edges> edgeOrders_;
 
    // Attributes stored at each vertex and edge
    std::vector<Attributes> vertexAttributes_;
    std::vector<Attributes> edgeAttributes_;
 
public:
    CfgPath() {}
 
    explicit CfgPath(const ControlFlowGraph::ConstVertexIterator &vertex)
        : frontVertex_(vertex), vertexAttributes_(1, Attributes()) {}
 
    explicit CfgPath(const ControlFlowGraph::ConstEdgeIterator &edge)
        : frontVertex_(edge->source()), edges_(1, edge), vertexAttributes_(2, Attributes()), edgeAttributes_(1, Attributes()) {}
 
    void clear() {
        frontVertex_ = Sawyer::Nothing();
        edges_.clear();
        edgeOrders_.clear();
        vertexAttributes_.clear();
        edgeAttributes_.clear();
    }
 
    bool isEmpty() const {
        return !frontVertex_;
    }
 
    bool isConnected() const;
 
    size_t nEdges() const {
        return edges_.size();
    }
 
    size_t nVertices() const {
        return isEmpty() ? 0 : (1+nEdges());
    }
 
    ControlFlowGraph::ConstVertexIterator frontVertex() const {
        ASSERT_forbid(isEmpty());
        return *frontVertex_;
    }
 
    ControlFlowGraph::ConstVertexIterator backVertex() const {
        ASSERT_forbid(isEmpty());
        return edges_.empty() ? *frontVertex_ : edges_.back()->target();
    }
 
    const Edges& edges() const {
        return edges_;
    }
 
    Vertices vertices() const;
 
    void pushBack(ControlFlowGraph::ConstEdgeIterator edge);
 
    void pushBack(const std::vector<ControlFlowGraph::ConstEdgeIterator> &edges);
 
    void pushFront(ControlFlowGraph::ConstEdgeIterator edge);
 
    void pushFront(const std::vector<ControlFlowGraph::ConstEdgeIterator> &edges);
 
    void popBack();
 
    std::vector<ControlFlowGraph::ConstEdgeIterator>  backtrack();
 
    Attributes& vertexAttributes(size_t);
    const Attributes& vertexAttributes(size_t) const;
    Attributes& edgeAttributes(size_t);
    const Attributes& edgeAttributes(size_t) const;
    size_t nVisits(const ControlFlowGraph::ConstVertexIterator &vertex) const;
 
    size_t nVisits(const ControlFlowGraph::ConstEdgeIterator &edge) const;
 
    size_t nCalls(const FunctionPtr&) const;
    size_t nCalls() const;
    size_t nReturns(const FunctionPtr&) const;
    size_t nReturns() const;
    ssize_t callDepth(const FunctionPtr&) const;
    ssize_t callDepth() const;
    size_t maxCallDepth(const FunctionPtr&) const;
    size_t maxCallDepth() const;
    std::vector<ControlFlowGraph::ConstEdgeIterator> truncate(const ControlFlowGraph::ConstEdgeIterator&);
    std::vector<ControlFlowGraph::ConstEdgeIterator> truncate(const CfgConstEdgeSet&);
    std::pair<size_t /*vertex*/, size_t /*insn*/> lastInsnIndex(SgAsmInstruction*) const;
 
    uint64_t hash() const;
 
    uint64_t hash(SgAsmInstruction*) const;
 
    void print(std::ostream &out) const;
};
 
//                                      Functions for operating on paths
 
std::vector<bool>
findPathEdges(const ControlFlowGraph &graph,
              const CfgConstVertexSet &beginVertices,
              const CfgConstVertexSet &avoidVertices = CfgConstVertexSet(),
              const CfgConstEdgeSet &avoidEdges = CfgConstEdgeSet(), bool avoidCallsAndReturns = false);
std::vector<bool>
findPathEdges(const ControlFlowGraph &graph,
              const CfgConstVertexSet &beginVertices, const CfgConstVertexSet &endVertices,
              const CfgConstVertexSet &avoidVertices = CfgConstVertexSet(),
              const CfgConstEdgeSet &avoidEdges = CfgConstEdgeSet(), bool avoidCallsAndReturns = false);
CfgConstEdgeSet
findPathReachableEdges(const ControlFlowGraph &graph,
                       const CfgConstVertexSet &beginVertices, const CfgConstVertexSet &endVertices,
                       const CfgConstVertexSet &avoidVertices = CfgConstVertexSet(),
                       const CfgConstEdgeSet &avoidEdges = CfgConstEdgeSet(),
                       bool avoidCallsAndReturns = false);
 
CfgConstEdgeSet
findPathUnreachableEdges(const ControlFlowGraph &graph,
                         const CfgConstVertexSet &beginVertices, const CfgConstVertexSet &endVertices,
                         const CfgConstVertexSet &avoidVertices = CfgConstVertexSet(),
                         const CfgConstEdgeSet &avoidEdges = CfgConstEdgeSet(),
                         bool avoidCallsAndReturns = false);
 
size_t
eraseUnreachablePaths(ControlFlowGraph &graph /*in,out*/, CfgConstVertexSet &beginVertices /*in,out*/,
                      CfgConstVertexSet &endVertices /*in,out*/, CfgVertexMap &vmap /*in,out*/, CfgPath &path /*in,out*/);
 
void
findPaths(const ControlFlowGraph &srcCfg, ControlFlowGraph &paths /*out*/, CfgVertexMap &vmap /*out*/,
          const CfgConstVertexSet &beginVertices, const CfgConstVertexSet &endVertices,
          const CfgConstVertexSet &avoidVertices = CfgConstVertexSet(),
          const CfgConstEdgeSet &avoidEdges = CfgConstEdgeSet(),
          bool avoidCallsAndReturns = false);
 
void
findPaths(const ControlFlowGraph &srcCfg, ControlFlowGraph &paths /*out*/, CfgVertexMap &vmap /*out*/,
          const CfgConstVertexSet &beginVertices,
          const CfgConstVertexSet &avoidVertices = CfgConstVertexSet(),
          const CfgConstEdgeSet &avoidEdges = CfgConstEdgeSet(),
          bool avoidCallsAndReturns = false);
 
void
findFunctionPaths(const ControlFlowGraph &srcCfg, ControlFlowGraph &paths /*out*/, CfgVertexMap &vmap /*out*/,
                  const CfgConstVertexSet &beginVertices,
                  const CfgConstVertexSet &avoidVertices = CfgConstVertexSet(),
                  const CfgConstEdgeSet &avoidEdges = CfgConstEdgeSet());
void
findFunctionPaths(const ControlFlowGraph &srcCfg, ControlFlowGraph &paths /*out*/, CfgVertexMap &vmap /*out*/,
                  const CfgConstVertexSet &beginVertices, const CfgConstVertexSet &endVertices,
                  const CfgConstVertexSet &avoidVertices = CfgConstVertexSet(),
                  const CfgConstEdgeSet &avoidEdges = CfgConstEdgeSet());
void
findInterFunctionPaths(const ControlFlowGraph &srcCfg, ControlFlowGraph &paths /*out*/, CfgVertexMap &vmap /*out*/,
                       const CfgConstVertexSet &beginVertices,
                       const CfgConstVertexSet &avoidVertices = CfgConstVertexSet(),
                       const CfgConstEdgeSet &avoidEdges = CfgConstEdgeSet());
void
findInterFunctionPaths(const ControlFlowGraph &srcCfg, ControlFlowGraph &paths /*out*/, CfgVertexMap &vmap /*out*/,
                       const CfgConstVertexSet &beginVertices, const CfgConstVertexSet &endVertices,
                       const CfgConstVertexSet &avoidVertices = CfgConstVertexSet(),
                       const CfgConstEdgeSet &avoidEdges = CfgConstEdgeSet());
bool
inlineMultipleCallees(ControlFlowGraph &paths /*in,out*/, 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);
bool
inlineOneCallee(ControlFlowGraph &paths /*in,out*/, const ControlFlowGraph::ConstVertexIterator &pathsCallSite,
                const ControlFlowGraph &cfg, const ControlFlowGraph::ConstVertexIterator &cfgCallTarget,
                const CfgConstVertexSet &cfgAvoidVertices, const CfgConstEdgeSet &cfgAvoidEdges,
                std::vector<ControlFlowGraph::ConstVertexIterator> *newVertices = nullptr);
class Inliner {
public:
 
    enum HowInline {
        INLINE_NONE,                                    
        INLINE_NORMAL,                                  
        INLINE_USER,                                    
    };
 
    class ShouldInline: public Sawyer::SharedObject {
        size_t maxCallDepth_;                           // max depth for inlining
    protected:
        ShouldInline(): maxCallDepth_(100) {}
    public:
        virtual ~ShouldInline() {}
 
        typedef Sawyer::SharedPointer<ShouldInline> Ptr;
 
        static Ptr instance() { return Ptr(new ShouldInline); }
 
        size_t maxCallDepth() const { return maxCallDepth_; }
        void maxCallDepth(size_t n) { maxCallDepth_ = n; }
        virtual HowInline operator()(const PartitionerConstPtr&, const ControlFlowGraph::ConstEdgeIterator cfgCallEdge,
                                     const ControlFlowGraph &paths, const ControlFlowGraph::ConstVertexIterator &pathsCallSite,
                                     size_t callDepth);
    };
 
private:
    struct CallSite {
        ControlFlowGraph::ConstVertexIterator pathsVertex;
        size_t callDepth;
        CallSite(const ControlFlowGraph::ConstVertexIterator &pathsVertex, size_t callDepth)
            : pathsVertex(pathsVertex), callDepth(callDepth) {}
    };
 
    ControlFlowGraph paths_;                            // the resulting paths graph
    CfgVertexMap vmap_;                                 // relates CFG vertices to paths graph vertices
    CfgConstVertexSet pathsBeginVertices_;              // vertices where traversal starts
    CfgConstVertexSet pathsEndVertices_;                // vertices where traversal ends
    std::list<CallSite> workList_;                      // call sites to be processed
    ShouldInline::Ptr shouldInline_;                    // user predicate for whether to inline a call
 
public:
    Inliner()
        : shouldInline_(ShouldInline::instance()) {}
 
    ShouldInline::Ptr shouldInline() const { return shouldInline_; }
    void shouldInline(const ShouldInline::Ptr &p) { shouldInline_ = p; }
    void inlinePaths(const PartitionerConstPtr &partitioner, const CfgConstVertexSet &cfgBeginVertices,
                     const CfgConstVertexSet &cfgEndVertices, const CfgConstVertexSet &cfgAvoidVertices,
                     const CfgConstEdgeSet &cfgAvoidEdges);
 
    const ControlFlowGraph& paths() const { return paths_; }
 
    const CfgConstVertexSet& pathsBeginVertices() const { return pathsBeginVertices_; }
 
    const CfgConstVertexSet& pathsEndVertices() const { return pathsEndVertices_; }
 
private:
    void reset(const PartitionerConstPtr &partitioner, const CfgConstVertexSet &cfgBeginVertices,
               const CfgConstVertexSet &cfgEndVertices, const CfgConstVertexSet &cfgAvoidVertices,
               const CfgConstEdgeSet &cfgAvoidEdges);
 
    // Returns true if pathVertex is a function call. Does so by consulting the corresponding vertex in the partitioner's
    // global CFG.
    static bool isFunctionCall(const PartitionerConstPtr&, const ControlFlowGraph::ConstVertexIterator &pathVertex);
 
    // Convert a path vertex to the corresponding vertex in the partitioner's global CFG.
    static ControlFlowGraph::ConstVertexIterator pathToCfg(const PartitionerConstPtr &partitioner,
                                                           const ControlFlowGraph::ConstVertexIterator &pathVertex);
 
    // Convert global CFG vertices to paths graph vertices. */
    static CfgConstVertexSet cfgToPaths(const CfgConstVertexSet &vertices, const CfgVertexMap &vmap);
};
 
std::ostream& operator<<(std::ostream &out, const CfgPath &path);
 
} // namespace
} // namespace
} // namespace
 
#endif
#endif