Are there any tests we should add to this? Or does this seem good to merge?

I've added a small fixup which addresses a test case I hadn't sufficiently thought through originally.

One of the tests does depend non-trivially on the recursion being correct, but I can take another pass since TCO seems to be an area of special concern. (In particular, I probably should add some cases exercising more complex chains of inner functions.)

So just as a heads-up: more extensive testing has revealed a number of problems with this patch, which are making me reconsider the approach a little bit. I'll go into more detail when I have more of an opinion formed, but for now, this isn't ready to merge.

Okay, I've resolved all the issues I've found. I didn't change anything too dramatically from the previous implementation but I did miss some important details the first time around. Namely:

Arity

The initial implementation only considered functions with arity 1. Whoops! Handling functions with higher arity, both as the outermost tail-recursive function and as inner functions participating in the recursion, required a bit more care in the implementation. The stickiest part was what to do with functions that are only partially invoked—in the original TCO, any tail call is necessarily going to have arity matching the function declaration, because it wouldn't type-check otherwise. But allowing other functions to be involved allows for things like:

f x y = if y <= 0 then x else g x (y - 1)
  where
  g x' = f (x' + 2)

where even though the recursive call to f is in tail position in g, and g is called in tail position in f, the fact that the last argument is missing from the recursive call to f means that this can't be TCO'd without performing an eta expansion on g. In theory, the optimizer could perform that expansion automatically, but implicit eta expansion seems like the sort of semantics-altering behavior that we try to avoid in the optimizer. So instead, the above example is not optimized.

Nested tail recursion

Currently, functions are TCO'd from the inside out, and they all use the same variable name for loop control. This is not an issue when tail-recursive inner functions don't interact with the tail recursion of outer functions; the inner variable shadows the outer one, which results in correct behavior. Allowing tail recursion to cross function boundaries means that this also needs to be reconsidered; as an example:

f x y = g x (y - 1)
  where
  g x' y' =
    if y' <= 0 then x'
    else if y' > 10000 then g (x' + 3) (y' - 1)
    else f (x' + 2) y'

Both f and g can compile to tail-recursive loops. But different branches of g should trigger either the end of g's loop or the end of both f and g's loops, which means that different variables for controlling those loops are needed. Implementing this meant adding some state to the TCO pass and converting the pass to be top-down rather than bottom-up. I don't think this should have any adverse effects on existing code, but my confidence in that assessment isn't especially high.

This looks good to me too. @rhendric would you like to hit the 'merge' button on this one?

GitHub still tells me I'm not authorized to do that, but otherwise yes!

haha oops

@rhendric try now?