ROSE  0.11.2.0
AddressUsageMap.h
1 #ifndef ROSE_Partitioner2_AddressUsageMap_H
2 #define ROSE_Partitioner2_AddressUsageMap_H
3 
4 #include <rosePublicConfig.h>
5 #ifdef ROSE_BUILD_BINARY_ANALYSIS_SUPPORT
6 
7 #include <Partitioner2/BasicBlock.h>
8 #include <Partitioner2/BasicTypes.h>
9 #include <Partitioner2/DataBlock.h>
10 
11 #include <Sawyer/IntervalMap.h>
12 #include <Sawyer/IntervalSet.h>
13 #include <Sawyer/Optional.h>
14 
15 #include <boost/serialization/access.hpp>
16 #include <boost/serialization/vector.hpp>
17 
18 #include <algorithm>
19 #include <boost/foreach.hpp>
20 #include <ostream>
21 #include <string>
22 
23 namespace Rose {
24 namespace BinaryAnalysis {
25 namespace Partitioner2 {
26 
28 // AddressUser
30 
36 class AddressUser {
37  SgAsmInstruction *insn_;
38  std::vector<BasicBlock::Ptr> bblocks_; // sorted and unique
39  DataBlock::Ptr dblock_;
40 
41 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
42 private:
43  friend class boost::serialization::access;
44 
45  template<class S>
46  void serialize(S &s, const unsigned version) {
47  s & BOOST_SERIALIZATION_NVP(insn_);
48  s & BOOST_SERIALIZATION_NVP(bblocks_);
49  if (version < 1) {
50  ASSERT_not_reachable("Rose::BinaryAnalysis::Partitioner2::AddressUser version 0 no longer supported");
51  } else {
52  s & BOOST_SERIALIZATION_NVP(dblock_);
53  }
54  }
55 #endif
56 
57 public:
59  AddressUser(): insn_(NULL) {}
60 
66  AddressUser(SgAsmInstruction *insn, const BasicBlock::Ptr &bblock): insn_(insn) {
67  ASSERT_not_null(insn_);
68  if (bblock)
69  bblocks_.push_back(bblock);
70  }
71 
73  explicit AddressUser(const DataBlockPtr &dblock)
74  : insn_(NULL), dblock_(dblock) {
75  ASSERT_not_null(dblock);
76  }
77 
82  rose_addr_t address() const;
83 
85  bool isBasicBlock() const { return insn_ != NULL; }
86 
88  bool isDataBlock() const { return dblock_ != NULL; }
89 
93  bool isEmpty() const {
94  return NULL == insn_ && NULL == dblock_;
95  }
96 
101  return insn_;
102  }
103 
109  return bblocks_.empty() ? BasicBlock::Ptr() : bblocks_[0];
110  }
111 
117  const std::vector<BasicBlock::Ptr>& basicBlocks() const {
118  return bblocks_;
119  }
120 
122  void insertBasicBlock(const BasicBlock::Ptr &bblock);
123 
125  void eraseBasicBlock(const BasicBlock::Ptr &bblock);
126 
131  return dblock_;
132  }
133 
140 
146  bool operator==(const AddressUser &other) const;
147 
154  bool operator<(const AddressUser&) const;
155 
157  void print(std::ostream&) const;
158 
162  bool isConsistent() const;
163 
167  operator bool() const {
168  return !isEmpty();
169  }
170 };
171 
172 
174 // AddressUsers
176 
183  std::vector<AddressUser> users_; // sorted
184 
185 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
186 private:
187  friend class boost::serialization::access;
188 
189  template<class S>
190  void serialize(S &s, const unsigned /*version*/) {
191  s & BOOST_SERIALIZATION_NVP(users_);
192  }
193 #endif
194 
195 public:
198 
200  explicit AddressUsers(SgAsmInstruction *insn, const BasicBlock::Ptr &bb) {
201  insertInstruction(insn, bb);
202  }
203 
205  explicit AddressUsers(const DataBlock::Ptr &db) {
206  insertDataBlock(db);
207  }
208 
217  SgAsmInstruction* instructionExists(rose_addr_t va) const;
228  BasicBlock::Ptr basicBlockExists(rose_addr_t va) const;
239  DataBlock::Ptr dataBlockExists(rose_addr_t va, rose_addr_t size) const;
250  AddressUser findInstruction(rose_addr_t va) const;
262  AddressUser findBasicBlock(rose_addr_t va) const;
273  AddressUser findDataBlock(rose_addr_t va, rose_addr_t size) const;
281 
287 
289  void insert(const AddressUsers&);
290 
296 
302 
306  static bool selectAllUsers(const AddressUser&) {
307  return true;
308  }
309 
314  static bool selectBasicBlocks(const AddressUser &user) {
315  return user.isBasicBlock();
316  }
317 
322  static bool selectDataBlocks(const AddressUser &user) {
323  return user.isDataBlock();
324  }
325 
329  template<class UserPredicate>
330  AddressUsers select(UserPredicate predicate) const {
331  AddressUsers retval;
332  BOOST_FOREACH (const AddressUser &user, users_) {
333  if (predicate(user))
334  retval.users_.push_back(user);
335  }
336  return retval;
337  }
338 
342  const std::vector<AddressUser>& addressUsers() const {
343  return users_;
344  }
345 
350  return select(selectBasicBlocks);
351  }
352 
357  return select(selectDataBlocks);
358  }
359 
365  std::vector<SgAsmInstruction*> instructions() const;
366 
372  std::vector<BasicBlock::Ptr> instructionOwners() const;
373 
377  std::vector<DataBlock::Ptr> dataBlocks() const;
378 
380  size_t size() const {
381  return users_.size();
382  }
383 
387  bool isEmpty() const {
388  return users_.empty();
389  }
390 
392  AddressUsers intersection(const AddressUsers&) const;
393 
395  AddressUsers union_(const AddressUsers&) const;
396 
398  bool operator==(const AddressUsers &other) const;
399 
401  void print(std::ostream&) const;
402 
406  bool isConsistent() const;
407 };
408 
409 
411 // AddressUsageMap
413 
421  Map map_;
422 
423 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
424 private:
425  friend class boost::serialization::access;
426 
427  template<class S>
428  void serialize(S &s, const unsigned /*version*/) {
429  s & BOOST_SERIALIZATION_NVP(map_);
430  }
431 #endif
432 
433 public:
438  bool isEmpty() const {
439  return map_.isEmpty();
440  }
441 
443  void clear() {
444  map_.clear();
445  }
446 
450  size_t size() const {
451  return map_.size();
452  }
453 
459  return map_.hull();
460  }
461 
465  AddressIntervalSet extent() const;
466 
472  bool exists(rose_addr_t va) const {
473  return map_.exists(va);
474  }
475 
483  bool anyExists(const AddressInterval&) const;
484  bool anyExists(const AddressIntervalSet&) const;
494  AddressIntervalSet unusedExtent(size_t nBits) const;
504  AddressInterval nextUnused(rose_addr_t minVa) const;
505 
512  SgAsmInstruction* instructionExists(rose_addr_t va) const;
524  BasicBlock::Ptr basicBlockExists(rose_addr_t startOfBlock) const;
534  DataBlock::Ptr dataBlockExists(rose_addr_t va, rose_addr_t size) const;
545  AddressUser findInstruction(rose_addr_t va) const;
557  AddressUser findBasicBlock(rose_addr_t va) const;
568  AddressUser findDataBlock(rose_addr_t va, rose_addr_t size) const;
577 
583 
590 
595 
604  AddressUsers spanning(const AddressInterval &interval) const {
605  return spanning(interval, AddressUsers::selectAllUsers);
606  }
607 
608  template<class UserPredicate>
609  AddressUsers spanning(const AddressInterval &interval, UserPredicate userPredicate) const {
610  AddressUsers retval;
611  size_t nIters = 0;
612  BOOST_FOREACH (const Map::Node &node, map_.findAll(interval)) {
613  AddressUsers users = node.value().select(userPredicate);
614  retval = 0==nIters++ ? users : retval.intersection(users);
615  if (retval.isEmpty())
616  break;
617  }
618  return retval;
619  }
631  AddressUsers overlapping(const AddressInterval &interval) const {
632  return overlapping(interval, AddressUsers::selectAllUsers);
633  }
634 
635  template<class UserPredicate>
636  AddressUsers overlapping(const AddressInterval &interval, UserPredicate userPredicate) const {
637  AddressUsers retval;
638  BOOST_FOREACH (const Map::Node &node, map_.findAll(interval))
639  retval.insert(node.value().select(userPredicate));
640  return retval;
641  }
653  AddressUsers containedIn(const AddressInterval &interval) const {
654  return containedIn(interval, AddressUsers::selectAllUsers);
655  }
656 
657  template<class UserPredicate>
658  AddressUsers containedIn(const AddressInterval &interval, UserPredicate userPredicate) const;
659  // FIXME[Robb P. Matzke 2014-08-26]: not implemented yet
667  Sawyer::Optional<rose_addr_t> leastUnmapped(rose_addr_t startVa) const {
668  return map_.leastUnmapped(startVa);
669  }
670 
674  void print(std::ostream&, const std::string &prefix="") const;
675 
679  void checkConsistency() const;
680 };
681 
682 } // namespace
683 } // namespace
684 } // namespace
685 
686 // Class versions must be at global scope
688 
689 #endif
690 #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:135
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