Dissertação
{en_GB=Evaluating Value-Wise Poison Values for the LLVM Compiler } {} EVALUATED
{pt=A Representação Intermédia (IR) de um compilador tem-se tornado num aspeto importante dos chamados compiladores optimizadores nos últimos anos. A IR de um compilador deve facilitar a realização de transformações ao código e dar portabilidade ao compilador. Um aspeto do design de uma IR é a função do Comportamento Indefinido (UB). O UB é importante para refletir as semânticas de linguagens de programação com muitos casos de UB, como é o C e C++, mas também porque permite a realização de múltiplas optimizações e a modelação de operações de baixo nível pouco seguras. Consequentemente, o UB de compiladores importantes, como o LLVM ou o GCC, suportam uma ou mais formas de UB. Neste trabalho o nosso foco é no compilador LLVM e em como é que esta infra-estrutura lida com UB na sua IR, através de conceitos como “poison" e “undef", e como é que a existência de múltiplas formas de UB entram em conflito e causam problemas a optimizações “textbook" importantes, como “Global Value Numbering" e “Loop Unswitching", puxar operações para fora de fluxo de controlo, entre outras. Para resolver estes problemas introduzimos uma nova semântica de UB no LLVM, explicando como esta trata dos problemas mencionados, enquanto mantem as optimizações atualmente no LLVM corretas. Uma parte da implementação é a introdução de um novo tipo de estrutura na IR do LLVM – o tipo Explicitly Packed Struct – que representa cada campo da estrutura no seu próprio tipo inteiro. A nossa implementação não degrada o desempenho do compilador., en=The Intermediate Representation (IR) of a compiler has become an important aspect of optimizing compilers in recent years. The IR of a compiler should make it easy to perform transformations while also giving portability to the compiler. One aspect of IR design is the role of Undefined Behavior (UB). UB is important to reflect the semantics of UB-heavy programming languages, like C and C++, namely allowing multiple desirable optimizations to be made and the modeling of unsafe low-level operations. Consequently, the IR of important compilers, such as LLVM or GCC, supports one or more forms of UB. In this work we focus on the LLVM compiler infrastructure and how it deals with UB in its IR, with the concepts of “poison” and “undef”, and how the existence of multiple forms of UB conflict with each other and cause problems to very important “textbook” optimizations, such as some forms of “Global Value Numbering” and “Loop Unswitching”, hoisting operations past control-flow, among others. To solve these problems we introduce a new semantics of UB to the LLVM, explaining how it can solve the different problems stated, while most optimizations currently in LLVM remain sound. Part of the implementation of the new semantics is the introduction of a new type of structure to the LLVM IR – Explicitly Packed Structure type – that represents each field in its own integer type with size equal to that of the field in the source code. Our implementation does not degrade the performance of the compiler.}
abril 28, 2020, 9:0
Publicação
Obra sujeita a Direitos de Autor
Orientação
ORIENTADOR
José Carlos Alves Pereira Monteiro
Departamento de Engenharia Informática (DEI)
Professor Catedrático
