[GHC] #1904: Strictness analyser should be smarter

[GHC]

#1904: Strictness analyser should be smarter
----------------------+-----------------------------------------------------
 Reporter:  igloo     |          Owner:         
     Type:  bug       |         Status:  new    
 Priority:  normal    |      Milestone:  _|_    
Component:  Compiler  |        Version:  6.8.1  
 Severity:  normal    |     Resolution:         
 Keywords:            |     Difficulty:  Unknown
 Testcase:            |   Architecture:  Unknown
       Os:  Unknown   |  
----------------------+-----------------------------------------------------
Changes (by simonpj):

  * summary:  strictness analyser should be smarter => Strictness analyser
              should be smarter

Comment:

 Here is my analysis copied from the thread (initially I missed the link,
 and reconstructed them in my head, so I thought it'd be worth dumping them
 here).

 Simon

 When GHC decides that 'foo' is strict, it does not '''require''' that
 every caller must evaluate the argument before the call.  So GHC does
 not assume that foo always gets an evaluated argument.  Indeed, if GHC
 sees the call `(foo v)`, where `foo` is strict, it does not evaluate `v`
 before the call.  Nor in the case of `(map foo xs)`.

 When GHC sees
 {{{
         case x of
             pat -> .....(case x of DEFAULT -> e)...
             ...
 }}}
 it removes the `(case x of DEFAULT ->)`, because it can "see" that `x` is
 already evaluated. [A 'seq' turns into one of those `(case x of DEFAULT)`
 things.]  This transformation is done by the simplifier, which keeps an
 environment mapping variables to information about their degree of
 evaluation.

 However, if the outer case was
 {{{
         case (f x) of
            pat  -> ...
 }}}
 then GHC does not record anything about `x`, even if `f` is strict.  I
 guess
 it could, by making use of f's strictness information.

 But then what about
 {{{
         case (f (g x)) of ...
 }}}
 where both f and g are strict?  Etc.

 One could imagine either
  * Beefing up the existing simplifier optimisation in a relatively ad hoc
 way.

  ''Advantage'': applies even if the (case x of DEFAULT) thing shows up
 much later

  ''Disadvantage'': probably a bit ad hoc, and the simplifier is already v
 complicated

  * Adding a new top-down sweep to the strictness analyser.  Actually it
 could be done separately  from strictness analysis, but would use much of
 the same code (e.g. "what demand is placed on `x` by evaluating `(f (g
 x))`?").

  ''Advantage'': doesn't complicated the already-complex simplifier.  The
 new pass ("case optimisation", perhaps) could remove some stuff
 from the too-complex simplifier

  ''Disadvantage'': a new pass

 I'm not terribly inclined to do this myself, unless someone convinces me
 that there are big gains to be had, but I'd be happy to support someone
 who already knows GHC a bit (Ian?) if you want to have a go.

-- 
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/1904#comment:1>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler