Reachability.h

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

#include <Rose/BitFlags.h>
#include <boost/serialization/access.hpp>
#include <boost/serialization/split_member.hpp>
#include <Rose/BinaryAnalysis/Partitioner2/ControlFlowGraph.h>
#include <Sawyer/Map.h>
#include <Sawyer/Tracker.h>
#include <set>
#include <vector>

namespace Rose {
namespace BinaryAnalysis {

class Reachability {
public:
    enum Reason {
        // Predefined reasons
        NOT_REACHABLE           = 0,                    
        PROGRAM_ENTRY_POINT     = 0x00000001,           
        EXPORTED_FUNCTION       = 0x00000002,           
        SIGNAL_HANDLER          = 0x00000004,           
        ASSUMED                 = 0x00000080,           
        EXPLICIT_MEM_CONSTANT   = 0x00000100,           
        EXPLICIT_INSN_CONSTANT  = 0x00000200,           
        IMPLICIT_FUNC_CONSTANT  = 0x00000400,           
        // User-defined reasons
        USER_DEFINED_0          = 0x00010000,           
        USER_DEFINED_1          = 0x00020000,           
        USER_DEFINED_2          = 0x00040000,           
        USER_DEFINED_3          = 0x00080000,           
        USER_DEFINED_4          = 0x00100000,           
        USER_DEFINED_5          = 0x00200000,           
        USER_DEFINED_6          = 0x00400000,           
        USER_DEFINED_7          = 0x00800000,           
        USER_DEFINED_8          = 0x01000000,           
        USER_DEFINED_9          = 0x02000000,           
        USER_DEFINED_10         = 0x04000000,           
        USER_DEFINED_11         = 0x08000000,           
        USER_DEFINED_12         = 0x10000000,           
        USER_DEFINED_13         = 0x20000000,           
        USER_DEFINED_14         = 0x40000000,           
        USER_DEFINED_15         = 0x80000000            
    };

    typedef BitFlags<Reason, uint32_t> ReasonFlags;

    struct Settings {
        ReasonFlags markingEntryFunctions;               
        ReasonFlags markingExportFunctions;              
        ReasonFlags markingExplicitMemoryReferents;      
        ReasonFlags markingExplicitInstructionReferents; 
        ReasonFlags markingImplicitFunctionReferents;    
        rose_addr_t addressAlignment;                    
        size_t addressNBytes;                            
        ByteOrder::Endianness byteOrder;                 
        bool precomputeImplicitFunctionReferents;        
        Sawyer::Optional<size_t> nThreads;               
        Settings()
            : markingEntryFunctions(PROGRAM_ENTRY_POINT),
              markingExportFunctions(EXPORTED_FUNCTION),
              markingExplicitMemoryReferents(EXPLICIT_MEM_CONSTANT),
              markingExplicitInstructionReferents(EXPLICIT_INSN_CONSTANT),
              markingImplicitFunctionReferents(NOT_REACHABLE), // disabled by default because it's slow
              addressAlignment(0), addressNBytes(0), byteOrder(ByteOrder::ORDER_UNSPECIFIED),
              precomputeImplicitFunctionReferents(true)
            {}
    };

    /* Mapping from functions to sets of CFG vertex IDs. */
    typedef Sawyer::Container::Map<Partitioner2::FunctionPtr, std::set<size_t/*vertexId*/> > FunctionToVertexMap;

public:
    static Diagnostics::Facility mlog;

private:
    Settings settings_;                                   // settings that affect behavior
    std::vector<ReasonFlags> intrinsicReachability_;      // intrinsic reachability of each vertex in the CFG
    std::vector<ReasonFlags> reachability_;               // computed reachability of each vertex in the CFG
    FunctionToVertexMap dfReferents_;                     // results from findImplicitFunctionReferents
    Sawyer::Container::Tracker<size_t> scannedVertexIds_; // vertex IDs that have been used for marking intrinsic reachability

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

    template<class S>
    void serialize(S &s, const unsigned version) {
        // Version zero files are no longer supported. I don't think there are two many of these around anyway and supporting
        // backward compatibility for version 0 is not trivial.
        if (version < 1) {
            mlog[Sawyer::Message::FATAL] <<"cannot de-serialized version " <<version <<" object\n";
            ASSERT_not_reachable("aborting due to unsupported old serialization file format");
        }
        s & BOOST_SERIALIZATION_NVP(intrinsicReachability_);
        s & BOOST_SERIALIZATION_NVP(reachability_);
        s & BOOST_SERIALIZATION_NVP(intrinsicReachability_);
        s & BOOST_SERIALIZATION_NVP(reachability_);
        // s & BOOST_SERIALIZATION_NVP(settings_); -- not serialized
        // s & BOOST_SERIALIZATION_NVP(dfReferents_); -- not serialized
        // s & BOOST_SERIALIZATION_NVP(scannedVertexIds_); -- not serialized
    }
#endif

public:
    Reachability() {}

    static void initDiagnostics();

    const Settings& settings() const { return settings_; }
    Settings& settings() { return settings_; }
    void settings(const Settings &s) { settings_ = s; }
    static Sawyer::CommandLine::SwitchGroup commandLineSwitches(Settings &settings /*in,out*/);

