DataFlow.h

#ifndef ROSE_BinaryAnalysis_DataFlow_H
#define ROSE_BinaryAnalysis_DataFlow_H
#include <featureTests.h>
#ifdef ROSE_ENABLE_BINARY_ANALYSIS

#include <Rose/BinaryAnalysis/InstructionSemantics/DataFlowSemantics.h>
#include <Rose/Diagnostics.h>
#include <Rose/Exception.h>
#include <Rose/BinaryAnalysis/InstructionSemantics/SymbolicSemantics.h>

#include <boost/lexical_cast.hpp>
#include <list>
#include <Sawyer/GraphTraversal.h>
#include <Sawyer/DistinctList.h>
#include <sstream>
#include <string>
#include <vector>

namespace Rose {
namespace BinaryAnalysis {

class DataFlow {
public:
    typedef InstructionSemantics::DataFlowSemantics::DataFlowGraph Graph;

    typedef AbstractLocation Variable;

    typedef std::list<Variable> VariableList;

    typedef Sawyer::Container::Map<size_t, Graph> VertexFlowGraphs;

public:
    class Exception: public Rose::Exception {
    public:
        explicit Exception(const std::string &s): Rose::Exception(s) {}
    };

    class NotConverging: public Exception {
    public:
        explicit NotConverging(const std::string &s): Exception(s) {}
    };

private:
    InstructionSemantics::BaseSemantics::RiscOperatorsPtr userOps_;   // operators (and state) provided by the user
    InstructionSemantics::DataFlowSemantics::RiscOperatorsPtr dfOps_; // data-flow operators (which point to user ops)
    InstructionSemantics::BaseSemantics::DispatcherPtr dispatcher_;   // copy of user's dispatcher but with DataFlowSemantics

public:
    static Sawyer::Message::Facility mlog;                            // diagnostics for data-flow

public:
    DataFlow(const InstructionSemantics::BaseSemantics::DispatcherPtr &userDispatcher) {
        init(userDispatcher);
    }

    static void initDiagnostics();

private:
    void init(const InstructionSemantics::BaseSemantics::DispatcherPtr&);

public:
    Graph buildGraph(const std::vector<SgAsmInstruction*>&);
    class DefaultVertexUnpacker {
    public:
        typedef std::vector<SgAsmInstruction*> Instructions;
        Instructions operator()(SgAsmInstruction *insn) { return Instructions(1, insn); }
        Instructions operator()(SgAsmBlock *blk);
    };

public:
    template<class CFG, class VertexUnpacker>
    VertexFlowGraphs buildGraphPerVertex(const CFG &cfg, size_t startVertex, VertexUnpacker vertexUnpacker) {
        using namespace Diagnostics;
        ASSERT_this();
        ASSERT_require(startVertex < cfg.nVertices());
        Stream mesg(mlog[WHERE] <<"buildGraphPerVertex startVertex=" <<startVertex);

        VertexFlowGraphs result;
        result.insert(startVertex, buildGraph(vertexUnpacker(cfg.findVertex(startVertex)->value())));
        std::vector<InstructionSemantics::BaseSemantics::StatePtr> postState(cfg.nVertices()); // user-defined states
        postState[startVertex] = userOps_->currentState();

        typedef Sawyer::Container::Algorithm::DepthFirstForwardEdgeTraversal<const CFG> Traversal;
        for (Traversal t(cfg, cfg.findVertex(startVertex)); t; ++t) {
            typename CFG::ConstVertexIterator source = t->source();
            typename CFG::ConstVertexIterator target = t->target();
            InstructionSemantics::BaseSemantics::StatePtr state = postState[target->id()];
            if (state==NULL) {
                ASSERT_not_null(postState[source->id()]);
                state = postState[target->id()] = postState[source->id()]->clone();
                userOps_->currentState(state);
                std::vector<SgAsmInstruction*> insns = vertexUnpacker(target->value());
                result.insert(target->id(), buildGraph(insns));
            }
        }
        
        mesg <<"; processed " <<StringUtility::plural(result.size(), "vertices", "vertex") <<"\n";
        return result;
    }

