Зависимость от контроля

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

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

S1. если (a == b)S2. а = а + bS3. б = а + б

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

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

Типичным примером является наличие управляющих зависимостей между условной частью оператора 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 в восходящем обходе дерева пост-доминатора выполните: ПостДоминированиеГраница(X) ← ∅ для каждого Y ∈ Predecessors(X) делаем: если immediatelyPostDominator(Y) ≠ X: затем ПостДоминированиеГраница(X) ← ПостДоминированиеГраница(X) ∪ {Y} сделанный для каждого Z ∈ Children(X) делаем: для каждого Y ∈ PostDominanceFrontier(Z) выполните: если immediatelyPostDominator(Y) ≠ X: затем ПостДоминированиеГраница(X) ← ПостДоминированиеГраница(X) ∪ {Y} сделанный сделанныйсделанный

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

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

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

Ссылки

1. Cytron, R.; Ferrante, J.; Rosen, BK; Wegman, MN; Zadeck, FK (1989-01-01). "Эффективный метод вычисления статической формы одиночного присваивания". Труды 16-го симпозиума ACM SIGPLAN-SIGACT по принципам языков программирования - POPL '89 . Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 25–35. doi :10.1145/75277.75280. ISBN 0897912942. S2CID  8301431.