ghc: panic! (linkBCO: >= 64k ptrs)

[archgrove]

dict is a [String] with around 100,000 entries (around 1.4MB of data), exported from a module Dict. ghci will happily import this module, but any operations on this list (e.g. take 1 dict) fail with a ghc panic. I admit it's perhaps not the best idea to work with a list of this magnitude, but in this case a better error message would be useful.

GHCi, version 6.12.1: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Loading package ffi-1.0 ... linking ... done.
Prelude> :load Dict
[1 of 1] Compiling Dict             ( Dict.hs, interpreted )
Ok, modules loaded: Dict.
*Dict> take 1 dict
ghc: panic! (the 'impossible' happened)
  (GHC version 6.12.1 for i386-apple-darwin):
	linkBCO: >= 64k ptrs

Please report this as a GHC bug:  http://www.haskell.org/ghc/reportabug

[igloo]

This creates a suitable Dict.hs:

main :: IO ()
main = writeFile "Dict.hs" ("module Dict where\ndict = " ++ show strs)

strs :: [String]
strs = take 100000 xs

xs :: [String]
xs = "" : [ c : cs
          | cs <- xs,
            c <- ['a'..'z']]

and 1.2G of RAM later:

GHCi, version 6.13.20100211: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Loading package ffi-1.0 ... linking ... done.
[1 of 1] Compiling Dict             ( Dict.hs, interpreted )
Ok, modules loaded: Dict.
*Dict> take 1 dict
ghc-stage2: panic! (the 'impossible' happened)
  (GHC version 6.13.20100211 for x86_64-unknown-linux):
        linkBCO: >= 64k ptrs

Please report this as a GHC bug:  http://www.haskell.org/ghc/reportabug

*Dict> 
Leaving GHCi.
ghci Dict.hs  54.32s user 0.82s system 83% cpu 1:05.89 total

This ought to be quite straightforward to fix, as I think all the hard work was already done when fixing the >= 64k insns problem.

[gyppo]

Similar situation here, this time working with a large (>500kB) list of primes saved to a .hs file.

Output: *Main> let no_even_digits p = all odd (digify p) Loading package array-0.3.0.0 ... linking ... done. Loading package bytestring-0.9.1.5 ... linking ... done. Loading package Win32-2.2.0.1 ... linking ... done. Loading package filepath-1.1.0.3 ... linking ... done. Loading package old-locale-1.0.0.2 ... linking ... done. Loading package old-time-1.0.0.3 ... linking ... done. Loading package directory-1.0.1.0 ... linking ... done. Loading package process-1.0.1.2 ... linking ... done. Loading package time-1.1.4 ... linking ... done. Loading package random-1.0.0.2 ... linking ... done. Loading package haskell98 ... linking ... done. : panic! (the 'impossible' happened)

(GHC version 6.12.1 for i386-unknown-mingw32):

linkBCO: >= 64k ptrs

Please report this as a GHC bug: http://www.haskell.org/ghc/reportabug

---

where: rint c = read c :: Integer digify n = map (rint.(:[])) (show n)

are defined in the .hs file alongside the list of primes.

[gyppo]

Clarification: GHCi, version 6.12.1: http://www.haskell.org/ghc/ :? for help Loading package ghc-prim ... linking ... done. Loading package integer-gmp ... linking ... done. Loading package base ... linking ... done. Loading package ffi-1.0 ... linking ... done. [1 of 1] Compiling Main ( C:\Users\Sam\Documents\Programming\Haskell \primes.hs, interpreted ) Ok, modules loaded: Main.

Works fine. Then: *Main> 1+1 2

Also fine. But if I attempt to use any of the functions in primes.hs (which worked prior to the copy-pasted huge list of primes) I get something similar to

