A control-flow block built out of sub-components. More...

#include <block.hh>

Inheritance diagram for ghidra::BlockGraph:

Public Member Functions
void	clear (void)
	Clear all component FlowBlock objects.

virtual	~BlockGraph (void)
	Destructor.

const vector< FlowBlock * > &	getList (void) const
	Get the list of component FlowBlock objects.

int4	getSize (void) const
	Get the number of components.

FlowBlock *	getBlock (int4 i) const
	Get the i-th component.

virtual block_type	getType (void) const
	Get the FlowBlock type of this.

virtual FlowBlock *	subBlock (int4 i) const
	Get the i-th component block.

virtual void	markUnstructured (void)
	Mark target blocks of any unstructured edges.

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

virtual void	scopeBreak (int4 curexit, int4 curloopexit)
	Mark unstructured edges that should be breaks.

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

virtual void	printRaw (ostream &s) const
	Print raw instructions contained in this FlowBlock.

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

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

virtual void	finalTransform (Funcdata &data)
	Do any structure driven final transforms.

virtual void	finalizePrinting (Funcdata &data) const
	Make any final configurations necessary to print the block.

virtual void	encodeBody (Encoder &encoder) const
	Encode detail about components to a stream.

virtual void	decodeBody (Decoder &decoder)
	Restore details about this FlowBlock from an element stream. More...

void	decode (Decoder &decoder)
	Decode this BlockGraph from a stream. More...

void	addEdge (FlowBlock begin, FlowBlock end)
	Add a directed edge between component FlowBlocks. More...

void	addLoopEdge (FlowBlock *begin, int4 outindex)
	Mark a given edge as a loop edge. More...

void	removeEdge (FlowBlock begin, FlowBlock end)
	Remove an edge between component FlowBlocks. More...

void	switchEdge (FlowBlock in, FlowBlock outbefore, FlowBlock *outafter)
	Move an edge from one out FlowBlock to another. More...

void	moveOutEdge (FlowBlock blold, int4 slot, FlowBlock blnew)
	Move indicated out edge to a new FlowBlock. More...

void	removeBlock (FlowBlock *bl)
	Remove a FlowBlock from this BlockGraph. More...

void	removeFromFlow (FlowBlock *bl)
	Remove given FlowBlock preserving flow in this. More...

void	removeFromFlowSplit (FlowBlock *bl, bool flipflow)
	Remove FlowBlock splitting flow between input and output edges. More...

void	spliceBlock (FlowBlock *bl)
	Splice given FlowBlock together with its output. More...

void	setStartBlock (FlowBlock *bl)
	Set the entry point FlowBlock for this graph. More...

FlowBlock *	getStartBlock (void) const
	Get the entry point FlowBlock. More...

FlowBlock *	newBlock (void)
	Build a new plain FlowBlock. More...

BlockBasic *	newBlockBasic (Funcdata *fd)
	Build a new BlockBasic. More...

BlockCopy *	newBlockCopy (FlowBlock *bl)
	Build a new BlockCopy. More...

BlockGoto *	newBlockGoto (FlowBlock *bl)
	Build a new BlockGoto. More...

BlockMultiGoto *	newBlockMultiGoto (FlowBlock *bl, int4 outedge)
	Build a new BlockMultiGoto. More...

BlockList *	newBlockList (const vector< FlowBlock *> &nodes)
	Build a new BlockList. More...

BlockCondition *	newBlockCondition (FlowBlock b1, FlowBlock b2)
	Build a new BlockCondition. More...

BlockIf *	newBlockIfGoto (FlowBlock *cond)
	Build a new BlockIfGoto. More...

BlockIf *	newBlockIf (FlowBlock cond, FlowBlock tc)
	Build a new BlockIf. More...

BlockIf *	newBlockIfElse (FlowBlock cond, FlowBlock tc, FlowBlock *fc)
	Build a new BlockIfElse. More...

BlockWhileDo *	newBlockWhileDo (FlowBlock cond, FlowBlock cl)
	Build a new BlockWhileDo. More...

BlockDoWhile *	newBlockDoWhile (FlowBlock *condcl)
	Build a new BlockDoWhile. More...

BlockInfLoop *	newBlockInfLoop (FlowBlock *body)
	Build a new BlockInfLoop. More...

BlockSwitch *	newBlockSwitch (const vector< FlowBlock *> &cs, bool hasExit)
	Build a new BlockSwitch. More...

void	orderBlocks (void)

void	buildCopy (const BlockGraph &graph)
	Build a copy of a BlockGraph. More...

void	clearVisitCount (void)
	Clear the visit count in all node FlowBlocks.

void	calcForwardDominator (const vector< FlowBlock *> &rootlist)
	Calculate forward dominators. More...

void	buildDomTree (vector< vector< FlowBlock *> > &child) const
	Build the dominator tree. More...

int4	buildDomDepth (vector< int4 > &depth) const
	Calculate dominator depths. More...

void	buildDomSubTree (vector< FlowBlock > &res, FlowBlock root) const
	Collect nodes from a dominator sub-tree. More...

void	calcLoop (void)
	Calculate loop edges. More...

void	collectReachable (vector< FlowBlock > &res, FlowBlock bl, bool un) const
	Collect reachable/unreachable FlowBlocks from a given start FlowBlock. More...

void	structureLoops (vector< FlowBlock *> &rootlist)
	Label loop edges. More...

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

