Mantis Bug Tracker

View Issue Details Jump to Notes ] Issue History ] Print ]
IDProjectCategoryView StatusDate SubmittedLast Update
0006441OCamlOCaml backend (code generation)public2014-05-22 22:122014-06-05 18:01
Reporterstefanholdermans 
Assigned Togasche 
PrioritynormalSeveritymajorReproducibilityalways
StatusresolvedResolutionfixed 
PlatformOSOS Version
Product Version4.01.0 
Target Version4.02.0+devFixed in Version 
Summary0006441: Failure to detect obvious tail call
DescriptionConsider 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 InformationThis 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.
Tagspatch
Attached Files? file icon test.ml [^] (367 bytes) 2014-05-22 22:12 [Show Content]

- Relationships

-  Notes
(0011556)
stefanholdermans (reporter)
2014-05-22 22:40

A pull request for a fix (accompanied by a regression test) was submitted: https://github.com/ocaml/ocaml/pull/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
(0011681)
xleroy (administrator)
2014-06-05 16:45

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.
(0011686)
gasche (developer)
2014-06-05 18:01

I'll merge this.

The procedure is very simple:
  https://github.com/ocaml/ocaml/pull/66.patch [^]
(note it's exactly <URL>.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".

- Issue History
Date Modified Username Field Change
2014-05-22 22:12 stefanholdermans New Issue
2014-05-22 22:12 stefanholdermans File Added: test.ml
2014-05-22 22:40 stefanholdermans Note Added: 0011556
2014-05-23 14:17 doligez Target Version => 4.02.0+dev
2014-05-23 14:17 doligez Tag Attached: patch
2014-05-30 11:10 shinwell Assigned To => xleroy
2014-05-30 11:10 shinwell Status new => acknowledged
2014-06-05 16:45 xleroy Note Added: 0011681
2014-06-05 16:45 xleroy Assigned To xleroy =>
2014-06-05 16:45 xleroy Status acknowledged => confirmed
2014-06-05 18:01 gasche Note Added: 0011686
2014-06-05 18:01 gasche Status confirmed => resolved
2014-06-05 18:01 gasche Resolution open => fixed
2014-06-05 18:01 gasche Assigned To => gasche


Copyright © 2000 - 2011 MantisBT Group
Powered by Mantis Bugtracker