This repository holds some of the project assignments used in DCC888 - Introduction to Program Analysis, a course offered by the Department of Computer Science of the Federal University of Minas Gerais, as part of the courses of UFMG's Compilers Lab. For the course material, check its website. A full list of the topics covered is available in the syllabus.
This webpage contains a few labs: short project assignments. In practice, these assignments are automatically graded using UFMG's Moodle.
However, the labs can be used independently.
They are all implemented in Python.
Each program contains lots of doctests.
Thus, to test, say, your implementation of dataflow.py, just do:
python3 -m doctest dataflow.py
Additionally, most of the labs contain a folder called tests, with some text files that you can run using the main routine, in driver.py, e.g.:
python3 driver.py < tests/fib.txt
The following labs are available:
In this lab, the student will create simple control-flow graphs using a toy, assembly-like, programming language.
In this lab, the student will create a small parser that will convert text files into control-flow graphs.
In this lab, the student will implement liveness analysis and run this implementation onto our toy language.
In this lab, the student will implement a worklist-based solver for dataflow analyses.
In this lab, the student will implement a data-flow analysis to compute the dominance tree of a program.
In this lab, the student will add phi-functions to our toy three-address code language, so that we can write programs in Static Single-Assignment Form.
In this lab, the student will implement the sparse data-flow equations for constant propagation. The student will use the results of this analysis to remove some instructions (those whose value can be computed at compilation time) from the program.
In this lab, the student will implement a version of Andersen-style Alias Analysis, following the lecture notes seen in class.
In this lab, the student will implement Type-Checking to verify if programs are Safe, as seen in class
In this lab, the student will build and color the interference graph of programs in SSA-form using maximum cardinality search and greedy coloring. The resulting coloring represents the minimum register allocation without spilling, as seen in SSA-Based Register Allocation