Skip to content

A Tiger compiler for a x64 target-machine, written in ML

Notifications You must be signed in to change notification settings

perezzini/blackMAMBO

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

blackMAMBO

A Tiger compiler, for a X64 target-machine, implemented in Standard ML, a "strict, statically typed functional programming language with modular structure".

About Tiger

Tiger is a simple, statically-typed, programming language defined in Andrew W. Appel's book Modern Compiler Implementation in ML. You can find a fine specification from NYU.

Platform

Linux

Compiler Phases

  • Lex. Break the source file into individual words, or tokens.
  • Parse. Analyze the phrase structure of the program.
  • Semantic Actions. Builda a piece of abstract syntax tree corresponding to each phrase.
  • Frame Layout. Place variables, function-parameters, etc, into activation records (stack frames) in a machine-dependent way.
  • Translate. Produce intermediate representation trees (IR trees), a notation that is not tied to any particular source language or target-machine architecture.
  • Canonicalize. Hoist side effects out of expressions, and clean up conditional branches, for the convenience of the next phases.
  • Instruction Selection. Group the IR-tree nodes into clumps that correspond to the actions of target-machine instructions.
  • Control Flow Analysis. Analyze the sequence of instructions into a control flow graph that shows all the possible flows of control the program might follow when it executes.
  • Liveness Analysis. Gather info about the flow of info through variables of the the program: calculates the places where each program variable holds a still-needed value (is live).
  • Register Allocation. Choose a register to hold each of the variables and temporary values used by the program; variables not live at the same time can share the same register.
  • Code Emission. Replace the temporary names in each machine instruction with machine registers.

Usage

First of all:

  1. Clone repo.
  2. Download and install Moscow ML. Moscow ML is a "light-weight implementation of Standard ML (SML), a strict functional language used in teaching and research".
  3. Open Makefile from blackMAMBO, and update HOME path with the path where you installed Moscow ML.
  4. Open a terminal, change directory to blackMAMBO folder, do the following: make clean && make depend && make

Now, let's say you want to compile a Tiger program program.tig. The simplest way to carry out this operation is by doing the following: ./tiger program.tig.

There exist several options available to display information when compiling a Tiger program using blackMAMBO: ./tiger -option program.tig, where option can be

  • ir: displays IR-tree.
  • canon: displays canon code.
  • liveout: displays live-out info in an instruction-graph way.
  • assembly: displays program assembly.

Bibliography

Modern Compiler Implementation in ML, Andrew W. Appel.

More Info

  • Compilers final class project. Computer Science. National University of Rosario.
  • Some code comments are written in Spanish, although the majority of them are written in English. Sorry about that.

Yes! I did it! 🤘

Project presented on December 6, 2017. National University of Rosario