Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Other references to how the Stalin compiler brutally optimizes?

J.M. Siskind's research statement 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. 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.

like image 889
Jules Avatar asked Jan 14 '12 01:01

Jules


1 Answers

R. Kent Dybvig's publications list.

Edit: A good introduction to Chez Scheme is his ICFP presentation and the paper that went along with that. Some of the papers relate to Scheme specifically (macros, multiple-values, continuations) and some are more broadly applicable (Register Allocation Using Lazy Saves, Eager Restores, and Greedy Shuffling).

like image 62
erjiang Avatar answered Nov 03 '22 02:11

erjiang