# Finding loops¶

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

In the below example an ir function is defined, and then the loops are detected.

```>>> import io
>>> from ppci.relooper import find_structure, print_shape
>>> from ppci.irutils import read_module, verify_module
>>> ir_source = """
... module demo;
... function i32 inc(i32 a, i32 b) {
...   inc_block0: {
...     jmp inc_block1;
...   }
...   inc_block1: {
...     i32 x = phi inc_block0: a, inc_block1: result;
...     i32 result = x + b;
...     cjmp result > b ? inc_block2 : inc_block1;
...   }
...   inc_block2: {
...     return result;
...   }
... }
... """
>>> ir_module = read_module(io.StringIO(ir_source))
>>> verify_module(ir_module)
>>> ir_module.stats()
'functions: 1, blocks: 3, instructions: 5'
>>> ir_function = ir_module.get_function('inc')
>>> shape, _ = find_structure(ir_function)
>>> print_shape(shape)
code: CFG-node(inc_block0)
loop
if-then CFG-node(inc_block1)
Break-shape 0
else
Continue-shape 0
end-if
end-loop
code: CFG-node(inc_block2)
```

As can be seen, the program contains one loop.

## 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.``BasicShape`(content)
class `ppci.relooper.``BreakShape`(level)
class `ppci.relooper.``ContinueShape`(level)
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.``SequenceShape`(shapes)
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. A control flow tree structure.

Control flow graph algorithms.

Functions present:

• dominators
• post dominators
• reachability
• dominator tree
• dominance frontier
class `ppci.utils.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

`bottom_up`(tree)

Generator that yields all nodes in bottom up way

`calculate_dominance_frontier`()

Calculate the dominance frontier.

Algorithm from Ron Cytron et al.

how to calculate the dominance frontier for all nodes using the dominator tree.

`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.

`children`(n)

Return all children for node n

`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

`strictly_dominates`(one, other)

Test whether a node strictly dominates another node

`validate`()

Run some sanity checks on the control flow graph

class `ppci.utils.cfg.``ControlFlowNode`(graph, name=None)
`can_reach`(other)

Test if this node can reach the another node

`dominates`(other)

Test whether this node dominates the other node

`post_dominates`(other)

Test whether this node post-dominates the other node

`reached`()

Test if this node is reached

class `ppci.utils.cfg.``DomTreeNode`(node, children)
`children`

Alias for field number 1

`node`

Alias for field number 0

class `ppci.utils.cfg.``IrToCfg`

Convert ir function into a control flow graph

`convert`(ir_function)

Convert ir function into a control flow graph

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

Alias for field number 0

`rest`

Alias for field number 1

`ppci.utils.cfg.``ir_function_to_graph`(ir_function)

Take an ir function and create a cfg of it