#5539: GHC panic - Simplifier ticks exhausted
---------------------------------+------------------------------------------
Reporter: hvr | Owner: simonpj
Type: bug | Status: new
Priority: high | Milestone: 7.4.1
Component: Compiler | Version: 7.3
Resolution: | Keywords:
Os: Linux | Architecture: x86_64 (amd64)
Failure: Compile-time crash | Difficulty: Unknown
Testcase: | Blockedby:
Blocking: | Related:
---------------------------------+------------------------------------------
Changes (by simonpj):
* cc: rl (added)
Comment:
I have gotten as far as compiling `vector-algorithms`, and indeed I get
{{{
[8 of 9] Compiling Data.Vector.Algorithms.Intro (
Data/Vector/Algorithms/Intro.hs, dist/build/Data/Vector/Algorithms/Intro.o
)
ghc: panic! (the 'impossible' happened)
(GHC version 7.3.20111030 for x86_64-unknown-linux):
Simplifier ticks exhausted
When trying UnfoldingDone ghc-prim:GHC.Classes.not{v r1d} [gid]
To increase the limit, use -fsimpl-tick-factor=N (default 100)
If you need to do this, let GHC HQ know, and what factor you needed
To see detailed counts use -ddump-simpl-stats
Total ticks: 42922
}}}
So what is going on? To take one example, there's a call of
`Data.Vector.Algorithms.Optimal.sort3ByIndex`, and that inlines a giant
function. Why giant? Well, `sort3ByIndex` has three calls of
{{{
UNSAFE_CHECK(checkIndex) "sort3ByIndex" i (length a)
}}}
Moreover, `sort3ByIndex` calls the INLINE function
`Data.Vector.Generic.Mutable.unsafeRead` 3 times, and `unsafeWrite` 12
times. Each of those functions has another use of `UNSAFE_CHECK`. This
UNSAFE_CHECK thing is a CPP macro which expands thus
{{{
UNSAFE_CHECK(checkIndex) "sort3ByIndex" i (length a) x
--> (by cpp)
checkIndex "Foo.hs" 45 Unsafe "sort3ByIndex" i (length a) x
--> (INLINE checkIndex)
let n = length a in
check "Foo.hs" 45 Unsafe "sort3ByIndex" (checkIndex_msg i n) (i >= 0 && i
< n) x
--> (INLINE check)
let n = length a in
if (not (doChecks Unsafe) || (i >= 0 && i < n))
then x
else error "Foo.hs" 45 Unsafe "sort3ByIndex" (checkIndex_msg i n)
}}}
Now imagine all of that inlined 18 times, and you get a lot of code. And
that's only `sort3ByIndex`, which itself has an INLINE pragma.
Let's just focus on the number of calls to `(||)`. In the module
`Intro.hs`:
* `sortByBounds` calls `sort2ByOffset`, `sort3ByOffset`, and
`sort4ByOffset` (and `introsort` which I'll temporarily ignore)
* Those three calls are inlined, resulting in 110 calls to `(||)`.
* But `sortByBounds` is itself an INLINE function, and is inlined into
`sortBy`; result = 110 more calls to `(||)`.
* And `sortBy` is INLINE, and is inlined into `sort`, giving another 110
calls; total so far 330 calls.
* Along with those 330 calls to `(||)` are 330 calls to `not`. All those
are finally inlined independently and simplified away, but it uses up
ticks!
* Moreover all these `sort3ByIndex` functions work in an arbitrary monad,
so it's all stitched together will calls to the overloaded `(>>)` and
dictionary-passing.
And I did all this measurement with `Intro.introsort` commented out; it
does more crazy stuff. I think this is why the code is so bloated.
Now, in fact `vector` is compiled in such a way that `(doChecks Unsafe)`
evaluates to `False`. So in the bloated unfolding for `UNSAFE_CHECK` we
see this:
{{{
let n = length a in
case (not False || (i >= 0 && i < n)) of
True -> a
False -> error "Foo.hs" 45 Unsafe "sort3ByIndex" (checkIndex_msg i n)
}}}
Look at that `(not False)`! If GHC had been clever enough to inline `not`
and `||` in the unfolding of `sort3ByIndex`, all this code would have
collapsed away as dead code -- and indeed it does so in the eventual
client module.
It's hard for GHC to know how clever to be.
* The basic idea of an INLINE pragma on a definition `f x = <expr>`, then
we'll inline precisely `<expr>` at every call site. GHC is faithfully
doing this.
* However GHC does ''some'' gentle simplification on `<expr>` before
stowing it away ready for inlining:
* It does simple case-of-constructor stuff
* It inlines functions that are themselves marked INLINE, or calls that
use the `inline` pseudo-function.
The current defn of `Data.Vector.Internal.check` is
{{{
check file line kind loc msg cond x
| not (doChecks kind) || cond = x
| otherwise = error file line kind loc msg
}}}
Here are two ways of making the `not` and `(||)` inline even inside
`check`'s inlining. First, do it by hand:
{{{
check file line kind loc msg cond x
= case doChecks kind of
False -> x
True | cond -> x
| otherwise -> error file line kind loc msg
}}}
Second, use `inline`:
{{{
check file line kind loc msg cond x
| inline (||) (inline not (doChecks kind)) cond = x
| otherwise = error file line kind loc msg
}}}
Then the size of `Intro` is more reasonable, and compiles within the
current tick bounds without problem.
I have taken the trouble to write this up so that everyone gets a clearer
idea of how inlining works.
I will make the above change to `check` in package `vector` (at least in
GHC's tree). '''BUT if you change the macros so that full bounds-checking
is on, all the bloat will return'''. So that really needs attention from
Roman. For example, when bounds checking is on, the indexing fuctions
should probably not inline.
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/5539#comment:28>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler
_______________________________________________
Glasgow-haskell-bugs mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
