[GHC] #7994: Make foldl into a good consumer

[GHC]

#7994: Make foldl into a good consumer
-------------------------------------+------------------------------------
        Reporter:  simonpj           |            Owner:
            Type:  bug               |           Status:  new
        Priority:  normal            |        Milestone:
       Component:  Compiler          |          Version:  7.6.3
      Resolution:                    |         Keywords:
Operating System:  Unknown/Multiple  |     Architecture:  Unknown/Multiple
 Type of failure:  None/Unknown      |       Difficulty:  Unknown
       Test Case:                    |       Blocked By:
        Blocking:                    |  Related Tickets:
-------------------------------------+------------------------------------

Comment (by nomeata):

 I have come up with a stand-alone analysis that tries to find out the
 “caller arity” of a function. Quite a bit like the usage demand, but
 different from the demand analyser in a few aspects: It does not bother
 about the demand put on function arguments by a function (so much less
 fixed-pointing due to that), and it currently looks only for tail-calls
 (or almost-tail-calls; some post-processing of return values a after the
 “tail call” is ok, as long as it does not do any relevant calls).

 It is an analysis phase that puts the result in the IdInfo, and the
 simplifier will eta-expand functions where the „caller arity” is higher
 than the manifest arity.

 It has zero effect on the current code base.

 If I implement `foldl` via `foldr` (but ''without'' the use of `oneShot`),
 I get essentially the same as the result as without the analysis, but with
 the explicit `oneShot`:

 {{{
             Min          -0.2%    -74.5%     -3.0%     -3.0%    -50.0%
             Max          +0.9%     +1.8%     +2.5%     +2.5%    +14.8%
  Geometric Mean          -0.0%     -3.7%     -0.3%     -0.3%     -0.5%
 }}}

 It still does not help with `bernoulli`, and probably nothing will:
 Implementing `foldl` as `foldr` will always yield bad code if list fusion
 does not work all the way and the `build` (or in this case, `build2`) is
 not completely gone. But if list fusion works, the results can be very
 good

 The `oneShot` change is much simpler, has little risk of introducing bugs
 and does not increase compilation times. The “caller arity” pass, OTOH,
 may optimise other code as well (but at least nofib does not seem to
 contain much such code), and can likely be made more precise. But the
 conclusion is that `foldl` can be made a good consumer!

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