For the following problems, consider the following piece of three-address code 1. READ (A) 2. READ (B) 3. C=A+B 5, B=C*D 7. T2 = T1 + C 8, F=A+B 11, T3 = F + B 12. WRITE(T3) 1. Perform liveness analysis on this piece of code, assuming that it is the entire code of the program. Show which variables are live after each of the statements in the program 2. For the next two subproblems, we will perform register allocation using bottom-up register allocation as presented in the notes. READ(X) defines the value of X (i.e., it assigns to X). WRITE(X) reads the value of X to write it out to the screen Show what code would be generated for each 3AC instruction. Use LOAD X Rx to load from a variable/temporary into a register, STORE Rx X to store from a register into a variable/temporary, Rx - Ry + Rz for addition, and Rx - Ry * Rz for multiplication When choosing registers to allocate, always allocate the lowest-numbered register available. When choosing registers to spill, choose the non-dirty register that will be used farthest in the future. In case all registers are dirty, choose the register that will be used farthest in the future. In case of a tie, choose the lowest-numbered register. If a load or store is the result of a spill (kicking a value out of a register earlier than required, or loading one of those values back into the register), indicate that. Perform register allocation for a machine with 4 registers. Perform register allocation for a machine with 3 registers 3. Assume you have a machine with 2 ALUs (ALU0 and ALU1) and one LD/ST unit. Your instruction set consists of 5 instructions: ADD, MUL, LOAD and STORE. An ADD instruction can be performed on either ALU, and takes one cycle. A MUL For the following problems, consider the following piece of three-address code 1. READ (A) 2. READ (B) 3. C=A+B 5, B=C*D 7. T2 = T1 + C 8, F=A+B 11, T3 = F + B 12. WRITE(T3) 1. Perform liveness analysis on this piece of code, assuming that it is the entire code of the program. Show which variables are live after each of the statements in the program 2. For the next two subproblems, we will perform register allocation using bottom-up register allocation as presented in the notes. READ(X) defines the value of X (i.e., it assigns to X). WRITE(X) reads the value of X to write it out to the screen Show what code would be generated for each 3AC instruction. Use LOAD X Rx to load from a variable/temporary into a register, STORE Rx X to store from a register into a variable/temporary, Rx - Ry + Rz for addition, and Rx - Ry * Rz for multiplication When choosing registers to allocate, always allocate the lowest-numbered register available. When choosing registers to spill, choose the non-dirty register that will be used farthest in the future. In case all registers are dirty, choose the register that will be used farthest in the future. In case of a tie, choose the lowest-numbered register. If a load or store is the result of a spill (kicking a value out of a register earlier than required, or loading one of those values back into the register), indicate that. Perform register allocation for a machine with 4 registers. Perform register allocation for a machine with 3 registers 3. Assume you have a machine with 2 ALUs (ALU0 and ALU1) and one LD/ST unit. Your instruction set consists of 5 instructions: ADD, MUL, LOAD and STORE. An ADD instruction can be performed on either ALU, and takes one cycle. A MUL