virtual	~FlowBlock (void)
	Destructor.

int4	getIndex (void) const
	Get the index assigned to this block.

FlowBlock *	getParent (void)
	Get the parent FlowBlock of this.

FlowBlock *	getImmedDom (void) const
	Get the immediate dominator FlowBlock.

FlowBlock *	getCopyMap (void) const
	Get the mapped FlowBlock.

const FlowBlock *	getParent (void) const
	Get the parent FlowBlock of this.

uint4	getFlags (void) const
	Get the block_flags properties.

virtual Address	getStart (void) const
	Get the starting address of code in this FlowBlock.

virtual Address	getStop (void) const
	Get the ending address of code in this FlowBlock.

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

virtual const FlowBlock *	getExitLeaf (void) const
	Get the FlowBlock to which this block exits.

virtual PcodeOp *	lastOp (void) const
	Get the last PcodeOp executed by this FlowBlock.

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

virtual bool	preferComplement (Funcdata &data)
	Rearrange this hierarchy to simplify boolean expressions. 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
	Is this too complex to be a condition (BlockCondition)

virtual void	encodeHeader (Encoder &encoder) const
	Encode basic information as attributes. More...

virtual void	decodeHeader (Decoder &decoder)
	Decode basic information from element attributes. More...

void	encodeEdges (Encoder &encoder) const
	Encode edge information to a stream. More...

void	decodeEdges (Decoder &decoder, BlockMap &resolver)
	Restore edges from an encoded stream. More...

void	encode (Encoder &encoder) const
	Encode this to a stream. More...

void	decode (Decoder &decoder, BlockMap &resolver)
	Decode this from a stream. More...

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

void	setVisitCount (int4 i)
	Set the number of times this block has been visited.

int4	getVisitCount (void) const
	Get the count of visits.

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

void	setDefaultSwitch (int4 pos)
	Mark an edge as the switch default. More...

bool	isMark (void) const
	Return true if this block has been marked.

void	setMark (void)
	Mark this block.

void	clearMark (void)
	Clear any mark on this block.

void	setDonothingLoop (void)
	Label this as a do nothing loop.

void	setDead (void)
	Label this as dead.

bool	hasSpecialLabel (void) const
	Return true if this uses a different label.

bool	isJoined (void) const
	Return true if this is a joined basic block.

bool	isDuplicated (void) const
	Return true if this is a duplicated block.

void	setLoopExit (int4 i)
	Label the edge exiting this as a loop.

void	clearLoopExit (int4 i)
	Clear the loop exit edge.

void	setBackEdge (int4 i)
	Label the back edge of a loop.

bool	getFlipPath (void) const
	Have out edges been flipped.

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

FlowBlock *	getFalseOut (void) const
	Get the false output FlowBlock.

FlowBlock *	getTrueOut (void) const
	Get the true output FlowBlock.

FlowBlock *	getOut (int4 i)
	Get the i-th output FlowBlock.

const FlowBlock *	getOut (int4 i) const
	Get i-th output FlowBlock.

int4	getOutRevIndex (int4 i) const
	Get the input index of the i-th output FlowBlock.

FlowBlock *	getIn (int4 i)
	Get the i-th input FlowBlock.

const FlowBlock *	getIn (int4 i) const
	Get the i-th input FlowBlock.

int4	getInRevIndex (int4 i) const
	Get the output index of the i-th input FlowBlock.

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...

int4	sizeOut (void) const
	Get the number of out edges.

int4	sizeIn (void) const
	Get the number of in edges.

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...

bool	isLoopIn (int4 i) const
	Is the i-th incoming edge a loop edge.

bool	isLoopOut (int4 i) const
	Is the i-th outgoing edge a loop edge.

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	isDefaultBranch (int4 i) const
	Is the i-th out edge the switch default edge.

bool	isLabelBumpUp (void) const
	Are labels for this printed by the parent.

bool	isUnstructuredTarget (void) const
	Is this the target of an unstructured goto.

bool	isInteriorGotoTarget (void) const
	Is there an unstructured goto to this block's interior.

bool	hasInteriorGoto (void) const
	Is there an unstructured goto out of this block's interior.

bool	isEntryPoint (void) const
	Is the entry point of the function.

bool	isSwitchOut (void) const
	Is this a switch block.

bool	isDonothingLoop (void) const
	Is this a do nothing block.

bool	isDead (void) const
	Is this block dead.

bool	isTreeEdgeIn (int4 i) const
	Is the i-th incoming edge part of the spanning tree.

bool	isBackEdgeIn (int4 i) const
	Is the i-th incoming edge a back edge.

bool	isBackEdgeOut (int4 i) const
	Is the i-th outgoing edge a back edge.

bool	isIrreducibleOut (int4 i) const
	Is the i-th outgoing edge an irreducible edge.

bool	isIrreducibleIn (int4 i) const
	Is the i-th incoming edge an irreducible edge.

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.

bool	isGotoIn (int4 i) const
	Is the i-th incoming edge unstructured.

bool	isGotoOut (int4 i) const
	Is the i-th outgoing edge unstructured.

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

Protected Member Functions
void	swapBlocks (int4 i, int4 j)
	Swap the positions two component FlowBlocks. More...

Protected Member Functions inherited from ghidra::FlowBlock
void	setFlag (uint4 fl)
	Set a boolean property.

void	clearFlag (uint4 fl)
	Clear a boolean property.

