ROSE  0.9.10.44
MemoryCellList.h
1 #ifndef ROSE_BinaryAnalysis_InstructionSemantics2_MemoryCellList_H
2 #define ROSE_BinaryAnalysis_InstructionSemantics2_MemoryCellList_H
3 
4 #include <BaseSemantics2.h>
5 #include <MemoryCellState.h>
6 
7 #include <boost/serialization/access.hpp>
8 #include <boost/serialization/base_object.hpp>
9 #include <boost/serialization/export.hpp>
10 
11 namespace Rose {
12 namespace BinaryAnalysis {
13 namespace InstructionSemantics2 {
14 namespace BaseSemantics {
15 
17 typedef boost::shared_ptr<class MemoryCellList> MemoryCellListPtr;
18 
38 public:
39  typedef std::list<MemoryCellPtr> CellList;
41 protected:
42  CellList cells; // list of cells in reverse chronological order
43  bool occlusionsErased_; // prune away old cells that are occluded by newer ones.
44 
46  // Serialization
47 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
48 private:
49  friend class boost::serialization::access;
50 
51  template<class S>
52  void serialize(S &s, const unsigned /*version*/) {
53  s & BOOST_SERIALIZATION_BASE_OBJECT_NVP(MemoryCellState);
54  s & BOOST_SERIALIZATION_NVP(cells);
55  s & BOOST_SERIALIZATION_NVP(occlusionsErased_);
56  }
57 #endif
58 
60  // Real constructors
61 protected:
62  MemoryCellList() // for serialization
63  : occlusionsErased_(false) {}
64 
65  explicit MemoryCellList(const MemoryCellPtr &protocell)
66  : MemoryCellState(protocell), occlusionsErased_(false) {}
67 
68  MemoryCellList(const SValuePtr &addrProtoval, const SValuePtr &valProtoval)
69  : MemoryCellState(addrProtoval, valProtoval), occlusionsErased_(false) {}
70 
71  // deep-copy cell list so that modifying this new state does not modify the existing state
72  MemoryCellList(const MemoryCellList &other)
73  : MemoryCellState(other), occlusionsErased_(other.occlusionsErased_) {
74  for (CellList::const_iterator ci=other.cells.begin(); ci!=other.cells.end(); ++ci)
75  cells.push_back((*ci)->clone());
76  }
77 
79  // Static allocating constructors
80 public:
84  static MemoryCellListPtr instance(const SValuePtr &addrProtoval, const SValuePtr &valProtoval) {
85  return MemoryCellListPtr(new MemoryCellList(addrProtoval, valProtoval));
86  }
87 
89  static MemoryCellListPtr instance(const MemoryCellPtr &protocell) {
90  return MemoryCellListPtr(new MemoryCellList(protocell));
91  }
92 
94  static MemoryCellListPtr instance(const MemoryCellListPtr &other) {
95  return MemoryCellListPtr(new MemoryCellList(*other));
96  }
97 
98 
100  // Virtual constructors
101 public:
102  virtual MemoryStatePtr create(const SValuePtr &addrProtoval, const SValuePtr &valProtoval) const ROSE_OVERRIDE {
103  return instance(addrProtoval, valProtoval);
104  }
105 
107  virtual MemoryStatePtr create(const MemoryCellPtr &protocell) const {
108  return instance(protocell);
109  }
110 
111  virtual MemoryStatePtr clone() const ROSE_OVERRIDE {
112  return MemoryStatePtr(new MemoryCellList(*this));
113  }
114 
116  // Dynamic pointer casts
117 public:
120  static MemoryCellListPtr promote(const BaseSemantics::MemoryStatePtr &m) {
121  MemoryCellListPtr retval = boost::dynamic_pointer_cast<MemoryCellList>(m);
122  ASSERT_not_null(retval);
123  return retval;
124  }
125 
127  // Methods we inherited
128 public:
129  virtual void clear() ROSE_OVERRIDE;
130  virtual bool merge(const MemoryStatePtr &other, RiscOperators *addrOps, RiscOperators *valOps) ROSE_OVERRIDE;
131  virtual std::vector<MemoryCellPtr> matchingCells(const MemoryCell::Predicate&) const ROSE_OVERRIDE;
132  virtual std::vector<MemoryCellPtr> leadingCells(const MemoryCell::Predicate&) const ROSE_OVERRIDE;
133  virtual void eraseMatchingCells(const MemoryCell::Predicate&) ROSE_OVERRIDE;
134  virtual void eraseLeadingCells(const MemoryCell::Predicate&) ROSE_OVERRIDE;
135  virtual void traverse(MemoryCell::Visitor&) ROSE_OVERRIDE;
136 
147  virtual SValuePtr readMemory(const SValuePtr &address, const SValuePtr &dflt,
148  RiscOperators *addrOps, RiscOperators *valOps) ROSE_OVERRIDE;
149 
150  virtual SValuePtr peekMemory(const SValuePtr &address, const SValuePtr &dflt,
151  RiscOperators *addrOps, RiscOperators *valOps) ROSE_OVERRIDE;
152 
159  virtual void writeMemory(const SValuePtr &addr, const SValuePtr &value,
160  RiscOperators *addrOps, RiscOperators *valOps) ROSE_OVERRIDE;
161 
162  virtual void print(std::ostream&, Formatter&) const ROSE_OVERRIDE;
163 
165  // Methods first declared at this level of the class hierarchy
166 public:
171  bool mergeNoAliasing(const MemoryStatePtr &other, RiscOperators *addrOps, RiscOperators *valOps);
172 
177  bool mergeWithAliasing(const MemoryStatePtr &other, RiscOperators *addrOps, RiscOperators *valOps);
178 
183  virtual bool isAllPresent(const SValuePtr &address, size_t nBytes, RiscOperators *addrOps, RiscOperators *valOps) const;
184 
191  bool occlusionsErased() const { return occlusionsErased_; }
192  void occlusionsErased(bool b) { occlusionsErased_ = b; }
210  template<class Iterator>
211  CellList scan(Iterator &cursor /*in,out*/, const SValuePtr &addr, size_t nBits,
212  RiscOperators *addrOps, RiscOperators *valOps) const {
213  ASSERT_not_null(addr);
214  CellList retval;
215  MemoryCellPtr tempCell = protocell->create(addr, valOps->undefined_(nBits));
216  for (/*void*/; cursor!=cells.end(); ++cursor) {
217  if (tempCell->may_alias(*cursor, addrOps)) {
218  retval.push_back(*cursor);
219  if (tempCell->must_alias(*cursor, addrOps))
220  break;
221  }
222  }
223  return retval;
224  }
225 
226  // [Robb P. Matzke 2015-08-18]: deprecated
227  virtual CellList scan(const SValuePtr &address, size_t nbits, RiscOperators *addrOps, RiscOperators *valOps,
228  bool &short_circuited/*out*/) const ROSE_DEPRECATED("use the cursor-based scan instead");
229 
232  virtual const CellList& get_cells() const { return cells; }
233  virtual CellList& get_cells() { return cells; }
236  // [Robb Matzke 2015-12-26]: deprecated
237  virtual MemoryCellPtr get_latest_written_cell() const ROSE_DEPRECATED("use latestWrittenCell instead") {
238  return latestWrittenCell();
239  }
240 
241  virtual MemoryCell::AddressSet getWritersUnion(const SValuePtr &addr, size_t nBits, RiscOperators *addrOps,
242  RiscOperators *valOps) ROSE_OVERRIDE;
243 
244  virtual MemoryCell::AddressSet getWritersIntersection(const SValuePtr &addr, size_t nBits, RiscOperators *addrOps,
245  RiscOperators *valOps) ROSE_OVERRIDE;
246 
247  // [Robb P. Matzke 2015-08-17]: deprecated
248  virtual std::set<rose_addr_t> get_latest_writers(const SValuePtr &addr, size_t nbits,
249  RiscOperators *addrOps, RiscOperators *valOps)
250  ROSE_DEPRECATED("use getWritersUnion instead");
251 
252 
253 protected:
254  // Compute a new value by merging the specified cells. If the cell list is empty return the specified default.
255  virtual SValuePtr mergeCellValues(const CellList &cells, const SValuePtr &dflt, RiscOperators *addrOps,
256  RiscOperators *valOps);
257 
258  // Returns the union of all writers from the specified cells.
259  virtual AddressSet mergeCellWriters(const CellList &cells);
260 
261  // Returns the union of all properties from the specified cells.
262  virtual InputOutputPropertySet mergeCellProperties(const CellList &cells);
263 
264  // Adjust I/O properties in the specified cells to make it look like they were just read. This adds the READ property and
265  // may also add READ_AFTER_WRITE, READ_BEFORE_WRITE, and/or READ_UNINITIALIZED.
266  virtual void updateReadProperties(CellList &cells);
267 
268  // Insert a new cell at the head of the list. It's writers set is empty and its I/O properties will be READ,
269  // READ_BEFORE_WRITE, and READ_UNINITIALIZED.
270  virtual MemoryCellPtr insertReadCell(const SValuePtr &addr, const SValuePtr &value);
271 
272  // Insert a new cell at the head of the list. The specified writers and I/O properties are used.
273  virtual MemoryCellPtr insertReadCell(const SValuePtr &addr, const SValuePtr &value,
274  const AddressSet &writers, const InputOutputPropertySet &props);
275 };
276 
277 } // namespace
278 } // namespace
279 } // namespace
280 } // namespace
281 
282 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
284 #endif
285 
286 #endif
boost::shared_ptr< class MemoryCell > MemoryCellPtr
Shared-ownership pointer to a semantic memory cell.
Definition: MemoryCell.h:15
virtual SValuePtr readMemory(const SValuePtr &address, const SValuePtr &dflt, RiscOperators *addrOps, RiscOperators *valOps) ROSE_OVERRIDE
Read a value from memory.
virtual SValuePtr undefined_(size_t nbits)
Returns a new undefined value.
virtual const CellList & get_cells() const
Returns the list of all memory cells.
virtual void writeMemory(const SValuePtr &addr, const SValuePtr &value, RiscOperators *addrOps, RiscOperators *valOps) ROSE_OVERRIDE
Write a value to memory.
bool mergeWithAliasing(const MemoryStatePtr &other, RiscOperators *addrOps, RiscOperators *valOps)
Merge two states with aliasing.
STL namespace.
virtual SValuePtr peekMemory(const SValuePtr &address, const SValuePtr &dflt, RiscOperators *addrOps, RiscOperators *valOps) ROSE_OVERRIDE
Read a value from memory without side effects.
Main namespace for the ROSE library.
static MemoryCellListPtr instance(const MemoryCellPtr &protocell)
Instantiate a new memory state with prototypical memory cell.
Sawyer::Container::Set< rose_addr_t > AddressSet
A set of concrete virtual addresses.
Definition: MemoryCell.h:26
virtual MemoryCell::AddressSet getWritersUnion(const SValuePtr &addr, size_t nBits, RiscOperators *addrOps, RiscOperators *valOps) ROSE_OVERRIDE
Writers for an address.
virtual MemoryStatePtr create(const MemoryCellPtr &protocell) const
Virtual allocating constructor.
boost::shared_ptr< class MemoryCellList > MemoryCellListPtr
Shared-ownership pointer to a list-based memory state.
virtual MemoryStatePtr clone() const ROSE_OVERRIDE
Virtual allocating copy constructor.
Base classes for instruction semantics.
Sawyer::Container::Set< rose_addr_t > AddressSet
Set of concrete virtual addresses.
static MemoryCellListPtr instance(const SValuePtr &addrProtoval, const SValuePtr &valProtoval)
Instantiate a new prototypical memory state.
Sawyer::SharedPointer< class SValue > SValuePtr
Shared-ownership pointer to a semantic value in any domain.
Base class for most instruction semantics RISC operators.
virtual void traverse(MemoryCell::Visitor &) ROSE_OVERRIDE
Traverse and modify cells.
virtual void print(std::ostream &, Formatter &) const ROSE_OVERRIDE
Print a memory state to more than one line of output.
CellList scan(Iterator &cursor, const SValuePtr &addr, size_t nBits, RiscOperators *addrOps, RiscOperators *valOps) const
Scan cell list to find matching cells.
virtual MemoryCell::AddressSet getWritersIntersection(const SValuePtr &addr, size_t nBits, RiscOperators *addrOps, RiscOperators *valOps) ROSE_OVERRIDE
Writers for an address.
std::list< MemoryCellPtr > CellList
List of memory cells.
virtual CellList & get_cells()
Returns the list of all memory cells.
boost::shared_ptr< class MemoryState > MemoryStatePtr
Shared-ownership pointer to a memory state.
virtual std::vector< MemoryCellPtr > leadingCells(const MemoryCell::Predicate &) const ROSE_OVERRIDE
Find leading matching cells.
virtual void eraseMatchingCells(const MemoryCell::Predicate &) ROSE_OVERRIDE
Remove all matching cells.
bool mergeNoAliasing(const MemoryStatePtr &other, RiscOperators *addrOps, RiscOperators *valOps)
Merge two states without aliasing.
virtual void eraseLeadingCells(const MemoryCell::Predicate &) ROSE_OVERRIDE
Remove leading matching cells.
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.
Sawyer::Container::Set< InputOutputProperty > InputOutputPropertySet
Set of Boolean properties.
virtual std::vector< MemoryCellPtr > matchingCells(const MemoryCell::Predicate &) const ROSE_OVERRIDE
Find all matching cells.
virtual MemoryCellPtr latestWrittenCell() const
Property: Cell most recently written.
virtual MemoryStatePtr create(const SValuePtr &addrProtoval, const SValuePtr &valProtoval) const ROSE_OVERRIDE
Virtual allocating constructor.
virtual bool merge(const MemoryStatePtr &other, RiscOperators *addrOps, RiscOperators *valOps) ROSE_OVERRIDE
Merge memory states for data flow analysis.
virtual bool isAllPresent(const SValuePtr &address, size_t nBytes, RiscOperators *addrOps, RiscOperators *valOps) const
Predicate to determine whether all bytes are present.