ROSE  0.9.11.151
Classes | Public Types | Public Member Functions | Static Public Member Functions | Protected Member Functions | List of all members
Rose::BinaryAnalysis::Partitioner2::BasicBlock Class Reference

Description

Basic block information.

A basic block is a sequence of distinct instructions with linear control flow from the first instruction to the last. No edges are permitted to enter or leave the basic block except to the first instruction and from the last instruction, respectively. The instructions of a basic block are not required to be contiguous or non-overlapping or at increasing addresses.

In the absense of interrupt handling, the instructions of a basic block are executed entirely. In the absense of multi-threading, no other instructions intervene.

A basic block is a read-only object once it reaches the BB_COMPLETE state, and can thus be shared between partitioners and threads. The memory for these objects is shared and managed by a shared pointer implementation.

A basic block may belong to multiple functions.

Thread safety: Most of this API is not thread safe, however it is possible to call the non-safe functions as long as no other thread is modifying the basic block at the same tme. The functions for querying and modifying the semantic state are thread safe since they're often called from parallel analysis, but no non-safe methods should be called at the same time by other threads.

See also, SgAsmBlock which is how a basic block (and some other things) are represented in the AST.

Definition at line 128 of file BasicBlock.h.

#include <BasicBlock.h>

Inheritance diagram for Rose::BinaryAnalysis::Partitioner2::BasicBlock:
Inheritance graph
[legend]
Collaboration diagram for Rose::BinaryAnalysis::Partitioner2::BasicBlock:
Collaboration graph
[legend]

Classes

class  Successor
 Basic block successor. More...
 

Public Types

typedef Sawyer::SharedPointer< BasicBlockPtr
 Shared pointer to a basic block. More...
 
typedef std::vector< SuccessorSuccessors
 All successors in no particular order. More...
 
- Public Types inherited from Sawyer::Attribute::Storage<>
typedef SynchronizationTraits< Sawyer::SingleThreadedTagSync
 

Public Member Functions

void copyCache (const BasicBlock::Ptr &other)
 
virtual Ptr create (rose_addr_t startVa, const Partitioner &partitioner) const
 Virtual constructor. More...
 
void clearCache ()
 Clear all cached data. More...
 
bool isFrozen () const
 Determine if basic block is read-only. More...
 
rose_addr_t address () const
 Get the address for a basic block. More...
 
AddressIntervalSet insnAddresses () const
 Get all instruction addresses. More...
 
rose_addr_t fallthroughVa () const
 Get the address after the end of the final instruction. More...
 
size_t nInstructions () const
 Get the number of instructions in this block. More...
 
bool isEmpty () const
 Return true if this basic block has no instructions. More...
 
SgAsmInstructioninstructionExists (rose_addr_t startVa) const
 Determine if this basic block contains an instruction at a specific address. More...
 
Sawyer::Optional< size_t > instructionExists (SgAsmInstruction *) const
 Determines if this basic block contains the specified instruction. More...
 
const std::vector< SgAsmInstruction * > & instructions () const
 Get the instructions for this block. More...
 
void append (const Partitioner &, SgAsmInstruction *)
 Append an instruction to a basic block. More...
 
void pop ()
 Undo the latest append. More...
 
std::set< rose_addr_t > explicitConstants () const
 Set of explicit constants. More...
 
size_t nDataBlocks () const
 Get the number of data blocks owned. More...
 
AddressIntervalSet dataAddresses () const
 Addresses that are part of static data. More...
 
DataBlock::Ptr dataBlockExists (const DataBlock::Ptr &) const
 Determine if this basic block contains the specified data block or equivalent data block. More...
 
bool insertDataBlock (const DataBlock::Ptr &)
 Make this basic block own the specified data block or equivalent data block. More...
 
DataBlock::Ptr eraseDataBlock (const DataBlock::Ptr &)
 Remove specified or equivalent data block from this basic block. More...
 
const std::vector< DataBlock::Ptr > & dataBlocks () const
 Data blocks owned. More...
 
BasicBlockSemantics semantics () const
 Return information about semantics. More...
 
void dropSemantics (const Partitioner &)
 Drops semantic information. More...
 
BasicBlockSemantics undropSemantics (const Partitioner &)
 Undrop semantics. More...
 