Static Protected Member Functions
static void	markCopyBlock (FlowBlock *bl, uint4 fl)
	Set properties on the first leaf FlowBlock. More...

Private Member Functions
void	addBlock (FlowBlock *bl)
	Add a component FlowBlock. More...

void	forceOutputNum (int4 i)
	Force number of outputs. More...

void	selfIdentify (void)
	Inherit our edges from the edges of our components. More...

void	identifyInternal (BlockGraph ident, const vector< FlowBlock > &nodes)
	Move nodes from this into a new BlockGraph. More...

void	clearEdgeFlags (uint4 fl)
	Clear a set of properties from all edges in the graph. More...

void	findSpanningTree (vector< FlowBlock > &preorder, vector< FlowBlock > &rootlist)
	Find a spanning tree (skipping irreducible edges). More...

bool	findIrreducible (const vector< FlowBlock *> &preorder, int4 &irreduciblecount)
	Identify irreducible edges. More...

void	forceFalseEdge (const FlowBlock *out0)
	Force the false out edge to go to the given FlowBlock. More...

Static Private Member Functions
static FlowBlock *	createVirtualRoot (const vector< FlowBlock *> &rootlist)
	Create a single root block. More...

Private Attributes
vector< FlowBlock * >	list
	List of FlowBlock components within this super-block.

Additional Inherited Members
Public Types inherited from ghidra::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...

Static Public Member Functions inherited from ghidra::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...

Detailed Description

A control-flow block built out of sub-components.

This is the core class for building a hierarchy of control-flow blocks. A set of control-flow blocks can be grouped together and viewed as a single block, with its own input and output blocks. All the code structuring elements (BlockList, BlockIf, BlockWhileDo, etc.) derive from this.

Member Function Documentation

◆ addBlock()

void ghidra::BlockGraph::addBlock ( FlowBlock * bl )

private

Add a component FlowBlock.

Add the given FlowBlock to the list and make this the parent Update index so that it has the minimum over all components

Parameters

bl	is the given FlowBlock

References ghidra::FlowBlock::index, and ghidra::FlowBlock::parent.

Referenced by identifyInternal().

◆ addEdge()

void ghidra::BlockGraph::addEdge	(	FlowBlock *	begin,
		FlowBlock *	end
	)

Add a directed edge between component FlowBlocks.

Parameters

begin	is the start FlowBlock
end	is the stop FlowBlock

References ghidra::FlowBlock::addInEdge(), and ghidra::FlowBlock::parent.

Referenced by ghidra::FlowInfo::connectBasic(), ghidra::FlowInfo::generateBlocks(), ghidra::Funcdata::nodeJoinCreateBlock(), and ghidra::Funcdata::nodeSplitBlockEdge().

◆ addLoopEdge()

void ghidra::BlockGraph::addLoopEdge	(	FlowBlock *	begin,
		int4	outindex
	)

Mark a given edge as a loop edge.

Parameters

begin	is a given component FlowBlock
outindex	is the index of the out edge to mark as a loop

References ghidra::FlowBlock::parent, and ghidra::FlowBlock::setOutEdgeFlag().

◆ buildCopy()

void ghidra::BlockGraph::buildCopy ( const BlockGraph & graph )

Build a copy of a BlockGraph.

Construct a copy of the given BlockGraph in this. The nodes of the copy will be official BlockCopy objects which will contain a reference to their corresponding FlowBlock in the given graph. All edges will be duplicated.

Parameters

graph is the given BlockGraph to copy

References list.

Referenced by ghidra::ActionBlockStructure::apply(), ghidra::IfcStructureBlocks::execute(), and ghidra::StructureGraph::rawAction().

◆ buildDomDepth()

int4 ghidra::BlockGraph::buildDomDepth ( vector< int4 > & depth ) const

Calculate dominator depths.

Associate every FlowBlock node in this graph with its depth in the dominator tree. The dominator root has depth 1, the nodes it immediately dominates have depth 2, etc.

Parameters

depth is array that will be populated with depths

Returns: the maximum depth across all nodes

References ghidra::FlowBlock::getIndex(), and ghidra::FlowBlock::immed_dom.

◆ buildDomSubTree()

void ghidra::BlockGraph::buildDomSubTree	(	vector< FlowBlock *> &	res,
		FlowBlock *	root
	)		const

Collect nodes from a dominator sub-tree.

Collect all nodes in the dominator sub-tree starting at a given root FlowBlock. We assume blocks in are reverse post order.

Parameters

res	will hold the list of nodes in the sub-tree
root	is the given root FlowBlock

References ghidra::FlowBlock::getImmedDom(), and ghidra::FlowBlock::getIndex().

◆ buildDomTree()

void ghidra::BlockGraph::buildDomTree ( vector< vector< FlowBlock *> > & child ) const

Build the dominator tree.

Associate dominator children with each node via a list (of lists) indexed by the FlowBlock index.

Parameters

child is the initially empty list of lists

References ghidra::FlowBlock::immed_dom, and ghidra::FlowBlock::index.

◆ calcForwardDominator()

void ghidra::BlockGraph::calcForwardDominator ( const vector< FlowBlock *> & rootlist )

Calculate forward dominators.

Calculate the immediate dominator for each FlowBlock node in this BlockGraph, for forward control-flow. The algorithm must be provided a list of entry points for the graph. We assume the blocks are in reverse post-order and this is reflected in the index field. Using an algorithm by Cooper, Harvey, and Kennedy. Softw. Pract. Exper. 2001; 4: 1-10

