# [GHC] #2642: Improve SpecConstr for join points

GHC trac at galois.com
Thu Oct 2 08:22:04 EDT 2008

```#2642: Improve SpecConstr for join points
-----------------------------------------+----------------------------------
Reporter:  simonpj                   |       Owner:
Type:  run-time performance bug  |      Status:  new
Priority:  normal                    |   Milestone:
Component:  Compiler                  |     Version:  6.8.3
Severity:  normal                    |    Keywords:
Difficulty:  Unknown                   |    Testcase:
Architecture:  Unknown/Multiple          |          Os:  Unknown/Multiple
-----------------------------------------+----------------------------------
#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?

--