Зависимость по управлению: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Создана новая страница размером '''Зависимость по управлению''' (''Control dependence'') - зависимость, направленная от ...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| (не показана 1 промежуточная версия этого же участника) | |||
| Строка 1: | Строка 1: | ||
'''Зависимость по управлению''' (''Control dependence'') | '''Зависимость по управлению''' (''[[Control dependence]]'') — зависимость, направленная от оператора IF к операторам, находящимся под его управлением. Более строгое определение использует понятие [[постдоминатор|''постдоминатора'']]. А именно, пусть <math>G</math> — ''[[управляющий граф]]'', а <math>x</math> и <math>y</math> — две его [[вершина|вершины]]. Вершина <math>y</math> зависит по управлению от <math>x</math>, если: | ||
зависимость, направленная от оператора IF к операторам, находящимся | |||
под его управлением. Более строгое определение использует понятие | |||
''постдоминатора''. А именно, пусть <math>G</math> | |||
и <math>y</math> | |||
если: | |||
(1) существует путь из <math>x</math> в <math>y</math>, в котором любая вершина <math>z</math> (за | :(1) существует путь из <math>x</math> в <math>y</math>, в котором любая вершина <math>z</math> (за исключением <math>x</math> и <math>y</math>) постдоминируется вершиной <math>y</math>, и | ||
исключением <math>x</math> и <math>y</math>) постдоминируется вершиной <math>y</math>, и | |||
(2) вершина <math>x</math> не постдоминируется вершиной <math>y</math>. | :(2) вершина <math>x</math> не постдоминируется вершиной <math>y</math>. | ||
В применении к циклу | В применении к [[цикл|циклу]] в управляющем [[граф|графе]] данное определение '''зависимости по управлению''' характеризует сильно связную область (''[[зона|зону]]'') зависимости по управлению, вершинами | ||
в управляющем графе данное определение ''' | |||
связную область (''зону'') зависимости по управлению, вершинами | |||
которой являются предикаты, определяющие выход из цикла. | которой являются предикаты, определяющие выход из цикла. | ||
==Литература== | ==Литература== | ||
* Векторизация программ: теория, методы, реализация. — М.: Мир, 1991. | |||
Текущая версия от 13:03, 9 февраля 2011
Зависимость по управлению (Control dependence) — зависимость, направленная от оператора IF к операторам, находящимся под его управлением. Более строгое определение использует понятие постдоминатора. А именно, пусть [math]\displaystyle{ G }[/math] — управляющий граф, а [math]\displaystyle{ x }[/math] и [math]\displaystyle{ y }[/math] — две его вершины. Вершина [math]\displaystyle{ y }[/math] зависит по управлению от [math]\displaystyle{ x }[/math], если:
- (1) существует путь из [math]\displaystyle{ x }[/math] в [math]\displaystyle{ y }[/math], в котором любая вершина [math]\displaystyle{ z }[/math] (за исключением [math]\displaystyle{ x }[/math] и [math]\displaystyle{ y }[/math]) постдоминируется вершиной [math]\displaystyle{ y }[/math], и
- (2) вершина [math]\displaystyle{ x }[/math] не постдоминируется вершиной [math]\displaystyle{ y }[/math].
В применении к циклу в управляющем графе данное определение зависимости по управлению характеризует сильно связную область (зону) зависимости по управлению, вершинами которой являются предикаты, определяющие выход из цикла.
Литература
- Векторизация программ: теория, методы, реализация. — М.: Мир, 1991.