re CWS paper

[Henry Cejtin]

I'm  very  confused about why the combination of call-based and continuation-
based contification performed worse then either alone.  I must say that to me
the continuation-based version seems much better.

Note,  in  some  sense the example you sent me: a tail-position if where each
branch is a tail-call to f (these being the only calls to f) seems more  like
a place where the problem is that the CPS conversion didn't perform some kind
of common-sub-expression elimination.  I.e., convert

    if ???
       then g (AAA)
       else g (BBB)
to
    g (if ???
          then AAA
          else BBB)

I still don't see any case where call-based will do it but continuation-based
won't.  Looking at your example:

    fun f () = let ... in loop () end
    fun loop () = let ... in loop () end
    fun g () = ...  K1 (f ()) ...  K2 (f ()) ...

it  is  just  that  the  call-based version is willing to duplicate f when it
makes the two new continuations that are K1 o f and K2 of f?  It seems to  me
that  this  is  really  an  orthogonal  notion:  inlining  and  the resulting
duplication of code.  Perhaps the basic inlining doesn't handle it because of
the connected contification, but it seems to me that what has really happened
in this case is that first you duplicated f, then you performed the  inlining
and  contification  because  each  version  of  f  was  only  called with one
continuation.  I can definitely believe that this happens, but it seems to me
that  it should come from these two separate optimizations.  (Part of this is
the claim that you can only contify without code duplication in the case that
the  continuation-based  analysis  says you can contify.)  From this point of
view, the call-based analysis  approximates  the  continuation-based  one  by
noting  that only one external call and all internal calls being tail => only
one continuation.

Looking at the final example you gave (where neither analysis will contify)

    fun f () = ... g () ... g () ...
    fun g () = ... f () ...
    fun h () = ... K1 (f ()) ... K2 (f ()) ...

are the two calls to g in f tail calls?  If so then clearly the continuation-
based  analysis WILL contify g in f.  Note, the continuation that you look at
is JUST the local part of the continuation, not the full continuation.  I.e.,
in any procedure all continuations end with a return or a tail-call.  (I have
to think about ones that end in raise going outside.)  I guess that there  is
a  phase  ordering  problem,  but  it seems to me that the continuation-based
analysis clearly says that g can be contified in f.  Who cares what the stack
part of the continuation is?