JetBrains/kotlin — pull request #310 by cy6erGn0m (2013-10-15 18:06:28+00:00)
Title: Tail recursion optimization

Subj

This patch provides optimization for tail recursions of functions that marked with annotation TailRecursive.
See compiler/testData/codegen/box/functions/recursion.kt for examples.

Test FunctionCodegenTest have test with full list of cases that should be optimized in recursion.kt so if optimizer will optimize something that it shouldn't then it will fail. Also there is black box test to ensure that the generated code is working.

Briefly optimizer works as follows: if call expression is found then we are looking from call psi element to the top. At every step we are checking the the node is last in block, inside then/else in IF but not condition, inside finally or catch without finally, inside when branch expression but not condition, and so on. In some cases we can see that it's tail recursion (for example if we discovered recursive call node directly inside return expression). In some case we can stop trace if we discover that surely no tail recursion (for example if we found our node in the middle of block element and no void return after it).

The generated code works as follows. Let's imagine we have the following:

```kotlin
fun me(x : Int, const : String) {
if (x > 0) {
me(x - 1, const)
}
}
```

Then it will be optimized to this (pesudocode)
```
L0:
assertNotNullParameter(const, "const")
L1:
if not x > 0 then goto L2
push x - 1
pop to x
// we don't push const since it's already assigned
goto L1
L2:
return
```

Also note that non-tail recursive calls are generated as usual.