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

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

Инструкция B имеет зависимость управления от предыдущей инструкции A, если результат A определяет, должна ли B выполняться или нет. В следующем примере инструкция имеет зависимость управления от инструкции . Однако это не зависит от того, потому что выполняется всегда независимо от результата . ${\displaystyle S_{2}}$ ${\displaystyle S_{1}}$ ${\displaystyle S_{3}}$ ${\displaystyle S_{1}}$ ${\displaystyle S_{3}}$ ${\displaystyle S_{1}}$

С1. если (а == б)С2. а = а + бС3. б = а + б

Интуитивно понятно, что между двумя утверждениями A и B существует зависимость управления, если

• B может быть выполнен после A
• Результат выполнения A определит, будет ли выполнен B или нет.

Типичным примером является наличие управляющих зависимостей между условной частью оператора if и операторами в его телах true/false.

Формальное определение зависимости управления можно представить следующим образом:

Говорят, что оператор является управляющим, зависящим от другого оператора , если и только если ${\displaystyle S_{2}}$ ${\displaystyle S_{1}}$

• существует путь от до такой, что за каждым оператором ≠ внутри будет следовать каждый возможный путь до конца программы и ${\displaystyle P}$ ${\displaystyle S_{1}}$ ${\displaystyle S_{2}}$ ${\displaystyle S_{i}}$ ${\displaystyle S_{1}}$ ${\displaystyle P}$ ${\displaystyle S_{2}}$
• ${\displaystyle S_{1}}$не обязательно последует , т.е. существует путь выполнения от до конца программы, который не проходит . ${\displaystyle S_{2}}$ ${\displaystyle S_{1}}$ ${\displaystyle S_{2}}$

Выраженные с помощью (пост)доминирования, эти два условия эквивалентны

• ${\displaystyle S_{2}}$пост-доминирует над всем ${\displaystyle S_{i}}$
• ${\displaystyle S_{2}}$не постдоминирует ${\displaystyle S_{1}}$

Построение управляющих зависимостей

Зависимости управления по сути являются границей доминирования на обратном графике графа потока управления (CFG). ^[1] Таким образом, одним из способов их построения было бы построить границу пост-доминирования CFG, а затем повернуть ее вспять, чтобы получить график зависимости управления.

Ниже приведен псевдокод для построения границы пост-доминирования:

для каждого X при обходе дерева постдоминатора снизу вверх выполните: PostDominanceFrontier(X) ← ∅ для каждого Y ∈ Predecessors(X) выполните: если немедленныйПостДоминатор(Y) ≠ X: тогда PostDominanceFrontier(X) ← PostDominanceFrontier(X) ∪ {Y} сделанный для каждого Z ∈ Children(X) выполните: для каждого Y ∈ PostDominanceFrontier(Z) выполните: если немедленныйПостДоминатор(Y) ≠ X: тогда PostDominanceFrontier(X) ← PostDominanceFrontier(X) ∪ {Y} сделанный сделанныйсделанный

Здесь Children(X) — это набор узлов в CFG, в которых непосредственно пост-доминирует X , а Predecessors(X) — это набор узлов в CFG, которые непосредственно предшествуют X в CFG. Обратите внимание, что узел X должен обрабатываться только после того, как будут обработаны все его дочерние элементы. После того, как карта границы пост-доминирования вычислена, ее обращение приведет к отображению узлов в CFG на узлы, которые имеют от них зависимость управления.

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

• Анализ зависимостей
• Зависимость данных
• Анализ зависимости контура § Зависимость управления

Рекомендации

1. Цитрон, Р.; Ферранте, Дж.; Розен, БК; Вегман, Миннесота; Задек, ФК (1 января 1989 г.). «Эффективный метод вычисления статической формы одиночного присваивания». Материалы 16-го симпозиума ACM SIGPLAN-SIGACT по принципам языков программирования - POPL '89 . Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 25–35. дои : 10.1145/75277.75280. ISBN 0897912942. S2CID  8301431.