const Sawyer::Cached< std::set< rose_addr_t > > & ghostSuccessors () const
 Ghost successors. More...
 
void clearSuccessors ()
 Clear all successor information. More...
 
const Sawyer::Cached< bool > & isFunctionCall () const
 Is a function call? More...
 
const Sawyer::Cached< bool > & isFunctionReturn () const
 Is a function return? More...
 
const Sawyer::Cached< bool > & mayReturn () const
 May-return property. More...
 
const Sawyer::Cached< bool > & popsStack () const
 Pops stack property. More...
 
std::string printableName () const
 A printable name for this basic block. More...
 
const std::string & comment () const
 Comment. More...
 
void comment (const std::string &s)
 Comment. More...
 
const Sawyer::Cached< Successors > & successors () const
 Control flow successors. More...
 
void successors (const Successors &)
 Control flow successors. More...
 
void insertSuccessor (const BaseSemantics::SValuePtr &, EdgeType type=E_NORMAL, Confidence confidence=ASSUMED)
 Insert a new successor. More...
 
void insertSuccessor (rose_addr_t va, size_t nBits, EdgeType type=E_NORMAL, Confidence confidence=ASSUMED)
 Insert a new successor. More...
 
- Public Member Functions inherited from Sawyer::SharedObject
 SharedObject ()
 Default constructor. More...
 
 SharedObject (const SharedObject &)
 Copy constructor. More...
 
virtual ~SharedObject ()
 Virtual destructor. More...
 
SharedObjectoperator= (const SharedObject &)
 Assignment. More...
 
- Public Member Functions inherited from Sawyer::Attribute::Storage<>
 Storage ()
 Default constructor. More...
 
 Storage (const Storage &other)
 Copy constructor. More...
 
Storageoperator= (const Storage &other)
 Assignment operator. More...
 
bool attributeExists (Id id) const
 Check attribute existence. More...
 
void eraseAttribute (Id id)
 Erase an attribute. More...
 
void clearAttributes ()
 Erase all attributes. More...
 
void setAttribute (Id id, const T &value)
 Store an attribute. More...
 
bool setAttributeMaybe (Id id, const T &value)
 Store an attribute if not already present. More...
 
getAttribute (Id id) const
 Get an attribute that is known to exist. More...
 
attributeOrElse (Id id, const T &dflt) const
 Return an attribute or a specified value. More...
 
attributeOrDefault (Id id) const
 Return an attribute or a default-constructed value. More...
 
Sawyer::Optional< T > optionalAttribute (Id id) const
 Return the attribute as an optional value. More...
 
size_t nAttributes () const
 Number of attributes stored. More...
 
std::vector< IdattributeIds () const
 Returns ID numbers for all IDs stored in this container. More...
 

Static Public Member Functions

static Ptr instance (rose_addr_t startVa, const Partitioner &partitioner)
 Static allocating constructor. More...
 

Protected Member Functions

 BasicBlock (rose_addr_t startVa, const Partitioner &partitioner)
 

Member Typedef Documentation

Shared pointer to a basic block.

See Shared ownership.

Definition at line 131 of file BasicBlock.h.

All successors in no particular order.

Definition at line 177 of file BasicBlock.h.

Member Function Documentation

static Ptr Rose::BinaryAnalysis::Partitioner2::BasicBlock::instance ( rose_addr_t  startVa,
const Partitioner partitioner 
)
inlinestatic

Static allocating constructor.

The startVa is the starting address for this basic block. The partitioner is the partitioner on whose behalf this basic block is created. The partitioner is not stored in the basic block, but is only used to initialize certain data members of the block (such as its instruction dispatcher).

Definition at line 280 of file BasicBlock.h.

Referenced by create().

virtual Ptr Rose::BinaryAnalysis::Partitioner2::BasicBlock::create ( rose_addr_t  startVa,
const Partitioner partitioner 
) const
inlinevirtual

Virtual constructor.

The startVa is the starting address for this basic block. The partitioner is the partitioner on whose behalf this basic block is created. The partitioner is not stored in the basic block, but is only used to initialize certain data members of the block (such as its instruction dispatcher).

Definition at line 289 of file BasicBlock.h.

References instance().

void Rose::BinaryAnalysis::Partitioner2::BasicBlock::clearCache ( )
inline

Clear all cached data.