    template<class CFG>
    VertexFlowGraphs buildGraphPerVertex(const CFG &cfg, size_t startVertex) {
        return buildGraphPerVertex(cfg, startVertex, DefaultVertexUnpacker());
    }
    VariableList getUniqueVariables(const VertexFlowGraphs&);

    class SemanticsMerge {
        InstructionSemantics::BaseSemantics::RiscOperatorsPtr ops_;
    public:
        explicit SemanticsMerge(const InstructionSemantics::BaseSemantics::RiscOperatorsPtr &ops): ops_(ops) {}
        explicit SemanticsMerge(const InstructionSemantics::BaseSemantics::DispatcherPtr &cpu): ops_(cpu->operators()) {}

        bool operator()(InstructionSemantics::BaseSemantics::StatePtr &dst /*in,out*/,
                        const InstructionSemantics::BaseSemantics::StatePtr &src) const {
            struct PreserveCurrentState {
                InstructionSemantics::BaseSemantics::RiscOperatorsPtr ops;
                InstructionSemantics::BaseSemantics::StatePtr state;
                PreserveCurrentState(const InstructionSemantics::BaseSemantics::RiscOperatorsPtr &ops)
                    : ops(ops), state(ops->currentState()) {}
                ~PreserveCurrentState() { ops->currentState(state); }
            } t(ops_);

            if (!dst) {
                dst = src->clone();
                return true;
            } else {
                ops_->currentState(src);
                return dst->merge(src, ops_.get());
            }
        }
    };

    template<class CFG, class State>
    class PathAlwaysFeasible {
    public:
        bool operator()(const CFG&, const typename CFG::Edge&, const State&, const State&) {
            return true;
        }
    };
    
    template<class CFG, class State, class TransferFunction, class MergeFunction,
             class PathFeasibility = PathAlwaysFeasible<CFG, State> >
    class Engine {
    public:
        typedef std::vector<State> VertexStates;        
    private:
        std::string name_;                              // optional name for debugging
        const CFG &cfg_;
        TransferFunction &xfer_;
        MergeFunction merge_;
        VertexStates incomingState_;                    // incoming data-flow state per CFG vertex ID
        VertexStates outgoingState_;                    // outgoing data-flow state per CFG vertex ID
        typedef Sawyer::Container::DistinctList<size_t> WorkList;
        WorkList workList_;                             // CFG vertex IDs to be visited, last in first out w/out duplicates
        size_t maxIterations_;                          // max number of iterations to allow
        size_t nIterations_;                            // number of iterations since last reset
        PathFeasibility isFeasible_;                    // predicate to test path feasibility

    public:
        Engine(const CFG &cfg, TransferFunction &xfer, MergeFunction merge = MergeFunction(),
               PathFeasibility isFeasible = PathFeasibility())
            : cfg_(cfg), xfer_(xfer), merge_(merge), maxIterations_(-1), nIterations_(0), isFeasible_(isFeasible) {
            reset();
        }

        const CFG &cfg() const {
            return cfg_;
        }
        
        void reset(State initialState = State()) {
            ASSERT_this();
            incomingState_.clear();
            incomingState_.resize(cfg_.nVertices(), initialState);
            outgoingState_.clear();
            outgoingState_.resize(cfg_.nVertices(), initialState);
            workList_.clear();
            nIterations_ = 0;
        }

        const std::string& name() const { return name_; }
        void name(const std::string &s) { name_ = s; }
        std::string prefix() const {
            if (name_.empty()) {
                return "";
            } else {
                return name_ + ": ";
            }
        }

        size_t maxIterations() const { return maxIterations_; }
        void maxIterations(size_t n) { maxIterations_ = n; }
        size_t nIterations() const { return nIterations_; }
        
