A basic block for p-code operations. More...

#include <block.hh>

Inheritance diagram for BlockBasic:

Public Member Functions
Address	getEntryAddr (void) const
	Get the address of the (original) first operation to execute. More...

virtual Address	getStart (void) const

virtual Address	getStop (void) const

virtual block_type	getType (void) const

virtual FlowBlock *	subBlock (int4 i) const

virtual void	saveXmlBody (ostream &s) const

virtual void	restoreXmlBody (List::const_iterator &iter, List::const_iterator enditer, BlockMap &resolver)
	Restore details about this FlowBlock from an XML stream. More...

virtual void	printHeader (ostream &s) const
	Print a simple description of this to stream. More...

virtual void	printRaw (ostream &s) const

virtual void	emit (PrintLanguage *lng) const
	Emit the instructions in this FlowBlock as structured code. More...

virtual const FlowBlock *	getExitLeaf (void) const

virtual PcodeOp *	lastOp (void) const

virtual bool	negateCondition (bool toporbottom)
	Flip the condition computed by this. More...

virtual FlowBlock *	getSplitPoint (void)
	Get the leaf splitting block. More...

virtual int4	flipInPlaceTest (vector< PcodeOp * > &fliplist) const
	Test normalizing the conditional branch in this. More...

virtual void	flipInPlaceExecute (void)
	Perform the flip to normalize conditional branch executed by this block. More...

virtual bool	isComplex (void) const

bool	unblockedMulti (int4 outslot) const
	Check if this block can be removed without introducing inconsistencies. More...

bool	hasOnlyMarkers (void) const
	Does this block contain only MULTIEQUAL and INDIRECT ops. More...

bool	isDoNothing (void) const
	Should this block should be removed. More...

Public Member Functions inherited from FlowBlock
	FlowBlock (void)
	Construct a block with no edges.

virtual void	markLabelBumpUp (bool bump)
	Let hierarchical blocks steal labels of their (first) components. More...

virtual void	printTree (ostream &s, int4 level) const
	Print tree structure of any blocks owned by this. More...

virtual bool	preferComplement (Funcdata &data)
	Rearrange this hierarchy to simplify boolean expressions. More...

virtual FlowBlock *	nextFlowAfter (const FlowBlock *bl) const
	Get the leaf FlowBlock that will execute after the given FlowBlock. More...

virtual void	saveXmlHeader (ostream &s) const
	Save basic information as XML attributes. More...

virtual void	restoreXmlHeader (const Element *el)
	Restore basic information for XML attributes. More...

void	saveXmlEdges (ostream &s) const
	Save edge information to an XML stream. More...

void	restoreXmlEdges (List::const_iterator &iter, List::const_iterator enditer, BlockMap &resolver)
	Restore edges from an XML stream. More...

void	saveXml (ostream &s) const
	Write out this to an XML stream. More...

void	restoreXml (const Element *el, BlockMap &resolver)
	Restore this from an XML stream. More...

const FlowBlock *	nextInFlow (void) const
	Return next block to be executed in flow. More...

void	setGotoBranch (int4 i)
	Mark a goto branch. More...

bool	isJumpTarget (void) const
	Return true if non-fallthru jump flows into this. More...

const FlowBlock *	getFrontLeaf (void) const
	Get the first leaf FlowBlock. More...

FlowBlock *	getFrontLeaf (void)
	Get the first leaf FlowBlock. More...

int4	calcDepth (const FlowBlock *leaf) const
	Get the depth of the given component FlowBlock. More...

bool	dominates (const FlowBlock *subBlock) const
	Does this block dominate the given block. More...

bool	restrictedByConditional (const FlowBlock *cond) const
	Check if the condition from the given block holds for this block. More...

bool	hasLoopIn (void) const
	Is there a looping edge coming into this block. More...

bool	hasLoopOut (void) const
	Is there a looping edge going out of this block. More...

int4	getInIndex (const FlowBlock *bl) const
	Get the incoming edge index for the given FlowBlock. More...

int4	getOutIndex (const FlowBlock *bl) const
	Get the outgoing edge index for the given FlowBlock. More...

