Joachim
Interesting. We can discuss when you get back, but let me jot down one comment. You write:
 This will always happen if the join point function gets a richer
 CPR property than the function that it belongs to
Good observation. Maybe we can exploit it directly rather than figuring out "common contexts"? If we knew, for each local function, whether it was a join point, and if so for what, we could just make its inferred CPR property no richer than its "parent", perhaps.
Simon
 Original Message
 From: ghcdevs [mailto:ghcdevsbounces at haskell.org] On Behalf Of
 Joachim Breitner
 Sent: 12 December 2013 01:29
 To: ghcdevs at haskell.org
 Subject: Common Context transformation for join points

 Hi all,

 I just came up with this, and unless I write it down I doubt I?ll be
 able to fall asleep.

 The problem I?m trying to solve is the bad interaction of the CPR worker
 wrapper transformation and join points. Consider, as a running example:

 f x =
 let $j n = Just (Int# (n +# 1))
 in case x of
 A > $j 1
 B > $j 2
 C > Just undefined

 The join point $j has the important property that in the final code, it
 can be jumped to, because its result is also the result of f, so no
 function closure has to be allocated for it. It seems that this is
 crucial for performance.

 But now lets do CPR, and just for demonstration, do nested CPR (the
 effect can also occur with nonnested CPR). Doing w/w we get

 $wf x = case (
 let $w$j n = n +# 1
 $j n = Just (Int# ($w$j n))
 in case x of
 A > $j 1
 B > $j 2
 C > Just undefined
 ) of Just n > n
 f x = Just ($wf x)

 now we simplify, i.e. move the worker transformation inside, and inline
 $j?s wrapper. (I hope I am doing this right; but this is what I expect
 to happen):

 $wf x =
 let $w$j n = n+1
 in case x of
 A > Int# ($w$j 1)
 B > Int# ($w$j 2)
 C > undefined
 f x = Just ($wf x)

 So f?s worker transformation has nicely canceled with the invocations of
 Just, but it still leaves a "Int#" invocation around $w$j, so we lose
 the noletescape property of it and get worse code in the backend. This
 will always happen if the join point function gets a richer CPR property
 than the function that it belongs to, and is the reason for some hacks
 in the CPR code (i.e. no CPR for locally stuff that returns a sum
 type... not nice.)

 I think I have a solution for this. One observation is that these $j
 functions are not really functions of their own. For this transformation
 (and possibly for others), one should try to treat them so that they
 behave as if they were inlined. So here is the idea:

 We do not do any w/w for $j at first, on the premise that it is not a
 proper function of its own. We do w/w for f as before, and simplify as
 before, ending up with

 $wf x =
 let $j n = Just (Int# (n +# 1))
 in case x of
 A > case $j 1 of Just n > n
 B > case $j 2 of Just n > n
 C > undefined
 f x = Just ($wf x)

 so we temporarily broke the property. Now a new simplifier step kicks
 in: For a let that looks like it was or should be a join point (hand
 waving here ? one could possibly do it for all nonrecursive lets, maybe
 there is even more to gain), we find out

 for all uses of $j applied to its arity number of arguments,
 what is the largest common context?

 where a context is
 * ?, the trivial context,
 * case c of ..., where c is a context, and ... does not contain a
 call to $j,
 * f c, where c is a context and f does not contain a call to $j,
 or
 * c x, where c is a context and f does not contain a call to $j.
 In particular we do not include code here where $j is part of an
 alternative of a case. (Casts should ok fine as well, ignoring them for
 now.)

 In our example, the context would be "case ? of Just n > n".

 Once we have found that, I believe it will be always safe and beneficial
 to replace the body e of $j by c[e], and in the body of the let replace
 every c[$j args..] by $j args.

 In our example, we would obtain

 $wf x =
 let ?j n = case Just (Int# (n +# 1)) of Just n > n in case x of
 A > $j 1
 B > $j 2
 C > undefined
 f x = Just ($wf x)

 which then in further steps simplifies to the in all respects ideal code

 $wf x =
 let ?j n = Int# (n +# 1))
 in case x of
 A > $j 1
 B > $j 2
 C > undefined
 f x = Just ($wf x)


 Implementationwise I figured that this will need two traversals (down
 and up each) of the let body: Starting from a let binding that looks
 promising (e.g. oneshot nonrecursive lambda), walk down the body until
 invocations of the right arity are found. Then walk back returning a
 growing contest, and at caseexpressions lub these contexts by taking
 their common prefix (or suffix, depends on how they are
 represented :)). Then decide whether the transformation is useful (i.e.
 the context is nontrivial), and if so, walk back down to find the $j
 invocations again, and then walk back, removing the final context while
 doing so.


 I believe this would make some letnoescaperelated reluctanceness in
 the CPRanalysis obsolete, which would be great. And it might be a
 worthwhile transformation on its own (if it actually does occur), as it
 reduces code size without any downside (as far as I can see).


 Now it is likely that I thought of something existing here, or of
 something that has been tried and found not useful or feasible. If so,
 please let me know.


 Good night,
 Joachim


 
 Joachim ?nomeata? Breitner
 mail at joachimbreitner.de ?
http://www.joachimbreitner.de/ Jabber: nomeata at joachimbreitner.de ? GPGKey: 0x4743206C
 Debian Developer: nomeata at debian.org