Erratum : liveness analysis

We specify a function $lvin$ which takes as argument an instruction $i$ or a sequence of instructions $s$ (implemented by 2 different Caml functions) and a set $lvout$ of variables alive at the end of the instructions and computes the variables alive before the instructions.

We are only considering local variables in the body of a function definition

We have as explained in the document instructions.txt :

The difficulty comes from while loop, the value given in the instructions.txt file is not correct.

The correct value for livin(while($e$){$s$},$lvout$) is $U(e) \cup lvout \cup lvin(s, \emptyset)$

• all variables in $lvout$ are alive before the while loop is executed because of the execution path where the body of the loop is not executed
• it is easy to show that the data-flow equation with $I$ denoting lvin(while(e){s},lvout) is $I=U(e) \cup lvout \cup lvin(s, I)$. We start the iteration with $I_0=\emptyset$ and show that the fixpoint is reached in one pass.

Computing the variables alive in the body of the loop :

• the variables alive after executing the body of the loop are the one alive at the beginning of the loop instruction. So we need to compute $lvin(s, I)$ with $I$ the set computed above of the variables alive before the loop.
• we need to be careful on the complexity of the procedure : if we have 3 imbricated loops, and each time we have a loop with body $s$ we compute both $lvin(s, \emptyset)$ to obtain $I$ and then $lvin(s, I)$, the fonction lvin will be applied 8 times on the deeper loop body, we will end up with an exponential complexity !