ROSE  0.9.11.151
Public Member Functions | List of all members
Rose::BinaryAnalysis::Partitioner2::AddressUsageMap Class Reference

Description

Address usage map.

Keeps track of which instructions and data span each virtual address. The AUM that's part of the partitioner is never modified directly by the user, and represents the instructions and basic blocks that are in the control flow graph as well as any data blocks they own.

Definition at line 416 of file AddressUsageMap.h.

#include <AddressUsageMap.h>

Public Member Functions

bool isEmpty () const
 Determines whether a map is empty. More...
 
void clear ()
 Reset map to initial empty state. More...
 
size_t size () const
 Number of addresses represented by the map. More...
 
AddressInterval hull () const
 Minimum and maximum used addresses. More...
 
AddressIntervalSet extent () const
 Addresses represented. More...
 
bool exists (rose_addr_t va) const
 Predicate to determine whether an address is used. More...
 
AddressInterval nextUnused (rose_addr_t minVa) const
 Next unused address interval. More...
 
AddressUser insertInstruction (SgAsmInstruction *, const BasicBlock::Ptr &)
 Insert the instruction along with an owning basic block. More...
 
AddressUser insertDataBlock (const DataBlock::Ptr &)
 Insert the data block. More...
 
SgAsmInstructioneraseInstruction (SgAsmInstruction *, const BasicBlock::Ptr &)
 Remove the specified instruction/basic block pair. More...
 
DataBlock::Ptr eraseDataBlock (const DataBlock::Ptr &)
 Remove the specified data block. More...
 
Sawyer::Optional< rose_addr_t > leastUnmapped (rose_addr_t startVa) const
 Returns the least unmapped address with specified lower limit. More...
 
void print (std::ostream &, const std::string &prefix="") const
 Dump the contents of this AUM to a stream. More...
 
void checkConsistency () const
 Check invariants. More...
 
bool anyExists (const AddressInterval &) const
 Predicate to determine whether any of the specified addresses are used. More...
 
bool anyExists (const AddressIntervalSet &) const
 Predicate to determine whether any of the specified addresses are used. More...
 
AddressIntervalSet unusedExtent (size_t nBits) const
 Addresses not represented. More...
 
AddressIntervalSet unusedExtent (const AddressInterval &) const
 Addresses not represented. More...
 
AddressIntervalSet unusedExtent (const AddressIntervalSet &) const
 Addresses not represented. More...
 
SgAsmInstructioninstructionExists (SgAsmInstruction *) const
 Determines whether the specified instruction or an equivalent exists. More...
 
SgAsmInstructioninstructionExists (rose_addr_t va) const
 Determines whether the specified instruction or an equivalent exists. More...
 
BasicBlock::Ptr basicBlockExists (const BasicBlock::Ptr &) const
 Determine if a basic block exists. More...
 
BasicBlock::Ptr basicBlockExists (rose_addr_t startOfBlock) const
 Determine if a basic block exists. More...
 
DataBlock::Ptr dataBlockExists (const DataBlock::Ptr &) const
 Determines if a data block exists. More...
 
DataBlock::Ptr dataBlockExists (rose_addr_t va, rose_addr_t size) const
 Determines if a data block exists. More...
 
AddressUser findInstruction (SgAsmInstruction *) const
 Find an AddressUser record for the specified instruction, or equivalent. More...
 
AddressUser findInstruction (rose_addr_t va) const
 Find an AddressUser record for the specified instruction, or equivalent. More...
 
AddressUser findBasicBlock (const BasicBlock::Ptr &) const
 Find an AddressUser record for the specified basic block, or equivalent. More...
 
AddressUser findBasicBlock (rose_addr_t va) const
 Find an AddressUser record for the specified basic block, or equivalent. More...
 
AddressUser findDataBlock (const DataBlock::Ptr &) const
 Find an AddressUser record for the specified data block, or equivalent. More...
 
AddressUser findDataBlock (rose_addr_t va, rose_addr_t size) const
 Find an AddressUser record for the specified data block, or equivalent. More...
 
AddressUsers spanning (const AddressInterval &interval) const
 Find address users that span the entire interval. More...
 
