Анализ зависимости - Dependence analysis

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

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

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

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

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

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

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

Видеть зависимости данных Больше подробностей.

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

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

Поточная (истинная) зависимость

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

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

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

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

S1 х: = у + cS2 у: = 10

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

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

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

S1 x: = 10S2 x: = 20

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

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

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

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

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

Циклические зависимости

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

Смотрите также

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

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

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