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

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...
 
FlowBlockselectGoto (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< FloatingEdgelikelygoto
 The current likely goto list.
 
list< FloatingEdge >::iterator likelyiter
 Iterator to the next most likely goto edge.
 
list< LoopBodyloopbody
 The list of loop bodies for this control-flow graph.
 
list< LoopBody >::iterator loopbodyiter
 Current (innermost) loop being structured.
 
BlockGraphgraph
 The control-flow graph.
 
int4 dataflow_changecount
 Number of data-flow changes made during structuring.
 

Detailed Description

Build a code structure from a control-flow graph (BlockGraph).

This class manages the main control-flow structuring algorithm for the decompiler. In short:

Constructor & Destructor Documentation

◆ CollapseStructure()

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.

Parameters
gis the (copy of the) control-flow graph

References dataflow_changecount.

Member Function Documentation

◆ checkSwitchSkips()

bool ghidra::CollapseStructure::checkSwitchSkips ( FlowBlock switchbl,
FlowBlock exitblock 
)
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.

Parameters
switchblis the entry FlowBlock for the switch
exitblockis the designated exit FlowBlock for the switch
Returns
true if there are no skip edges

References ghidra::FlowBlock::getOut(), ghidra::FlowBlock::getType(), ghidra::BlockMultiGoto::hasDefaultGoto(), ghidra::FlowBlock::isDefaultBranch(), ghidra::FlowBlock::setGotoBranch(), and ghidra::FlowBlock::sizeOut().

◆ clipExtraRoots()

bool ghidra::CollapseStructure::clipExtraRoots ( void  )
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.

Returns
true if any cross-over edges were found (and marked)

References ghidra::LoopBody::clearMarks(), and ghidra::FlowBlock::sizeIn().

◆ collapseAll()

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().

◆ collapseConditions()

void ghidra::CollapseStructure::collapseConditions ( void  )
private

Simplify conditionals.

Simplify just the conditional AND/OR constructions.

Referenced by collapseAll().

◆ collapseInternal()

int4 ghidra::CollapseStructure::collapseInternal ( FlowBlock targetbl)
private

The main collapsing loop.

Collapse everything until no additional rules apply. If handed a particular FlowBlock, try simplifying from that block first.

Parameters
targetblis the FlowBlock to start from or NULL
Returns
the count of isolated FlowBlocks (with no incoming or outgoing edges)

References ghidra::FlowBlock::sizeIn(), and ghidra::FlowBlock::sizeOut().

Referenced by collapseAll().

◆ labelLoops()

void ghidra::CollapseStructure::labelLoops ( vector< LoopBody *> &  looporder)
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.

Parameters
looporderis 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().

◆ markExitsAsGotos()

int4 ghidra::CollapseStructure::markExitsAsGotos ( vector< FlowBlock *> &  body)
private

Mark edges exiting the body as unstructured gotos.

The FlowBlock objects in the body must all be marked.

Parameters
bodyis the list of FlowBlock objects in the body
Returns
the number of edges that were marked as unstructured

References ghidra::FlowBlock::getOut(), ghidra::FlowBlock::isMark(), ghidra::FlowBlock::setGotoBranch(), and ghidra::FlowBlock::sizeOut().

◆ onlyReachableFromRoot()

void ghidra::CollapseStructure::onlyReachableFromRoot ( FlowBlock root,
vector< FlowBlock *> &  body 
)
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/

Parameters
rootis the given FlowBlock root
bodyis 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().

◆ orderLoopBodies()

void ghidra::CollapseStructure::orderLoopBodies ( void  )
private

Identify and label all loop structure for this graph.

Find the loop bodies, then:

  • Label all edges which exit their loops.
  • Generate a partial order on the loop bodies.

References ghidra::LoopBody::clearMarks(), and ghidra::LoopBody::mergeIdenticalHeads().

Referenced by collapseAll().

◆ ruleBlockCat()

bool ghidra::CollapseStructure::ruleBlockCat ( FlowBlock bl)
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

Parameters
blis the given FlowBlock
Returns
true if the structure was applied

References ghidra::FlowBlock::getIn(), ghidra::FlowBlock::getOut(), ghidra::FlowBlock::isDecisionOut(), ghidra::FlowBlock::isSwitchOut(), ghidra::FlowBlock::sizeIn(), and ghidra::FlowBlock::sizeOut().

◆ ruleBlockDoWhile()

bool ghidra::CollapseStructure::ruleBlockDoWhile ( FlowBlock bl)
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.

Parameters
blis the given FlowBlock
Returns
true if the structure was applied

References ghidra::FlowBlock::getOut(), ghidra::FlowBlock::isGotoOut(), ghidra::FlowBlock::isSwitchOut(), ghidra::FlowBlock::negateCondition(), and ghidra::FlowBlock::sizeOut().

◆ ruleBlockGoto()

bool ghidra::CollapseStructure::ruleBlockGoto ( FlowBlock bl)
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.

Parameters
blis the given FlowBlock
Returns
true if the structure was applied

References ghidra::FlowBlock::isGotoOut(), ghidra::FlowBlock::isSwitchOut(), ghidra::FlowBlock::negateCondition(), and ghidra::FlowBlock::sizeOut().

◆ ruleBlockIfElse()

bool ghidra::CollapseStructure::ruleBlockIfElse ( FlowBlock bl)
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.

Parameters
blis the given FlowBlock
Returns
true if the structure was applied

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().

◆ ruleBlockIfNoExit()

bool ghidra::CollapseStructure::ruleBlockIfNoExit ( FlowBlock bl)
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.

Parameters
blis the given FlowBlock
Returns
true if the structure was applied

References ghidra::FlowBlock::getOut(), ghidra::FlowBlock::isDecisionOut(), ghidra::FlowBlock::isGotoOut(), ghidra::FlowBlock::isSwitchOut(), ghidra::FlowBlock::negateCondition(), ghidra::FlowBlock::sizeIn(), and ghidra::FlowBlock::sizeOut().

◆ ruleBlockInfLoop()

bool ghidra::CollapseStructure::ruleBlockInfLoop ( FlowBlock bl)
private

Attempt to apply the BlockInfLoop structure.

Try to find a loop structure with no exits, starting at the given FlowBlock.

Parameters
blis the given FlowBlock
Returns
true if the structure was applied

References ghidra::FlowBlock::getOut(), ghidra::FlowBlock::isGotoOut(), and ghidra::FlowBlock::sizeOut().

◆ ruleBlockOr()

bool ghidra::CollapseStructure::ruleBlockOr ( FlowBlock bl)
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

Parameters
blis the given FlowBlock
Returns
true if the structure was applied

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().

◆ ruleBlockProperIf()

bool ghidra::CollapseStructure::ruleBlockProperIf ( FlowBlock bl)
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.

Parameters
blis the given FlowBlock
Returns
true if the structure was applied

References ghidra::FlowBlock::getOut(), ghidra::FlowBlock::isDecisionOut(), ghidra::FlowBlock::isGotoOut(), ghidra::FlowBlock::isSwitchOut(), ghidra::FlowBlock::negateCondition(), ghidra::FlowBlock::sizeIn(), and ghidra::FlowBlock::sizeOut().

◆ ruleBlockSwitch()

bool ghidra::CollapseStructure::ruleBlockSwitch ( FlowBlock bl)
private

Attempt to apply the BlockSwitch structure.

Try to find a switch structure, starting with the given FlowBlock.

Parameters
blis the given FlowBlock
Returns
true if the structure was applied

References ghidra::FlowBlock::getOut(), ghidra::FlowBlock::isGotoIn(), ghidra::FlowBlock::isGotoOut(), ghidra::FlowBlock::isSwitchOut(), ghidra::FlowBlock::sizeIn(), and ghidra::FlowBlock::sizeOut().

◆ ruleBlockWhileDo()

bool ghidra::CollapseStructure::ruleBlockWhileDo ( FlowBlock bl)
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.

Parameters
blis the given FlowBlock
Returns
true if the structure was applied

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().

◆ ruleCaseFallthru()

bool ghidra::CollapseStructure::ruleCaseFallthru ( FlowBlock bl)
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.

Parameters
blis the given FlowBlock
Returns
true if the structure was applied

References ghidra::FlowBlock::getIn(), ghidra::FlowBlock::getOut(), ghidra::FlowBlock::getOutRevIndex(), ghidra::FlowBlock::isSwitchOut(), ghidra::FlowBlock::setGotoBranch(), ghidra::FlowBlock::sizeIn(), and ghidra::FlowBlock::sizeOut().

◆ selectGoto()

FlowBlock * ghidra::CollapseStructure::selectGoto ( void  )
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.

Returns
the FlowBlock whose outgoing edge was marked unstructured or NULL

References ghidra::TraceDAG::likelygoto, and ghidra::FlowBlock::setGotoBranch().

Referenced by collapseAll().

◆ updateLoopBody()

bool ghidra::CollapseStructure::updateLoopBody ( void  )
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.

Returns
true if there are likely unstructured edges left to provide

References ghidra::TraceDAG::addRoot(), ghidra::TraceDAG::initialize(), ghidra::TraceDAG::likelygoto, ghidra::TraceDAG::pushBranches(), ghidra::TraceDAG::setFinishBlock(), and ghidra::FlowBlock::sizeIn().


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