Thread safety: This method is thread safe.

Definition at line 300 of file BasicBlock.h.

bool Rose::BinaryAnalysis::Partitioner2::BasicBlock::isFrozen ( ) const
inline

Determine if basic block is read-only.

Returns true if read-only, false otherwise.

Thread safety: This method is thread safe.

Definition at line 314 of file BasicBlock.h.

const std::string& Rose::BinaryAnalysis::Partitioner2::BasicBlock::comment ( ) const
inline

Comment.

A basic block may have a multi-line, plain-text comment.

Thread safety: This method is not thread safe.

Definition at line 326 of file BasicBlock.h.

void Rose::BinaryAnalysis::Partitioner2::BasicBlock::comment ( const std::string &  s)
inline

Comment.

A basic block may have a multi-line, plain-text comment.

Thread safety: This method is not thread safe.

Definition at line 327 of file BasicBlock.h.

rose_addr_t Rose::BinaryAnalysis::Partitioner2::BasicBlock::address ( ) const
inline

Get the address for a basic block.

A basic block's address is also the starting address of its initial instruction. The initial instruction need not be the instruction with the lowest address, but rather the instruction which is always executed first by the basic block.

Thread safety: This method is thread-safe.

Definition at line 342 of file BasicBlock.h.

AddressIntervalSet Rose::BinaryAnalysis::Partitioner2::BasicBlock::insnAddresses ( ) const

Get all instruction addresses.

The return value is the set of all virtual addresses for both instruction starting addresses and the internal addresses of instructions.

Thread safety: This method is not thread safe.

rose_addr_t Rose::BinaryAnalysis::Partitioner2::BasicBlock::fallthroughVa ( ) const

Get the address after the end of the final instruction.

This is the address that immediately follows the final byte of the instruction that is executed last by the basic block. The final executed instruction need not be the instruction with the highest address.

Thread safety: This method is not thread safe.

size_t Rose::BinaryAnalysis::Partitioner2::BasicBlock::nInstructions ( ) const
inline

Get the number of instructions in this block.

Thread safety: This method is thread safe.

Definition at line 366 of file BasicBlock.h.

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

Return true if this basic block has no instructions.

A basic block is always expected to have at least one instruction whose address is the same as the basic block's address, and this method returns true if that instruction has not yet been discovered and appended to this basic block. A basic block may also own data blocks, but they are not counted by this method.

Thread safety: This method is thread-safe.

Definition at line 378 of file BasicBlock.h.

SgAsmInstruction* Rose::BinaryAnalysis::Partitioner2::BasicBlock::instructionExists ( rose_addr_t  startVa) const

Determine if this basic block contains an instruction at a specific address.

Returns a non-null instruction pointer if this basic block contains an instruction that starts at the specified address, returns null otherwise.

Thread safety: This method is not thread safe.

Sawyer::Optional<size_t> Rose::BinaryAnalysis::Partitioner2::BasicBlock::instructionExists ( SgAsmInstruction ) const

Determines if this basic block contains the specified instruction.

If the basic block contains the instruction then this method returns the index of this instruction within the block, otherwise it returns nothing.

Thread safety: This method is not thread safe.

const std::vector<SgAsmInstruction*>& Rose::BinaryAnalysis::Partitioner2::BasicBlock::instructions ( ) const
inline

Get the instructions for this block.

Instructions are returned in the order they would be executed (i.e., the order they were added to the block). Blocks in the undiscovered and not-existing states never have instructions (they return an empty vector); blocks in the incomplete and complete states always return at least one instruction.

Thread safety: This method is not thread safe since it returns a reference.

Definition at line 406 of file BasicBlock.h.

void Rose::BinaryAnalysis::Partitioner2::BasicBlock::append ( const Partitioner ,
SgAsmInstruction  
)

Append an instruction to a basic block.

If this is the first instruction then the instruction address must match the block's starting address, otherwise the new instruction must not already be a member of this basic block. No other attempt is made to verify the integrety of the intra-block control flow (i.e., we do not check that the previous instruction had a single successor which is the newly appended instruction). It is an error to attempt to append to a frozen block.

The partitioner argument is only used for adjusting the instruction semantics framework for the block.

When adding multiple instructions:

