[GHC] #855: Improvements to SpecConstr

[GHC]

#855: Improvements to SpecConstr
-------------------------------------+-------------------------------------
        Reporter:  simonpj           |                Owner:  (none)
            Type:  task              |               Status:  new
        Priority:  normal            |            Milestone:  ⊥
       Component:  Compiler          |              Version:  6.4.2
      Resolution:                    |             Keywords:  SpecConstr
Operating System:  Unknown/Multiple  |         Architecture:
 Type of failure:  Runtime           |  Unknown/Multiple
  performance bug                    |            Test Case:  N/A
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):
       Wiki Page:                    |
-------------------------------------+-------------------------------------
Changes (by sgraf):

 * blocking:  915 =>


Comment:

 Re: Specialising on lambdas.

 To have a concrete example to work on, I here is
 [https://gist.github.com/sgraf812/7b272f09c7da34073b994efd5425ccc8#file-
 stream-fusion-hs stream-fusion.hs], which contains a minimal stream fusion
 harness using just `singletonS`, `enumFromToS`, `sumS`, `mapS` and
 `concatMapS`. There are three example functions `ex{1,2,3}` with
 increasing nesting of `concatMapS` that should all reduce to the same
 function `goal`. More examples can follow when we get these running.

 Currently, GHC HEAD (8.5, `8529fbba309cd692bbbb0386321515d05a6ed256`)
 produces
 [https://gist.github.com/sgraf812/7b272f09c7da34073b994efd5425ccc8#file-
 stream-fusion-head-simpl-L436 this infamous piece of Core]
 ([https://gist.github.com/sgraf812/7b272f09c7da34073b994efd5425ccc8#file-
 stream-fusion-head-spec-L1387 -ddump-spec]) for `ex1`. The goal is to
 specialise `go` for the call-pattern including a lambda
 [https://gist.github.com/sgraf812/7b272f09c7da34073b994efd5425ccc8#file-
 stream-fusion-head-simpl-L466-L470 here].

 Before I found this ticket, I basically re-implemented part of what
 simonpj did, results in
 [https://github.com/sgraf812/ghc/commit/c6c9fbe1eb5ad117b5bd23e943c82ca7bc2362df
 this commit]. I basically tracked `CallOcc`urrences similarly to
 `ScrutOcc`s.

 With this specialisation for lambdas, things currently look like
 [https://gist.github.com/sgraf812/7b272f09c7da34073b994efd5425ccc8#file-
 stream-fusion-lam-simpl-L435 this]. The function has been specialised
 alright, but the free variables of
 [https://gist.github.com/sgraf812/7b272f09c7da34073b994efd5425ccc8#file-
 stream-fusion-head-simpl-L466-L470 said lambda], which includes the
 constant `Step`, are passed to
 [https://gist.github.com/sgraf812/7b272f09c7da34073b994efd5425ccc8#file-
 stream-fusion-lam-simpl-L453-L457 the specialisation as arguments].

 We want to specialise for this new `Call` pattern! However, without
 `-fspec-constr-keen`, !SpecConstr will only fire when it finds a matching
 `ScrutOcc`. Looking at the output of
 [https://gist.github.com/sgraf812/7b272f09c7da34073b994efd5425ccc8#file-
 stream-fusion-lam-spec-L1495-L1499 -ddump-spec] the corresponding
 `ScrutOcc` will only become visible in the specialised RHS, but we
 currently only specialise the original RHS. Even then, I imagine that in
 the general case we need a simplifier run in-between to reliably detect
 that we scrutinize the new parameter. But that's not actually a problem,
 because we can use `GHC.Types.SPEC` to tell the compiler to specialise
 without seeing an `ArgOcc`.

 Still, GHC needs to see a `Call` pattern with that constant argument,
 which will emerge
 [https://gist.github.com/sgraf812/7b272f09c7da34073b994efd5425ccc8#file-
 stream-fusion-lam-spec-L1503-L1517 here], but only after the corresponding
 RULEs fired.

 Here are some ideas:

 1. We can query the `exprFreeVarsList`
 [https://github.com/sgraf812/ghc/commit/c6c9fbe1eb5ad117b5bd23e943c82ca7bc2362df
 #diff-992f9a53caac96c0e6303669d68a20e1R2163 here] and see which free
 variables of the lambda have known constant value and include these in the
 specialisation. This was somehow fruitless so far for this case, as the
 free var for the `Yield ...` wasn't included in the `ValueEnv`. Not sure
 if this is even enough to reach the fixed point in all cases.
 2. Specialise specialisations (and fix anything non-terminating) (+ mini
 simplifier passes) + mini RULE engine. I'm uncomfortable with that much
 code duplication.
 3. Include call-pattern specialisation in the Simplifier, for a radical
 change. On an abstract level, this seems reasonable: Specialisation is a
 more modest form of inlining with code size in mind, one that even works
 for recursive functions. It could chew on stuff the inliner gave up on
 because of code size requirements (even non-recursive functions).

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