    static std::string reasonArgument(Reason);

    static Sawyer::CommandLine::ValueParser::Ptr reasonParser(ReasonFlags &storage);

    static std::string reasonArgumentDocumentation();

    static void insertReasonSwitch(Sawyer::CommandLine::SwitchGroup&, const std::string &switchName, ReasonFlags &storage,
                                   Reason dfltArg, const std::string &doc);

    static std::string reasonDocumentation(Reason dflt);

    void clear();

    void clearReachability();

    size_t markStartingPoints(const Partitioner2::PartitionerConstPtr&, MemoryMapPtr map = MemoryMap::Ptr());

    size_t markEntryFunctions(const Partitioner2::PartitionerConstPtr&, ReasonFlags how = PROGRAM_ENTRY_POINT);

    size_t markExportFunctions(const Partitioner2::PartitionerConstPtr&, ReasonFlags how = EXPORTED_FUNCTION);

    size_t markExplicitInstructionReferents(const Partitioner2::PartitionerConstPtr&, const Partitioner2::BasicBlockPtr&,
                                            ReasonFlags how = EXPLICIT_INSN_CONSTANT);

    size_t markExplicitMemoryReferents(const Partitioner2::PartitionerConstPtr&, const MemoryMapPtr&, size_t bytesPerWord = 0,
                                       size_t alignment = 0, ByteOrder::Endianness sex = ByteOrder::ORDER_UNSPECIFIED,
                                       ReasonFlags how = EXPLICIT_MEM_CONSTANT);

    size_t markImplicitFunctionReferents(const Partitioner2::PartitionerConstPtr&, const Partitioner2::FunctionPtr&,
                                         ReasonFlags how = IMPLICIT_FUNC_CONSTANT);

    size_t markSpecifiedVas(const Partitioner2::PartitionerConstPtr&, const std::vector<AddressInterval>&, ReasonFlags);

    size_t intrinsicallyReachable(size_t vertexId, ReasonFlags how);

    template<class ForwardIterator>
    size_t intrinsicallyReachable(ForwardIterator begin, ForwardIterator end, ReasonFlags how) {
        size_t nChanged = 0;
        while (begin != end)
            nChanged += intrinsicallyReachable(*begin++, how);
        return nChanged;
    }

    static bool hasReasons(ReasonFlags reasons,
                           ReasonFlags any = ReasonFlags(), ReasonFlags all = ReasonFlags(), ReasonFlags none = ReasonFlags());
    
    bool isIntrinsicallyReachable(size_t vertexId,
                                  ReasonFlags any = ReasonFlags(), ReasonFlags all = ReasonFlags(),
                                  ReasonFlags none = ReasonFlags()) const;

    bool isReachable(size_t vertexId,
                     ReasonFlags any = ReasonFlags(), ReasonFlags all = ReasonFlags(),
                     ReasonFlags none = ReasonFlags()) const;

    ReasonFlags intrinsicReachability(size_t vertexId) const;
    const std::vector<ReasonFlags>& intrinsicReachability() const;
    ReasonFlags reachability(size_t vertexId) const;
    const std::vector<ReasonFlags>& reachability() const;
    std::vector<size_t> reachableVertices(ReasonFlags any = ReasonFlags(), ReasonFlags all = ReasonFlags(),
                                          ReasonFlags none = ReasonFlags()) const;
    
    size_t propagate(const Partitioner2::PartitionerConstPtr&);
    size_t propagate(const Partitioner2::PartitionerConstPtr&, std::vector<size_t> &changedVertexIds /*in,out*/);
    void iterate(const Partitioner2::PartitionerConstPtr &partitioner);

    static std::set<size_t>
    findExplicitInstructionReferents(const Partitioner2::PartitionerConstPtr&, const Partitioner2::BasicBlockPtr&);

    std::set<size_t>
    findExplicitMemoryReferents(const Partitioner2::PartitionerConstPtr&, const MemoryMapPtr&, size_t bytesPerWord = 0,
                                size_t alignment = 0, ByteOrder::Endianness sex = ByteOrder::ORDER_UNSPECIFIED);

    static std::set<size_t>
    findImplicitFunctionReferents(const Partitioner2::PartitionerConstPtr&, const Partitioner2::FunctionPtr&);

private:
    // Implementation of the "propagate" functions
    size_t propagateImpl(const Partitioner2::PartitionerConstPtr&, std::vector<size_t>*);

    // Resize vectors based on partitioner CFG size
    void resize(const Partitioner2::PartitionerConstPtr&);

    // Run findImplicitFunctionReferents on all (or specified) functions in parallel and cache the results
    void cacheAllImplicitFunctionReferents(const Partitioner2::PartitionerConstPtr&);
    void cacheImplicitFunctionReferents(const Partitioner2::PartitionerConstPtr&, const std::set<Partitioner2::FunctionPtr>&);

    // Do the marking part of the "iterate" function.
    size_t iterationMarking(const Partitioner2::PartitionerConstPtr&, const std::vector<size_t> &vertexIds);
};

} // namespace
} // namespace

// Class versions must be at global scope
BOOST_CLASS_VERSION(Rose::BinaryAnalysis::Reachability, 1);

#endif
#endif