AddressUsageMap.h

#ifndef ROSE_BinaryAnalysis_Partitioner2_AddressUsageMap_H
#define ROSE_BinaryAnalysis_Partitioner2_AddressUsageMap_H
#include <featureTests.h>
#ifdef ROSE_ENABLE_BINARY_ANALYSIS
#include <Rose/BinaryAnalysis/Partitioner2/BasicTypes.h>
 
#include <Rose/BinaryAnalysis/AddressIntervalSet.h>
 
#include <Sawyer/IntervalMap.h>
#include <Sawyer/IntervalSet.h>
#include <Sawyer/Optional.h>
 
#ifdef ROSE_ENABLE_BOOST_SERIALIZATION
#include <boost/serialization/access.hpp>
#endif
 
#include <algorithm>
#include <ostream>
#include <string>
 
class SgAsmInstruction;
 
namespace Rose {
namespace BinaryAnalysis {
namespace Partitioner2 {
 
// AddressUser
 
class AddressUser {
    SgAsmInstruction *insn_;
    std::vector<BasicBlockPtr> bblocks_;                // sorted and unique
    DataBlockPtr dblock_;
 
#ifdef ROSE_ENABLE_BOOST_SERIALIZATION
private:
    friend class boost::serialization::access;
    template<class S> void serialize(S&, const unsigned version);
#endif
 
public:
    AddressUser();
 
    AddressUser(SgAsmInstruction*, const BasicBlockPtr&);
 
    explicit AddressUser(const DataBlockPtr&);
 
    ~AddressUser();
 
    Address address() const;
 
    bool isBasicBlock() const;
 
    bool isDataBlock() const;
 
    bool isEmpty() const;
 
    SgAsmInstruction* insn() const;
 
    BasicBlockPtr firstBasicBlock() const;
 
    const std::vector<BasicBlockPtr>& basicBlocks() const;
 
    void insertBasicBlock(const BasicBlockPtr &bblock);
 
    void eraseBasicBlock(const BasicBlockPtr &bblock);
    
    DataBlockPtr dataBlock() const;
 
    BasicBlockPtr isBlockEntry() const;
 
    bool operator==(const AddressUser &other) const;
 
    bool operator<(const AddressUser&) const;
 
    void print(std::ostream&) const;
 
    bool isConsistent() const;
 
    operator bool() const {
        return !isEmpty();
    }
};
 
 
// AddressUsers
 
class AddressUsers {
    std::vector<AddressUser> users_;                    // sorted
 
#ifdef ROSE_ENABLE_BOOST_SERIALIZATION
private:
    friend class boost::serialization::access;
    template<class S> void serialize(S&, const unsigned version);
#endif
 
public:
    AddressUsers();
    ~AddressUsers();
 
    explicit AddressUsers(SgAsmInstruction *insn, const BasicBlockPtr&);
 
    explicit AddressUsers(const DataBlockPtr&);
 
    SgAsmInstruction* instructionExists(SgAsmInstruction*) const;
    SgAsmInstruction* instructionExists(Address va) const;
    BasicBlockPtr basicBlockExists(const BasicBlockPtr&) const;
    BasicBlockPtr basicBlockExists(Address va) const;
    DataBlockPtr dataBlockExists(const DataBlockPtr&) const;
    DataBlockPtr dataBlockExists(Address va, Address size) const;
    AddressUser findInstruction(SgAsmInstruction*) const;
    AddressUser findInstruction(Address va) const;
    AddressUser findBasicBlock(const BasicBlockPtr&) const;
    AddressUser findBasicBlock(Address va) const;
    AddressUser findDataBlock(const DataBlockPtr&) const;
    AddressUser findDataBlock(Address va, Address size) const;
    AddressUser insertInstruction(SgAsmInstruction*, const BasicBlockPtr&);
 
    AddressUser insertDataBlock(const DataBlockPtr&);
 
    void insert(const AddressUsers&);
 
    SgAsmInstruction* eraseInstruction(SgAsmInstruction*, const BasicBlockPtr&);
 
    DataBlockPtr eraseDataBlock(const DataBlockPtr&);
 
    static bool selectAllUsers(const AddressUser&);
 
    static bool selectBasicBlocks(const AddressUser&);
 
    static bool selectDataBlocks(const AddressUser&);
 
    template<class UserPredicate>
    AddressUsers select(UserPredicate predicate) const {
        AddressUsers retval;
        for (const AddressUser &user: users_) {
            if (predicate(user))
                retval.users_.push_back(user);
        }
        return retval;
    }
 
