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;
...   }
... }
... """
>>> 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)
         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:

• relooper https://github.com/kripken/Relooper/blob/master/paper.pdf

[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. Returns:A control flow tree structure.