Make UNCOL cool again

Abstract

Criar e manter um compilador otimizador requer grandes esforços de desenvolvimento. Ao mesmo tempo, o número de compiladores necessários para traduzir cada linguagem de alto nível para várias arquiteturas de hardware cresce de forma multiplicativa. Uma possível abordagem para resolver esse problema envolve adotar uma representação intermediária comum, também conhecida como Universal Computer Oriented Language (UNCOL). Embora tal solução tenha sido proposta pela primeira vez em 1958, a tecnologia de compiladores e a teoria de linguagens de programação muito evoluíram desde então. No contexto destes avanços, o presente trabalho tem como objetivo reavaliar a ideia de uma representação intermediária universal; começando por um estudo da literatura e do estado da arte de linguagens de programação, de forma a elicitar requisitos e identificar princípios de criação para uma UNCOL moderna. Esses requisitos são a base de uma análise de algumas das representações intermediárias utilizadas em compiladores existentes. Além disso, os princípios extraídos da revisão sistemática motivaram a criação de uma nova representação intermediária, que combina técnicas de compilação originárias de diversas fontes na literatura. A nova representação intermediária é descrita em múltiplos aspectos, incluindo uma definição formal da sua estrutura em multigrafo e uma correspondência informal de sua semântica em termos de um modelo computacional já existente. Por fim, este trabalho descreve alguns algoritmos de análise e transformação de código customizados para a nova representação. Entre estes consta uma formulação de eliminação de código morto (uma otimização global) através de um algoritmo de coleção de lixo.

Developing and maintaining an optimizing compiler requires great amounts of effort. At the same time, the number of compilers needed in order to translate many high-level languages to every other target architecture grows multiplicatively. One possible approach to solve this problem is the adoption of a shared intermediate representation, also known as Universal Computer Oriented Language (UNCOL). While the UNCOL solution was first proposed in 1958, there have been many developments in compiler technology and programming language theory since then. This work aims to re-evaluate the idea of a universal intermediate representation in light of these advances, beginning by surveying the programming language literature and state of the art in order to identify requirements and design principles for a modern version of UNCOL. Then, these requirements are used to analyze program representations in existing compiler infrastructures. Furthermore, the set of principles extracted from the systematic review has motivated the design of a new intermediate representation, which combines compilation techniques from various sources in the literature. Multiple aspects of the new intermediate representation are described, encompassing a formal definition of its multigraph structure, an informal explanation of its semantics in terms of the join calculus, and a few custom optimization algorithms, including a formulation of global Dead Code Elimination as a garbage collection process.