bool	isDecisionOut (int4 i) const
	Can this and the i-th output be merged into a BlockIf or BlockList.

bool	isDecisionIn (int4 i) const
	Can this and the i-th input be merged into a BlockIf or BlockList.

bool	isLoopDAGOut (int4 i) const
	Is the i-th outgoing edge part of the DAG sub-graph.

bool	isLoopDAGIn (int4 i) const
	Is the i-th incoming edge part of the DAG sub-graph.

JumpTable *	getJumptable (void) const
	Get the JumpTable associated this block. More...

Static Public Member Functions
static bool	noInterveningStatement (PcodeOp first, int4 path, PcodeOp last)
	Check if there is meaningful activity between two branch instructions. More...

Static Public Member Functions inherited from FlowBlock
static block_type	nameToType (const string &name)
	Get the block_type associated with a name string. More...

static string	typeToName (block_type bt)
	Get the name string associated with a block_type. More...

static bool	compareBlockIndex (const FlowBlock bl1, const FlowBlock bl2)
	Compare FlowBlock by index. More...

static bool	compareFinalOrder (const FlowBlock bl1, const FlowBlock bl2)
	Final FlowBlock comparison. More...

static FlowBlock *	findCommonBlock (FlowBlock bl1, FlowBlock bl2)
	Find the common dominator of two FlowBlocks. More...

static FlowBlock *	findCommonBlock (const vector< FlowBlock * > &blockSet)
	Find common dominator of multiple FlowBlocks. More...

Private Member Functions
void	insert (list< PcodeOp * >::iterator iter, PcodeOp *inst)
	Insert p-code operation at a given position. More...

void	setInitialRange (const Address &beg, const Address &end)
	Set the initial address range of the block. More...

void	setOrder (void)
	Reset the SeqNum::order field for all PcodeOp objects in this block. More...

void	removeOp (PcodeOp *inst)
	Remove PcodeOp from this basic block. More...

Private Attributes
list< PcodeOp * >	op
	The sequence of p-code operations.

Funcdata *	data
	The function of which this block is a part.

RangeList	cover
	Original range of addresses covered by this basic block.

Friends
class	Funcdata

Additional Inherited Members
Public Types inherited from FlowBlock
enum	block_type { t_plain, t_basic, t_graph, t_copy, t_goto, t_multigoto, t_ls, t_condition, t_if, t_whiledo, t_dowhile, t_switch, t_infloop }
	The possible block types.

enum	block_flags { f_goto_goto = 1, f_break_goto = 2, f_continue_goto = 4, f_switch_out = 0x10, f_unstructured_targ = 0x20, f_mark = 0x80, f_mark2 = 0x100, f_entry_point = 0x200, f_interior_gotoout = 0x400, f_interior_gotoin = 0x800, f_label_bumpup = 0x1000, f_donothing_loop = 0x2000, f_dead = 0x4000, f_whiledo_overflow = 0x8000, f_flip_path = 0x10000, f_joined_block = 0x20000, f_duplicate_block = 0x40000 }
	Boolean properties of blocks. More...

enum	edge_flags { f_goto_edge = 1, f_loop_edge = 2, f_defaultswitch_edge = 4, f_irreducible = 8, f_tree_edge = 0x10, f_forward_edge = 0x20, f_cross_edge = 0x40, f_back_edge = 0x80, f_loop_exit_edge = 0x100 }
	Boolean properties on edges. More...

Detailed Description

A basic block for p-code operations.

A basic block is a maximal sequence of p-code operations (PcodeOp) that, within the context of a function, always execute starting with the first operation in sequence through in order to the last operation. Any decision points in the control flow of a function manifest as branching operations (BRANCH, CBRANCH, BRANCHIND) that necessarily occur as the last operation in a basic block.

Every Funcdata object implements the control-flow graph of the underlying function using BlockBasic objects as the underlying nodes of the graph. The decompiler structures code by making a copy of this graph and then overlaying a hierarchy of structured nodes on top of it.

The block also keeps track of the original range of addresses of instructions constituting the block. As decompiler transformations progress, the set of addresses associated with the current set of PcodeOps my migrate away from this original range.

Member Function Documentation

◆ emit()

