id	summary	reporter	owner	description	type	status	priority	milestone	component	version	resolution	keywords	cc	os	architecture	failure	difficulty	testcase	blockedby	blocking	related
2642	Improve SpecConstr for join points	simonpj		"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?

"	bug	new	lowest	7.6.2	Compiler	6.8.3				Unknown/Multiple	Unknown/Multiple	Runtime performance bug	Unknown