Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Failure to detect obvious tail call #6441

Closed
vicuna opened this issue May 22, 2014 · 3 comments
Closed

Failure to detect obvious tail call #6441

vicuna opened this issue May 22, 2014 · 3 comments
Assignees
Milestone

Comments

@vicuna
Copy link

vicuna commented May 22, 2014

Original bug ID: 6441
Reporter: stefanholdermans
Assigned to: @gasche
Status: closed (set by @xavierleroy on 2015-12-11T18:27:58Z)
Resolution: fixed
Priority: normal
Severity: major
Version: 4.01.0
Target version: 4.02.0+dev
Category: back end (clambda to assembly)
Tags: patch
Monitored by: stefanholdermans @gasche

Bug description

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
| 0 -> a
| x -> (* tail call: *)
foo (a + 1) (b + 2) (c + 3) (d + 4) (e + 5) (f + 6) (g + 7) (h + 8)
(i + 9) (j + 10) (k + 11) (l + 12) (m + 13) (n + 14) (o + 15)
(x - 1)
and bar = [foo]

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
The OCaml native-code compiler, version 4.02.0+dev10-2014-05-20
Standard library directory: /Users/stefan/Code/ocaml/lib/ocaml

$ cat test.ml
let rec foo a b c d e f g h i j k l m n o = function
| 0 -> a
| x -> (* tail call: *)
foo (a + 1) (b + 2) (c + 3) (d + 4) (e + 5) (f + 6) (g + 7) (h + 8)
(i + 9) (j + 10) (k + 11) (l + 12) (m + 13) (n + 14) (o + 15)
(x - 1)
and bar = [foo]

let _ =
Printf.printf "%d\n" (foo 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 10000000)

$ ocamlopt test.ml -o a.out

$ ./a.out
Fatal error: exception Stack_overflow

Additional information

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:

(letrec
(foo/1027
(closure
(fun camlTest__fun_1066
16 a/1029 b/1030 c/1031 d/1032 e/1033 f/1034 g/1035 h/1036 i/1037
j/1038 k/1039 l/1040 m/1041 n/1042 o/1043 x/1044 env/1068
(if (!= x/1044 0)
(apply (field 3 env/1068) (+ a/1029 1) (+ b/1030 2) (+ c/1031 3)
(+ d/1032 4) (+ e/1033 5) (+ f/1034 6) (+ g/1035 7)
(+ h/1036 8) (+ i/1037 9) (+ j/1038 10) (+ k/1039 11)
(+ l/1040 12) (+ m/1041 13) (+ n/1042 14) (+ o/1043 15)
(- x/1044 1))
a/1029))
foo/1027)
bar/1028 (makeblock 0 foo/1027 0a))
(seq (setfield_imm 0 (global camlTest!) foo/1027)
(setfield_imm 1 (global camlTest!) bar/1028)))

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.

File attachments

@vicuna
Copy link
Author

vicuna commented May 22, 2014

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:

(letrec
(foo/1027
(closure
(fun camlTest__foo_1027
16 a/1029 b/1030 c/1031 d/1032 e/1033 f/1034 g/1035 h/1036 i/1037
j/1038 k/1039 l/1040 m/1041 n/1042 o/1043 x/1044
(if (!= x/1044 0)
(apply* camlTest__foo_1027 (+ a/1029 1) (+ b/1030 2)
(+ c/1031 3) (+ d/1032 4) (+ e/1033 5) (+ f/1034 6)
(+ g/1035 7) (+ h/1036 8) (+ i/1037 9) (+ j/1038 10)
(+ k/1039 11) (+ l/1040 12) (+ m/1041 13) (+ n/1042 14)
(+ o/1043 15) (- x/1044 1))
a/1029)) )
bar/1028 (makeblock 0 foo/1027 0a))
(seq (setfield_imm 0 (global camlTest!) foo/1027)
(setfield_imm 1 (global camlTest!) bar/1028)))

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

$ ./b.out
10000002

@vicuna
Copy link
Author

vicuna commented Jun 5, 2014

Comment author: @xavierleroy

I reviewed the patch, which is fine. Green light for inclusion in 4.02 and trunk. Not being familiar with the procedure to merge a Git request in our SVN, I'll let someone else do it.

@vicuna
Copy link
Author

vicuna commented Jun 5, 2014

Comment author: @gasche

I'll merge this.

The procedure is very simple:
https://github.com/ocaml/ocaml/pull/66.patch
(note it's exactly .path) contains a patch for the commits being submitted (the beginning being the commit message), and from then "patch -pN < ..." then "svn commit" will work.

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".

@vicuna vicuna closed this as completed Dec 11, 2015
@vicuna vicuna added this to the 4.02.0 milestone Mar 14, 2019
@vicuna vicuna added the bug label Mar 20, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

2 participants