Advanced

Prototyping a PEG-based compiler

Tervalampi Olsson, Olle LU (2017) In LU-CS-EX 2017-13 EDA920 20161
Department of Computer Science
Abstract
Compiler optimizations are typically implemented as a sequence of trans-
formations, applied to some representation of source code. The problem of
ordering these transformations in an optimal way is commonly referred to as
the phase-ordering problem. Program Expressions Graphs (PEGs) are a code
representation designed to get around this problem, by deferring the decision
of which optimizations to perform and how after we know the effects of all
optimizations. This is accomplished by adding information to a base represen-
tation of the program (as opposed to transforming a representation), using a
technique called equality saturation. Equality saturation finds equivalent ways
of expressing the computations carried out in the... (More)
Compiler optimizations are typically implemented as a sequence of trans-
formations, applied to some representation of source code. The problem of
ordering these transformations in an optimal way is commonly referred to as
the phase-ordering problem. Program Expressions Graphs (PEGs) are a code
representation designed to get around this problem, by deferring the decision
of which optimizations to perform and how after we know the effects of all
optimizations. This is accomplished by adding information to a base represen-
tation of the program (as opposed to transforming a representation), using a
technique called equality saturation. Equality saturation finds equivalent ways
of expressing the computations carried out in the original program. Once this
is done, we can choose the most optimal way to compute an expression, with
knowledge of all other optimizations in mind. We investigate this approach to
optimization, and in doing so have developed a prototype extension to ARMs
existing graphics compiler. Due to time constraints, we did not manage to ex-
plore the merits of equality saturation for mobile GPUs, but we identify and
solve problems that occur when reverting a PEG representation of code back
to an executable representation. We also present the theory behind PEGs, with
particular focus on the translation to and from PEG form, and our extensions
to this process (adapting it to work with SSA representations of code). (Less)
Popular Abstract (Swedish)
När en kompilator optimerar programkod så är det typiska tillvägagångssättet att
applicera en sekvens av transformationer på den ursprungliga koden. Den slutgiltiga
prestandan kan försämras om ordningen på den sekvensen inte är optimal. För att
komma runt det här problemet har jag undersökt ett kompileringssätt baserat på
Program Expression Graphs (PEGs), och utvecklat ett tillägg till ARMs existerande
kompilator för OpenGL ES.
Please use this url to cite or link to this publication:
author
Tervalampi Olsson, Olle LU
supervisor
organization
course
EDA920 20161
year
type
H3 - Professional qualifications (4 Years - )
subject
keywords
Program Expression Graphs, Optimizing Compilers, Intermediate Representations
publication/series
LU-CS-EX 2017-13
report number
LU-CS-EX 2017-13
ISSN
1650-2884
language
English
id
8923147
date added to LUP
2017-08-17 14:19:25
date last changed
2017-08-17 14:19:25
@misc{8923147,
  abstract     = {Compiler optimizations are typically implemented as a sequence of trans-
formations, applied to some representation of source code. The problem of
ordering these transformations in an optimal way is commonly referred to as
the phase-ordering problem. Program Expressions Graphs (PEGs) are a code
representation designed to get around this problem, by deferring the decision
of which optimizations to perform and how after we know the effects of all
optimizations. This is accomplished by adding information to a base represen-
tation of the program (as opposed to transforming a representation), using a
technique called equality saturation. Equality saturation finds equivalent ways
of expressing the computations carried out in the original program. Once this
is done, we can choose the most optimal way to compute an expression, with
knowledge of all other optimizations in mind. We investigate this approach to
optimization, and in doing so have developed a prototype extension to ARMs
existing graphics compiler. Due to time constraints, we did not manage to ex-
plore the merits of equality saturation for mobile GPUs, but we identify and
solve problems that occur when reverting a PEG representation of code back
to an executable representation. We also present the theory behind PEGs, with
particular focus on the translation to and from PEG form, and our extensions
to this process (adapting it to work with SSA representations of code).},
  author       = {Tervalampi Olsson, Olle},
  issn         = {1650-2884},
  keyword      = {Program Expression Graphs,Optimizing Compilers,Intermediate Representations},
  language     = {eng},
  note         = {Student Paper},
  series       = {LU-CS-EX 2017-13},
  title        = {Prototyping a PEG-based compiler},
  year         = {2017},
}