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

0602bba Â· Dec 18, 2018
Aug 27, 2017
Dec 6, 2017
Nov 23, 2017
Dec 3, 2017
Dec 18, 2018
Dec 4, 2017
Sep 12, 2017
Nov 23, 2017
Oct 4, 2017
Oct 4, 2017
Nov 1, 2017
Dec 2, 2017
Aug 30, 2017
Aug 30, 2017
Dec 3, 2017
Dec 4, 2017
Aug 30, 2017
Aug 30, 2017
Aug 30, 2017
Oct 20, 2017
Sep 27, 2017
Aug 30, 2017
Aug 30, 2017
Nov 18, 2017
Nov 28, 2017
Dec 6, 2017
Aug 30, 2017
Aug 30, 2017
Aug 30, 2017
Sep 27, 2017
Sep 27, 2017
Aug 30, 2017
Nov 29, 2017
Dec 6, 2017
Aug 30, 2017
Dec 4, 2017
Oct 20, 2017
Nov 8, 2017
Nov 8, 2017
Nov 18, 2017
Nov 18, 2017
Oct 11, 2017
Aug 30, 2017
Nov 30, 2017
Oct 11, 2017
Dec 3, 2017
Oct 7, 2017
Nov 28, 2017
Nov 28, 2017

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