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

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

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

S1.         if (a == b)
S2.             a = a + b
S3.         b = a + b

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

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

Типичным примером является наличие управляющих зависимостей между условной частью оператора 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, а затем повернуть ее вспять, чтобы получить график зависимости управления.

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

for each X in a bottom-up traversal of the post-dominator tree do:
    PostDominanceFrontier(X) ← ∅
    for each Y ∈ Predecessors(X) do:
        if immediatePostDominator(Y) ≠ X:
            then PostDominanceFrontier(X) ← PostDominanceFrontier(X) ∪ {Y}
    done
    for each Z ∈ Children(X) do:
        for each Y ∈ PostDominanceFrontier(Z) do:
            if immediatePostDominator(Y) ≠ X:
                then PostDominanceFrontier(X) ← PostDominanceFrontier(X) ∪ {Y}
        done
    done
done

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

См. также

Ссылки

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

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

[1]