ROSE 0.11.145.147
ConcreteSemantics.h
1#ifndef ROSE_BinaryAnalysis_InstructionSemantics_ConcreteSemantics_H
2#define ROSE_BinaryAnalysis_InstructionSemantics_ConcreteSemantics_H
3#include <featureTests.h>
4#ifdef ROSE_ENABLE_BINARY_ANALYSIS
5#include <Rose/BinaryAnalysis/BasicTypes.h>
6
7#include <Rose/BinaryAnalysis/InstructionSemantics/BaseSemantics.h>
8#include <Rose/BinaryAnalysis/MemoryMap.h>
9
10#include <Sawyer/BitVector.h>
11
12namespace Rose {
13namespace BinaryAnalysis {
14namespace InstructionSemantics {
15
20namespace ConcreteSemantics {
21
23// Value type
25
28
30typedef BaseSemantics::Formatter Formatter; // we might extend this in the future
31
40public:
43
45 using Ptr = SValuePtr;
46
47protected:
49
51 // Real constructors
52protected:
53 explicit SValue(size_t nbits);
54 SValue(size_t nbits, uint64_t number);
55
57 // Static allocating constructors
58public:
61
66 static SValuePtr instance(size_t nbits);
67
69 static SValuePtr instance(size_t nbits, uint64_t value);
70
72 // Virtual allocating constructors
73public:
74 virtual BaseSemantics::SValuePtr undefined_(size_t nbits) const override;
75 virtual BaseSemantics::SValuePtr unspecified_(size_t nbits) const override;
76 virtual BaseSemantics::SValuePtr bottom_(size_t nbits) const override;
77 virtual BaseSemantics::SValuePtr number_(size_t nbits, uint64_t value) const override;
78 virtual BaseSemantics::SValuePtr boolean_(bool value) const override;
79 virtual BaseSemantics::SValuePtr copy(size_t new_width=0) const override;
80
83 const SmtSolverPtr&) const override;
84
86 // Dynamic pointer casts
87public:
90
92 // Override virtual methods...
93public:
94 virtual void hash(Combinatorics::Hasher&) const override;
95 virtual bool isBottom() const override;
96 virtual void print(std::ostream&, BaseSemantics::Formatter&) const override;
97
99 // Override legacy virtual methods. These snake_case names may eventually go away, but for now they're the ones you should
100 // override. Be sure to use "override" in your own code in order to be notified when we finally remove these.
101public:
102 // See mayEqual
103 virtual bool may_equal(const BaseSemantics::SValuePtr &other,
104 const SmtSolverPtr &solver = SmtSolverPtr()) const override;
105
106 // See mustEqual
107 virtual bool must_equal(const BaseSemantics::SValuePtr &other,
108 const SmtSolverPtr &solver = SmtSolverPtr()) const override;
109
110 // See nBits
111 virtual void set_width(size_t nbits) override;
112
113 // See isConcrete
114 virtual bool is_number() const override {
115 return true;
116 }
117
118 // See toUnsigned and toSigned
119 virtual uint64_t get_number() const override;
120
122 // Additional methods first declared in this class...
123public:
127 virtual const Sawyer::Container::BitVector& bits() const { return bits_; }
128 virtual void bits(const Sawyer::Container::BitVector&);
130};
131
132
134// Register State
136
138typedef BaseSemantics::RegisterStateGenericPtr RegisterStatePtr;
139
140
142// Memory State
144
146typedef boost::shared_ptr<class MemoryState> MemoryStatePtr;
147
153public:
156
159
160private:
161 MemoryMap::Ptr map_;
162 rose_addr_t pageSize_;
163
165 // Real constructors
166protected:
167 explicit MemoryState(const BaseSemantics::SValuePtr &addrProtoval, const BaseSemantics::SValuePtr &valProtoval);
168 MemoryState(const MemoryState &other);
169
171 // Static allocating constructors
172public:
176 static MemoryStatePtr instance(const BaseSemantics::SValuePtr &addrProtoval, const BaseSemantics::SValuePtr &valProtoval);
177
183
185 // Virtual constructors
186public:
192 const BaseSemantics::SValuePtr &valProtoval) const override;
193
199 virtual BaseSemantics::MemoryStatePtr clone() const override;
200
202 // Dynamic pointer casts
203public:
207
209 // Methods we inherited
210public:
211 virtual void clear() override;
212
214 BaseSemantics::RiscOperators *valOps) const override;
215
216 virtual void print(std::ostream&, Formatter&) const override;
217
220 BaseSemantics::RiscOperators *valOps) override;
221
224 BaseSemantics::RiscOperators *valOps) override;
225
226 virtual void writeMemory(const BaseSemantics::SValuePtr &addr, const BaseSemantics::SValuePtr &value,
228
230 BaseSemantics::RiscOperators *valOps) override;
231
232protected:
233 BaseSemantics::SValuePtr readOrPeekMemory(const BaseSemantics::SValuePtr &addr,
234 const BaseSemantics::SValuePtr &dflt,
237 bool allowSideEffects);
238
240 // Methods first declared in this class
241public:
243 const MemoryMap::Ptr memoryMap() const { return map_; }
244
251
258 rose_addr_t pageSize() const { return pageSize_; }
259 void pageSize(rose_addr_t nBytes);
266 void allocatePage(rose_addr_t va);
267
268};
269
270
272// Complete semantic state
274
276typedef BaseSemantics::StatePtr StatePtr;
277
278
280// RISC operators
282
284typedef boost::shared_ptr<class RiscOperators> RiscOperatorsPtr;
285
304public:
307
310
312 // Real constructors
313protected:
315
317
319 // Static allocating constructors
320public:
322
328
334
340
342 // Virtual constructors
343public:
345 const SmtSolverPtr &solver = SmtSolverPtr()) const override;
346
348 const SmtSolverPtr &solver = SmtSolverPtr()) const override;
349
351 // Dynamic pointer casts
352public:
356
358 // New methods for constructing values, so we don't have to write so many SValue::promote calls in the RiscOperators
359 // implementations.
360protected:
361 SValuePtr svalueNumber(size_t nbits, uint64_t value);
362 SValuePtr svalueNumber(const Sawyer::Container::BitVector&);
363 SValuePtr svalueBoolean(bool b);
364 SValuePtr svalueZero(size_t nbits);
365
367 // Override methods from base class. These are the RISC operators that are invoked by a Dispatcher.
368public:
369 virtual void interrupt(int majr, int minr) override;
371 const BaseSemantics::SValuePtr &b_) override;
373 const BaseSemantics::SValuePtr &b_) override;
375 const BaseSemantics::SValuePtr &b_) override;
378 size_t begin_bit, size_t end_bit) override;
380 const BaseSemantics::SValuePtr &b_) override;
384 const BaseSemantics::SValuePtr &sa_) override;
386 const BaseSemantics::SValuePtr &sa_) override;
388 const BaseSemantics::SValuePtr &sa_) override;
390 const BaseSemantics::SValuePtr &sa_) override;
392 const BaseSemantics::SValuePtr &sa_) override;
395 const BaseSemantics::SValuePtr &a_,
396 const BaseSemantics::SValuePtr &b_,
397 IteStatus&) override;
398 virtual BaseSemantics::SValuePtr unsignedExtend(const BaseSemantics::SValuePtr &a_, size_t new_width) override;
399 virtual BaseSemantics::SValuePtr signExtend(const BaseSemantics::SValuePtr &a_, size_t new_width) override;
401 const BaseSemantics::SValuePtr &b_) override;
403 const BaseSemantics::SValuePtr &b_,
404 const BaseSemantics::SValuePtr &c_,
405 BaseSemantics::SValuePtr &carry_out/*out*/) override;
408 const BaseSemantics::SValuePtr &b_) override;
410 const BaseSemantics::SValuePtr &b_) override;
412 const BaseSemantics::SValuePtr &b_) override;
414 const BaseSemantics::SValuePtr &b_) override;
416 const BaseSemantics::SValuePtr &b_) override;
418 const BaseSemantics::SValuePtr &b_) override;
419
422 const BaseSemantics::SValuePtr &dflt) override;
424 SgAsmFloatType*) override;
426 SgAsmFloatType*) override;
428 SgAsmFloatType*) override;
430
432 const BaseSemantics::SValuePtr &addr,
433 const BaseSemantics::SValuePtr &dflt,
434 const BaseSemantics::SValuePtr &cond) override;
436 const BaseSemantics::SValuePtr &addr,
437 const BaseSemantics::SValuePtr &dflt) override;
438 virtual void writeMemory(RegisterDescriptor segreg,
439 const BaseSemantics::SValuePtr &addr,
440 const BaseSemantics::SValuePtr &data,
441 const BaseSemantics::SValuePtr &cond) override;
442
443protected:
444 // handles readMemory and peekMemory
445 BaseSemantics::SValuePtr readOrPeekMemory(RegisterDescriptor segreg, const BaseSemantics::SValuePtr &address,
446 const BaseSemantics::SValuePtr &dflt, bool allowSideEffects);
447
448 // Convert expression to double
449 double exprToDouble(const BaseSemantics::SValuePtr &expr, SgAsmFloatType*);
450
451 // Convert double to expression
452 BaseSemantics::SValuePtr doubleToExpr(double d, SgAsmFloatType*);
453};
454
455} // namespace
456} // namespace
457} // namespace
458} // namespace
459
460#endif
461#endif
Base class for most instruction semantics RISC operators.
virtual SmtSolverPtr solver() const
Property: Satisfiability module theory (SMT) solver.
virtual SValuePtr protoval() const
Property: Prototypical semantic value.
Base class for semantics machine states.
Definition State.h:41
static MemoryStatePtr instance(const MemoryStatePtr &other)
Instantiates a new deep copy of an existing state.
virtual void hash(Combinatorics::Hasher &, BaseSemantics::RiscOperators *addrOps, BaseSemantics::RiscOperators *valOps) const override
Calculate a hash for this memory state.
static MemoryStatePtr instance(const BaseSemantics::SValuePtr &addrProtoval, const BaseSemantics::SValuePtr &valProtoval)
Instantiates a new memory state having specified prototypical value.
void memoryMap(const MemoryMap::Ptr &, Sawyer::Optional< unsigned > padAccess=Sawyer::Nothing())
Set memory map.
void allocatePage(rose_addr_t va)
Allocate a page of memory.
virtual BaseSemantics::SValuePtr readMemory(const BaseSemantics::SValuePtr &addr, const BaseSemantics::SValuePtr &dflt, BaseSemantics::RiscOperators *addrOps, BaseSemantics::RiscOperators *valOps) override
Read a value from memory.
static MemoryStatePtr promote(const BaseSemantics::MemoryStatePtr &)
Recasts a base pointer to a concrete memory state.
virtual BaseSemantics::MemoryStatePtr clone() const override
Virtual copy constructor.
const MemoryMap::Ptr memoryMap() const
Returns the memory map.
virtual BaseSemantics::SValuePtr peekMemory(const BaseSemantics::SValuePtr &addr, const BaseSemantics::SValuePtr &dflt, BaseSemantics::RiscOperators *addrOps, BaseSemantics::RiscOperators *valOps) override
Read a value from memory without side effects.
virtual void writeMemory(const BaseSemantics::SValuePtr &addr, const BaseSemantics::SValuePtr &value, BaseSemantics::RiscOperators *addrOps, BaseSemantics::RiscOperators *valOps) override
Write a value to memory.
void pageSize(rose_addr_t nBytes)
Size of each page of memory.
virtual bool merge(const BaseSemantics::MemoryStatePtr &other, BaseSemantics::RiscOperators *addrOps, BaseSemantics::RiscOperators *valOps) override
Merge memory states for data flow analysis.
virtual BaseSemantics::MemoryStatePtr create(const BaseSemantics::SValuePtr &addrProtoval, const BaseSemantics::SValuePtr &valProtoval) const override
Virtual constructor.
virtual void print(std::ostream &, Formatter &) const override
Print a memory state to more than one line of output.
Defines RISC operators for the ConcreteSemantics domain.
virtual BaseSemantics::SValuePtr fpMultiply(const BaseSemantics::SValuePtr &a, const BaseSemantics::SValuePtr &b, SgAsmFloatType *) override
Multiply two floating-point values.
virtual BaseSemantics::SValuePtr mostSignificantSetBit(const BaseSemantics::SValuePtr &a_) override
Returns position of most significant set bit; zero when no bits are set.
virtual BaseSemantics::SValuePtr unsignedDivide(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &b_) override
Divides two unsigned values.
virtual BaseSemantics::SValuePtr fpToInteger(const BaseSemantics::SValuePtr &fpValue, SgAsmFloatType *fpType, const BaseSemantics::SValuePtr &dflt) override
Construct an integer value from a floating-point value.
virtual BaseSemantics::SValuePtr rotateLeft(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &sa_) override
Rotate bits to the left.
virtual BaseSemantics::SValuePtr invert(const BaseSemantics::SValuePtr &a_) override
One's complement.
static RiscOperatorsPtr promote(const BaseSemantics::RiscOperatorsPtr &)
Run-time promotion of a base RiscOperators pointer to concrete operators.
virtual BaseSemantics::RiscOperatorsPtr create(const BaseSemantics::SValuePtr &protoval, const SmtSolverPtr &solver=SmtSolverPtr()) const override
Virtual allocating constructor.
virtual BaseSemantics::SValuePtr signedModulo(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &b_) override
Calculates modulo with signed values.
virtual BaseSemantics::SValuePtr concat(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &b_) override
Concatenates the bits of two values.
virtual void interrupt(int majr, int minr) override
Unconditionally raise an interrupt.
virtual BaseSemantics::SValuePtr extract(const BaseSemantics::SValuePtr &a_, size_t begin_bit, size_t end_bit) override
Extracts bits from a value.
virtual BaseSemantics::SValuePtr signExtend(const BaseSemantics::SValuePtr &a_, size_t new_width) override
Sign extends a value.
static RiscOperatorsPtr instanceFromProtoval(const BaseSemantics::SValuePtr &protoval, const SmtSolverPtr &solver=SmtSolverPtr())
Allocating constructor.
virtual BaseSemantics::SValuePtr signedMultiply(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &b_) override
Multiplies two signed values.
virtual BaseSemantics::SValuePtr leastSignificantSetBit(const BaseSemantics::SValuePtr &a_) override
Returns position of least significant set bit; zero when no bits are set.
virtual void writeMemory(RegisterDescriptor segreg, const BaseSemantics::SValuePtr &addr, const BaseSemantics::SValuePtr &data, const BaseSemantics::SValuePtr &cond) override
Writes a value to memory.
virtual BaseSemantics::SValuePtr negate(const BaseSemantics::SValuePtr &a_) override
Two's complement.
virtual BaseSemantics::SValuePtr or_(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &b_) override
Computes bit-wise OR of two values.
virtual BaseSemantics::SValuePtr fpAdd(const BaseSemantics::SValuePtr &a, const BaseSemantics::SValuePtr &b, SgAsmFloatType *) override
Add two floating-point values.
virtual BaseSemantics::SValuePtr fpSubtract(const BaseSemantics::SValuePtr &a, const BaseSemantics::SValuePtr &b, SgAsmFloatType *) override
Subtract one floating-point value from another.
virtual BaseSemantics::RiscOperatorsPtr create(const BaseSemantics::StatePtr &, const SmtSolverPtr &solver=SmtSolverPtr()) const override
Virtual allocating constructor.
virtual BaseSemantics::SValuePtr unsignedExtend(const BaseSemantics::SValuePtr &a_, size_t new_width) override
Extend (or shrink) operand a so it is nbits wide by adding or removing high-order bits.
virtual BaseSemantics::SValuePtr shiftRight(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &sa_) override
Returns arg shifted right logically (no sign bit).
virtual BaseSemantics::SValuePtr xor_(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &b_) override
Computes bit-wise XOR of two values.
virtual BaseSemantics::SValuePtr peekMemory(RegisterDescriptor segreg, const BaseSemantics::SValuePtr &addr, const BaseSemantics::SValuePtr &dflt) override
Read memory without side effects.
virtual BaseSemantics::SValuePtr shiftRightArithmetic(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &sa_) override
Returns arg shifted right arithmetically (with sign bit).
virtual BaseSemantics::SValuePtr signedDivide(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &b_) override
Divides two signed values.
static RiscOperatorsPtr instanceFromState(const BaseSemantics::StatePtr &, const SmtSolverPtr &solver=SmtSolverPtr())
Allocating constructor.
virtual BaseSemantics::SValuePtr equalToZero(const BaseSemantics::SValuePtr &a_) override
Determines whether a value is equal to zero.
virtual BaseSemantics::SValuePtr iteWithStatus(const BaseSemantics::SValuePtr &sel_, const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &b_, IteStatus &) override
If-then-else with status.
virtual BaseSemantics::SValuePtr add(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &b_) override
Adds two integers of equal size.
virtual BaseSemantics::SValuePtr fpRoundTowardZero(const BaseSemantics::SValuePtr &a, SgAsmFloatType *) override
Round toward zero.
virtual BaseSemantics::SValuePtr and_(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &b_) override
Computes bit-wise AND of two values.
virtual BaseSemantics::SValuePtr readMemory(RegisterDescriptor segreg, const BaseSemantics::SValuePtr &addr, const BaseSemantics::SValuePtr &dflt, const BaseSemantics::SValuePtr &cond) override
Reads a value from memory.
virtual BaseSemantics::SValuePtr unsignedModulo(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &b_) override
Calculates modulo with unsigned values.
virtual BaseSemantics::SValuePtr fpFromInteger(const BaseSemantics::SValuePtr &intValue, SgAsmFloatType *) override
Construct a floating-point value from an integer value.
virtual BaseSemantics::SValuePtr rotateRight(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &sa_) override
Rotate bits to the right.
virtual BaseSemantics::SValuePtr addWithCarries(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &b_, const BaseSemantics::SValuePtr &c_, BaseSemantics::SValuePtr &carry_out) override
Add two values of equal size and a carry bit.
static RiscOperatorsPtr instanceFromRegisters(const RegisterDictionaryPtr &, const SmtSolverPtr &solver=SmtSolverPtr())
Allocating constructor.
virtual BaseSemantics::SValuePtr shiftLeft(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &sa_) override
Returns arg shifted left.
virtual BaseSemantics::SValuePtr unsignedMultiply(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &b_) override
Multiply two unsigned values.
Type of values manipulated by the concrete domain.
virtual const Sawyer::Container::BitVector & bits() const
Returns the bit vector storing the concrete value.
static SValuePtr instance(size_t nbits)
Instantiate a new undefined value of specified width.
virtual BaseSemantics::SValuePtr number_(size_t nbits, uint64_t value) const override
Create a new concrete semantic value.
virtual BaseSemantics::SValuePtr unspecified_(size_t nbits) const override
Create a new unspecified semantic value.
virtual uint64_t get_number() const override
Virtual API.
static SValuePtr instance()
Instantiate a new prototypical value.
virtual void bits(const Sawyer::Container::BitVector &)
Returns the bit vector storing the concrete value.
virtual bool may_equal(const BaseSemantics::SValuePtr &other, const SmtSolverPtr &solver=SmtSolverPtr()) const override
Virtual API.
virtual BaseSemantics::SValuePtr copy(size_t new_width=0) const override
Create a new value from an existing value, changing the width if new_width is non-zero.
virtual bool must_equal(const BaseSemantics::SValuePtr &other, const SmtSolverPtr &solver=SmtSolverPtr()) const override
Virtual API.
virtual void print(std::ostream &, BaseSemantics::Formatter &) const override
Print a value to a stream using default format.
virtual BaseSemantics::SValuePtr bottom_(size_t nbits) const override
Data-flow bottom value.
virtual Sawyer::Optional< BaseSemantics::SValuePtr > createOptionalMerge(const BaseSemantics::SValuePtr &other, const BaseSemantics::MergerPtr &, const SmtSolverPtr &) const override
Possibly create a new value by merging two existing values.
virtual void set_width(size_t nbits) override
Virtual API.
virtual BaseSemantics::SValuePtr boolean_(bool value) const override
Create a new, Boolean value.
static SValuePtr promote(const BaseSemantics::SValuePtr &)
Promote a base value to a SymbolicSemantics value.
virtual bool isBottom() const override
Determines whether a value is a data-flow bottom.
static SValuePtr instance(size_t nbits, uint64_t value)
Instantiate a new concrete value.
virtual BaseSemantics::SValuePtr undefined_(size_t nbits) const override
Create a new undefined semantic value.
virtual void hash(Combinatorics::Hasher &) const override
Hash this semantic value.
Describes (part of) a physical CPU register.
Represents no value.
Definition Optional.h:36
Holds a value or nothing.
Definition Optional.h:56
Reference-counting intrusive smart pointer.
Floating point types.
boost::shared_ptr< RiscOperators > RiscOperatorsPtr
Shared-ownership pointer to a RISC operators object.
boost::shared_ptr< MemoryState > MemoryStatePtr
Shared-ownership pointer to a memory state.
boost::shared_ptr< class RegisterStateGeneric > RegisterStateGenericPtr
Shared-ownership pointer to generic register states.
boost::shared_ptr< class MemoryState > MemoryStatePtr
Shared-ownership pointer to a concrete memory state.
boost::shared_ptr< class RiscOperators > RiscOperatorsPtr
Shared-ownership pointer to concrete RISC operations.
BaseSemantics::Formatter Formatter
Formatter for symbolic values.
Sawyer::SharedPointer< class SValue > SValuePtr
Smart-ownership pointer to a concrete semantic value.
std::shared_ptr< SmtSolver > SmtSolverPtr
Reference counting pointer.
The ROSE library.