virtual void BlockBasic::emit ( PrintLanguage * lng ) const

inlinevirtual

Emit the instructions in this FlowBlock as structured code.

This is the main entry point, at the control-flow level, for printing structured code.

Parameters

lng	is the PrintLanguage that provides details of the high-level language being printed

Reimplemented from FlowBlock.

References PrintLanguage::emitBlockBasic().

◆ flipInPlaceExecute()

void BlockBasic::flipInPlaceExecute ( void )

virtual

Perform the flip to normalize conditional branch executed by this block.

This reverses the outgoing edge order in the right basic blocks, but does not modify the instructions directly.

Reimplemented from FlowBlock.

References PcodeOp::fallthru_true, FlowBlock::negateCondition(), and op.

Referenced by ActionNormalizeBranches::apply().

◆ flipInPlaceTest()

int4 BlockBasic::flipInPlaceTest ( vector< PcodeOp * > & fliplist ) const

virtual

Test normalizing the conditional branch in this.

Find the set of PcodeOp objects that need to be adjusted to flip the condition this FlowBlock calculates.

Return:

0 if the flip would normalize the condition
1 if the flip doesn't affect normalization of the condition
2 if the flip produces an unnormalized condition
Parameters

fliplist will contain the PcodeOps that need to be adjusted

Returns
0 if the condition will be normalized, 1 or 2 otherwise

Reimplemented from FlowBlock.

References CPUI_CBRANCH, op, and opFlipInPlaceTest().

◆ getEntryAddr()

Address BlockBasic::getEntryAddr ( void ) const

Get the address of the (original) first operation to execute.

This relies slightly on normal semantics: when instructions fall-thru during execution, the associated address increases.

Returns: the address of the original entry point instruction for this block

References cover, RangeList::getFirstRange(), Address::getOffset(), RangeList::getRange(), Address::getSpace(), and op.

Referenced by PrintC::emitLabel().

◆ getSplitPoint()

FlowBlock * BlockBasic::getSplitPoint ( void )

virtual

Get the leaf splitting block.

If this block ends with a conditional branch, return the deepest component block that performs the split. This component needs to be able to perform flipInPlaceTest() and flipInPlaceExecute()

Returns: the component FlowBlock or NULL if this doesn't end in a conditional branch

Reimplemented from FlowBlock.

◆ hasOnlyMarkers()

bool BlockBasic::hasOnlyMarkers ( void ) const

Does this block contain only MULTIEQUAL and INDIRECT ops.

This is a crucial test for whether this block is doing anything substantial or is a candidate for removal. Even blocks that "do nothing" have some kind of branch and placeholder operations (MULTIEQUAL and INDIRECT) for data flowing through the block. This tests if there is any other operation going on.

Returns: true if there only MULTIEQUAL, INDIRECT, and branch operations in this

References op.

Referenced by isDoNothing(), and noInterveningStatement().

◆ insert()

void BlockBasic::insert	(	list< PcodeOp * >::iterator	iter,
		PcodeOp *	inst
	)

private

Insert p-code operation at a given position.

The operation is inserted before the PcodeOp pointed at by the iterator. This method also assigns the ordering index for the PcodeOp, getSeqNum().getOrder()

Parameters

iter	points at the PcodeOp to insert before
inst	is the PcodeOp to insert

References CPUI_BRANCHIND, FlowBlock::f_switch_out, op, and setOrder().

Referenced by Funcdata::opInsert().

◆ isDoNothing()

bool BlockBasic::isDoNothing ( void ) const

Should this block should be removed.

Check if this block is doing anything useful.

Returns: true if the block does nothing and should be removed

References CPUI_BRANCHIND, and hasOnlyMarkers().

Referenced by ActionDoNothing::apply().

◆ negateCondition()

bool BlockBasic::negateCondition ( bool toporbottom )

virtual

Flip the condition computed by this.

Flip the order of outgoing edges (at least). This should also affect the original op causing the condition. Note: we don't have to flip at all levels of the hierarchy only at the top and at the bottom

Parameters

toporbottom is true if this is the top outermost block of the hierarchy getting negated

Returns: true if a change was made to data-flow

