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

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

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

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

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

Заявление S2 является управлением в зависимости от S1 (написано ) тогда и только тогда , когда S2' s выполнения условно охраняются S1 . Ниже приводится пример такой управляющей зависимости:${\ Displaystyle S1 \ \ дельта ^ {с} \ S2}$

S1, если x> 2 перейти к L1S2 у: = 3 S3 L1: z: = y + 1

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

Для получения более подробной информации см. Зависимости данных.

Зависимости данных [ править ]

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

Поточная (истинная) зависимость [ править ]

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

S1 x: = 10S2 у: = х + с

Антизависимость [ править ]

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

S1 х: = у + сS2 у: = 10

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

Выходная зависимость [ править ]

Заявление S2 является зависимым выходом на S1 (написано ) тогда и только тогда , когда S1 и S2 модифицировать тот же ресурс и S1 предшествует S2 в исполнении. Ниже приведен пример выходной зависимости (WAW: запись после записи):${\ Displaystyle S1 \ \ дельта ^ {о} \ S2}$

S1 x: = 10S2 х: = 20

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

Входная зависимость [ править ]

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

S1 у: = х + 3S2 z: = х + 5

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

Циклические зависимости [ править ]

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

См. Также [ править ]

• Программный анализ (информатика)
• Автоматическое распараллеливание
• Автоматическая векторизация
• Анализ петлевой зависимости
• Каркасы, поддерживающие многогранную модель
• Опасность (компьютерная архитектура)
• Программа нарезки
• Устранение мертвого кода

Дальнейшее чтение [ править ]

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