# 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;
... 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.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.