ROSE 0.11.145.317
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_ENABLE_BOOST_SERIALIZATION
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_ENABLE_BOOST_SERIALIZATION
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
61 // Defined in the .C file where all necessary class definitions (plain and templatized) are available.
64 AddressUser& operator=(const AddressUser&);
65
71
73 bool isBasicBlock() const;
74
76 bool isDataBlock() const;
77
81 bool isEmpty() const;
82
87
93
99 const std::vector<BasicBlockPtr>& basicBlocks() const;
100
102 void insertBasicBlock(const BasicBlockPtr &bblock);
103
105 void eraseBasicBlock(const BasicBlockPtr &bblock);
106
111
118
124 bool operator==(const AddressUser &other) const;
125
132 bool operator<(const AddressUser&) const;
133
135 void print(std::ostream&) const;
136
140 bool isConsistent() const;
141
145 operator bool() const {
146 return !isEmpty();
147 }
148};
149
150
152// AddressUsers
154
161 std::vector<AddressUser> users_; // sorted
162
163#ifdef ROSE_ENABLE_BOOST_SERIALIZATION
164private:
165 friend class boost::serialization::access;
166 template<class S> void serialize(S&, const unsigned version);
167#endif
168
169public:
173
176
178 explicit AddressUsers(const DataBlockPtr&);
179
252
258
260 void insert(const AddressUsers&);
261
267
273
277 static bool selectAllUsers(const AddressUser&);
278
283 static bool selectBasicBlocks(const AddressUser&);
284
289 static bool selectDataBlocks(const AddressUser&);
290
294 template<class UserPredicate>
295 AddressUsers select(UserPredicate predicate) const {
296 AddressUsers retval;
297 for (const AddressUser &user: users_) {
298 if (predicate(user))
299 retval.users_.push_back(user);
300 }
301 return retval;
302 }
303
307 const std::vector<AddressUser>& addressUsers() const;
308
313
318
324 std::vector<SgAsmInstruction*> instructions() const;
325
331 std::vector<BasicBlockPtr> instructionOwners() const;
332
336 std::vector<DataBlockPtr> dataBlocks() const;
337
339 size_t size() const;
340
344 bool isEmpty() const;
345
348
351
353 bool operator==(const AddressUsers &other) const;
354
356 void print(std::ostream&) const;
357
361 bool isConsistent() const;
362};
363
364
366// AddressUsageMap
368
376 Map map_;
377
378#ifdef ROSE_ENABLE_BOOST_SERIALIZATION
379private:
380 friend class boost::serialization::access;
381 template<class S> void serialize(S&, const unsigned version);
382#endif
383
384public:
387
388public:
393 bool isEmpty() const;
394
396 void clear();
397
401 size_t size() const;
402
408
413
419 bool exists(Address) const;
420
428 bool anyExists(const AddressInterval&) const;
429 bool anyExists(const AddressIntervalSet&) const;
439 AddressIntervalSet unusedExtent(size_t nBits) const;
450
522
528
535
540
550
551 template<class UserPredicate>
552 AddressUsers spanning(const AddressInterval &interval, UserPredicate userPredicate) const {
553 AddressUsers retval;
554 size_t nIters = 0;
555 for (const Map::Node &node: map_.findAll(interval)) {
556 AddressUsers users = node.value().select(userPredicate);
557 retval = 0==nIters++ ? users : retval.intersection(users);
558 if (retval.isEmpty())
559 break;
560 }
561 return retval;
562 }
575
576 template<class UserPredicate>
577 AddressUsers overlapping(const AddressInterval &interval, UserPredicate userPredicate) const {
578 AddressUsers retval;
579 for (const Map::Node &node: map_.findAll(interval))
580 retval.insert(node.value().select(userPredicate));
581 return retval;
582 }
594 // FIXME[Robb P. Matzke 2014-08-26]: not implemented yet
596
597 //template<class UserPredicate>
598 //AddressUsers containedIn(const AddressInterval &interval, UserPredicate userPredicate) const {...}
607
611 void print(std::ostream&, const std::string &prefix="") const;
612
616 void checkConsistency() const;
617};
618
619} // namespace
620} // namespace
621} // namespace
622
623#endif
624#endif
AddressIntervalSet unusedExtent(const AddressIntervalSet &) const
Addresses not represented.
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 anyExists(const AddressInterval &) const
Predicate to determine whether any of the specified addresses are used.
SgAsmInstruction * instructionExists(Address va) const
Determines whether the specified instruction or an equivalent exists.
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.
AddressUser findInstruction(Address va) const
Find an AddressUser record for the specified instruction, or equivalent.
AddressUser findBasicBlock(Address va) const
Find an AddressUser record for the specified basic block, or equivalent.
AddressUsers containedIn(const AddressInterval &) const
Users that are fully contained in the interval.
AddressUsers spanning(const AddressInterval &) const
Find address users that span the entire interval.
AddressIntervalSet extent() const
Addresses represented.
Sawyer::Optional< Address > leastUnmapped(Address startVa) const
Returns the least unmapped address with specified lower limit.
BasicBlockPtr basicBlockExists(Address startOfBlock) const
Determine if a basic block exists.
void checkConsistency() const
Check invariants.
AddressUser findDataBlock(Address va, Address size) const
Find an AddressUser record for the specified data 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.
AddressInterval nextUnused(Address minVa) const
Next unused address interval.
AddressUser findInstruction(SgAsmInstruction *) const
Find an AddressUser record for the specified instruction, or equivalent.
bool exists(Address) const
Predicate to determine whether an address is used.
AddressIntervalSet unusedExtent(size_t nBits) const
Addresses not represented.
bool isEmpty() const
Determines whether a map is empty.
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.
DataBlockPtr dataBlockExists(Address va, Address size) const
Determines if a data block exists.
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.
Address address() const
Address of user.
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.
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.
DataBlockPtr dataBlockExists(Address va, Address size) const
Determines whether the specified data block or an equivalent exists.
std::vector< SgAsmInstruction * > instructions() const
Returns all instructions.
bool isEmpty() const
Determines whether this address user list is empty.
AddressUsers(SgAsmInstruction *insn, const BasicBlockPtr &)
Constructs a list having one instruction user.
BasicBlockPtr basicBlockExists(Address va) const
Determines whether the specified basic block or an equivalent exists.
AddressUsers union_(const AddressUsers &) const
Computes the union of this list with another.
std::vector< BasicBlockPtr > instructionOwners() const
Returns all basic blocks.
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.
static bool selectBasicBlocks(const AddressUser &)
Selector to select instructions and basic blocks.
AddressUser findDataBlock(Address va, Address size) const
Find an AddressUser record for the specified data block, or equivalent.
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.
AddressUser findInstruction(Address va) const
Find an AddressUser record for the specified instruction, or equivalent.
AddressUser findBasicBlock(Address va) 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.
SgAsmInstruction * instructionExists(Address va) const
Determines whether the specified instruction or an equivalent exists.
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:54
Base class for machine instructions.
std::uint64_t Address
Address.
Definition Address.h:11
The ROSE library.