Генерация кода: сети зависимостей

[tyomitch]

* Для начала -- об обозначениях. То, что инструкция X использует регистр ix, производит регистр jx и получает регистр kx, будем обозначать "X ix/jx/kx" и называть разметкой инструкции. Стек будем обозначать st; так, если инструкция только лишь использует стек, то это обозначается "X st//".

Тогда наш код запишется следующим образом:

push A st//
push B st//
mov dx, C /dx/
sub [sp], dx st//dx
pop bx st/bx/
add [sp], bx st//bx
push D st//
mov ax, E /ax/
mul [sp] st,ax/dx/dx
mov [sp], ax st//ax
pop cx st/cx/
add [sp], cx st//cx

* Чтобы высокоинтеллектуально обрабатывать генерируемый код, кардинально изменим его представление: вместо обычного списка инструкций будем использовать сети зависимостей. Будем говорить, что инструкция А зависит от инструкции Б, если 1) в нашей записи кода А следует за Б (не обязательно непосредственно), и 2) некий регистр (либо стек) присутствует в разметках их обеих. Инструкции, связанные отношением зависимости, должны выполняться в определённом порядке; инструкции, не связанные этим отношением, могут выполняться "одновременно" (т.е. в любом порядке).

Теперь выполним операцию, обратную транзитивному замыканию: если А зависит от Б, а Б зависит от В, то исключим из рассмотрения зависимость А от В, если она есть (её может и не быть). После этого отношение зависимости задаст для инструкций [url=http://ru.wikipedia.org/wiki/Частично_упорядоченное_множество]строго частичный порядок[/url]. (Кстати, как эта обратная операция правильно называется по-русски? По-английски это, видимо, назвается transitive reduction)

Сеть зависимостей -- это сеть (ориентированный граф), содержащая инструкции программы как узлы и зависимости между ними как дуги. Изображать её мы будем в виде таблицы; горизонтальные границы между ячейками соответствуют дугам сети (а вертикальные нарисованы просто для красоты). Таким образом, в нашей таблице две инструкции связаны отношением зависимости, если их ячейки расположены одна над другой.

Вот сеть зависимостей нашей программы. Поскольку все инструкции, кроме двух, используют стек, то они выстроились "в линеечку". По мере того, как мы переводим промежуточные значения из стека в регистры, сеть будет становиться всё более и более параллельной.

(рисунок не слишком крупный? я не знаю, какое у кого разрешение)


* Наши дальнейшие действия будут заключаться в поиске в сети определённых пар инструкций, и замене их на другие инструкции. Сеть при этом будет перестраиваться.

Наши замены явно не указывают, как именно перестраивается сеть. Можно каждый раз получать её заново, из списка инструкций; а можно заметить, что зависимость двух инструкций осуществляется по одному из пяти "регистров" (ax,bx,cx,dx,st), и хранить для каждого узла сети пять указателей "вверх" и пять указателей "вниз". Тогда перестроение сети будет достаточно понятным образом сводиться к перевешиванию этих указателей.

Вот правила для наших замен: (правило 1 уже формулировалось; правила 2 и 3 различаются только разметкой последней инструкции)

1. push X st//; pop ix st/ix/ --> mov ix, X /ix/
2. op [sp], ix st//ix; pop jx st/jx/ --> pop jx st/jx/; op jx, ix jx//ix
3. mov [sp], ix st//ix; pop jx st/jx/ --> pop jx st/jx/; mov jx, ix /jx/ix
4. mul [sp] st,ax/dx/dx; pop ix st/ix/ --> pop ix st/ix/; mul ix ax/dx/dx,ix
5. mov ix, jx /ix/jx; op [sp], ix st//ix --> op [sp], jx st//jx
6. mov ix, X /ix/; op jx, ix jx//ix --> op jx, X jx//

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

[tyomitch]

ап! пост существенно исправлен и дополнен.

[GSerg]

http://lingvo.yandex.ru/en?text=transit ... ranslate=1