LARA

Code generation

Introduction

Welcome to the last common assignment for the Amy compiler. At this point, we are finally done with the frontend: we have translated source programs to ASTs and have checked that all correctness conditions hold for our program. We are finally ready to generate code for our program. In our case the target language will be WebAssembly.

WebAssembly is “a new portable, size- and load-time-efficient format suitable for compilation to the web” (http://webassembly.org). WebAssembly is designed to be called from JavaScript in browsers and lends itself to highly-performant execution.

For simplicity, we will not use a browser, but execute the resulting WebAssembly bytecode directly using nodejs which is essentially a standalone distribution of the Chrome browser's JavaScript engine. When you run your complete compiler (or the reference compiler) with no options on program p, it will generate four different files under the wasmout directory:

  • p.wat is the wasm output of the compiler in text format. You can use this representation to debug your generated code.
  • p.wasm is the binary output of the compiler. This is what nodejs will use. To translate to the binary format, we use the wat2wasm tool provided by the WebAssembly developers. For your convenience we have included it in the bin directory of the skeleton. Note that this tool performs a purely mechanical translation and thus its output (for instance, p.wasm) corresponds to a binary representation of p.wat.
  • p.js is a JavaScript wrapper which we will run with nodejs and serve as an entrypoint into your generated binary.

To run the program, simply type nodejs wasmout/p.js

Installing nodejs

  • You can find directions for your favorite operating system here or here. You should have nodejs 8 or later (run nodejs --version to make sure).
  • After you install, run npm install deasync at the directory you plan to run amyc, i.e. the toplevel directory of the compiler.
  • Make sure the wat2wasm executable is visible, i.e. it is in the system path or you are at the toplevel of the amyc directory.

WebAssembly and Amy

Look at this presentation for the main concepts of how to translate Amy programs to WebAssembly.

You can find the annotated compiler output to the concat example here.

The assignment code

Overview

The code for the assignment is divided into two directories: wasm for the modelling of the WebAssembly framework, and codegen for Amy-specific code generation. There is a lot of code here, but your task is only to implement code generation for Amy expressions within codegen/CodeGen.scala.

  • wasm/Instructions.scala provides types that describe a subset of WebAssembly instructions. It also provides a type Code to describe sequences of instructions. You can chain multiple instructions or Code objects together to generate a longer Code with the <:> operator.
  • wasm/Function.scala describes a wasm function.
    • LocalsHandler is an object which will create fresh indexes for local variables as needed.
    • A Function contains a field called isMain which is used to denote a main function without return value, which will be handled differently when printing, and will be exported to JavaScript.
    • The only way to create a Function is using Function.apply. Its last argument is a function from a LocalsHandler to Code. The reason for this unusual choice is to make sure the Function object is instantiated with the number of local variables that will be requested from the LocalsHandler. To see how it is used, you can look in codegen/Utils.scala (but you won't have to use it directly).
  • wasm/Module.scala and wasm/ModulePrinter.scala describe a wasm module, which you can think of as a set of functions and the corresponding module headers.
  • codegen/Utils.scala contains a few utility functions (which you should use!) and implementations of the built-in functions of Amy. Use the built-ins as examples.
  • codegen/CodeGen.scala is the focus of the assignment. It contains code to translate Amy modules, functions and expressions to wasm code. It is a pipeline and returns a wasm Module.
  • codegen/CodePrinter.scala is a Pipeline which will print output files from the wasm module.

The cgExpr function

The focus of this assignment is the cgExpr function, which takes an expression and generates a Code object. It also takes two additional arguments: (1) a LocalsHandler which you can use to get a new slot for a local when you encounter a local variable or you need a temporary variable for your computation. (2) a map locals from Identifiers to locals slots, i.e. indices, in the wasm world. For example, if locals contains a pair i → 4, we know that get_local 4 in wasm will push the value of i to the stack. Notice how locals is instantiated with the function parameters in cgFunction.

Skeleton

As usual, you can find the skeleton for this lab on Courseware. After merging it with your existing work, the structure of your project src directory should be as follows:

amyc
 ├── Main.scala               (updated)
 │
 ├── analyzer   
 │    ├── SymbolTable.scala
 │    ├── NameAnalyzer.scala
 │    └── TypeChecker.scala
 │
 ├── ast                         
 │    ├── Identifier.scala
 │    ├── Printer.scala
 │    └── TreeModule.scala
 │
 ├── codegen                  (new)      
 │    ├── CodeGen.scala
 │    ├── CodePrinter.scala
 │    └── Utils.scala
 │
 ├── parsing
 │    ├── ASTConstructor.scala
 │    ├── ASTConstructorLL1.scala
 │    ├── Parser.scala
 │    ├── Lexer.scala
 │    └── Tokens.scala
 │
 ├── utils
 │    ├── AmycFatalError.scala
 │    ├── Context.scala
 │    ├── Document.scala
 │    ├── Pipeline.scala
 │    ├── Position.scala
 │    ├── Reporter.scala
 │    └── UniqueCounter.scala
 │
 └── wasm                     (new)
      ├── Function.scala
      ├── Instructions.scala 
      ├── ModulePrinter.scala
      └── Module.scala

Deliverables

You have four weeks to complete this assignment.

Deadline: Tuesday, December 18th, 23:59

Please use the Courseware interface to submit your solution and get some preliminary feedback from our automated tests.