Assignment 5: Optimization and Register Allocation🔗

Due: Sun 04/20 at 11:59pm

git clone

In this assignment, you will improve the performance of your compiled Diamondback code by implementing two optimizations:

• Register allocation

• Elimination of integer type assertions

Each of these optimizations is based on a corresponding analysis:

• Liveness Analysis to determine the interference graph for register allocation

• Possible Values Analysis to determine if a value is guaranteed to be a (tagged) integer.

To support these analyses, the SSA datatypes have been extended with a new generic type parameter Ana, standing for "Analysis", with every program point containing an element of this type.

1 Register Allocation🔗

The incorporation of register allocation into the compiler is broken down into several tasks:

• Liveness Analysis

• Construction of the interference graph and the perfect elimination ordering

• Coloring the interference graph using Chaitin’s algorithm

• Adapting code generation to use the provided coloring

You will implement the first three of these in backend.rs. The Emitter has already been extended to us the output of the prevoius passes.

1.1 Liveness Analysis🔗

Liveness analysis is implemented as methods in the LivenessAnalyzer. The liveness analysis is an iterative reverse dataflow analysis. The LivenessAnalyzer struct contains two fields previous and current which keep track of what variables are live in each basic block in the program. You need to implement the LivenessAnalyzer::analyze_prog method, which fills in the liveness information for the program, using previous as a starting point, and updating the information for the basic blocks in current.

1.2 Conflict Analysis and Elimination Ordering🔗

The output of the liveness analysis feeds into the ConflictAnalysis. This traverses a program annotated with liveness information and constructs two pieces of data: an interference graph and a perfect elimination order of the vertices. The interference graph should include all in the program that are subject to register allocation1The only variables not subject to register allocation are function block parameters and extern parameters as vertices, and an edge if the variables cannot be assigned to the same register. The perfect elimination ordering is an ordering of all of these variables in the program. A perfect elimination order can be constructed by ordering the variables in scope/dominance order: if x is already in scope when y is defined, then x should occur earlier than y in the ordering.

1.3 Graph Coloring🔗

The final step of the register allocation is graph coloring, implemented in the RegisterAllocator struct. This contains fields for the register assignment you are constructing as well as the next available spill offset. You will implement the graph coloring algorithm in RegisterAllocator::chaitin described in class, removing the nodes from the graph and recursively coloring the sub-graph before adding the node back and coloring it.

2 Assertion Removal🔗

The second optimization we perform is type assertion removal. Specifically, we are removing assertions of the form AssertInt(imm) when we can be sure at runtime that imm is a tagged integer, i.e., that it is even. For simplicity, the analysis you implement is an intraprocedural analysis, meaning we assume that any function call, whether to external or internal functions, can always produce arbtitrary values.

The assertion removal optimization is implemented in middle_end.rs, and is run on the SSA code produced by Lowerer::lower_prog.

2.1 Possible Values Analysis🔗

The possible values analysis is a forward dataflow analysis based on a lattice of PossibleValuesEnvironments. A PossibleValuesEnv is a finite map from variables to PossibleValues, where a PossibleValues is an abstraction of a set of possible 64-bit integers. The cases of PossibleValues are

• Any, representing the set of all possible 64-bit integer values

• Even, representing the set of even 64-bit integer values, i.e., the set of tagged integer values

• None, representing the empty set. This occurs when a variable is never set, which in our well-formed SSA IR can only happen in dead code.

These are ordered by subset inclusion: None is less than Even is less than Any. PossibleValuesEnvironments lift this ordering to maps: an environment e1 is less than an environment e2 if for every x |-> p1 in e1, x |-> p2 in e2 and p1 is less than p2. If the HashMap does not contain a key x, then this is considered equivalent to mapping x |-> None.

The possible values analysis assigns a PossibleValuesEnv to every program point by storing it in the ana fields of the constructors. This works by an iterative procedure: the program is initialized with the assumption that all variables are never set (x |-> None) and this is iteratively refined based on analyzing the program until reaching a fixed point.

The starter code provides much of the infrastructure of this analysis, in AssertionRemover::analyze, as well as the cases for function blocks, basic blocks and terminators. You need to complete the cases for BlockBody as well as lattice operations for PossibleValues and PossibleValuesEnv.

2.2 Assertion Removal🔗

After the program has been annotated with possible values information, the AssertionRemover::remove_assertions function you implement should traverse the program and remove assertions that are guaranteed to succeed by the dataflow analysis.

3 Updated Command Line Interface🔗

The command-line interface has been extended significantly to enable you to run your compiler with different optimizations and inspect intermediate states of your analyses.

There are two new flags that let you tune the optimizations:

• The -O flag lets you specify which optimizations to run. These include "ar" for your assertion removal pass, as well as "cp" (Copy Propagation) and "dce" (Dead Store Elimination/Parameter Dropping) that we have provided.

• The -R flag lets you specify what registers to use in register allocation. Setting this to "none" will spill all variables, similar to compilers for the previous assignments.

Additionally, there are new targets you can pass to -t to output the intermediate states of your register allocator.

4 Testing and Performance Evaluation🔗

As of the initial release, we have provided some extra public tests for stress testing your compiler. For example, we have provided a tail recursive loop example that in the reference solution exhibits a nearly 5x speedup when assertion removal and register allocation are implemented correctly. You can use this as a benchmark for performance evaluation.

The tests on the autograder do not test the performance directly, but rather the soundness and precision of your analysis:

• Tests for assertion removal test that remove exactly the assert ints that cannot fail at runtime, and do not otherwise change the code.

• Liveness and conflict tests check that you produce the correct interference graph.

• Graph coloring tests further check that you correctly color the generated interference graph.

The starter code includes some example public tests for each to help you get started.

5 Starter Code and Deliverables🔗

This assignment’s starter code includes a full implemtation of the frontend, and much of the scaffolding of the middle end.

For this assignment you will submit your updated versions of two files:

• src/middle_end.rs

• src/backend.rs

You can inspect src/ssa.rs to see how cases for analysis annotations have been added to the SSA AST, and src/ana.rs has been added which defines some types (LiveSet, Graph, Nil, and PerfectEliminationOrder) that are used in your analyses.

These are the only files that you can change in your submission, your code will be linked with reference versions of the other files.

We’ve included a script mk_submission.sh in the starter code repo that should make zip file with just those three files and your testing files that you should upload to gradescope. The testing files are included for us to get some idea of how students are testing their code, they are not graded.

6 Grading Standards🔗

Your compiler will be tested on the

• Soundness of your optimizations: you never assign conflicting variables the same register and you never remove assertions that may fail.

• Precision of your analyses: your analyses are effective at finding assertions that can be removed safely and your register allocation doesn’t spill excessively.

1The only variables not subject to register allocation are function block parameters and extern parameters