In this step, we will implement liveness analysis and apply it to register allocation algorithm to avoid unnecessary spilling of variables if the variable is dead.
Liveness analysis is a data flow analysis that finds what variables are live after any statement. It is an any-path, backward flow analysis. Since we don't have inter procedural analysis, we have to be conservative and assume all global variables are live, all parameters are live at a function call, and all variables returned by a function are live in that function.
A control flow graph is needed for data flow analysis since we need predecessor and successor node information. Micro language does not have any irregular control flow. All control structures (if/while) are regular.
For each statement, we need to maintain two data structures, the "Gen" set and "Kill" set. "Gen" set is the set of variables that may be used (read) by a statement and "Kill" set is the set of variables that must be defined by a statement.
You must perform an intraprocedural liveness analysis on every function in your program
We discussed two register allocation algorithms in class, bottom-up register allocation (which is performed on a per-basic-block basis) and graph coloring (which is performed on a per-procedure basis). 468 students can choose either approach to register allocation. 573 students must use graph coloring and perform register allocation across an entire procedure (this includes rewriting code to implement spills).
Your compiler should also provide a way to turn liveness analysis on and off. If flag "-live" is given, the liveness analysis and register allocation should be applied. Otherwise, it should output original tiny code. For 573 students: at the beginning of each function, emit the interference graph generated for your analysis of that function. The format should be as follows:
Var/Temp name: List of vars/temps that interfere with this var/temp
All test case output has control flow information included. This is just a set of outputs from one possible implementation so your output may be different.
Please use the tiny simulator (for Linux 64bit) supporting only 4 registers for this step.