Partitioner2/DataFlow.h

#ifndef ROSE_BinaryAnalysis_Partitioner2_DataFlow_H
#define ROSE_BinaryAnalysis_Partitioner2_DataFlow_H
#include <featureTests.h>
#ifdef ROSE_ENABLE_BINARY_ANALYSIS
#include <Rose/BinaryAnalysis/Partitioner2/BasicTypes.h>
#include <Rose/BinaryAnalysis/InstructionSemantics/BaseSemantics/BasicTypes.h>

#include <Rose/BinaryAnalysis/DataFlow.h>
#include <Rose/BinaryAnalysis/Variables.h>
#include <Sawyer/Graph.h>

#include <ostream>
#include <string>

namespace Rose {
namespace BinaryAnalysis {
namespace Partitioner2 {

namespace DataFlow {

//                                      Control Flow Graph

class DfCfgVertex {
public:
    enum Type {
        BBLOCK,                                         
        FAKED_CALL,                                     
        FUNCRET,                                        
        INDET,                                          
    };

private:
    Type type_;
    BasicBlockPtr bblock_;                              // attached to BBLOCK vertices
    FunctionPtr callee_;                                // function represented by FAKED_CALL
    FunctionPtr parentFunction_;                        // function "owning" this vertex
    size_t inliningId_;                                 // invocation ID for inlining functions during inter-procedural

public:
    ~DfCfgVertex();

    DfCfgVertex(const BasicBlockPtr&, const FunctionPtr &parentFunction, size_t inliningId);

    DfCfgVertex(const FunctionPtr &function, const FunctionPtr &parentFunction, size_t inliningId);

    DfCfgVertex(Type type, const FunctionPtr &parentFunction, size_t inliningId);

    Type type() const;

    const BasicBlockPtr& bblock() const;

    const FunctionPtr& callee() const;

    FunctionPtr parentFunction() const;

    size_t inliningId() const;

    Sawyer::Optional<rose_addr_t> address() const;

    void print(std::ostream&) const;

    std::string toString() const;
};

using DfCfg = Sawyer::Container::Graph<DfCfgVertex>;

class InterproceduralPredicate {
public:
    virtual ~InterproceduralPredicate() {}
    virtual bool operator()(const ControlFlowGraph&, const ControlFlowGraph::ConstEdgeIterator&, size_t depth) = 0;
};

class NotInterprocedural: public InterproceduralPredicate {
public:
    bool operator()(const ControlFlowGraph&, const ControlFlowGraph::ConstEdgeIterator&, size_t /*depth*/) override {
        return false;
    }
};
extern NotInterprocedural NOT_INTERPROCEDURAL;

std::vector<SgAsmInstruction*> vertexUnpacker(const DfCfgVertex&);

DfCfg buildDfCfg(const PartitionerConstPtr&, const ControlFlowGraph&, const ControlFlowGraph::ConstVertexIterator &startVertex,
                 InterproceduralPredicate &predicate = NOT_INTERPROCEDURAL);

void dumpDfCfg(std::ostream&, const DfCfg&);

FunctionPtr bestSummaryFunction(const FunctionSet &functions);

template<class DfCfg>
typename Sawyer::Container::GraphTraits<DfCfg>::VertexIterator
findReturnVertex(DfCfg &dfCfg) {
    using namespace Sawyer::Container;
    typename GraphTraits<DfCfg>::VertexIterator retval = dfCfg.vertices().end();
    for (typename GraphTraits<DfCfg>::VertexIterator vi = dfCfg.vertices().begin(); vi != dfCfg.vertices().end(); ++vi) {
        if (vi->value().type() == DfCfgVertex::FUNCRET) {
            ASSERT_require(retval == dfCfg.vertices().end());
            retval = vi;
        }
    }
    return retval;
}

//                                      Transfer function
//
// The transfer function is reponsible for taking a CFG vertex and an initial state and producing the next state, the final
// state for that vertex.  Users can use whatever transfer function they want; this one is based on the DfCfg and an
// instruction semantics state.

class TransferFunction {
    InstructionSemantics::BaseSemantics::DispatcherPtr cpu_;
    InstructionSemantics::BaseSemantics::SValuePtr callRetAdjustment_;
    const RegisterDescriptor STACK_POINTER_REG;
    const RegisterDescriptor INSN_POINTER_REG;
    CallingConvention::DefinitionPtr defaultCallingConvention_;
    bool ignoringSemanticFailures_;

public:
    ~TransferFunction();

    explicit TransferFunction(const InstructionSemantics::BaseSemantics::DispatcherPtr&);

    InstructionSemantics::BaseSemantics::StatePtr initialState() const;

    InstructionSemantics::BaseSemantics::DispatcherPtr cpu() const;

    CallingConvention::DefinitionPtr defaultCallingConvention() const;
    void defaultCallingConvention(const CallingConvention::DefinitionPtr&);
    bool ignoringSemanticFailures() const;
    void ignoringSemanticFailures(bool);
    // Required by data-flow engine
    std::string toString(const InstructionSemantics::BaseSemantics::StatePtr &state);

    // Required by data-flow engine: compute new output state given a vertex and input state.
    InstructionSemantics::BaseSemantics::StatePtr
    operator()(const DfCfg&, size_t vertexId, const InstructionSemantics::BaseSemantics::StatePtr &incomingState) const;
};

typedef Rose::BinaryAnalysis::DataFlow::SemanticsMerge MergeFunction;

using Engine = Rose::BinaryAnalysis::DataFlow::Engine<DfCfg,
                                                      InstructionSemantics::BaseSemantics::StatePtr,
                                                      TransferFunction,
                                                      MergeFunction>;

Variables::StackVariables findStackVariables(const FunctionPtr &function,
                                             const InstructionSemantics::BaseSemantics::RiscOperatorsPtr &ops,
                                             const InstructionSemantics::BaseSemantics::SValuePtr &initialStackPointer);

Variables::StackVariables findLocalVariables(const FunctionPtr &function,
                                             const InstructionSemantics::BaseSemantics::RiscOperatorsPtr &ops,
                                             const InstructionSemantics::BaseSemantics::SValuePtr &initialStackPointer);

Variables::StackVariables findFunctionArguments(const FunctionPtr &function,
                                                const InstructionSemantics::BaseSemantics::RiscOperatorsPtr &ops,
                                                const InstructionSemantics::BaseSemantics::SValuePtr &initialStackPointer);

std::vector<AbstractLocation> findGlobalVariables(const InstructionSemantics::BaseSemantics::RiscOperatorsPtr &ops,
                                                  size_t wordNBytes);

} // namespace
} // namespace
} // namespace
} // namespace

#endif
#endif