decompiler  1.0.0
Public Member Functions | Private Member Functions | Private Attributes | List of all members
ghidra::ConditionalExecution Class Reference

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

#include <condexe.hh>

Public Member Functions

 ConditionalExecution (Funcdata *f)
 Constructor. More...
 
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...
 
VarnodegetNewMulti (PcodeOp *op, BlockBasic *bl)
 Create a MULTIEQUAL in the given block that will hold data-flow from the given PcodeOp. More...
 
VarnodegetReplacementRead (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

Funcdatafd
 Function being analyzed.
 
PcodeOpcbranch
 CBRANCH in iblock.
 
BlockBasicinitblock
 The initial block computing the boolean value.
 
BlockBasiciblock
 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.
 
BlockBasicposta_block
 First block in posta path.
 
BlockBasicpostb_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.

Constructor & Destructor Documentation

◆ ConditionalExecution()

ghidra::ConditionalExecution::ConditionalExecution ( Funcdata f)

Constructor.

Set up for testing ConditionalExecution on multiple iblocks

Parameters
fis the function to do testing on

Member Function Documentation

◆ adjustDirectMulti()

void ghidra::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 ghidra::PcodeOp::code(), ghidra::CPUI_MULTIEQUAL, ghidra::Varnode::getDef(), ghidra::PcodeOp::getIn(), ghidra::PcodeOp::getParent(), ghidra::Varnode::isWritten(), and ghidra::PcodeOp::numInput().

◆ 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 ghidra::AddrSpace::getIndex(), ghidra::AddrSpaceManager::getSpace(), ghidra::AddrSpace::isHeritaged(), and ghidra::AddrSpaceManager::numSpaces().

◆ 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
opis the given PcodeOp

References ghidra::Varnode::beginDescend(), ghidra::PcodeOp::code(), ghidra::CPUI_COPY, ghidra::CPUI_MULTIEQUAL, ghidra::Varnode::endDescend(), ghidra::PcodeOp::getIn(), ghidra::FlowBlock::getIn(), ghidra::FlowBlock::getInRevIndex(), ghidra::PcodeOp::getOut(), ghidra::PcodeOp::getParent(), ghidra::PcodeOp::getSlot(), and ghidra::Varnode::hasNoDescend().

◆ execute()

void ghidra::ConditionalExecution::execute ( void  )

Eliminate the unnecessary path join at iblock.

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

References ghidra::PcodeOp::code(), ghidra::CPUI_MULTIEQUAL, and ghidra::PcodeOp::isBranch().

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::sizeIn(), and ghidra::FlowBlock::sizeOut().

◆ 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
opis the PcodeOp whose output will get held
blis the block that will contain the new MULTIEQUAL
Returns
the output Varnode of the new MULTIEQUAL

References ghidra::CPUI_MULTIEQUAL, ghidra::PcodeOp::getOut(), ghidra::Varnode::getSize(), ghidra::BlockBasic::getStart(), and ghidra::FlowBlock::sizeIn().

◆ 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
opis the given PcodeOp whose output we must replace
blis the given basic block (containing a read of the Varnode)
Returns
the replacement Varnode

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

◆ predefineDirectMulti()

void ghidra::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
opis the given PcodeOp

References ghidra::CPUI_MULTIEQUAL, ghidra::Varnode::getAddr(), ghidra::PcodeOp::getIn(), ghidra::PcodeOp::getOut(), and ghidra::Varnode::getSize().

◆ 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 ghidra::CPUI_CBRANCH.

◆ testMultiRead()

bool ghidra::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
vnis the given Varnode
opis 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::PcodeOp::getIn(), ghidra::PcodeOp::getParent(), and ghidra::PcodeOp::numInput().

◆ 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
vnis the given Varnode
opis 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_MULTIEQUAL, ghidra::CPUI_RETURN, ghidra::Varnode::getDef(), ghidra::PcodeOp::getIn(), ghidra::PcodeOp::getParent(), ghidra::Varnode::isWritten(), and ghidra::PcodeOp::numInput().

◆ testRemovability()

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

◆ 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
ibis the trial iblock
Returns
true if (some) configuration is recognized and can be modified

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

◆ 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 ghidra::PcodeOp::code(), ghidra::CPUI_CBRANCH, ghidra::ConditionMarker::getFlip(), ghidra::ConditionMarker::getMultiSlot(), ghidra::ConditionMarker::multislot, and ghidra::ConditionMarker::verifyCondition().


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