A class for simplifying a series of conditionally executed statements. More...

#include <condexe.hh>

Public Member Functions
	ConditionalExecution (Funcdata *f)
	Constructor.

bool	trial (BlockBasic *ib)
	Test for a modifiable configuration around the given block.

void	execute (void)
	Eliminate the unnecessary path join at iblock.

Private Member Functions
void	buildHeritageArray (void)
	Calculate boolean array of all address spaces that have had a heritage pass run.

bool	testIBlock (void)
	Test the most basic requirements on iblock.

bool	findInitPre (void)
	Find initblock, based on iblock.

bool	verifySameCondition (void)
	Verify that initblock and iblock branch on the same condition.

bool	testOpRead (Varnode vn, PcodeOp op)
	Can we move the (non MULTIEQUAL) defining p-code of the given Varnode.

bool	testMultiRead (Varnode vn, PcodeOp op)
	Can we move the MULTIEQUAL defining p-code of the given Varnode.

bool	testRemovability (PcodeOp *op)
	Test if the given PcodeOp can be removed from iblock.

Varnode *	findPullback (int4 inbranch)
	Find previously constructed pull-back op.

Varnode *	pullbackOp (PcodeOp *op, int4 inbranch)
	Pull-back PcodeOp out of the iblock.

Varnode *	getNewMulti (PcodeOp op, BlockBasic bl)
	Create a MULTIEQUAL in the given block that will hold data-flow from the given PcodeOp.

Varnode *	resolveRead (PcodeOp op, BlockBasic bl)
	Resolve a read op coming through an arbitrary block.

Varnode *	resolveIblockRead (PcodeOp *op, int4 inbranch)
	Resolve a read op coming through the iblock.

Varnode *	getMultiequalRead (PcodeOp op, PcodeOp readop, int4 slot)
	Get the replacement Varnode for the output of a MULTIEQUAL in the iblock, given the op reading it.

Varnode *	getReplacementRead (PcodeOp op, BlockBasic bl)
	Find a replacement Varnode for the output of the given PcodeOp that is read in the given block.

void	doReplacement (PcodeOp *op)
	Replace the data-flow for the given PcodeOp in iblock.

bool	verify (void)
	Verify that we have a removable iblock.

Private Attributes
Funcdata *	fd
	Function being analyzed.

PcodeOp *	cbranch
	CBRANCH in iblock.

BlockBasic *	initblock
	The initial block computing the boolean value.

BlockBasic *	iblock
	The block where flow is (unnecessarily) coming together.

int4	prea_inslot
	iblock->In(prea_inslot) = pre a path

bool	init2a_true
	Does true branch (in terms of iblock) go to path pre a.

bool	iblock2posta_true
	Does true branch go to path post a.

int4	camethruposta_slot
	init or pre slot to use, for data-flow thru post

int4	posta_outslot
	The out edge from iblock to posta.

BlockBasic *	posta_block
	First block in posta path.

BlockBasic *	postb_block
	First block in postb path.

map< int4, Varnode * >	replacement
	Map from block to replacement Varnode for (current) Varnode.

vector< Varnode * >	pullback
	Outputs of ops that have been pulled back from iblock for (current) Varnode.

vector< bool >	heritageyes
	Boolean array indexed by address space indicating whether the space is heritaged.

Detailed Description

A class for simplifying a series of conditionally executed statements.

This class tries to perform transformations like the following:

if (a) {           if (a) {
   BODY1
}          ==>       BODY1
if (a) {             BODY2
   BODY2
}                  }

Other similar configurations where two CBRANCHs are based on the same condition are handled. The main variation, referred to as a directsplit in the code looks like:

if (a) {                      if (a && new_boolean()) {
   a = new_boolean();
}                      ==>      BODY1
if (a) {
   BODY1
}                             }

The value of 'a' doesn't need to be reevaluated if it is false.