template<class UserPredicate >
AddressUsers spanning (const AddressInterval &interval, UserPredicate userPredicate) const
 Find address users that span the entire interval. More...
 
AddressUsers overlapping (const AddressInterval &interval) const
 Users that overlap the interval. More...
 
template<class UserPredicate >
AddressUsers overlapping (const AddressInterval &interval, UserPredicate userPredicate) const
 Users that overlap the interval. More...
 
AddressUsers containedIn (const AddressInterval &interval) const
 Users that are fully contained in the interval. More...
 
template<class UserPredicate >
AddressUsers containedIn (const AddressInterval &interval, UserPredicate userPredicate) const
 Users that are fully contained in the interval. More...
 

Member Function Documentation

bool Rose::BinaryAnalysis::Partitioner2::AddressUsageMap::isEmpty ( ) const
inline

Determines whether a map is empty.

Returns true if the map contains no instructions or data, false if it contains at least one instruction or at least one data block.

Definition at line 435 of file AddressUsageMap.h.

References Sawyer::Container::IntervalMap< I, T, Policy >::isEmpty().

void Rose::BinaryAnalysis::Partitioner2::AddressUsageMap::clear ( )
inline

Reset map to initial empty state.

Definition at line 440 of file AddressUsageMap.h.

References Sawyer::Container::IntervalMap< I, T, Policy >::clear().

size_t Rose::BinaryAnalysis::Partitioner2::AddressUsageMap::size ( ) const
inline

Number of addresses represented by the map.

Returns the number of addresses that have at least one user. This is a constant-time operation.

Definition at line 447 of file AddressUsageMap.h.

References Sawyer::Container::IntervalMap< I, T, Policy >::size().

Referenced by Rose::BinaryAnalysis::Partitioner2::Partitioner::nBytes().

AddressInterval Rose::BinaryAnalysis::Partitioner2::AddressUsageMap::hull ( ) const
inline

Minimum and maximum used addresses.

Returns minimum and maximum addresses that exist in this address usage map. If the map is empty then the returned interval is empty, containing neither a minimum nor maximum address.

Definition at line 455 of file AddressUsageMap.h.

References Sawyer::Container::IntervalMap< I, T, Policy >::hull().

AddressIntervalSet Rose::BinaryAnalysis::Partitioner2::AddressUsageMap::extent ( ) const

Addresses represented.

Returns the set of addresses that are represented.

bool Rose::BinaryAnalysis::Partitioner2::AddressUsageMap::exists ( rose_addr_t  va) const
inline

Predicate to determine whether an address is used.

Returns true if the specified address belongs to any instruction, basic block, or data block. This is a O(log N) operation where N is the number of contiguous intervals in this address usage map. It may be slightly faster than some of the other methods since it doesn't need to construct a non-POD return value.

Definition at line 469 of file AddressUsageMap.h.

References Sawyer::Container::IntervalMap< I, T, Policy >::exists().

bool Rose::BinaryAnalysis::Partitioner2::AddressUsageMap::anyExists ( const AddressInterval ) const

Predicate to determine whether any of the specified addresses are used.

Returns true if any address in the specified set or interval belongs to any instruction, basic block, or data block. This may be slightly faster than some of the other predicates because it doesn't need to construct a non-POD return value.

bool Rose::BinaryAnalysis::Partitioner2::AddressUsageMap::anyExists ( const AddressIntervalSet ) const

Predicate to determine whether any of the specified addresses are used.

Returns true if any address in the specified set or interval belongs to any instruction, basic block, or data block. This may be slightly faster than some of the other predicates because it doesn't need to construct a non-POD return value.

AddressIntervalSet Rose::BinaryAnalysis::Partitioner2::AddressUsageMap::unusedExtent ( size_t  nBits) const

Addresses not represented.

Returns the set of addresses that are not represented. The nBits argument is the number of bits in the virtual address space, usually 32 or 64, and must be between 1 and 64, inclusive. Alternatively, an interval or interval set can be supplied to limit the return value.

AddressIntervalSet Rose::BinaryAnalysis::Partitioner2::AddressUsageMap::unusedExtent ( const AddressInterval ) const

