Блог

Я борюсь с вычислением алгоритма рабочего списка, я не хочу реализовывать итеративный алгоритм, поскольку он требует так много избыточных шагов.

Алгоритм, которому я следую для вычисления рабочего списка для переменных в реальном времени, выглядит следующим образом

Может ли кто-нибудь объяснить мне для примера, приведенного ниже, каким будет начальный рабочий список и как к нему будет применен алгоритм worklist?

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

Я вычислил эти многие уравнения только для блока In [n], кроме этого, я не понимаю, как создать рабочий список, какие узлы я должен вставить в него и когда я должен удалить определенные узлы из рабочего списка, чтобы сделать его пустым в конце.

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

Я использую главу 6 алгоритмов Нильсона, чтобы понять эту концепцию. Здесь они дали объяснение для достижения определения (слайд 15), но меня интересует анализ переменных в реальном времени для рабочего списка.

Позвольте мне объяснить работу приведенного выше алгоритма на вашем примере.

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

Значение ‘x’, вычисленное в блоке 1, не является текущим (не используется после, его можно удалить)