    const std::vector<AddressUser>& addressUsers() const;
 
    AddressUsers instructionUsers() const;
 
    AddressUsers dataBlockUsers() const;
 
    std::vector<SgAsmInstruction*> instructions() const;
 
    std::vector<BasicBlockPtr> instructionOwners() const;
 
    std::vector<DataBlockPtr> dataBlocks() const;
 
    size_t size() const;
 
    bool isEmpty() const;
 
    AddressUsers intersection(const AddressUsers&) const;
 
    AddressUsers union_(const AddressUsers&) const;
 
    bool operator==(const AddressUsers &other) const;
 
    void print(std::ostream&) const;
 
    bool isConsistent() const;
};
 
 
// AddressUsageMap
 
class AddressUsageMap {
    using Map = Sawyer::Container::IntervalMap<AddressInterval, AddressUsers>;
    Map map_;
 
#ifdef ROSE_ENABLE_BOOST_SERIALIZATION
private:
    friend class boost::serialization::access;
    template<class S> void serialize(S&, const unsigned version);
#endif
 
public:
    AddressUsageMap();
    ~AddressUsageMap();
 
public:
    bool isEmpty() const;
 
    void clear();
 
    size_t size() const;
 
    AddressInterval hull() const;
 
    AddressIntervalSet extent() const;
 
    bool exists(Address) const;
 
    bool anyExists(const AddressInterval&) const;
    bool anyExists(const AddressIntervalSet&) const;
    AddressIntervalSet unusedExtent(size_t nBits) const;
    AddressIntervalSet unusedExtent(const AddressInterval&) const;
    AddressIntervalSet unusedExtent(const AddressIntervalSet&) const;
    AddressInterval nextUnused(Address minVa) const;
 
    SgAsmInstruction* instructionExists(SgAsmInstruction*) const;
    SgAsmInstruction* instructionExists(Address va) const;
    BasicBlockPtr basicBlockExists(const BasicBlockPtr&) const;
    BasicBlockPtr basicBlockExists(Address startOfBlock) const;
    DataBlockPtr dataBlockExists(const DataBlockPtr&) const;
    DataBlockPtr dataBlockExists(Address va, Address size) const;
    AddressUser findInstruction(SgAsmInstruction*) const;
    AddressUser findInstruction(Address va) const;
    AddressUser findBasicBlock(const BasicBlockPtr&) const;
    AddressUser findBasicBlock(Address va) const;
    AddressUser findDataBlock(const DataBlockPtr&) const;
    AddressUser findDataBlock(Address va, Address size) const;
    AddressUser insertInstruction(SgAsmInstruction*, const BasicBlockPtr&);
 
    AddressUser insertDataBlock(const DataBlockPtr&);
 
    SgAsmInstruction* eraseInstruction(SgAsmInstruction*, const BasicBlockPtr&);
 
    DataBlockPtr eraseDataBlock(const DataBlockPtr&);
 
    AddressUsers spanning(const AddressInterval&) const;
 
    template<class UserPredicate>
    AddressUsers spanning(const AddressInterval &interval, UserPredicate userPredicate) const {
        AddressUsers retval;
        size_t nIters = 0;
        for (const Map::Node &node: map_.findAll(interval)) {
            AddressUsers users = node.value().select(userPredicate);
            retval = 0==nIters++ ? users : retval.intersection(users);
            if (retval.isEmpty())
                break;
        }
        return retval;
    }
    AddressUsers overlapping(const AddressInterval&) const;
 
    template<class UserPredicate>
    AddressUsers overlapping(const AddressInterval &interval, UserPredicate userPredicate) const {
        AddressUsers retval;
        for (const Map::Node &node: map_.findAll(interval))
            retval.insert(node.value().select(userPredicate));
        return retval;
    }
    // FIXME[Robb P. Matzke 2014-08-26]: not implemented yet
    AddressUsers containedIn(const AddressInterval&) const;
 
    //template<class UserPredicate>
    //AddressUsers containedIn(const AddressInterval &interval, UserPredicate userPredicate) const {...}
    Sawyer::Optional<Address> leastUnmapped(Address startVa) const;
 
    void print(std::ostream&, const std::string &prefix="") const;
 
    void checkConsistency() const;
};
 
} // namespace
} // namespace
} // namespace
 
#endif
#endif