        bool runOneIteration() {
            using namespace Diagnostics;
            if (!workList_.isEmpty()) {
                if (++nIterations_ > maxIterations_) {
                    throw NotConverging("data-flow max iterations reached"
                                        " (max=" + StringUtility::numberToString(maxIterations_) + ")");
                }
                size_t cfgVertexId = workList_.popFront();
                if (mlog[DEBUG]) {
                    mlog[DEBUG] <<prefix() <<"runOneIteration: vertex #" <<cfgVertexId <<"\n";
                    mlog[DEBUG] <<prefix() <<"  remaining worklist is {";
                    for (size_t id: workList_.items())
                        mlog[DEBUG] <<" " <<id;
                    mlog[DEBUG] <<" }\n";
                }
                
                ASSERT_require2(cfgVertexId < cfg_.nVertices(),
                                "vertex " + boost::lexical_cast<std::string>(cfgVertexId) + " must be valid within CFG");
                typename CFG::ConstVertexIterator vertex = cfg_.findVertex(cfgVertexId);
                State state = incomingState_[cfgVertexId];
                if (mlog[DEBUG]) {
                    mlog[DEBUG] <<prefix() <<"  incoming state for vertex #" <<cfgVertexId <<":\n"
                                <<StringUtility::prefixLines(xfer_.toString(state), prefix() + "    ") <<"\n";
                }

                state = outgoingState_[cfgVertexId] = xfer_(cfg_, cfgVertexId, state);
                if (mlog[DEBUG]) {
                    mlog[DEBUG] <<prefix() <<"  outgoing state for vertex #" <<cfgVertexId <<":\n"
                                <<StringUtility::prefixLines(xfer_.toString(state), prefix() + "    ") <<"\n";
                }
                
                // Outgoing state must be merged into the incoming states for the CFG successors.  Any such incoming state that
                // is modified as a result will have its CFG vertex added to the work list.
                SAWYER_MESG(mlog[DEBUG]) <<prefix() <<"  forwarding vertex #" <<cfgVertexId <<" output state to "
                                         <<StringUtility::plural(vertex->nOutEdges(), "vertices", "vertex") <<"\n";
                for (const typename CFG::Edge &edge: vertex->outEdges()) {
                    size_t nextVertexId = edge.target()->id();
                    if (!isFeasible_(cfg_, edge, state, incomingState_[nextVertexId])) {
                        SAWYER_MESG(mlog[DEBUG]) <<prefix() <<"    path to vertex #" <<nextVertexId
                                                 <<" is not feasible, thus skipped\n";
                    } else if (merge_(incomingState_[nextVertexId], state)) {
                        if (mlog[DEBUG]) {
                            mlog[DEBUG] <<prefix() <<"    merged with vertex #" <<nextVertexId <<" (which changed as a result)\n";
                            mlog[DEBUG] <<prefix() <<"    merge state is: "
                                        <<StringUtility::prefixLines(xfer_.toString(incomingState_[nextVertexId]),
                                                                     prefix() + "      ", false) <<"\n";
                        }
                        workList_.pushBack(nextVertexId);
                    } else {
                        SAWYER_MESG(mlog[DEBUG]) <<prefix() <<"    merged with vertex #" <<nextVertexId <<" (no change)\n";
                    }
                }
            }
            return !workList_.isEmpty();
        }

        void insertStartingVertex(size_t startVertexId, const State &initialState) {
            incomingState_[startVertexId] = initialState;
            workList_.pushBack(startVertexId);
        }

        void runToFixedPoint() {
            while (runOneIteration()) /*void*/;
        }

        void runToFixedPoint(size_t startVertexId, const State &initialState) {
            reset();
            insertStartingVertex(startVertexId, initialState);
            while (runOneIteration()) /*void*/;
        }

        State getInitialState(size_t cfgVertexId) const {
            return incomingState_[cfgVertexId];
        }

        void setInitialState(size_t cfgVertexId, State state) {
            incomingState_[cfgVertexId] = state;
        }
        
        State getFinalState(size_t cfgVertexId) const {
            return outgoingState_[cfgVertexId];
        }

        const VertexStates& getInitialStates() const {
            return incomingState_;
        }

        const VertexStates& getFinalStates() const {
            return outgoingState_;
        }
    };
};

} // namespace
} // namespace

#endif
#endif