Быстрый расчет покорителей

Question

Говорят, что при преобразовании промежуточного кода в статической форме единого назначения,

1. Необходимо рассчитать доминаторов основных блоков

2. Несколько очевидный способ сделать это как неподвижная точка уравнений медленно

3. чтобы сделать это быстро, вам нужно использовать в достаточно сложной Lengauer-Tarján алгоритм

Я вижу первые два момента, но я не совсем понимаю, что касается третьего. В частности, есть ли какая-то причина, по которой вы не можете сделать это только в процессе вычисления дерева доминантного предзаказа? Я реализовал версию, что в JavaScript, и это, кажется, работает:

var domPreorder = []; 

function doms(b) { 
    b.children = []; 
    for (var c of b[b.length - 1].targets) 
     if (c.i == null) { 
      c.i = domPreorder.length 
      domPreorder.push(c) 
      b.children.push(c) 
      c.parent = b 
      doms(c) 
     } 
} 

f[0].i = 0 
domPreorder.push(f[0]) 
doms(f[0]) 

Есть некоторые недостатки этого метода, что я не вижу?

Answer 1

Хотя вычисление доминантов быстро и правильно действительно не тривиально, на практике существуют гораздо более простые алгоритмы, чем Ленгауэр-Тарьян, которые на практике бывают быстрыми или быстрыми (т. Е. По типам графиков потока управления, которые встречаются в большинстве программ), хотя наихудшая сложность звучит страшно. См .: Cooper, Keith D .; Харви, Тимоти J; и Кеннеди, Кен (2001). "A Simple, Fast Dominance Algorithm"

Answer 2

Ах, теперь я вижу, что простые методы не правильно обрабатывают графики потока управления, которые имеют произвольно много вилок и воссоединений. Вы должны быть в состоянии найти обход путей, и если вы хотите, чтобы код для этого был быстрым, вам нужно рассчитать и вспомнить полудоминаторы, а потом, похоже, вы в конечном итоге оказываетесь с Ленгауэр-Тарьяном или что-то похожее на подобные строки.