decompiler
1.0.0
|
Build a code structure from a control-flow graph (BlockGraph). More...
#include <blockaction.hh>
Public Member Functions | |
CollapseStructure (BlockGraph &g) | |
Construct given a control-flow graph. More... | |
int4 | getChangeCount (void) const |
Get number of data-flow changes. | |
void | collapseAll (void) |
Run the whole algorithm. More... | |
Private Member Functions | |
bool | checkSwitchSkips (FlowBlock *switchbl, FlowBlock *exitblock) |
Check for switch edges that go straight to the exit block. More... | |
void | onlyReachableFromRoot (FlowBlock *root, vector< FlowBlock *> &body) |
Mark FlowBlocks only reachable from a given root. More... | |
int4 | markExitsAsGotos (vector< FlowBlock *> &body) |
Mark edges exiting the body as unstructured gotos. More... | |
bool | clipExtraRoots (void) |
Mark edges between root components as unstructured gotos. More... | |
void | labelLoops (vector< LoopBody *> &looporder) |
Identify all the loops in this graph. More... | |
void | orderLoopBodies (void) |
Identify and label all loop structure for this graph. More... | |
bool | updateLoopBody (void) |
Find likely unstructured edges within the innermost loop body. More... | |
FlowBlock * | selectGoto (void) |
Select an edge to mark as unstructured. More... | |
bool | ruleBlockGoto (FlowBlock *bl) |
Attempt to apply the BlockGoto structure. More... | |
bool | ruleBlockCat (FlowBlock *bl) |
Attempt to apply a BlockList structure. More... | |
bool | ruleBlockOr (FlowBlock *bl) |
Attempt to apply a BlockCondition structure. More... | |
bool | ruleBlockProperIf (FlowBlock *bl) |
Attempt to apply a 2 component form of BlockIf. More... | |
bool | ruleBlockIfElse (FlowBlock *bl) |
Attempt to apply a 3 component form of BlockIf. More... | |
bool | ruleBlockIfNoExit (FlowBlock *bl) |
Attempt to apply BlockIf where the body does not exit. More... | |
bool | ruleBlockWhileDo (FlowBlock *bl) |
Attempt to apply the BlockWhileDo structure. More... | |
bool | ruleBlockDoWhile (FlowBlock *bl) |
Attempt to apply the BlockDoWhile structure. More... | |
bool | ruleBlockInfLoop (FlowBlock *bl) |
Attempt to apply the BlockInfLoop structure. More... | |
bool | ruleBlockSwitch (FlowBlock *bl) |
Attempt to apply the BlockSwitch structure. More... | |
bool | ruleCaseFallthru (FlowBlock *bl) |
Attempt to one switch case falling through to another. More... | |
int4 | collapseInternal (FlowBlock *targetbl) |
The main collapsing loop. More... | |
void | collapseConditions (void) |
Simplify conditionals. More... | |
Private Attributes | |
bool | finaltrace |
Have we a made search for unstructured edges in the final DAG. | |
bool | likelylistfull |
Have we generated a likely goto list for the current innermost loop. | |
list< FloatingEdge > | likelygoto |
The current likely goto list. | |
list< FloatingEdge >::iterator | likelyiter |
Iterator to the next most likely goto edge. | |
list< LoopBody > | loopbody |
The list of loop bodies for this control-flow graph. | |
list< LoopBody >::iterator | loopbodyiter |
Current (innermost) loop being structured. | |
BlockGraph & | graph |
The control-flow graph. | |
int4 | dataflow_changecount |
Number of data-flow changes made during structuring. | |
Build a code structure from a control-flow graph (BlockGraph).
This class manages the main control-flow structuring algorithm for the decompiler. In short:
ghidra::CollapseStructure::CollapseStructure | ( | BlockGraph & | g | ) |
Construct given a control-flow graph.
The initial BlockGraph should be a copy of the permanent control-flow graph. In particular the FlowBlock nodes should be BlockCopy instances.
g | is the (copy of the) control-flow graph |
References dataflow_changecount.
|
private |
Check for switch edges that go straight to the exit block.
Some switch forms have edges that effectively skip the body of the switch and go straight to the exit Many jumptables schemes have a default (i.e. if nothing else matches) edge. This edge cannot be a normal case because there would be too many labels to explicitly specify. The edge must either be labeled as default or it must go straight to the exit block. If there is a default edge, if it does not go straight to the exit, there can be no other edge that skips straight to the exit.
If such skip edges exist, they are converted to gotos and false is returned.
switchbl | is the entry FlowBlock for the switch |
exitblock | is the designated exit FlowBlock for the switch |
References ghidra::FlowBlock::getOut(), ghidra::FlowBlock::getType(), ghidra::BlockMultiGoto::hasDefaultGoto(), ghidra::FlowBlock::isDefaultBranch(), ghidra::FlowBlock::setGotoBranch(), and ghidra::FlowBlock::sizeOut().
|
private |
Mark edges between root components as unstructured gotos.
Find distinct control-flow FlowBlock roots (having no incoming edges). These delineate disjoint subsets of the control-flow graph, where a subset is defined as the FlowBlock nodes that are only reachable from the root. This method searches for one disjoint subset with cross-over edges, edges from that subset into another. The exiting edges for this subset are marked as unstructured gotos and true is returned.
References ghidra::LoopBody::clearMarks(), and ghidra::FlowBlock::sizeIn().
void ghidra::CollapseStructure::collapseAll | ( | void | ) |
Run the whole algorithm.
Collapse everything in the control-flow graph to isolated blocks with no inputs and outputs.
References ghidra::BlockGraph::clearVisitCount(), collapseConditions(), collapseInternal(), finaltrace, ghidra::BlockGraph::getSize(), graph, orderLoopBodies(), and selectGoto().
Referenced by ghidra::ActionBlockStructure::apply(), ghidra::IfcStructureBlocks::execute(), and ghidra::StructureGraph::rawAction().
|
private |
Simplify conditionals.
Simplify just the conditional AND/OR constructions.
Referenced by collapseAll().
|
private |
The main collapsing loop.
Collapse everything until no additional rules apply. If handed a particular FlowBlock, try simplifying from that block first.
targetbl | is the FlowBlock to start from or NULL |
References ghidra::FlowBlock::sizeIn(), and ghidra::FlowBlock::sizeOut().
Referenced by collapseAll().
|
private |
Identify all the loops in this graph.
Identify all the distinct loops in the graph (via their back-edge) and create a LoopBody record.
looporder | is the container that will hold the LoopBody record for each loop |
References ghidra::LoopBody::addTail(), ghidra::LoopBody::compare_ends(), ghidra::FlowBlock::getIn(), ghidra::FlowBlock::isBackEdgeIn(), and ghidra::FlowBlock::sizeIn().
|
private |
Mark edges exiting the body as unstructured gotos.
The FlowBlock objects in the body must all be marked.
body | is the list of FlowBlock objects in the body |
References ghidra::FlowBlock::getOut(), ghidra::FlowBlock::isMark(), ghidra::FlowBlock::setGotoBranch(), and ghidra::FlowBlock::sizeOut().
|
private |
Mark FlowBlocks only reachable from a given root.
For a given root FlowBlock, find all the FlowBlocks that can only be reached from it, mark them and put them in a list/
root | is the given FlowBlock root |
body | is the container to hold the list of reachable nodes |
References ghidra::FlowBlock::getOut(), ghidra::FlowBlock::getVisitCount(), ghidra::FlowBlock::isMark(), ghidra::FlowBlock::setMark(), ghidra::FlowBlock::setVisitCount(), ghidra::FlowBlock::sizeIn(), and ghidra::FlowBlock::sizeOut().
|
private |
Identify and label all loop structure for this graph.
Find the loop bodies, then:
References ghidra::LoopBody::clearMarks(), and ghidra::LoopBody::mergeIdenticalHeads().
Referenced by collapseAll().
|
private |
Attempt to apply a BlockList structure.
Try to concatenate a straight sequences of blocks starting with the given FlowBlock. All of the internal edges should be DAG (no exit, goto,or loopback). The final edge can be an exit or loopback
bl | is the given FlowBlock |
References ghidra::FlowBlock::getIn(), ghidra::FlowBlock::getOut(), ghidra::FlowBlock::isDecisionOut(), ghidra::FlowBlock::isSwitchOut(), ghidra::FlowBlock::sizeIn(), and ghidra::FlowBlock::sizeOut().
|
private |
Attempt to apply the BlockDoWhile structure.
Try to find a do/while structure, starting with the given FlowBlock. Any break and continue must have already been collapsed as some form of goto.
bl | is the given FlowBlock |
References ghidra::FlowBlock::getOut(), ghidra::FlowBlock::isGotoOut(), ghidra::FlowBlock::isSwitchOut(), ghidra::FlowBlock::negateCondition(), and ghidra::FlowBlock::sizeOut().
|
private |
Attempt to apply the BlockGoto structure.
For the given FlowBlock, look for an outgoing edge marked as unstructured. Create or update the BlockGoto or BlockMultiGoto structure.
bl | is the given FlowBlock |
References ghidra::FlowBlock::isGotoOut(), ghidra::FlowBlock::isSwitchOut(), ghidra::FlowBlock::negateCondition(), and ghidra::FlowBlock::sizeOut().
|
private |
Attempt to apply a 3 component form of BlockIf.
Try to find an if/else structure starting with the given FlowBlock. Edges into the clauses cannot be goto, exit,or loopback. The returning edges can be exit or loopback.
bl | is the given FlowBlock |
References ghidra::FlowBlock::getFalseOut(), ghidra::FlowBlock::getOut(), ghidra::FlowBlock::getTrueOut(), ghidra::FlowBlock::isDecisionOut(), ghidra::FlowBlock::isGotoOut(), ghidra::FlowBlock::isSwitchOut(), ghidra::FlowBlock::sizeIn(), and ghidra::FlowBlock::sizeOut().
|
private |
Attempt to apply BlockIf where the body does not exit.
Try to find an if structure, where the condition clause does not exit, starting with the given FlowBlock.
bl | is the given FlowBlock |
References ghidra::FlowBlock::getOut(), ghidra::FlowBlock::isDecisionOut(), ghidra::FlowBlock::isGotoOut(), ghidra::FlowBlock::isSwitchOut(), ghidra::FlowBlock::negateCondition(), ghidra::FlowBlock::sizeIn(), and ghidra::FlowBlock::sizeOut().
|
private |
Attempt to apply the BlockInfLoop structure.
Try to find a loop structure with no exits, starting at the given FlowBlock.
bl | is the given FlowBlock |
References ghidra::FlowBlock::getOut(), ghidra::FlowBlock::isGotoOut(), and ghidra::FlowBlock::sizeOut().
|
private |
Attempt to apply a BlockCondition structure.
Try to find an OR conditions (finding ANDs by duality) starting with the given FlowBlock. The top of the OR should not perform gotos, the edge to the orblock should not be exit or loopback
bl | is the given FlowBlock |
References ghidra::FlowBlock::getOut(), ghidra::FlowBlock::isBackEdgeOut(), ghidra::FlowBlock::isComplex(), ghidra::FlowBlock::isGotoOut(), ghidra::FlowBlock::isInteriorGotoTarget(), ghidra::FlowBlock::isSwitchOut(), ghidra::FlowBlock::negateCondition(), ghidra::FlowBlock::sizeIn(), and ghidra::FlowBlock::sizeOut().
|
private |
Attempt to apply a 2 component form of BlockIf.
Try to structure a proper if structure (with no else clause) starting from the given FlowBlock. The edge to the clause should not be an exit or loopbottom. The outgoing edges can be exit or loopbottom.
bl | is the given FlowBlock |
References ghidra::FlowBlock::getOut(), ghidra::FlowBlock::isDecisionOut(), ghidra::FlowBlock::isGotoOut(), ghidra::FlowBlock::isSwitchOut(), ghidra::FlowBlock::negateCondition(), ghidra::FlowBlock::sizeIn(), and ghidra::FlowBlock::sizeOut().
|
private |
Attempt to apply the BlockSwitch structure.
Try to find a switch structure, starting with the given FlowBlock.
bl | is the given FlowBlock |
References ghidra::FlowBlock::getOut(), ghidra::FlowBlock::isGotoIn(), ghidra::FlowBlock::isGotoOut(), ghidra::FlowBlock::isSwitchOut(), ghidra::FlowBlock::sizeIn(), and ghidra::FlowBlock::sizeOut().
|
private |
Attempt to apply the BlockWhileDo structure.
Try to find a while/do structure, starting with a given FlowBlock. Any break or continue must have already been collapsed as some form of goto.
bl | is the given FlowBlock |
References ghidra::FlowBlock::getOut(), ghidra::FlowBlock::isComplex(), ghidra::FlowBlock::isGotoOut(), ghidra::FlowBlock::isInteriorGotoTarget(), ghidra::FlowBlock::isSwitchOut(), ghidra::FlowBlock::negateCondition(), ghidra::BlockGraph::newBlockWhileDo(), ghidra::BlockWhileDo::setOverflowSyntax(), ghidra::FlowBlock::sizeIn(), and ghidra::FlowBlock::sizeOut().
|
private |
Attempt to one switch case falling through to another.
Look for a switch case that falls thru to another switch case, starting with the given switch FlowBlock.
bl | is the given FlowBlock |
References ghidra::FlowBlock::getIn(), ghidra::FlowBlock::getOut(), ghidra::FlowBlock::getOutRevIndex(), ghidra::FlowBlock::isSwitchOut(), ghidra::FlowBlock::setGotoBranch(), ghidra::FlowBlock::sizeIn(), and ghidra::FlowBlock::sizeOut().
|
private |
Select an edge to mark as unstructured.
Pick an edge from among the likely goto list generated by a trace of the current innermost loop. Given ongoing collapsing, this may involve updating which loop is currently innermost and throwing out potential edges whose endpoints have already been collapsed.
References ghidra::TraceDAG::likelygoto, and ghidra::FlowBlock::setGotoBranch().
Referenced by collapseAll().
|
private |
Find likely unstructured edges within the innermost loop body.
Find the current innermost loop, make sure its likely goto edges are calculated. If there are no loops, make sure the likely goto edges are calculated for the final DAG.
References ghidra::TraceDAG::addRoot(), ghidra::TraceDAG::initialize(), ghidra::TraceDAG::likelygoto, ghidra::TraceDAG::pushBranches(), ghidra::TraceDAG::setFinishBlock(), and ghidra::FlowBlock::sizeIn().