Induction detection is relatively simple in LLVM IR. The first thing to remember is that the compiler doesn't work on the same source code that the human does;

Induction detection is relatively simple in LLVM IR. The first thing to remember is that the compiler doesn't work on the same source code that the human does; it works on a different representation. The canonical loop structure would look something like this: loop.preheader: ; This is the block that executes before the loop does. br label %loop.body; loop.body: %i = phi i32 [0, %loop.preheader], [%i.next, %loop.body] %val = phi i1 [0, %loop.preheader], [%val.next, %loop.body] %val.next = xor i1 %val, -1 %i.next = add i32 %i, 1 %cmp = icmp slt i32 %i, %N br i1 %cmp, %loop.exit, %loop.body loop.exit: ; After the loop is done Because of how phis work, in constructing this form, we immediately realize how to describe a value either in terms of its value in the first iteration (this is the value it takes coming from the preheader), or in terms solely of its value in the previous iteration. In other words, %val.next = f(%val) for some function f, which we can easily identify in the source code. Now, if we can compute the repeated composition of f easily, we can replace the recurrence in the loop with repeated composition. Repeated addition of the same value is multiplication, and repeated multiplication of the same value is exponentiation--that's two very easy examples to do so. We recognize that there is no use of the value except of its final occurrence, and so instead of doing the loop, we can generate the composition itself. Thus, after N iterations of the loop, we can conclude that %val.next = f^N(0), and if we can identify the loop iteration count (that's %N in this case), we can simply write out f^N instead of having to compute every individual value.