ANH NGUYEN Compiler design and implementation in OCaml with LLVM framework Metropolia University of Applied Sciences Bachelor of Engineering Information Technology Bachelor’s Thesis 10th March 2019 Abstract Author ANH NGUYEN Title Compiler design and implementation in OCaml with LLVM framework Number of Pages 103 pages + 1 appendices Date 10th March 2019 Degree Bachelor of Engineering Degree Programme Information Technology Professional Major Software engineering Instructors Jarkko Vuori, Principal Lecturer Minna Paananen-Porkka, Language Supervisor The past several decades constantly witnessed the noticeable growth in the quantity as well as the performance of compilers for high-level programming languages due to the high demand for increasingly intricate computer programs. The objective of this thesis is to explore the feasibility of adopting Low Level Virtual Machine (LLVM) framework which is a set of well-optimised, reusable tools for constructing modern compilers. Specifically, the thesis focuses on employing LLVM framework as the Intermediate Representation (IR) code generator and as the back-end compiler infrastruc- ture to rapidly construct compilers. Along the way, this thesis depicts the fundamental structure of a modern compiler as well as the techniques to apply compiler theoretical con- cepts into practice.
In order to achieve the goal of demonstrating those concepts, practices and the effective- ness of LLVM framework, the thesis project was to design and implement a compiler for a simple, imperative programming language known as Tiger. During the process of develop- ing this compiler, several commonly used libraries for building compiler including Lex, Yacc were leveraged to solve domain specific problems. The final outcome of the project is a compiler written in a strongly-typed, general purpose, functional programming language known as Objective Categorical Abstract Machine Language (OCaml). This compiler can translate the Tiger programming language to LLVM Abstract IR and subsequently to any architecture-dependent native code supported by LLVM.
As a result, the project analyzes and emphasizes the robustness and effectiveness of LLVM framework in the process of constructing compilers. Additionally, the operational compiler serves as concrete examples as well as proofs for the correctness of the theories and skills discussed in this thesis. Keywords Compiler, LLVM, OCaml, Lex, Yacc Contents 1 Introduction 1 1.1 Computer programming languages 2 1.1 Tiger programming language 3 1.2 OCaml programming language 4 1.3 LLVM compiler framework 4 1.3 Structure of the implementation process 5 2 Lexical analysis 8 2.1 Deterministic finite automata (DFA) 10 2.2 Nonedeterministic finite automata (NFA) 12 2.3 Translation algorithm from NFA to DFA 14 2.2 Tiger tokens handling 18 3 Syntax analysis 22 3.1 Context-free grammar (CFG) 22 3.1 NULLABLE, FIRST algorithms 25 3.4 Abstract syntax tree (AST) 32 3.2 Context-free grammar of Tiger 37 3.3 Abstract syntax tree of Tiger 38 3.4 Tiger mapping logic between CFG and AST 41 4 Semantic analysis 43 4.1 Rules of variable scope in Tiger 43 4.1 Imperative hash table 45 4.3 Type system in Tiger 48 4.4 Functions in Tiger 50 4.5 Type checking implementation 50 4.3 Tiger expressions 52 5 Activation record 55 5.5 Implementation 62 6 Intermediate Representation (IR) 65 6.2 Static Single Assignment (SSA) 68 6.4 Function definition and control flow 71 6.1 Primitive value translations 74 6.5 Arithmetic and comparison expressions 80 6.1 Mem2reg Pass 98 6.2 Constant propagation Pass 99 6.3 Dead instruction elimination Pass 99 6.4 Assembly emission and linking 99 7 Evaluations 100 7.2 Drawbacks 101 8 Conclusion 103 Appendices Appendix 1. List of basic LLVM IR instructions List of Abbreviations AST Abstract syntax tree ARM Advanced RISC Machine DFA Deterministic Finite Automata FSA Finite State Automata GCC GNU Compiler Collection Lex Lexical Analyzer Generator LLVM Low Level Virtual Machine LLC Low Level Virtual Machine Static Compiler ML Meta Language MIPS Microprocessor without Interlocked Pipelined Stages NFA Nondeterministic Finite Automata OCaml Objective Categorical Abstract Machine Language SSA Static Single Assignment YACC Yet Another Compiler-Compiler 1 1 Introduction Compiler development is an interesting computer science field that empowers count- less modern technological advancements in information technology industry.
As the de- mand for robust, complex computations in various IT fields is booming, the increasing number of new programming languages such as Swift, Go, Rust and Elixir have quickly emerged in the last few decades. In fact, the process of constructing the compiler often requires the equal understandings from both computation theories and programming practices. As a result, developing compilers not only strengthens programmers' theoret- ical foundation of computer science but also boosts their problem-solving, programing skills. More importantly, the process of implementing compilers often provides the in- sights into how popular programming languages operates behind the scenes.
Indeed, the curiosity about the underlying implementation of modern programming languages is the biggest motivation behind this project. Tiger is a simple, general-purpose, statically-typed and procedural programming lan- guage designed by Andrew Appel in his book "Modern Compiler Implementation" [1, p. It has been commonly used for teaching compiler design principles at many univer- sities such as Princeton, Columbia. As a result, there are many existing implementa- tions of Tiger back-end compilers, each of which targets merely a single architecture either MIPS, x86 or ARM.
However, this project employs the power of LLVM Intermedi- ate Representation (IR) and its industrial-strength static compiler LLC to target multiple computer architectures at once. In fact, LLVM infrastructure is selected for this project because of its wide adoptions by many recent compiler projects either to create new programming languages such as Swift, Rust, Julia or to enhance the development pro- cess of the existing ones such as Glasgow Haskell Compiler (GHC) [2]. The purposes of this thesis were to give an overview of modern compiler development process and to analyze the benefits of using LLVM framework. Those two goals were achieved by constructing the compiler’s front-end components that collaboratively translate the Tiger language to LLVM IR code before adopting LLVM back-end infra- structure to produce architecture-dependent, decently optimized native code.1 Computer programming languages A computer program is a set of instructions following rules of a specific programming language.
Once a program is executed, it instructs the computer to perform actions and achieve outcome. In order to construct executable software, programmers are required to use specific vocabularies and to follow a set of grammatical rules which are formu- lated in programming languages specifications. 42] Programming languages can be categorized into two groups: low-level languages and high-level languages. Machine languages are the lowest level programming languages as they can be di- rectly executed by processors.
Those languages can be used directly to build software yet the development process is usually inconvenient, time-consuming and error-prone. Moreover, machine languages are architecture-dependent since different processors requires different types of machine code. 9] On the contrary, high-level programming languages are human-readable thanks to their high abstractions that prioritize the easiness of expression and readability [4, p. As a matter of fact, the use of high-level programming languages noticeably eases the pain of building software as they give programmers the ability to express complicated ideas with more concise, readable instructions.
In fact, instructions in high-level languages are relatively similar to English, which brings the easiness when translating human's ideas into code. Additionally, compilers for high-level languages are often more intelli- gent in detecting programming errors and they also give programmers more informa- tive error messages. As a result, it is easier to spot the mistakes and correct them dur- ing the software development process.2 Compiler software Implementing software in high-level programming languages is apparently more pro- ductive compared to programming in raw machine code. However, computers can not directly execute instructions written in high-level programming languages.
As a result, code in high-level languages must be translated to machine languages before being 3 processed by the processors. This translation procedure is often time-consuming, re- petitive; yet it can fortunately be automated by translation software known as compiler. 1] Formally, a compiler is a software that is responsible for translating a sequence of in- structions written in one language (source language) to the corresponding version writ- ten in another language (target language). Usually, the source language tends to be a high-level language while the target language is low-level one.
During the course of compiling, overly apparent programming defects are often detected and reported [5, p.1 Tiger programming language Tiger is a simple, statically-typed, procedural programming language of the Algo family. Tiger has 4 main types: integer, string, array and record. The language has support for control flow with if statement, while loop, for loop, functions and nested functions. The syntaxes of Tiger are similar to languages in Meta-language (ML) family.
[7, p2] The sample program in Tiger language is shown in Figure 1: Figure 1. Sample program in Tiger 4 1.2 OCaml programming language OCaml is a statically typed, general purpose, and functional programming language that has been in the industry for more than 20 years [8]. It is a strongly typed language with support for polymorphic type checking which gives flexibility to the type checking mechanism. Another innovative functionality is type inference, which exempts program- mers from explicitly declaring types for every single variable and function-parameters as long as those missing types are automatically deductable from the context.
As a re- sult, this functionality allows programmers to write more concise, reusable code since the compiler can usually infer the types from programming context. [8] In addition, OCaml promotes functional programming principles with full support for mathematical lambda functions, immutable data structure, recursion tail-call optimiza- tion, algebraic data structures and pattern matching. Nonetheless, due to the require- ment of expressing idea easily in some specific programming tasks, the language also supports imperative paradigm, mutable data types such as array, hash table and a complex exception handling system. [8] In particular, OCaml provides automatic memory management which mitigates the risk of memory corruption.
In fact, this feature allows programmers to focus solely on the structure of data computation, rather than the manual memory deallocation process [8]. Therefore, implementing compilers in OCaml is more convenient compared to using languages without garbage collector such as C or C++. Finally, OCaml offers well-supported tools for writing compilers, such as Lexical Ana- lyzer Generator (Lex), Yet Another Compiler-Compiler (Yacc) and LLVM bindings that interact with C++ API of LLVM. As a result, the pain of writing this compiler is eased significantly thanks to those toolkits.3 LLVM compiler framework LLVM is a compiler toolkit implemented in C++ that offers a rich set of commonly used modules and reusable toolchains for constructing modern compilers in a timely man- ner.
In fact, LLVM provides developers tools to programmatically generate instructions in LLVM IR - a statically typed, architecture independent abstraction of assembly code. LLVM IR bitcode can further be optimized in a sequence of phrases and consequently 5 compiled into native machine code in various target architectures such as MIPS, x86, ARM. As a result, this advantage boosts the portability of the source languages to mul- tiple machine platforms. In addition, LLVM can also perform Just-In-Time (JIT) compila- tion on the IR code in the context of another program as an interpreter.
[2] Initially, LLVM was a created by Chris Latter, who is also the father of Swift program- ming language, as a research project at the University of Illinois in 2000. In fact, LLVM framework was created because other existing open source C compilers such as GNU Compiler Collection (GCC) had become stagnated. [2] Indeed, GCC aging codebase often poses a steep learning curve for new developers. GCC was implemented in a monolithic mindset which means that every component is tightly coupled with each other causing the poor reusability when integrating with other software.
Furthermore, GCC did not provide support for modern compiling techniques such as JIT code generation, cross-file optimization at that time. [9] As a result, LLVM took a completely different approach by employing a modular, reusa- ble architecture in which each compiler component is constructed following the single responsibility principle and they are a loosely coupled. Therefore, those components can be composed together in order to build a full compiler.