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