Failure to detect obvious tail call #6441
Original bug ID: 6441
Consider the following recursive binding group:
let rec foo a b c d e f g h i j k l m n o = function
Note: (1) the number of parameters of the function foo exceeds the number of available registers for integer arguments on any of the currently supported target platforms; (2) foo is tail-recursive; (3) the binding group mixes functional and nonfunctional bindings.
Under these circumstances, the native-code compiler does not emit a tail call for the recursive invocation of foo.
This is to be considered a serious bugs as programmers tend to rely heavily on tail-call optimisation to be performed (cf., e.g., https://realworldocaml.org/v1/en/html/lists-and-patterns.html#tail-recursion).
Steps to reproduce
$ ocamlopt -v
$ cat test.ml
let _ =
$ ocamlopt test.ml -o a.out
This defect is a direct consequence of the way in closure conversion is performed for mixed recursive binding groups. The right-hand sides of the functional bindings in such groups are closed as anonymous rather than named expressions. For example, in the example above, closure conversion results in the following clambda-expression:
As the right-hand side of the binding for foo is closed as an anonymous expression, the recursive call to foo is compiled as an indirect call rather than a direct call.
Later on, during pseudo-instruction generation this indirection causes the call not be recognised as a direct recursive call. For calls to functions that require arguments to be passed via the stack, being a direct recursive call is however a necessary condition for being complied as a tail call.
The solution to this problem is as simple as making sure that the right-hand side of a functional binding in a recursive binding group is always closed as a named expression.
Comment author: stefanholdermans
A pull request for a fix (accompanied by a regression test) was submitted: #66.
With this fix, closure conversion now yields, as desired, a direct recursive call:
Moreover, the closure for foo does not need an environment anymore.
All-importantly, pseudo-instruction selection now results in a tail call being generated for the recursive invocation of foo:
$ ../bin/ocamlopt test.ml -o b.out
Comment author: @gasche
I'll merge this.
The procedure is very simple:
I use a git-svn repo internally (a git repository that can checkout/commit from/to the SVN repo through the "git svn" tools), where it's even simpler to merge commits: "git am foo.patch", (fix the commit message, Changes, etc.) then "git svn dcommit".