ROSE  0.11.83.2
AddressUsageMap.h
1 #ifndef ROSE_BinaryAnalysis_Partitioner2_AddressUsageMap_H
2 #define ROSE_BinaryAnalysis_Partitioner2_AddressUsageMap_H
3 #include <featureTests.h>
4 #ifdef ROSE_ENABLE_BINARY_ANALYSIS
5 
6 #include <Rose/BinaryAnalysis/Partitioner2/BasicBlock.h>
7 #include <Rose/BinaryAnalysis/Partitioner2/BasicTypes.h>
8 #include <Rose/BinaryAnalysis/Partitioner2/DataBlock.h>
9 
10 #include <Sawyer/IntervalMap.h>
11 #include <Sawyer/IntervalSet.h>
12 #include <Sawyer/Optional.h>
13 
14 #include <boost/serialization/access.hpp>
15 #include <boost/serialization/vector.hpp>
16 
17 #include <algorithm>
18 #include <ostream>
19 #include <string>
20 
21 namespace Rose {
22 namespace BinaryAnalysis {
23 namespace Partitioner2 {
24 
26 // AddressUser
28 
34 class AddressUser {
35  SgAsmInstruction *insn_;
36  std::vector<BasicBlock::Ptr> bblocks_; // sorted and unique
37  DataBlock::Ptr dblock_;
38 
39 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
40 private:
41  friend class boost::serialization::access;
42 
43  template<class S>
44  void serialize(S &s, const unsigned version) {
45  s & BOOST_SERIALIZATION_NVP(insn_);
46  s & BOOST_SERIALIZATION_NVP(bblocks_);
47  if (version < 1) {
48  ASSERT_not_reachable("Rose::BinaryAnalysis::Partitioner2::AddressUser version 0 no longer supported");
49  } else {
50  s & BOOST_SERIALIZATION_NVP(dblock_);
51  }
52  }
53 #endif
54 
55 public:
57  AddressUser(): insn_(NULL) {}
58 
64  AddressUser(SgAsmInstruction *insn, const BasicBlock::Ptr &bblock): insn_(insn) {
65  ASSERT_not_null(insn_);
66  if (bblock)
67  bblocks_.push_back(bblock);
68  }
69 
71  explicit AddressUser(const DataBlockPtr &dblock)
72  : insn_(NULL), dblock_(dblock) {
73  ASSERT_not_null(dblock);
74  }
75 
80  rose_addr_t address() const;
81 
83  bool isBasicBlock() const { return insn_ != NULL; }
84 
86  bool isDataBlock() const { return dblock_ != NULL; }
87 
91  bool isEmpty() const {
92  return NULL == insn_ && NULL == dblock_;
93  }
94 
99  return insn_;
100  }
101 
107  return bblocks_.empty() ? BasicBlock::Ptr() : bblocks_[0];
108  }
109 
115  const std::vector<BasicBlock::Ptr>& basicBlocks() const {
116  return bblocks_;
117  }
118 
120  void insertBasicBlock(const BasicBlock::Ptr &bblock);
121 
123  void eraseBasicBlock(const BasicBlock::Ptr &bblock);
124 
129  return dblock_;
130  }
131 
138 
144  bool operator==(const AddressUser &other) const;
145 
152  bool operator<(const AddressUser&) const;
153 
155  void print(std::ostream&) const;
156 
160  bool isConsistent() const;
161 
165  operator bool() const {
166  return !isEmpty();
167  }
168 };
169 
170 
172 // AddressUsers
174 
181  std::vector<AddressUser> users_; // sorted
182 
183 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
184 private:
185  friend class boost::serialization::access;
186 
187  template<class S>
188  void serialize(S &s, const unsigned /*version*/) {
189  s & BOOST_SERIALIZATION_NVP(users_);
190  }
191 #endif
192 
193 public:
196 
198  explicit AddressUsers(SgAsmInstruction *insn, const BasicBlock::Ptr &bb) {
199  insertInstruction(insn, bb);
200  }
201 
203  explicit AddressUsers(const DataBlock::Ptr &db) {
204  insertDataBlock(db);
205  }
206 
215  SgAsmInstruction* instructionExists(rose_addr_t va) const;
226  BasicBlock::Ptr basicBlockExists(rose_addr_t va) const;
237  DataBlock::Ptr dataBlockExists(rose_addr_t va, rose_addr_t size) const;
248  AddressUser findInstruction(rose_addr_t va) const;
260  AddressUser findBasicBlock(rose_addr_t va) const;
271  AddressUser findDataBlock(rose_addr_t va, rose_addr_t size) const;
279 
285 
287  void insert(const AddressUsers&);
288 
294 
300 
304  static bool selectAllUsers(const AddressUser&) {
305  return true;
306  }
307 
312  static bool selectBasicBlocks(const AddressUser &user) {
313  return user.isBasicBlock();
314  }
315 
320  static bool selectDataBlocks(const AddressUser &user) {
321  return user.isDataBlock();
322  }
323 
327  template<class UserPredicate>
328  AddressUsers select(UserPredicate predicate) const {
329  AddressUsers retval;
330  for (const AddressUser &user: users_) {
331  if (predicate(user))
332  retval.users_.push_back(user);
333  }
334  return retval;
335  }
336 
340  const std::vector<AddressUser>& addressUsers() const {
341  return users_;
342  }
343 
348  return select(selectBasicBlocks);
349  }
350 
355  return select(selectDataBlocks);
356  }
357 
363  std::vector<SgAsmInstruction*> instructions() const;
364 
370  std::vector<BasicBlock::Ptr> instructionOwners() const;
371 
375  std::vector<DataBlock::Ptr> dataBlocks() const;
376 
378  size_t size() const {
379  return users_.size();
380  }
381 
385  bool isEmpty() const {
386  return users_.empty();
387  }
388 
390  AddressUsers intersection(const AddressUsers&) const;
391 
393  AddressUsers union_(const AddressUsers&) const;
394 
396  bool operator==(const AddressUsers &other) const;
397 
399  void print(std::ostream&) const;
400 
404  bool isConsistent() const;
405 };
406 
407 
409 // AddressUsageMap
411 
419  Map map_;
420 
421 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
422 private:
423  friend class boost::serialization::access;
424 
425  template<class S>
426  void serialize(S &s, const unsigned /*version*/) {
427  s & BOOST_SERIALIZATION_NVP(map_);
428  }
429 #endif
430 
431 public:
436  bool isEmpty() const {
437  return map_.isEmpty();
438  }
439 
441  void clear() {
442  map_.clear();
443  }
444 
448  size_t size() const {
449  return map_.size();
450  }
451 
457  return map_.hull();
458  }
459 
463  AddressIntervalSet extent() const;
464 
470  bool exists(rose_addr_t va) const {
471  return map_.exists(va);
472  }
473 
481  bool anyExists(const AddressInterval&) const;
482  bool anyExists(const AddressIntervalSet&) const;
492  AddressIntervalSet unusedExtent(size_t nBits) const;
502  AddressInterval nextUnused(rose_addr_t minVa) const;
503 
510  SgAsmInstruction* instructionExists(rose_addr_t va) const;
522  BasicBlock::Ptr basicBlockExists(rose_addr_t startOfBlock) const;
532  DataBlock::Ptr dataBlockExists(rose_addr_t va, rose_addr_t size) const;
543  AddressUser findInstruction(rose_addr_t va) const;
555  AddressUser findBasicBlock(rose_addr_t va) const;
566  AddressUser findDataBlock(rose_addr_t va, rose_addr_t size) const;
575 
581 
588 
593 
602  AddressUsers spanning(const AddressInterval &interval) const {
603  return spanning(interval, AddressUsers::selectAllUsers);
604  }
605 
606  template<class UserPredicate>
607  AddressUsers spanning(const AddressInterval &interval, UserPredicate userPredicate) const {
608  AddressUsers retval;
609  size_t nIters = 0;
610  for (const Map::Node &node: map_.findAll(interval)) {
611  AddressUsers users = node.value().select(userPredicate);
612  retval = 0==nIters++ ? users : retval.intersection(users);
613  if (retval.isEmpty())
614  break;
615  }
616  return retval;
617  }
629  AddressUsers overlapping(const AddressInterval &interval) const {
630  return overlapping(interval, AddressUsers::selectAllUsers);
631  }
632 
633  template<class UserPredicate>
634  AddressUsers overlapping(const AddressInterval &interval, UserPredicate userPredicate) const {
635  AddressUsers retval;
636  for (const Map::Node &node: map_.findAll(interval))
637  retval.insert(node.value().select(userPredicate));
638  return retval;
639  }
651  AddressUsers containedIn(const AddressInterval &interval) const {
652  return containedIn(interval, AddressUsers::selectAllUsers);
653  }
654 
655  template<class UserPredicate>
656  AddressUsers containedIn(const AddressInterval &interval, UserPredicate userPredicate) const;
657  // FIXME[Robb P. Matzke 2014-08-26]: not implemented yet
665  Sawyer::Optional<rose_addr_t> leastUnmapped(rose_addr_t startVa) const {
666  return map_.leastUnmapped(startVa);
667  }
668 
672  void print(std::ostream&, const std::string &prefix="") const;
673 
677  void checkConsistency() const;
678 };
679 
680 } // namespace
681 } // namespace
682 } // namespace
683 
684 // Class versions must be at global scope
686 
687 #endif
688 #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.
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:134
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