In the first scenario, there is a block where two flows come together but don't need to, as the evaluation of the boolean is redundant. This block is the iblock. The original evaluation of the boolean occurs in initblock. There are two paths from here to iblock, called the prea path and preb path, either of which may contain additional 1in/1out blocks. There are also two paths out of iblock, posta, and postb. The ConditionalExecution class determines if the CBRANCH in iblock is redundant by determining if the boolean value is either the same as, or the complement of, the boolean value in initblock. If the CBRANCH is redundant, iblock is removed, linking prea to posta and preb to postb (or vice versa depending on whether the booleans are complements of each other). If iblock is to be removed, modifications to data-flow made by iblock must be preserved. For MULTIEQUALs in iblock, reads are examined to see if they came from the posta path, or the postb path, then the are replaced by the MULTIEQUAL slot corresponding to the matching prea or preb branch. If posta and postb merge at an exitblock, the MULTIEQUAL must be pushed into the exitblock and reads which can't be attributed to the posta or postb path are replaced by the exitblock MULTIEQUAL.

In theory, other operations performed in iblock could be pushed into exitblock if they are not read in the posta or postb paths, but currently non MULTIEQUAL operations in iblock terminate the action.

In the second scenario, the boolean evaluated in initblock remains unmodified along only one of the two paths out, prea or reb. The boolean in iblock (modulo complementing) will evaluate in the same way. We define posta as the path out of iblock that will be followed by this unmodified path. The transform that needs to be made is to have the unmodified path out of initblock flow immediately into the posta path without having to reevalute the condition in iblock. iblock is not removed because flow from the "modified" path may also flow into posta, depending on how the boolean was modified. Adjustments to data-flow are similar to the first scenario but slightly more complicated. The first block along the posta path is referred to as the posta_block, this block will have a new block flowing into it.

Constructor & Destructor Documentation

◆ ConditionalExecution()

ghidra::ConditionalExecution::ConditionalExecution ( Funcdata * f )

Constructor.

Set up for testing ConditionalExecution on multiple iblocks

Parameters

f	is the function to do testing on

References buildHeritageArray(), and fd.

Member Function Documentation

◆ buildHeritageArray()

void ghidra::ConditionalExecution::buildHeritageArray ( void )

private

Calculate boolean array of all address spaces that have had a heritage pass run.

Used to test if all the links out of the iblock have been calculated.

References fd, ghidra::Funcdata::getArch(), ghidra::AddrSpace::getIndex(), ghidra::AddrSpaceManager::getSpace(), heritageyes, ghidra::AddrSpace::isHeritaged(), ghidra::Funcdata::numHeritagePasses(), and ghidra::AddrSpaceManager::numSpaces().

Referenced by ConditionalExecution().

◆ doReplacement()

void ghidra::ConditionalExecution::doReplacement ( PcodeOp * op )

private

Replace the data-flow for the given PcodeOp in iblock.

The data-flow for the given op is reproduced in the new control-flow configuration. After completion of this method, the op can be removed.

Parameters

op	is the given PcodeOp

References ghidra::Varnode::beginDescend(), ghidra::PcodeOp::code(), ghidra::CPUI_COPY, ghidra::CPUI_MULTIEQUAL, ghidra::CPUI_RETURN, ghidra::Varnode::endDescend(), fd, ghidra::PcodeOp::getAddr(), ghidra::Varnode::getAddr(), ghidra::PcodeOp::getIn(), getMultiequalRead(), ghidra::PcodeOp::getOut(), ghidra::PcodeOp::getParent(), getReplacementRead(), ghidra::Varnode::getSize(), ghidra::PcodeOp::getSlot(), iblock, ghidra::Funcdata::newOp(), ghidra::Funcdata::newVarnodeOut(), ghidra::Funcdata::opInsertBefore(), ghidra::Funcdata::opSetInput(), ghidra::Funcdata::opSetOpcode(), ghidra::Funcdata::opUnsetInput(), pullback, and replacement.

Referenced by execute().

◆ execute()

void ghidra::ConditionalExecution::execute ( void )

Eliminate the unnecessary path join at iblock.

We assume the last call to verify() returned true.

