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.