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

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

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

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

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

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

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

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

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

void	predefineDirectMulti (PcodeOp *op)
	Prebuild a replacement MULTIEQUAL for output Varnode of the given PcodeOp in posta_block. More...

void	adjustDirectMulti (void)
	Update inputs to any MULTIEQUAL in the direct block. More...

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

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

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

void	fixReturnOp (void)
	Reproduce COPY data-flow into RETURN ops affected by the removal of iblock.

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

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.

bool	directsplit
	True if this the direct split variation.

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

vector< PcodeOp * >	returnop
	RETURN ops that have flow coming out of the iblock.

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.

Member Function Documentation

◆ adjustDirectMulti()

void ConditionalExecution::adjustDirectMulti ( void )

private

Update inputs to any MULTIEQUAL in the direct block.

In the direct split case, MULTIEQUALs in the body block (posta_block) must update their flow to account for iblock being removed and a new block flowing into the body block.

References BlockBasic::beginOp(), camethruposta_slot, PcodeOp::code(), CPUI_MULTIEQUAL, BlockBasic::endOp(), fd, Varnode::getDef(), PcodeOp::getIn(), FlowBlock::getOutRevIndex(), PcodeOp::getParent(), iblock, Varnode::isWritten(), PcodeOp::numInput(), Funcdata::opInsertInput(), Funcdata::opSetInput(), posta_block, and posta_outslot.

Referenced by execute().

◆ buildHeritageArray()

void 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, Funcdata::getArch(), AddrSpace::getIndex(), AddrSpaceManager::getSpace(), heritageyes, AddrSpace::isHeritaged(), Funcdata::numHeritagePasses(), and AddrSpaceManager::numSpaces().

Referenced by trial().

◆ doReplacement()

void 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 Varnode::beginDescend(), camethruposta_slot, PcodeOp::code(), CPUI_COPY, CPUI_MULTIEQUAL, directsplit, Varnode::endDescend(), fd, PcodeOp::getIn(), FlowBlock::getIn(), FlowBlock::getInRevIndex(), PcodeOp::getOut(), PcodeOp::getParent(), getReplacementRead(), PcodeOp::getSlot(), Varnode::hasNoDescend(), iblock, Funcdata::opSetInput(), Funcdata::opUnsetInput(), posta_outslot, predefineDirectMulti(), and replacement.

Referenced by execute().

◆ execute()

void ConditionalExecution::execute ( void )

Eliminate the unnecessary path join at iblock.

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

References adjustDirectMulti(), BlockBasic::beginOp(), camethruposta_slot, PcodeOp::code(), CPUI_MULTIEQUAL, directsplit, doReplacement(), BlockBasic::endOp(), fd, fixReturnOp(), FlowBlock::getIn(), iblock, PcodeOp::isBranch(), Funcdata::opDestroy(), posta_block, posta_outslot, Funcdata::removeFromFlowSplit(), and Funcdata::switchEdge().

Referenced by ActionConditionalExe::apply().

◆ findInitPre()

bool ConditionalExecution::findInitPre ( void )

private

Find initblock, based on iblock.

Returns: true if configuration between initblock and iblock is correct

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

Referenced by verify().

◆ getNewMulti()

Varnode * 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 CPUI_MULTIEQUAL, fd, PcodeOp::getOut(), Varnode::getSize(), BlockBasic::getStart(), Funcdata::newOp(), Funcdata::newUniqueOut(), Funcdata::opInsertBegin(), Funcdata::opSetInput(), Funcdata::opSetOpcode(), and FlowBlock::sizeIn().

Referenced by getReplacementRead().

◆ getReplacementRead()

Varnode * 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 camethruposta_slot, FlowBlock::getImmedDom(), PcodeOp::getIn(), FlowBlock::getIndex(), getNewMulti(), iblock, posta_outslot, and replacement.

Referenced by doReplacement().

◆ predefineDirectMulti()

void ConditionalExecution::predefineDirectMulti ( PcodeOp * op )

private

Prebuild a replacement MULTIEQUAL for output Varnode of the given PcodeOp in posta_block.

The new op will hold the same data-flow as the original Varnode once a new edge into posta_block is created.

Parameters

op	is the given PcodeOp

References camethruposta_slot, CPUI_MULTIEQUAL, fd, Varnode::getAddr(), PcodeOp::getIn(), FlowBlock::getIndex(), PcodeOp::getOut(), FlowBlock::getOutRevIndex(), Varnode::getSize(), BlockBasic::getStart(), iblock, Funcdata::newOp(), Funcdata::newVarnodeOut(), Funcdata::opInsertBegin(), Funcdata::opSetInput(), Funcdata::opSetOpcode(), posta_block, posta_outslot, replacement, and FlowBlock::sizeIn().

Referenced by doReplacement().

◆ testIBlock()

bool 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, PcodeOp::code(), CPUI_CBRANCH, iblock, BlockBasic::lastOp(), FlowBlock::sizeIn(), and FlowBlock::sizeOut().

Referenced by verify().

◆ testMultiRead()

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

private

Can we mave 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 PcodeOp::code(), CPUI_COPY, CPUI_RETURN, directsplit, PcodeOp::getIn(), PcodeOp::getParent(), iblock, PcodeOp::numInput(), and returnop.

Referenced by testRemovability().

◆ testOpRead()

bool 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 PcodeOp::code(), CPUI_COPY, CPUI_MULTIEQUAL, CPUI_RETURN, directsplit, Varnode::getDef(), PcodeOp::getIn(), PcodeOp::getParent(), iblock, Varnode::isWritten(), PcodeOp::numInput(), and returnop.

Referenced by testRemovability().

◆ testRemovability()

bool 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 Varnode::beginDescend(), PcodeOp::code(), CPUI_INDIRECT, CPUI_LOAD, CPUI_MULTIEQUAL, CPUI_STORE, Varnode::endDescend(), AddrSpace::getIndex(), PcodeOp::getOut(), Varnode::getSpace(), heritageyes, PcodeOp::isCall(), PcodeOp::isFlowBreak(), testMultiRead(), and testOpRead().

Referenced by verify().

◆ trial()

bool 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 buildHeritageArray(), camethruposta_slot, cbranch, directsplit, iblock, iblock2posta_true, init2a_true, initblock, posta_block, posta_outslot, postb_block, prea_inslot, and verify().

Referenced by ActionConditionalExe::apply().

◆ verify()

bool 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 BlockBasic::beginOp(), camethruposta_slot, directsplit, BlockBasic::endOp(), findInitPre(), FlowBlock::getOut(), iblock, iblock2posta_true, init2a_true, posta_block, posta_outslot, postb_block, prea_inslot, returnop, testIBlock(), testRemovability(), and verifySameCondition().

Referenced by trial().

◆ verifySameCondition()

bool 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, PcodeOp::code(), CPUI_CBRANCH, directsplit, ConditionMarker::getFlip(), ConditionMarker::getMultiSlot(), init2a_true, initblock, BlockBasic::lastOp(), posta_outslot, prea_inslot, and ConditionMarker::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

Member Function Documentation

◆ adjustDirectMulti()

◆ buildHeritageArray()

◆ doReplacement()

◆ execute()

◆ findInitPre()

◆ getNewMulti()

◆ getReplacementRead()

◆ predefineDirectMulti()

◆ testIBlock()

◆ testMultiRead()

◆ testOpRead()

◆ testRemovability()

◆ trial()

◆ verify()

◆ verifySameCondition()