Анализ зависимостей
В теории компиляторов создает анализ зависимостей ограничения порядка выполнения между операторами/инструкциями. В общих чертах, оператор S2 зависит от S1 , если S1 должен быть выполнен до S2 . В общих чертах существует два класса зависимостей — зависимости управления и зависимости данных .
Анализ зависимостей определяет, безопасно ли переупорядочивать или распараллеливать операторы.
Зависимости управления [ править ]
Зависимость управления — это ситуация, в которой инструкция программы выполняется, если предыдущая инструкция оценивается таким образом, что позволяет ее выполнение.
Оператор S2 является управляемо-зависимым от S1 (записывается ) тогда и только тогда, когда выполнение S2 условно защищено S1 . S2 зависит Управление от S1 тогда и только тогда, когда где это пост-доминантная граница высказывания . Ниже приведен пример такой зависимости управления:
S1, если x > 2, перейти к L1 S2 у := 3 S3 L1: z := y + 1
Здесь S2 выполняется только в том случае, если предикат в S1 ложен.
Зависимости данных [ править ]
Зависимость данных возникает из-за двух операторов, которые обращаются к одному и тому же ресурсу или изменяют его.
Зависимость Flow(True) [ править ]
Оператор S2 является потокозависимым от S1 (записывается ) тогда и только тогда, когда S1 изменяет ресурс, который читает S2 , и S1 предшествует S2 в выполнении. Ниже приведен пример зависимости от потока (RAW: чтение после записи):
С1 х := 10 S2 у := х + с
Антизависимость [ править ]
Высказывание S2 антизависимо от S1 ( записывается ) тогда и только тогда, когда S2 изменяет ресурс, который читает S1 , и S1 предшествует S2 в выполнении. Ниже приведен пример антизависимости (WAR: Write After Read):
S1 х := у + с S2 у := 10
Здесь S2 устанавливает значение y
но S1 считывает предыдущее значение y
.
Выходная зависимость [ править ]
Оператор S2 выводится в зависимости от S1 (записывается ) тогда и только тогда, когда S1 и S2 модифицируют один и тот же ресурс и S1 предшествует S2 в выполнении. Ниже приведен пример зависимости вывода (WAW: Write After Write):
С1 х := 10 S2 х := 20
Здесь S2 и S1 устанавливают переменную x
.
Входная зависимость [ править ]
Оператор S2 зависит ввода от S1 (записывается ) тогда и только тогда, когда S1 и S2 читают один и тот же ресурс и S1 предшествует S2 в выполнении. Ниже приведен пример входной зависимости (RAR: Read-After-Read):
S1 у := х + 3 S2 г := х + 5
Здесь S2 и S1 оба обращаются к переменной x
. Эта зависимость не запрещает переупорядочение.
Зависимости цикла [ править ]
Проблема вычисления зависимостей внутри циклов, которая является важной и нетривиальной проблемой, решается с помощью анализа зависимостей цикла , который расширяет приведенную здесь структуру зависимостей.
См. также [ править ]
- Программный анализ (информатика)
- Автоматическое распараллеливание
- Автоматическая векторизация
- Анализ зависимости цикла
- Фреймворки, поддерживающие многогранную модель
- Опасность (компьютерная архитектура)
- Нарезка программы
- Удаление мертвого кода
Дальнейшее чтение [ править ]
- Купер, Кейт Д.; Торчон, Линда. (2005). Разработка компилятора . Морган Кауфманн. ISBN 1-55860-698-Х .
- Кеннеди, Кен; Аллен, Рэнди. (2001). Оптимизация компиляторов для современных архитектур: подход, основанный на зависимостях . Морган Кауфманн. ISBN 1-55860-286-0 .
- Мучник, Стивен С. (1997). Расширенное проектирование и реализация компилятора . Морган Кауфманн. ISBN 1-55860-320-4 .