BasicBlock.h

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

#include <Rose/BinaryAnalysis/Partitioner2/BasicTypes.h>
#include <Rose/BinaryAnalysis/Partitioner2/DataBlock.h>
#include <Rose/BinaryAnalysis/Partitioner2/Semantics.h>
#include <Rose/SourceLocation.h>

#include <Sawyer/Attribute.h>
#include <Sawyer/Cached.h>
#include <Sawyer/Map.h>
#include <Sawyer/Optional.h>
#include <Sawyer/SharedPointer.h>
#include <Sawyer/Synchronization.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;

// BasicBlockSemantics

class BasicBlockSemantics {
public:
    BaseSemantics::DispatcherPtr dispatcher;

    BaseSemantics::RiscOperatorsPtr operators;

    BaseSemantics::StatePtr initialState;

    bool usingDispatcher;

    Sawyer::Optional<BaseSemantics::StatePtr> optionalPenultimateState;

    bool wasDropped;

public:
    BasicBlockSemantics()
        : usingDispatcher(false), wasDropped(false) {}

    bool isSemanticsDropped() const {
        return dispatcher && !initialState;
    }

    bool isSemanticsError() const {
        return dispatcher && initialState && !usingDispatcher;
    }
    
    BaseSemantics::StatePtr finalState() const {
        return usingDispatcher && operators ? operators->currentState() : BaseSemantics::StatePtr();
    }
};

// BasicBlock

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

    public: // "protected" fails for boost-1.58.
        // 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:
    mutable SAWYER_THREAD_TRAITS::Mutex mutex_;

    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
    BasicBlockSemantics semantics_;                     // All semantics-related information
    std::vector<DataBlock::Ptr> dblocks_;               // Data blocks owned by this basic block, sorted
    SourceLocation sourceLocation_;                     // Optional location of basic block in source code

    // 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
    Sawyer::Cached<bool> popsStack_;                    // basic block has a net popping effect

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

public:
    void copyCache(const BasicBlock::Ptr &other) {
        ASSERT_not_null(other);
        SAWYER_THREAD_TRAITS::LockGuard2 lock(mutex_, other->mutex_);
        successors_ = other->successors_;
        ghostSuccessors_ = other->ghostSuccessors_;
        isFunctionCall_ = other->isFunctionCall_;
        isFunctionReturn_ = other->isFunctionReturn_;
        mayReturn_ = other->mayReturn_;
        popsStack_ = other->popsStack_;
    }


    //                                  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::make_nvp("dispatcher_", semantics_.dispatcher);
        s & boost::serialization::make_nvp("operators_", semantics_.operators);
        s & boost::serialization::make_nvp("initialState_", semantics_.initialState);
        s & boost::serialization::make_nvp("usingDispatcher_", semantics_.usingDispatcher);
        s & boost::serialization::make_nvp("optionalPenultimateState_", semantics_.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_);
        if (version >= 1)
            s & BOOST_SERIALIZATION_NVP(popsStack_);
        if (version >= 2)
            s & BOOST_SERIALIZATION_NVP(sourceLocation_);
    }
#endif


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

    // use instance() instead
    BasicBlock(rose_addr_t startVa, const Partitioner &partitioner)
        : isFrozen_(false), startVa_(startVa) {
        semantics_.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);
    }

    //                                  Cache
public:
    void clearCache() {
        SAWYER_THREAD_TRAITS::LockGuard lock(mutex_);
        clearCacheNS();
    }
    
    //                                  Status
public:
    bool isFrozen() const {
        SAWYER_THREAD_TRAITS::LockGuard lock(mutex_);
        return isFrozen_;
    }

    const std::string& comment() const { return comment_; }
    void comment(const std::string &s) { comment_ = s; }
    const SourceLocation& sourceLocation() const { return sourceLocation_; }
    void sourceLocation(const SourceLocation &loc) { sourceLocation_ = loc; }
    //                                  Instructions
public:
    rose_addr_t address() const {
        SAWYER_THREAD_TRAITS::LockGuard lock(mutex_);
        return startVa_;
    }

    AddressIntervalSet insnAddresses() const;

    rose_addr_t fallthroughVa() const;

    size_t nInstructions() const {
        SAWYER_THREAD_TRAITS::LockGuard lock(mutex_);
        return insns_.size();
    }

    bool isEmpty() const {
        SAWYER_THREAD_TRAITS::LockGuard lock(mutex_);
        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(const Partitioner&, SgAsmInstruction*);

    void pop();

    std::set<rose_addr_t> explicitConstants() const;


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

    AddressIntervalSet dataAddresses() const;

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

    bool insertDataBlock(const DataBlock::Ptr&);

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

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


    //                                  Semantics
public:
    BasicBlockSemantics semantics() const;

    void dropSemantics(const Partitioner&);

    BasicBlockSemantics undropSemantics(const Partitioner&);



    //                                  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_; }

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

    const Sawyer::Cached<bool>& popsStack() const { return popsStack_; }

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


    //                                  Private members for the partitioner
private:
    friend class Partitioner;
    void init(const Partitioner&);
    void freeze() { isFrozen_ = true; semantics_.optionalPenultimateState = Sawyer::Nothing(); }
    void thaw() { isFrozen_ = false; }
    BasicBlockSemantics undropSemanticsNS(const Partitioner&);

    // Find an equivalent data block and replace it with the specified data block, or insert the specified data block.
    void replaceOrInsertDataBlock(const DataBlock::Ptr&);
};

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

// Class versions must be at global scope
BOOST_CLASS_VERSION(Rose::BinaryAnalysis::Partitioner2::BasicBlock, 2);

#endif
#endif