Reimplemented from FlowBlock.

References PcodeOp::boolean_flip, PcodeOp::fallthru_true, FlowBlock::negateCondition(), and op.

◆ noInterveningStatement()

bool BlockBasic::noInterveningStatement	(	PcodeOp *	first,
		int4	path,
		PcodeOp *	last
	)

static

Check if there is meaningful activity between two branch instructions.

The first branch is assumed to be a CBRANCH one edge of which flows into the other branch. The flow can be through 1 or 2 blocks. If either block performs an operation other than MULTIEQUAL, INDIRECT (or the branch), then return false.

Parameters

first	is the CBRANCH operation
path	is the index of the edge to follow to the other branch
last	is the other branch operation

Returns: true if there is no meaningful activity

References hasOnlyMarkers().

Referenced by JumpBasic::foldInOneGuard().

◆ printHeader()

void BlockBasic::printHeader ( ostream & s ) const

virtual

Print a simple description of this to stream.

Only print a header for this single block

Parameters

s	is the output stream

Reimplemented from FlowBlock.

References FlowBlock::printHeader().

◆ removeOp()

void BlockBasic::removeOp ( PcodeOp * inst )

private

Remove PcodeOp from this basic block.

Parameters

inst	is the PcodeOp to remove, which must be in the block

References PcodeOp::basiciter, and op.

◆ restoreXmlBody()

void BlockBasic::restoreXmlBody	(	List::const_iterator &	iter,
		List::const_iterator	enditer,
		BlockMap &	resolver
	)

virtual

Restore details about this FlowBlock from an XML stream.

Parameters

iter	is an iterator to XML elements containing component tags etc.
enditer	marks the end of the XML tags
resolver	is used to recover FlowBlock objects based on XML references

Reimplemented from FlowBlock.

References cover, and RangeList::restoreXml().

◆ setInitialRange()

void BlockBasic::setInitialRange	(	const Address &	beg,
		const Address &	end
	)

private

Set the initial address range of the block.

In terms of machine instructions, a basic block always covers a range of addresses, from its first instruction to its last. This method establishes that range.

Parameters

beg	is the address of the first instruction in the block
end	is the address of the last instruction in the block

References cover, Address::getOffset(), Address::getSpace(), and RangeList::insertRange().

Referenced by Funcdata::nodeJoinCreateBlock(), and Funcdata::setBasicBlockRange().

◆ setOrder()

void BlockBasic::setOrder ( void )

private

Reset the SeqNum::order field for all PcodeOp objects in this block.

The SeqNum::order field for each PcodeOp must mirror the ordering of that PcodeOp within this block. Insertions are usually handled by calculating an appropriate SeqNum::order field for the new PcodeOp, but sometime there isn't enough room between existing ops. This method is then called to recalculate the SeqNum::order field for all PcodeOp objects in this block, reestablishing space between the field values.

References op.

Referenced by insert(), and Funcdata::spliceBlockBasic().

◆ unblockedMulti()

bool BlockBasic::unblockedMulti ( int4 outslot ) const

Check if this block can be removed without introducing inconsistencies.

Does removing this block leads to redundant MULTIEQUAL entries which are inconsistent. A MULTIEQUAL can hide an implied copy, in which case this block is actually doing something and shouldn't be removed.

Parameters

outslot is the index of the outblock that this is getting collapsed to

Returns: true if there is no implied COPY

References CPUI_MULTIEQUAL, FlowBlock::getInIndex(), and op.

Referenced by ActionDoNothing::apply().

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

block.hh
block.cc

Public Member Functions

Static Public Member Functions

Private Member Functions

Private Attributes

Friends

Additional Inherited Members

Detailed Description

Member Function Documentation

◆ emit()

◆ flipInPlaceExecute()

◆ flipInPlaceTest()

◆ getEntryAddr()

◆ getSplitPoint()

◆ hasOnlyMarkers()

◆ insert()

◆ isDoNothing()

◆ negateCondition()

◆ noInterveningStatement()

◆ printHeader()

◆ removeOp()

◆ restoreXmlBody()

◆ setInitialRange()

◆ setOrder()

◆ unblockedMulti()