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

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

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

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

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

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

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

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

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

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

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

$S_{2}$ пост-доминирует над всеми $S_{i}$
$S_{2}$ не пост-доминирует $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 в узлы, которые имеют зависимость от управления.

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

Ссылки

^ 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.

[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.