*Main> is_prime 7
Loading package array-0.3.0.0 ... linking ... done.
Loading package bytestring-0.9.1.5 ... linking ... done.
Loading package Win32-2.2.0.1 ... linking ... done.
Loading package filepath-1.1.0.3 ... linking ... done.
Loading package old-locale-1.0.0.2 ... linking ... done.
Loading package old-time-1.0.0.3 ... linking ... done.
Loading package directory-1.0.1.0 ... linking ... done.
Loading package process-1.0.1.2 ... linking ... done.
Loading package time-1.1.4 ... linking ... done.
Loading package random-1.0.0.2 ... linking ... done.
Loading package haskell98 ... linking ... done.
: panic! (the 'impossible' happened)
  (GHC version 6.12.1 for i386-unknown-mingw32):
        linkBCO: >= 64k ptrs

Please report this as a GHC bug:  http://www.haskell.org/ghc/reportabug

The list doesn't have to be referred, any reference to anything included in the file throws this error.

[igloo]

See also #5479

[igloo]

Punting

[pcapriotti]

There are two problems here:

1) The 16-bit counter used to keep track of stack depth during bytecode generation can wrap around and generate bogus instructions.

2) Pointers and literals are addressed by 16-bit operands, so there can't be more than 2¹⁶ of each.

The attached patch series fixes both issues. Please check the commit messages for more details.

[simonmar]

The patches look ok. It might be an idea to do a spot check on compile-time and run-time performance and make sure nothing has gone wrong.

[pcapriotti]

I run a couple of tests on some code in nofib. There were no significant differences, and in one case I actually got better timings after the patch.

Here's one of the tests:

nofib/imaginary/test.script:

:set args 8
:l ./bernouilli/Main.hs
main
:l ./integrate/Main.hs
main
:l ./primes/Main.hs
main
:l ./queens/Main.hs
main
:l ./x2n1/Main.hs
main
:l ./paraffins/Main.hs
main
:l ./wheel-sieve1/Main.hs
main
:l ./tak/Main.hs
main
:l ./rfib/Main.hs
main
:l ./exp3_8/Main.hs
main
:l ./wheel-sieve2/Main.hs
main

before patch:

real    0m7.058s
user    0m6.996s
sys     0m0.036s

after patch:

real    0m6.844s
user    0m6.808s
sys     0m0.016s

[simonmar]

Ok, looks like we're good to go ahead with this patch then.

[pcapriotti]

Pushed:

commit 6ba8b3309709fa1ad43382e23792b1c4a624d7ad
Author: Paolo Capriotti <p.capriotti@gmail.com>
Date:   Mon Apr 16 19:46:26 2012 +0100

    Fix operand expansion function.

commit d5ec2967b0662e46b495d4bfeed90ec2a4b02e97
Author: Paolo Capriotti <p.capriotti@gmail.com>
Date:   Thu Apr 5 18:42:37 2012 +0100

    Implemented word-sized addressing of pointers and literals.

commit f8d48821a819604e21ba0794e8794f76ed21c758
Author: Paolo Capriotti <p.capriotti@gmail.com>
Date:   Thu Apr 5 18:09:40 2012 +0100

    Bytecode assembler refactoring.
    
    Use a free monad to specify the assembling procedure, so that it can be
    run multiple times without producing side effects.
    
    This paves the way for a more general implementation of variable-sized
    instructions, since we need to dry-run the bytecode assembler to
    determine the size of the operands for some instructions.

commit e408f4f507d2cfb302a7f5a7f502336672b57107
Author: Paolo Capriotti <p.capriotti@gmail.com>
Date:   Thu Apr 5 16:45:21 2012 +0100

    Export State monad transformer from ByteCodeItbls.

commit 6dc22bfa9d0026c09abf94e44f04fb9e761d4e54
Author: Paolo Capriotti <p.capriotti@gmail.com>
Date:   Thu Apr 5 09:52:18 2012 +0100

    Support large SLIDE instructions.
    
    The bytecode generator used to keep track of the stack depth with a
    16-bit counter, which could overflow for very large BCOs, resulting in
    incorrect bytecode.
    
    This commit switches to a word-sized counter, and eagerly panics
    whenever an operand is too big, instead of truncating the result.
    
    This allows us to work around the 16-bit limitation in the case of SLIDE
    instructions, since we can simply factor it into multiple SLIDEs with
    smaller arguments.