ROSE  0.11.57.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 
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 <boost/foreach.hpp>
19 #include <ostream>
20 #include <string>
21 
22 namespace Rose {
23 namespace BinaryAnalysis {
24 namespace Partitioner2 {
25 
27 // AddressUser
29 
35 class AddressUser {
36  SgAsmInstruction *insn_;
37  std::vector<BasicBlock::Ptr> bblocks_; // sorted and unique
38  DataBlock::Ptr dblock_;
39 
40 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
41 private:
42  friend class boost::serialization::access;
43 
44  template<class S>
45  void serialize(S &s, const unsigned version) {
46  s & BOOST_SERIALIZATION_NVP(insn_);
47  s & BOOST_SERIALIZATION_NVP(bblocks_);
48  if (version < 1) {
49  ASSERT_not_reachable("Rose::BinaryAnalysis::Partitioner2::AddressUser version 0 no longer supported");
50  } else {
51  s & BOOST_SERIALIZATION_NVP(dblock_);
52  }
53  }
54 #endif
55 
56 public:
58  AddressUser(): insn_(NULL) {}
59 
65  AddressUser(SgAsmInstruction *insn, const BasicBlock::Ptr &bblock): insn_(insn) {
66  ASSERT_not_null(insn_);
67  if (bblock)
68  bblocks_.push_back(bblock);
69  }
70 
72  explicit AddressUser(const DataBlockPtr &dblock)
73  : insn_(NULL), dblock_(dblock) {
74  ASSERT_not_null(dblock);
75  }
76 
81  rose_addr_t address() const;
82 
84  bool isBasicBlock() const { return insn_ != NULL; }
85 
87  bool isDataBlock() const { return dblock_ != NULL; }
88 
92  bool isEmpty() const {
93  return NULL == insn_ && NULL == dblock_;
94  }
95 
100  return insn_;
101  }
102 
108  return bblocks_.empty() ? BasicBlock::Ptr() : bblocks_[0];
109  }
110 
116  const std::vector<BasicBlock::Ptr>& basicBlocks() const {
117  return bblocks_;
118  }
119 
121  void insertBasicBlock(const BasicBlock::Ptr &bblock);
122 
124  void eraseBasicBlock(const BasicBlock::Ptr &bblock);
125 
130  return dblock_;
131  }
132 
139 
145  bool operator==(const AddressUser &other) const;
146 
153  bool operator<(const AddressUser&) const;
154 
156  void print(std::ostream&) const;
157 
161  bool isConsistent() const;
162 
166  operator bool() const {
167  return !isEmpty();
168  }
169 };
170 
171 
173 // AddressUsers
175 
182  std::vector<AddressUser> users_; // sorted
183 
184 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
185 private:
186  friend class boost::serialization::access;
187 
188  template<class S>
189  void serialize(S &s, const unsigned /*version*/) {
190  s & BOOST_SERIALIZATION_NVP(users_);
191  }
192 #endif
193 
194 public:
197 
199  explicit AddressUsers(SgAsmInstruction *insn, const BasicBlock::Ptr &bb) {
200  insertInstruction(insn, bb);
201  }
202 
204  explicit AddressUsers(const DataBlock::Ptr &db) {
205  insertDataBlock(db);
206  }
207 
216  SgAsmInstruction* instructionExists(rose_addr_t va) const;
227  BasicBlock::Ptr basicBlockExists(rose_addr_t va) const;
238  DataBlock::Ptr dataBlockExists(rose_addr_t va, rose_addr_t size) const;
249  AddressUser findInstruction(rose_addr_t va) const;
261  AddressUser findBasicBlock(rose_addr_t va) const;
272  AddressUser findDataBlock(rose_addr_t va, rose_addr_t size) const;
280 
286 
288  void insert(const AddressUsers&);
289 
295 
301 
305  static bool selectAllUsers(const AddressUser&) {
306  return true;
307  }
308 
313  static bool selectBasicBlocks(const AddressUser &user) {
314  return user.isBasicBlock();
315  }
316 
321  static bool selectDataBlocks(const AddressUser &user) {
322  return user.isDataBlock();
323  }
324 
328  template<class UserPredicate>
329  AddressUsers select(UserPredicate predicate) const {
330  AddressUsers retval;
331  BOOST_FOREACH (const AddressUser &user, users_) {
332  if (predicate(user))
333  retval.users_.push_back(user);
334  }
335  return retval;
336  }
337 
341  const std::vector<AddressUser>& addressUsers() const {
342  return users_;
343  }
344 
349  return select(selectBasicBlocks);
350  }
351 
356  return select(selectDataBlocks);
357  }
358 
364  std::vector<SgAsmInstruction*> instructions() const;
365 
371  std::vector<BasicBlock::Ptr> instructionOwners() const;
372 
376  std::vector<DataBlock::Ptr> dataBlocks() const;
377 
379  size_t size() const {
380  return users_.size();
381  }
382 
386  bool isEmpty() const {
387  return users_.empty();
388  }
389 
391  AddressUsers intersection(const AddressUsers&) const;
392 
394  AddressUsers union_(const AddressUsers&) const;
395 
397  bool operator==(const AddressUsers &other) const;
398 
400  void print(std::ostream&) const;
401 
405  bool isConsistent() const;
406 };
407 
408 
410 // AddressUsageMap
412 
420  Map map_;
421 
422 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
423 private:
424  friend class boost::serialization::access;
425 
426  template<class S>
427  void serialize(S &s, const unsigned /*version*/) {
428  s & BOOST_SERIALIZATION_NVP(map_);
429  }
430 #endif
431 
432 public:
437  bool isEmpty() const {
438  return map_.isEmpty();
439  }
440 
442  void clear() {
443  map_.clear();
444  }
445 
449  size_t size() const {
450  return map_.size();
451  }
452 
458  return map_.hull();
459  }
460 
464  AddressIntervalSet extent() const;
465 
471  bool exists(rose_addr_t va) const {
472  return map_.exists(va);
473  }
474 
482  bool anyExists(const AddressInterval&) const;
483  bool anyExists(const AddressIntervalSet&) const;
493  AddressIntervalSet unusedExtent(size_t nBits) const;
503  AddressInterval nextUnused(rose_addr_t minVa) const;
504 
511  SgAsmInstruction* instructionExists(rose_addr_t va) const;
523  BasicBlock::Ptr basicBlockExists(rose_addr_t startOfBlock) const;
533  DataBlock::Ptr dataBlockExists(rose_addr_t va, rose_addr_t size) const;
544  AddressUser findInstruction(rose_addr_t va) const;
556  AddressUser findBasicBlock(rose_addr_t va) const;
567  AddressUser findDataBlock(rose_addr_t va, rose_addr_t size) const;
576 
582 
589 
594 
603  AddressUsers spanning(const AddressInterval &interval) const {
604  return spanning(interval, AddressUsers::selectAllUsers);
605  }
606 
607  template<class UserPredicate>
608  AddressUsers spanning(const AddressInterval &interval, UserPredicate userPredicate) const {
609  AddressUsers retval;
610  size_t nIters = 0;
611  BOOST_FOREACH (const Map::Node &node, map_.findAll(interval)) {
612  AddressUsers users = node.value().select(userPredicate);
613  retval = 0==nIters++ ? users : retval.intersection(users);
614  if (retval.isEmpty())
615  break;
616  }
617  return retval;
618  }
630  AddressUsers overlapping(const AddressInterval &interval) const {
631  return overlapping(interval, AddressUsers::selectAllUsers);
632  }
633 
634  template<class UserPredicate>
635  AddressUsers overlapping(const AddressInterval &interval, UserPredicate userPredicate) const {
636  AddressUsers retval;
637  BOOST_FOREACH (const Map::Node &node, map_.findAll(interval))
638  retval.insert(node.value().select(userPredicate));
639  return retval;
640  }
652  AddressUsers containedIn(const AddressInterval &interval) const {
653  return containedIn(interval, AddressUsers::selectAllUsers);
654  }
655 
656  template<class UserPredicate>
657  AddressUsers containedIn(const AddressInterval &interval, UserPredicate userPredicate) const;
658  // FIXME[Robb P. Matzke 2014-08-26]: not implemented yet
666  Sawyer::Optional<rose_addr_t> leastUnmapped(rose_addr_t startVa) const {
667  return map_.leastUnmapped(startVa);
668  }
669 
673  void print(std::ostream&, const std::string &prefix="") const;
674 
678  void checkConsistency() const;
679 };
680 
681 } // namespace
682 } // namespace
683 } // namespace
684 
685 // Class versions must be at global scope
687 
688 #endif
689 #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.
A container holding a set of values.
Definition: IntervalSet.h:55
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