Parameters

rootlist is the list of entry point FlowBlocks

References ghidra::FlowBlock::getIn(), ghidra::FlowBlock::getOut(), ghidra::FlowBlock::immed_dom, ghidra::FlowBlock::index, ghidra::FlowBlock::removeOutEdge(), ghidra::FlowBlock::sizeIn(), and ghidra::FlowBlock::sizeOut().

Referenced by ghidra::IfcStructureBlocks::execute(), ghidra::StructureGraph::rawAction(), and ghidra::Funcdata::structureReset().

◆ calcLoop()

void ghidra::BlockGraph::calcLoop ( void )

Calculate loop edges.

This algorithm identifies a set of edges such that, if the edges are removed, the remaining graph has NO directed cycles The algorithm works as follows: Starting from the start block, do a depth first search through the "out" edges of the block. If the outblock is already on the current path from root to node, we have found a cycle, we add the last edge to the list and continue pretending that edge didn't exist. If the outblock is not on the current path but has been visited before, we can truncate the search. This is now only applied as a failsafe if the graph has irreducible edges.

References ghidra::FlowBlock::clearFlag(), ghidra::FlowBlock::flags, ghidra::FlowBlock::getOut(), ghidra::FlowBlock::isLoopOut(), ghidra::FlowBlock::setFlag(), and ghidra::FlowBlock::sizeOut().

◆ clearEdgeFlags()

void ghidra::BlockGraph::clearEdgeFlags ( uint4 fl )

private

Clear a set of properties from all edges in the graph.

Parameters

fl	is the set of boolean properties

References ghidra::FlowBlock::intothis, and ghidra::FlowBlock::outofthis.

◆ collectReachable()

void ghidra::BlockGraph::collectReachable	(	vector< FlowBlock *> &	res,
		FlowBlock *	bl,
		bool	un
	)		const

Collect reachable/unreachable FlowBlocks from a given start FlowBlock.

If the boolean un is true, collect unreachable blocks. Otherwise collect reachable blocks.

Parameters

res	will hold the reachable or unreachable FlowBlocks
bl	is the starting FlowBlock
un	toggles reachable,unreachable

References ghidra::FlowBlock::clearMark(), ghidra::FlowBlock::getOut(), ghidra::FlowBlock::isMark(), ghidra::FlowBlock::setMark(), and ghidra::FlowBlock::sizeOut().

Referenced by ghidra::Funcdata::removeUnreachableBlocks().

◆ createVirtualRoot()

FlowBlock * ghidra::BlockGraph::createVirtualRoot ( const vector< FlowBlock *> & rootlist )

staticprivate

Create a single root block.

Some algorithms need a graph with a single entry node. Given multiple entry points, this routine creates an artificial root with no in edges and an out edge to each of the real entry points. The resulting root FlowBlock isn't owned by any BlockGraph, and the caller is responsible for freeing it.

Parameters

rootlist is the given set of entry point FlowBlocks

Returns: the new artificial root FlowBlock

◆ decode()

void ghidra::BlockGraph::decode ( Decoder & decoder )

Decode this BlockGraph from a stream.

Parse a <block> element. This is currently just a wrapper around the FlowBlock::decode() that sets of the BlockMap resolver

Parameters

decoder is the stream decoder

References ghidra::FlowBlock::decode().

Referenced by ghidra::IfcStructureBlocks::execute().

◆ decodeBody()

void ghidra::BlockGraph::decodeBody ( Decoder & decoder )

virtual

Restore details about this FlowBlock from an element stream.

Parameters

decoder is the stream decoder

Reimplemented from ghidra::FlowBlock.

References ghidra::Decoder::closeElement(), ghidra::BlockMap::createBlock(), ghidra::FlowBlock::decode(), ghidra::FlowBlock::index, ghidra::Decoder::openElement(), ghidra::Decoder::peekElement(), ghidra::Decoder::readSignedInteger(), ghidra::Decoder::readString(), and ghidra::BlockMap::sortList().

◆ emit()

virtual void ghidra::BlockGraph::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 ghidra::FlowBlock.

Reimplemented in ghidra::BlockSwitch, ghidra::BlockInfLoop, ghidra::BlockDoWhile, ghidra::BlockWhileDo, ghidra::BlockIf, ghidra::BlockCondition, ghidra::BlockList, ghidra::BlockMultiGoto, and ghidra::BlockGoto.

References ghidra::BlockEdge::decode(), and ghidra::PrintLanguage::emitBlockGraph().

◆ findIrreducible()

bool ghidra::BlockGraph::findIrreducible	(	const vector< FlowBlock *> &	preorder,
		int4 &	irreduciblecount
	)

private

Identify irreducible edges.

Assuming the spanning tree has been properly labeled using findSpanningTree(), test for and label and irreducible edges (the test ignores any edges already labeled as irreducible). Return true if the spanning tree needs to be rebuilt, because one of the tree edges is irreducible. Original algorithm due to Tarjan.

Parameters

preorder	is the list of FlowBlocks in pre-order
irreduciblecount	will hold the number of irreducible edges

Returns: true if the spanning tree needs to be rebuilt

