Теория к заданиям — различия между версиями

Материал из Compilers Wiki
Перейти к: навигация, поиск
(Новая страница: «== Множества Gen и Kill == В лекциях определения этих множеств даются в рамках темы Достигающ…»)
 
 
(не показано 6 промежуточных версий 2 участников)
Строка 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;"><img src="http://compilers.csmsu.ru/images/RDexample.png">[[File:RDexample.png|20px|link=http://compilers.csmsu.ru/images/RDexample.png]]</div>
+
<div style="float:right;">[[File:RDexample.png | 100px]]</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 &isin; Pred(m) & n &isin; Dom(p)</code>
 +
# n не является строгим доминатором m
 +
#: <code>n &notin; (Dom (m) – {m})</code>
 +
 +
<strong>Примечание от нерадивых студентов.</strong>
 +
 +
== Бесполезный код ==

Текущая версия на 18:23, 5 апреля 2018

Множества Gen и Kill[править]

В лекциях определения этих множеств даются в рамках темы "Достигающие определения" (Тема №2. Построение множеств Input и Output).

  • gen – множество определений, порождаемых инструкцией
  • kill – множество определений, убиваемых инструкцией

Примечание от нерадивых студентов. Попробуем сформулировать проще. Предположим в блоке Блок1 определена переменная с именем Переменная1. Определим в качестве пары (Переменная1, Блок1). Тогда:

  • множество Gen для блока - это множество всех переменных, которые объявляются в этом блоке;
  • множество Kill для блока Блок1 определяется с помощью множества Gen следующим образом. Для каждой переменной блока Блок1 (в нашем случае это будет только Переменная1), сопоставляя её с множеством Gen для блока Блок1, проверяется наличие переменной с таким же именем в множествах Gen всех других блоков программы, и, в случае, если вхождение присутствует, переменная (в нашем случае Переменная1) входит в множество Kill блока Блок1.

Достигающие определения[править]

Из лекций:

  • Определением переменной x называется инструкция, которая

присваивает значение переменной х.

  • Использованием переменной x является инструкция, одним из

операндов которой является переменная х.

  • Каждое новое определение переменной x убивает ее предыдущее

определение.

  • Определение d достигает точки p, если существует путь от точки, непосредственно следующей за d, к точке p, такой, что вдоль этого пути d остается живым.
RDexample.png
Пример. (Из лекций).
B1
i ← –, m, 1
j ← n
a ← u1
B2
i ← +, i, 1
j ← -, j, 1 a
B3
a ← u2
B4
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

Примечание от нерадивых студентов. Возможно, Вам поможет статья на Wikipedia.

Множества Def и Use[править]

  • def – множество переменных, определяемых в блоке В до их использования в этом блоке (любая переменная из defB мертва на входе в блок В).
  • use – множество переменных, используемых в блоке В до их определения в этом блоке (любая переменная из useB жива на входе в блок В).
DUexample.png
Пример. (Из лекций).
B1
i ← –, m, 1
j ← n
a ← u1
B2
i ← +, i, 1
j ← -, j, 1 a
B3
a ← u2
B4
i ← u3
  • в блоке B2 переменные i и j используются до их переопределения, следовательно,
useB2 = {(i,B1), (i,B4), (j,B1)} = (1100001)
  • в блоке B2 определяются новые значения переменных i и j, так что
defB2 = {(i,B2), (j,B2)} = (0001100)

Примечание от нерадивых студентов. Пример алгоритма и дополнительную информацию можно найти на github. Обратите внимание, в примерах следующего вида:

export function w $f(w %n, w %m) {
@start
   %a =w add 1, 1
@end
   ret %a
}

переменная %a должна входить в use(ret).

Живые переменные[править]

Для определения переменной x в точке p программы выяснить, будет ли указанное значение x использоваться вдоль какого-нибудь пути, начинающемся в точке p.

  • Если да – переменная x жива (активна) в точке p.
  • Если нет – переменная x мертва (неактивна) в точке p.

Примечание от нерадивых студентов. Фактически, это Reaching Definitions (Достигающие определения) наоборот. Пример алгоритма.

for (каждый базовый блок B) {
    In[B] = ∅
}
while (внесены изменения в In) {
    for (каждый базовый блок, отличный от выходного) {
        Out[B] = ⋃In[S], S - преемник В
        In[B] = use[B] ∪ (Out[B] \ def[B])
    }
}

Тогда живые переменные блока - это его Out.

Доминаторы[править]

Из лекций: В ГПУ вершина d является доминатором вершины n (этот факт записывается как d dom n или d = Dom(n)), если любой путь от вершины Entry до вершины n проходит через вершину d.

Другой вариант определения. Узел d графа потока доминирует над узлом n, если любой путь от входного узла графа потока к n проходит через d. Заметим, что при таком определении каждый узел доминирует над самим собой.

Форма SSA[править]

Из лекций: Форма статического единственного присваивания (SSA) позволяет в каждой точке программы объединить

  • информацию об имени переменной
  • с информацией о текущем значении этой переменной (или, что то же самое, с информацией о том, какое из определений данной переменной определяет ее текущее значение в данной точке).

Примечание от нерадивых студентов. Вы также можете почерпнуть некоторую дополнительную информацию в соответствующей статье на Wikipedia.

Граница доминирования[править]

Из лекций: Границей доминирования n, DF(n), называется множество узлов m, удоволетворяющих условиям:

  1. n является доминатором предшественника m
    p ∈ Pred(m) & n ∈ Dom(p)
  2. n не является строгим доминатором m
    n ∉ (Dom (m) – {m})

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

Бесполезный код[править]