Граф зависимостей

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

Рассмотри пример:

0    beg
1    mov $1 -> V1
2    mov $2 -> V2
3    mov $3 -> V3
4    cmp p1, p2 = V1,V2
5    (p1)add V1,V2->v4
6    (p2)add V2,V3->V4
7    (p1)mul V4,$10 -> V5
8    (p2)mul V4,$20 -> V5
9    add V5,V5->V6
10    end

Инструкции i0:beg и i10:end удобно дописывать в начале и конце анализируемого кода, так как тогда те инструкции, которые ни от кого не зависят (например, инструкции i1, i2, i3), можно получить, как саксессоры beg'а и соответственно, предецессоры end'а(здесь, только одна инструкция i9) - инструкции, после выполнения которых, можно считать, что анализируемый участок кода закончился (то есть как раз тогда, когда может выполняться i10: end)

Для такого кода получаем следующий граф зависимостей:

depgraph1.JPG
Заметим, что граф избыточный, но нас сейчас это не волнует, поскольку в худшем случае наши алгоритмы будут работать медленнее и "съедать" больше памяти, и только. Для начала и такое было бы неплохо.

Также обратим внимание, что при выполнении I4 p1 и p2 не могут принимать одновременно значение 1 (disjoint), поэтому, например, I5 не зависит от I6. Как я понимаю, у нас будет таблица, в которой указано являются ли предикаты disjoint.

Впоследствие к каждой дуге можно будет "прицепить" время задержки (latency), взятое из машинной модели.

Мы будем различать несколько типов зависимостей:

  • FLOW (Read after Write)
  • OUTPUT (Write after Write)
  • ANTI (Write after Read)

Ресурсом зависимостей - это ресурс (регистр, предикат…), по которому происходит зависимость.

Соответственно различаем типы зависимостей:

  • REG_TYPE - зависимость по регистру
  • PREDCT_TYPE - зависимость по предикату
  • CONTROL_TYPE - нельзя одну инструкции выполнить после другой не нарушая поток управления(например, branch выполняется после инструкций следующих перед ним)
  • MEMORY_TYPE - зависимость с точки зрения ячейки памяти

Рассмотрим алгоритм для REG_TYPE .
Для каждого регистра заводим два списка def и use.
Проходим по инструкциям. Видим, что I1 пишет в V1 - записываем I1 в V1.def.
Аналогично проходим I2 ,I3 .
На I4 - видим, что используется V1. Записываем I4.cmp в V1.use Проходим по V1.def, и для каждой инструкции строим зависимость между ней и I4 . В нашем случаем dep(I1, I4, FLOW, REG_TYPE)
и т. д.

Список use будет полезен, чтобы строить OUTPUT-зависимости и ANTI-зависимости.
(Кстати, я что-то маленько запутался с ними. Было бы хорошо, если кто-нибудь напишет пример, где у нас точно возникает OUTPUT зависимость и ANTI-зависимость)

Как видим, весь алгоритм работает за один проход.

Про MEMORY-зависимости имеет смысл говорить, когда будет оконочательно построена defuse - трансляция.

Рассмотрим теперь следующий пример с branch'ами
depgraph2.JPG

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

cmp p5 = 1,0 //p5=0
mov ...->v1
mov ...->v2
cmp p1,p2 = v1,v2
(p1)mov v1->v3
(p1)cmp p3,p4 = v3,v1
(p3)br
(p2)cmp p5,p0 = 1,1 //p5=1
(p4)cmp p5,p0 = 1,1 //p5=1
(p5)mov v2->v3

Рассмотрим какие интересные зависимости у нас встречаются в связи с branch'ем.
branch нельзя перенести вверх из-за flow зависимости по p3
Но между branch'ем и последующими инструкциями у нас пока никакой зависимости не введено. В то же время понятно, что перенести branch, например, после mov'а мы не можем, не нарушая логики программы. Вот здесь как раз и требуется введение control-зависимостей.

Чтобы построить control-зависимости нам нужно:

  1. сразу искючить disjoint-инструкции
  2. построить таблицу достижимости (reach-table)

Таблица достижимости может выглядеть так:

1 2 3 4 5 6
1 1
2 1
3 1 1 1
4 1 1 1 1
5 1 1 1 1
6 1 1 1 1 1

То есть каждую инструкцию можно достигнуть саму из себя. Если какую-то инструкцию можно достигнуть из нескольких других, то соответствующая строка будет логическим-или от строк, соответствующим другим инструкциям.

Далее мы будем смотреть, если инструкция является branch, то из недостижимых инструкций рисуем control-зависимость.

(буду благодарен, если кто-то покажет, как приведённая таблица согласуется с примером кода)

//snark

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-Share Alike 2.5 License.