decompiler
1.0.0
|
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... | |
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. | |
A class for simplifying a series of conditionally executed statements.
This class tries to perform transformations like the following:
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:
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.
ghidra::ConditionalExecution::ConditionalExecution | ( | Funcdata * | f | ) |
Constructor.
Set up for testing ConditionalExecution on multiple iblocks
f | is the function to do testing on |
|
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().
|
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().
|
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.
op | is 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().
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().
|
private |
Find initblock, based on iblock.
References ghidra::FlowBlock::getIn(), ghidra::FlowBlock::sizeIn(), and ghidra::FlowBlock::sizeOut().
|
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
op | is the PcodeOp whose output will get held |
bl | is the block that will contain the new MULTIEQUAL |
References ghidra::CPUI_MULTIEQUAL, ghidra::PcodeOp::getOut(), ghidra::Varnode::getSize(), ghidra::BlockBasic::getStart(), and ghidra::FlowBlock::sizeIn().
|
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.
op | is the given PcodeOp whose output we must replace |
bl | is the given basic block (containing a read of the Varnode) |
References ghidra::FlowBlock::getImmedDom(), ghidra::PcodeOp::getIn(), and ghidra::FlowBlock::getIndex().
|
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.
op | is the given PcodeOp |
References ghidra::CPUI_MULTIEQUAL, ghidra::Varnode::getAddr(), ghidra::PcodeOp::getIn(), ghidra::PcodeOp::getOut(), and ghidra::Varnode::getSize().
|
private |
Test the most basic requirements on iblock.
The block must have 2 in edges and 2 out edges and a final CBRANCH op.
References ghidra::CPUI_CBRANCH.
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
References ghidra::PcodeOp::code(), ghidra::CPUI_COPY, ghidra::CPUI_RETURN, ghidra::PcodeOp::getIn(), ghidra::PcodeOp::getParent(), and ghidra::PcodeOp::numInput().
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
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().
|
private |
Test if the given PcodeOp can be removed from iblock.
op | is the PcodeOp within iblock to test |
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(), ghidra::PcodeOp::isCall(), and ghidra::PcodeOp::isFlowBreak().
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.
ib | is the trial iblock |
Referenced by ghidra::ActionConditionalExe::apply().
|
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.
|
private |
Verify that initblock and iblock branch on the same condition.
The conditions must always have the same value or always have complementary values.
References ghidra::PcodeOp::code(), ghidra::CPUI_CBRANCH, ghidra::ConditionMarker::getFlip(), ghidra::ConditionMarker::getMultiSlot(), ghidra::ConditionMarker::multislot, and ghidra::ConditionMarker::verifyCondition().