Do not eta-expand in SimplGentl
Needs RevisionPublic

Authored by nomeata on Apr 17 2015, 9:02 AM.

Details

Reviewers
simonpj
goldfire
bgamari
austin
Trac Issues
#9020
Summary

Eta-expansion can seriously blow up the size of the code, if there are
newtypes and coercions involved; see Trac #9020 for a particularly good
example.

It may work out well in a full simplifier phase, when the additional
coercions can be optimized away, e.g. after inlining. But the gentle
phase does less, in particular no inlining, so chances are high that we
will blow up our code for on good reason.

If this change works out, there is no need for Trac #10319 anymore.

Test Plan

validate

Diff Detail

Repository
rGHC Glasgow Haskell Compiler
Branch
master
Lint
Lint Skipped
Unit
Unit Tests Skipped
Build Status
Buildable 3806
Build 3836: GHC Patch Validation (amd64/Linux)
nomeata updated this revision to Diff 2793.Apr 17 2015, 9:02 AM
nomeata retitled this revision from to Do not eta-expand in SimplGentl.
nomeata updated this object.
nomeata edited the test plan for this revision. (Show Details)
nomeata added a reviewer: simonpj.
nomeata updated the Trac tickets for this revision.

Eek, the build fails with *** End of Offense *** in Data.Void. Let’s see if I can reproduce this here.

Indeed:

*** Core Lint errors : in result of Common sub-expression ***
<no location info>: warning:
    [in body of lambda with binder x_a56d :: Void]
    No alternatives for a case scrutinee not known to diverge for sure: lvl_s5zi
                                                                          x_a56d
*** Offending Program ***
lvl_s5zi :: Void -> ShowS
[LclId, Str=DmdType]
lvl_s5zi =
  \ (eta_B1 :: Void) -> case eta_B1 of wild_X11 [Dmd=<B,U>] { }

$cshow_a4Up :: Void -> String
[LclId,
 Arity=1,
 Str=DmdType <B,1*U>b,
 Unf=Unf{Src=InlineStable, TopLvl=True, Value=True, ConLike=True,
         WorkFree=True, Expandable=True,
         Guidance=ALWAYS_IF(arity=1,unsat_ok=True,boring_ok=False)
         Tmpl= \ (x_a56d [Occ=Once] :: Void) ->
                 case x_a56d of _ [Occ=Dead] { }}]
$cshow_a4Up =
  \ (x_a56d :: Void) -> case x_a56d of wild_X11 [Dmd=<B,U>] { }

$s$dmshow_s5hT :: Void -> String
[LclId,
 Arity=1,
 Str=DmdType <B,1*U>b,
 Unf=Unf{Src=InlineStable, TopLvl=True, Value=True, ConLike=True,
         WorkFree=True, Expandable=True,
         Guidance=ALWAYS_IF(arity=-1,unsat_ok=True,boring_ok=False)
         Tmpl= \ (x_a56d [Occ=Once] :: Void) ->
                 case lvl_s5zi x_a56d of _ [Occ=Dead] { }}]
$s$dmshow_s5hT = $cshow_a4Up

This lint message was introduced in rGHCa0678f1f0e62496c108491e1c80d5eef3936474a. This particular code at hand is a false positive and confirms my suspicion that local knowledge is _not_ always sufficient to determine that an empty case is valid....

nomeata updated this revision to Diff 2797.Apr 17 2015, 12:01 PM
nomeata edited edge metadata.

Make empty case lint check a warning.

simonpj edited edge metadata.Apr 17 2015, 1:07 PM
In D851#23035, @nomeata wrote:

This lint message was introduced in rGHCa0678f1f0e62496c108491e1c80d5eef3936474a. This particular code at hand is a false positive and confirms my suspicion that local knowledge is _not_ always sufficient to determine that an empty case is valid....

Let's investigate a little more.

  1. Why does lint complain after CSE but not before? Can you show the before and after?
  1. Why is this happening now, but not before?
  1. Finally, anything of type Void is surely bottom, so you could add that possiblity to Lint. But first lets find out the answer to (1) and (2)

Let's investigate a little more.

  1. Why does lint complain after CSE but not before? Can you show the before and after?

