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

редактировать

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

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

Содержание

1 Зависимости управления
2 Зависимости данных
- 2.1 Зависимость потока (True)
- 2.2 Антизависимость
- 2.3 Выходная зависимость
- 2.4 Входная зависимость
3 Циклические зависимости
4 См. Также
5 Дополнительная литература

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

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

Оператор S2 зависит от управления S1 (записывается $S 1 δ c S 2 {\ displaystyle S1 \ \ delta ^ {c} \ S2}$ $S1 \ \ delta ^ {c} \ S2$ ) тогда и только тогда, когда Выполнение S2 условно охраняется S1. Ниже приводится пример такой управляющей зависимости:

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

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

Подробнее см. зависимости данных.

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

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

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

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

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

Antidependence

Инструкция S2 является антизависимым от S1 (записывается $S 1 δ a S 2 {\ displaystyle S1 \ \ delta ^ {a} \ S2}$ $S1 \ \ delta ^ {a} \ S2$ ) тогда и только тогда, когда S2 изменяет a ресурс, который читает S1, а S1 предшествует S2 в исполнении. Ниже приведен пример антизависимости (WAR: запись после чтения):

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

Здесь S2 устанавливает значение y, но S1 читает предыдущее значение y. Термин «антизависимость», широко используемый в литературе, неверен, потому что «анти» означает противоположное. Правильный термин должен быть «анте», что означает перед. Следовательно, правильным словом должно быть «антедезависимость».

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

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

S1 x: = 10 S2 x: = 20

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

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

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

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

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

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

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

См. Также

Дополнительная литература

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