Jump to : Abstract | Keyword | Contact | BibTex reference | EndNote reference |

shivers91a

Olin Grigsby Shivers. Control-Flow Analysis of Higher-Order Languages or Taming Lambda. PhD Thesis Carnige-Mellon Univeristy, May 1991.

Abstract

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

Keyword

[ Dyntyp ]

Contact

Olin Shivers

BibTex Reference

@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}
}

EndNote Reference [help]

Get EndNote Reference (.ref)