ROSE  0.11.123.0
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 #include <Rose/BinaryAnalysis/Partitioner2/BasicTypes.h>
6 
7 #include <Sawyer/IntervalMap.h>
8 #include <Sawyer/IntervalSet.h>
9 #include <Sawyer/Optional.h>
10 
11 #include <boost/serialization/access.hpp>
12 #include <boost/serialization/vector.hpp>
13 
14 #include <algorithm>
15 #include <ostream>
16 #include <string>
17 
18 namespace Rose {
19 namespace BinaryAnalysis {
20 namespace Partitioner2 {
21 
23 // AddressUser
25 
31 class AddressUser {
32  SgAsmInstruction *insn_;
33  std::vector<BasicBlockPtr> bblocks_; // sorted and unique
34  DataBlockPtr dblock_;
35 
36 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
37 private:
38  friend class boost::serialization::access;
39 
40  template<class S>
41  void serialize(S &s, const unsigned version) {
42  s & BOOST_SERIALIZATION_NVP(insn_);
43  s & BOOST_SERIALIZATION_NVP(bblocks_);
44  if (version < 1) {
45  ASSERT_not_reachable("Rose::BinaryAnalysis::Partitioner2::AddressUser version 0 no longer supported");
46  } else {
47  s & BOOST_SERIALIZATION_NVP(dblock_);
48  }
49  }
50 #endif
51 
52 public:
54  AddressUser();
55 
62 
64  explicit AddressUser(const DataBlockPtr&);
65 
66  ~AddressUser();
67 
72  rose_addr_t address() const;
73 
75  bool isBasicBlock() const;
76 
78  bool isDataBlock() const;
79 
83  bool isEmpty() const;
84 
88  SgAsmInstruction* insn() const;
89 
95 
101  const std::vector<BasicBlockPtr>& basicBlocks() const;
102 
104  void insertBasicBlock(const BasicBlockPtr &bblock);
105 
107  void eraseBasicBlock(const BasicBlockPtr &bblock);
108 
112  DataBlockPtr dataBlock() const;
113 
119  BasicBlockPtr isBlockEntry() const;
120 
126  bool operator==(const AddressUser &other) const;
127 
134  bool operator<(const AddressUser&) const;
135 
137  void print(std::ostream&) const;
138 
142  bool isConsistent() const;
143 
147  operator bool() const {
148  return !isEmpty();
149  }
150 };
151 
152 
154 // AddressUsers
156 
163  std::vector<AddressUser> users_; // sorted
164 
165 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
166 private:
167  friend class boost::serialization::access;
168 
169  template<class S>
170  void serialize(S &s, const unsigned /*version*/) {
171  s & BOOST_SERIALIZATION_NVP(users_);
172  }
173 #endif
174 
175 public:
177  AddressUsers();
178  ~AddressUsers();
179 
181  explicit AddressUsers(SgAsmInstruction *insn, const BasicBlockPtr&);
182 
184  explicit AddressUsers(const DataBlockPtr&);
185 
194  SgAsmInstruction* instructionExists(rose_addr_t va) const;
205  BasicBlockPtr basicBlockExists(rose_addr_t va) const;
216  DataBlockPtr dataBlockExists(rose_addr_t va, rose_addr_t size) const;
227  AddressUser findInstruction(rose_addr_t va) const;
239  AddressUser findBasicBlock(rose_addr_t va) const;
249  AddressUser findDataBlock(const DataBlockPtr&) const;
250  AddressUser findDataBlock(rose_addr_t va, rose_addr_t size) const;
258 
264 
266  void insert(const AddressUsers&);
267 
273 
279 
283  static bool selectAllUsers(const AddressUser&);
284 
289  static bool selectBasicBlocks(const AddressUser&);
290 
295  static bool selectDataBlocks(const AddressUser&);
296 
300  template<class UserPredicate>
301  AddressUsers select(UserPredicate predicate) const {
302  AddressUsers retval;
303  for (const AddressUser &user: users_) {
304  if (predicate(user))
305  retval.users_.push_back(user);
306  }
307  return retval;
308  }
309 
313  const std::vector<AddressUser>& addressUsers() const;
314 
319 
324 
330  std::vector<SgAsmInstruction*> instructions() const;
331 
337  std::vector<BasicBlockPtr> instructionOwners() const;
338 
342  std::vector<DataBlockPtr> dataBlocks() const;
343 
345  size_t size() const;
346 
350  bool isEmpty() const;
351 
353  AddressUsers intersection(const AddressUsers&) const;
354 
356  AddressUsers union_(const AddressUsers&) const;
357 
359  bool operator==(const AddressUsers &other) const;
360 
362  void print(std::ostream&) const;
363 
367  bool isConsistent() const;
368 };
369 
370 
372 // AddressUsageMap
374 
382  Map map_;
383 
384 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
385 private:
386  friend class boost::serialization::access;
387 
388  template<class S>
389  void serialize(S &s, const unsigned /*version*/) {
390  s & BOOST_SERIALIZATION_NVP(map_);
391  }
392 #endif
393 
394 public:
395  AddressUsageMap();
396  ~AddressUsageMap();
397 
398 public:
403  bool isEmpty() const;
404 
406  void clear();
407 
411  size_t size() const;
412 
417  AddressInterval hull() const;
418 
422  AddressIntervalSet extent() const;
423 
429  bool exists(rose_addr_t) const;
430 
438  bool anyExists(const AddressInterval&) const;
439  bool anyExists(const AddressIntervalSet&) const;
449  AddressIntervalSet unusedExtent(size_t nBits) const;
459  AddressInterval nextUnused(rose_addr_t minVa) const;
460 
467  SgAsmInstruction* instructionExists(rose_addr_t va) const;
479  BasicBlockPtr basicBlockExists(rose_addr_t startOfBlock) const;
489  DataBlockPtr dataBlockExists(rose_addr_t va, rose_addr_t size) const;
500  AddressUser findInstruction(rose_addr_t va) const;
512  AddressUser findBasicBlock(rose_addr_t va) const;
522  AddressUser findDataBlock(const DataBlockPtr&) const;
523  AddressUser findDataBlock(rose_addr_t va, rose_addr_t size) const;
532 
538 
545 
550 
559  AddressUsers spanning(const AddressInterval&) const;
560 
561  template<class UserPredicate>
562  AddressUsers spanning(const AddressInterval &interval, UserPredicate userPredicate) const {
563  AddressUsers retval;
564  size_t nIters = 0;
565  for (const Map::Node &node: map_.findAll(interval)) {
566  AddressUsers users = node.value().select(userPredicate);
567  retval = 0==nIters++ ? users : retval.intersection(users);
568  if (retval.isEmpty())
569  break;
570  }
571  return retval;
572  }
585 
586  template<class UserPredicate>
587  AddressUsers overlapping(const AddressInterval &interval, UserPredicate userPredicate) const {
588  AddressUsers retval;
589  for (const Map::Node &node: map_.findAll(interval))
590  retval.insert(node.value().select(userPredicate));
591  return retval;
592  }
604  // FIXME[Robb P. Matzke 2014-08-26]: not implemented yet
606 
607  //template<class UserPredicate>
608  //AddressUsers containedIn(const AddressInterval &interval, UserPredicate userPredicate) const {...}
616  Sawyer::Optional<rose_addr_t> leastUnmapped(rose_addr_t startVa) const;
617 
621  void print(std::ostream&, const std::string &prefix="") const;
622 
626  void checkConsistency() const;
627 };
628 
629 } // namespace
630 } // namespace
631 } // namespace
632 
633 // Class versions must be at global scope
635 
636 #endif
637 #endif
SgAsmInstruction * instructionExists(SgAsmInstruction *) const
Determines whether the specified instruction or an equivalent exists.
AddressUser insertDataBlock(const DataBlockPtr &)
Insert the data block.
void insertBasicBlock(const BasicBlockPtr &bblock)
Add another basic block to the set of basic blocks.
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.
DataBlockPtr dataBlock() const
Returns the data block.
static bool selectDataBlocks(const AddressUser &)
Selector to select data blocks.
AddressUsers overlapping(const AddressInterval &) const
Users that overlap the interval.
void clear()
Reset map to initial empty state.
AddressUser findBasicBlock(const BasicBlockPtr &) const
Find an AddressUser record for the specified basic block, or equivalent.
BasicBlockPtr isBlockEntry() const
Determines if this user is a first instruction of a basic block.
AddressUser()
Default constructed user is empty.
rose_addr_t address() const
Address of user.
Base class for machine instructions.
BasicBlockPtr basicBlockExists(const BasicBlockPtr &) const
Determine if a basic block exists.
AddressUser insertInstruction(SgAsmInstruction *, const BasicBlockPtr &)
Insert an instruction/basic block pair.
static bool selectBasicBlocks(const AddressUser &)
Selector to select instructions and 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.
DataBlockPtr dataBlockExists(const DataBlockPtr &) const
Determines if a data block exists.
AddressUsers spanning(const AddressInterval &interval, UserPredicate userPredicate) const
Find address users that span the entire interval.
Main namespace for the ROSE library.
const std::vector< AddressUser > & addressUsers() const
Return all address users.
SgAsmInstruction * eraseInstruction(SgAsmInstruction *, const BasicBlockPtr &)
Remove the specified instruction/basic block pair.
bool isConsistent() const
Perform logic consistency checks.
AddressInterval nextUnused(rose_addr_t minVa) const
Next unused address interval.
AddressUser findDataBlock(const DataBlockPtr &) const
Find an AddressUser record for the specified data block, or equivalent.
bool isBasicBlock() const
Predicate returning true if user is a basic block or instruction.
std::vector< DataBlockPtr > dataBlocks() const
Returns all data blocks.
SgAsmInstruction * insn() const
Return the instruction.
AddressUsers overlapping(const AddressInterval &interval, UserPredicate userPredicate) const
Users that overlap the interval.
AddressUsers instructionUsers() const
Returns all instruction users.
bool operator==(const AddressUsers &other) const
True if two lists are equal.
AddressUser findBasicBlock(const BasicBlockPtr &) const
Find an AddressUser record for the specified basic block, or equivalent.
void print(std::ostream &) const
Prints pairs space separated on a single line.
void eraseBasicBlock(const BasicBlockPtr &bblock)
Remove a basic block from the set of basic blocks.
void print(std::ostream &) const
Print the pair on one line.
AddressIntervalSet unusedExtent(size_t nBits) const
Addresses not represented.
BasicBlockPtr basicBlockExists(const BasicBlockPtr &) const
Determines whether the specified basic block or an equivalent exists.
void checkConsistency() const
Check invariants.
bool isDataBlock() const
Predicate returning true if user is a data block.
const std::vector< BasicBlockPtr > & basicBlocks() const
Returns all basic blocks to which this instruction belongs.
AddressInterval hull() const
Minimum and maximum used addresses.
SgAsmInstruction * instructionExists(SgAsmInstruction *) const
Determines whether the specified instruction or an equivalent exists.
BasicBlockPtr firstBasicBlock() const
Returns an arbitrary basic 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.
DataBlockPtr dataBlockExists(const DataBlockPtr &) const
Determines whether the specified data block or an equivalent exists.
AddressUsers select(UserPredicate predicate) const
Selects certain users from a list.
bool exists(rose_addr_t) const
Predicate to determine whether an address is used.
DataBlockPtr eraseDataBlock(const DataBlockPtr &)
Remove the specified data block.
AddressUser findInstruction(SgAsmInstruction *) const
Find an AddressUser record for the specified instruction, or equivalent.
AddressUser findDataBlock(const DataBlockPtr &) const
Find an AddressUser record for the specified data block, or equivalent.
SgAsmInstruction * eraseInstruction(SgAsmInstruction *, const BasicBlockPtr &)
Erase an instruction/basic block pair 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 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.
std::vector< BasicBlockPtr > instructionOwners() const
Returns all basic blocks.
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.
AddressUsers spanning(const AddressInterval &) const
Find address users that span the entire interval.
AddressUser insertInstruction(SgAsmInstruction *, const BasicBlockPtr &)
Insert the instruction along with an owning basic block.
DataBlockPtr eraseDataBlock(const DataBlockPtr &)
Erase a data block from this list.
AddressUsers containedIn(const AddressInterval &) const
Users that are fully contained in the interval.
Type for stored nodes.
Definition: Sawyer/Map.h:89
AddressUser insertDataBlock(const DataBlockPtr &)
Insert a data block.