Problem 4 - Compilation

Answer the following questions.

#1#2#3#4#5@font20 #3#4#5

1.

Find all live variables at each of heads and tails of B1, B2, B3, and B4.

2.

Point out a loop invariant formula. What is the result of extracting it to outside of the loop?

3.

Point out a copy sentence which is copy-transferable, and describe the results after copy-transfer.

1.

We call the set of live variables at the head of block $B$ and the set of live variables at the tail of block $B$. is the set of variables that will receive for sure a value inside $B$ before being used inside $B$. is the set of variables that may be used inside $B$ without having been assigned inside $B$.

A variable is a live variable at the head of a block if it is used inside block before being reassigned or if it is live at the tail of the block without having been reassigned inside the block. A variable is a live variable at the tail of a block if and only if it is live at the head of one of the following blocks.

#1#2#3#4#530 #3#4#5

To analyse the live variables, we can use the following method:

block $B$ do

repeat

block $B$ do

until all the converge

From this algorithm, we deduce the following table:

	B0	B1	B2	B3	B4
head	x	x,y,z	w,x,z	w,x,z	t,x,y
tail	x,y,z	w,x,z	w,x,z	t,x,y,z	t,x,y,z

2.

Let's consider the intern loop involving only block B4. The value of $z$ is an invariant since the values of both $t$ and $y$ are not affected when going through the loop. We can extract that assignement outside of the block so that we'll save the time needed to execute that instruction.

3.

Let's consider blocks B0, B3, and B4. and are copy instructions. As no change to the $z$ value occurs between blocks and , we can delete the first one and replace $z$ with 0 in the second one. We have propagate the copy and delete one useless instruction (which is not much, since it is not involved in any loop). We can even go further by suppressing $t$ from all the blocks because it is just used in block B4 as a reference (to 0). Now, we see that $z$ is just a copy of $y$ that is used afterward. It seems that this variable can be deleted as well.