<p>The key is probably the fact that it uses whole program analysis and whole program optimisation. The more you know about a how a program behaves, the more you can specialise and inline and make performant.</p>

<p>The MLton compiler for Standard ML does a similar thing (<a href="http://mlton.org/" rel="nofollow">http://mlton.org/</a>). There is one presentation (at least) about it: <a href="http://mlton.org/pages/References/attachments/060916-mlton.pdf" rel="nofollow">http://mlton.org/pages/References/attachments/060916-mlton.pdf</a>. </p>

<p>Earlier work was done by Craig Chambers and his group at the University of Washington (for example: <a href="http://www.cs.washington.edu/research/projects/cecil/www/pubs/jdean-thesis.html" rel="nofollow">http://www.cs.washington.edu/research/projects/cecil/www/pubs/jdean-thesis.html</a>). This was done in the context of Self and later Cecil/Vortex.</p>

<p>There's probably more work in the Scheme/Lisp community. You probably want to consider googling "whole program optimisation".</p>

CC BY-SA 3.0
2012-01-16T12:14:06.497Z
2014-09-28T06:24:48.940Z
2014-09-28T06:24:48.940Z
Dave Clarke
<p><a href="ftp://ftp.ecn.purdue.edu/qobi/research-statement.pdf" rel="noreferrer">J.M. Siskind's research statement</a> states:</p>
<blockquote>
<p>Stalin is an optimizing compiler for Scheme that performs whole-program static analysis and uses the results of that analysis to generate extremely efficient code. Stalin utilizes a large collection of static-analysis techniques. It performs a novel form of polyvariant flow analysis that uses iterated monovariant flow analysis to perform flow-directed splitting: cloning of specialized copies of procedures and per-call-site assignment of targets to such clones. It uses the results of flow analysis to perform life-time analysis, escape analysis, points-to analysis, and must-alias analysis. These analyses support a novel form of lightweight closure conversion that eliminates most closure slots, using techniques such as variable globalization and localization, compresses the static backchain, and usually eliminates most closures from programs. It also uses the above analyses to support flow-directed region-based storage management, where run-time garbage collection is replaced with static allocation and deallocation on a per-abstract-value and per-program-point basis. It also performs flow-directed lightweight CPS conversion, using extensions of the techniques pioneered with Screamer, to support extremely efficient first-class continuations. Finally, it supports flow-directed inlining and low-level representation selection to choose the implementation (or nonimplementation) of tags, tag checking, and tag dispatching on a per-abstract-value and per-program-point basis. This eliminates most run-time tags, tag checking, tagging, tag stripping, tag dispatching, boxing, and unboxing from programs. <strong>These analyses and optimizations allow Stalin to generate extremely efficient code that outperforms all other Scheme compilers by factors ranging between two and one hundred, particularly for numerically intensive code. Stalin often generates code that outperforms handwritten c and Fortran code.</strong></p>
</blockquote>
<p>I was able to find the following very interesting paper on closures/function calls implementation: <a href="ftp://ftp.ecn.purdue.edu/qobi/fdlcc.pdf" rel="noreferrer">Flow-Directed Lightweight Closure Conversion</a>. I've also emailed the author to ask about the papers on the other topics, which are mentioned as to be written in the closure conversion paper:</p>
<blockquote>
<p>Siskind, J. M. 2000a. Flow-directed lightweight CPS conversion. In preparation.</p>
<p>Siskind, J. M. 2000b. Flow-directed polyvariance. In preparation.</p>
<p>Siskind, J. M. 2000c. Flow-directed representation selection. In preparation.</p>
<p>Siskind, J. M. 2000d. Flow-directed storage management. In preparation</p>
</blockquote>
<p>Unfortunately, he never got around to writing those papers. My question to you is: are there any alternative or related papers that cover these topics? I'm very interested to learn how Stalin (or other compilers) can compile such a high level language as Scheme that is garbage collected, dynamically typed, supports first class functions, and even first class continuations, can be statically compiled to such efficient code. Although papers on flow analysis are quite abundant, papers on using the results of such an analysis to do the optimizations mentioned above aren't.</p>

<compilers>
The Stalin compiler brutally optimizes, but how?
Jules
# The Stalin compiler brutally optimizes, but how?

(Asked by: username_0 on 2012-01-16)

[J.M. Siskind's research statement](ftp://ftp.ecn.purdue.edu/qobi/research-statement.pdf) states:

> Stalin is an optimizing compiler for Scheme that performs whole-program static analysis and uses the results of that analysis to generate extremely efficient code. Stalin utilizes a large collection of static-analysis techniques. It performs a novel form of polyvariant flow analysis that uses iterated monovariant flow analysis to perform flow-directed splitting: cloning of specialized copies of procedures and per-call-site assignment of targets to such clones. It uses the results of flow analysis to perform life-time analysis, escape analysis, points-to analysis, and must-alias analysis. These analyses support a novel form of lightweight closure conversion that eliminates most closure slots, using techniques such as variable globalization and localization, compresses the static backchain, and usually eliminates most closures from programs. It also uses the above analyses to support flow-directed region-based storage management, where run-time garbage collection is replaced with static allocation and deallocation on a per-abstract-value and per-program-point basis. It also performs flow-directed lightweight CPS conversion, using extensions of the techniques pioneered with Screamer, to support extremely efficient first-class continuations. Finally, it supports flow-directed inlining and low-level representation selection to choose the implementation (or nonimplementation) of tags, tag checking, and tag dispatching on a per-abstract-value and per-program-point basis. This eliminates most run-time tags, tag checking, tagging, tag stripping, tag dispatching, boxing, and unboxing from programs. **These analyses and optimizations allow Stalin to generate extremely efficient code that outperforms all other Scheme compilers by factors ranging between two and one hundred, particularly for numerically intensive code. Stalin often generates code that outperforms handwritten c and Fortran code.**

I was able to find the following very interesting paper on closures/function calls implementation: [Flow-Directed Lightweight Closure Conversion](ftp://ftp.ecn.purdue.edu/qobi/fdlcc.pdf). I've also emailed the author to ask about the papers on the other topics, which are mentioned as to be written in the closure conversion paper:

> Siskind, J. M. 2000a. Flow-directed lightweight CPS conversion. In preparation.
>
> Siskind, J. M. 2000b. Flow-directed polyvariance. In preparation.
>
> Siskind, J. M. 2000c. Flow-directed representation selection. In preparation.
>
> Siskind, J. M. 2000d. Flow-directed storage management. In preparation

Unfortunately, he never got around to writing those papers. My question to you is: are there any alternative or related papers that cover these topics? I'm very interested to learn how Stalin (or other compilers) can compile such a high level language as Scheme that is garbage collected, dynamically typed, supports first class functions, and even first class continuations, can be statically compiled to such efficient code. Although papers on flow analysis are quite abundant, papers on using the results of such an analysis to do the optimizations mentioned above aren't.

**Tags:** compilers


---

## 1 answers

### Answer by username_1 on 2012-01-16. Score: 11

The key is probably the fact that it uses whole program analysis and whole program optimisation. The more you know about a how a program behaves, the more you can specialise and inline and make performant.

The MLton compiler for Standard ML does a similar thing (<http://mlton.org/>). There is one presentation (at least) about it: <http://mlton.org/pages/References/attachments/060916-mlton.pdf>.

Earlier work was done by Craig Chambers and his group at the University of Washington (for example: <http://www.cs.washington.edu/research/projects/cecil/www/pubs/jdean-thesis.html>). This was done in the context of Self and later Cecil/Vortex.

There's probably more work in the Scheme/Lisp community. You probably want to consider googling "whole program optimisation".


---

