Prototyping a PEG-based compiler
(2017) In LU-CS-EX 2017-13 EDA920 20161Department 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:
http://lup.lub.lu.se/student-papers/record/8923147
- author
- Tervalampi Olsson, Olle LU
- supervisor
- organization
- course
- EDA920 20161
- year
- 2017
- 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}}, language = {{eng}}, note = {{Student Paper}}, series = {{LU-CS-EX 2017-13}}, title = {{Prototyping a PEG-based compiler}}, year = {{2017}}, }