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.

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:

Start with a control-flow graph of basic blocks.
Repeatedly apply:
- Search for sub-graphs matching specific code structure elements.
- Note the structure element and collapse the component nodes to a single node.
If the process gets stuck, remove appropriate edges, marking them as unstructured.

Constructor & Destructor Documentation

◆ CollapseStructure()

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

g	is the (copy of the) control-flow graph

References dataflow_changecount.

Member Function Documentation

◆ checkSwitchSkips()

bool 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

switchbl	is the entry FlowBlock for the switch
exitblock	is the designated exit FlowBlock for the switch

Returns: true if there are no skip edges

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

Referenced by ruleBlockSwitch().

◆ clipExtraRoots()

bool 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 LoopBody::clearMarks(), BlockGraph::getBlock(), BlockGraph::getSize(), graph, markExitsAsGotos(), onlyReachableFromRoot(), and FlowBlock::sizeIn().

Referenced by selectGoto().

◆ collapseAll()

void CollapseStructure::collapseAll ( void )

Run the whole algorithm.

Collapse everything in the control-flow graph to isolated blocks with no inputs and outputs.

References BlockGraph::clearVisitCount(), collapseConditions(), collapseInternal(), finaltrace, BlockGraph::getSize(), graph, orderLoopBodies(), and selectGoto().

Referenced by ActionBlockStructure::apply(), and StructureGraph::rawAction().

◆ collapseConditions()

void CollapseStructure::collapseConditions ( void )

private

Simplify conditionals.

Simplify just the conditional AND/OR constructions.

References BlockGraph::getBlock(), BlockGraph::getSize(), graph, and ruleBlockOr().

Referenced by collapseAll().

◆ collapseInternal()

int4 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

targetbl is the FlowBlock to start from or NULL

Returns: the count of isolated FlowBlocks (with no incoming or outgoing edges)

References BlockGraph::getBlock(), BlockGraph::getSize(), graph, ruleBlockCat(), ruleBlockDoWhile(), ruleBlockGoto(), ruleBlockIfElse(), ruleBlockIfNoExit(), ruleBlockInfLoop(), ruleBlockProperIf(), ruleBlockSwitch(), ruleBlockWhileDo(), ruleCaseFallthru(), FlowBlock::sizeIn(), and FlowBlock::sizeOut().

Referenced by collapseAll().

◆ labelLoops()

void 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

looporder is the container that will hold the LoopBody record for each loop

References LoopBody::addTail(), LoopBody::compare_ends(), BlockGraph::getBlock(), FlowBlock::getIn(), BlockGraph::getSize(), graph, FlowBlock::isBackEdgeIn(), loopbody, and FlowBlock::sizeIn().

Referenced by orderLoopBodies().

◆ markExitsAsGotos()

int4 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

body	is the list of FlowBlock objects in the body

Returns: the number of edges that were marked as unstructured

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

Referenced by clipExtraRoots().

◆ onlyReachableFromRoot()

void 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

root	is the given FlowBlock root
body	is the container to hold the list of reachable nodes

References FlowBlock::getOut(), FlowBlock::getVisitCount(), FlowBlock::isMark(), FlowBlock::setMark(), FlowBlock::setVisitCount(), FlowBlock::sizeIn(), and FlowBlock::sizeOut().

Referenced by clipExtraRoots().

◆ orderLoopBodies()

void 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 LoopBody::clearMarks(), labelLoops(), likelylistfull, loopbody, loopbodyiter, and LoopBody::mergeIdenticalHeads().

Referenced by collapseAll().

◆ ruleBlockCat()

bool 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

bl	is the given FlowBlock

Returns: true if the structure was applied

References FlowBlock::getIn(), FlowBlock::getOut(), graph, FlowBlock::isDecisionOut(), FlowBlock::isSwitchOut(), BlockGraph::newBlockList(), FlowBlock::sizeIn(), and FlowBlock::sizeOut().

Referenced by collapseInternal().

◆ ruleBlockDoWhile()

bool 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

bl	is the given FlowBlock

Returns: true if the structure was applied

References dataflow_changecount, FlowBlock::getOut(), graph, FlowBlock::isGotoOut(), FlowBlock::isSwitchOut(), FlowBlock::negateCondition(), BlockGraph::newBlockDoWhile(), and FlowBlock::sizeOut().

Referenced by collapseInternal().

◆ ruleBlockGoto()

bool 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

bl	is the given FlowBlock

Returns: true if the structure was applied

References dataflow_changecount, graph, FlowBlock::isGotoOut(), FlowBlock::isSwitchOut(), FlowBlock::negateCondition(), BlockGraph::newBlockGoto(), BlockGraph::newBlockIfGoto(), BlockGraph::newBlockMultiGoto(), and FlowBlock::sizeOut().

Referenced by collapseInternal().

◆ ruleBlockIfElse()

bool 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

bl	is the given FlowBlock

Returns: true if the structure was applied

