Variables.h

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

#include <Rose/BinaryAnalysis/InstructionSemantics/BaseSemantics/Types.h>
#include <Rose/BinaryAnalysis/InstructionSemantics/BaseSemantics/MemoryCellState.h>
#include <Rose/BinaryAnalysis/Partitioner2/BasicTypes.h>
#include <Rose/BinaryAnalysis/SymbolicExpr.h>

#include <Sawyer/IntervalMap.h>
#include <Sawyer/Message.h>
#include <Sawyer/Optional.h>
#include <Sawyer/Set.h>

#include <boost/serialization/access.hpp>
#include <boost/serialization/split_member.hpp>

namespace Rose {
namespace BinaryAnalysis {

namespace Variables {

// Basic types

typedef Sawyer::Container::Set<rose_addr_t> AddressSet;

typedef std::map<int64_t /*offset*/, AddressSet> OffsetToAddresses;

typedef std::map<rose_addr_t /*globalVa*/, AddressSet /*insns*/> AddressToAddresses;

typedef Sawyer::Container::Interval<int64_t> OffsetInterval;

// Global variables

extern Sawyer::Message::Facility mlog;

// Global utilities

void initDiagnostics();

std::string offsetStr(int64_t offset);

std::string sizeStr(uint64_t size);

// Base class for variable descriptors

class BaseVariable {
    rose_addr_t maxSizeBytes_ = 0;                  // maximum possible size of this variable in bytes
    AddressSet insnVas_;                            // instructions where the variable was detected that reference the variable
    InstructionSemantics::BaseSemantics::InputOutputPropertySet ioProperties_; 
    std::string name_;                              // optional variable name

#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(maxSizeBytes_);
        s & BOOST_SERIALIZATION_NVP(insnVas_);
        s & BOOST_SERIALIZATION_NVP(ioProperties_);
        s & BOOST_SERIALIZATION_NVP(name_);
    }
#endif
    
protected:
    BaseVariable();

    BaseVariable(size_t maxSizeBytes, const AddressSet &definingInstructionVas, const std::string &name);

public:
    BaseVariable(const BaseVariable&);
    ~BaseVariable();

public:
    rose_addr_t maxSizeBytes() const;
    void maxSizeBytes(rose_addr_t size);
    const AddressSet& definingInstructionVas() const;
    AddressSet& definingInstructionVas();
    void definingInstructionVas(const AddressSet &vas);
    const InstructionSemantics::BaseSemantics::InputOutputPropertySet& ioProperties() const;
    InstructionSemantics::BaseSemantics::InputOutputPropertySet& ioProperties();
    void ioProperties(const InstructionSemantics::BaseSemantics::InputOutputPropertySet &set);
    const std::string& name() const;
    void name(const std::string &s);
};

// Local variable descriptors

class StackVariable: public BaseVariable {
public:
    enum class Purpose {
        RETURN_ADDRESS,                                 
        FRAME_POINTER,                                  
        SPILL_AREA,                                     
        NORMAL,                                         
        UNKNOWN,                                        
        OTHER                                           
    };

    struct Boundary {
        int64_t frameOffset = 0;                        
        AddressSet definingInsns;                       
        Purpose purpose = Purpose::UNKNOWN;             
    };

    using Boundaries = std::vector<Boundary>;

private:
    Partitioner2::FunctionPtr function_;            // function in which local variable exists
    int64_t frameOffset_ = 0;                       // offset where variable is located in the function's stack frame
    Purpose purpose_ = Purpose::UNKNOWN;

#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_NVP(BaseVariable);
        s & BOOST_SERIALIZATION_NVP(function_);
        s & BOOST_SERIALIZATION_NVP(frameOffset_);
        if (version >= 1)
            s & BOOST_SERIALIZATION_NVP(purpose_);
    }
#endif
        
public:
    StackVariable();

    StackVariable(const Partitioner2::FunctionPtr&, int64_t frameOffset, rose_addr_t maxSizeBytes, Purpose,
                  const AddressSet &definingInstructionVas = AddressSet(), const std::string &name = "");

    StackVariable(const StackVariable&);
    ~StackVariable();

    Partitioner2::FunctionPtr function() const;
    void function(const Partitioner2::FunctionPtr&);
    int64_t frameOffset() const;
    void frameOffset(int64_t offset);
    Purpose purpose() const;
    void purpose(Purpose p);
    const std::string& setDefaultName();

    bool operator==(const StackVariable &other) const;
    bool operator!=(const StackVariable &other) const;
    OffsetInterval interval() const;

    static Boundary& insertBoundary(Boundaries& /*in,out*/, int64_t frameOffset, rose_addr_t insnVa);

