Lab for Automated Reasoning and Analysis LARA

Code generation


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 final code for our program. What we choose as our target language is WebAssembly.

WebAssembly “is a new portable, size- and load-time-efficient format suitable for compilation to the web” ( WebAssembly is designed to be called from JavaScript in browsers to efficiently implement high-performance functionality.

In our case, for simplicity we will not use a browser, but instead nodejs, which is essentially the js engine of Chrome distributed as a standalone tool. 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. Use it to debug (or marvel at) 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 a translator provided by the wasm developers which we distribute under the bin directory in our compiler.
  • p.js is the js wrapper which we will run with nodejs.
  • p.html should be an html wrapper to use in a browser, but is unfortunately currently not functional.

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


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 one is 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 essentially contains a few functions and the 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 we encounter a local variable, or you need a temporary variable for your computation. (2) a map from Identifiers to locals slots 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.


As usual, merge the stubs of the parser into your main branch by typing

git fetch --all

git merge origin/Lab06

(assuming that origin is the name of your remote repository).

The structure of your project src directory should be as following:

 ├── 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
 ├── interpreter                     
 │    └── Interpreter.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


You can deliver this assignment after the midterm.

Deadline: Friday 22 December, 23:59

IMPORTANT: Please remember to deliver the commit you want us to grade under

cc17/labs_06.txt · Last modified: 2017/12/06 09:12 by manos