Анализ зависимостей

В теории компиляторов анализ зависимостей создает ограничения порядка выполнения между операторами/инструкциями. В общих чертах, оператор S2 зависит от S1 , если S1 должен быть выполнен до S2 . В общих чертах существует два класса зависимостей — зависимости управления и зависимости данных .

Анализ зависимостей определяет, безопасно ли переупорядочивать или распараллеливать операторы.

Зависимости управления

Зависимость управления — это ситуация, в которой инструкция программы выполняется, если предыдущая инструкция оценивается таким образом, что позволяет ее выполнение.

Оператор S2 является управляемо-зависимым от S1 (записывается $S1\ \delta ^{c}\ S2$ ) тогда и только тогда, когда выполнение S2 условно защищено S1 . S2 зависит Управление от S1 тогда и только тогда, когда $S1\in PDF(S2)$ где $PDF(S)$ это пост-доминантная граница высказывания $S$ . Ниже приведен пример такой зависимости управления:

S1       if x > 2 goto L1
S2       y := 3   
S3   L1: z := y + 1

Здесь S2 выполняется только в том случае, если предикат в S1 ложен.

Зависимости данных

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

Зависимость потока(True)

Оператор S2 является потокозависимым от S1 (записывается $S1\ \delta ^{f}\ S2$ ) тогда и только тогда, когда S1 изменяет ресурс, который S2 читает , и S1 предшествует S2 в выполнении. Ниже приведен пример зависимости от потока (RAW: чтение после записи):

S1       x := 10
S2       y := x + c

Антизависимость

Высказывание S2 антизависимо от S1 ( записывается $S1\ \delta ^{a}\ S2$ ) тогда и только тогда, когда S2 изменяет ресурс, который S1 читает , и S1 предшествует S2 в выполнении. Ниже приведен пример антизависимости (WAR: Write After Read):

S1       x := y + c
S2       y := 10

Здесь S2 устанавливает значение y но S1 считывает предыдущее значение y.

Выходная зависимость

Оператор S2 выводится в зависимости от S1 (записывается $S1\ \delta ^{o}\ S2$ ) тогда и только тогда, когда S1 и S2 модифицируют один и тот же ресурс и S1 предшествует S2 в выполнении. Ниже приведен пример зависимости вывода (WAW: Write After Write):

S1       x := 10
S2       x := 20

Здесь S2 и S1 устанавливают переменную x.

Входная зависимость

Оператор S2 зависит ввода от S1 (записывается $S1\ \delta ^{i}\ S2$ ) тогда и только тогда, когда S1 и S2 читают один и тот же ресурс и S1 предшествует S2 в выполнении. Ниже приведен пример входной зависимости (RAR: Read-After-Read):

S1       y := x + 3
S2       z := x + 5

Здесь S2 и S1 оба обращаются к переменной x. Эта зависимость не запрещает переупорядочение.

Зависимости цикла

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

См. также

Дальнейшее чтение

Купер, Кейт Д.; Торчон, Линда. (2005). Разработка компилятора . Морган Кауфманн. ISBN 1-55860-698-Х .
Кеннеди, Кен; Аллен, Рэнди. (2001). Оптимизация компиляторов для современных архитектур: подход, основанный на зависимостях . Морган Кауфманн. ISBN 1-55860-286-0 .
Мучник, Стивен С. (1997). Расширенное проектирование и реализация компилятора . Морган Кауфманн. ISBN 1-55860-320-4 .