ROSE  0.9.11.56
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 
8 #include <Sawyer/IntervalMap.h>
9 #include <Sawyer/IntervalSet.h>
10 #include <Sawyer/Optional.h>
11 
12 #include <boost/serialization/access.hpp>
13 #include <boost/serialization/vector.hpp>
14 
15 #include <algorithm>
16 #include <boost/foreach.hpp>
17 #include <ostream>
18 #include <string>
19 
20 namespace Rose {
21 namespace BinaryAnalysis {
22 namespace Partitioner2 {
23 
25 // AddressUser
27 
33 class AddressUser {
34  SgAsmInstruction *insn_;
35  std::vector<BasicBlock::Ptr> bblocks_; // sorted and unique
36  DataBlock::Ptr dblock_;
37 
38 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
39 private:
40  friend class boost::serialization::access;
41 
42  template<class S>
43  void serialize(S &s, const unsigned version) {
44  s & BOOST_SERIALIZATION_NVP(insn_);
45  s & BOOST_SERIALIZATION_NVP(bblocks_);
46  if (version < 1) {
47  ASSERT_not_reachable("Rose::BinaryAnalysis::Partitioner2::AddressUser version 0 no longer supported");
48  } else {
49  s & BOOST_SERIALIZATION_NVP(dblock_);
50  }
51  }
52 #endif
53 
54 public:
56  AddressUser(): insn_(NULL) {}
57 
63  AddressUser(SgAsmInstruction *insn, const BasicBlock::Ptr &bblock): insn_(insn) {
64  ASSERT_not_null(insn_);
65  if (bblock)
66  bblocks_.push_back(bblock);
67  }
68 
70  explicit AddressUser(const DataBlockPtr &dblock)
71  : insn_(NULL), dblock_(dblock) {
72  ASSERT_not_null(dblock);
73  }
74 
79  rose_addr_t address() const;
80 
82  bool isBasicBlock() const { return insn_ != NULL; }
83 
85  bool isDataBlock() const { return dblock_ != NULL; }
86 
90  bool isEmpty() const {
91  return NULL == insn_ && NULL == dblock_;
92  }
93 
98  return insn_;
99  }
100 
106  return bblocks_.empty() ? BasicBlock::Ptr() : bblocks_[0];
107  }
108 
114  const std::vector<BasicBlock::Ptr>& basicBlocks() const {
115  return bblocks_;
116  }
117 
119  void insertBasicBlock(const BasicBlock::Ptr &bblock);
120 
122  void eraseBasicBlock(const BasicBlock::Ptr &bblock);
123 
128  return dblock_;
129  }
130 
137 
143  bool operator==(const AddressUser &other) const;
144 
151  bool operator<(const AddressUser&) const;
152 
154  void print(std::ostream&) const;
155 
159  bool isConsistent() const;
160 
164  operator bool() const {
165  return !isEmpty();
166  }
167 };
168 
169 
171 // AddressUsers
173 
180  std::vector<AddressUser> users_; // sorted
181 
182 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
183 private:
184  friend class boost::serialization::access;
185 
186  template<class S>
187  void serialize(S &s, const unsigned /*version*/) {
188  s & BOOST_SERIALIZATION_NVP(users_);
189  }
190 #endif
191 
192 public:
195 
197  explicit AddressUsers(SgAsmInstruction *insn, const BasicBlock::Ptr &bb) {
198  insertInstruction(insn, bb);
199  }
200 
202  explicit AddressUsers(const DataBlock::Ptr &db) {
203  insertDataBlock(db);
204  }
205 
214  SgAsmInstruction* instructionExists(rose_addr_t va) const;
225  BasicBlock::Ptr basicBlockExists(rose_addr_t va) const;
236  DataBlock::Ptr dataBlockExists(rose_addr_t va, rose_addr_t size) const;
247  AddressUser findInstruction(rose_addr_t va) const;
259  AddressUser findBasicBlock(rose_addr_t va) const;
270  AddressUser findDataBlock(rose_addr_t va, rose_addr_t size) const;
278 
284 
286  void insert(const AddressUsers&);
287 
293 
299 
303  static bool selectAllUsers(const AddressUser&) {
304  return true;
305  }
306 
311  static bool selectBasicBlocks(const AddressUser &user) {
312  return user.isBasicBlock();
313  }
314 
319  static bool selectDataBlocks(const AddressUser &user) {
320  return user.isDataBlock();
321  }
322 
326  template<class UserPredicate>
327  AddressUsers select(UserPredicate predicate) const {
328  AddressUsers retval;
329  BOOST_FOREACH (const AddressUser &user, users_) {
330  if (predicate(user))
331  retval.users_.push_back(user);
332  }
333  return retval;
334  }
335 
339  const std::vector<AddressUser>& addressUsers() const {
340  return users_;
341  }
342 
347  return select(selectBasicBlocks);
348  }
349 
354  return select(selectDataBlocks);
355  }
356 
362  std::vector<SgAsmInstruction*> instructions() const;
363 
369  std::vector<BasicBlock::Ptr> instructionOwners() const;
370 
374  std::vector<DataBlock::Ptr> dataBlocks() const;
375 
377  size_t size() const {
378  return users_.size();
379  }
380 
384  bool isEmpty() const {
385  return users_.empty();
386  }
387 
389  AddressUsers intersection(const AddressUsers&) const;
390 
392  AddressUsers union_(const AddressUsers&) const;
393 
395  bool operator==(const AddressUsers &other) const;
396 
398  void print(std::ostream&) const;
399 
403  bool isConsistent() const;
404 };
405 
406 
408 // AddressUsageMap
410 
418  Map map_;
419 
420 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
421 private:
422  friend class boost::serialization::access;
423 
424  template<class S>
425  void serialize(S &s, const unsigned /*version*/) {
426  s & BOOST_SERIALIZATION_NVP(map_);
427  }
428 #endif
429 
430 public:
435  bool isEmpty() const {
436  return map_.isEmpty();
437  }
438 
440  void clear() {
441  map_.clear();
442  }
443 
447  size_t size() const {
448  return map_.size();
449  }
450 
456  return map_.hull();
457  }
458 
462  AddressIntervalSet extent() const;
463 
469  bool exists(rose_addr_t va) const {
470  return map_.exists(va);
471  }
472 
480  bool anyExists(const AddressInterval&) const;
481  bool anyExists(const AddressIntervalSet&) const;
491  AddressIntervalSet unusedExtent(size_t nBits) const;
501  AddressInterval nextUnused(rose_addr_t minVa) const;
502 
509  SgAsmInstruction* instructionExists(rose_addr_t va) const;
521  BasicBlock::Ptr basicBlockExists(rose_addr_t startOfBlock) const;
531  DataBlock::Ptr dataBlockExists(rose_addr_t va, rose_addr_t size) const;
542  AddressUser findInstruction(rose_addr_t va) const;
554  AddressUser findBasicBlock(rose_addr_t va) const;
565  AddressUser findDataBlock(rose_addr_t va, rose_addr_t size) const;
574 
580 
587 
592 
601  AddressUsers spanning(const AddressInterval &interval) const {
602  return spanning(interval, AddressUsers::selectAllUsers);
603  }
604 
605  template<class UserPredicate>
606  AddressUsers spanning(const AddressInterval &interval, UserPredicate userPredicate) const {
607  AddressUsers retval;
608  size_t nIters = 0;
609  BOOST_FOREACH (const Map::Node &node, map_.findAll(interval)) {
610  AddressUsers users = node.value().select(userPredicate);
611  retval = 0==nIters++ ? users : retval.intersection(users);
612  if (retval.isEmpty())
613  break;
614  }
615  return retval;
616  }
628  AddressUsers overlapping(const AddressInterval &interval) const {
629  return overlapping(interval, AddressUsers::selectAllUsers);
630  }
631 
632  template<class UserPredicate>
633  AddressUsers overlapping(const AddressInterval &interval, UserPredicate userPredicate) const {
634  AddressUsers retval;
635  BOOST_FOREACH (const Map::Node &node, map_.findAll(interval))
636  retval.insert(node.value().select(userPredicate));
637  return retval;
638  }
650  AddressUsers containedIn(const AddressInterval &interval) const {
651  return containedIn(interval, AddressUsers::selectAllUsers);
652  }
653 
654  template<class UserPredicate>
655  AddressUsers containedIn(const AddressInterval &interval, UserPredicate userPredicate) const;
656  // FIXME[Robb P. Matzke 2014-08-26]: not implemented yet
664  Sawyer::Optional<rose_addr_t> leastUnmapped(rose_addr_t startVa) const {
665  return map_.leastUnmapped(startVa);
666  }
667 
671  void print(std::ostream&, const std::string &prefix="") const;
672 
676  void checkConsistency() const;
677 };
678 
679 } // namespace
680 } // namespace
681 } // namespace
682 
683 // Class versions must be at global scope
685 
686 #endif
SgAsmInstruction * instructionExists(SgAsmInstruction *) const
Determines whether the specified instruction or an equivalent exists.
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 &)
Insert one set of address users into another.
DataBlock::Ptr dataBlockExists(const DataBlock::Ptr &) const
Determines whether the specified data block or an equivalent exists.
void clear()
Reset map to initial empty state.
AddressUser findDataBlock(const DataBlock::Ptr &) const
Find an AddressUser record for the specified data block, or equivalent.
AddressUser()
Default constructed user is empty.
rose_addr_t address() const
Address of user.
Value & value()
Value part of key/value node.
Definition: Sawyer/Map.h:105
Base class for machine instructions.
BasicBlock::Ptr firstBasicBlock() const
Returns an arbitrary basic block.
DataBlock::Ptr dataBlockExists(const DataBlock::Ptr &) const
Determines if a data block exists.
void insertBasicBlock(const BasicBlock::Ptr &bblock)
Add another basic block to the set of basic blocks.
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.
const std::vector< BasicBlock::Ptr > & basicBlocks() const
Returns all basic blocks to which this instruction belongs.
Main namespace for the ROSE library.
AddressUser findBasicBlock(const BasicBlock::Ptr &) const
Find an AddressUser record for the specified basic block, or equivalent.
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
DataBlock::Ptr eraseDataBlock(const DataBlock::Ptr &)
Remove the specified data block.
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
SgAsmInstruction * eraseInstruction(SgAsmInstruction *, const BasicBlock::Ptr &)
Remove the specified instruction/basic block pair.
std::vector< DataBlock::Ptr > dataBlocks() const
Returns all data blocks.
AddressUser findBasicBlock(const BasicBlock::Ptr &) const
Find an AddressUser record for the specified basic block, or equivalent.
AddressUsers instructionUsers() const
Returns all instruction users.
bool operator==(const AddressUsers &other) const
True if two lists are equal.
AddressUser findDataBlock(const DataBlock::Ptr &) const
Find an AddressUser record for the specified data block, or equivalent.
std::vector< BasicBlock::Ptr > instructionOwners() const
Returns all basic blocks.
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
AddressUsers(const DataBlock::Ptr &db)
Constructs a list having one data block user.
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.
AddressUser insertDataBlock(const DataBlock::Ptr &)
Insert a data block.
AddressUsers(SgAsmInstruction *insn, const BasicBlock::Ptr &bb)
Constructs a list having one instruction user.
AddressUsers spanning(const AddressInterval &interval) const
Find address users that span the entire interval.
AddressUser insertDataBlock(const DataBlock::Ptr &)
Insert the data block.
void checkConsistency() const
Check invariants.
bool exists(rose_addr_t va) const
Predicate to determine whether an address is used.
AddressUser(const DataBlockPtr &dblock)
Constructs a new user which is a data block.
bool isDataBlock() const
Predicate returning true if user is a data block.
AddressInterval hull() const
Minimum and maximum used addresses.
SgAsmInstruction * instructionExists(SgAsmInstruction *) const
Determines whether the specified instruction or an equivalent exists.
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.
SgAsmInstruction * eraseInstruction(SgAsmInstruction *, const BasicBlock::Ptr &)
Erase an instruction/basic block pair from this list.
BasicBlock::Ptr basicBlockExists(const BasicBlock::Ptr &) const
Determine if a basic block exists.
Sawyer::SharedPointer< BasicBlock > Ptr
Shared pointer to a basic block.
Definition: BasicBlock.h:131
AddressUsers select(UserPredicate predicate) const
Selects certain users from a list.
BasicBlock::Ptr basicBlockExists(const BasicBlock::Ptr &) const
Determines whether the specified basic block or an equivalent exists.
AddressUser findInstruction(SgAsmInstruction *) const
Find an AddressUser record for the specified instruction, or equivalent.
DataBlock::Ptr eraseDataBlock(const DataBlock::Ptr &)
Erase a data block from this list.
AddressUsers intersection(const AddressUsers &) const
Computes the intersection of this list with another.
AddressIntervalSet extent() const
Addresses represented.
bool isEmpty() const
True if this object was default constructed.
bool operator==(const AddressUser &other) const
Compare two users for equality.
AddressUser insertInstruction(SgAsmInstruction *, const BasicBlock::Ptr &)
Insert the instruction along with an owning basic block.
AddressUser findInstruction(SgAsmInstruction *) const
Find an AddressUser record for the specified instruction, or equivalent.
bool isEmpty() const
Determines whether a map is empty.
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.
AddressUser insertInstruction(SgAsmInstruction *, const BasicBlock::Ptr &)
Insert an instruction/basic block pair.
Type for stored nodes.
Definition: Sawyer/Map.h:89