References ghidra::BlockBasic::beginOp(), camethruposta_slot, doReplacement(), ghidra::BlockBasic::endOp(), fd, iblock, ghidra::PcodeOp::isBranch(), ghidra::Funcdata::opDestroy(), posta_outslot, and ghidra::Funcdata::removeFromFlowSplit().

Referenced by ghidra::ActionConditionalExe::apply().

◆ findInitPre()

bool ghidra::ConditionalExecution::findInitPre ( void )

private

Find initblock, based on iblock.

Returns: true if configuration between initblock and iblock is correct

References ghidra::FlowBlock::getIn(), ghidra::FlowBlock::getTrueOut(), iblock, init2a_true, initblock, prea_inslot, ghidra::FlowBlock::sizeIn(), and ghidra::FlowBlock::sizeOut().

Referenced by verify().

◆ findPullback()

Varnode * ghidra::ConditionalExecution::findPullback ( int4 inbranch )

private

Find previously constructed pull-back op.

Parameters

inbranch is the iblock incoming branch to pullback through

Returns: the output of the previous pullback op, or null

References pullback.

Referenced by pullbackOp().

◆ getMultiequalRead()

Varnode * ghidra::ConditionalExecution::getMultiequalRead	(	PcodeOp *	op,
		PcodeOp *	readop,
		int4	slot
	)

private

Get the replacement Varnode for the output of a MULTIEQUAL in the iblock, given the op reading it.

Parameters

op	is the MULTIEQUAL from iblock
readop	is the PcodeOp reading the output Varnode
slot	is the input slot being read

Returns: the Varnode to use as a replacement

References camethruposta_slot, ghidra::FlowBlock::getIn(), ghidra::FlowBlock::getInRevIndex(), ghidra::PcodeOp::getParent(), getReplacementRead(), iblock, posta_outslot, and resolveIblockRead().

Referenced by doReplacement().

◆ getNewMulti()

Varnode * ghidra::ConditionalExecution::getNewMulti	(	PcodeOp *	op,
		BlockBasic *	bl
	)

private

Create a MULTIEQUAL in the given block that will hold data-flow from the given PcodeOp.

A new MULTIEQUAL is created whose inputs are the output of the given PcodeOp

Parameters

op	is the PcodeOp whose output will get held
bl	is the block that will contain the new MULTIEQUAL

Returns: the output Varnode of the new MULTIEQUAL

References ghidra::CPUI_MULTIEQUAL, fd, ghidra::PcodeOp::getOut(), ghidra::Varnode::getSize(), ghidra::BlockBasic::getStart(), ghidra::Funcdata::newOp(), ghidra::Funcdata::newUniqueOut(), ghidra::Funcdata::opInsertBegin(), ghidra::Funcdata::opSetInput(), ghidra::Funcdata::opSetOpcode(), and ghidra::FlowBlock::sizeIn().

Referenced by resolveRead().

◆ getReplacementRead()

Varnode * ghidra::ConditionalExecution::getReplacementRead	(	PcodeOp *	op,
		BlockBasic *	bl
	)

private

Find a replacement Varnode for the output of the given PcodeOp that is read in the given block.

The replacement Varnode must be valid for everything below (dominated) by the block. If we can't find a replacement, create one (as a MULTIEQUAL) in the given block (creating recursion through input blocks). Any new Varnode created is cached in the replacement array so it can get picked up by other calls to this function for different blocks.

Parameters

op	is the given PcodeOp whose output we must replace
bl	is the given basic block (containing a read of the Varnode)

Returns: the replacement Varnode

References ghidra::FlowBlock::getImmedDom(), ghidra::FlowBlock::getIndex(), iblock, replacement, and resolveRead().

Referenced by doReplacement(), and getMultiequalRead().

◆ pullbackOp()

Varnode * ghidra::ConditionalExecution::pullbackOp	(	PcodeOp *	op,
		int4	inbranch
	)

private

Pull-back PcodeOp out of the iblock.

Create a duplicate PcodeOp outside the iblock. The first input to the PcodeOp can be defined by a MULTIEQUAL in the iblock, in which case the duplicate's input will be selected from the MULTIEQUAL input. Any other inputs must be constants.

Parameters

