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

Материал из Compilers Wiki
Перейти к: навигация, поиск
(Новая страница: «== Множества Gen и 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>

Версия 17:44, 23 марта 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.