| Текущая версия |
Ваш текст |
| Строка 1: |
Строка 1: |
| | == Множества Gen и Kill == | | == Множества Gen и Kill == |
| | | | |
| − | В лекциях определения этих множеств даются в рамках темы "Достигающие определения" (Тема №2. Построение множеств Input и Output). | + | В лекциях определения этих множеств даются в рамках темы Достигающих определений (Тема №2. Построение множеств Input и Output). |
| | *gen – множество определений, порождаемых инструкцией | | *gen – множество определений, порождаемых инструкцией |
| | *kill – множество определений, убиваемых инструкцией | | *kill – множество определений, убиваемых инструкцией |
| Строка 49: |
Строка 49: |
| | <strong>Примечание от нерадивых студентов.</strong> | | <strong>Примечание от нерадивых студентов.</strong> |
| | Возможно, Вам поможет статья на [https://ru.wikipedia.org/wiki/Достигающие_определения Wikipedia]. | | Возможно, Вам поможет статья на [https://ru.wikipedia.org/wiki/Достигающие_определения Wikipedia]. |
| − |
| |
| − | == Множества Def и Use ==
| |
| − |
| |
| − | *def – множество переменных, определяемых в блоке В до их использования в этом блоке (любая переменная из defB мертва на входе в блок В).
| |
| − | *use – множество переменных, используемых в блоке В до их определения в этом блоке (любая переменная из useB жива на входе в блок В).
| |
| − |
| |
| − | <div style="float:right;">[[File:DUexample.png | 100px]]</div>
| |
| − | <strong>Пример. (Из лекций).</strong>
| |
| − | <u>B1</u>
| |
| − | i ← –, m, 1
| |
| − | j ← n
| |
| − | a ← u1
| |
| − |
| |
| − | <u>B2</u>
| |
| − | i ← +, i, 1
| |
| − | j ← -, j, 1 a
| |
| − |
| |
| − | <u>B3</u>
| |
| − | a ← u2
| |
| − |
| |
| − | <u>B4</u>
| |
| − | i ← u3
| |
| − |
| |
| − | *в блоке B2 переменные i и j используются до их переопределения, следовательно,
| |
| − | useB2 = {(i,B1), (i,B4), (j,B1)} = (1100001)
| |
| − |
| |
| − | *в блоке B2 определяются новые значения переменных i и j, так что
| |
| − | defB2 = {(i,B2), (j,B2)} = (0001100)
| |
| − |
| |
| − | <strong>Примечание от нерадивых студентов.</strong>
| |
| − | Пример алгоритма и дополнительную информацию можно найти на [https://github.com/wisestump/OptimizingCompiler/blob/4105258f3865a6ebed70a1445fbf1f1df264a61c/documentation/PiedPiper/PiedPiper-DefUseCalculation.md github].
| |
| − | <u>Обратите внимание</u>, в примерах следующего вида:
| |
| − | export function w $f(w %n, w %m) {
| |
| − | @start
| |
| − | %a =w add 1, 1
| |
| − | @end
| |
| − | ret %a
| |
| − | }
| |
| − | переменная <code>%a</code> должна входить в <code>use(ret)</code>.
| |
| − |
| |
| − | == Живые переменные ==
| |
| − |
| |
| − | Для определения переменной x в точке p программы выяснить, будет ли указанное значение x использоваться вдоль какого-нибудь пути, начинающемся в точке p.
| |
| − | *Если да – переменная x жива (активна) в точке p.
| |
| − | *Если нет – переменная x мертва (неактивна) в точке p.
| |
| − |
| |
| − | <strong>Примечание от нерадивых студентов.</strong>
| |
| − | Фактически, это Reaching Definitions (Достигающие определения) наоборот.
| |
| − | Пример алгоритма.
| |
| − | for (каждый базовый блок B) {
| |
| − | In[B] = ∅
| |
| − | }
| |
| − | while (внесены изменения в In) {
| |
| − | for (каждый базовый блок, отличный от выходного) {
| |
| − | Out[B] = ⋃In[S], S - преемник В
| |
| − | In[B] = use[B] ∪ (Out[B] \ def[B])
| |
| − | }
| |
| − | }
| |
| − | Тогда живые переменные блока - это его Out.
| |
| − |
| |
| − | == Доминаторы ==
| |
| − | Из лекций:
| |
| − | В [https://ru.wikipedia.org/wiki/Граф_потока_управления ГПУ] вершина <code>d</code> является <strong>доминатором</strong> вершины <code>n</code> (этот факт записывается как <code>d dom n</code> или <code>d = Dom(n))</code>, если любой путь от вершины <code>Entry</code> до вершины <code>n</code> проходит через вершину <code>d</code>.
| |
| − |
| |
| − | Другой вариант определения.
| |
| − | Узел <code>d</code> графа потока доминирует над узлом <code>n</code>, если любой путь от входного узла графа потока к <code>n</code> проходит через <code>d</code>. Заметим, что при таком определении каждый узел доминирует над самим собой.
| |
| − |
| |
| − | == Форма SSA ==
| |
| − | Из лекций:
| |
| − | Форма статического единственного присваивания (SSA) позволяет в каждой точке программы объединить
| |
| − | *информацию об имени переменной
| |
| − | *с информацией о текущем значении этой переменной (или, что то же самое, с информацией о том, какое из определений данной переменной определяет ее текущее значение в данной точке).
| |
| − |
| |
| − | <strong>Примечание от нерадивых студентов.</strong> Вы также можете почерпнуть некоторую дополнительную информацию в соответствующей статье на [https://ru.wikipedia.org/wiki/SSA Wikipedia].
| |
| − |
| |
| − | == Граница доминирования ==
| |
| − | Из лекций:
| |
| − | Границей доминирования n, DF(n), называется множество узлов m, удоволетворяющих условиям:
| |
| − | # n является доминатором предшественника m
| |
| − | #: <code>p ∈ Pred(m) & n ∈ Dom(p)</code>
| |
| − | # n не является строгим доминатором m
| |
| − | #: <code>n ∉ (Dom (m) – {m})</code>
| |
| − |
| |
| − | <strong>Примечание от нерадивых студентов.</strong>
| |
| − |
| |
| − | == Бесполезный код ==
| |
