COS 320, Spring 2005. Programming Assignment 7

Programming Assignment 7: Liveness analysis and Interference Graph Construction


1) Copy /u/cos320/chap7/* into a new directory as7 using the command:

cp -r /u/cos320/chap7/* SOMEWHERE-IN-YOUR-HOME/as7


The goal of this assignment is to  implement liveness analysis and construct an interference graph for register allocation.  This assignment is based on chapter 10.2 of your textbook. Please read chapter 10 before starting. 

The objective of this assignment is to write the function interferenceGraph in liveness.sml

Probably the most difficult part of this assignment is understanding the various interfaces that you have to use to implement the function.  You will have to look through the interfaces of various modules (try to rely on the .sig interface files as opposed to the .sml implementations) that we have provided for you including table.sig, graph.sig, and Mips.sig.  There are some helpful hints in the file notes.txt.


You will have to devise testing mechanisms for testing interference graph construction yourself.  In liveness.sml, there is a function to print out your interference graph once you have constructed it.


To submit, go to and type

submit 7 liveness.sml README

The README should list your collaborators and explain any unusual assumptions or decisions you have made.