References ghidra::FlowBlock::clearMark(), ghidra::FlowBlock::clearOutEdgeFlag(), ghidra::FlowBlock::copymap, ghidra::FlowBlock::getIn(), ghidra::FlowBlock::getInRevIndex(), ghidra::FlowBlock::isBackEdgeIn(), ghidra::FlowBlock::isIrreducibleIn(), ghidra::FlowBlock::isMark(), ghidra::FlowBlock::isTreeEdgeIn(), ghidra::FlowBlock::numdesc, ghidra::FlowBlock::setMark(), ghidra::FlowBlock::setOutEdgeFlag(), ghidra::FlowBlock::sizeIn(), and ghidra::FlowBlock::visitcount.

◆ findSpanningTree()

void ghidra::BlockGraph::findSpanningTree	(	vector< FlowBlock *> &	preorder,
		vector< FlowBlock *> &	rootlist
	)

private

Find a spanning tree (skipping irreducible edges).

Label pre and reverse-post orderings, tree, forward, cross, and back edges.
Calculate number of descendants.
Put the blocks of the graph in reverse post order.
Return an array of all nodes in pre-order.
If the graph does not have a real root, create one and return it, otherwise return null.

Algorithm originally due to Tarjan. The first block is the entry block, and should remain the first block

Parameters

preorder	will hold the list of FlowBlock components in pre-order
rootlist	will hold the list of entry points

References ghidra::FlowBlock::copymap, ghidra::FlowBlock::getOut(), ghidra::FlowBlock::index, ghidra::FlowBlock::isIrreducibleOut(), ghidra::FlowBlock::numdesc, ghidra::FlowBlock::setOutEdgeFlag(), ghidra::FlowBlock::sizeIn(), ghidra::FlowBlock::sizeOut(), and ghidra::FlowBlock::visitcount.

◆ forceFalseEdge()

void ghidra::BlockGraph::forceFalseEdge ( const FlowBlock * out0 )

private

Force the false out edge to go to the given FlowBlock.

Make sure this has exactly 2 out edges and the first edge flows to the given FlowBlock. Swap the edges if necessary. Throw an exception if this is not possible.

Parameters

out0	is the given FlowBlock

References ghidra::FlowBlock::getParent(), and ghidra::BlockEdge::point.

◆ forceOutputNum()

void ghidra::BlockGraph::forceOutputNum ( int4 i )

private

Force number of outputs.

Force this FlowBlock to have the indicated number of outputs. Create edges back into itself if necessary.

Parameters

i	is the number of out edges to force

◆ getStartBlock()

FlowBlock * ghidra::BlockGraph::getStartBlock ( void ) const

Get the entry point FlowBlock.

Throw an exception if no entry point is registered

Returns: the entry point FlowBlock

◆ identifyInternal()

void ghidra::BlockGraph::identifyInternal	(	BlockGraph *	ident,
		const vector< FlowBlock *> &	nodes
	)

private

Move nodes from this into a new BlockGraph.

This does most of the work of collapsing a set of components in this into a single node. The components are removed from this, put in the new FlowBlock and adjusts edges. The new FlowBlock must be added back into this.

Parameters

ident	is the new FlowBlock
nodes	is the list component FlowBlocks to move

References addBlock(), and selfIdentify().

◆ markCopyBlock()

void ghidra::BlockGraph::markCopyBlock	(	FlowBlock *	bl,
		uint4	fl
	)

staticprotected

Set properties on the first leaf FlowBlock.

For the given BlockGraph find the first component leaf FlowBlock and set its properties

Parameters

bl	is the given BlockGraph
fl	is the property to set

References ghidra::FlowBlock::flags, and ghidra::FlowBlock::getFrontLeaf().

◆ markLabelBumpUp()

void ghidra::BlockGraph::markLabelBumpUp ( bool bump )

virtual

Let hierarchical blocks steal labels of their (first) components.

Parameters

bump	if true, mark that labels for this block are printed by somebody higher in hierarchy

Reimplemented from ghidra::FlowBlock.

Reimplemented in ghidra::BlockInfLoop, ghidra::BlockDoWhile, and ghidra::BlockWhileDo.

References ghidra::FlowBlock::markLabelBumpUp().

Referenced by ghidra::ActionFinalStructure::apply(), ghidra::BlockWhileDo::markLabelBumpUp(), ghidra::BlockDoWhile::markLabelBumpUp(), and ghidra::BlockInfLoop::markLabelBumpUp().

◆ moveOutEdge()

void ghidra::BlockGraph::moveOutEdge	(	FlowBlock *	blold,
		int4	slot,
		FlowBlock *	blnew
	)

Move indicated out edge to a new FlowBlock.

Given an edge specified by its input FlowBlock, replace that input with new FlowBlock.

Parameters

blold	is the original input FlowBlock
slot	is the index of the out edge of blold
blnew	is the FlowBlock that will become the input to the edge

References ghidra::FlowBlock::getOut(), ghidra::FlowBlock::getOutRevIndex(), ghidra::FlowBlock::parent, and ghidra::FlowBlock::replaceInEdge().

Referenced by ghidra::Funcdata::nodeJoinCreateBlock(), and ghidra::Funcdata::pushBranch().

◆ newBlock()

FlowBlock * ghidra::BlockGraph::newBlock ( void )

Build a new plain FlowBlock.

Add the new FlowBlock to this

Returns: the new FlowBlock

◆ newBlockBasic()

BlockBasic * ghidra::BlockGraph::newBlockBasic ( Funcdata * fd )

