Skip to content

Loops

Finds the loops in one function.

Where this happens

LoopFinder::for_each_loop in codegen/optimizations/helpers/loops.rs.

Used by Nonvolatile Memory to find wait loops.

How we find them

    mov  esi, [ecx]
loop:
    cmp  dword ptr [esi], 0
    jz   loop

Step 1: find the jumps back

loop:               ; <- header
    ...
    jz   loop       ; <- jumps back

We follow every path from the start of function.
A jump to an instruction we passed on the way here closes a loop.

Step 2: collect the loop

loop:                        ; stop here
    cmp  dword ptr [esi], 0  ; in the loop
    jz   loop                ; start here, walk back

We walk back from the jz until we hit loop.
Everything we pass is in the loop.

Giving up

We return false if:

  • We can't follow the function's jumps.
  • Something jumps into the middle of a loop.
    We notice that when walking back reaches the function entry.

Loops found before that were already handed to the caller.
So if false comes back, throw away what you got.