Step 7: Liveness Analysis and Register Allocation - Due Date: Dec. 3rd, 11:59pm

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

Liveness analysis is a data flow analysis that finds what variables are live after any statement. It is an any-path, backward flow analysis. We will perform liveness analysis at a per-basic-block level (i.e., we will compute liveness for each basic block independently)

Computing basic blocks

Basic blocks are straight line pieces of code. For each function in your program, you should identify the basic blocks in the function. Use the basic block identification algorithm we discussed in the lecture notes on loop optimizations. The easiest way to do this is to create a list for each basic block, and have the elements of that list contain the IR nodes in the basic block. Function calls do not break basic blocks: do not treat a function call as a branch instruction (so function calls can exist in the middle of basic blocks).

Liveness for basic blocks

For each IR node in a basic block, you should compute which variables (temporaries, local variables and global variables) are live. Use the procedure discussed in the register allocation notes: work backwards through the basic blocks, and as you process each statement, remove any variables that are defined, and add any variables that are used in the statement. A few important notes:

• At the end of each basic block (i.e., at the beginning of your liveness analysis), assume that all local variables and global variables are live. Assume that no temporaries are live.
• When a function is called, we do not know what the function we are calling might do. To be conservative, we must consider which variables a function may use, and which variables a function must define. For a function call IR node, assume that (a) any local variables passed as arguments are used; (b) all global variables are used; (c) the variable holding the return value is defined; (d) no other variables are defined.
• READ(x) defines x, and WRITE(x) uses x.

Register Allocation Algorithm

Use the bottom-up register allocation algorithm discussed in class. For each statement, you must ensure that the source operands are in registers, and that there is a register for the destination operand. Use the liveness information you computed to determine when it is safe to free registers, and when a dirty register needs to be stored back to memory (only when the variable in the register is live).

Testcases

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. Outputs coming soon! (though note that the functional behavior of these outputs is exactly the same as the outputs from previous steps)

• Test_Expression micro source
• Test_Adv micro source
• Fma micro source
• Factorial micro source
• Fibonacci micro source

Tiny Simulator

Please use the tiny simulator (for Linux 64bit) supporting only 4 registers for this step.