You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
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.
$ 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]
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.
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.
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".
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
The text was updated successfully, but these errors were encountered: