compiler-construction - 使用实时变量分析计算工作列表

Question

我正在努力计算 worklist算法，我不想实现迭代算法，因为它需要很多冗余步骤。

我用来计算实时变量工作列表的算法如下

任何人都可以为下面给出的示例向我解释一下，初始工作列表是什么以及工作列表算法将如何应用于此？

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

我只为 In[n] block 计算了这么多方程，除此之外我不知道如何构建工作列表，我应该将哪些节点插入其中以及何时从工作列表中删除特定节点以便最后让它为空。

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 {  }

我正在使用 Nilson's Algorithms chap-6理解这个概念。这里他们给出了达到定义的解释(slide 15)，但我对工作列表的实时变量分析很感兴趣。

Answer 1

让我在您的示例中解释上述算法的工作原理。

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

最终值:

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

在block 1计算的'x'的值不是活的(之后没有用到，可以删除)