op	is the PcodeOp in the iblock being replaced
inbranch	is the direction to pullback from

Returns: the output Varnode of the new op

References ghidra::PcodeOp::code(), fd, findPullback(), ghidra::PcodeOp::getAddr(), ghidra::Varnode::getAddr(), ghidra::Varnode::getDef(), ghidra::FlowBlock::getImmedDom(), ghidra::FlowBlock::getIn(), ghidra::PcodeOp::getIn(), ghidra::PcodeOp::getOut(), ghidra::PcodeOp::getParent(), ghidra::Varnode::getSize(), iblock, ghidra::Varnode::isWritten(), ghidra::Funcdata::newOp(), ghidra::Funcdata::newVarnodeOut(), ghidra::PcodeOp::numInput(), ghidra::Funcdata::opInsertEnd(), ghidra::Funcdata::opSetInput(), ghidra::Funcdata::opSetOpcode(), and pullback.

Referenced by resolveIblockRead().

◆ resolveIblockRead()

Varnode * ghidra::ConditionalExecution::resolveIblockRead	(	PcodeOp *	op,
		int4	inbranch
	)

private

Resolve a read op coming through the iblock.

Parameters

op	is the iblock op whose output is being read
inbranch	is the known direction of the reading op

Returns: the replacement Varnode to use for the read

References ghidra::PcodeOp::code(), ghidra::CPUI_COPY, ghidra::CPUI_INT_ADD, ghidra::CPUI_MULTIEQUAL, ghidra::CPUI_PTRSUB, ghidra::CPUI_SUBPIECE, ghidra::Varnode::getDef(), ghidra::PcodeOp::getIn(), ghidra::PcodeOp::getParent(), iblock, ghidra::Varnode::isWritten(), and pullbackOp().

Referenced by getMultiequalRead(), and resolveRead().

◆ resolveRead()

Varnode * ghidra::ConditionalExecution::resolveRead	(	PcodeOp *	op,
		BlockBasic *	bl
	)

private

Resolve a read op coming through an arbitrary block.

Given an op in the iblock and the basic block of another op that reads the output Varnode, calculate the replacement Varnode for the read.

Parameters

op	is the given op in the iblock
bl	is the basic block of the read

Returns: the replacement Varnode

References camethruposta_slot, ghidra::FlowBlock::getInRevIndex(), getNewMulti(), posta_outslot, resolveIblockRead(), and ghidra::FlowBlock::sizeIn().

Referenced by getReplacementRead().

◆ testIBlock()

bool ghidra::ConditionalExecution::testIBlock ( void )

private

Test the most basic requirements on iblock.

The block must have 2 in edges and 2 out edges and a final CBRANCH op.

Returns: true if iblock matches basic requirements

References cbranch, ghidra::PcodeOp::code(), ghidra::CPUI_CBRANCH, iblock, ghidra::BlockBasic::lastOp(), ghidra::FlowBlock::sizeIn(), and ghidra::FlowBlock::sizeOut().

Referenced by verify().

◆ testMultiRead()

bool ghidra::ConditionalExecution::testMultiRead	(	Varnode *	vn,
		PcodeOp *	op
	)

private

Can we move the MULTIEQUAL defining p-code of the given Varnode.

The given Varnode is defined by a MULTIEQUAL in iblock which must be removed. Test if this is possible/advisable given a specific p-code op that reads the Varnode

Parameters

vn	is the given Varnode
op	is the given PcodeOp reading the Varnode

Returns: false if it is not possible to move the defining op (because of the given op)

References ghidra::PcodeOp::code(), ghidra::CPUI_COPY, ghidra::CPUI_RETURN, ghidra::CPUI_SUBPIECE, ghidra::PcodeOp::getIn(), ghidra::PcodeOp::getParent(), iblock, and ghidra::PcodeOp::numInput().

Referenced by testRemovability().

◆ testOpRead()

bool ghidra::ConditionalExecution::testOpRead	(	Varnode *	vn,
		PcodeOp *	op
	)

private

Can we move the (non MULTIEQUAL) defining p-code of the given Varnode.

