# 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.graph.relooper import find_structure, print_shape
>>> from ppci.irutils import read_module, verify_module
>>> ir_source = """
... module demo;
... global 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;
...   }
... }
... """
>>> 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)
code: CFG-node(inc_block2)
else
Continue-shape 0
end-if
end-loop
```

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.

The algorithm for finding a program structure is as following:

• Create a control flow graph from the ir-function.
• Find loops in the control flow graph
• Now start with entry node, and check if this node is:
• a start of a loop
• an if statement with two outgoing control flow paths
• straight line code
class `ppci.graph.relooper.``BasicShape`(content)
class `ppci.graph.relooper.``BreakShape`(level)
class `ppci.graph.relooper.``ContinueShape`(level)
class `ppci.graph.relooper.``IfShape`(content, yes_shape, no_shape)

If statement

class `ppci.graph.relooper.``LoopShape`(body)

Loop shape

class `ppci.graph.relooper.``MultipleShape`

Can be a switch statement?

class `ppci.graph.relooper.``Relooper`

Implementation of the relooper algorithm

class `ppci.graph.relooper.``SequenceShape`(shapes)
class `ppci.graph.relooper.``Shape`

A control flow shape.

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