Редактирование: Теория к заданиям

== Множества Gen и Kill ==

В лекциях определения этих множеств даются в рамках темы Достигающих определений (Тема №2. Построение множеств Input и Output).
*gen – множество определений, порождаемых инструкцией
*kill – множество определений, убиваемых инструкцией

<strong>Примечание от нерадивых студентов.</strong>
Попробуем сформулировать проще. Предположим в блоке <code>Блок1</code> определена переменная с именем <code>Переменная1</code>. Определим в качестве пары (<code>Переменная1</code>, <code>Блок1</code>). Тогда:
*множество <code>Gen</code> для блока - это множество всех переменных, которые объявляются в этом блоке;
*множество <code>Kill</code> для блока <code>Блок1</code> определяется с помощью множества <code>Gen</code> следующим образом. Для каждой переменной блока <code>Блок1</code> (в нашем случае это будет только <code>Переменная1</code>), сопоставляя её с множеством <code>Gen</code> для блока <code>Блок1</code>, проверяется наличие переменной с таким же именем в множествах <code>Gen</code> всех других блоков программы, и, в случае, если вхождение присутствует, переменная (в нашем случае <code>Переменная1</code>) входит в множество <code>Kill</code> блока <code>Блок1</code>.

== Достигающие определения ==

Из лекций:
*<strong>Определением переменной x</strong> называется инструкция, которая
присваивает значение переменной <code>х</code>.
*<strong>Использованием переменной x</strong> является инструкция, одним из
операндов которой является переменная <code>х</code>.
*Каждое новое определение переменной x <strong>убивает</strong> ее предыдущее
определение.
*Определение <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>
 <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, B1), (j, B1), (a, B1),
*(j, B2) (других определений j на пути от (j, B2) до начала блока B2 нет)
*(a, B3)
*(i, B4)

(i, B2) не достигает начала B2, так как его убивает (i, B4)
(j, B2) убивает (j, B1), не позволяя ему достичь блоков B3 и B4

<strong>Примечание от нерадивых студентов.</strong> 
Возможно, Вам поможет статья на [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 &isin; Pred(m) & n &isin; Dom(p)</code>
# n не является строгим доминатором m
#: <code>n &notin; (Dom (m) – {m})</code>

<strong>Примечание от нерадивых студентов.</strong>

== Бесполезный код ==