It’s the dual of the CSE-Dmd-Analyze-bug you fixed recently: By losing demand information, we no longer can tell if something is bottoming:

  lvl_s5Al :: Void -> ShowS                                                             |  lvl_s5Al :: Void -> ShowS                                                             
  [LclId, Str=DmdType]                                                                  |  [LclId, Str=DmdType]                                                                  
  lvl_s5Al =                                                                            |  lvl_s5Al =                                                                            
    \ (eta_B1 :: Void) -> case eta_B1 of _ [Occ=Dead, Dmd=<B,A>] { }                    |    \ (eta_B1 :: Void) -> case eta_B1 of wild_X10 [Dmd=<B,U>] { }                       


| $sshows_s5iU :: Void -> ShowS                                                         || $sshows_s5iU :: Void -> ShowS                                                         
| [LclId,                                                                               || [LclId,                                                                               
   Arity=1,                                                                             |   Arity=1,                                                                             
   Str=DmdType <B,1*U>b,                                                                |   Str=DmdType <B,1*U>b,                                                                
   Unf=Unf{Src=InlineStable, TopLvl=True, Value=True, ConLike=True,                     |   Unf=Unf{Src=InlineStable, TopLvl=True, Value=True, ConLike=True,                     
           WorkFree=True, Expandable=True,                                              |           WorkFree=True, Expandable=True,                                              
           Guidance=ALWAYS_IF(arity=0,unsat_ok=True,boring_ok=False)                    |           Guidance=ALWAYS_IF(arity=0,unsat_ok=True,boring_ok=False)                    
           Tmpl= $cshowsPrec_a4Vk shows25}]                                             |           Tmpl= $cshowsPrec_a4Vk shows25}]                                             
  $sshows_s5iU =                                                                        |  $sshows_s5iU = lvl_s5Al                                                               
    \ (eta_B1 :: Void) -> case eta_B1 of _ [Occ=Dead, Dmd=<B,A>] { }                    |  --------------------------------------------------------------------------------------

  $s$dmshow_s5iW :: Void -> String                                                      |  $s$dmshow_s5iW :: Void -> String                                                      
  [LclId,                                                                               |  [LclId,                                                                               
   Arity=1,                                                                             |   Arity=1,                                                                             
   Str=DmdType <B,1*U>b,                                                                |   Str=DmdType <B,1*U>b,                                                                
   Unf=Unf{Src=InlineStable, TopLvl=True, Value=True, ConLike=True,                     |   Unf=Unf{Src=InlineStable, TopLvl=True, Value=True, ConLike=True,                     
           WorkFree=True, Expandable=True,                                              |           WorkFree=True, Expandable=True,                                              
           Guidance=ALWAYS_IF(arity=-1,unsat_ok=True,boring_ok=False)                   |           Guidance=ALWAYS_IF(arity=-1,unsat_ok=True,boring_ok=False)                   
           Tmpl= \ (x_a57g [Occ=Once] :: Void) ->                                       |           Tmpl= \ (x_a57g [Occ=Once] :: Void) ->                                       
                   case $sshows_s5iU x_a57g of _ [Occ=Dead] { }}]                       |                   case lvl_s5Al x_a57g of _ [Occ=Dead] { }}]                           
  $s$dmshow_s5iW =                                                                      |  $s$dmshow_s5iW = $cshow_a4Vs                                                          
    \ (x_a57g :: Void) -> case x_a57g of _ [Occ=Dead, Dmd=<B,A>] { }                    |  --------------------------------------------------------------------------------------
  1. Why is this happening now, but not before?

Not sure so far. I’ll see if I can get something useful.

  1. Finally, anything of type Void is surely bottom, so you could add that possiblity to Lint.

We have that already (isEmptyTy). The problem here is that the case is not of type Void, but ShowS.

Here is an indication of the cause. This differences starts to show up after the first main simplifier phase:

$sshows_s5iU :: Void -> ShowS                                                       |  $sshows_s5iW :: Void -> ShowS                                                           
[LclId,                                                                             |  [LclId,                                                                                 
 Arity=1,                                                                           |   Arity=1,                                                                               
 Str=DmdType,                                                                       |   Str=DmdType,                                                                           
 Unf=Unf{Src=InlineStable, TopLvl=True, Value=True, ConLike=True,                   |   Unf=Unf{Src=InlineStable, TopLvl=True, Value=True, ConLike=True,                       
         WorkFree=True, Expandable=True,                                            |           WorkFree=True, Expandable=True,                                                
         Guidance=ALWAYS_IF(arity=0,unsat_ok=True,boring_ok=False)                  |           Guidance=ALWAYS_IF(arity=0,unsat_ok=True,boring_ok=False)                      
         Tmpl= $cshowsPrec_a4Vk shows25}]                                           |           Tmpl= $cshowsPrec_a4Vm shows25}]                                               
