Prototyping a PEG-based compiler
Olle Tervalampi Olsson · 2017
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).