ROSE 0.11.145.147
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 <Rose/BinaryAnalysis/AddressIntervalSet.h>
8
9#include <Sawyer/IntervalMap.h>
10#include <Sawyer/IntervalSet.h>
11#include <Sawyer/Optional.h>
12
13#ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
14#include <boost/serialization/access.hpp>
15#endif
16
17#include <algorithm>
18#include <ostream>
19#include <string>
20
22
23namespace Rose {
24namespace BinaryAnalysis {
25namespace Partitioner2 {
26
28// AddressUser
30
37 SgAsmInstruction *insn_;
38 std::vector<BasicBlockPtr> bblocks_; // sorted and unique
39 DataBlockPtr dblock_;
40
41#ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
42private:
43 friend class boost::serialization::access;
44 template<class S> void serialize(S&, const unsigned version);
45#endif
46
47public:
50
57
59 explicit AddressUser(const DataBlockPtr&);
60
62
67 rose_addr_t address() const;
68
70 bool isBasicBlock() const;
71
73 bool isDataBlock() const;
74
78 bool isEmpty() const;
79
84
90
96 const std::vector<BasicBlockPtr>& basicBlocks() const;
97
99 void insertBasicBlock(const BasicBlockPtr &bblock);
100
102 void eraseBasicBlock(const BasicBlockPtr &bblock);
103
108
115
121 bool operator==(const AddressUser &other) const;
122
129 bool operator<(const AddressUser&) const;
130
132 void print(std::ostream&) const;
133
137 bool isConsistent() const;
138
142 operator bool() const {
143 return !isEmpty();
144 }
145};
146
147
149// AddressUsers
151
158 std::vector<AddressUser> users_; // sorted
159
160#ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
161private:
162 friend class boost::serialization::access;
163 template<class S> void serialize(S&, const unsigned version);
164#endif
165
166public:
170
173
175 explicit AddressUsers(const DataBlockPtr&);
176
185 SgAsmInstruction* instructionExists(rose_addr_t va) const;
196 BasicBlockPtr basicBlockExists(rose_addr_t va) const;
207 DataBlockPtr dataBlockExists(rose_addr_t va, rose_addr_t size) const;
218 AddressUser findInstruction(rose_addr_t va) const;
230 AddressUser findBasicBlock(rose_addr_t va) const;
241 AddressUser findDataBlock(rose_addr_t va, rose_addr_t size) const;
249
255
257 void insert(const AddressUsers&);
258
264
270
274 static bool selectAllUsers(const AddressUser&);
275
280 static bool selectBasicBlocks(const AddressUser&);
281
286 static bool selectDataBlocks(const AddressUser&);
287
291 template<class UserPredicate>
292 AddressUsers select(UserPredicate predicate) const {
293 AddressUsers retval;
294 for (const AddressUser &user: users_) {
295 if (predicate(user))
296 retval.users_.push_back(user);
297 }
298 return retval;
299 }
300
304 const std::vector<AddressUser>& addressUsers() const;
305
310
315
321 std::vector<SgAsmInstruction*> instructions() const;
322
328 std::vector<BasicBlockPtr> instructionOwners() const;
329
333 std::vector<DataBlockPtr> dataBlocks() const;
334
336 size_t size() const;
337
341 bool isEmpty() const;
342
345
348
350 bool operator==(const AddressUsers &other) const;
351
353 void print(std::ostream&) const;
354
358 bool isConsistent() const;
359};
360
361
363// AddressUsageMap
365
373 Map map_;
374
375#ifdef ROSE_HAVE_BOOST_SERIALIZATION_LIB
376private:
377 friend class boost::serialization::access;
378 template<class S> void serialize(S&, const unsigned version);
379#endif
380
381public:
384
385public:
390 bool isEmpty() const;
391
393 void clear();
394
398 size_t size() const;
399
405
410
416 bool exists(rose_addr_t) const;
417
425 bool anyExists(const AddressInterval&) const;
426 bool anyExists(const AddressIntervalSet&) const;
436 AddressIntervalSet unusedExtent(size_t nBits) const;
446 AddressInterval nextUnused(rose_addr_t minVa) const;
447
454 SgAsmInstruction* instructionExists(rose_addr_t va) const;
466 BasicBlockPtr basicBlockExists(rose_addr_t startOfBlock) const;
476 DataBlockPtr dataBlockExists(rose_addr_t va, rose_addr_t size) const;
487 AddressUser findInstruction(rose_addr_t va) const;
499 AddressUser findBasicBlock(rose_addr_t va) const;
510 AddressUser findDataBlock(rose_addr_t va, rose_addr_t size) const;
519
525
532
537
547
548 template<class UserPredicate>
549 AddressUsers spanning(const AddressInterval &interval, UserPredicate userPredicate) const {
550 AddressUsers retval;
551 size_t nIters = 0;
552 for (const Map::Node &node: map_.findAll(interval)) {
553 AddressUsers users = node.value().select(userPredicate);
554 retval = 0==nIters++ ? users : retval.intersection(users);
555 if (retval.isEmpty())
556 break;
557 }
558 return retval;
559 }
572
573 template<class UserPredicate>
574 AddressUsers overlapping(const AddressInterval &interval, UserPredicate userPredicate) const {
575 AddressUsers retval;
576 for (const Map::Node &node: map_.findAll(interval))
577 retval.insert(node.value().select(userPredicate));
578 return retval;
579 }
591 // FIXME[Robb P. Matzke 2014-08-26]: not implemented yet
593
594 //template<class UserPredicate>
595 //AddressUsers containedIn(const AddressInterval &interval, UserPredicate userPredicate) const {...}
604
608 void print(std::ostream&, const std::string &prefix="") const;
609
613 void checkConsistency() const;
614};
615
616} // namespace
617} // namespace
618} // namespace
619
620#endif
621#endif
DataBlockPtr dataBlockExists(rose_addr_t va, rose_addr_t size) const
Determines if a data block exists.
AddressIntervalSet unusedExtent(const AddressIntervalSet &) const
Addresses not represented.
AddressUser findDataBlock(rose_addr_t va, rose_addr_t size) const
Find an AddressUser record for the specified data block, or equivalent.
SgAsmInstruction * eraseInstruction(SgAsmInstruction *, const BasicBlockPtr &)
Remove the specified instruction/basic block pair.
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.
AddressUser insertDataBlock(const DataBlockPtr &)
Insert the data block.
bool exists(rose_addr_t) const
Predicate to determine whether an address is used.
bool anyExists(const AddressInterval &) const
Predicate to determine whether any of the specified addresses are used.
bool anyExists(const AddressIntervalSet &) const
Predicate to determine whether any of the specified addresses are used.
void clear()
Reset map to initial empty state.
DataBlockPtr eraseDataBlock(const DataBlockPtr &)
Remove the specified data block.
AddressUsers containedIn(const AddressInterval &) const
Users that are fully contained in the interval.
AddressUser findInstruction(rose_addr_t va) const
Find an AddressUser record for the specified instruction, or equivalent.
AddressUsers spanning(const AddressInterval &) const
Find address users that span the entire interval.
AddressIntervalSet extent() const
Addresses represented.
BasicBlockPtr basicBlockExists(rose_addr_t startOfBlock) const
Determine if a basic block exists.
void checkConsistency() const
Check invariants.
AddressUser findBasicBlock(rose_addr_t va) const
Find an AddressUser record for the specified basic block, or equivalent.
AddressIntervalSet unusedExtent(const AddressInterval &) const
Addresses not represented.
AddressInterval hull() const
Minimum and maximum used addresses.
AddressUsers overlapping(const AddressInterval &interval, UserPredicate userPredicate) const
Users that overlap the interval.
SgAsmInstruction * instructionExists(rose_addr_t va) const
Determines whether the specified instruction or an equivalent exists.
AddressUser findInstruction(SgAsmInstruction *) const
Find an AddressUser record for the specified instruction, or equivalent.
AddressIntervalSet unusedExtent(size_t nBits) const
Addresses not represented.
bool isEmpty() const
Determines whether a map is empty.
AddressInterval nextUnused(rose_addr_t minVa) const
Next unused address interval.
BasicBlockPtr basicBlockExists(const BasicBlockPtr &) const
Determine if a basic block exists.
void print(std::ostream &, const std::string &prefix="") const
Dump the contents of this AUM to a stream.
AddressUsers overlapping(const AddressInterval &) const
Users that overlap the interval.
AddressUser findBasicBlock(const BasicBlockPtr &) const
Find an AddressUser record for the specified basic block, or equivalent.
SgAsmInstruction * instructionExists(SgAsmInstruction *) const
Determines whether the specified instruction or an equivalent exists.
AddressUser insertInstruction(SgAsmInstruction *, const BasicBlockPtr &)
Insert the instruction along with an owning basic block.
Sawyer::Optional< rose_addr_t > leastUnmapped(rose_addr_t startVa) const
Returns the least unmapped address with specified lower limit.
AddressUser findDataBlock(const DataBlockPtr &) const
Find an AddressUser record for the specified data block, or equivalent.
size_t size() const
Number of addresses represented by the map.
bool operator==(const AddressUser &other) const
Compare two users for equality.
void insertBasicBlock(const BasicBlockPtr &bblock)
Add another basic block to the set of basic blocks.
bool isBasicBlock() const
Predicate returning true if user is a basic block or instruction.
AddressUser(SgAsmInstruction *, const BasicBlockPtr &)
Constructs new user which is an instruction and its basic block.
bool isConsistent() const
Perform logic consistency checks.
void eraseBasicBlock(const BasicBlockPtr &bblock)
Remove a basic block from the set of basic blocks.
BasicBlockPtr 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.
rose_addr_t address() const
Address of user.
bool isDataBlock() const
Predicate returning true if user is a data block.
bool isEmpty() const
True if this object was default constructed.
bool operator<(const AddressUser &) const
Compare two users for sorting.
const std::vector< BasicBlockPtr > & basicBlocks() const
Returns all basic blocks to which this instruction belongs.
DataBlockPtr dataBlock() const
Returns the data block.
SgAsmInstruction * insn() const
Return the instruction.
AddressUser(const DataBlockPtr &)
Constructs a new user which is a data block.
BasicBlockPtr firstBasicBlock() const
Returns an arbitrary basic block.
AddressUser()
Default constructed user is empty.
std::vector< SgAsmInstruction * > instructions() const
Returns all instructions.
bool isEmpty() const
Determines whether this address user list is empty.
SgAsmInstruction * instructionExists(rose_addr_t va) const
Determines whether the specified instruction or an equivalent exists.
AddressUser findDataBlock(rose_addr_t va, rose_addr_t size) const
Find an AddressUser record for the specified data block, or equivalent.
AddressUser findInstruction(rose_addr_t va) const
Find an AddressUser record for the specified instruction, or equivalent.
AddressUsers(SgAsmInstruction *insn, const BasicBlockPtr &)
Constructs a list having one instruction user.
AddressUsers union_(const AddressUsers &) const
Computes the union of this list with another.
std::vector< BasicBlockPtr > instructionOwners() const
Returns all basic blocks.
AddressUser findBasicBlock(rose_addr_t va) const
Find an AddressUser record for the specified basic block, or equivalent.
BasicBlockPtr basicBlockExists(rose_addr_t va) const
Determines whether the specified basic block or an equivalent exists.
BasicBlockPtr basicBlockExists(const BasicBlockPtr &) const
Determines whether the specified basic block or an equivalent exists.
SgAsmInstruction * instructionExists(SgAsmInstruction *) const
Determines whether the specified instruction or an equivalent exists.
DataBlockPtr eraseDataBlock(const DataBlockPtr &)
Erase a data block from this list.
void insert(const AddressUsers &)
Insert one set of address users into another.
bool operator==(const AddressUsers &other) const
True if two lists are equal.
DataBlockPtr dataBlockExists(rose_addr_t va, rose_addr_t size) const
Determines whether the specified data block or an equivalent exists.
static bool selectBasicBlocks(const AddressUser &)
Selector to select instructions and basic blocks.
static bool selectDataBlocks(const AddressUser &)
Selector to select data blocks.
const std::vector< AddressUser > & addressUsers() const
Return all address users.
AddressUsers intersection(const AddressUsers &) const
Computes the intersection of this list with another.
bool isConsistent() const
Check logical consistency.
size_t size() const
Number of address users.
SgAsmInstruction * eraseInstruction(SgAsmInstruction *, const BasicBlockPtr &)
Erase an instruction/basic block pair from this list.
AddressUser findBasicBlock(const BasicBlockPtr &) const
Find an AddressUser record for the specified basic block, or equivalent.
AddressUsers(const DataBlockPtr &)
Constructs a list having one data block user.
void print(std::ostream &) const
Prints pairs space separated on a single line.
AddressUser insertInstruction(SgAsmInstruction *, const BasicBlockPtr &)
Insert an instruction/basic block pair.
static bool selectAllUsers(const AddressUser &)
Selector to select all users.
AddressUser insertDataBlock(const DataBlockPtr &)
Insert a data block.
AddressUsers instructionUsers() const
Returns all instruction users.
AddressUsers select(UserPredicate predicate) const
Selects certain users from a list.
AddressUsers dataBlockUsers() const
Returns all data block users.
DataBlockPtr dataBlockExists(const DataBlockPtr &) const
Determines whether the specified data block or an equivalent exists.
std::vector< DataBlockPtr > dataBlocks() const
Returns all data blocks.
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.
boost::iterator_range< NodeIterator > findAll(const Interval &interval)
Finds all nodes overlapping the specified interval.
Type for stored nodes.
Definition Sawyer/Map.h:107
Holds a value or nothing.
Definition Optional.h:56
Base class for machine instructions.
The ROSE library.