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/DataFlow.h>
#include <Rose/BinaryAnalysis/Partitioner2/BasicBlock.h>
#include <Rose/BinaryAnalysis/Partitioner2/ControlFlowGraph.h>
#include <Rose/BinaryAnalysis/Partitioner2/Function.h>
#include <Sawyer/Graph.h>

namespace Rose {
namespace BinaryAnalysis {
namespace Partitioner2 {

namespace DataFlow {

//                                      Control Flow Graph

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

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

public:
    explicit DfCfgVertex(const BasicBlock::Ptr &bblock, const Function::Ptr &parentFunction, size_t inliningId)
        : type_(BBLOCK), bblock_(bblock), parentFunction_(parentFunction), inliningId_(inliningId) {
        ASSERT_not_null(bblock);
    }

    explicit DfCfgVertex(const Function::Ptr &function, const Function::Ptr &parentFunction, size_t inliningId)
        : type_(FAKED_CALL), callee_(function), parentFunction_(parentFunction), inliningId_(inliningId) {}

    explicit DfCfgVertex(Type type, const Function::Ptr &parentFunction, size_t inliningId)
        : type_(type), parentFunction_(parentFunction), inliningId_(inliningId) {
        ASSERT_require2(BBLOCK!=type && FAKED_CALL!=type, "use a different constructor");
    }

    Type type() const { return type_; }

    const BasicBlock::Ptr& bblock() const { return bblock_; }

    const Function::Ptr& callee() const { return callee_; }

    Function::Ptr parentFunction() const { return parentFunction_; }

    size_t inliningId() const { return inliningId_; }

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

typedef Sawyer::Container::Graph<DfCfgVertex> DfCfg;

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 Partitioner&, const ControlFlowGraph&, const ControlFlowGraph::ConstVertexIterator &startVertex,
                 InterproceduralPredicate &predicate = NOT_INTERPROCEDURAL);

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

Function::Ptr 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 {
    BaseSemantics::DispatcherPtr cpu_;
    BaseSemantics::SValuePtr callRetAdjustment_;
    const RegisterDescriptor STACK_POINTER_REG;
    const RegisterDescriptor INSN_POINTER_REG;
    CallingConvention::DefinitionPtr defaultCallingConvention_;
public:
    explicit TransferFunction(const BaseSemantics::DispatcherPtr &cpu)
        : cpu_(cpu), STACK_POINTER_REG(cpu->stackPointerRegister()), INSN_POINTER_REG(cpu->instructionPointerRegister()) {
        size_t adjustment = STACK_POINTER_REG.nBits() / 8; // sizeof return address on top of stack
        callRetAdjustment_ = cpu->number_(STACK_POINTER_REG.nBits(), adjustment);
    }

    BaseSemantics::StatePtr initialState() const;

    BaseSemantics::DispatcherPtr cpu() const { return cpu_; }

    CallingConvention::DefinitionPtr defaultCallingConvention() const { return defaultCallingConvention_; }
    void defaultCallingConvention(const CallingConvention::DefinitionPtr &x) { defaultCallingConvention_ = x; }
    // Required by data-flow engine
    std::string toString(const BaseSemantics::StatePtr &state);

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

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

typedef Rose::BinaryAnalysis::DataFlow::Engine<DfCfg, BaseSemantics::StatePtr, TransferFunction, MergeFunction> Engine;

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

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

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

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



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

#endif
#endif