References FlowBlock::getFalseOut(), FlowBlock::getOut(), FlowBlock::getTrueOut(), graph, FlowBlock::isDecisionOut(), FlowBlock::isGotoOut(), FlowBlock::isSwitchOut(), BlockGraph::newBlockIfElse(), FlowBlock::sizeIn(), and FlowBlock::sizeOut().

Referenced by collapseInternal().

◆ ruleBlockIfNoExit()

bool 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

bl	is the given FlowBlock

Returns: true if the structure was applied

References dataflow_changecount, FlowBlock::getOut(), graph, FlowBlock::isDecisionOut(), FlowBlock::isGotoOut(), FlowBlock::isSwitchOut(), FlowBlock::negateCondition(), BlockGraph::newBlockIf(), FlowBlock::sizeIn(), and FlowBlock::sizeOut().

Referenced by collapseInternal().

◆ ruleBlockInfLoop()

bool 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

bl	is the given FlowBlock

Returns: true if the structure was applied

References FlowBlock::getOut(), graph, FlowBlock::isGotoOut(), BlockGraph::newBlockInfLoop(), and FlowBlock::sizeOut().

Referenced by collapseInternal().

◆ ruleBlockOr()

bool 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

bl	is the given FlowBlock

Returns: true if the structure was applied

References dataflow_changecount, FlowBlock::getOut(), graph, FlowBlock::isBackEdgeOut(), FlowBlock::isComplex(), FlowBlock::isGotoOut(), FlowBlock::isInteriorGotoTarget(), FlowBlock::isSwitchOut(), FlowBlock::negateCondition(), BlockGraph::newBlockCondition(), FlowBlock::sizeIn(), and FlowBlock::sizeOut().

Referenced by collapseConditions().

◆ ruleBlockProperIf()

bool 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

bl	is the given FlowBlock

Returns: true if the structure was applied

References dataflow_changecount, FlowBlock::getOut(), graph, FlowBlock::isDecisionOut(), FlowBlock::isGotoOut(), FlowBlock::isSwitchOut(), FlowBlock::negateCondition(), BlockGraph::newBlockIf(), FlowBlock::sizeIn(), and FlowBlock::sizeOut().

Referenced by collapseInternal().

◆ ruleBlockSwitch()

bool CollapseStructure::ruleBlockSwitch ( FlowBlock * bl )

private

Attempt to apply the BlockSwitch structure.

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

Parameters

bl	is the given FlowBlock

Returns: true if the structure was applied

References checkSwitchSkips(), FlowBlock::getOut(), graph, FlowBlock::isGotoIn(), FlowBlock::isGotoOut(), FlowBlock::isSwitchOut(), BlockGraph::newBlockSwitch(), FlowBlock::sizeIn(), and FlowBlock::sizeOut().

Referenced by collapseInternal().

◆ ruleBlockWhileDo()

bool 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

bl	is the given FlowBlock

Returns: true if the structure was applied

References dataflow_changecount, FlowBlock::getOut(), graph, FlowBlock::isComplex(), FlowBlock::isGotoOut(), FlowBlock::isInteriorGotoTarget(), FlowBlock::isSwitchOut(), FlowBlock::negateCondition(), BlockGraph::newBlockWhileDo(), BlockWhileDo::setOverflowSyntax(), FlowBlock::sizeIn(), and FlowBlock::sizeOut().

Referenced by collapseInternal().

◆ ruleCaseFallthru()

bool 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

bl	is the given FlowBlock

Returns: true if the structure was applied

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

Referenced by collapseInternal().

◆ selectGoto()

FlowBlock * 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 clipExtraRoots(), graph, likelygoto, likelyiter, FlowBlock::setGotoBranch(), and updateLoopBody().

Referenced by collapseAll().

◆ updateLoopBody()

bool 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 TraceDAG::addRoot(), finaltrace, BlockGraph::getBlock(), BlockGraph::getSize(), graph, TraceDAG::initialize(), likelygoto, likelyiter, likelylistfull, loopbody, loopbodyiter, TraceDAG::pushBranches(), TraceDAG::setFinishBlock(), and FlowBlock::sizeIn().

Referenced by selectGoto().

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

blockaction.hh
blockaction.cc

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ CollapseStructure()

Member Function Documentation

◆ checkSwitchSkips()

◆ clipExtraRoots()

◆ collapseAll()

◆ collapseConditions()

◆ collapseInternal()

◆ labelLoops()

◆ markExitsAsGotos()

◆ onlyReachableFromRoot()

◆ orderLoopBodies()

◆ ruleBlockCat()

◆ ruleBlockDoWhile()

◆ ruleBlockGoto()

◆ ruleBlockIfElse()

◆ ruleBlockIfNoExit()

◆ ruleBlockInfLoop()

◆ ruleBlockOr()

◆ ruleBlockProperIf()

◆ ruleBlockSwitch()

◆ ruleBlockWhileDo()

◆ ruleCaseFallthru()

◆ selectGoto()

◆ updateLoopBody()