Finding loops

To detect program structure like loops and if statements from basic blocks, one can use algorithms in these classes to find them.

Warning

Example below is idea of an API.

>>> from ppci.relooper import find_structure
>>> # TODO: show sensible demo

Reference

Rverse engineer the structured control flow of a program.

Possible algorithms:

References:

[Cifuentes1998]

[Baker1977]

A hint might be “Hammock graphs” which are single entry, single exit graphs. They might be the join point between dominator and post dominator nodes.

class ppci.relooper.IfShape(content, yes_shape, no_shape)

If statement

class ppci.relooper.LoopShape(body)

Loop shape

class ppci.relooper.MultipleShape

Can be a switch statement?

class ppci.relooper.Relooper

Implementation of the relooper algorithm

class ppci.relooper.Shape

A control flow shape.

ppci.relooper.find_structure(ir_function)

Figure out the block structure of

Parameters:ir_function – an ir.SubRoutine containing a soup-of-blocks.
Returns:A control flow tree structure.

Control flow graph module

class ppci.cfg.ControlFlowGraph

Control flow graph.

Has methods to query properties of the control flow graph and its nodes.

Such as: - Dominators - Strict dominators - Immediate dominators - Post dominators - Strict post dominators - Immediate post dominators - Reachable nodes - Loops

calculate_dominators()

Calculate the dominator sets iteratively

calculate_immediate_dominators()

Calculate immediate dominators for all nodes.

Do this by choosing n from sdom(x) such that dom(n) == sdom(x).

calculate_immediate_post_dominators()

Calculate immediate post dominators for all nodes.

Do this by choosing n from spdom(x) such that pdom(n) == spdom(x).

calculate_loops()

Calculate loops by use of the dominator info

calculate_post_dominators()

Calculate the post dominator sets iteratively.

Post domination is the same as domination, but then starting at the exit node.

calculate_reach()

Calculate which nodes can reach what other nodes

calculate_strict_dominators()

Calculate the strict dominators.

Strict domination is the dominance set minus the node itself.

dominates(one, other)

Test whether a node dominates another node

get_immediate_dominator(node)

Retrieve a nodes immediate dominator

get_immediate_post_dominator(node)

Retrieve a nodes immediate post dominator

post_dominates(one, other)

Test whether a node post dominates another node

validate()

Run some sanity checks on the control flow graph

class ppci.cfg.DomTreeNode(block, children)
block

Alias for field number 0

children

Alias for field number 1

class ppci.cfg.IrToCfg

Convert ir function into a control flow graph

convert(ir_function)

Convert ir function into a control flow graph

class ppci.cfg.Loop(header, rest)
header

Alias for field number 0

rest

Alias for field number 1

ppci.cfg.ir_function_to_graph(ir_function)

Take an ir function and create a cfg of it