ROSE 0.11.145.147
IntervalSemantics.h
1#ifndef ROSE_BinaryAnalysis_InstructionSemantics_IntervalSemantics_H
2#define ROSE_BinaryAnalysis_InstructionSemantics_IntervalSemantics_H
3#include <featureTests.h>
4#ifdef ROSE_ENABLE_BINARY_ANALYSIS
5
6#include <Rose/BinaryAnalysis/BasicTypes.h>
7#include <Rose/BinaryAnalysis/InstructionSemantics/BaseSemantics/MemoryCellList.h>
8#include <Rose/BinaryAnalysis/InstructionSemantics/BaseSemantics/SValue.h>
9
10#include <Sawyer/IntervalSet.h>
11
12namespace Rose {
13namespace BinaryAnalysis {
14namespace InstructionSemantics {
15
17namespace IntervalSemantics {
18
19/* Single contiguous interval. */
21
24
26// Semantic values
28
31
34public:
37
39 using Ptr = SValuePtr;
40
41protected:
42 Intervals intervals_;
43 bool isBottom_;
44
45protected:
46 // Protected constructors. See base class and public members for documentation
47 explicit SValue(size_t nbits);
48 SValue(size_t nbits, uint64_t number);
49 SValue(size_t nbits, uint64_t v1, uint64_t v2);
50 SValue(size_t nbits, const Intervals &intervals);
51
53 // Static allocating constructors
54public:
57
59 static SValuePtr instance_bottom(size_t nbits);
60
63 static SValuePtr instance_undefined(size_t nbits);
64
69 static SValuePtr instance_unspecified(size_t nbits);
70
72 static SValuePtr instance_integer(size_t nbits, uint64_t number);
73
75 static SValuePtr instance_intervals(size_t nbits, const Intervals &intervals);
76
78 static SValuePtr instance_hull(size_t nbits, uint64_t v1, uint64_t v2);
79
82
84 static SValuePtr instance_from_bits(size_t nbits, uint64_t possible_bits);
85
88
90 // Virtual allocating constructors inherited from the super class
91public:
92 virtual BaseSemantics::SValuePtr bottom_(size_t nbits) const override;
93 virtual BaseSemantics::SValuePtr undefined_(size_t nbits) const override;
94 virtual BaseSemantics::SValuePtr unspecified_(size_t nbits) const override;
95 virtual BaseSemantics::SValuePtr number_(size_t nbits, uint64_t number) const override;
96 virtual BaseSemantics::SValuePtr copy(size_t new_width=0) const override;
97
100 const SmtSolverPtr&) const override;
101
103 // Virtual allocating constructors first defined at this level of the class hierarchy
104public:
106 virtual SValuePtr create(size_t nbits, uint64_t v1, uint64_t v2);
107
110 virtual SValuePtr create(size_t nbits, const Intervals&);
111
115 virtual SValuePtr create_from_bits(size_t nbits, uint64_t possible_bits);
116
118 // Override virtual methods...
119public:
120 virtual void hash(Combinatorics::Hasher&) const override;
121 virtual bool isBottom() const override;
122 virtual void print(std::ostream &output, BaseSemantics::Formatter&) const override;
123
125 // Override legacy methods. Override these, but always call the camelCase versions from BaseSemantics::SValue. These
126 // snake_case names may eventually go away, so be sure to make good use of "override" in your own code.
127public:
128 // See mayEqual
129 virtual bool may_equal(const BaseSemantics::SValuePtr &other,
130 const SmtSolverPtr &solver = SmtSolverPtr()) const override;
131
132 // See mustEqual
133 virtual bool must_equal(const BaseSemantics::SValuePtr &other,
134 const SmtSolverPtr &solver = SmtSolverPtr()) const override;
135
136 // See isConcrete
137 virtual bool is_number() const override;
138
139 // See toUnsigned and toSigned
140 virtual uint64_t get_number() const override;
141
143 // Additional methods introduced at this level of the class hierarchy
144public:
146 const Intervals& get_intervals() const;
147
150
152 uint64_t possible_bits() const;
153};
154
155
157// Register state
159
161typedef BaseSemantics::RegisterStateGenericPtr RegisterStateGenericPtr;
162
163
165// Memory state
167
169typedef boost::shared_ptr<class MemoryState> MemoryStatePtr;
170
182public:
185
188
190 // Real constructors
191protected:
193 MemoryState(const BaseSemantics::SValuePtr &addrProtoval, const BaseSemantics::SValuePtr &valProtoval);
194 MemoryState(const MemoryState &);
195
197 // Static allocating constructors
198public:
201
204 static MemoryStatePtr instance(const BaseSemantics::SValuePtr &addrProtoval, const BaseSemantics::SValuePtr &valProtoval);
205
207 // Virtual constructors
208public:
209 virtual BaseSemantics::MemoryStatePtr create(const BaseSemantics::MemoryCellPtr &protocell) const override;
211 const BaseSemantics::SValuePtr &valProtoval) const override;
212 virtual BaseSemantics::MemoryStatePtr clone() const override;
213
215 // Methods we inherited
216public:
223
230
234 virtual void writeMemory(const BaseSemantics::SValuePtr &addr, const BaseSemantics::SValuePtr &value,
236};
237
238
240// Complete state
242
244typedef BaseSemantics::StatePtr StatePtr;
245
246
248// RISC operators
250
252typedef boost::shared_ptr<class RiscOperators> RiscOperatorsPtr;
253
256public:
259
262
264 // Real constructors
265protected:
267
268 explicit RiscOperators(const BaseSemantics::StatePtr&, const SmtSolverPtr&);
269
271 // Static allocating constructors
272public:
276
280 const SmtSolverPtr &solver = SmtSolverPtr());
281
285
287 // Virtual constructors
288public:
290 const SmtSolverPtr &solver = SmtSolverPtr()) const override;
291
293 const SmtSolverPtr &solver = SmtSolverPtr()) const override;
294
296 // Dynamic pointer casts
297public:
301
303 // Methods first introduced at this level of the class hierarchy.
304public:
305
308 virtual SValuePtr svalue_from_bits(size_t nbits, uint64_t possible_bits);
309
312 virtual SValuePtr svalue_from_intervals(size_t nbits, const Intervals &intervals);
313
315 // Override methods from base class. These are the RISC operators that are invoked by a Dispatcher.
316public:
318 const BaseSemantics::SValuePtr &b_) override;
320 const BaseSemantics::SValuePtr &b_) override;
322 const BaseSemantics::SValuePtr &b_) override;
325 size_t begin_bit, size_t end_bit) override;
327 const BaseSemantics::SValuePtr &b_) override;
331 const BaseSemantics::SValuePtr &sa_) override;
333 const BaseSemantics::SValuePtr &sa_) override;
335 const BaseSemantics::SValuePtr &sa_) override;
337 const BaseSemantics::SValuePtr &sa_) override;
339 const BaseSemantics::SValuePtr &sa_) override;
342 const BaseSemantics::SValuePtr &a_,
343 const BaseSemantics::SValuePtr &b_,
344 IteStatus&) override;
345 virtual BaseSemantics::SValuePtr unsignedExtend(const BaseSemantics::SValuePtr &a_, size_t new_width) override;
346 virtual BaseSemantics::SValuePtr signExtend(const BaseSemantics::SValuePtr &a_, size_t new_width) override;
348 const BaseSemantics::SValuePtr &b_) override;
350 const BaseSemantics::SValuePtr &b_,
351 const BaseSemantics::SValuePtr &c_,
352 BaseSemantics::SValuePtr &carry_out/*out*/) override;
355 const BaseSemantics::SValuePtr &b_) override;
357 const BaseSemantics::SValuePtr &b_) override;
359 const BaseSemantics::SValuePtr &b_) override;
361 const BaseSemantics::SValuePtr &b_) override;
363 const BaseSemantics::SValuePtr &b_) override;
365 const BaseSemantics::SValuePtr &b_) override;
367 const BaseSemantics::SValuePtr &addr,
368 const BaseSemantics::SValuePtr &dflt,
369 const BaseSemantics::SValuePtr &cond) override;
371 const BaseSemantics::SValuePtr &addr,
372 const BaseSemantics::SValuePtr &dflt) override;
373 virtual void writeMemory(RegisterDescriptor segreg,
374 const BaseSemantics::SValuePtr &addr,
375 const BaseSemantics::SValuePtr &data,
376 const BaseSemantics::SValuePtr &cond) override;
377};
378
379} // namespace
380} // namespace
381} // namespace
382} // namespace
383
384#endif
385#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 BaseSemantics::MemoryCellPtr &protocell)
Instantiate a new memory state with specified prototypical cells and values.
virtual BaseSemantics::SValuePtr peekMemory(const BaseSemantics::SValuePtr &addr, const BaseSemantics::SValuePtr &dflt, BaseSemantics::RiscOperators *addrOps, BaseSemantics::RiscOperators *valOps) override
Read a byte from memory without side effects.
static MemoryStatePtr instance(const BaseSemantics::SValuePtr &addrProtoval, const BaseSemantics::SValuePtr &valProtoval)
Instantiate a new memory state with prototypical value.
virtual BaseSemantics::SValuePtr readMemory(const BaseSemantics::SValuePtr &addr, const BaseSemantics::SValuePtr &dflt, BaseSemantics::RiscOperators *addrOps, BaseSemantics::RiscOperators *valOps) override
Read a byte from memory.
virtual BaseSemantics::MemoryStatePtr create(const BaseSemantics::MemoryCellPtr &protocell) const override
Virtual allocating constructor.
virtual BaseSemantics::MemoryStatePtr clone() const override
Virtual allocating copy constructor.
virtual void writeMemory(const BaseSemantics::SValuePtr &addr, const BaseSemantics::SValuePtr &value, BaseSemantics::RiscOperators *addrOps, BaseSemantics::RiscOperators *valOps) override
Write a byte to memory.
virtual BaseSemantics::MemoryStatePtr create(const BaseSemantics::SValuePtr &addrProtoval, const BaseSemantics::SValuePtr &valProtoval) const override
Virtual allocating constructor.
virtual BaseSemantics::SValuePtr peekMemory(RegisterDescriptor segreg, const BaseSemantics::SValuePtr &addr, const BaseSemantics::SValuePtr &dflt) override
Read memory without side effects.
virtual BaseSemantics::SValuePtr equalToZero(const BaseSemantics::SValuePtr &a_) override
Determines whether a value is equal to zero.
virtual BaseSemantics::SValuePtr shiftRightArithmetic(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &sa_) override
Returns arg shifted right arithmetically (with sign bit).
virtual BaseSemantics::SValuePtr invert(const BaseSemantics::SValuePtr &a_) override
One's complement.
virtual BaseSemantics::SValuePtr shiftRight(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &sa_) override
Returns arg shifted right logically (no sign bit).
virtual BaseSemantics::SValuePtr unsignedDivide(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &b_) override
Divides two unsigned 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 or_(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &b_) override
Computes bit-wise OR of two values.
static RiscOperatorsPtr instanceFromRegisters(const RegisterDictionaryPtr &, const SmtSolverPtr &solver=SmtSolverPtr())
Instantiates a new RiscOperators object and configures it to use semantic values and states that are ...
virtual BaseSemantics::SValuePtr signedDivide(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &b_) override
Divides two signed values.
virtual BaseSemantics::RiscOperatorsPtr create(const BaseSemantics::SValuePtr &protoval, const SmtSolverPtr &solver=SmtSolverPtr()) const override
Virtual allocating constructor.
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 rotateLeft(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &sa_) override
Rotate bits to the left.
virtual BaseSemantics::SValuePtr signedMultiply(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &b_) override
Multiplies two signed values.
virtual BaseSemantics::SValuePtr unsignedModulo(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &b_) override
Calculates modulo with unsigned values.
virtual BaseSemantics::SValuePtr signedModulo(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &b_) override
Calculates modulo with signed values.
virtual BaseSemantics::SValuePtr rotateRight(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &sa_) override
Rotate bits to the right.
virtual BaseSemantics::SValuePtr unsignedMultiply(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &b_) override
Multiply two unsigned values.
static RiscOperatorsPtr instanceFromProtoval(const BaseSemantics::SValuePtr &protoval, const SmtSolverPtr &solver=SmtSolverPtr())
Instantiates a new RiscOperators object with specified prototypical value.
virtual BaseSemantics::SValuePtr xor_(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &b_) override
Computes bit-wise XOR of two values.
virtual BaseSemantics::SValuePtr concat(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &b_) override
Concatenates the bits of two values.
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.
static RiscOperatorsPtr instanceFromState(const BaseSemantics::StatePtr &, const SmtSolverPtr &solver=SmtSolverPtr())
Instantiates a new RiscOperators with specified state.
virtual BaseSemantics::SValuePtr readMemory(RegisterDescriptor segreg, const BaseSemantics::SValuePtr &addr, const BaseSemantics::SValuePtr &dflt, const BaseSemantics::SValuePtr &cond) override
Reads a value from memory.
static RiscOperatorsPtr promote(const BaseSemantics::RiscOperatorsPtr &)
Run-time promotion of a base RiscOperators pointer to interval operators.
virtual BaseSemantics::RiscOperatorsPtr create(const BaseSemantics::StatePtr &, const SmtSolverPtr &solver=SmtSolverPtr()) const override
Virtual allocating constructor.
virtual BaseSemantics::SValuePtr extract(const BaseSemantics::SValuePtr &a_, size_t begin_bit, size_t end_bit) override
Extracts bits from a value.
virtual SValuePtr svalue_from_intervals(size_t nbits, const Intervals &intervals)
Create a new SValue from a set of intervals.
virtual BaseSemantics::SValuePtr and_(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &b_) override
Computes bit-wise AND of two values.
virtual BaseSemantics::SValuePtr signExtend(const BaseSemantics::SValuePtr &a_, size_t new_width) override
Sign extends a value.
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.
virtual BaseSemantics::SValuePtr shiftLeft(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &sa_) override
Returns arg shifted left.
virtual SValuePtr svalue_from_bits(size_t nbits, uint64_t possible_bits)
Create a new SValue from a set of possible bits.
virtual BaseSemantics::SValuePtr add(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &b_) override
Adds two integers of equal size.
virtual BaseSemantics::SValuePtr leastSignificantSetBit(const BaseSemantics::SValuePtr &a_) override
Returns position of least significant set bit; zero when no bits are set.
virtual BaseSemantics::SValuePtr iteWithStatus(const BaseSemantics::SValuePtr &sel_, const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &b_, IteStatus &) override
If-then-else with status.
Type of values manipulated by the IntervalSemantics domain.
static SValuePtr instance_copy(const SValuePtr &)
Instantiate a new copy of an existing value.
static SValuePtr instance_from_bits(size_t nbits, uint64_t possible_bits)
Create a value from a set of possible bits.
static SValuePtr instance_hull(size_t nbits, uint64_t v1, uint64_t v2)
Instantiate a new value that's constrained to be between two unsigned values, inclusive.
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 BaseSemantics::SValuePtr bottom_(size_t nbits) const override
Data-flow bottom value.
virtual SValuePtr create(size_t nbits, const Intervals &)
Construct a ValueType from a rangemap.
static SValuePtr instance_intervals(size_t nbits, const Intervals &intervals)
Instantiate a new value from a set of intervals.
virtual BaseSemantics::SValuePtr unspecified_(size_t nbits) const override
Create a new unspecified semantic value.
static SValuePtr instance_bottom(size_t nbits)
Instantiate a new data-flow-bottom value of specified width.
virtual SValuePtr create(size_t nbits, uint64_t v1, uint64_t v2)
Construct a ValueType that's constrained to be between two unsigned values, inclusive.
virtual bool isBottom() const override
Determines whether a value is a data-flow bottom.
uint64_t possible_bits() const
Returns all possible bits that could be set.
void set_intervals(const Intervals &)
Changes the rangemap stored in the value.
virtual BaseSemantics::SValuePtr undefined_(size_t nbits) const override
Create a new undefined semantic value.
virtual void print(std::ostream &output, BaseSemantics::Formatter &) const override
Print a value to a stream using default format.
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.
static SValuePtr instance()
Instantiate a new prototypical value.
virtual SValuePtr create_from_bits(size_t nbits, uint64_t possible_bits)
Generate ranges from bits.
virtual BaseSemantics::SValuePtr number_(size_t nbits, uint64_t number) const override
Create a new concrete semantic value.
const Intervals & get_intervals() const
Returns the rangemap stored in this value.
static SValuePtr instance_integer(size_t nbits, uint64_t number)
Instantiate a new concrete value of particular width.
virtual void hash(Combinatorics::Hasher &) const override
Hash this semantic value.
virtual bool must_equal(const BaseSemantics::SValuePtr &other, const SmtSolverPtr &solver=SmtSolverPtr()) const override
Virtual API.
static SValuePtr instance_undefined(size_t nbits)
Instantiate a new undefined value of particular width.
static SValuePtr instance_unspecified(size_t nbits)
Instantiate a new unspecified value of specific width.
static SValuePtr promote(const BaseSemantics::SValuePtr &)
Promote a base value to an IntevalSemantics value.
virtual uint64_t get_number() const override
Virtual API.
Describes (part of) a physical CPU register.
A container holding a set of values.
Definition IntervalSet.h:53
Range of values delimited by endpoints.
Definition Interval.h:31
Holds a value or nothing.
Definition Optional.h:56
Reference-counting intrusive smart pointer.
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< MemoryCell > MemoryCellPtr
Shared-ownership pointer to a memory cell.
boost::shared_ptr< class RegisterStateGeneric > RegisterStateGenericPtr
Shared-ownership pointer to generic register states.
Sawyer::Container::IntervalSet< Interval > Intervals
Set of intervals.
boost::shared_ptr< class RiscOperators > RiscOperatorsPtr
Shared-ownership pointer to interval RISC operations.
Sawyer::SharedPointer< class SValue > SValuePtr
Shared-ownership pointer to an interval semantic value.
boost::shared_ptr< class MemoryState > MemoryStatePtr
Shared-ownership pointer to an interval memory state.
std::shared_ptr< SmtSolver > SmtSolverPtr
Reference counting pointer.
The ROSE library.