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