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