ROSE  0.11.50.0
RiscOperators.h
1 #ifndef ROSE_BinaryAnalysis_InstructionSemantics2_BaseSemantics_RiscOperators_H
2 #define ROSE_BinaryAnalysis_InstructionSemantics2_BaseSemantics_RiscOperators_H
3 #include <featureTests.h>
4 #ifdef ROSE_ENABLE_BINARY_ANALYSIS
5 
6 #include <Rose/BinaryAnalysis/InstructionSemantics2/BaseSemantics/Types.h>
7 #include <Rose/BinaryAnalysis/InstructionSemantics2/Util.h>
8 #include <Rose/BinaryAnalysis/HotPatch.h>
9 #include <Rose/BinaryAnalysis/SmtSolver.h>
10 #include <Combinatorics.h>
11 
12 #include <boost/enable_shared_from_this.hpp>
13 #include <boost/serialization/access.hpp>
14 #include <boost/serialization/export.hpp>
15 #include <boost/serialization/nvp.hpp>
16 #include <boost/serialization/shared_ptr.hpp>
17 #include <boost/serialization/version.hpp>
18 
19 namespace Rose {
20 namespace BinaryAnalysis {
21 namespace InstructionSemantics2 {
22 namespace BaseSemantics {
23 
25 // RISC Operators
27 
48 class RiscOperators: public boost::enable_shared_from_this<RiscOperators> {
49 public:
52 
53 private:
54  SValuePtr protoval_; // Prototypical value used for its virtual constructors
55  StatePtr currentState_; // State upon which RISC operators operate
56  StatePtr initialState_; // Lazily updated initial state; see readMemory
57  SmtSolverPtr solver_; // Optional SMT solver
58  SgAsmInstruction *currentInsn_; // Current instruction, as set by latest startInstruction call
59  size_t nInsns_; // Number of instructions processed
60  std::string name_; // Name to use for debugging
61  HotPatch hotPatch_; // Adjustments to the semantic state after each instruction.
62 
64  // Serialization
65 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
66 private:
67  friend class boost::serialization::access;
68 
69  template<class S>
70  void serialize(S &s, const unsigned version) {
71  s & BOOST_SERIALIZATION_NVP(protoval_);
72  s & BOOST_SERIALIZATION_NVP(currentState_);
73  s & BOOST_SERIALIZATION_NVP(initialState_);
74  s & BOOST_SERIALIZATION_NVP(solver_);
75  s & BOOST_SERIALIZATION_NVP(currentInsn_);
76  s & BOOST_SERIALIZATION_NVP(nInsns_);
77  s & BOOST_SERIALIZATION_NVP(name_);
78  if (version >= 1)
79  s & BOOST_SERIALIZATION_NVP(hotPatch_);
80  }
81 #endif
82 
84  // Real constructors
85 protected:
86  // for serialization
87  RiscOperators();
88 
89  explicit RiscOperators(const SValuePtr &protoval, const SmtSolverPtr &solver = SmtSolverPtr());
90  explicit RiscOperators(const StatePtr &state, const SmtSolverPtr &solver = SmtSolverPtr());
91 
92 public:
93  virtual ~RiscOperators();
94 
96  // Static allocating constructors. None needed since this class is abstract.
97 
98 
100  // Virtual constructors.
101 public:
105  virtual RiscOperatorsPtr create(const SValuePtr &protoval, const SmtSolverPtr &solver = SmtSolverPtr()) const = 0;
106 
111  virtual RiscOperatorsPtr create(const StatePtr &state, const SmtSolverPtr &solver = SmtSolverPtr()) const = 0;
112 
114  // Dynamic pointer casts. No-op since this is the base class.
115 public:
116  static RiscOperatorsPtr promote(const RiscOperatorsPtr &x) {
117  ASSERT_not_null(x);
118  return x;
119  }
120 
122  // Other methods part of our API
123 public:
127  virtual SValuePtr protoval() const { return protoval_; }
128 
137  virtual SmtSolverPtr solver() const { return solver_; }
138  virtual void solver(const SmtSolverPtr &s) { solver_ = s; }
147  const HotPatch& hotPatch() const { return hotPatch_; }
148  HotPatch& hotPatch() { return hotPatch_; }
149  void hotPatch(const HotPatch &hp) { hotPatch_ = hp; }
163  virtual StatePtr currentState() const { return currentState_; }
164  virtual void currentState(const StatePtr &s) { currentState_ = s; }
204  virtual StatePtr initialState() const { return initialState_; }
205  virtual void initialState(const StatePtr &s) { initialState_ = s; }
213  virtual const std::string& name() const { return name_; }
214  virtual void name(const std::string &s) { name_ = s; }
220  virtual void hash(Combinatorics::Hasher&);
221 
224  void print(std::ostream &stream, const std::string prefix="") const;
225  virtual void print(std::ostream &stream, Formatter &fmt) const;
230  RiscOperatorsPtr obj;
231  Formatter &fmt;
232  public:
233  WithFormatter(const RiscOperatorsPtr &obj, Formatter &fmt): obj(obj), fmt(fmt) {}
234  void print(std::ostream &stream) const { obj->print(stream, fmt); }
235  };
236 
252  WithFormatter with_format(Formatter &fmt) { return WithFormatter(shared_from_this(), fmt); }
253  WithFormatter operator+(Formatter &fmt) { return with_format(fmt); }
254  WithFormatter operator+(const std::string &linePrefix);
262  virtual size_t nInsns() const { return nInsns_; }
263  virtual void nInsns(size_t n) { nInsns_ = n; }
272  virtual SgAsmInstruction* currentInstruction() const {
273  return currentInsn_;
274  }
275  virtual void currentInstruction(SgAsmInstruction *insn) {
276  currentInsn_ = insn;
277  }
282  virtual void startInstruction(SgAsmInstruction *insn);
283 
286  virtual void finishInstruction(SgAsmInstruction *insn);
287 
288 
290  // Value Construction Operations
292  // The trailing underscores are necessary for for undefined_() on some machines, so we just add one to the end of all the
293  // virtual constructors for consistency.
294 
298  virtual SValuePtr undefined_(size_t nbits);
299  virtual SValuePtr unspecified_(size_t nbits);
303  virtual SValuePtr number_(size_t nbits, uint64_t value);
304 
306  virtual SValuePtr boolean_(bool value);
307 
309  virtual SValuePtr bottom_(size_t nbits);
310 
311 
313  // x86-specific Operations (FIXME)
315 
318  virtual SValuePtr filterCallTarget(const SValuePtr &a);
319 
323  virtual SValuePtr filterReturnTarget(const SValuePtr &a);
324 
328  virtual SValuePtr filterIndirectJumpTarget(const SValuePtr &a);
329 
331  virtual void hlt() {}
332 
334  virtual void cpuid() {}
335 
337  virtual SValuePtr rdtsc() { return unspecified_(64); }
338 
339 
341  // Boolean Operations
343 
346  virtual SValuePtr and_(const SValuePtr &a, const SValuePtr &b) = 0;
347 
350  virtual SValuePtr or_(const SValuePtr &a, const SValuePtr &b) = 0;
351 
354  virtual SValuePtr xor_(const SValuePtr &a, const SValuePtr &b) = 0;
355 
357  virtual SValuePtr invert(const SValuePtr &a) = 0;
358 
362  virtual SValuePtr extract(const SValuePtr &a, size_t begin_bit, size_t end_bit) = 0;
363 
369  virtual SValuePtr concat(const SValuePtr &lowBits, const SValuePtr &highBits) = 0;
370 
378  virtual SValuePtr concatLoHi(const SValuePtr &lowBits, const SValuePtr &highBits) {
379  return concat(lowBits, highBits);
380  }
381  virtual SValuePtr concatHiLo(const SValuePtr &highBits, const SValuePtr &lowBits) {
382  return concat(lowBits, highBits);
383  }
391  virtual std::pair<SValuePtr /*low*/, SValuePtr /*high*/> split(const SValuePtr &a, size_t splitPoint);
392 
395  virtual SValuePtr leastSignificantSetBit(const SValuePtr &a) = 0;
396 
399  virtual SValuePtr mostSignificantSetBit(const SValuePtr &a) = 0;
400 
405  virtual SValuePtr countLeadingZeros(const SValuePtr &a);
406 
411  virtual SValuePtr countLeadingOnes(const SValuePtr &a);
412 
416  virtual SValuePtr rotateLeft(const SValuePtr &a, const SValuePtr &nbits) = 0;
417 
421  virtual SValuePtr rotateRight(const SValuePtr &a, const SValuePtr &nbits) = 0;
422 
426  virtual SValuePtr shiftLeft(const SValuePtr &a, const SValuePtr &nbits) = 0;
427 
431  virtual SValuePtr shiftRight(const SValuePtr &a, const SValuePtr &nbits) = 0;
432 
437  virtual SValuePtr shiftRightArithmetic(const SValuePtr &a, const SValuePtr &nbits) = 0;
438 
444  virtual SValuePtr reverseElmts(const SValuePtr &a, size_t elmtNBits);
445 
446 
448  // Comparison Operations
450 
453  virtual SValuePtr equalToZero(const SValuePtr &a) = 0;
454 
458  virtual SValuePtr ite(const SValuePtr &cond, const SValuePtr &a, const SValuePtr &b) = 0;
459 
466  virtual SValuePtr isEqual(const SValuePtr &a, const SValuePtr &b);
467  virtual SValuePtr isNotEqual(const SValuePtr &a, const SValuePtr &b);
477  virtual SValuePtr isUnsignedLessThan(const SValuePtr &a, const SValuePtr &b);
478  virtual SValuePtr isUnsignedLessThanOrEqual(const SValuePtr &a, const SValuePtr &b);
479  virtual SValuePtr isUnsignedGreaterThan(const SValuePtr &a, const SValuePtr &b);
480  virtual SValuePtr isUnsignedGreaterThanOrEqual(const SValuePtr &a, const SValuePtr &b);
490  virtual SValuePtr isSignedLessThan(const SValuePtr &a, const SValuePtr &b);
491  virtual SValuePtr isSignedLessThanOrEqual(const SValuePtr &a, const SValuePtr &b);
492  virtual SValuePtr isSignedGreaterThan(const SValuePtr &a, const SValuePtr &b);
493  virtual SValuePtr isSignedGreaterThanOrEqual(const SValuePtr &a, const SValuePtr &b);
496  // Integer Arithmetic Operations
499 
502  virtual SValuePtr unsignedExtend(const SValuePtr &a, size_t new_width);
503 
506  virtual SValuePtr signExtend(const SValuePtr &a, size_t new_width) = 0;
507 
510  virtual SValuePtr add(const SValuePtr &a, const SValuePtr &b) = 0;
511 
516  virtual SValuePtr addCarry(const SValuePtr &a, const SValuePtr &b,
517  SValuePtr &carryOut /*out*/, SValuePtr &overflowed /*out*/);
518 
524  virtual SValuePtr subtract(const SValuePtr &minuend, const SValuePtr &subtrahend);
525 
534  virtual SValuePtr subtractCarry(const SValuePtr &minuend, const SValuePtr &subtrahend,
535  SValuePtr &carryOut /*out*/, SValuePtr &overflowed /*out*/);
536 
553  virtual SValuePtr addWithCarries(const SValuePtr &a, const SValuePtr &b, const SValuePtr &c,
554  SValuePtr &carry_out/*output*/) = 0;
555 
557  virtual SValuePtr negate(const SValuePtr &a) = 0;
558 
560  virtual SValuePtr signedDivide(const SValuePtr &dividend, const SValuePtr &divisor) = 0;
561 
563  virtual SValuePtr signedModulo(const SValuePtr &a, const SValuePtr &b) = 0;
564 
566  virtual SValuePtr signedMultiply(const SValuePtr &a, const SValuePtr &b) = 0;
567 
569  virtual SValuePtr unsignedDivide(const SValuePtr &dividend, const SValuePtr &divisor) = 0;
570 
572  virtual SValuePtr unsignedModulo(const SValuePtr &a, const SValuePtr &b) = 0;
573 
575  virtual SValuePtr unsignedMultiply(const SValuePtr &a, const SValuePtr &b) = 0;
576 
577 
579  // Interrupt and system calls
581 
588  virtual void interrupt(int majr, int minr) {}
589 
595  virtual void interrupt(const SValuePtr &majr, const SValuePtr &minr, const SValuePtr &enabled);
596 
597 
599  // Floating-point operations
600  //
601  // For now these all have default implementations that throw NotImplemented, but we might change them to pure virtual
602  // sometime in the future so they're consistent with most other RISC operators. [Robb P. Matzke 2015-08-03]
604 
606  virtual SValuePtr fpFromInteger(const SValuePtr &intValue, SgAsmFloatType *fpType);
607 
613  virtual SValuePtr fpToInteger(const SValuePtr &fpValue, SgAsmFloatType *fpType, const SValuePtr &dflt);
614 
618  virtual SValuePtr fpConvert(const SValuePtr &a, SgAsmFloatType *aType, SgAsmFloatType *retType);
619 
621  virtual SValuePtr fpIsNan(const SValuePtr &fpValue, SgAsmFloatType *fpType);
622 
624  virtual SValuePtr fpIsDenormalized(const SValuePtr &fpValue, SgAsmFloatType *fpType);
625 
627  virtual SValuePtr fpIsZero(const SValuePtr &fpValue, SgAsmFloatType *fpType);
628 
633  virtual SValuePtr fpIsInfinity(const SValuePtr &fpValue, SgAsmFloatType *fpType);
634 
638  virtual SValuePtr fpSign(const SValuePtr &fpValue, SgAsmFloatType *fpType);
639 
645  virtual SValuePtr fpEffectiveExponent(const SValuePtr &fpValue, SgAsmFloatType *fpType);
646 
650  virtual SValuePtr fpAdd(const SValuePtr &a, const SValuePtr &b, SgAsmFloatType *fpType);
651 
656  virtual SValuePtr fpSubtract(const SValuePtr &a, const SValuePtr &b, SgAsmFloatType *fpType);
657 
661  virtual SValuePtr fpMultiply(const SValuePtr &a, const SValuePtr &b, SgAsmFloatType *fpType);
662 
666  virtual SValuePtr fpDivide(const SValuePtr &a, const SValuePtr &b, SgAsmFloatType *fpType);
667 
671  virtual SValuePtr fpSquareRoot(const SValuePtr &a, SgAsmFloatType *fpType);
672 
676  virtual SValuePtr fpRoundTowardZero(const SValuePtr &a, SgAsmFloatType *fpType);
677 
679  // Conversion operations
681 
687  virtual SValuePtr reinterpret(const SValuePtr &a, SgAsmType *retType);
688 
699  virtual SValuePtr convert(const SValuePtr &a, SgAsmType *srcType, SgAsmType *dstType);
700 
701 
703  // State Accessing Operations
705 
730  virtual SValuePtr readRegister(RegisterDescriptor reg) { // old subclasses can still override this if they want,
731  return readRegister(reg, undefined_(reg.nBits())); // but new subclasses should not override this method.
732  }
733  virtual SValuePtr readRegister(RegisterDescriptor reg, const SValuePtr &dflt); // new subclasses override this
745  virtual void writeRegister(RegisterDescriptor reg, const SValuePtr &a);
746 
754  virtual SValuePtr peekRegister(RegisterDescriptor, const SValuePtr &dflt);
756  return peekRegister(reg, undefined_(reg.nBits()));
757  }
781  virtual SValuePtr readMemory(RegisterDescriptor segreg, const SValuePtr &addr, const SValuePtr &dflt,
782  const SValuePtr &cond) = 0;
783 
794  virtual void writeMemory(RegisterDescriptor segreg, const SValuePtr &addr, const SValuePtr &data,
795  const SValuePtr &cond) = 0;
796 
801  virtual SValuePtr peekMemory(RegisterDescriptor segreg, const SValuePtr &addr, const SValuePtr &dflt) = 0;
802 };
803 
804 std::ostream& operator<<(std::ostream&, const RiscOperators&);
805 std::ostream& operator<<(std::ostream&, const RiscOperators::WithFormatter&);
806 
807 } // namespace
808 } // namespace
809 } // namespace
810 } // namespace
811 
814 
815 #endif
816 #endif
virtual SValuePtr signedMultiply(const SValuePtr &a, const SValuePtr &b)=0
Multiplies two signed values.
Unsigned shiftRight(Unsigned src, size_t n, bool b=false)
Right shift a value.
Definition: Rose/BitOps.h:106
boost::shared_ptr< RiscOperators > RiscOperatorsPtr
Shared-ownership pointer to a RISC operators object.
virtual SValuePtr fpIsDenormalized(const SValuePtr &fpValue, SgAsmFloatType *fpType)
Whether a floating-point value is denormalized.
Unsigned rotateLeft(Unsigned src, size_t n)
Rotate bits left.
Definition: Rose/BitOps.h:310
ROSE_UTIL_API std::vector< std::string > split(const std::string &separator, const std::string &str, size_t maxparts=UNLIMITED, bool trim_white_space=false)
Splits strings into parts.
size_t nBits() const
Property: Size in bits.
virtual SValuePtr fpMultiply(const SValuePtr &a, const SValuePtr &b, SgAsmFloatType *fpType)
Multiply two floating-point values.
Describes how to modify machine state after each instruction.
Definition: HotPatch.h:22
virtual SValuePtr convert(const SValuePtr &a, SgAsmType *srcType, SgAsmType *dstType)
Convert value from one type to another.
virtual void writeMemory(RegisterDescriptor segreg, const SValuePtr &addr, const SValuePtr &data, const SValuePtr &cond)=0
Writes a value to memory.
Base class for machine instructions.
Unsigned signExtend(Unsigned src, size_t n)
Sign extend part of a value to the full width of the src type.
Definition: Rose/BitOps.h:272
HotPatch & hotPatch()
Property: Post-instruction hot patches.
Unsigned shiftLeft(Unsigned src, size_t n, bool b=false)
Left shift a value.
Definition: Rose/BitOps.h:76
const HotPatch & hotPatch() const
Property: Post-instruction hot patches.
virtual SValuePtr fpFromInteger(const SValuePtr &intValue, SgAsmFloatType *fpType)
Construct a floating-point value from an integer value.
virtual SValuePtr unsignedDivide(const SValuePtr &dividend, const SValuePtr &divisor)=0
Divides two unsigned values.
virtual SValuePtr fpRoundTowardZero(const SValuePtr &a, SgAsmFloatType *fpType)
Round toward zero.
boost::shared_ptr< State > StatePtr
Shared-ownership pointer to a semantic state.
void invert(Word *words, const BitRange &range)
Invert bits.
virtual SValuePtr fpDivide(const SValuePtr &a, const SValuePtr &b, SgAsmFloatType *fpType)
Divide one floating-point value by another.
virtual SValuePtr signedDivide(const SValuePtr &dividend, const SValuePtr &divisor)=0
Divides two signed values.
virtual SValuePtr fpSign(const SValuePtr &fpValue, SgAsmFloatType *fpType)
Sign of floating-point value.
virtual SValuePtr protoval() const
Property: Prototypical semantic value.
Main namespace for the ROSE library.
virtual SValuePtr fpToInteger(const SValuePtr &fpValue, SgAsmFloatType *fpType, const SValuePtr &dflt)
Construct an integer value from a floating-point value.
virtual SValuePtr unsignedMultiply(const SValuePtr &a, const SValuePtr &b)=0
Multiply two unsigned values.
virtual SValuePtr addWithCarries(const SValuePtr &a, const SValuePtr &b, const SValuePtr &c, SValuePtr &carry_out)=0
Used for printing RISC operators with formatting.
virtual SValuePtr peekMemory(RegisterDescriptor segreg, const SValuePtr &addr, const SValuePtr &dflt)=0
Read memory without side effects.
virtual void solver(const SmtSolverPtr &s)
Property: Satisfiability module theory (SMT) solver.
virtual SValuePtr readMemory(RegisterDescriptor segreg, const SValuePtr &addr, const SValuePtr &dflt, const SValuePtr &cond)=0
Reads a value from memory.
virtual void interrupt(int majr, int minr)
Invoked for instructions that cause an interrupt.
Unsigned rotateRight(Unsigned src, size_t n)
Rotate bits right.
Definition: Rose/BitOps.h:334
virtual StatePtr currentState() const
Property: Current semantic state.
virtual SValuePtr reinterpret(const SValuePtr &a, SgAsmType *retType)
Reinterpret an expression as a different type.
virtual SValuePtr fpIsInfinity(const SValuePtr &fpValue, SgAsmFloatType *fpType)
Whether a floating-point value is infinity.
Describes (part of) a physical CPU register.
virtual SValuePtr fpIsZero(const SValuePtr &fpValue, SgAsmFloatType *fpType)
Whether a floating-point value is equal to zero.
T shiftRightArithmetic(T value, size_t count)
Shifts bits of value right by count bits with sign extension.
Definition: integerOps.h:131
Optional< size_t > leastSignificantSetBit(const Word *words, const BitRange &range)
Index of least significant set bit.
virtual SValuePtr fpSquareRoot(const SValuePtr &a, SgAsmFloatType *fpType)
Square root.
virtual SValuePtr fpAdd(const SValuePtr &a, const SValuePtr &b, SgAsmFloatType *fpType)
Add two floating-point values.
virtual void currentState(const StatePtr &s)
Property: Current semantic state.
Optional< size_t > mostSignificantSetBit(const Word *words, const BitRange &range)
Index of most significant set bit.
void print(std::ostream &stream, const std::string prefix="") const
Print multi-line output for this object.
virtual StatePtr initialState() const
Property: Optional lazily updated initial state.
virtual SValuePtr fpIsNan(const SValuePtr &fpValue, SgAsmFloatType *fpType)
Whether a floating-point value is a special not-a-number bit pattern.
Base class for most instruction semantics RISC operators.
Definition: RiscOperators.h:48
virtual SValuePtr unsignedModulo(const SValuePtr &a, const SValuePtr &b)=0
Calculates modulo with unsigned values.
SValuePtr peekRegister(RegisterDescriptor reg)
Obtain a register value without side effects.
virtual void initialState(const StatePtr &s)
Property: Optional lazily updated initial state.
virtual SValuePtr fpConvert(const SValuePtr &a, SgAsmFloatType *aType, SgAsmFloatType *retType)
Convert from one floating-point type to another.
Base class for binary types.
virtual SValuePtr fpEffectiveExponent(const SValuePtr &fpValue, SgAsmFloatType *fpType)
Exponent of floating-point value.
virtual void name(const std::string &s)
Property: Name used for debugging.
Sawyer::SharedPointer< SValue > SValuePtr
Shared-ownership pointer to a semantic value in any domain.
virtual void writeRegister(RegisterDescriptor reg, const SValuePtr &a)
Writes a value to a register.
virtual void hash(Combinatorics::Hasher &)
Compute hash of current state.
virtual SValuePtr negate(const SValuePtr &a)=0
Two's complement.
virtual SValuePtr peekRegister(RegisterDescriptor, const SValuePtr &dflt)
Obtain a register value without side effects.
virtual SmtSolverPtr solver() const
Property: Satisfiability module theory (SMT) solver.
void hotPatch(const HotPatch &hp)
Property: Post-instruction hot patches.
virtual RiscOperatorsPtr create(const SValuePtr &protoval, const SmtSolverPtr &solver=SmtSolverPtr()) const =0
Virtual allocating constructor.
virtual const std::string & name() const
Property: Name used for debugging.
RiscOperatorsPtr Ptr
Shared-ownership pointer for a RiscOperators object.
Definition: RiscOperators.h:51
virtual SValuePtr readRegister(RegisterDescriptor reg)
Reads a value from a register.
virtual SValuePtr fpSubtract(const SValuePtr &a, const SValuePtr &b, SgAsmFloatType *fpType)
Subtract one floating-point value from another.
T extract(T bits)
Extract bits from a value.
Definition: integerOps.h:255
virtual SValuePtr signedModulo(const SValuePtr &a, const SValuePtr &b)=0
Calculates modulo with signed values.
Floating point types.
std::shared_ptr< class SmtSolver > SmtSolverPtr
Reference-counting pointer for SMT solvers.
Definition: SmtSolver.h:25