Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Когда каждый путь в графе потока управления должен проходить через один узел, чтобы достичь другого.
When every path in a control flow graph must go through one node to reach another
1 dom 3 4 5 6 2 dom 3 dom 4 dom 5 dom 6 dom Соответствующее отношение доминирования: не строго доминируются, немедленно доминируются.
1 dom 3 4 5 6 2 dom 3 dom 4 dom 5 dom 6 dom Corresponding domination relation: are not strictly dominated are immediately dominated
В информатике узел d графа потока управления доминирует над узлом n, если каждый путь от начального узла к n должен проходить через d. Это обозначается как d dom n (или иногда d ≫ n). По определению, каждый узел доминирует над самим собой. Существует ряд связанных понятий:
In computer science, a node d of a control flow graph dominates a node n if every path from the entry node to n must go through d. Notationally, this is written as d dom n (or sometimes d ≫ n). By definition, every node dominates itself. There are a number of related concepts:
Узел d строго доминирует над узлом n, если d доминирует над n и d не равен n.
Непосредственный доминатор (idom) узла n — это уникальный узел, который строго доминирует над n, но не строго доминирует над каким-либо другим узлом, который строго доминирует над n. Каждый узел, кроме начального, имеет непосредственный доминатор. Проссер не представил алгоритм для вычисления доминирования, который пришлось ждать десять лет, пока его не разработали Эдвард С. Лоури и Си. В. Медлок. Рон Сайтрон и другие вновь вызвали интерес к доминированию в 1989 году, когда применили его к задаче эффективного вычисления размещения φ-функций, которые используются в статической форме однозначного присваивания.
A node d strictly dominates a node n if d dominates n and d does not equal n.
The immediate dominator or idom of a node n is the unique node that strictly dominates n but does not strictly dominate any other node that strictly dominates n. Every node, except the entry node, has an immediate dominator. Prosser did not present an algorithm for computing dominance, which had to wait ten years for Edward S. Lowry and C. W. Medlock. Ron Cytron et al. rekindled interest in dominance in 1989 when they applied it to the problem of efficiently computing the placement of φ functions, which are used in static single assignment form.
Приложения
Доминанты, и границы доминантности особенно, находят применение в компиляторах для вычисления статической формы однозначного присваивания. Многие оптимизации компилятора также могут выиграть от использования доминантов. В данном случае граф потока состоит из базовых блоков. Автоматическая параллелизация выигрывает от границ постдоминирования. Это эффективный метод вычисления управляющей зависимости, критически важной для анализа. Анализ использования памяти может использовать дерево доминаторов для простого обнаружения утечек и выявления участков с высоким потреблением памяти. В аппаратных системах доминанты используются для вычисления вероятностей сигналов при генерации тестов, оценки переключений для анализа энергопотребления и шума, а также для выбора точек разреза при проверке эквивалентности. В программных системах они применяются для уменьшения размера набора тестов в методах структурного тестирования, таких как покрытие операторов и покрытие ветвей.
Dominators, and dominance frontiers particularly, have applications in compilers for computing static single assignment form. A number of compiler optimizations can also benefit from dominators. The flow graph in this case comprises basic blocks. Automatic parallelization benefits from postdominance frontiers. This is an efficient method of computing control dependence, which is critical to the analysis. Memory usage analysis can benefit from the dominator tree to easily find leaks and identify high memory usage. In hardware systems, dominators are used for computing signal probabilities for test generation, estimating switching activities for power and noise analysis, and selecting cut points in equivalence checking. In software systems, they are used for reducing the size of the test set in structural testing techniques such as statement and branch coverage.
Постдоминирование
Аналогично определению доминирования, узел z называется постдоминантом узла n, если все пути к выходному узлу графа, начинающиеся в n, должны проходить через z. Соответственно, непосредственный постдоминатор узла n – это постдоминатор n, который не строго постдоминирует ни один другой строгий постдоминатор n.
Analogous to the definition of dominance above, a node z is said to post dominate a node n if all paths to the exit node of the graph starting at n must go through z. Similarly, the immediate post dominator of a node n is the postdominator of n that doesn't strictly postdominate any other strict postdominators of n.