Граф зависимостей(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)
Для такого кода получаем следующий граф зависимостей:
Заметим, что граф избыточный, но нас сейчас это не волнует, поскольку в худшем случае наши алгоритмы будут работать медленнее и "съедать" больше памяти, и только. Для начала и такое было бы неплохо.
Также обратим внимание, что при выполнении 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'ами
Данный код можно представить в виде одного блока с одним входом и двумя выходами следующим образом
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-зависимости нам нужно:
- сразу искючить disjoint-инструкции
- построить таблицу достижимости (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
