A very good thesis

[dufrp@oricom.ca]

Optimizing Compilers for Structured Programming Languages:
ftp://ftp.inf.ethz.ch/pub/publications/dissertations/th11024.ps 


year         : 1995
title        : Optimizing Compilers for Structured Programming Languages
author       : Marc M. Brandis
school       : ETH Zürich
address      : Institute of Computer Systems
abstract     :
Modern processor architectures rely on optimizing  compilers  to  achieve  high
performance.  Such  architectures  expose  details  of  their  hardware  to the
compiler, which has  to  deal  with  them  in  generating  machine  code.  This
development  has  led  to  complex  and  slow compilers, which are difficult to
understand, implement, and maintain.
    This thesis reports on methods to simultaneously reduce the complexity  and
the  compile-time  of  optimizing  compilers  by  more  than a decimal order of
magnitude. It presents  a  novel  intermediate  program  representation,  which
integrates  data-  and control-flow into a single data-structure. This provides
not just for simpler and faster optimization  algorithms,  but  also  for  more
powerful   optimization  techniques.  The  thesis  also  describes  single-pass
algorithms  to  construct  this  intermediate   program   representation   from
structured source code, as well as single-pass techniques to transform programs
with  restricted  kinds  of  unstructured  control-flow  like  in  Oberon  into
structured  form. The integration of these techniques with the parser allows to
implement fast and compact front-ends  for  structured  programming  languages,
that  avoid  the  many  auxiliary  data  structures  other optimizing compilers
require.
    A description of several  optimization  algorithms  and  how  they  can  be
implemented  on  this intermediate program representation shows the feasibility
of  the  approach.  Most  of  these  techniques  have  been  implemented  in  a
prototypical  optimizing  compiler  translating  a  subset  of  the programming
language Oberon for the PowerPC architecture.  Measurements  on  this  compiler
prove that both the complexity and the compile-time of optimizing compilers can
be reduced by an order of magnitude when translating a  structured  programming
language  and  when  using  this  novel  intermediate  representation  and  the
associated  algorithms.  The  thesis  concludes  with  some  feedback  to   the
programming   language   designers,   which  language  constructs  cause  undue
complications in optimizing compilers and should therefore be omitted.