CIS 341 - Compilers
Spring 2020
HW4: Oat v.1 Compiler

Overview

In this project, you will implement a compiler frontend for a simple imperative language that has boolean, int, string, and array types as well as top-level, mutually-recursive functions and global variables. Your compiler will accept source files that use syntax like:

int fact(int x) {
  var acc = 1;
  while (x > 0) {
    acc = acc * x;
    x = x - 1;
  }
  return acc;
}

int program(int argc, string[] argv) {
  print_string(string_of_int(fact(5)));
  return 0;
}
  

and will produce an executable (by default named a.out) that, when linked against runtime.c and then executed produces the resulting output:

  ./a.out
  120
  

The Oat Language

Oat supports multiple base-types of data: int, bool, and string, as well as arrays of such data. The Oat language specification contains a definition of the language syntax. Oat concrete syntax does not require a local variable declaration to include a type definition, instead it uses the keyword var, as shown in the example above. Oat mostly sticks with C or Java-like syntax, except for some quirks: null requires a type annotation, bit-wise arithmetic operators have their own notation (so there is no overloading).

See the file ast.ml for the OCaml representation of the abstract syntax -- the type typ of types is defined there, along with representations of expressions, statements, blocks, function declarations, etc. You should familiarize yourself with the correspondence between the OCaml representation and the notation used in the specification. The astlib module defines some helper functions for printing Oat programs and abstract syntax.

This version of Oat will not be safe — it is possible to access an array out of bounds or to call a function with incorrectly typed arguments. The next version of Oat will address these issues and add some other missing features. In particular, although the grammar gives a syntax for function types, this version of Oat does not need to support function pointers; these are included in anticipation of the next project.

Features

Functions:
Oat supports mutually-recursive, top-level functions. Each function body consisting of a series of imperative statements that have Java-like semantics.

A complete Oat program contains a function called program with type (int, string[]) -> int, which takes command-line arguments like the C main function and is the entry-point of the executable. The file runtime.c defines the Oat standard library, which provides a few universally available functions, mostly for doing I/O and working with strings.

Global values:
Oat supports globally-declared variables with a limited set of initializers, including just base values (integer and boolean constants and null) and array literals. Unlike LLVM, Oat global initializers can't contain identifiers that refer to other global values.

Expression forms:
Oat supports several forms of expressions, including all the usual binary and unary operations. Boolean values are true and false. Integer values have type int and they are 64-bits. Oat uses different syntax to distinguish boolean logical operations b1 & b2 (and) and b1 | b2 (or) from bit-wise int operations i1 [&] i2 (bitwise or) and i1 [|] i2 (bitwise or). (This difference from a C-like language is necessitated by the lack of casts and overloading.)

Arrays:
Oat supports arrays whose elements are all of the same type, which could be any type, including nested arrays. Arrays are considered to be reference types. The expression new typ [len] creates a new default-initialized array of length len. In this case, typ must be either int or bool. Each element of an integer array will be set to 0, boolean arrays will be set false.

Explicitly-initialized arrays, have a length determined at compile time, and are written using braces with a comma-seperated enumeration of array elements. They can appear as expressions declared inside a function, and, unlike default-initialized arrays, may contain reference types:

  var vec = new int[]{1, -2, 3+1, f(4)};       /* vec has length 4 */
  var strs = new string[]{"a", "b", "c"};      /* strs has length 3 */
  var matrix = new int[][]{new int[]{1, 2, 3},
                           new int[]{4, 5, 6}};  /* an array of arrays */
  

or as global explicitly-initialized arrays (which can only use constant values):

  global arr = int[]{1, 2, 3, 4};
  

Arrays are mutable, and they can be updated using assignment notation: vec[0] = 17. Array indices start at 0 and go through len - 1, where len is the length of the array. Oat arrays (unlike C arrays) also store a length field to support array-bounds checks, which we will add in a future project. For this project, you do not have to implement bounds checking.

Arrays in Oat are represented at the LL IR level by objects of the LL type {i64, [0 x t]}*, that is, an array is a pointer to a struct whose first element is an i64 value that is the array's length, and whose second component is an array of elements of type t. See the translation of Oat types into LL types via the cmp_ty function.

This array representation is similar to that used in OCaml or Java, which do not allow "inlined" multidimensional arrays as in C. We choose this representation to facilitate array-bounds checking (which we will implement in a later HW). The length information is located before the 0th element of the array. For example, the following array would be represented as a pointer to memory as shown below:

  int[]{11,12,13,14};
  
  arr --+
        |
        v
       [4][11][12][13][14]
  

We will exploit this array representation that includes length data in the next assignment, when we use a type system to make it a safe language.

Left-Hand-Side Expressions: As usual in imperative languages, local and global identifiers denote mutable locations, they can also appear to the left of an assignment operation. In the example below, the identifier x appears in both ways:

  x = x + 1;
  

On the right-hand-side of the assignment, x is implicitly dereferenced to obtain its value, whereas on the left hand side, it stands for the location where the value of x is stored. For example, in our LLVMlite IR, each Oat local identifier will correspond to an alloca'd value on the stack, accessed through a pointer.