Addresses not represented.

Returns the set of addresses that are not represented. The nBits argument is the number of bits in the virtual address space, usually 32 or 64, and must be between 1 and 64, inclusive. Alternatively, an interval or interval set can be supplied to limit the return value.

AddressIntervalSet Rose::BinaryAnalysis::Partitioner2::AddressUsageMap::unusedExtent ( const AddressIntervalSet ) const

Addresses not represented.

Returns the set of addresses that are not represented. The nBits argument is the number of bits in the virtual address space, usually 32 or 64, and must be between 1 and 64, inclusive. Alternatively, an interval or interval set can be supplied to limit the return value.

AddressInterval Rose::BinaryAnalysis::Partitioner2::AddressUsageMap::nextUnused ( rose_addr_t  minVa) const

Next unused address interval.

Returns the next address interval that begins at or after the specified address and which does not correspond to any instruction, basic block, data block, or function. The largest such interval is returned, but it will not contain any values less than minVa. Returns an empty interval if no such interval exists.

SgAsmInstruction* Rose::BinaryAnalysis::Partitioner2::AddressUsageMap::instructionExists ( SgAsmInstruction ) const

Determines whether the specified instruction or an equivalent exists.

Returns the instruction or equivalent that exists, otherwise null.

SgAsmInstruction* Rose::BinaryAnalysis::Partitioner2::AddressUsageMap::instructionExists ( rose_addr_t  va) const

Determines whether the specified instruction or an equivalent exists.

Returns the instruction or equivalent that exists, otherwise null.

BasicBlock::Ptr Rose::BinaryAnalysis::Partitioner2::AddressUsageMap::basicBlockExists ( const BasicBlock::Ptr ) const

Determine if a basic block exists.

If the specified basic block's starting address exists in this AUM and is the starting instruction of this basic block or an equivalent then returns a pointer to the existing basic block, otherwise the null pointer is returned. A basic block exists only when it has at least one instruction; this is contrary to the CFG, where a basic block can be represented by a placeholder with no instructions.

BasicBlock::Ptr Rose::BinaryAnalysis::Partitioner2::AddressUsageMap::basicBlockExists ( rose_addr_t  startOfBlock) const

Determine if a basic block exists.

If the specified basic block's starting address exists in this AUM and is the starting instruction of this basic block or an equivalent then returns a pointer to the existing basic block, otherwise the null pointer is returned. A basic block exists only when it has at least one instruction; this is contrary to the CFG, where a basic block can be represented by a placeholder with no instructions.

DataBlock::Ptr Rose::BinaryAnalysis::Partitioner2::AddressUsageMap::dataBlockExists ( const DataBlock::Ptr ) const

Determines if a data block exists.

If the specified data block or an equivalent exists in the map then a pointer to the exsiting data block is returned, otherwise a null pointer is returned.

DataBlock::Ptr Rose::BinaryAnalysis::Partitioner2::AddressUsageMap::dataBlockExists ( rose_addr_t  va,
rose_addr_t  size 
) const

Determines if a data block exists.

If the specified data block or an equivalent exists in the map then a pointer to the exsiting data block is returned, otherwise a null pointer is returned.

AddressUser Rose::BinaryAnalysis::Partitioner2::AddressUsageMap::findInstruction ( SgAsmInstruction ) const

Find an AddressUser record for the specified instruction, or equivalent.

If the specified instruction or an equivalent instruction exists in this object, then its record is returned, otherwise an empty record is returned. The instruction can be indicated by either an SgAsmInstruction object or a starting address.

Referenced by Rose::BinaryAnalysis::Partitioner2::Partitioner::instructionExists().

AddressUser Rose::BinaryAnalysis::Partitioner2::AddressUsageMap::findInstruction ( rose_addr_t  va) const

Find an AddressUser record for the specified instruction, or equivalent.

If the specified instruction or an equivalent instruction exists in this object, then its record is returned, otherwise an empty record is returned. The instruction can be indicated by either an SgAsmInstruction object or a starting address.

