ROSE  0.9.9.109
AddressUsageMap.h
1 #ifndef ROSE_Partitioner2_AddressUsageMap_H
2 #define ROSE_Partitioner2_AddressUsageMap_H
3 
4 #include <Partitioner2/BasicBlock.h>
5 #include <Partitioner2/BasicTypes.h>
6 #include <Partitioner2/DataBlock.h>
7 #include <Partitioner2/OwnedDataBlock.h>
8 
9 #include <Sawyer/IntervalMap.h>
10 #include <Sawyer/IntervalSet.h>
11 #include <Sawyer/Optional.h>
12 
13 #include <boost/serialization/access.hpp>
14 #include <boost/serialization/vector.hpp>
15 
16 #include <algorithm>
17 #include <boost/foreach.hpp>
18 #include <ostream>
19 #include <string>
20 
21 namespace Rose {
22 namespace BinaryAnalysis {
23 namespace Partitioner2 {
24 
30 class AddressUser {
31  SgAsmInstruction *insn_;
32  std::vector<BasicBlock::Ptr> bblocks_;
33  OwnedDataBlock odblock_;
34 
35 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
36 private:
37  friend class boost::serialization::access;
38 
39  template<class S>
40  void serialize(S &s, const unsigned version) {
41  s & BOOST_SERIALIZATION_NVP(insn_);
42  s & BOOST_SERIALIZATION_NVP(bblocks_);
43  s & BOOST_SERIALIZATION_NVP(odblock_);
44  }
45 #endif
46 
47 public:
48  AddressUser(): insn_(NULL) {} // needed by std::vector<AddressUser>, but otherwise unused
49 
55  AddressUser(SgAsmInstruction *insn, const BasicBlock::Ptr &bblock): insn_(insn) {
56  ASSERT_not_null(insn_);
57  if (bblock)
58  bblocks_.push_back(bblock);
59  }
60 
62  AddressUser(const OwnedDataBlock &odblock): insn_(NULL), odblock_(odblock) {}
63 
65  bool isBasicBlock() const { return insn_!=NULL; }
66 
68  bool isDataBlock() const { return odblock_.dataBlock()!=NULL; }
69 
74  return insn_;
75  }
76 
83  return bblocks_.empty() ? BasicBlock::Ptr() : bblocks_[0];
84  }
85 
91  const std::vector<BasicBlock::Ptr>& basicBlocks() const {
92  return bblocks_;
93  }
94 
96  void insertBasicBlock(const BasicBlock::Ptr &bblock);
97 
99  void eraseBasicBlock(const BasicBlock::Ptr &bblock);
100 
105  return odblock_.dataBlock();
106  }
107 
115  return odblock_;
116  }
118  return odblock_;
119  }
128 
134  bool operator==(const AddressUser &other) const;
135 
142  bool operator<(const AddressUser&) const;
143 
145  void print(std::ostream&) const;
146 
150  bool isConsistent() const;
151 };
152 
153 
154 
162  std::vector<AddressUser> users_; // sorted
163 
164 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
165 private:
166  friend class boost::serialization::access;
167 
168  template<class S>
169  void serialize(S &s, const unsigned version) {
170  s & BOOST_SERIALIZATION_NVP(users_);
171  }
172 #endif
173 
174 public:
177 
179  explicit AddressUsers(SgAsmInstruction *insn, const BasicBlock::Ptr &bb) { insertInstruction(insn, bb); }
180 
182  explicit AddressUsers(const OwnedDataBlock &odb) { insertDataBlock(odb); }
183 
184 #if 0 // [Robb P Matzke 2016-06-30]: insn can be owned by multiple blocks now; use instructionExists(rose_addr_t) instead.
185 
189 #endif
190 
195  Sawyer::Optional<AddressUser> instructionExists(rose_addr_t insnStart) const;
196 
201 
207  Sawyer::Optional<OwnedDataBlock> dataBlockExists(rose_addr_t dbStart) const;
208 
214  BasicBlock::Ptr findBasicBlock(rose_addr_t bbVa) const;
215 
221 
227  void insertDataBlock(const OwnedDataBlock&);
228 
233  void insert(const AddressUsers&);
234 
240 
245  void eraseDataBlock(const DataBlock::Ptr&);
246 
250  static bool selectAllUsers(const AddressUser&) { return true; }
251 
256  static bool selectBasicBlocks(const AddressUser &user) { return user.isBasicBlock(); }
257 
262  static bool selectDataBlocks(const AddressUser &user) { return user.isDataBlock(); }
263 
267  template<class UserPredicate>
268  AddressUsers select(UserPredicate predicate) const {
269  AddressUsers retval;
270  BOOST_FOREACH (const AddressUser &user, users_) {
271  if (predicate(user))
272  retval.users_.push_back(user);
273  }
274  return retval;
275  }
276 
280  const std::vector<AddressUser>& addressUsers() const { return users_; }
281 
286 
291 
297  std::vector<SgAsmInstruction*> instructions() const;
298 
304  std::vector<BasicBlock::Ptr> instructionOwners() const;
305 
309  std::vector<DataBlock::Ptr> dataBlocks() const;
310 
312  size_t size() const { return users_.size(); }
313 
317  bool isEmpty() const { return users_.empty(); }
318 
320  AddressUsers intersection(const AddressUsers&) const;
321 
323  AddressUsers union_(const AddressUsers&) const;
324 
326  bool operator==(const AddressUsers &other) const;
327 
329  void print(std::ostream&) const;
330 
334  bool isConsistent() const;
335 
336 protected:
337  std::vector<AddressUser>::iterator findInstruction(SgAsmInstruction*);
338 };
339 
340 
341 
349  Map map_;
350 
351 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
352 private:
353  friend class boost::serialization::access;
354 
355  template<class S>
356  void serialize(S &s, const unsigned version) {
357  s & BOOST_SERIALIZATION_NVP(map_);
358  }
359 #endif
360 
361 public:
366  bool isEmpty() const { return map_.isEmpty(); }
367 
369  void clear() { map_.clear(); }
370 
374  size_t size() const { return map_.size(); }
375 
380  AddressInterval hull() const { return map_.hull(); }
381 
385  AddressIntervalSet extent() const;
386 
392  bool exists(rose_addr_t va) const { return map_.exists(va); }
393 
401  bool anyExists(const AddressInterval&) const;
402  bool anyExists(const AddressIntervalSet&) const;
412  AddressIntervalSet unusedExtent(size_t nBits) const;
422  AddressInterval nextUnused(rose_addr_t minVa) const;
423 
427  bool instructionExists(SgAsmInstruction*) const;
428 
433  Sawyer::Optional<AddressUser> instructionExists(rose_addr_t startOfInsn) const;
434 
440  BasicBlock::Ptr basicBlockExists(rose_addr_t startOfBlock) const;
441 
446  OwnedDataBlock dataBlockExists(rose_addr_t startOfBlock) const;
447 
453 
462  AddressUsers spanning(const AddressInterval &interval) const {
463  return spanning(interval, AddressUsers::selectAllUsers);
464  }
465 
466  template<class UserPredicate>
467  AddressUsers spanning(const AddressInterval &interval, UserPredicate userPredicate) const {
468  AddressUsers retval;
469  size_t nIters = 0;
470  BOOST_FOREACH (const Map::Node &node, map_.findAll(interval)) {
471  AddressUsers users = node.value().select(userPredicate);
472  retval = 0==nIters++ ? users : retval.intersection(users);
473  if (retval.isEmpty())
474  break;
475  }
476  return retval;
477  }
489  AddressUsers overlapping(const AddressInterval &interval) const {
490  return overlapping(interval, AddressUsers::selectAllUsers);
491  }
492 
493  template<class UserPredicate>
494  AddressUsers overlapping(const AddressInterval &interval, UserPredicate userPredicate) const {
495  AddressUsers retval;
496  BOOST_FOREACH (const Map::Node &node, map_.findAll(interval))
497  retval.insert(node.value().select(userPredicate));
498  return retval;
499  }
511  AddressUsers containedIn(const AddressInterval &interval) const {
512  return containedIn(interval, AddressUsers::selectAllUsers);
513  }
514 
515  template<class UserPredicate>
516  AddressUsers containedIn(const AddressInterval &interval, UserPredicate userPredicate) const;
517  // FIXME[Robb P. Matzke 2014-08-26]: not implemented yet
525  Sawyer::Optional<rose_addr_t> leastUnmapped(rose_addr_t startVa) const {
526  return map_.leastUnmapped(startVa);
527  }
528 
532  void print(std::ostream&, const std::string &prefix="") const;
533 private:
534  friend class Partitioner;
535 
536  // Insert an instruction/block pair into the map.
537  void insertInstruction(SgAsmInstruction*, const BasicBlock::Ptr&);
538 
539  // Insert a data block into the map. The data block must not be a null pointer and must not already exist in the map. A
540  // data pointer is always inserted along with ownership information--which functions and basic blocks own this data block.
541  void insertDataBlock(const OwnedDataBlock&);
542 
543  // Remove an instruction/block pair from the map. If the instruction exists in the map then the specified block is removed
544  // from the instruction's owner list. If this results in an empty owner list then the instruction is also removed.
545  // If the pointer is null or the instruction/block pair does not exist in the map, then this is a no-op.
546  void eraseInstruction(SgAsmInstruction*, const BasicBlock::Ptr&);
547 
548  // Remove a data block from the map. The specified data block is removed from the map. If the pointer is null or the data
549  // block does not exist in the map, then this is a no-op.
550  void eraseDataBlock(const DataBlock::Ptr&);
551 };
552 
553 } // namespace
554 } // namespace
555 } // namespace
556 
557 #endif
AddressUsers overlapping(const AddressInterval &interval) const
Users that overlap the interval.
std::vector< SgAsmInstruction * > instructions() const
Returns all instructions.
size_t size() const
Number of addresses represented by the map.
bool isEmpty() const
Determines whether this address user list is empty.
void insert(const AddressUsers &)
Inser a user.
void clear()
Reset map to initial empty state.
Value & value()
Value part of key/value node.
Definition: Sawyer/Map.h:103
Base class for machine instructions.
BasicBlock::Ptr firstBasicBlock() const
Returns an arbitrary basic block.
AddressUsers(const OwnedDataBlock &odb)
Constructs a list having one data block user.
void insertBasicBlock(const BasicBlock::Ptr &bblock)
Add another basic block to the set of basic blocks.
Holds a value or nothing.
Definition: Optional.h:49
void print(std::ostream &, const std::string &prefix="") const
Dump the contents of this AUM to a stream.
AddressUsers union_(const AddressUsers &) const
Computes the union of this list with another.
AddressUsers spanning(const AddressInterval &interval, UserPredicate userPredicate) const
Find address users that span the entire interval.
OwnedDataBlock dataBlockExists(rose_addr_t startOfBlock) const
Determines if an address is the start of a data block.
const std::vector< BasicBlock::Ptr > & basicBlocks() const
Returns all basic blocks to which this instruction belongs.
Main namespace for the ROSE library.
void eraseBasicBlock(const BasicBlock::Ptr &bblock)
Remove a basic block from the set of basic blocks.
Interval::Value size() const
Returns the number of values represented by this container.
Definition: IntervalMap.h:681
bool isEmpty() const
Determine if the container is empty.
Definition: IntervalMap.h:665
const std::vector< AddressUser > & addressUsers() const
Return all address users.
bool isConsistent() const
Perform logic consistency checks.
AddressInterval nextUnused(rose_addr_t minVa) const
Next unused address interval.
AddressUser(SgAsmInstruction *insn, const BasicBlock::Ptr &bblock)
Constructs new user which is an instruction and its basic block.
bool isBasicBlock() const
Predicate returning true if user is a basic block or instruction.
static bool selectDataBlocks(const AddressUser &user)
Selector to select data blocks.
SgAsmInstruction * insn() const
Return the instruction.
AddressUsers overlapping(const AddressInterval &interval, UserPredicate userPredicate) const
Users that overlap the interval.
Optional< typename Interval::Value > leastUnmapped(typename Interval::Value lowerLimit) const
Returns the limited-minimum unmapped scalar key.
Definition: IntervalMap.h:724
AddressUser(const OwnedDataBlock &odblock)
Constructs a new user which is a data block.
std::vector< DataBlock::Ptr > dataBlocks() const
Returns all data blocks.
AddressUsers instructionUsers() const
Returns all instruction users.
bool operator==(const AddressUsers &other) const
True if two lists are equal.
std::vector< BasicBlock::Ptr > instructionOwners() const
Returns all basic blocks.
OwnedDataBlock & dataBlockOwnership()
Return the data block ownership information.
static bool selectBasicBlocks(const AddressUser &user)
Selector to select instructions and basic blocks.
bool exists(const typename Interval::Value &size) const
Returns true if element exists.
Definition: IntervalMap.h:579
void clear()
Empties the container.
Definition: IntervalMap.h:764
DataBlock::Ptr dataBlock() const
Returns the data block for this ownership record.
bool instructionExists(SgAsmInstruction *) const
Determines whether an instruction exists in the map.
void print(std::ostream &) const
Prints pairs space separated on a single line.
BasicBlock::Ptr isBlockEntry() const
Determines if this user is a first instruction of a basic block.
void print(std::ostream &) const
Print the pair on one line.
AddressIntervalSet unusedExtent(size_t nBits) const
Addresses not represented.
BasicBlock::Ptr findBasicBlock(rose_addr_t bbVa) const
Find the basic block that starts at this address.
const OwnedDataBlock & dataBlockOwnership() const
Return the data block ownership information.
AddressUsers(SgAsmInstruction *insn, const BasicBlock::Ptr &bb)
Constructs a list having one instruction user.
void eraseInstruction(SgAsmInstruction *, const BasicBlock::Ptr &)
Erase an instruction/basic block pair from the list.
AddressUsers spanning(const AddressInterval &interval) const
Find address users that span the entire interval.
bool exists(rose_addr_t va) const
Predicate to determine whether an address is used.
bool isDataBlock() const
Predicate returning true if user is a data block.
AddressInterval hull() const
Minimum and maximum used addresses.
Interval hull() const
Returns the range of values in this map.
Definition: IntervalMap.h:753
AddressUsers containedIn(const AddressInterval &interval) const
Users that are fully contained in the interval.
DataBlock::Ptr dataBlock() const
Returns the data block.
boost::iterator_range< NodeIterator > findAll(const Interval &interval)
Finds all nodes overlapping the specified interval.
Definition: IntervalMap.h:390
bool operator<(const AddressUser &) const
Compare two users for sorting.
Sawyer::Optional< rose_addr_t > leastUnmapped(rose_addr_t startVa) const
Returns the least unmapped address with specified lower limit.
void eraseDataBlock(const DataBlock::Ptr &)
Erase a data block user.
Sawyer::SharedPointer< BasicBlock > Ptr
Shared pointer to a basic block.
Definition: BasicBlock.h:37
AddressUsers select(UserPredicate predicate) const
Selects certain users from a list.
Sawyer::Optional< AddressUser > instructionExists(rose_addr_t insnStart) const
Determines if an instruction exists in the list.
void insertInstruction(SgAsmInstruction *, const BasicBlock::Ptr &)
Insert an instruction/basic block pair.
AddressUsers intersection(const AddressUsers &) const
Computes the intersection of this list with another.
AddressIntervalSet extent() const
Addresses represented.
bool operator==(const AddressUser &other) const
Compare two users for equality.
void insertDataBlock(const OwnedDataBlock &)
Insert a data block.
bool isEmpty() const
Determines whether a map is empty.
Partitions instructions into basic blocks and functions.
Definition: Partitioner.h:289
bool anyExists(const AddressInterval &) const
Predicate to determine whether any of the specified addresses are used.
size_t size() const
Number of address users.
static bool selectAllUsers(const AddressUser &)
Selector to select all users.
bool isConsistent() const
Check logical consistency.
AddressUsers dataBlockUsers() const
Returns all data block users.
Sawyer::Optional< OwnedDataBlock > dataBlockExists(const DataBlock::Ptr &) const
Determines if a data block exists in the list.
Type for stored nodes.
Definition: Sawyer/Map.h:87
BasicBlock::Ptr basicBlockExists(rose_addr_t startOfBlock) const
Determines if an address is the start of a basic block.