ROSE  0.9.11.35
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 #include <Partitioner2/OwnedDataBlock.h>
8 
9 #include <Sawyer/IntervalMap.h>
10 #include <Sawyer/IntervalSet.h>
11 #include <Sawyer/Optional.h>
12 
13 #include <boost/serialization/access.hpp>
14 #include <boost/serialization/vector.hpp>
15 
16 #include <algorithm>
17 #include <boost/foreach.hpp>
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_;
37  OwnedDataBlock odblock_;
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  s & BOOST_SERIALIZATION_NVP(odblock_);
48  }
49 #endif
50 
51 public:
52  AddressUser(): insn_(NULL) {} // needed by std::vector<AddressUser>, but otherwise unused
53 
59  AddressUser(SgAsmInstruction *insn, const BasicBlock::Ptr &bblock): insn_(insn) {
60  ASSERT_not_null(insn_);
61  if (bblock)
62  bblocks_.push_back(bblock);
63  }
64 
66  AddressUser(const OwnedDataBlock &odblock): insn_(NULL), odblock_(odblock) {}
67 
72  rose_addr_t address() const;
73 
75  bool isBasicBlock() const { return insn_!=NULL; }
76 
78  bool isDataBlock() const { return odblock_.dataBlock()!=NULL; }
79 
84  return insn_;
85  }
86 
93  return bblocks_.empty() ? BasicBlock::Ptr() : bblocks_[0];
94  }
95 
101  const std::vector<BasicBlock::Ptr>& basicBlocks() const {
102  return bblocks_;
103  }
104 
106  void insertBasicBlock(const BasicBlock::Ptr &bblock);
107 
109  void eraseBasicBlock(const BasicBlock::Ptr &bblock);
110 
115  return odblock_.dataBlock();
116  }
117 
125  return odblock_;
126  }
128  return odblock_;
129  }
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 };
162 
163 
165 // AddressUsers
167 
175  std::vector<AddressUser> users_; // sorted
176 
177 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
178 private:
179  friend class boost::serialization::access;
180 
181  template<class S>
182  void serialize(S &s, const unsigned /*version*/) {
183  s & BOOST_SERIALIZATION_NVP(users_);
184  }
185 #endif
186 
187 public:
190 
192  explicit AddressUsers(SgAsmInstruction *insn, const BasicBlock::Ptr &bb) { insertInstruction(insn, bb); }
193 
195  explicit AddressUsers(const OwnedDataBlock &odb) { insertDataBlock(odb); }
196 
197 #if 0 // [Robb P Matzke 2016-06-30]: insn can be owned by multiple blocks now; use instructionExists(rose_addr_t) instead.
198 
202 #endif
203 
208  Sawyer::Optional<AddressUser> instructionExists(rose_addr_t insnStart) const;
209 
215 
221  Sawyer::Optional<OwnedDataBlock> dataBlockExists(rose_addr_t dbStart) const;
222 
228  BasicBlock::Ptr findBasicBlock(rose_addr_t bbVa) const;
229 
235 
245 
250  void insert(const AddressUsers&);
251 
257 
262  void eraseDataBlock(const DataBlock::Ptr&);
263 
267  static bool selectAllUsers(const AddressUser&) { return true; }
268 
273  static bool selectBasicBlocks(const AddressUser &user) { return user.isBasicBlock(); }
274 
279  static bool selectDataBlocks(const AddressUser &user) { return user.isDataBlock(); }
280 
284  template<class UserPredicate>
285  AddressUsers select(UserPredicate predicate) const {
286  AddressUsers retval;
287  BOOST_FOREACH (const AddressUser &user, users_) {
288  if (predicate(user))
289  retval.users_.push_back(user);
290  }
291  return retval;
292  }
293 
297  const std::vector<AddressUser>& addressUsers() const { return users_; }
298 
303 
308 
314  std::vector<SgAsmInstruction*> instructions() const;
315 
321  std::vector<BasicBlock::Ptr> instructionOwners() const;
322 
326  std::vector<DataBlock::Ptr> dataBlocks() const;
327 
329  size_t size() const { return users_.size(); }
330 
334  bool isEmpty() const { return users_.empty(); }
335 
337  AddressUsers intersection(const AddressUsers&) const;
338 
340  AddressUsers union_(const AddressUsers&) const;
341 
343  bool operator==(const AddressUsers &other) const;
344 
346  void print(std::ostream&) const;
347 
351  bool isConsistent() const;
352 
353 protected:
354  std::vector<AddressUser>::iterator findInstruction(SgAsmInstruction*);
355 };
356 
357 
359 // AddressUsageMap
361 
369  Map map_;
370 
371 #ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
372 private:
373  friend class boost::serialization::access;
374 
375  template<class S>
376  void serialize(S &s, const unsigned /*version*/) {
377  s & BOOST_SERIALIZATION_NVP(map_);
378  }
379 #endif
380 
381 public:
386  bool isEmpty() const { return map_.isEmpty(); }
387 
389  void clear() { map_.clear(); }
390 
394  size_t size() const { return map_.size(); }
395 
400  AddressInterval hull() const { return map_.hull(); }
401 
405  AddressIntervalSet extent() const;
406 
412  bool exists(rose_addr_t va) const { return map_.exists(va); }
413 
421  bool anyExists(const AddressInterval&) const;
422  bool anyExists(const AddressIntervalSet&) const;
432  AddressIntervalSet unusedExtent(size_t nBits) const;
442  AddressInterval nextUnused(rose_addr_t minVa) const;
443 
447  bool instructionExists(SgAsmInstruction*) const;
448 
453  Sawyer::Optional<AddressUser> instructionExists(rose_addr_t startOfInsn) const;
454 
460  BasicBlock::Ptr basicBlockExists(rose_addr_t startOfBlock) const;
461 
466  OwnedDataBlock dataBlockExists(rose_addr_t startOfBlock) const;
467 
473 
482  AddressUsers spanning(const AddressInterval &interval) const {
483  return spanning(interval, AddressUsers::selectAllUsers);
484  }
485 
486  template<class UserPredicate>
487  AddressUsers spanning(const AddressInterval &interval, UserPredicate userPredicate) const {
488  AddressUsers retval;
489  size_t nIters = 0;
490  BOOST_FOREACH (const Map::Node &node, map_.findAll(interval)) {
491  AddressUsers users = node.value().select(userPredicate);
492  retval = 0==nIters++ ? users : retval.intersection(users);
493  if (retval.isEmpty())
494  break;
495  }
496  return retval;
497  }
509  AddressUsers overlapping(const AddressInterval &interval) const {
510  return overlapping(interval, AddressUsers::selectAllUsers);
511  }
512 
513  template<class UserPredicate>
514  AddressUsers overlapping(const AddressInterval &interval, UserPredicate userPredicate) const {
515  AddressUsers retval;
516  BOOST_FOREACH (const Map::Node &node, map_.findAll(interval))
517  retval.insert(node.value().select(userPredicate));
518  return retval;
519  }
531  AddressUsers containedIn(const AddressInterval &interval) const {
532  return containedIn(interval, AddressUsers::selectAllUsers);
533  }
534 
535  template<class UserPredicate>
536  AddressUsers containedIn(const AddressInterval &interval, UserPredicate userPredicate) const;
537  // FIXME[Robb P. Matzke 2014-08-26]: not implemented yet
545  Sawyer::Optional<rose_addr_t> leastUnmapped(rose_addr_t startVa) const {
546  return map_.leastUnmapped(startVa);
547  }
548 
552  void print(std::ostream&, const std::string &prefix="") const;
553 
557  void checkConsistency() const;
558 
559 private:
560  friend class Partitioner;
561 
562  // Insert an instruction/block pair into the map.
563  void insertInstruction(SgAsmInstruction*, const BasicBlock::Ptr&);
564 
565  // Insert or merge a data block into the map. The data block must not be a null pointer. A data pointer is always inserted
566  // along with ownership information--which functions and basic blocks own this data block. If the address usage map already
567  // has this data block, then the provided ownership information is merged into the existing ownership lists. Returns the
568  // data block ownership information, either a copy of the argument or a copy of the updated existing one in the AUM.
569  OwnedDataBlock insertDataBlock(const OwnedDataBlock&);
570 
571  // Remove an instruction/block pair from the map. If the instruction exists in the map then the specified block is removed
572  // from the instruction's owner list. If this results in an empty owner list then the instruction is also removed.
573  // If the pointer is null or the instruction/block pair does not exist in the map, then this is a no-op.
574  void eraseInstruction(SgAsmInstruction*, const BasicBlock::Ptr&);
575 
576  // Remove a data block from the map. The specified data block is removed from the map. If the pointer is null or the data
577  // block does not exist in the map, then this is a no-op.
578  void eraseDataBlock(const DataBlock::Ptr&);
579 };
580 
581 } // namespace
582 } // namespace
583 } // namespace
584 
585 #endif
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 &)
Inser a user.
void clear()
Reset map to initial empty state.
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.
AddressUsers(const OwnedDataBlock &odb)
Constructs a list having one data block user.
void insertBasicBlock(const BasicBlock::Ptr &bblock)
Add another basic block to the set of basic blocks.
Holds a value or nothing.
Definition: Optional.h:49
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.
OwnedDataBlock dataBlockExists(rose_addr_t startOfBlock) const
Determines if an address is the start of a data block.
const std::vector< BasicBlock::Ptr > & basicBlocks() const
Returns all basic blocks to which this instruction belongs.
Main namespace for the ROSE library.
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
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
AddressUser(const OwnedDataBlock &odblock)
Constructs a new user which is a data block.
std::vector< DataBlock::Ptr > dataBlocks() const
Returns all data blocks.
OwnedDataBlock insertDataBlock(const OwnedDataBlock &)
Insert a data block.
AddressUsers instructionUsers() const
Returns all instruction users.
bool operator==(const AddressUsers &other) const
True if two lists are equal.
std::vector< BasicBlock::Ptr > instructionOwners() const
Returns all basic blocks.
OwnedDataBlock & dataBlockOwnership()
Return the data block ownership information.
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
DataBlock::Ptr dataBlock() const
Returns the data block for this ownership record.
bool instructionExists(SgAsmInstruction *) const
Determines whether an instruction exists in the map.
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.
BasicBlock::Ptr findBasicBlock(rose_addr_t bbVa) const
Find the basic block that starts at this address.
const OwnedDataBlock & dataBlockOwnership() const
Return the data block ownership information.
AddressUsers(SgAsmInstruction *insn, const BasicBlock::Ptr &bb)
Constructs a list having one instruction user.
void eraseInstruction(SgAsmInstruction *, const BasicBlock::Ptr &)
Erase an instruction/basic block pair from the list.
AddressUsers spanning(const AddressInterval &interval) const
Find address users that span the entire interval.
void checkConsistency() const
Check invariants.
bool exists(rose_addr_t va) const
Predicate to determine whether an address is used.
bool isDataBlock() const
Predicate returning true if user is a data block.
AddressInterval hull() const
Minimum and maximum used addresses.
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.
void eraseDataBlock(const DataBlock::Ptr &)
Erase a data block user.
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.
Sawyer::Optional< AddressUser > instructionExists(rose_addr_t insnStart) const
Determines if an instruction exists in the list.
void insertInstruction(SgAsmInstruction *, const BasicBlock::Ptr &)
Insert an instruction/basic block pair.
AddressUsers intersection(const AddressUsers &) const
Computes the intersection of this list with another.
AddressIntervalSet extent() const
Addresses represented.
bool operator==(const AddressUser &other) const
Compare two users for equality.
bool isEmpty() const
Determines whether a map is empty.
Partitions instructions into basic blocks and functions.
Definition: Partitioner.h:293
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.
Sawyer::Optional< OwnedDataBlock > dataBlockExists(const DataBlock::Ptr &) const
Determines if a data block exists in the list.
Type for stored nodes.
Definition: Sawyer/Map.h:89
BasicBlock::Ptr basicBlockExists(rose_addr_t startOfBlock) const
Determines if an address is the start of a basic block.