ROSE  0.11.101.0
SourceAstSemantics.h
1 // Turn instruction semantics into a C source AST
2 #ifndef ROSE_BinaryAnalysis_InstructionSemantics_SourceAstSemantics_H
3 #define ROSE_BinaryAnalysis_InstructionSemantics_SourceAstSemantics_H
4 #include <featureTests.h>
5 #ifdef ROSE_ENABLE_BINARY_ANALYSIS
6 
7 #include <Rose/BinaryAnalysis/BasicTypes.h>
8 #include <Rose/BinaryAnalysis/InstructionSemantics/BaseSemantics/RegisterStateGeneric.h>
9 #include <Rose/BinaryAnalysis/InstructionSemantics/NullSemantics.h>
10 
11 namespace Rose {
12 namespace BinaryAnalysis { // documented elsewhere
13 namespace InstructionSemantics { // documented elsewhere
14 
50 namespace SourceAstSemantics {
51 
53 // Value type
55 
58 
69 public:
72 
74  using Ptr = SValuePtr;
75 
76 protected:
77  static size_t nVariables_;
78  std::string ctext_;
79 
80 protected:
81  // An undefined or unspecified value is a C variable that's not initialized.
82  explicit SValue(size_t nbits);
83 
84  // An integer value, various types depending on width
85  SValue(size_t nbits, uint64_t number);
86 
87  // Copy constructor deep-copies the AST.
88  SValue(const SValue &other);
89 
90 public:
94  static SValuePtr instance() {
95  return SValuePtr(new SValue(1));
96  }
97 
101  static SValuePtr instance_undefined(size_t nbits) {
102  return SValuePtr(new SValue(nbits));
103  }
104 
106  static SValuePtr instance_integer(size_t nbits, uint64_t value) {
107  return SValuePtr(new SValue(nbits, value));
108  }
109 
110 public:
111  virtual BaseSemantics::SValuePtr bottom_(size_t nbits) const override {
112  return instance_undefined(nbits);
113  }
114  virtual BaseSemantics::SValuePtr undefined_(size_t nbits) const override {
115  return instance_undefined(nbits);
116  }
117  virtual BaseSemantics::SValuePtr unspecified_(size_t nbits) const override {
118  return instance_undefined(nbits);
119  }
120  virtual BaseSemantics::SValuePtr number_(size_t nbits, uint64_t value) const override {
121  return instance_integer(nbits, value);
122  }
123  virtual BaseSemantics::SValuePtr boolean_(bool value) const override {
124  return instance_integer(1, value ? 1 : 0);
125  }
126  virtual BaseSemantics::SValuePtr copy(size_t new_width=0) const override {
127  SValuePtr retval(new SValue(*this));
128  if (new_width!=0 && new_width!=retval->nBits())
129  retval->set_width(new_width);
130  return retval;
131  }
134  const SmtSolverPtr&) const override {
135  throw BaseSemantics::NotImplemented("SourceAstSemantics is not suitable for dataflow analysis", NULL);
136  }
137 
138 public:
140  static SValuePtr promote(const BaseSemantics::SValuePtr &v) { // hot
141  SValuePtr retval = v.dynamicCast<SValue>();
142  ASSERT_not_null(retval);
143  return retval;
144  }
145 
146 public:
147  virtual bool isBottom() const override {
148  return false;
149  }
150 
151  virtual void hash(Combinatorics::Hasher&) const override;
152  virtual void print(std::ostream&, BaseSemantics::Formatter&) const override;
153 
154 public:
155  // These are not needed since this domain never tries to compare semantic values.
156  virtual bool may_equal(const BaseSemantics::SValuePtr &other,
157  const SmtSolverPtr &solver = SmtSolverPtr()) const override {
158  ASSERT_not_reachable("no implementation necessary");
159  }
160 
161  virtual bool must_equal(const BaseSemantics::SValuePtr &other,
162  const SmtSolverPtr &solver = SmtSolverPtr()) const override {
163  ASSERT_not_reachable("no implementation necessary");
164  }
165 
166  virtual void set_width(size_t nbits) override {
167  ASSERT_not_reachable("no implementation necessary");
168  }
169 
170  virtual bool is_number() const override {
171  return false;
172  }
173 
174  virtual uint64_t get_number() const override {
175  ASSERT_not_reachable("no implementation necessary");
176  }
177 
178 public:
182  static std::string unsignedTypeNameForSize(size_t nbits);
183  static std::string signedTypeNameForSize(size_t nbits);
186 public:
190  virtual const std::string& ctext() const {
191  return ctext_;
192  }
193  virtual void ctext(const std::string &s) {
194  ctext_ = s;
195  }
197 };
198 
200 // State
202 
203 // No state is necessary for this domain because all instruction side effects are immediately attached to the AST that's
204 // being generated rather than being stored in some state.
205 
216 // RiscOperators
219 
221 typedef boost::shared_ptr<class RiscOperators> RiscOperatorsPtr;
222 
231 public:
234 
237 
238 public:
240  struct SideEffect {
245  // Default constructor. Not normally used, but needed by <code>std::vector</code>. (DON'T DOCUMENT)
246  SideEffect() {}
247 
248  // Used internally, not neede by users since data members are public.
249  SideEffect(const BaseSemantics::SValuePtr &location, const BaseSemantics::SValuePtr &temporary,
250  const BaseSemantics::SValuePtr &expression)
251  : location(location), temporary(temporary), expression(expression) {}
252 
254  bool isValid() const { return expression != NULL; }
255 
259  bool isSubstitution() const {
260  return isValid() && location==NULL && temporary!=NULL;
261  }
262  };
263 
265  typedef std::vector<SideEffect> SideEffects;
266 
267 private:
268  SideEffects sideEffects_; // Side effects, including substitutions
269  bool executionHalted_; // Stop adding inputs and outputs?
270 
271 protected:
272  RiscOperators(const BaseSemantics::SValuePtr &protoval, const SmtSolverPtr&);
273 
274  RiscOperators(const BaseSemantics::StatePtr&, const SmtSolverPtr&);
275 
276 public:
279  static RiscOperatorsPtr instanceFromRegisters(const RegisterDictionaryPtr&, const SmtSolverPtr &solver = SmtSolverPtr());
280 
284  static RiscOperatorsPtr instanceFromProtoval(const BaseSemantics::SValuePtr &protoval,
285  const SmtSolverPtr &solver = SmtSolverPtr());
286 
289  static RiscOperatorsPtr instanceFromState(const BaseSemantics::StatePtr&, const SmtSolverPtr&);
290 
292  // Virtual constructors
293 public:
295  const SmtSolverPtr &solver = SmtSolverPtr()) const override;
296 
298  const SmtSolverPtr &solver = SmtSolverPtr()) const override;
299 
301  // Dynamic pointer casts
302 public:
305  static RiscOperatorsPtr promote(const BaseSemantics::RiscOperatorsPtr&);
306 
308  // Supporting functions
309 public:
311  BaseSemantics::SValuePtr makeSValue(size_t nbits, SgNode*, const std::string &ctext = "");
312 
320 
327 
331  const SideEffects& sideEffects() const {
332  return sideEffects_;
333  }
334 
336  void resetState();
337 
343 
345  void reset() {
346  sideEffects_.clear();
347  executionHalted_ = false;
348  resetState();
349  }
350 
357  void haltExecution() { executionHalted_ = true; }
358 
364  BaseSemantics::SValuePtr makeMask(size_t nBits, size_t nSet, size_t sa=0);
365 
367  // Override all operator methods from base class. These are the RISC operators that are invoked by a Dispatcher.
368 public:
369  virtual BaseSemantics::SValuePtr unspecified_(size_t nbits) override;
370  virtual void hlt() override;
371  virtual void cpuid() override;
372  virtual BaseSemantics::SValuePtr rdtsc() override;
374  const BaseSemantics::SValuePtr &b_) override;
376  const BaseSemantics::SValuePtr &b_) override;
378  const BaseSemantics::SValuePtr &b_) override;
379  virtual BaseSemantics::SValuePtr invert(const BaseSemantics::SValuePtr &a_) override;
381  size_t begin_bit, size_t end_bit) override;
383  const BaseSemantics::SValuePtr &b_) override;
387  const BaseSemantics::SValuePtr &sa_) override;
389  const BaseSemantics::SValuePtr &sa_) override;
391  const BaseSemantics::SValuePtr &sa_) override;
393  const BaseSemantics::SValuePtr &sa_) override;
395  const BaseSemantics::SValuePtr &sa_) override;
398  const BaseSemantics::SValuePtr &a_,
399  const BaseSemantics::SValuePtr &b_,
400  IteStatus&) override;
401  virtual BaseSemantics::SValuePtr unsignedExtend(const BaseSemantics::SValuePtr &a_, size_t new_width) override;
402  virtual BaseSemantics::SValuePtr signExtend(const BaseSemantics::SValuePtr &a_, size_t new_width) override;
404  const BaseSemantics::SValuePtr &b_) override;
406  const BaseSemantics::SValuePtr &b_,
407  const BaseSemantics::SValuePtr &c_,
408  BaseSemantics::SValuePtr &carry_out/*out*/) override;
409  virtual BaseSemantics::SValuePtr negate(const BaseSemantics::SValuePtr &a_) override;
411  const BaseSemantics::SValuePtr &b_) override;
413  const BaseSemantics::SValuePtr &b_) override;
415  const BaseSemantics::SValuePtr &b_) override;
417  const BaseSemantics::SValuePtr &b_) override;
419  const BaseSemantics::SValuePtr &b_) override;
421  const BaseSemantics::SValuePtr &b_) override;
422  virtual void interrupt(int majr, int minr) override;
424  const BaseSemantics::SValuePtr &dflt) override;
426  const BaseSemantics::SValuePtr &dflt) override;
427  virtual void writeRegister(RegisterDescriptor reg, const BaseSemantics::SValuePtr &a) override;
429  const BaseSemantics::SValuePtr &addr,
430  const BaseSemantics::SValuePtr &dflt,
431  const BaseSemantics::SValuePtr &cond) override;
433  const BaseSemantics::SValuePtr &addr,
434  const BaseSemantics::SValuePtr &dflt) override;
435  virtual void writeMemory(RegisterDescriptor segreg,
436  const BaseSemantics::SValuePtr &addr,
437  const BaseSemantics::SValuePtr &data,
438  const BaseSemantics::SValuePtr &cond) override;
439 };
440 
441 
442 } // namespace
443 } // namespace
444 } // namespace
445 } // namespace
446 
447 #endif
448 #endif
virtual BaseSemantics::SValuePtr bottom_(size_t nbits) const override
Data-flow bottom value.
static SValuePtr instance()
Instantiate a prototypical SValue.
virtual BaseSemantics::SValuePtr unspecified_(size_t nbits) override
Returns a new undefined value.
Semantic values for generating C source code ASTs.
virtual void ctext(const std::string &s)
C source text associated with this semantic value.
BaseSemantics::StatePtr StatePtr
Pointer to states used by this domain.
boost::shared_ptr< class RiscOperators > RiscOperatorsPtr
Shared-ownership pointer for basic semantic operations.
virtual BaseSemantics::SValuePtr or_(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &b_) override
Computes bit-wise OR of two values.
virtual BaseSemantics::SValuePtr peekRegister(RegisterDescriptor reg, const BaseSemantics::SValuePtr &dflt) override
Obtain a register value without side effects.
bool isValid() const
Predicate to determine whether side effect is valid.
boost::shared_ptr< RiscOperators > RiscOperatorsPtr
Shared-ownership pointer to a RISC operators object.
virtual BaseSemantics::SValuePtr signedDivide(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &b_) override
Divides two signed values.
BaseSemantics::SValuePtr makeSValue(size_t nbits, SgNode *, const std::string &ctext="")
Create a new SValue.
static std::string signedTypeNameForSize(size_t nbits)
Name of integer type used for value.
virtual BaseSemantics::SValuePtr xor_(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &b_) override
Computes bit-wise XOR of two values.
virtual BaseSemantics::SValuePtr number_(size_t nbits, uint64_t value) const override
Create a new concrete semantic value.
virtual void writeMemory(RegisterDescriptor segreg, const BaseSemantics::SValuePtr &addr, const BaseSemantics::SValuePtr &data, const BaseSemantics::SValuePtr &cond) override
Writes a value to memory.
virtual bool isBottom() const override
Determines whether a value is a data-flow bottom.
virtual BaseSemantics::SValuePtr undefined_(size_t nbits) const override
Create a new undefined semantic value.
Holds a value or nothing.
Definition: Optional.h:49
Sawyer::SharedPointer< class SValue > SValuePtr
Shared-ownership pointer for a binary-to-source semantic value.
virtual BaseSemantics::SValuePtr signExtend(const BaseSemantics::SValuePtr &a_, size_t new_width) override
Sign extends a value.
virtual void print(std::ostream &, BaseSemantics::Formatter &) const override
Print a value to a stream using default format.
virtual BaseSemantics::SValuePtr and_(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &b_) override
Computes bit-wise AND of two values.
Main namespace for the ROSE library.
virtual BaseSemantics::SValuePtr signedModulo(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &b_) override
Calculates modulo with signed values.
BaseSemantics::SValuePtr saveSideEffect(const BaseSemantics::SValuePtr &expression, const BaseSemantics::SValuePtr &location=BaseSemantics::SValuePtr())
Save a side effect.
virtual void cpuid() override
Invoked for the x86 CPUID instruction.
virtual BaseSemantics::SValuePtr boolean_(bool value) const override
Create a new, Boolean value.
Reference-counting intrusive smart pointer.
Definition: SharedPointer.h:68
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 ...
boost::shared_ptr< State > StatePtr
Shared-ownership pointer to a semantic state.
BaseSemantics::SValuePtr substitute(const BaseSemantics::SValuePtr &expression)
Save input value.
boost::shared_ptr< class MemoryState > MemoryStatePtr
Shared-ownership pointer to null register state.
virtual BaseSemantics::SValuePtr add(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &b_) override
Adds two integers of equal size.
virtual BaseSemantics::SValuePtr rotateLeft(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &sa_) override
Rotate bits to the left.
virtual BaseSemantics::SValuePtr shiftRight(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &sa_) override
Returns arg shifted right logically (no sign bit).
virtual void hlt() override
Invoked for the x86 HLT instruction.
static RiscOperatorsPtr instanceFromState(const BaseSemantics::StatePtr &, const SmtSolverPtr &)
Instantiates a new RiscOperators object with specified state.
virtual BaseSemantics::SValuePtr signedMultiply(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &b_) override
Multiplies two signed values.
virtual BaseSemantics::SValuePtr mostSignificantSetBit(const BaseSemantics::SValuePtr &a_) override
Returns position of most significant set bit; zero when no bits are set.
boost::shared_ptr< class RegisterStateGeneric > RegisterStateGenericPtr
Shared-ownership pointer to generic register states.
std::string registerVariableName(RegisterDescriptor)
Global variable name for a register.
static SValuePtr promote(const BaseSemantics::SValuePtr &v)
Promote a base instance to an instance of this class.
bool isSubstitution() const
Predicate to determine whether side effect is rather a substitution.
virtual void writeRegister(RegisterDescriptor reg, const BaseSemantics::SValuePtr &a) override
Writes a value to a register.
virtual BaseSemantics::SValuePtr unsignedMultiply(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &b_) override
Multiply two unsigned values.
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 extract(const BaseSemantics::SValuePtr &a_, size_t begin_bit, size_t end_bit) override
Extracts bits from a value.
static std::string unsignedTypeNameForSize(size_t nbits)
Name of integer type used for value.
Describes (part of) a physical CPU register.
BaseSemantics::RegisterStateGeneric RegisterState
Register state used by this domain.
This class represents the base class for all IR nodes within Sage III.
Definition: Cxx_Grammar.h:9433
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 unsignedModulo(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &b_) override
Calculates modulo with unsigned values.
virtual BaseSemantics::SValuePtr invert(const BaseSemantics::SValuePtr &a_) override
One's complement.
virtual BaseSemantics::RiscOperatorsPtr create(const BaseSemantics::SValuePtr &protoval, const SmtSolverPtr &solver=SmtSolverPtr()) const override
Virtual allocating constructor.
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.
BaseSemantics::SValuePtr makeMask(size_t nBits, size_t nSet, size_t sa=0)
Return a bit mask.
static SValuePtr instance_integer(size_t nbits, uint64_t value)
Instantiate an integer constant.
virtual BaseSemantics::SValuePtr iteWithStatus(const BaseSemantics::SValuePtr &sel_, const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &b_, IteStatus &) override
If-then-else with status.
virtual void interrupt(int majr, int minr) override
Invoked for instructions that cause an interrupt.
SharedPointer< U > dynamicCast() const
Dynamic cast.
BaseSemantics::RegisterStateGenericPtr RegisterStatePtr
Pointer to register states used by this domain.
const SideEffects & sideEffects() const
Accumulated side effects and substitutions.
Binary analysis.
virtual Sawyer::Optional< BaseSemantics::SValuePtr > createOptionalMerge(const BaseSemantics::SValuePtr &, const BaseSemantics::MergerPtr &, const SmtSolverPtr &) const override
Possibly create a new value by merging two existing values.
virtual BaseSemantics::SValuePtr shiftRightArithmetic(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &sa_) override
Returns arg shifted right arithmetically (with sign bit).
virtual BaseSemantics::SValuePtr unsignedDivide(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &b_) override
Divides two unsigned 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...
BaseSemantics::State State
State used by this domain.
virtual void set_width(size_t nbits) override
Virtual API.
virtual BaseSemantics::SValuePtr unspecified_(size_t nbits) const override
Create a new unspecified semantic value.
NullSemantics::MemoryState MemoryState
Memory state used by this domain.
virtual BaseSemantics::SValuePtr rdtsc() override
Invoked for the x86 RDTSC instruction.
virtual SmtSolverPtr solver() const
Property: Satisfiability module theory (SMT) solver.
static SValuePtr instance_undefined(size_t nbits)
Instantiate an undefined value.
virtual BaseSemantics::SValuePtr readRegister(RegisterDescriptor reg, const BaseSemantics::SValuePtr &dflt) override
Reads a value from a register.
virtual SValuePtr protoval() const
Property: Prototypical semantic value.
static RiscOperatorsPtr promote(const BaseSemantics::RiscOperatorsPtr &)
Run-time promotion of a base RiscOperators instance to an instance of this semantic domain's operator...
Base class for most instruction semantics RISC operators.
Definition: RiscOperators.h:48
virtual bool must_equal(const BaseSemantics::SValuePtr &other, const SmtSolverPtr &solver=SmtSolverPtr()) const override
Virtual API.
virtual BaseSemantics::SValuePtr shiftLeft(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &sa_) override
Returns arg shifted left.
static RiscOperatorsPtr instanceFromProtoval(const BaseSemantics::SValuePtr &protoval, const SmtSolverPtr &solver=SmtSolverPtr())
Instantiates a new RiscOperators object with specified prototypical values.
virtual BaseSemantics::SValuePtr equalToZero(const BaseSemantics::SValuePtr &a_) override
Determines whether a value is equal to zero.
Base class for semantics machine states.
Definition: State.h:39
NullSemantics::MemoryStatePtr MemoryStatePtr
Pointer to memory states used by this domain.
virtual bool may_equal(const BaseSemantics::SValuePtr &other, const SmtSolverPtr &solver=SmtSolverPtr()) const override
Virtual API.
virtual const std::string & ctext() const
C source text associated with this semantic value.
virtual BaseSemantics::SValuePtr peekMemory(RegisterDescriptor segreg, const BaseSemantics::SValuePtr &addr, const BaseSemantics::SValuePtr &dflt) override
Read memory without side effects.
virtual BaseSemantics::SValuePtr readMemory(RegisterDescriptor segreg, const BaseSemantics::SValuePtr &addr, const BaseSemantics::SValuePtr &dflt, const BaseSemantics::SValuePtr &cond) override
Reads a value from memory.
std::vector< SideEffect > SideEffects
Side effects in the order they occur.
virtual void hash(Combinatorics::Hasher &) const override
Hash this semantic value.
virtual BaseSemantics::SValuePtr concat(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &b_) override
Concatenates the bits of two values.
virtual BaseSemantics::SValuePtr rotateRight(const BaseSemantics::SValuePtr &a_, const BaseSemantics::SValuePtr &sa_) override
Rotate bits to the right.
virtual BaseSemantics::SValuePtr negate(const BaseSemantics::SValuePtr &a_) override
Two's complement.