Build a new BlockBasic.

Add the new BlockBasic to this

Parameters

fd	is the function underlying the basic block

Returns: the new BlockBasic

Referenced by ghidra::FlowInfo::generateBlocks(), ghidra::Funcdata::nodeJoinCreateBlock(), ghidra::Funcdata::nodeSplitBlockEdge(), and ghidra::FlowInfo::splitBasic().

◆ newBlockCondition()

BlockCondition * ghidra::BlockGraph::newBlockCondition	(	FlowBlock *	b1,
		FlowBlock *	b2
	)

Build a new BlockCondition.

Add the new BlockCondition to this, collapsing its pieces into it.

Parameters

b1	is the first FlowBlock piece
b2	is the second FlowBlock piece

Returns: the new BlockCondition

References ghidra::CPUI_INT_AND, ghidra::CPUI_INT_OR, ghidra::FlowBlock::getFalseOut(), and ghidra::FlowBlock::getOut().

◆ newBlockCopy()

BlockCopy * ghidra::BlockGraph::newBlockCopy ( FlowBlock * bl )

Build a new BlockCopy.

Add the new BlockCopy to this

Parameters

bl	is the FlowBlock underlying the copy

Returns: the new BlockCopy

References ghidra::FlowBlock::flags, ghidra::FlowBlock::immed_dom, ghidra::FlowBlock::index, ghidra::FlowBlock::intothis, ghidra::FlowBlock::numdesc, and ghidra::FlowBlock::outofthis.

◆ newBlockDoWhile()

BlockDoWhile * ghidra::BlockGraph::newBlockDoWhile ( FlowBlock * condcl )

Build a new BlockDoWhile.

Add the new BlockDoWhile to this, collapsing the condition clause FlowBlock into it.

Parameters

condcl is the condition clause FlowBlock

Returns: the new BlockDoWhile

◆ newBlockGoto()

BlockGoto * ghidra::BlockGraph::newBlockGoto ( FlowBlock * bl )

Build a new BlockGoto.

Add the new BlockGoto to this, incorporating the given FlowBlock

Parameters

bl	is the given FlowBlock whose outgoing edge is to be marked as a goto

Returns: the new BlockGoto

References ghidra::FlowBlock::getOut().

◆ newBlockIf()

BlockIf * ghidra::BlockGraph::newBlockIf	(	FlowBlock *	cond,
		FlowBlock *	tc
	)

Build a new BlockIf.

Add the new BlockIf to this, collapsing the condition and body FlowBlocks into it.

Parameters

cond	is the condition FlowBlock
tc	is the body FlowBlock

Returns: the new BlockIf

◆ newBlockIfElse()

BlockIf * ghidra::BlockGraph::newBlockIfElse	(	FlowBlock *	cond,
		FlowBlock *	tc,
		FlowBlock *	fc
	)

Build a new BlockIfElse.

Add the new BlockIfElse to this, collapsing the condition, true clause, and false clause into it.

Parameters

cond	is the condition FlowBlock
tc	is the true clause FlowBlock
fc	is the false clause FlowBlock

Returns: the new BlockIf

◆ newBlockIfGoto()

BlockIf * ghidra::BlockGraph::newBlockIfGoto ( FlowBlock * cond )

Build a new BlockIfGoto.

Add the new BlockIfGoto to this, collapsing the given condition FlowBlock into it.

Parameters

cond	is the given condition FlowBlock

Returns: the new BlockIfGoto

References ghidra::FlowBlock::getOut(), ghidra::FlowBlock::getTrueOut(), ghidra::FlowBlock::isGotoOut(), and ghidra::BlockIf::setGotoTarget().

◆ newBlockInfLoop()

BlockInfLoop * ghidra::BlockGraph::newBlockInfLoop ( FlowBlock * body )

Build a new BlockInfLoop.

Add the new BlockInfLoop to this, collapsing the body FlowBlock into it.

Parameters

body	is the body FlowBlock

Returns: the new BlockInfLoop

◆ newBlockList()

BlockList * ghidra::BlockGraph::newBlockList ( const vector< FlowBlock *> & nodes )

Build a new BlockList.

Add the new BlockList to this, collapsing the given FlowBlock components into it.

Parameters

nodes is the given set of FlowBlocks components

Returns: the new BlockList

References ghidra::FlowBlock::sizeOut().

◆ newBlockMultiGoto()

BlockMultiGoto * ghidra::BlockGraph::newBlockMultiGoto	(	FlowBlock *	bl,
		int4	outedge
	)

Build a new BlockMultiGoto.

The given FlowBlock may already be a BlockMultiGoto, otherwise we add the new BlockMultiGoto to this.

Parameters

bl	is the given FlowBlock with the new goto edge
outedge	is the index of the outgoing edge to make into a goto

Returns: the (possibly new) BlockMultiGoto

References ghidra::BlockMultiGoto::addEdge(), ghidra::FlowBlock::getOut(), ghidra::FlowBlock::getType(), ghidra::FlowBlock::isDefaultBranch(), and ghidra::BlockMultiGoto::setDefaultGoto().

◆ newBlockSwitch()

BlockSwitch * ghidra::BlockGraph::newBlockSwitch	(	const vector< FlowBlock *> &	cs,
		bool	hasExit
	)

Build a new BlockSwitch.

Add the new BlockSwitch to this, collapsing all the case FlowBlocks into it.

Parameters