BasicBlock::Ptr bb = protoBlock->create(startingVa)
->append(insn1)->append(p, insn2)->append(p, insn3)
->freeze();

Thread safety: This method is not thread safe.

void Rose::BinaryAnalysis::Partitioner2::BasicBlock::pop ( )

Undo the latest append.

An append can be undone so that instructions can be appended, the result checked, and then undone. Only one level of undo is available.

Thread safety: This method is thread safe.

std::set<rose_addr_t> Rose::BinaryAnalysis::Partitioner2::BasicBlock::explicitConstants ( ) const

Set of explicit constants.

Traverses all the instructions of this basic block and returns all explicit constants found in the instruction operands. Some architectures call these "immediate values".

Thread safety: This method is thread safe.

size_t Rose::BinaryAnalysis::Partitioner2::BasicBlock::nDataBlocks ( ) const
inline

Get the number of data blocks owned.

Thread safety: This method is thread safe.

Definition at line 452 of file BasicBlock.h.

AddressIntervalSet Rose::BinaryAnalysis::Partitioner2::BasicBlock::dataAddresses ( ) const

Addresses that are part of static data.

Returns all addresses that are part of static data.

Thread safety: This method is not thread safe.

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

Determine if this basic block contains the specified data block or equivalent data block.

If the basic block owns the specified data block or an equivalent data block then this method returns a pointer to the existing data block, otherwise it returns the null pointer.

Thread safety: This method is not thread safe.

bool Rose::BinaryAnalysis::Partitioner2::BasicBlock::insertDataBlock ( const DataBlock::Ptr )

Make this basic block own the specified data block or equivalent data block.

If the specified data block is not yet owned by this basic block and the basic block contains no equivalent data block, then the specified data block is added as a member of this basic block and this method returns true. Otherwise, this basic block already contains the specified data block or an equivalent data block and the method returns false. A data block cannot be inserted when this basic block is frozen.

Thread safety: This method is not thread safe.

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

Remove specified or equivalent data block from this basic block.

If this basic block is in a detached state (i.e., not part of the CFG/AUM) then the specified data block or equivalent data block is removed from this basic block. Returns the data block that was erased, or null if none was erased.

It is an error to invoke this method on basic block that is attached to the CFG/AUM, for which isFrozen returns true. This method is a no-op if the specified data block is a null pointer.

const std::vector<DataBlock::Ptr>& Rose::BinaryAnalysis::Partitioner2::BasicBlock::dataBlocks ( ) const
inline

Data blocks owned.

Returned vector is sorted according to data block starting address.

Thread safety: This method is not thread safe since it returns a reference.

Definition at line 496 of file BasicBlock.h.

BasicBlockSemantics Rose::BinaryAnalysis::Partitioner2::BasicBlock::semantics ( ) const

Return information about semantics.

Although most of the returned information can also be obtained by calling individual accessor functions, this function returns all the information as a single atomic operation.

Thread safety: This method is thread safe.

void Rose::BinaryAnalysis::Partitioner2::BasicBlock::dropSemantics ( const Partitioner )

Drops semantic information.

This function deletes semantic information for the basic block and can be used to save space. The partitioner can be configured to drop semantic information when a basic block is attached to the CFG. The partitioner is used only for adjusting the instruction semantics framework for the block.

Thread safety: This method is thread safe.

BasicBlockSemantics Rose::BinaryAnalysis::Partitioner2::BasicBlock::undropSemantics ( const Partitioner )

Undrop semantics.

This is the inverse of dropSemantics. If semantics have been dropped then they will be recalculated if possible. If semantics have not been dropped then nothing happens. The partitioner is used only for adjusting the instruction semantics framework for the block.

Thread safety: This method is thread safe.

const Sawyer::Cached<Successors>& Rose::BinaryAnalysis::Partitioner2::BasicBlock::successors ( ) const
inline

Control flow successors.

The control flow successors indicate how control leaves the end of a basic block. These successors should be the most basic level of information; e.g., a basic block that results in an unconditional function call should not have an edge representing the return from that call. The successors are typically computed in the partitioner and cached in the basic block.

Thread safety: The accessor is not thread safe since it returns a reference; The mutator is thread safe.

Definition at line 545 of file BasicBlock.h.

void Rose::BinaryAnalysis::Partitioner2::BasicBlock::successors ( const Successors )

