#2684: Stack overflow in stream-fusion library with GHC 6.10 RC
------------------------------+---------------------------------------------
Reporter: dons | Owner:
Type: bug | Status: new
Priority: high | Milestone: 6.10.1
Component: Compiler | Version: 6.9
Severity: major | Resolution:
Keywords: | Difficulty: Unknown
Testcase: | Architecture: Unknown/Multiple
Os: Unknown/Multiple |
------------------------------+---------------------------------------------
Comment (by simonpj):
I know more or less what is happening now. Here's the diagnosis.
Stream.2.hs contains this:
{{{
mapx f (x:xs) = f x : mapx f xs
{-# NOINLINE [1] mapx #-}
{-# RULES
"mapx -> fusible" [~1] forall f xs.
mapx f xs = unstream (mapy f (stream xs))
"mapx -> unfused" [1] forall f xs.
unstream (mapy f (stream xs)) = mapx f xs
#-}
}}}
(Note that the second of these rules is an orphan.)
After applying the `fusible` rule, at the end of Phase 1 GHC sees
{{{
mapx f (x:xs) = f x : unstream (mapy f (stream xs))
}}}
Now `mapx` looks non-recursive; after all, `mapy` is imported. So when
the occurrence analyser runs in Phase 0 `mapx` is not marked as a loop
breaker and can be inlined freely. However the `unfused` rule fires, and
makes `mapx` recursive after all. Before the occurrence analyser runs
again, though, the simplifier processes the next definition:
{{{
initsx (x:xs) = [] : mapx (x:) (initsx xs)
}}}
Since `mapx` is not a loop breaker, it's just inlined repeatedly; result
infinite loop.
You may say that the occurrence analyser should be run again ''after''
finishing each definition. But that is only sticking plaster. Suppose we
had
{{{
mapx x = mapy x
}}}
(non-recursive, no rules) and imported that into a scope where there was
an orphan rule
{{{
RULES "x" mapy = mapx
}}}
Then you can see that would make GHC loop. (Inline `mapx`, run the RULE,
and repeat.)
What to do? In general it's very hard to do much about RULES that give
rise to loops, esp when they are orphans. When they are defined in the
same module as the function they are RULES for, GHC is pretty good; but
otherwise it's difficult.
In this case the obvious thing is to add
{{{
{-# NOINLINE [~1] mapx #-}
}}}
to stop it being inlined after Phase 1. That should cure the loop, but
I'm not sure if the optimisations you have in mind would still work.
(Curiously the exact inverse annotation is provided in the test case,
saying don't inline ''until'' Phase 1.)
I'm surprised 6.8.3 works on this example; I suspect it's a fluke.
(Should check this.)
Bottom line: I can't see a quick fix. Need to discuss how important this
pattern is. At least we know what the problem is.
Simon
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/2684#comment:3>
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
