BasicBlock.h

#ifndef ROSE_Partitioner2_BasicBlock_H
#define ROSE_Partitioner2_BasicBlock_H

#include <Partitioner2/BasicTypes.h>
#include <Partitioner2/DataBlock.h>
#include <Partitioner2/Semantics.h>

#include <Sawyer/Attribute.h>
#include <Sawyer/Cached.h>
#include <Sawyer/Map.h>
#include <Sawyer/Optional.h>
#include <Sawyer/SharedPointer.h>

#include <boost/serialization/access.hpp>
#include <boost/serialization/base_object.hpp>
#include <boost/serialization/set.hpp>
#include <boost/serialization/string.hpp>
#include <boost/serialization/vector.hpp>

namespace Rose {
namespace BinaryAnalysis {
namespace Partitioner2 {

namespace BaseSemantics = Rose::BinaryAnalysis::InstructionSemantics2::BaseSemantics;

class BasicBlock: public Sawyer::SharedObject, public Sawyer::Attribute::Storage<> {
public:
    typedef Sawyer::SharedPointer<BasicBlock> Ptr;

    class Successor {
    private:
        Semantics::SValuePtr expr_;
        EdgeType type_;
        Confidence confidence_;

#ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
    private:
        friend class boost::serialization::access;

        template<class S>
        void serialize(S &s, const unsigned /*version*/) {
            s & BOOST_SERIALIZATION_NVP(expr_);
            s & BOOST_SERIALIZATION_NVP(type_);
            s & BOOST_SERIALIZATION_NVP(confidence_);
        }
#endif

    protected:
        // intentionally undocumented; needed for serialization
        Successor()
            : type_(E_USER_DEFINED), confidence_(ASSUMED) {}

    public:
        explicit Successor(const Semantics::SValuePtr &expr, EdgeType type=E_NORMAL, Confidence confidence=ASSUMED)
            : expr_(expr), type_(type), confidence_(confidence) {}

        const Semantics::SValuePtr& expr() const { return expr_; }

        EdgeType type() const { return type_; }
        void type(EdgeType t) { type_ = t; }

        Confidence confidence() const { return confidence_; }
        void confidence(Confidence c) { confidence_ = c; }
    };

    typedef std::vector<Successor> Successors;

private:
    bool isFrozen_;                                     // True when the object becomes read-only
    rose_addr_t startVa_;                               // Starting address, perhaps redundant with insns_[0]->p_address
    std::string comment_;                               // Mutli-line plain-text comment
    std::vector<SgAsmInstruction*> insns_;              // Instructions in the order they're executed
    BaseSemantics::DispatcherPtr dispatcher_;           // How instructions are dispatched (null if no instructions)
    BaseSemantics::RiscOperatorsPtr operators_;         // Risc operators even if we're not using a dispatcher
    BaseSemantics::StatePtr initialState_;              // Initial state for semantics (null if dropped semantics)
    bool usingDispatcher_;                              // True if dispatcher's state is up-to-date for the final instruction
    Sawyer::Optional<BaseSemantics::StatePtr> optionalPenultimateState_; // One level of undo information
    std::vector<DataBlock::Ptr> dblocks_;               // Data blocks owned by this basic block, sorted

    // When a basic block gets lots of instructions some operations become slow due to the linear nature of the instruction
    // list. Therefore, we also keep a mapping from instruction address to position in the list. The mapping is only used when
    // the bigBlock size is reached.
    static const size_t bigBlock_ = 200;
    typedef Sawyer::Container::Map<rose_addr_t, size_t> InsnAddrMap;
    InsnAddrMap insnAddrMap_;                           // maps instruction address to index in insns_ vector

    // The following members are caches either because their value is seldom needed and expensive to compute, or because
    // the value is best computed at a higher layer than a single basic block (e.g., in the partitioner) yet it makes the
    // most sense to store it here. Make sure clearCache() resets these to initial values.
    Sawyer::Cached<Successors> successors_;             // control flow successors out of final instruction
    Sawyer::Cached<std::set<rose_addr_t> > ghostSuccessors_;// non-followed successors from opaque predicates, all insns
    Sawyer::Cached<bool> isFunctionCall_;               // is this block semantically a function call?
    Sawyer::Cached<bool> isFunctionReturn_;             // is this block semantically a return from the function?
    Sawyer::Cached<bool> mayReturn_;                    // a function return is reachable from this basic block in the CFG

