Olin Grigsby Shivers. Control-Flow Analysis of Higher-Order Languages or Taming Lambda. PhD Thesis Carnige-Mellon Univeristy, May 1991.
Programs written in powerful, higher-order languages like Scheme, ML, and Common Lisp should run as fast as their FORTRAN and C counterparts. They should, but they don't. A major reason is the level of optimisation applied to these two classes of languages. Many FORTRAN and C copmilers employ an aresenal of sophisticated global optimisations that depend upon data-flow analysis: common-subexpression elimination, loop-invariant detection, induction-variable elimination, and many, many more. Compilers for higher-order languages do not provide these optimisations. Without them, Scheme, LISP and ML compilers are doomed to produce code that runs lsower than their FORTRAN and C counterparts. The problem is the lack of an explicit control-flow graph at compile time, something which traditional data-flow analysis techniques require. In this dissertation, I present a technique for recovering the control-flow graph of a Scheme program at compile time. I give examples of how this information can be used to perform several data-flow analysis optimisations, including copy propagation, induction-variable elimination, useless-variable elimination, and type recovery. The analysis is defined in terms of a non-standard semantic interpretation. The denotational semantics is carefully developed, and several theorems establishing the correctness of the semantics and the implementing algorithms are proven
[ Dyntyp ]
@PhdThesis{shivers91a,
Author = {Shivers, Olin Grigsby},
Title = {Control-Flow Analysis of Higher-Order Languages or Taming Lambda},
School = {Carnige-Mellon Univeristy},
Month = {May},
Year = {1991}
}
Get EndNote Reference (.ref)