Текущая версия |
Ваш текст |
Строка 1: |
Строка 1: |
| == Множества Gen и Kill == | | == Множества Gen и Kill == |
| | | |
− | В лекциях определения этих множеств даются в рамках темы "Достигающие определения" (Тема №2. Построение множеств Input и Output). | + | В лекциях определения этих множеств даются в рамках темы Достигающих определений (Тема №2. Построение множеств Input и Output). |
| *gen – множество определений, порождаемых инструкцией | | *gen – множество определений, порождаемых инструкцией |
| *kill – множество определений, убиваемых инструкцией | | *kill – множество определений, убиваемых инструкцией |
Строка 21: |
Строка 21: |
| *Определение <code>d</code> <strong>достигает</strong> точки <code>p</code>, если существует путь от точки, непосредственно следующей за <code>d</code>, к точке <code>p</code>, такой, что вдоль этого пути <code>d</code> остается живым. | | *Определение <code>d</code> <strong>достигает</strong> точки <code>p</code>, если существует путь от точки, непосредственно следующей за <code>d</code>, к точке <code>p</code>, такой, что вдоль этого пути <code>d</code> остается живым. |
| | | |
− | <div style="float:right;">[[File:RDexample.png | 100px]]</div> | + | <div style="float:right;"><img src="http://compilers.csmsu.ru/images/RDexample.png">[[File:RDexample.png|20px|link=http://compilers.csmsu.ru/images/RDexample.png]]</div> |
| <strong>Пример. (Из лекций).</strong> | | <strong>Пример. (Из лекций).</strong> |
| <u>B1</u> | | <u>B1</u> |
Строка 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>
| |
− |
| |
− | == Бесполезный код ==
| |