#2607: Inlining defeats selector thunk optimisation
---------------------------------+------------------------------------------
Reporter: simonmar | Owner:
Type: bug | Status: new
Priority: normal | Milestone: _|_
Component: Compiler | Version: 6.8.3
Keywords: | Testcase:
Blockedby: | Difficulty: Unknown
Os: Unknown/Multiple | Blocking:
Architecture: Unknown/Multiple | Failure: None/Unknown
---------------------------------+------------------------------------------
Comment(by simonpj):
The way GHC's current mechanisms fail is this. We start thus:
{{{
p = e
x = case p of (a,_) -> a
y = case p of (_,b) -> b
z = case x of
[] -> []
(t:ts) -> foo ts
}}}
The bindings for `x` and `y` look like selector thunks, and GHC's RTS does
the Wadler-thing on them. But what happens is that x only occurs once so
the optimiser inlines it in z (we assume there are other uses of 'y')
{{{
p = e
y = case p of (_,b) -> b
z = case p of
(a,_) -> case a of
[] -> []
(t:ts) -> foo ts
}}}
Now z doesn't look like a selector thunk any more.
One "solution" might be to restrict the optimiser, but what if the above
"optimised" program was exactly what the programmer wrote. Then it'd have
a space leak. Or what if the optimiser's inlining led to a useful cascade
of transformations that eliminated the leak some other way?
I had an idea on my bicycle this morning. In the code for 'z' we see the
pattern
{{{
z = ...(case p72 of (a, _) -> e)...
}}}
Assuming `p72` is in scope at the z-binding, we can immediately see that
we are picking just a little part of `p72`, and that is a leaky thing to
do. So
we could transform to
{{{
z = ...(e)...
a = case p72 of (a, _) -> a
}}}
thereby precisely reversing what went wrong, and making a thunk for 'a'
that fits what GHC thinks of as a selector thunk.
So that's the idea. Very late in the compiler (something like at STG
level, or just before), identify any case expression that:
* Scutinises a variable
* The variable is in scope at an enclosing let-binding, without passing
any intervening lambdas
* Has exactly one alternative (ie it's a product type)
* Has some dead binders in the pattern
In that case, float the case as above.
Simon
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/2607#comment:5>
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
