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 at the end of a basic block. 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/for) are regular.
For each basic block, we need to maintain two data structures, the "Gen" set and "Kill" set. "Gen" set is the set of variables that is used (read) in a basic block and "Kill" set is the set of variables defined in a basic block.
The register allocation algorithm will be applied to each basic block. All the registers that contain live variables should be spilled (saved in memory) at the end of each basic block.
Your compiler should also provide a way to turn liveness analysis on and off. If flag "-live" is given, the liveness analysis should be applied. Otherwise, it should output original tiny code.
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.