Re: [GHC] #7360: Case-of-identical-alts optimisation fails abjectly
#7360: Case-of-identical-alts optimisation fails abjectly
-+--
Reporter: simonpj | Owner:
Type: bug | Status: new
Priority: normal| Milestone:
Component: Compiler | Version: 7.6.1
Keywords:| Os: Unknown/Multiple
Architecture: Unknown/Multiple | Failure: None/Unknown
Difficulty: Unknown |Testcase:
Blockedby:|Blocking:
Related:|
-+--
Comment(by simonpj@…):
commit bacf7ca075498aed745f68448f7e2b8d15c39541
{{{
Author: Simon Peyton Jones simo...@microsoft.com
Date: Mon Dec 24 13:25:12 2012 +
Make combine-identical-alternatives work again (Trac #7360)
Move the combine indentical alternatives transformation *before*
simplifying the alternatives. For example
case x of y
[] - length y
(_:_) - length y }
If we look *post* simplification, since 'y' is used in the
alterantives, the case binders *might* be (see the keep_occ_info test
in Simplify.simplAlt); and hence the combination of the two
alteranatives does not happen. But if we do it *pre* simplification
there is no problem.
This fixes Trac #7360.
compiler/simplCore/SimplUtils.lhs | 127
-
1 files changed, 68 insertions(+), 59 deletions(-)
}}}
--
Ticket URL: http://hackage.haskell.org/trac/ghc/ticket/7360#comment:5
GHC http://www.haskell.org/ghc/
The Glasgow Haskell Compiler
___
Glasgow-haskell-bugs mailing list
Glasgow-haskell-bugs@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
Re: [GHC] #7360: Case-of-identical-alts optimisation fails abjectly
#7360: Case-of-identical-alts optimisation fails abjectly -+-- Reporter: simonpj | Owner: Type: bug | Status: closed Priority: normal | Milestone: Component: Compiler|Version: 7.6.1 Resolution: fixed | Keywords: Os: Unknown/Multiple| Architecture: Unknown/Multiple Failure: None/Unknown| Difficulty: Unknown Testcase: simplCore/should_compile/T7360 | Blockedby: Blocking: |Related: -+-- Changes (by simonpj): * status: new = closed * testcase: = simplCore/should_compile/T7360 * resolution: = fixed -- Ticket URL: http://hackage.haskell.org/trac/ghc/ticket/7360#comment:6 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler ___ Glasgow-haskell-bugs mailing list Glasgow-haskell-bugs@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
Re: [GHC] #7360: Case-of-identical-alts optimisation fails abjectly
#7360: Case-of-identical-alts optimisation fails abjectly -+-- Reporter: simonpj | Owner: Type: bug | Status: new Priority: normal| Milestone: Component: Compiler | Version: 7.6.1 Keywords:| Os: Unknown/Multiple Architecture: Unknown/Multiple | Failure: None/Unknown Difficulty: Unknown |Testcase: Blockedby:|Blocking: Related:| -+-- Comment(by simonpj): See also #7378 -- Ticket URL: http://hackage.haskell.org/trac/ghc/ticket/7360#comment:4 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler ___ Glasgow-haskell-bugs mailing list Glasgow-haskell-bugs@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
Re: [GHC] #7360: Case-of-identical-alts optimisation fails abjectly
#7360: Case-of-identical-alts optimisation fails abjectly
-+--
Reporter: simonpj | Owner:
Type: bug | Status: new
Priority: normal| Milestone:
Component: Compiler | Version: 7.6.1
Keywords:| Os: Unknown/Multiple
Architecture: Unknown/Multiple | Failure: None/Unknown
Difficulty: Unknown |Testcase:
Blockedby:|Blocking:
Related:|
-+--
Comment(by simonpj):
I'm afraid I don't but let me try here to explain the issues, and you can
have a go yourself.
To implement my comment above, here are the changes I have in mind:
* Remove the 'scrut' arg to `simplAlt` and `addBinderUnfolding`; simplify
the latter by eliminating the `(Just v)` alternative.
* Remove the call to `(isNothing scrut`) around line 2072 of
`Simplify.lhs`
Then you want to check that things are better. In particular I'd like
to be confident that we have not thereby increased the number of
simplifier iterations, or (worse still) claiming that something is
dead when it isn't.
So it would be good to run a nofib performance test before and after,
with -dcore-lint. That mainly checks runtime performance and
allocation. Adding `-ddump-simpl-stats` and looking for the
`SimplifierDone` figure tells you the number of simplifier iterations,
which should not increase. We don't have an automated way to check that.
Even this isn't ideal. If we have
{{{
case x of y {
[] - length y
(_:_) - length y }
}}}
we won't combine the alteratives because `y` is alive in the alternatives.
(See teh (necessary) call to `(isDeadBinder case_bndr')` online 2072 of
`Simplify.lhs`. This is silly.
So the next thing I'd try is moving the `Merge Identical ALternatives`
code from `mkCase1` to `prepareAlts`. The latter happens ''before''
the alternatives are simplified, so it'd be fine to simply combine the
alternatives without messing with the occurrence info on the
alternative binders at all.
Again easy to try, but we'd want the same performance testing as
before. Would you like to try?
Simon
--
Ticket URL: http://hackage.haskell.org/trac/ghc/ticket/7360#comment:3
GHC http://www.haskell.org/ghc/
The Glasgow Haskell Compiler
___
Glasgow-haskell-bugs mailing list
Glasgow-haskell-bugs@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
Re: [GHC] #7360: Case-of-identical-alts optimisation fails abjectly
#7360: Case-of-identical-alts optimisation fails abjectly -+-- Reporter: simonpj | Owner: Type: bug | Status: new Priority: normal| Milestone: Component: Compiler | Version: 7.6.1 Keywords:| Os: Unknown/Multiple Architecture: Unknown/Multiple | Failure: None/Unknown Difficulty: Unknown |Testcase: Blockedby:|Blocking: Related:| -+-- Comment(by hvr): I need enough time to do some comparative nofib runs to make sure I hvae not messed up, though. Do you happen to have a patch ready I could test/play-with? Is there anything I can do to help? -- Ticket URL: http://hackage.haskell.org/trac/ghc/ticket/7360#comment:2 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler ___ Glasgow-haskell-bugs mailing list Glasgow-haskell-bugs@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
[GHC] #7360: Case-of-identical-alts optimisation fails abjectly
#7360: Case-of-identical-alts optimisation fails abjectly
-+--
Reporter: simonpj | Owner:
Type: bug | Status: new
Priority: normal| Milestone:
Component: Compiler | Version: 7.6.1
Keywords:| Os: Unknown/Multiple
Architecture: Unknown/Multiple | Failure: None/Unknown
Difficulty: Unknown |Testcase:
Blockedby:|Blocking:
Related:|
-+--
Herbert Valerio Riedel writes: I've been trying to improve/fix a minor
optimization sub-optimality w.r.t to the following code (code like that
results from the generics-based NFData deriver[1]):
{{{
data Foo = Foo1 | Foo2 | Foo3 !Int
rnf1 :: Foo - ()
rnf1 x = case x of
Foo1 - ()
Foo2 - ()
Foo3 {} - ()
}}}
which the current GHC 7.6.1 translates to the following core
expression:
{{{
NFDataTest2.rnf1 =
\ x_aeG -
case x_aeG of _ {
__DEFAULT - GHC.Tuple.();
NFDataTest2.Foo3 ds_deT - GHC.Tuple.()
}
}}}
...whereas I'd have expected it to to compile it to a collapsed
`__DEFAULT`-only case, i.e.
{{{
NFDataTest2.rnf1 =
\ x_aeG - case x_aeG of _ { __DEFAULT - GHC.Tuple.() }
}}}
Now I've been hunting it down to the function `SimplUtils.mkCase1` [2],
which according to the source-code comments, is supposed to merge
identical alternatives, i.e.:
{{{
| 3. Merge identical alternatives.
| If several alternatives are identical, merge them into
| a single DEFAULT alternative. I've occasionally seen this
| making a big difference:
|
| case e of = case e of
| C _ - f x D v - v
| D v - v DEFAULT - f x
| DEFAULT - f x
}}}
...and the `mkCase1` function itself reads as follows:
{{{
mkCase1 dflags scrut case_bndr alts_ty ((_con1,bndrs1,rhs1) :
con_alts)
| all isDeadBinder bndrs1 -- Remember the
default
, length filtered_alts length con_alts -- alternative comes
first
-- Also Note [Dead binders]
= do { tick (AltMerge case_bndr)
; mkCase2 dflags scrut case_bndr alts_ty alts' }
where
alts' = (DEFAULT, [], rhs1) : filtered_alts
filtered_alts = filter keep con_alts
keep (_con,bndrs,rhs) = not (all isDeadBinder bndrs rhs
`cheapEqExpr` rhs1)
}}}
Now the problem seems to be, that `isDeadBinder` returns `False`; so I
hacked up `mkCase1` and inserted a `occurAnalyseExpr` on artificially
constructed single-alternative 'Case' values before applying
`isDeadBinder`, and then it would return `True` and simplify the case
expression as expected.
So now my question is, why isn't the occurrence information available for
the case-alternative's binders (the occInfo is set to `NoOccInfo`) at
`mkCase1`-time? When is occurence analysis performed relative to the
simplifier?
* [1]: [http://hackage.haskell.org/package/deepseq-generics]
* [2]:
[http://www.haskell.org/ghc/docs/7.6.1/html/libraries/ghc-7.6.1/src/SimplUtils.html#mkCase1]
--
Ticket URL: http://hackage.haskell.org/trac/ghc/ticket/7360
GHC http://www.haskell.org/ghc/
The Glasgow Haskell Compiler
___
Glasgow-haskell-bugs mailing list
Glasgow-haskell-bugs@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
Re: [GHC] #7360: Case-of-identical-alts optimisation fails abjectly
#7360: Case-of-identical-alts optimisation fails abjectly
-+--
Reporter: simonpj | Owner:
Type: bug | Status: new
Priority: normal| Milestone:
Component: Compiler | Version: 7.6.1
Keywords:| Os: Unknown/Multiple
Architecture: Unknown/Multiple | Failure: None/Unknown
Difficulty: Unknown |Testcase:
Blockedby:|Blocking:
Related:|
-+--
Comment(by simonpj):
I was very surprised to see this but you are absolutely right. The reason
the occurrence info does not show the alternative's binders as dead shows
up in `Simplify.simplAlt`. Look at the call to `zapBndrOccInfo`,
controlled by the boolean `keep_occ_info`. Notice that `keep_occ_info` is
false if the scrutinee is a variable, which it usually is. This is
enough to defeat the optimisation.
The reason is described in `Note [zapOccInfo]` in `Simplify.lhs`. If we
have
{{{
case x of { C a b - case x of { C p q - p } }
}}}
Now, `a` and `b` are not mentioned, and are hence dead. But if we were to
optimise the inner case, we'd reduce
{{{
case x of { C p q - p } ===a
}}}
and now `a` is alive. Moreover `mkCase1` is applied use '''after''' the
alternative has been simplified, so now it in fact looks like
{{{
case x of { C a b - a }
}}}
That's why a's occurrence info is zapped: it might not be dead any more.
But in fact the occurrence analyser goes to great trouble (the binder-
swap optimisation) to ensure that if the scrutinee is a variable, we
replace its uses in the alternatives with the case-binder. So the
occurrence analyser will produce this
{{{
case x of y { C a b - case y of { C p q - p } }
}}}
So we really don't need to take the scrutinee into account.
I think I see how to ''both'' simplify the code ''and'' make the
optimisation work again. I need enough time to do some comparative nofib
runs to make sure I hvae not messed up, though.
Thanks for pointing this out.
Simon
--
Ticket URL: http://hackage.haskell.org/trac/ghc/ticket/7360#comment:1
GHC http://www.haskell.org/ghc/
The Glasgow Haskell Compiler
___
Glasgow-haskell-bugs mailing list
Glasgow-haskell-bugs@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
