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/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>
 
#ifdef ROSE_ENABLE_BOOST_SERIALIZATION
#include <boost/serialization/access.hpp>
#endif
 
namespace Rose {
namespace BinaryAnalysis {
namespace Partitioner2 {
 
namespace BaseSemantics = Rose::BinaryAnalysis::InstructionSemantics::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();
    }
};
 
class BasicBlockSuccessor {
private:
    Semantics::SValuePtr expr_;
    EdgeType type_;
    Confidence confidence_;
 
#ifdef ROSE_ENABLE_BOOST_SERIALIZATION
private:
    friend class boost::serialization::access;
    template<class S> void serialize(S &s, const unsigned /*version*/);
#endif
 
public: // "protected" fails for boost-1.58.
    // intentionally undocumented; needed for serialization
    BasicBlockSuccessor()
        : type_(E_USER_DEFINED), confidence_(ASSUMED) {}
 
public:
    explicit BasicBlockSuccessor(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; }
};
 
// BasicBlock
 
class BasicBlock: public Sawyer::SharedObject, public Sawyer::Attribute::Storage<> {
public:
    typedef Sawyer::SharedPointer<BasicBlock> Ptr;
 
    using Successor = BasicBlockSuccessor;
 
    using Successors = BasicBlockSuccessors;
 
private:
    mutable SAWYER_THREAD_TRAITS::Mutex mutex_;
 
    bool isFrozen_;                                     // True when the object becomes read-only
    Address 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<DataBlockPtr> 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<Address, size_t> InsnAddrMap;
    InsnAddrMap insnAddrMap_;                           // maps instruction address to index in insns_ vector
    bool hasIndirectControlFlow_ = false;               // true if block has indirect control flow
 
    // 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<Address> > 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;
public:
    void copyCache(const BasicBlockPtr &other);
 
 
    //                                  Serialization
#ifdef ROSE_ENABLE_BOOST_SERIALIZATION
private:
    friend class boost::serialization::access;
    template<class S> void serializeCommon(S&, const unsigned version);
    template<class S> void save(S&, const unsigned version) const;
    template<class S> void load(S&, const unsigned version);
    BOOST_SERIALIZATION_SPLIT_MEMBER();
#endif
 
 
    //                                  Constructors
protected:
    BasicBlock();                                       // needed for serialization
 
    // use instance() instead
    BasicBlock(Address startVa, const PartitionerConstPtr&);
public:
    ~BasicBlock();
 
public:
    static Ptr instance(Address startVa, const PartitionerConstPtr &partitioner) {
        return Ptr(new BasicBlock(startVa, partitioner));
    }
 
    virtual Ptr create(Address startVa, const PartitionerConstPtr &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:
    Address address() const {
        SAWYER_THREAD_TRAITS::LockGuard lock(mutex_);
        return startVa_;
    }
 
    AddressIntervalSet insnAddresses() const;
 
    Address 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(Address startVa) const;
 
    Sawyer::Optional<size_t> instructionExists(SgAsmInstruction*) const;
 
    Sawyer::Optional<size_t> instructionIndex(Address) const;
    Sawyer::Optional<size_t> instructionIndex(SgAsmInstruction*) const;
    const std::vector<SgAsmInstruction*>& instructions() const { return insns_; }
 
    void append(const PartitionerConstPtr&, SgAsmInstruction*);
 
    void pop();
 
    std::set<Address> explicitConstants() const;
 
 
    //                                  Static data blocks
public:
    size_t nDataBlocks() const;
 
    AddressIntervalSet dataAddresses() const;
 
    DataBlockPtr dataBlockExists(const DataBlockPtr&) const;
 
    bool insertDataBlock(const DataBlockPtr&);
 
    DataBlockPtr eraseDataBlock(const DataBlockPtr&);
 
    const std::vector<DataBlockPtr>& dataBlocks() const { return dblocks_; }
 
 
    //                                  Semantics
public:
    BasicBlockSemantics semantics() const;
 
    void dropSemantics(const PartitionerConstPtr&);
 
    BasicBlockSemantics undropSemantics(const PartitionerConstPtr&);
 
 
 
    //                                  Control flow
public:
    const Sawyer::Cached<Successors>& successors() const { return successors_; }
    void successors(const Successors&);
    const Sawyer::Cached<std::set<Address> >& ghostSuccessors() const { return ghostSuccessors_; }
 
    void insertSuccessor(const BaseSemantics::SValuePtr&, EdgeType type=E_NORMAL, Confidence confidence=ASSUMED);
    void insertSuccessor(Address va, size_t nBits, EdgeType type=E_NORMAL, Confidence confidence=ASSUMED);
    bool eraseSuccessor(const BaseSemantics::SValuePtr&, EdgeType type, Sawyer::Optional<Confidence> = Sawyer::Nothing());
    bool eraseSuccessor(const BasicBlockSuccessor&);
    void clearSuccessors();
 
    bool hasIndirectControlFlow() const;
    void hasIndirectControlFlow(bool);
    //                                  Cached properties computed elsewhere
public:
    const Sawyer::Cached<bool>& isFunctionCall() const { return isFunctionCall_; }
    void isFunctionCall(bool flag) const { isFunctionCall_.set(flag); }
 
    const Sawyer::Cached<bool>& isFunctionReturn() const { return isFunctionReturn_; }
    void isFunctionReturn(bool flag) const { isFunctionReturn_.set(flag); }
 
    const Sawyer::Cached<bool>& mayReturn() const { return mayReturn_; }
    void mayReturn(bool flag) const { mayReturn_.set(flag); }
 
    const Sawyer::Cached<bool>& popsStack() const { return popsStack_; }
    void popsStack(bool flag) const { popsStack_.set(flag); }
 
    
    //                                  Output
public:
    std::string printableName() const;
 
 
    //                                  Private members for the partitioner
private:
    friend class Partitioner;
    void init(const PartitionerConstPtr&);
    void freeze() { isFrozen_ = true; semantics_.optionalPenultimateState = Sawyer::Nothing(); }
    void thaw() { isFrozen_ = false; }
    BasicBlockSemantics undropSemanticsNS(const PartitionerConstPtr&);
 
    // Find an equivalent data block and replace it with the specified data block, or insert the specified data block.
    void replaceOrInsertDataBlock(const DataBlockPtr&);
};
 
} // namespace
} // namespace
} // namespace
 
#endif
#endif