cs	is the list of case FlowBlocks
hasExit	is true if the switch has a formal exit

Returns: the new BlockSwitch

References ghidra::FlowBlock::clearFlag(), ghidra::FlowBlock::getExitLeaf(), ghidra::FlowBlock::getType(), ghidra::BlockSwitch::grabCaseBasic(), and ghidra::FlowBlock::subBlock().

◆ newBlockWhileDo()

BlockWhileDo * ghidra::BlockGraph::newBlockWhileDo	(	FlowBlock *	cond,
		FlowBlock *	cl
	)

Build a new BlockWhileDo.

Add the new BlockWhileDo to this, collapsing the condition and clause into it.

Parameters

cond	is the condition FlowBlock
cl	is the clause FlowBlock

Returns: the new BlockWhileDo

Referenced by ghidra::CollapseStructure::ruleBlockWhileDo().

◆ nextFlowAfter()

FlowBlock * ghidra::BlockGraph::nextFlowAfter ( const FlowBlock * bl ) const

virtual

Get the leaf FlowBlock that will execute after the given FlowBlock.

Within the hierarchy of this FlowBlock, assume the given FlowBlock will fall-thru in its execution at some point. Return the first leaf block (BlockBasic or BlockCopy) that will execute after the given FlowBlock completes, assuming this is a unique block.

Parameters

bl	is the given FlowBlock

Returns: the next FlowBlock to execute or NULL

Reimplemented from ghidra::FlowBlock.

Reimplemented in ghidra::BlockSwitch, ghidra::BlockInfLoop, ghidra::BlockDoWhile, ghidra::BlockWhileDo, ghidra::BlockIf, ghidra::BlockCondition, ghidra::BlockMultiGoto, and ghidra::BlockGoto.

References ghidra::FlowBlock::getFrontLeaf().

◆ orderBlocks()

void ghidra::BlockGraph::orderBlocks ( void )

inline

< Sort blocks using the final ordering

Referenced by ghidra::ActionFinalStructure::apply(), and ghidra::StructureGraph::rawAction().

◆ printTree()

void ghidra::BlockGraph::printTree	(	ostream &	s,
		int4	level
	)		const

virtual

Print tree structure of any blocks owned by this.

Recursively print out the hierarchical structure of this FlowBlock.

Parameters

s	is the output stream
level	is the current level of indentation

Reimplemented from ghidra::FlowBlock.

References ghidra::FlowBlock::printTree().

Referenced by ghidra::Funcdata::printBlockTree().

◆ removeBlock()

void ghidra::BlockGraph::removeBlock ( FlowBlock * bl )

Remove a FlowBlock from this BlockGraph.

The indicated block is pulled out of the component list and deleted. Any edges between it and the rest of the BlockGraph are simply removed.

Parameters

bl	is the indicated block

References ghidra::FlowBlock::getIn(), ghidra::FlowBlock::getOut(), ghidra::FlowBlock::parent, ghidra::FlowBlock::sizeIn(), and ghidra::FlowBlock::sizeOut().

Referenced by ghidra::Funcdata::blockRemoveInternal(), and ghidra::Funcdata::removeFromFlowSplit().

◆ removeEdge()

void ghidra::BlockGraph::removeEdge	(	FlowBlock *	begin,
		FlowBlock *	end
	)

Remove an edge between component FlowBlocks.

The edge must already exist

Parameters

begin	is the incoming FlowBlock of the edge
end	is the outgoing FlowBlock

References ghidra::FlowBlock::intothis, ghidra::FlowBlock::parent, and ghidra::FlowBlock::removeInEdge().

Referenced by ghidra::Funcdata::branchRemoveInternal(), and ghidra::Funcdata::nodeJoinCreateBlock().

◆ removeFromFlow()

void ghidra::BlockGraph::removeFromFlow ( FlowBlock * bl )

Remove given FlowBlock preserving flow in this.

This should be applied only if the given FlowBlock has 0 or 1 outputs. If there is an output FlowBlock, all incoming edges to the given FlowBlock are moved so they flow into the output FlowBlock, then all remaining edges into or out of the given FlowBlock are removed. The given FlowBlock is not removed from this. This routine doesn't preserve loopedge information

Parameters

bl	is the given FlowBlock component

References ghidra::FlowBlock::getIn(), ghidra::FlowBlock::getOut(), ghidra::FlowBlock::intothis, ghidra::FlowBlock::parent, ghidra::FlowBlock::removeOutEdge(), ghidra::FlowBlock::replaceOutEdge(), ghidra::FlowBlock::sizeIn(), and ghidra::FlowBlock::sizeOut().

Referenced by ghidra::Funcdata::blockRemoveInternal().

◆ removeFromFlowSplit()

void ghidra::BlockGraph::removeFromFlowSplit	(	FlowBlock *	bl,
		bool	flipflow
	)

Remove FlowBlock splitting flow between input and output edges.

Remove the given FlowBlock from the flow of the graph. It must have 2 inputs, and 2 outputs. The edges will be remapped so that

In(0) -> Out(0) and
In(1) -> Out(1)

Or if flipflow is true:

In(0) -> Out(1)
In(1) -> Out(0)
Parameters

bl is the given FlowBlock

flipflow indicates how the edges are remapped

References ghidra::FlowBlock::parent, ghidra::FlowBlock::replaceEdgesThru(), ghidra::FlowBlock::sizeIn(), and ghidra::FlowBlock::sizeOut().