$sshows_s5iU = absurd @ ShowS                                                       |  $sshows_s5iW =                                                                          
------------------------------------------------------------------------------------|    \ (eta_B1 :: Void) -> case eta_B1 of _ [Occ=Dead] { }

We eta-expand thunks (with this change) and afterwards absurd could be inlined. Later, this is CSE’d again with other instances of that code... I’m not sure what the conclusion is.

BTW, the change as poposed here has negative performance effects on T7257, T7954, T9203, so it doesn’t seem to be a good idea after all to wildly eta-expand PAPs.

It’s the dual of the CSE-Dmd-Analyze-bug you fixed recently: By losing demand information, we no longer can tell if something is bottoming:

I fixed the bug by zapping demand info. But this is different! I do no zap the strictness signature!

What is happening here is that we CSE together lvl_s5Al and $cshow_a4Up. The latter has a strictness signature (shown as "DmdType") but the former does not. Combining them loses the strictness signature, which has the effect you see.

Another thing is that $cshow_a4Up has a stable unfolding, and we lose that too when combining.

So:

  • We should probably not CSE if it loses a stable unfolding
  • I think that it probably is sensible to do CSE even if t risks losing a strictness signature. Yes that does mean the lint thing should be a warning; but we should add a big note to CSE about it.
  • I'm interested in why lvl_s5Al occurs BEFORE $cshow_a4Up in the bindings, even though it floated up from inside $s$dmshow_s5hT. If it occurred after then the substitution would have been the other way around.
  • I'm also interested in why lvl_s5Al doesn't have a better strictness signatures

I am attaching the full -ddump-verbose2verbose log. The level in question is called lvl_s5An in this iteration, and is floated out from $cshowList_a4Vz, which is defined just before $cshow_a4Vu (in the past above, I pasted the relevant parts together; there is code between lvl_s5An and $cshow_a4Vu.)

It does not get a strictness signature as we CSE immediatelly after FloatOut; the strictness analyzer does not run there.

simonpj added inline comments.Apr 17 2015, 2:54 PM
compiler/simplCore/SimplCore.hs
952

You've lost the detailed example in the previous Note [Do not eta-expand PAPs]! Do transfer it here

BTW, the change as poposed here has negative performance effects on T7257, T7954, T9203, so it doesn’t seem to be a good idea after all to wildly eta-expand PAPs.

But I wonder why not? Insight insight!

In D851#23051, @simonpj wrote:

BTW, the change as poposed here has negative performance effects on T7257, T7954, T9203, so it doesn’t seem to be a good idea after all to wildly eta-expand PAPs.

But I wonder why not? Insight insight!

Of course! I’m just having trouble keeping up with all the new questions that are arising :-)

nomeata updated this revision to Diff 2798.Apr 17 2015, 3:26 PM
nomeata edited edge metadata.

Improve the Notes a bit.

BTW, the change as poposed here has negative performance effects on T7257, T7954, T9203, so it doesn’t seem to be a good idea after all to wildly eta-expand PAPs.

For T9203 and T7954 (which are really small files), the effect seems to happen in the libraries somewhere. Didn’t dig deeper yet.

For T7257, it is strange: The core the same, with or without my changes; yet with my changes the test fails but without it does not. In both cases, the libraries were built with my changes applied, I then reverted them, rebuilt ghc-stage2, and then built T7257.hs.

Maybe this is a sign for me to go to bed and return to it some other time, with a fresh mind.

bgamari added a subscriber: bgamari.Jul 3 2015, 3:53 PM

@nomeata, what is the status of this? It seems more work is needed?

Yes, the performance impact has to be evaluated more properly and analyzed. I am generally not looking forward to figuring out performance problems that affect test cases through the standard libraries, as you need two clean separate working copies and all that hassle.

I guess I’ll pick it up eventually, but I’m in no hurry and if someone else feels like giving it a shot, I would not mind :-)

bgamari requested changes to this revision.Jul 5 2015, 12:05 PM
bgamari added a reviewer: bgamari.

Alright, I'm going to mark this as needing changes to get it out of the review queue in that case. Let me know when a review would be helpful.

This revision now requires changes to proceed.Jul 5 2015, 12:05 PM

This is related to: https://phabricator.haskell.org/D1268#38584

I've tested this diff and it makes it a tiny bit better: 777030656 vs 786189008 bytes allocated. If you read the comment, it suggests that more eta expansions happened after some things were processed in a different order. Perhaps worth looking into.

austin resigned from this revision.Nov 6 2017, 10:08 PM