Summary

fibc hangs when compiled with -O3 or -O4

Metadata

Description

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

Changes and comments

[2016-08-25 20:46:30 UTC] sjamaan set difficulty to hard

[2016-09-17 20:43:28 UTC] sjamaan wrote:

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

 #!scm
 (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))

[2016-09-17 21:17:42 UTC] sjamaan wrote:

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

 #!scm
 (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....

[2016-09-26 11:03:31 UTC] evhan changed status from new to closed

[2016-09-26 11:03:31 UTC] evhan set resolution to fixed

[2016-09-26 11:03:31 UTC] evhan wrote:

Fixed by 73b7b3d and eefcc20.