dcc888's Introduction

Introduction to Static Program Analyses

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.

Building and Running

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:

Control-Flow Graphs

In this lab, the student will create simple control-flow graphs using a toy, assembly-like, programming language.

Parsing

In this lab, the student will create a small parser that will convert text files into control-flow graphs.

Data-Flow Analysis

In this lab, the student will implement liveness analysis and run this implementation onto our toy language.

Worklist Algorithms

In this lab, the student will implement a worklist-based solver for dataflow analyses.

Dominators

In this lab, the student will implement a data-flow analysis to compute the dominance tree of a program.

Semantics of Phi-Functions

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.

Constant Propagation

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.

Alias Analysis

In this lab, the student will implement a version of Andersen-style Alias Analysis, following the lecture notes seen in class.

Type Checking

In this lab, the student will implement Type-Checking to verify if programs are Safe, as seen in class

Register Allocation by coloring chordal graphs

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

dcc888's People

Contributors

Stargazers

Watchers

dcc888's Issues

Python version constraint

I (think I) remember an earlier version of README stating the Python version was limited to 3.9 due to the labs being evaluated by Moodle. Is that still true? If so, I suggest adding a file .python-version at the root of the repo with the content:

3.9.18

(this creation can also be done with pyenv local 3.9.18)

This file is used by pyenv, which many people use to manage their locally installed python versions. I can open a PR with the change if there's agreement on this.

Note: It doesn't interfere with people that don't use pyenv

Users with pyenv would need to pyenv install 3.9.18. Then, with the simple existence of this file (assuming pyenv was correctly set up in the shell), the python version inside the project (and all subdirectories) should resolve to 3.9.18. To verify it, run: python --version after the above (it works even without a virtualenv).

I'd still recommend¹ running python -m venv .venv from the root of the repo after the above is done and verified, but that's just an extra layer of env isolation, in case 3.9.18 is used by other projects.

¹: If a .venv is created, it needs to be activated with source .venv/bin/activate. This has to be executed for every shell ("terminal"). That includes the one that created it, as well as new ones. Note: some IDEs can be configured to activate a virtualenv automatically when opening terminals (PyCharm is one).

Recommend Projects

pronesto / dcc888 Goto Github PK