Improve SpecConstr for join points
This is another SpecConstr
improvement suggestion. See also #2598, #2255.
Roman writes: Yes, this is turning into a major problem, in fact. This is the simplest example I could find:
foo :: Int -> Int :*: (Int :*: Int) -> Int
foo 0 p = p `seq` 0
foo i (m :*: (n1 :*: n2)) =
case (case even (i-n1-n2) of
True -> (i `div` 2, (n1-1) :*: (n2-1))
False -> (i-1, (n1+1) :*: (n2+1))) of
(j, p) -> foo (if even i then i-m else i+m) ((m-1) :*: p)
The pattern here seems to be
let j x = ....
in ...(j (C a b)).... (j (C p q)) ...
So a C value is built every time j is called. Simon Marlow also saw something very similar in some STM code he was optimising recently.
Here's a possible solution:
- extend
SpecConstr
to work on *non-recursive* functions too. - look for the call pattern not in j's RHS (as we do for recursive fns) but in the body of the let
A possible restriction is to do all this only for local, non-recursive fns that are themselves defined in the RHS of a recursive function. The motivation would be do it only when we're in a loop, and being in the body of a recursive function is a big clue.
Do you think that would address the cases you've encountered? It would be a bit like making join-points eager to inline (specialisation is a bit like partial inlining) except that
- we'd get sharing when there were two calls applied to the same constructor
- it'd only happen if that argument was taken apart in the join point
Roman comments: No, the last restriction is not good: we often have
foo p = let j x' = ... foo (x',c) ...
in ... j (C a) ... j (C b) ...
Here, the join point doesn't take apart the argument. In fact, this probably makes it a bit trickier: we want to specialise the join point and
- then* specialise foo, getting
foo p = let j x' = ... foo (x',c) ...
{-# RULES j (C z) = j' z #-}
j' z = ... foo (C z,c) ...
in ... j' a ... j' b ...
{-# RULES foo (C x,y) = foo' x y #-}
foo' x y = ...
A problem is that for SpecConstr
to specialise foo
, j
must be specialised
and *simplified* first to expose the structure of the argument in the
recursive call. Can this be done without running SpecConstr twice? Or is
running pecConstr/Simplify
repeatedly (until it produces no more
specialisations) acceptable?
Trac metadata
Trac field | Value |
---|---|
Version | 6.8.3 |
Type | Bug |
TypeOfFailure | OtherFailure |
Priority | normal |
Resolution | Unresolved |
Component | Compiler |
Test case | |
Differential revisions | |
BlockedBy | |
Related | |
Blocking | |
CC | |
Operating system | |
Architecture |