Calculating worklist with live variable analysis

Question

I am struggling with the calculation of the worklist algorithm, I do not want to implement the iterative algorithm as so many redundant steps it takes.

The algorithm I am following to calculate the worklist for live variables is as below

Can anybody explain to me for the example given below, what would be the initial worklist and how the worklist algorithm would be applied to this?

x = 1   /*block 1*/
y = 23  /*block 2*/
x = 100 /*block 3*/
print x+y /*block 4*/

I have calculated these many equations for In[n] block only, apart from this I am not getting how to construct a worklist, which nodes shall I insert into it and when shall I remove particular nodes from the worklist in order to make it empty at the end.

in[4] = use[4] U (out[4] - def[4])
   = {x, y} U { }
in[3] = use[3] U (out[3] - def[3])
   = { } U { y }
in[2] = use[2] U (out[2] - def[2])
   = { } U { y } - { y }
in[1] = use[1] U (out[1] - def[1])
   = { } U {  }

I am using Nilson's Algorithms chap-6 to understand this concept. Here they have given an explanation for reaching definition (slide 15), but I am interested in the live variable analysis for the worklist.

user_12199970 · Answer

Let me explain the working of above algorithm on your example.

Work list is a queue. initial values of in,out of all blocks are {}
Initial work list has blocks {1,2,3,4}
Remove the first element from the work list and compute
 out[1] = U in[succ(1)]  = in[2] = {}
 in[1]  = use[1] U { out[1]-def[1]} = {} U{{}-{x}} = {} No change in in[1]
Work list has {2,3,4}
Remove the first element from the work list and compute
 out[2] = U in[succ(2)] = in[3] ={}
 in[2]  = use[2] U {out[2]-def[2]} = {} U {{}-{y}} = {} No change in in[2]
Work list has {3,4}
Remove the first element from the work list and compute
 out[3] = U in[succ(3)] = in[4] = {}
 in[3] = use[3] U {out[3]-def[3]} = {}U{{}-{x}} = {} No change in in[3]
Work list has {4},
Remove the first element from the work list and compute
 out[4] = U in[nosucc] = {}
 in[4] = use[4] U {out[4] - def[3]} = {x,y} U {{}-{}} = {x,y} 
change in in[4]( previous value is empty, it has to be propagated to its   
predecessors)  add its predecessor to work list.
Work list has {3},
remove the first element from the work list and compute
 out[3] = U in[succ(3)] = in[4] = {x,y}
 in[3] = use[3] U {out[3]-def[3]} = {}U{{x,y}-{x}} = {y}
change in in[3]( previous value is empty, it has to be propagated to its 
predecessors)  add its predecessor to work list.   
Work list has {2}, 
remove the first element from the work list and compute
 out[2] = U in[succ(2)] = in[3] ={y}
 in[2]  = use[2] U {out[2]-def[2]} = {} U {{y}-{y}} = {} No change in in[2]
Work list is empty, it stops

Final values:

 out[4]={},  in[4]={x,y}
 out[3]={x,y}  in[3]={y}
 out[2]={y}     in[2]={}
 out[1]={}      in[1]={}

The value of 'x' computed at block 1 is not live(not used after, it can be eleminated)

Calculating worklist with live variable analysis

1 Answers