AddressUser Rose::BinaryAnalysis::Partitioner2::AddressUsageMap::findBasicBlock ( const BasicBlock::Ptr ) const

Find an AddressUser record for the specified basic block, or equivalent.

If the specified basic block or an equivalent basic block (based on starting address) is present in this list, then return its record, otherwise return an empty record. This looks up the basic block by looking for its first instruction, therefore returns a record only if the first instruction is present. The basic block can be specified by either a BasicBlock object or a starting address.

AddressUser Rose::BinaryAnalysis::Partitioner2::AddressUsageMap::findBasicBlock ( rose_addr_t  va) const

Find an AddressUser record for the specified basic block, or equivalent.

If the specified basic block or an equivalent basic block (based on starting address) is present in this list, then return its record, otherwise return an empty record. This looks up the basic block by looking for its first instruction, therefore returns a record only if the first instruction is present. The basic block can be specified by either a BasicBlock object or a starting address.

AddressUser Rose::BinaryAnalysis::Partitioner2::AddressUsageMap::findDataBlock ( const DataBlock::Ptr ) const

Find an AddressUser record for the specified data block, or equivalent.

If the specified data block or an equivalent data block exists in this object, then its record is returned, otherwise an empty record is returned. The data block can be specified by either a DataBlock object or a starting address and size.

AddressUser Rose::BinaryAnalysis::Partitioner2::AddressUsageMap::findDataBlock ( rose_addr_t  va,
rose_addr_t  size 
) const

Find an AddressUser record for the specified data block, or equivalent.

If the specified data block or an equivalent data block exists in this object, then its record is returned, otherwise an empty record is returned. The data block can be specified by either a DataBlock object or a starting address and size.

AddressUser Rose::BinaryAnalysis::Partitioner2::AddressUsageMap::insertInstruction ( SgAsmInstruction ,
const BasicBlock::Ptr  
)

Insert the instruction along with an owning basic block.

Inserts the specified instruction and its owning basic block if the information is not already present in this AUM. Returns the relavent address user information since this method might substitute existing equivalent instruction and owner.

AddressUser Rose::BinaryAnalysis::Partitioner2::AddressUsageMap::insertDataBlock ( const DataBlock::Ptr )

Insert the data block.

Inserts the specified data block if an equivalent data block is not already present. Returns the relevant address user information since this method might substitute an existing equivalent data block.

SgAsmInstruction* Rose::BinaryAnalysis::Partitioner2::AddressUsageMap::eraseInstruction ( SgAsmInstruction ,
const BasicBlock::Ptr  
)

Remove the specified instruction/basic block pair.

If the specified instruction or equivalent is found in this AUM then the specified basic block is removed as one of its owners. If this leaves the instruction with no owning basic blocks, then the instruction itself is also removed. Returns the affected instruction.

DataBlock::Ptr Rose::BinaryAnalysis::Partitioner2::AddressUsageMap::eraseDataBlock ( const DataBlock::Ptr )

Remove the specified data block.

Removes the specified data block or an equivalent from this AUM. Returns the data block that was erased.

AddressUsers Rose::BinaryAnalysis::Partitioner2::AddressUsageMap::spanning ( const AddressInterval interval) const
inline

Find address users that span the entire interval.

The return value is a vector of address users (instructions and/or data blocks) sorted by starting address where each user starts at or before the beginning of the interval and ends at or after the end of the interval. The specified predicate is used to select which users are inserted into the result and should be a functor that takes an AddressUser as an argument and returns true to select that user for inclusion in the result.

Definition at line 601 of file AddressUsageMap.h.

References Rose::BinaryAnalysis::Partitioner2::AddressUsers::selectAllUsers().

template<class UserPredicate >
AddressUsers Rose::BinaryAnalysis::Partitioner2::AddressUsageMap::spanning ( const AddressInterval interval,
UserPredicate  userPredicate 
) const
inline

Find address users that span the entire interval.

The return value is a vector of address users (instructions and/or data blocks) sorted by starting address where each user starts at or before the beginning of the interval and ends at or after the end of the interval. The specified predicate is used to select which users are inserted into the result and should be a functor that takes an AddressUser as an argument and returns true to select that user for inclusion in the result.

