ROSE  0.11.145.0
MemoryCellList.h
1 #ifndef ROSE_BinaryAnalysis_InstructionSemantics_BaseSemantics_MemoryCellList_H
2 #define ROSE_BinaryAnalysis_InstructionSemantics_BaseSemantics_MemoryCellList_H
3 #include <featureTests.h>
4 #ifdef ROSE_ENABLE_BINARY_ANALYSIS
5 
6 #include <Rose/BinaryAnalysis/InstructionSemantics/BaseSemantics/MemoryCellState.h>
7 #include <Rose/BinaryAnalysis/InstructionSemantics/BaseSemantics/RiscOperators.h>
8 
9 #include <boost/serialization/access.hpp>
10 #include <boost/serialization/base_object.hpp>
11 #include <boost/serialization/export.hpp>
12 
13 namespace Rose {
14 namespace BinaryAnalysis {
15 namespace InstructionSemantics {
16 namespace BaseSemantics {
17 
19 typedef boost::shared_ptr<class MemoryCellList> MemoryCellListPtr;
20 
40 public:
43 
46 
47 protected:
48  CellList cells; // list of cells in reverse chronological order
49  bool occlusionsErased_; // prune away old cells that are occluded by newer ones.
50 
52  // Serialization
53 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
54 private:
55  friend class boost::serialization::access;
56 
57  template<class S>
58  void serialize(S &s, const unsigned /*version*/) {
59  s & BOOST_SERIALIZATION_BASE_OBJECT_NVP(MemoryCellState);
60  s & BOOST_SERIALIZATION_NVP(cells);
61  s & BOOST_SERIALIZATION_NVP(occlusionsErased_);
62  }
63 #endif
64 
66  // Real constructors
67 protected:
68  MemoryCellList() // for serialization
69  : occlusionsErased_(false) {}
70 
71  explicit MemoryCellList(const MemoryCellPtr &protocell)
72  : MemoryCellState(protocell), occlusionsErased_(false) {}
73 
74  MemoryCellList(const SValuePtr &addrProtoval, const SValuePtr &valProtoval)
75  : MemoryCellState(addrProtoval, valProtoval), occlusionsErased_(false) {}
76 
77  // deep-copy cell list so that modifying this new state does not modify the existing state
78  MemoryCellList(const MemoryCellList &other)
79  : MemoryCellState(other), occlusionsErased_(other.occlusionsErased_) {
80  for (CellList::const_iterator ci=other.cells.begin(); ci!=other.cells.end(); ++ci)
81  cells.push_back((*ci)->clone());
82  }
83 
85  // Static allocating constructors
86 public:
90  static MemoryCellListPtr instance(const SValuePtr &addrProtoval, const SValuePtr &valProtoval) {
91  return MemoryCellListPtr(new MemoryCellList(addrProtoval, valProtoval));
92  }
93 
95  static MemoryCellListPtr instance(const MemoryCellPtr &protocell) {
96  return MemoryCellListPtr(new MemoryCellList(protocell));
97  }
98 
100  static MemoryCellListPtr instance(const MemoryCellListPtr &other) {
101  return MemoryCellListPtr(new MemoryCellList(*other));
102  }
103 
104 
106  // Virtual constructors
107 public:
108  virtual MemoryStatePtr create(const SValuePtr &addrProtoval, const SValuePtr &valProtoval) const override {
109  return instance(addrProtoval, valProtoval);
110  }
111 
113  virtual MemoryStatePtr create(const MemoryCellPtr &protocell) const {
114  return instance(protocell);
115  }
116 
117  virtual MemoryStatePtr clone() const override {
118  return MemoryStatePtr(new MemoryCellList(*this));
119  }
120 
122  // Dynamic pointer casts
123 public:
126  static MemoryCellListPtr promote(const BaseSemantics::MemoryStatePtr &m) {
127  MemoryCellListPtr retval = boost::dynamic_pointer_cast<MemoryCellList>(m);
128  ASSERT_not_null(retval);
129  return retval;
130  }
131 
133  // Methods we inherited
134 public:
135  virtual void clear() override;
136  virtual bool merge(const MemoryStatePtr &other, RiscOperators *addrOps, RiscOperators *valOps) override;
137  virtual std::vector<MemoryCellPtr> matchingCells(MemoryCell::Predicate&) const override;
138  virtual std::vector<MemoryCellPtr> leadingCells(MemoryCell::Predicate&) const override;
139  virtual void eraseMatchingCells(MemoryCell::Predicate&) override;
140  virtual void eraseLeadingCells(MemoryCell::Predicate&) override;
141  virtual void traverse(MemoryCell::Visitor&) override;
142  virtual void hash(Combinatorics::Hasher&, RiscOperators *addrOps, RiscOperators *valOps) const override;
143 
154  virtual SValuePtr readMemory(const SValuePtr &address, const SValuePtr &dflt,
155  RiscOperators *addrOps, RiscOperators *valOps) override;
156 
157  virtual SValuePtr peekMemory(const SValuePtr &address, const SValuePtr &dflt,
158  RiscOperators *addrOps, RiscOperators *valOps) override;
159 
166  virtual void writeMemory(const SValuePtr &addr, const SValuePtr &value,
167  RiscOperators *addrOps, RiscOperators *valOps) override;
168 
169  virtual void print(std::ostream&, Formatter&) const override;
170 
172  // Methods first declared at this level of the class hierarchy
173 public:
178  bool mergeNoAliasing(const MemoryStatePtr &other, RiscOperators *addrOps, RiscOperators *valOps);
179 
184  bool mergeWithAliasing(const MemoryStatePtr &other, RiscOperators *addrOps, RiscOperators *valOps);
185 
190  virtual bool isAllPresent(const SValuePtr &address, size_t nBytes, RiscOperators *addrOps, RiscOperators *valOps) const;
191 
198  bool occlusionsErased() const { return occlusionsErased_; }
199  void occlusionsErased(bool b) { occlusionsErased_ = b; }
217  template<class Iterator>
218  CellList scan(Iterator &cursor /*in,out*/, const SValuePtr &addr, size_t nBits,
219  RiscOperators *addrOps, RiscOperators *valOps) const {
220  ASSERT_not_null(addr);
221  CellList retval;
222  MemoryCellPtr tempCell = protocell->create(addr, valOps->undefined_(nBits));
223  for (/*void*/; cursor!=cells.end(); ++cursor) {
224  if (tempCell->mayAlias(*cursor, addrOps)) {
225  retval.push_back(*cursor);
226  if (tempCell->mustAlias(*cursor, addrOps))
227  break;
228  }
229  }
230  return retval;
231  }
232 
235  virtual const CellList& get_cells() const { return cells; }
236  virtual CellList& get_cells() { return cells; }
239  virtual AddressSet getWritersUnion(const SValuePtr &addr, size_t nBits, RiscOperators *addrOps,
240  RiscOperators *valOps) override;
241 
242  virtual AddressSet getWritersIntersection(const SValuePtr &addr, size_t nBits, RiscOperators *addrOps,
243  RiscOperators *valOps) override;
244 
245 protected:
246  // Compute a new value by merging the specified cells. If the cell list is empty return the specified default.
247  virtual SValuePtr mergeCellValues(const CellList &cells, const SValuePtr &dflt, RiscOperators *addrOps,
248  RiscOperators *valOps);
249 
250  // Returns the union of all writers from the specified cells.
251  virtual AddressSet mergeCellWriters(const CellList &cells);
252 
253  // Returns the union of all properties from the specified cells.
254  virtual InputOutputPropertySet mergeCellProperties(const CellList &cells);
255 
256  // Insert a new cell at the head of the list. It's writers set is empty and its I/O properties will be READ,
257  // READ_BEFORE_WRITE, and READ_UNINITIALIZED.
258  virtual MemoryCellPtr insertReadCell(const SValuePtr &addr, const SValuePtr &value);
259 
260  // Insert a new cell at the head of the list. The specified writers and I/O properties are used.
261  virtual MemoryCellPtr insertReadCell(const SValuePtr &addr, const SValuePtr &value,
262  const AddressSet &writers, const InputOutputPropertySet &props);
263 };
264 
265 } // namespace
266 } // namespace
267 } // namespace
268 } // namespace
269 
270 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
272 #endif
273 
274 #endif
275 #endif
virtual void writeMemory(const SValuePtr &addr, const SValuePtr &value, RiscOperators *addrOps, RiscOperators *valOps) override
Write a value to memory.
boost::shared_ptr< class MemoryCellList > MemoryCellListPtr
Shared-ownership pointer to a list-based memory state.
virtual SValuePtr peekMemory(const SValuePtr &address, const SValuePtr &dflt, RiscOperators *addrOps, RiscOperators *valOps) override
Read a value from memory without side effects.
static MemoryCellListPtr promote(const BaseSemantics::MemoryStatePtr &m)
Promote a base memory state pointer to a BaseSemantics::MemoryCellList pointer.
static MemoryCellListPtr instance(const MemoryCellListPtr &other)
Instantiate a new copy of an existing memory state.
virtual SValuePtr undefined_(size_t nbits)
Returns a new undefined value.
Main namespace for the ROSE library.
CellList scan(Iterator &cursor, const SValuePtr &addr, size_t nBits, RiscOperators *addrOps, RiscOperators *valOps) const
Scan cell list to find matching cells.
virtual void hash(Combinatorics::Hasher &, RiscOperators *addrOps, RiscOperators *valOps) const override
Calculate a hash for this memory state.
boost::shared_ptr< MemoryCell > MemoryCellPtr
Shared-ownership pointer to a memory cell.
virtual MemoryStatePtr clone() const override
Virtual allocating copy constructor.
virtual void print(std::ostream &, Formatter &) const override
Print a memory state to more than one line of output.
bool occlusionsErased() const
Property: erase occluded cells.
virtual void eraseMatchingCells(MemoryCell::Predicate &) override
Remove all matching cells.
static MemoryCellListPtr instance(const SValuePtr &addrProtoval, const SValuePtr &valProtoval)
Instantiate a new prototypical memory state.
boost::shared_ptr< MemoryState > MemoryStatePtr
Shared-ownership pointer to a memory state.
virtual CellList & get_cells()
Returns the list of all memory cells.
virtual std::vector< MemoryCellPtr > matchingCells(MemoryCell::Predicate &) const override
Find all matching cells.
virtual void traverse(MemoryCell::Visitor &) override
Traverse and modify cells.
bool mergeWithAliasing(const MemoryStatePtr &other, RiscOperators *addrOps, RiscOperators *valOps)
Merge two states with aliasing.
virtual MemoryStatePtr create(const MemoryCellPtr &protocell) const
Virtual allocating constructor.
virtual MemoryStatePtr create(const SValuePtr &addrProtoval, const SValuePtr &valProtoval) const override
Virtual allocating constructor.
std::list< MemoryCellPtr > CellList
List of memory cells.
Definition: MemoryCell.h:274
virtual SValuePtr readMemory(const SValuePtr &address, const SValuePtr &dflt, RiscOperators *addrOps, RiscOperators *valOps) override
Read a value from memory.
virtual bool merge(const MemoryStatePtr &other, RiscOperators *addrOps, RiscOperators *valOps) override
Merge memory states for data flow analysis.
virtual AddressSet getWritersUnion(const SValuePtr &addr, size_t nBits, RiscOperators *addrOps, RiscOperators *valOps) override
Writers for an address.
Sawyer::SharedPointer< SValue > SValuePtr
Shared-ownership pointer to a semantic value in any domain.
bool mergeNoAliasing(const MemoryStatePtr &other, RiscOperators *addrOps, RiscOperators *valOps)
Merge two states without aliasing.
static MemoryCellListPtr instance(const MemoryCellPtr &protocell)
Instantiate a new memory state with prototypical memory cell.
virtual std::vector< MemoryCellPtr > leadingCells(MemoryCell::Predicate &) const override
Find leading matching cells.
virtual bool isAllPresent(const SValuePtr &address, size_t nBytes, RiscOperators *addrOps, RiscOperators *valOps) const
Predicate to determine whether all bytes are present.
virtual void eraseLeadingCells(MemoryCell::Predicate &) override
Remove leading matching cells.
Base class for most instruction semantics RISC operators.
Definition: RiscOperators.h:49
virtual const CellList & get_cells() const
Returns the list of all memory cells.
virtual AddressSet getWritersIntersection(const SValuePtr &addr, size_t nBits, RiscOperators *addrOps, RiscOperators *valOps) override
Writers for an address.