Control flow successors.

The control flow successors indicate how control leaves the end of a basic block. These successors should be the most basic level of information; e.g., a basic block that results in an unconditional function call should not have an edge representing the return from that call. The successors are typically computed in the partitioner and cached in the basic block.

Thread safety: The accessor is not thread safe since it returns a reference; The mutator is thread safe.

const Sawyer::Cached<std::set<rose_addr_t> >& Rose::BinaryAnalysis::Partitioner2::BasicBlock::ghostSuccessors ( ) const
inline

Ghost successors.

A ghost successor is a control flow successor that is present in an individual instruction, but not present in the broader scope of a basic block. Ghost successors typically occur when a conditional branch instruction in the middle of a basic block has an opaque predicate, causing it to become an unconditional branch. The return value is the union of the ghost successors for each instruction in the basic block, and is updated whenever the set of instructions in the basic block changes. The ghost successors are typically computed in the partitioner and cached in the basic block.

Thread safety: This method is not thread safe since it returns a reference.

Definition at line 559 of file BasicBlock.h.

void Rose::BinaryAnalysis::Partitioner2::BasicBlock::insertSuccessor ( const BaseSemantics::SValuePtr ,
EdgeType  type = E_NORMAL,
Confidence  confidence = ASSUMED 
)

Insert a new successor.

Inserts a new successor into the cached successor list. If the successor is already present then it is not added again (the comparison uses structural equivalance). Both the expression and the edge type are significant when comparing. For instance, it is permissible to have a function call edge and a call-return edge that both point to the fall-through address.

Thread safety: This method is not thread safe.

void Rose::BinaryAnalysis::Partitioner2::BasicBlock::insertSuccessor ( rose_addr_t  va,
size_t  nBits,
EdgeType  type = E_NORMAL,
Confidence  confidence = ASSUMED 
)

Insert a new successor.

Inserts a new successor into the cached successor list. If the successor is already present then it is not added again (the comparison uses structural equivalance). Both the expression and the edge type are significant when comparing. For instance, it is permissible to have a function call edge and a call-return edge that both point to the fall-through address.

Thread safety: This method is not thread safe.

void Rose::BinaryAnalysis::Partitioner2::BasicBlock::clearSuccessors ( )

Clear all successor information.

Thread safety: This method is thread safe.

const Sawyer::Cached<bool>& Rose::BinaryAnalysis::Partitioner2::BasicBlock::isFunctionCall ( ) const
inline

Is a function call?

If the basic block appears to be a function call then this property is set to true. A block is a function call if it appears to store a return value on the stack and then unconditionally branch to a function. It need not end with a specific CALL instruction, nor are all CALL instructions actually function calls. This property is typically computed in the partitioner and cached in the basic block.

Thread safety: This method is not thread safe since it returns a reference.

Definition at line 593 of file BasicBlock.h.

const Sawyer::Cached<bool>& Rose::BinaryAnalysis::Partitioner2::BasicBlock::isFunctionReturn ( ) const
inline

Is a function return?

This property indicates whether the basic block appears to be a return from a function call. A block is a return from a function call if, after the block is executed, the instruction pointer contains the value stored in memory one past the top of the stack.

Thread safety: This method is not thread safe since it returns a reference.

Definition at line 602 of file BasicBlock.h.

const Sawyer::Cached<bool>& Rose::BinaryAnalysis::Partitioner2::BasicBlock::mayReturn ( ) const
inline

May-return property.

This property holds a Boolean that indicates whether a function-return basic block is reachable from this basic block. In other words, if control enters this basic block, might the top stack frame eventually be popped?

Thread safety: This method is not thread safe since it returns a reference.

Definition at line 610 of file BasicBlock.h.

const Sawyer::Cached<bool>& Rose::BinaryAnalysis::Partitioner2::BasicBlock::popsStack ( ) const
inline

Pops stack property.

This property holds a Boolean that indicates whether this basic block is known to have a net stack popping effect.

Thread safety: This method is not thread safe since it returns a reference.

Definition at line 617 of file BasicBlock.h.

std::string Rose::BinaryAnalysis::Partitioner2::BasicBlock::printableName ( ) const

A printable name for this basic block.

Returns a string like 'basic block 0x10001234'.

Thread safety: This method is not thread safe.


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