Definition at line 606 of file AddressUsageMap.h.

References Sawyer::Container::IntervalMap< I, T, Policy >::findAll(), Rose::BinaryAnalysis::Partitioner2::AddressUsers::intersection(), Rose::BinaryAnalysis::Partitioner2::AddressUsers::isEmpty(), and Sawyer::Container::Map< K, T, Cmp, Alloc >::Node::value().

AddressUsers Rose::BinaryAnalysis::Partitioner2::AddressUsageMap::overlapping ( const AddressInterval interval) const
inline

Users that overlap the interval.

The return value is a vector of address users (instructions and/or data blocks) sorted by starting address where each user overlaps with the interval. That is, at least one byte of the instruction or data block came from the specified interval of byte addresses. The specified predicate is used to select which users are inserted into the result and should be a functor that takes an AddressUser as an argument and returns true to select that user for inclusion in the result.

Definition at line 628 of file AddressUsageMap.h.

References Rose::BinaryAnalysis::Partitioner2::AddressUsers::selectAllUsers().

template<class UserPredicate >
AddressUsers Rose::BinaryAnalysis::Partitioner2::AddressUsageMap::overlapping ( const AddressInterval interval,
UserPredicate  userPredicate 
) const
inline

Users that overlap the interval.

The return value is a vector of address users (instructions and/or data blocks) sorted by starting address where each user overlaps with the interval. That is, at least one byte of the instruction or data block came from the specified interval of byte addresses. The specified predicate is used to select which users are inserted into the result and should be a functor that takes an AddressUser as an argument and returns true to select that user for inclusion in the result.

Definition at line 633 of file AddressUsageMap.h.

References Sawyer::Container::IntervalMap< I, T, Policy >::findAll(), Rose::BinaryAnalysis::Partitioner2::AddressUsers::insert(), and Sawyer::Container::Map< K, T, Cmp, Alloc >::Node::value().

AddressUsers Rose::BinaryAnalysis::Partitioner2::AddressUsageMap::containedIn ( const AddressInterval interval) const
inline

Users that are fully contained in the interval.

The return value is a vector of address users (instructions and/or data blocks) sorted by starting address where each user is fully contained within the specified interval. That is, each user starts at or after the beginning of the interval and ends at or before the end of the interval. The specified predicate is used to select which users are inserted into the result and should be a functor that takes an AddressUser as an argument and returns true to select that user for inclusion in the result.

Definition at line 650 of file AddressUsageMap.h.

References Rose::BinaryAnalysis::Partitioner2::AddressUsers::selectAllUsers().

template<class UserPredicate >
AddressUsers Rose::BinaryAnalysis::Partitioner2::AddressUsageMap::containedIn ( const AddressInterval interval,
UserPredicate  userPredicate 
) const

Users that are fully contained in the interval.

The return value is a vector of address users (instructions and/or data blocks) sorted by starting address where each user is fully contained within the specified interval. That is, each user starts at or after the beginning of the interval and ends at or before the end of the interval. The specified predicate is used to select which users are inserted into the result and should be a functor that takes an AddressUser as an argument and returns true to select that user for inclusion in the result.

Sawyer::Optional<rose_addr_t> Rose::BinaryAnalysis::Partitioner2::AddressUsageMap::leastUnmapped ( rose_addr_t  startVa) const
inline

Returns the least unmapped address with specified lower limit.

Returns the smallest unmapped address that is greater than or equal to startVa. If no such address exists then nothing is returned.

Definition at line 664 of file AddressUsageMap.h.

References Sawyer::Container::IntervalMap< I, T, Policy >::leastUnmapped().

void Rose::BinaryAnalysis::Partitioner2::AddressUsageMap::print ( std::ostream &  ,
const std::string &  prefix = "" 
) const

Dump the contents of this AUM to a stream.

The output contains one entry per line and the last line is terminated with a linefeed.

void Rose::BinaryAnalysis::Partitioner2::AddressUsageMap::checkConsistency ( ) const

Check invariants.

Aborts if invariants are not satisified.


The documentation for this class was generated from the following file: