В теории компиляторов анализ зависимости создает ограничения порядка выполнения между операторами/инструкциями. В общих чертах, оператор S2 зависит от S1 , если S1 должен быть выполнен до S2 . В общих чертах, существует два класса зависимостей — зависимости управления и зависимости данных .
Анализ зависимостей определяет, безопасно ли переупорядочивать или распараллеливать операторы.
Зависимость управления — это ситуация, в которой инструкция программы выполняется, если предыдущая инструкция оценивается таким образом, что позволяет ее выполнение.
Оператор S2 зависим по управлению от S1 (записан ) тогда и только тогда, когда выполнение S2 условно защищено S1 . S2 зависим по управлению от S1 тогда и только тогда, когда , где находится граница доминирования поста оператора . Ниже приведен пример такой зависимости по управлению:
S1 если x > 2 перейти к L1S2 у := 3 S3 L1: z := y + 1
Здесь S2 выполняется только в том случае, если предикат в S1 ложен.
Зависимость данных возникает из-за двух операторов, которые обращаются к одному и тому же ресурсу или изменяют его.
Оператор S2 зависит от потока S1 (записано ) тогда и только тогда, когда S1 изменяет ресурс, который читает S2 , и S1 предшествует S2 в выполнении. Ниже приведен пример зависимости потока (RAW: Read After Write):
S1 х := 10S2 у := х + с
Выражение S2 является антизависимым от S1 (записано ) тогда и только тогда, когда S2 изменяет ресурс, который читает S1 , и S1 предшествует S2 в выполнении. Ниже приведен пример антизависимости (WAR: Write After Read):
S1 x := y + cS2 у := 10
Здесь S2 устанавливает значение, yа S1 считывает предыдущее значение y.
Оператор S2 является зависимым от вывода S1 (записанным ), если и только если S1 и S2 изменяют один и тот же ресурс, а S1 предшествует S2 при выполнении. Ниже приведен пример зависимости вывода (WAW: Write After Write):
S1 х := 10S2 х := 20
Здесь S2 и S1 оба задают переменную x.
Оператор S2 является зависимым по входу от S1 (записанным ) тогда и только тогда, когда S1 и S2 читают один и тот же ресурс, а S1 предшествует S2 в выполнении. Ниже приведен пример зависимости по входу (RAR: Read-After-Read):
S1 у := х + 3S2 z := x + 5
Здесь S2 и S1 оба обращаются к переменной x. Эта зависимость не запрещает переупорядочивание.
Проблема вычисления зависимостей внутри циклов, которая является важной и нетривиальной проблемой, решается с помощью анализа зависимости циклов , который расширяет представленную здесь структуру зависимостей.
