#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/c6c9fbe1eb5ad117b5bd23e943c82ca7bc236... 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/c6c9fbe1eb5ad117b5bd23e943c82ca7bc236... #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