    void clearCache() const {
        successors_.clear();
        ghostSuccessors_.clear();
        isFunctionCall_.clear();
        isFunctionReturn_.clear();
        mayReturn_.clear();
    }

public:
    void copyCache(const BasicBlock::Ptr other) {
        successors_ = other->successors_;
        ghostSuccessors_ = other->ghostSuccessors_;
        isFunctionCall_ = other->isFunctionCall_;
        isFunctionReturn_ = other->isFunctionReturn_;
        mayReturn_ = other->mayReturn_;
    }


    //                                  Serialization
#ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
private:
    friend class boost::serialization::access;

    template<class S>
    void serialize(S &s, const unsigned /*version*/) {
        //s & boost::serialization::base_object<Sawyer::Attribute::Storage<> >(*this); -- not saved
        s & BOOST_SERIALIZATION_NVP(isFrozen_);
        s & BOOST_SERIALIZATION_NVP(startVa_);
        s & BOOST_SERIALIZATION_NVP(comment_);
        s & BOOST_SERIALIZATION_NVP(insns_);
        s & BOOST_SERIALIZATION_NVP(dispatcher_);       // FIXME[Robb P Matzke 2016-11-07]
        s & BOOST_SERIALIZATION_NVP(operators_);        // FIXME[Robb P Matzke 2016-11-07]
        s & BOOST_SERIALIZATION_NVP(initialState_);
        s & BOOST_SERIALIZATION_NVP(usingDispatcher_);
        s & BOOST_SERIALIZATION_NVP(optionalPenultimateState_);
        s & BOOST_SERIALIZATION_NVP(dblocks_);
        s & BOOST_SERIALIZATION_NVP(insnAddrMap_);
        s & BOOST_SERIALIZATION_NVP(successors_);
        s & BOOST_SERIALIZATION_NVP(ghostSuccessors_);
        s & BOOST_SERIALIZATION_NVP(isFunctionCall_);
        s & BOOST_SERIALIZATION_NVP(isFunctionReturn_);
        s & BOOST_SERIALIZATION_NVP(mayReturn_);
    }
#endif


    //                                  Constructors
protected:
    BasicBlock()                                        // needed for serialization
        : isFrozen_(false), startVa_(0), usingDispatcher_(false) {}

    // use instance() instead
    BasicBlock(rose_addr_t startVa, const Partitioner *partitioner)
        : isFrozen_(false), startVa_(startVa), usingDispatcher_(true) { init(partitioner); }

public:
    static Ptr instance(rose_addr_t startVa, const Partitioner *partitioner) {
        return Ptr(new BasicBlock(startVa, partitioner));
    }

    virtual Ptr create(rose_addr_t startVa, const Partitioner *partitioner) const {
        return instance(startVa, partitioner);
    }


    //                                  Status
public:
    bool isFrozen() const { return isFrozen_; }

    const std::string& comment() const { return comment_; }
    void comment(const std::string &s) { comment_ = s; }
    //                                  Instructions
public:
    rose_addr_t address() const { return startVa_; }

    AddressIntervalSet insnAddresses() const;

    rose_addr_t fallthroughVa() const;

    size_t nInstructions() const { return insns_.size(); }

    bool isEmpty() const { return insns_.empty(); }

    SgAsmInstruction* instructionExists(rose_addr_t startVa) const;

    Sawyer::Optional<size_t> instructionExists(SgAsmInstruction*) const;

    const std::vector<SgAsmInstruction*>& instructions() const { return insns_; }

    void append(SgAsmInstruction*);

    void pop();


    //                                  Static data blocks
public:
    size_t nDataBlocks() const { return dblocks_.size(); }

    AddressIntervalSet dataAddresses() const;

    DataBlock::Ptr dataBlockExists(const DataBlock::Ptr&) const;

    bool insertDataBlock(const DataBlock::Ptr&);

    const std::vector<DataBlock::Ptr> dataBlocks() const { return dblocks_; }