Referenced by ghidra::Funcdata::removeFromFlowSplit().

◆ selfIdentify()

void ghidra::BlockGraph::selfIdentify ( void )

private

Inherit our edges from the edges of our components.

Examine the set of components and their incoming and outgoing edges. If both ends of the edge are not within the set, then this block inherits the edge. A formal BlockEdge is added between this and the FlowBlock outside the set. The edges are deduplicated.

References ghidra::FlowBlock::intothis, ghidra::FlowBlock::isSwitchOut(), ghidra::FlowBlock::outofthis, ghidra::FlowBlock::parent, ghidra::FlowBlock::replaceInEdge(), and ghidra::FlowBlock::replaceOutEdge().

Referenced by identifyInternal().

◆ setStartBlock()

void ghidra::BlockGraph::setStartBlock ( FlowBlock * bl )

Set the entry point FlowBlock for this graph.

The component list is reordered to make the given FlowBlock first. The f_entry_point property is updated.

Parameters

bl	is the given FlowBlock to make the entry point

References ghidra::FlowBlock::flags, and ghidra::FlowBlock::parent.

Referenced by ghidra::FlowInfo::generateBlocks(), and ghidra::FlowInfo::splitBasic().

◆ spliceBlock()

void ghidra::BlockGraph::spliceBlock ( FlowBlock * bl )

Splice given FlowBlock together with its output.

The given FlowBlock must have exactly one output. That output must have exactly one input. The output FlowBlock is removed and any outgoing edges it has become outgoing edge of the given FlowBlock. The output FlowBlock is permanently removed. It is viewed as being spliced together with the given FlowBlock.

Parameters

bl	is the given FlowBlock

References ghidra::FlowBlock::flags, ghidra::FlowBlock::getOut(), ghidra::FlowBlock::removeOutEdge(), ghidra::FlowBlock::sizeIn(), and ghidra::FlowBlock::sizeOut().

Referenced by ghidra::Funcdata::spliceBlockBasic().

◆ structureLoops()

void ghidra::BlockGraph::structureLoops ( vector< FlowBlock *> & rootlist )

Label loop edges.

Find irreducible edges
Find a spanning tree
Set FlowBlock indices in reverse-post order
Label tree-edges, forward-edges, cross-edges, and back-edges
Parameters

rootlist will contain the entry points for the graph

References ghidra::FlowBlock::getIn(), ghidra::FlowBlock::getOut(), ghidra::FlowBlock::sizeIn(), and ghidra::FlowBlock::sizeOut().

Referenced by ghidra::IfcStructureBlocks::execute(), ghidra::StructureGraph::rawAction(), and ghidra::Funcdata::structureReset().

◆ swapBlocks()

void ghidra::BlockGraph::swapBlocks	(	int4	i,
		int4	j
	)

protected

Swap the positions two component FlowBlocks.

Parameters

i	is the position of the first FlowBlock to swap
j	is the position of the second

◆ switchEdge()

void ghidra::BlockGraph::switchEdge	(	FlowBlock *	in,
		FlowBlock *	outbefore,
		FlowBlock *	outafter
	)

Move an edge from one out FlowBlock to another.

The edge from in to outbefore must already exist. It will get removed and replaced with an edge from in to outafter. The new edge index will be the same as the removed edge, and all other edge ordering will be preserved.

Parameters

in	is the input FlowBlock
outbefore	is the initial output FlowBlock
outafter	is the new output FlowBlock

References ghidra::FlowBlock::outofthis, and ghidra::FlowBlock::replaceOutEdge().

Referenced by ghidra::Funcdata::nodeSplitBlockEdge(), and ghidra::Funcdata::switchEdge().

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

block.hh
block.cc

bl	is the given FlowBlock
flipflow	indicates how the edges are remapped

Public Member Functions

Protected Member Functions

Static Protected Member Functions

Private Member Functions

Static Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Member Function Documentation

◆ addBlock()

◆ addEdge()

◆ addLoopEdge()

◆ buildCopy()

◆ buildDomDepth()

◆ buildDomSubTree()

◆ buildDomTree()

◆ calcForwardDominator()

◆ calcLoop()

◆ clearEdgeFlags()

◆ collectReachable()

◆ createVirtualRoot()

◆ decode()

◆ decodeBody()

◆ emit()

◆ findIrreducible()

◆ findSpanningTree()

◆ forceFalseEdge()

◆ forceOutputNum()

◆ getStartBlock()

◆ identifyInternal()

◆ markCopyBlock()

◆ markLabelBumpUp()

◆ moveOutEdge()

◆ newBlock()

◆ newBlockBasic()

◆ newBlockCondition()

◆ newBlockCopy()

◆ newBlockDoWhile()

◆ newBlockGoto()

◆ newBlockIf()

◆ newBlockIfElse()

◆ newBlockIfGoto()

◆ newBlockInfLoop()

◆ newBlockList()

◆ newBlockMultiGoto()

◆ newBlockSwitch()

◆ newBlockWhileDo()

◆ nextFlowAfter()

◆ orderBlocks()

◆ printTree()

◆ removeBlock()

◆ removeEdge()

◆ removeFromFlow()

◆ removeFromFlowSplit()

◆ selfIdentify()

◆ setStartBlock()

◆ spliceBlock()

◆ structureLoops()

◆ swapBlocks()

◆ switchEdge()