Similarly, the ith array index denotes both the value stored in the array and the corresponding location in memory.

  myarr[i] = myarr[i] + 1;
  

In this case, myarr can be an arbitrary expression that evaluates to an array, including function calls or an index into an array of arrays. For example the code below shows that it is legal to index off of a function call expression, as long as the function returns an array.

int[] f(int[] x, int[] y, bool b) {
  if ( b ) {
    return x;
  } else {
    return y;
  }
}

global x = int[]{1, 2, 3};
global y = int[]{4, 5, 6};

int program (int argc, string[] argv) {
  f(x, y, true)[0] = 17;     /* non-trivial lhs */
  var z = f(x, y, true)[0] + f(y, x, false)[0];
  return z;  /* returns the value 34 */
}
  

Strings:
Oat supports C-style immutable strings, written "in quotes". For the moment, the string operations are very limited and mostly provided by built-in functions provided by the runtime system. Strings are considered to be reference types because they are represented by a pointer to some byte sequence. Therefore they cannot be used in implicitly-initialized arrays (we'll address this infelicity in HW5). Note that the type string[] makes sense in Oat v.1, and it means an array of strings, none of which is null. The only way to get a value of such a type in Oat v.1 is as an input to the toplevel program.

Built-in Functions:
We now have enough infrastructure to support interesting built-in operations, including:

• string_of_array : (int[]) -> string
Assumes each int of the array is in the range 0-127 and therefore represents an ASCII character.
• array_of_string : (string) -> int[]
• print_string : (string) -> void
• print_int : (int) -> void
• print_bool : (bool) -> void

These built-in operations, along with some internal C-functions used by the Oat runtime are implemented in runtime.c.

Task I: Lexing and Parsing

The first step in implementing the frontend of the compiler is to get the lexer and parser working. We have provided you with a partial implementation in the lexer.mll and parser.mly files, but the provided grammar is both ambiguous and missing syntax for several key language constructs. Complete this implementation so that your frontend can parse all of the example hw4programs/*.oat files.

The full grammar is given in the Oat v.1 Language Specification.

You need to:

1. Add the appropriate token definitions to parser.mly and adjust lexer.ml.
2. Complete the parser according to the full grammar.
3. Disambiguate any parse conflicts (shift/reduce or reduce/reduce) according to the precedence and associativity rules.

Missing constructs include:

• all of the binary operations except +, -, *, and ==
• the boolean type and values
• default-initialized and implicitly-initialized array expressions and array global initializers
• string literal expressions and global initializers
• for loops

    ./main.native -S --print-oat file.oat
    

Task II: Frontend Compilation

The bulk of this project is implemeting the compiler in frontend.ml.

The comments in that file will help you, but here is how we suggest you proceed:

1. Skim through the whole frontend.ml file to get a sense of its structure. It is arranged so that it mirrors the syntax described in the Oat v.1 Language Specification.

   To a first approximation, there is one compilation function for each nonterminal of the language syntax. The inputs to these functions are the static context and the piece of syntax (and its type) to be compiled. The output of such a function depends on which part of the program you are compiling: expressions evaluate to values, so their compilation function returns the code computing an operand; statements do not evaluate to values, but they do introduce new local variables, so their compilation function returns a new context and an instruction stream, etc.

2. Take a close look at the Ctxt to see how it represents the compilation contexts.
3. Begin by working on cmp_global_ctxt and cmp_gexp, though initially you can leave out arrays.
4. Next try to get a minimal cmp_fdecl working, producing an Ll.fdecl with the correct params and type.
5. Next handle the Ret case of cmp_stmt. Use the provided cfg_of_stream function to produce a non-empty function body in cmp_fdecl. At this point, you should be able to compile a program like hw4programs/easyrun1.oat.
6. Next implement boolean and integer values, Bop, and Uop cases of cmp_exp. Again, saving arrays for later.
7. Add support for the Decl statement and identifier expressions. Each local Oat variable will correspond to an alloca'd stack slot, which should be hoisted to the entry block of the function using the E() stream element constructor.
8. Add more statements. The If and While statements are very similar to what we've seen in the lecture code. You can do for in several ways, but one easy way is to translate it at the abstract syntax level to a block of code that uses a while loop. The SCall statement isn't that different from the expression form; you might want to find a way to have them share code.
9. Revisit the whole compiler adding support for arrays, following the same order as above.

Testing and Debugging Strategies

The test harness provided by main.ml gives several ways to assess your code. See the README file for a full description of the flags.

Graded Test Cases

As part of this project, you must post an interesting test case for the compiler to the course Piazza site. This test case must take the form of a valid .oat (v.1) file along with expected input arguments and outputs (as found in the hard tests of gradedtests.ml).

The test case you submit to Piazza will not count if it is too similar to previously-posted tests! Your test should be distinct from prior test cases. (Note that this policy encourages you to submit test cases early!)

We will validate these tests against our own implementation of the compiler (and clang). A second component of your grade will be determined by how your compiler fairs against the test cases submitted by the other groups in the class.

Grading

Your team's grade for this project will be based on:

• 90 Points: the various automated tests that we provide.
• 5 Points for posting an interesting test case to Piazza. (Graded manually.)
• 5 Points divided among the test cases created by other groups. (Graded manually.)