    //                                  Semantics
public:
    bool isSemanticsDropped() const { return dispatcher_ && !initialState_; }

    bool isSemanticsError() const { return dispatcher_ && initialState_ && !usingDispatcher_; }

    const BaseSemantics::StatePtr& initialState() const { return initialState_; }

    BaseSemantics::StatePtr finalState();

    const BaseSemantics::DispatcherPtr& dispatcher() const { return dispatcher_; }

    void dropSemantics();

    void undropSemantics();


    //                                  Control flow
public:
    const Sawyer::Cached<Successors>& successors() const { return successors_; }
    void successors(const Successors&);
    const Sawyer::Cached<std::set<rose_addr_t> >& ghostSuccessors() const { return ghostSuccessors_; }

    void insertSuccessor(const BaseSemantics::SValuePtr&, EdgeType type=E_NORMAL, Confidence confidence=ASSUMED);
    void insertSuccessor(rose_addr_t va, size_t nBits, EdgeType type=E_NORMAL, Confidence confidence=ASSUMED);
    void clearSuccessors();


    //                                  Cached properties computed elsewhere
public:
    const Sawyer::Cached<bool>& isFunctionCall() const { return isFunctionCall_; }

    const Sawyer::Cached<bool>& isFunctionReturn() const { return isFunctionReturn_; }

//     /** Property: Initial stack pointer.
//      *
//      *  Stack pointer at the entrance to the basic block relative to the stack pointer at the entrance to the basic block's
//      *  function.  This property caches the value computed elsewhere. See also, @ref stackDeltaOut and @ref stackDelta.
//      *
//      *  The @ref stackDeltaInConcrete method is a read-only accessor for the @ref stackDeltaIn property that returns the stack
//      *  delta expression as either a 64-bit signed value or the @ref SgAsmInstruction::INVALID_STACK_DELTA constant.
//      *
//      * @{ */
//     BaseSemantics::SValuePtr stackDeltaIn() const;
//     void stackDeltaIn(const BaseSemantics::SValuePtr&);
//     int64_t stackDeltaInConcrete() const;
//     /** @} */
// 
//     /** Property: Final stack pointer.
//      *
//      *  Stack pointer at the exit of the basic block relative to the stack pointer at the entrance to the basic block's
//      *  function.  This property caches the value computed elsewhere. See also, @ref stackDeltaIn and @ref stackDelta.
//      *
//      *  The @ref stackDeltaOutConcrete method is a read-only accessor for the @ref stackDeltaOut property that returns the
//      *  stack delta expression as either a 64-bit signed value or the @ref SgAsmInstruction::INVALID_STACK_DELTA constant.
//      *
//      * @{ */
//     BaseSemantics::SValuePtr stackDeltaOut() const;
//     void stackDeltaOut(const BaseSemantics::SValuePtr&);
//     int64_t stackDeltaOutConcrete() const;
//     /** @} */
// 
//     /** Property: Stack delta.
//      *
//      *  The stack delta is the difference between the final and initial stack pointers for this basic block if available. There
//      *  are two forms of this function: @ref stackDelta returns a symbolic expression or null, and @ref stackDeltaConcrete
//      *  returns a 64-bit signed value or the @ref SgAsmInstruction::INVALID_STACK_DELTA constant.
//      *
//      *  The symbolic stack delta is a property that can be queried or set. It is set by the stack pointer analysis. The
//      *  concrete version is a wrapper that returns a numeric value from the symbolic value.
//      *
//      * @{ */
//     BaseSemantics::SValuePtr stackDelta() const;
//     void stackDelta(const BaseSemantics::SValuePtr&);
//     int64_t stackDeltaConcrete() const;
//     /** @} */

    const Sawyer::Cached<bool>& mayReturn() const { return mayReturn_; }


    //                                  Output
public:
    std::string printableName() const;


    //                                  Private members for the partitioner
private:
    friend class Partitioner;
    void init(const Partitioner*);
    void freeze() { isFrozen_ = true; optionalPenultimateState_ = Sawyer::Nothing(); }
    void thaw() { isFrozen_ = false; }
};

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

#endif