fibc hangs when compiled with -O3 or -O4

[Mario Domenech Goulart]

The program below hangs eating CPU when compiled with -O3 or -O4:

(define (addc x y k)
  (if (zero? y)
    (k x)
    (addc (add1 x) (sub1 y) k)))

(define (fibc x c)
  (if (zero? x)
    (c 0)
    (if (zero? (sub1 x))
      (c 1)
      (addc (call-with-current-continuation (lambda (c) (fibc (sub1 x) c)))
            (call-with-current-continuation (lambda (c) (fibc (sub1 (sub1 x)) c)))
            c))))

(let ((x (time (fibc 30 (lambda (n) n)))))
  (if (not (equal? x 832040))
      (error "wrong result" x) ) )

$ csc fibc.scm 
$ ./fibc 
0.412s CPU time, 12/4237 GCs (major/minor)

$ csc -O3 fibc.scm 
$ ./fibc 
<hangs>

Also hangs when compiled with -O4. It works as expected (i.e., doesn't hang) when compiled with -O5.

I could reproduce this behavior with 4.11.0 and master (as of 724f6866b). I could not reproduce the problem with 4.10.0, so the bug has been introduced at some point between 4.10.0 and 4.11.0. The issue doesn't seem to be related to the C compiler. I could reproduce it with GCC 4.9.2, GCC 6.1.1 and clang 3.6.2.

This issue was caught while trying csc options for ​chicken-benchmarks (fibc is one of the benchmark programs).

[sjamaan]

It looks like the whole call-cc stuff is just a red herring. The following simplified version fails in the same way

(define (add x y)
  (if (zero? y)
      x
      (add (add1 x) (sub1 y))))

(define (fib x)
  (if (or (= x 0) (= x 1))
      x
      (add (fib (sub1 x))
           (fib (sub1 (sub1 x))))))

(print (fib 30))

[sjamaan]

Looks like there's a problem with the way we restart the continuation (or something?):

(foreign-declare
 "C_word print2(C_word x, C_word y) {\n"
 "  printf(\"add %ld + %ld\\n\", C_unfix(x), C_unfix(y)); "
 "  return C_SCHEME_FALSE;"
 "}\n")

(foreign-declare
 "C_word print1(C_word x) {\n"
 "  printf(\"fibc %ld\\n\", C_unfix(x)); "
 "  return C_SCHEME_FALSE;"
 "}\n")

(define (add x y)
  (##core#inline "print2" x y)
  (if (zero? y)
      x
      (add (add1 x) (sub1 y))))

(define (fib x)
  (##core#inline "print1" x)
  (if (or (= x 0) (= x 1))
      x
      (add (fib (- x 1))
           (fib (- x 2)))))

(print (fib 30))

When running this with -O2 versus -O3, I get a diff that looks like this:

--- working     2016-09-17 21:00:42.183955883 +0200
+++ broken 2016-09-17 21:10:51.879932979 +0200
@@ -6423,6 +6423,7 @@
 fibc 0
 add 1 + 0
 add 2 + 1
+add 2 + 1
 add 3 + 0
 add 5 + 3
 add 6 + 2
@@ -8200,6 +8201,14 @@
 add 94 + 50
 add 95 + 49
 add 96 + 48
+add 89 + 55
+add 90 + 54
+add 91 + 53
+add 92 + 52
+add 93 + 51
+add 94 + 50
+add 95 + 49
+add 96 + 48
 add 97 + 47
 add 98 + 46
 add 99 + 45
@@ -13708,6 +13717,23 @@
 add 158 + 75
 add 159 + 74
 add 160 + 73
+add 144 + 89
+add 145 + 88
+add 146 + 87
+add 147 + 86
+add 148 + 85
+add 149 + 84
+add 150 + 83
+add 151 + 82
+add 152 + 81
+add 153 + 80
+add 154 + 79
+add 155 + 78
+add 156 + 77
+add 157 + 76
+add 158 + 75
+add 159 + 74
+add 160 + 73
 add 161 + 72
 add 162 + 71
 add 163 + 70
@@ -19312,6 +19338,9 @@
 fibc 4
 fibc 3
 fibc 2
+fibc 4
+fibc 3
+fibc 2
 fibc 1
 fibc 0
 add 1 + 0
@@ -21163,6 +21192,9 @@
 fibc 4
 fibc 3
 fibc 2
+fibc 4
+fibc 3
+fibc 2
 fibc 1
 fibc 0
 add 1 + 0
@@ -25423,6 +25455,12 @@
 add 37 + 18
 add 38 + 17
 add 39 + 16
+add 34 + 21
+add 35 + 20
+add 36 + 19
+add 37 + 18
+add 38 + 17
+add 39 + 16
 add 40 + 15
 add 41 + 14
 add 42 + 13
@@ -30755,6 +30793,7 @@
 add 1 + 1
 add 2 + 0
 fibc 2
+fibc 2
 fibc 1
 fibc 0
 add 1 + 0
@@ -36066,6 +36105,25 @@
 add 50 + 5
 add 51 + 4
 add 52 + 3
+add 34 + 21
+add 35 + 20
+add 36 + 19
+add 37 + 18
+add 38 + 17
+add 39 + 16
+add 40 + 15
+add 41 + 14
+add 42 + 13
+add 43 + 12
+add 44 + 11
+add 45 + 10
+add 46 + 9
+add 47 + 8
+add 48 + 7
+add 49 + 6
+add 50 + 5
+add 51 + 4
+add 52 + 3
 add 53 + 2
 add 54 + 1
 add 55 + 0
@@ -43958,6 +44016,14 @@
 add 26 + 8
 add 27 + 7
 add 28 + 6
+add 21 + 13
+add 22 + 12
+add 23 + 11
+add 24 + 10
+add 25 + 9
+add 26 + 8
+add 27 + 7
+add 28 + 6
 add 29 + 5
 add 30 + 4
 add 31 + 3
@@ -58712,6 +58778,11 @@
 add 15 + 6
 add 16 + 5
 add 17 + 4
+add 13 + 8
+add 14 + 7
+add 15 + 6
+add 16 + 5
+add 17 + 4
 add 18 + 3
 add 19 + 2
 add 20 + 1
@@ -65949,6 +66020,1961 @@
 add 5178 + 1587
 add 5179 + 1586
 add 5180 + 1585
+add 4181 + 2584
+add 4182 + 2583
+add 4183 + 2582
+add 4184 + 2581
+add 4185 + 2580
+add 4186 + 2579
+add 4187 + 2578
+add 4188 + 2577
+add 4189 + 2576
+add 4190 + 2575
+add 4191 + 2574
+add 4192 + 2573
+add 4193 + 2572
+add 4194 + 2571

And so forth....

[evhan]

Fixed by 73b7b3d and eefcc20.