Heap overflow in optimizer
Compiling the following with optimisations:
module Test where
import Data.Bits (setBit)
f = foldl setBit 0 [x | (x,_) <- zip [0..] [1]] :: Integer
fails with:
$ ghc -O0 -fforce-recomp Test.hs
[1 of 1] Compiling Test ( Test.hs, Test.o )
$ ghc -O -fforce-recomp Test.hs
[1 of 1] Compiling Test ( Test.hs, Test.o )
ghc: panic! (the 'impossible' happened)
(GHC version 8.4.1 for x86_64-unknown-linux):
heap overflow
Fails on 8.0.2, 8.2.2, and 8.4.1
Trac metadata
Trac field | Value |
---|---|
Version | 8.4.1 |
Type | Bug |
TypeOfFailure | OtherFailure |
Priority | normal |
Resolution | Unresolved |
Component | Compiler |
Test case | |
Differential revisions | |
BlockedBy | |
Related | |
Blocking | |
CC | |
Operating system | |
Architecture |
- Show closed items
Relates to
- #156738.8.15
Activity
-
Newest first Oldest first
-
Show all activity Show comments only Show history only
- darchon changed weight to 5
changed weight to 5
- darchon added Tbug Trac import labels
added Tbug Trac import labels
- Ryan Scott changed title from Heep overflow in optimizer to Heap overflow in optimizer
changed title from Heep overflow in optimizer to Heap overflow in optimizer
- Maintainer
Stunning. This bug goes all the way back to GHC 8.0.1, even (note that before 8.4.1, you would simply get the error message
ghc: Out of memory
instead of a panic). GHC 7.10.3 does not suffer from this issue. - Author
Some notes which I forgot to mention:
- Result need to be
Integer
, no heap overflow onInt
orWord
- The folded computation needs to be
setBit
, no heap overflow on+
ordiv
- The
[0..]
needs to be the first argument ofzip
, no heap overflow onzip [1] [0..]
- Result need to be
- Maintainer
The
-ddump-rule-rewrites
output for this program is rather interesting:$ ghc -O -fforce-recomp -ddump-rule-rewrites Bug.hs [1 of 1] Compiling Test ( Bug.hs, Bug.o ) <elided> Rule fired Rule: ==# Module: (BUILTIN) Before: GHC.Prim.==# ValArg x_a2Lu ValArg 9223372036854775807# After: case x_a2Lu of wild_00 { __DEFAULT -> 0#; 9223372036854775807# -> 1# } Cont: StrictArg GHC.Prim.tagToEnum# Select nodup wild1_a2Lw Stop[RhsCtxt] [GHC.Integer.Type.Integer] -> GHC.Integer.Type.Integer -> GHC.Integer.Type.Integer Rule fired Rule: tagToEnum# Module: (BUILTIN) Before: GHC.Prim.tagToEnum# TyArg GHC.Types.Bool ValArg 0# After: GHC.Types.False Cont: Select ok wild1_a2Lw Stop[BoringCtxt] [GHC.Integer.Type.Integer] -> GHC.Integer.Type.Integer -> GHC.Integer.Type.Integer Rule fired Rule: tagToEnum# Module: (BUILTIN) Before: GHC.Prim.tagToEnum# TyArg GHC.Types.Bool ValArg 1# After: GHC.Types.True Cont: Select ok wild1_a2Lw Stop[BoringCtxt] [GHC.Integer.Type.Integer] -> GHC.Integer.Type.Integer -> GHC.Integer.Type.Integer Rule fired Rule: bitInteger Module: (BUILTIN) Before:ghc: Out of memory
- Author
Incidentally, the
bitInteger
rule was updated/changed/added in 8.0.1 according to: - Matthew Pickering mentioned in issue #14962 (closed)
mentioned in issue #14962 (closed)
- Developer
See also dup report #14962 (closed)
- Simon Peyton Jones mentioned in commit efc844f5
mentioned in commit efc844f5
- Developer
I see this code in Core
go_a2Rl = \ (x_a2Rm :: GHC.Prim.Int#) (eta_B1 :: [Integer]) (eta_X2 :: Integer) -> case eta_B1 of { [] -> eta_X2; : y_a2SA ys_a2SB -> let { eta_Xn :: Integer eta_Xn = GHC.Integer.Type.orInteger eta_X2 (GHC.Integer.Type.bitInteger x_a2Rm) } in case x_a2Rm of wild_XL { __DEFAULT -> go_a2Rl (GHC.Prim.+# wild_XL 1#) ys_a2SB eta_Xn; 9223372036854775807# -> eta_Xn } }
If we inline
eta_Xn
(which is only used once) we get...(case x_a2Rm of wild_XL { __DEFAULT -> ... 9223372036854775807# -> GHC.Integer.Type.orInteger eta_X2 (GHC.Integer.Type.bitInteger x_a2Rm) )...
Now GHC sees that in the branch of the case it knows that
x = 9223372036854775807#
. So it tries to do constant folding. But the result is a rather big Integer:Prelude Data.Bits GHC.Exts> bit (I# 3#) :: Integer 8 Prelude Data.Bits GHC.Exts> bit (I# 4#) :: Integer 16 Prelude Data.Bits GHC.Exts> bit (I# 20#) :: Integer 1048576 Prelude Data.Bits GHC.Exts> bit (I# 60#) :: Integer 1152921504606846976 Prelude Data.Bits GHC.Exts> bit (I# 200#) :: Integer 1606938044258990275541962092341162602522202993782792835301376
I'll leave you to imagine how big
bit 9223372036854775807#
is.Solution: the
bitInteger
rule should only work if its argument is "small enough". I suggest that "small enough" means "smaller than wordSizeInBits", ie x<64 on a 64 bit machine.I'm validating a patch.
- Developer
Trac metadata
Trac field Value Test case - → simplCore/should_compile/T14959 - Simon Peyton Jones added 1 deleted label
added 1 deleted label
- Ben Gamari closed
closed
- Ben Gamari changed milestone to %8.4.2
changed milestone to %8.4.2
- Maintainer
Merged to
ghc-8.4
.Trac metadata
Trac field Value Resolution Unresolved → ResolvedFixed - Ben Gamari removed 1 deleted label
removed 1 deleted label
- mcmayer mentioned in issue #15673 (closed)
mentioned in issue #15673 (closed)
- Ben Gamari added Pnormal label
added Pnormal label