Re: SSA

Johan Rydberg <jrydberg@night.trouble.net> writes:
>Do anyone know where I can find good information on SSA? If any
>examples were included, I would love it. And can anyone recommend a
>book that covers this topic?


A well-written thesis that serves as a great example of how to apply
SSA in practice is


@PhdThesis{bra95,
    author = "Marc M. Brandis",
    title = "Optimizing Compilers for Structured Programming
                                  Languages",
    school = "Institute for Computer Systems, ETH Zurich",
    year = "1995",
    type = "{PhD} Dissertation",
    url = "ftp://ftp.inf.ethz.ch/pub/publications/dissertations/th11024.ps.gz",
    number = "11024",
    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.",
}


- anton
--
M. Anton Ertl
anton@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/home.html

Return to the comp.compilers page.
Search the comp.compilers archives again.