Part 2 : Compiling the IMP language

MAIN TASK

You have to complete the two files liveness.ml and linearscan.ml, and adapt the file imp2mips.ml to build an optimizing IMP to Mips compiler.
Look for failwith "not implemented" or TODO to identify places where
something must be added or modified.

Altenatively, you can mix these additional elements with your current project.

BONUS TASKS

You may implement any of these suggested extensions, or add your own.

• The current version of imp2mips fails when compiling an expression that requires more registers than the 10 temporaries available.
  Extension: add a mechanism to use the stack instead.
• In the simplest version of the allocator, each spilled variable is given a separate slot on the stack.
  Extension: manage spilled variables with a second stage of linear scan allocation, which allows reusing the stack slots that are not needed anymore.
  Remark: this does not require a second pass of the allocator. Adding code to the case where a variable is spilled (and appropriate global data of the allocator) is enough. Difference of this second stage with respect to the first one: the set of available slots on the stack is unlimited.
• The current version of imp2mips passes all function arguments on the stack.
  Extension: use registers $a0 to $a3 for the first four parameters, and the stack only starting from the fifth parameter.
  Remark: at the very least, these registers have to be saved/restored at the appropriate point of each function call. Their contents can also be considered as a local variable that is managed by the allocator.
• Liveness analysis allows to identify "dead" [set] instructions, that is instruction that set a variable with a value which will surely never be used.
  Extension: add a pass that remove these dead instructions.
  Remark: you should not remove a set to a dead variable if the instruction itself contains another possibly visible side-effect.
• The current version of imp2mips manages separately the registers for the intermediate values of the computation of an expression and for the local variables.
  Extension: add a pass that flatten all expressions and explicitely uses local variables for intermediate values. Then use only one allocation for all these variables.
• Replace linear scan allocation with graph coloring allocation.

SKELETON

Archive file with a project skeleton
The directory contains

• Language definition :
  • implexer.mll, impparser.mly : description of the concrete syntax, generating a parser using ocamllex and menhir
  • imp.ml : description of the abstract syntax trees and an interpreter
• Generating MIPS assembly
  • mips.ml : library for generating mips assembly 
  • imp2mips.ml (to be completed) : basic translation to MIPS code
• Register allocation
  • nimp.ml : abstract syntax trees for programs with numbered instructions
  • liveness.ml (to be completed) : skeleton for liveness analysis
  • linearscan.ml (to be completed) : skeleton for linear scan allocation
• Main files
  • impi.ml : parses a IMP file given as argument and evaluates the main function in the file with a parameter given as the second argument
  • impc.ml : parses a IMP file given as argument and generates MIPS assembly code in a file with extension .asm which computes the value of the main function in the file with a parameter given as the second argument

Additional tests should appear in the tests directory.