comments

Stephen Weeks MLton@sourcelight.com
Wed, 14 Mar 2001 16:22:57 -0800 (PST)


Here's my notes on the rest of the comments.  Suresh, thanks a lot -- I took the
rest of your suggestions pretty much unchanged.  I put a snapshot up at
http://www.star-lab.com/sweeks/01-icfp.tgz.  Matthew, I am keeping the tokens on 
everything until I hear from you so I can continue doing minor edits.

> 1. I think the relationship between SSA and CPS is well-known, and
> doesn't require a separate section esp. since there's no specific
> experimental data on optimizations used on the contified program
> that is SSA-based described in the paper.
...
> 6. I'd punt Section 3.2 as it stands, or (a) elaborate
> to justify why it's where it is in the paper, or (b)
> move it closer to the intro.

Agreed.  I dropped section 3.2 entirely.

> 2. It's not clear many people are aware of proc/cont lambdas in
> Richards's work (actually, I think it's proc/jump lambdas if
> I'm not mistaken).  I'd dop the reference.

Agreed.  dropped.

> I would reorder the description of MLton's structure to put
> flow-analysis before closure conversion (since that's how
> it's structured logically in the implementation).

Done.

> 3. Rather than saying "Some readers may be confused", I'd
> rewrite to say "The reader might observe that the CPS ...".

I changed it to "It may be confusing that ...".  That removes our last reference 
to the reader.

> 3. I think it's important to highlight that wrt control-flow,
> contification simply turns function calls to jumps in the
> context of this IL.

I added this to the end of 3.1

> 5. I think the quote from Richard's paper is unnecessary
> esp. as it refers to "proc" expressions which are not 
> properly explained.  Given that Richard's paper is not 
> well-cited, I would punt the expanded quote, and summarize
> the reference.

OK.  It's gone.

> 1.  In the table describing A(f), can I replace "f always
> returns to continuation k" with "f only returns to
> continuation k"; the former sentence allows f to return
> to different continuations all of whom may eventually
> return to k, whereas the latter prohibits this.  Which 
> meaning did you intend?

What we mean by f always returns to continuation k (or to function g) is that it 
returns there either directly, or through a sequence of "tail returns".  We do
not mean through other nontail calls.

> In any case, I think you might
> consider elaborating a bit more here since this section forms
> the crux of the paper.

I think I'll leave it as always and say a bit more.  Here's what I added.

The meaning of $\A(f) = k$ is that whenever the body of $f$ is evaluating,
the top frame on the stack will have $k$ as its continuation.
The meaning of $\A(f) = g$ is that $g$ is always responsible for calling $f$,
either directly or through an intervening sequence of tail calls.  If there were 
no tail-call optimization, then this would correspond to $f$ always returning to 
$g$, possibly through an intervening sequence of frames corresponding to tail
calls.

> 2.  "all safe analyses label all and only the unreachable
> functions"  -- I don't understand this.

I changed it to
  The following lemma shows that a safe analysis never labels a reachable
  function as $\Uncalled$. 

> 7. "Another way to think of the safety" --> "Another way to
> think of safety"

Fixed.

> 9. I didn't follow your description of maximal analysis.
> Analysis A1 claims that g always returns to f, whereas
> A2 claims g always returns to K -- surely, this distinction
> would lead to different optimization opportunities.  If
> not, I think it would be worthwhile explaining why not.
> (Perhaps because the implementation computes a least
> fixed-point over reachable paths, or something along 
> those lines.)

Actually, the transformation would produce similar code in both cases.  The only 
difference would be the nesting.  In the case of A1, g would be nested within
f.  In the case of A2, f and g would be mutually recursive.

I decided that the easiest thing to do was to drop the mention of benefits
entirely and just say that A1 and A2 are both safe and maximal.

> 10. I find the description in Section 4.2 describing 
> tail calls confusing; there's a matrix of four cases
> that are blurred together.  I think it would be good
> to expand or clarify.

I rewrote it.  I also rewrote the rules in the figure.  Take a look at the new
snapshot to see.

> Fine, but it would be nice to have some conclusion about
> what the numbers mean; something along the lines of 
> a "dominator-based analysis is the preferred contification
> strategy for ML-like languages written in a functional
> style" etc.

I added the following.

Although the run times in \tabref{running-time} do not provide convincing
evidence that $\Adom$ is preferable to $\Acall$ or $\Acont$, the counts in
\tabref{counts} have convinced us to switch to $\Adom$ as the contification
analysis in {\mlton}.  We believe that the improved intraprocedural control-flow
information will benefit optimizations we plan to implement in the future.  We
also believe that the undesirable interaction with current optimizations (like
inlining) can be improved.

> I see where Henry is coming from, but I don't know the best way to fix it.
> I'm looking at the abstract and I think I can rework that to drop the
> reference to intra-procedural control flow and pull in a reference to SSA,
...
> Last note: definitely look at the abstract, particularly in light of the
> comments about the CPS/SSA relation.

I thought it made the abstract too wordy, so I rewrote the first part.  Take a
look.