The given Varnode is defined by an operation in iblock which must be removed. Test if this is possible/advisable given a specific p-code op that reads the Varnode

Parameters

vn	is the given Varnode
op	is the given PcodeOp reading the Varnode

Returns: false if it is not possible to move the defining op (because of the given op)

References ghidra::PcodeOp::code(), ghidra::CPUI_COPY, ghidra::CPUI_INT_ADD, ghidra::CPUI_MULTIEQUAL, ghidra::CPUI_PTRSUB, ghidra::CPUI_SUBPIECE, ghidra::Varnode::getDef(), ghidra::PcodeOp::getIn(), ghidra::PcodeOp::getParent(), iblock, ghidra::Varnode::isConstant(), ghidra::Varnode::isFree(), and ghidra::Varnode::isWritten().

Referenced by testRemovability().

◆ testRemovability()

bool ghidra::ConditionalExecution::testRemovability ( PcodeOp * op )

private

Test if the given PcodeOp can be removed from iblock.

Parameters

op	is the PcodeOp within iblock to test

Returns: true if it is removable

References ghidra::Varnode::beginDescend(), ghidra::PcodeOp::code(), ghidra::CPUI_INDIRECT, ghidra::CPUI_LOAD, ghidra::CPUI_MULTIEQUAL, ghidra::CPUI_STORE, ghidra::Varnode::endDescend(), ghidra::AddrSpace::getIndex(), ghidra::PcodeOp::getOut(), ghidra::Varnode::getSpace(), heritageyes, ghidra::Varnode::isAddrTied(), ghidra::PcodeOp::isCall(), ghidra::PcodeOp::isFlowBreak(), testMultiRead(), and testOpRead().

Referenced by verify().

◆ trial()

bool ghidra::ConditionalExecution::trial ( BlockBasic * ib )

Test for a modifiable configuration around the given block.

The given block is tested as a possible iblock. If this configuration works and is not a directsplit, true is returned. If the configuration works as a directsplit, then recursively check that its posta_block works as an iblock. If it does work, keep this iblock, otherwise revert to the directsplit configuration. In either case return true. Processing the directsplit first may prevent posta_block from being an iblock.

Parameters

ib	is the trial iblock

Returns: true if (some) configuration is recognized and can be modified

References iblock, and verify().

Referenced by ghidra::ActionConditionalExe::apply().

◆ verify()

bool ghidra::ConditionalExecution::verify ( void )

private

Verify that we have a removable iblock.

The iblock has been fixed. Test all control-flow conditions, and test removability of all ops in the iblock.

Returns: true if the configuration can be modified

References ghidra::BlockBasic::beginOp(), camethruposta_slot, ghidra::BlockBasic::endOp(), findInitPre(), ghidra::FlowBlock::getOut(), iblock, iblock2posta_true, init2a_true, posta_block, posta_outslot, postb_block, prea_inslot, testIBlock(), testRemovability(), and verifySameCondition().

Referenced by trial().

◆ verifySameCondition()

bool ghidra::ConditionalExecution::verifySameCondition ( void )

private

Verify that initblock and iblock branch on the same condition.

The conditions must always have the same value or always have complementary values.

Returns: true if the conditions are correlated

References cbranch, ghidra::PcodeOp::code(), ghidra::CPUI_CBRANCH, ghidra::BooleanExpressionMatch::getFlip(), init2a_true, initblock, ghidra::BlockBasic::lastOp(), and ghidra::BooleanExpressionMatch::verifyCondition().

Referenced by verify().

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

condexe.hh
condexe.cc

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ ConditionalExecution()

Member Function Documentation

◆ buildHeritageArray()

◆ doReplacement()

◆ execute()

◆ findInitPre()

◆ findPullback()

◆ getMultiequalRead()

◆ getNewMulti()

◆ getReplacementRead()

◆ pullbackOp()

◆ resolveIblockRead()

◆ resolveRead()

◆ testIBlock()

◆ testMultiRead()

◆ testOpRead()

◆ testRemovability()

◆ trial()

◆ verify()

◆ verifySameCondition()