    void print(std::ostream&) const;
    std::string toString() const;
    friend std::ostream& operator<<(std::ostream&, const Rose::BinaryAnalysis::Variables::StackVariable&);
};

using StackVariables = Sawyer::Container::IntervalMap<OffsetInterval, StackVariable>;

void print(const StackVariables&, const Partitioner2::Partitioner&, std::ostream &out, const std::string &prefix = "");

// Global variable descriptors

class GlobalVariable: public BaseVariable {
    rose_addr_t address_ = 0;                           // starting (lowest) virtual address

#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_NVP(BaseVariable);
        s & BOOST_SERIALIZATION_NVP(address_);
    }
#endif
    
public:
    GlobalVariable();

    GlobalVariable(rose_addr_t startingAddress, rose_addr_t maxSizeBytes,
                   const AddressSet &definingInstructionVas = AddressSet(), const std::string &name = "");

    ~GlobalVariable();

    rose_addr_t address() const;
    void address(rose_addr_t va);
    const std::string& setDefaultName();

    bool operator==(const GlobalVariable &other) const;
    bool operator!=(const GlobalVariable &other) const;
    AddressInterval interval() const;

    void print(std::ostream&) const;
    std::string toString() const;
    friend std::ostream& operator<<(std::ostream&, const Rose::BinaryAnalysis::Variables::GlobalVariable&);
};

typedef Sawyer::Container::IntervalMap<AddressInterval, GlobalVariable> GlobalVariables;

void print(const GlobalVariables&,const Partitioner2::Partitioner&, std::ostream &out, const std::string &prefix = "");

// StackFrame

struct StackFrame {
    enum Direction {
        GROWS_UP,                                       
        GROWS_DOWN                                      
    };

    Direction growthDirection = GROWS_DOWN;             
    RegisterDescriptor framePointerRegister;            
    Sawyer::Optional<int64_t> maxOffset;                
    Sawyer::Optional<int64_t> minOffset;                
    Sawyer::Optional<uint64_t> size;                    
    std::string rule;                                   
};

// Analyzer

class VariableFinder: public Sawyer::SharedObject {
public:
    struct Settings {};

    using Ptr = VariableFinderPtr;

private:
    Settings settings_;

protected:
    explicit VariableFinder(const Settings&);
public:
    ~VariableFinder();

public:
    static Ptr instance(const Settings &settings = Settings());

    const Settings& settings() const { return settings_; }
    Settings& settings() { return settings_; }
    StackVariables findStackVariables(const Partitioner2::Partitioner&, const Partitioner2::FunctionPtr&);
    StackVariables findStackVariables(const Partitioner2::Partitioner&, SgAsmInstruction*);
    GlobalVariables findGlobalVariables(const Partitioner2::Partitioner&);

    void evict(const Partitioner2::FunctionPtr&);
    void evict(const Partitioner2::Partitioner&);
    bool isCached(const Partitioner2::FunctionPtr&);

    StackFrame detectFrameAttributes(const Partitioner2::Partitioner&, const Partitioner2::FunctionPtr&);

    void initializeFrameBoundaries(const StackFrame&, const Partitioner2::Partitioner&, const Partitioner2::FunctionPtr&,
                                   StackVariable::Boundaries &boundaries /*in,out*/);

#if 0 // [Robb Matzke 2021-10-27]

    OffsetInterval referencedFrameArea(const Partitioner2::Partitioner&,
                                       const InstructionSemantics::BaseSemantics::RiscOperatorsPtr&,
                                       const SymbolicExpr::Ptr &address, size_t nBytes);
#endif

    std::set<int64_t> findFrameOffsets(const StackFrame&, const Partitioner2::Partitioner&, SgAsmInstruction*);

    Partitioner2::FunctionPtr functionForInstruction(const Partitioner2::Partitioner&, SgAsmInstruction*);

    AddressToAddresses findGlobalVariableVas(const Partitioner2::Partitioner&);

    std::set<rose_addr_t> findConstants(const SymbolicExpr::Ptr&);

    std::set<rose_addr_t> findConstants(SgAsmInstruction*);

    std::set<SymbolicExpr::Ptr> getMemoryAddresses(const InstructionSemantics::BaseSemantics::MemoryCellStatePtr&);

    std::set<rose_addr_t> findAddressConstants(const InstructionSemantics::BaseSemantics::MemoryCellStatePtr&);

#if 0 // [Robb Matzke 2021-10-27]

    InstructionSemantics::BaseSemantics::SValuePtr
    symbolicAddress(const Partitioner2::Partitioner&, const StackVariable&,
                    const InstructionSemantics::BaseSemantics::RiscOperatorsPtr&);
#endif

    void removeOutliers(const StackFrame&, const Partitioner2::Partitioner&, const Partitioner2::FunctionPtr&,
                        StackVariable::Boundaries &sortedBoundaries /*in,out*/);
};

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

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

#endif
#endif