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<Address> 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