Введение в теорию построения оптимизирующих компиляторов, 09 лекция (от 05 декабря)
Материал из eSyr's wiki.
(Содержимое страницы заменено на «== From Ebaums Inc to MurkLoar. == We at EbaumsWorld consider you as disgrace of human race. Your faggotry level exceeded any imaginab...») |
(Отмена правки № 1278 участника 88.191.57.15 (обсуждение)) |
||
Строка 1: | Строка 1: | ||
- | == | + | [[Введение в теорию построения оптимизирующих компиляторов, 08 лекция (от 21 ноября)|Предыдущая лекция]] | [[Введение в теорию построения оптимизирующих компиляторов, 10 лекция (от 12 декабря)|Следующая лекция]] |
- | + | ||
- | + | <!-- Чернов 05.12.06 --> | |
- | + | ||
+ | Список имеет важное сельскохозяйственное значение | ||
+ | |||
+ | Лектору на экзамене будет интересано, что мы поняли, какие выводы сделали, и вообще. | ||
+ | |||
+ | Alias analysis (анализ алиасов, указателей, синонимов) | ||
+ | |||
+ | Данные хранятся в адресуемых ячейках памяти. Ячейка может выстуцпать под несколькими именами. Есть переменная a , есть указатель pa: | ||
+ | int a; | ||
+ | int pa; | ||
+ | pa=*a; | ||
+ | |||
+ | алиас: *pa – a | ||
+ | |||
+ | Задача, определить, какие имена должеы адрес к одной ячейке памяти. | ||
+ | |||
+ | for (a=0; a<n; a++) - не можем брать переменную на регистр, потому, что исп под другим именем | ||
+ | { | ||
+ | *pa = | ||
+ | } | ||
+ | |||
+ | Время жизни: | ||
+ | a=0 | ||
+ | ... | ||
+ | b = *pa – до сюда есть | ||
+ | |||
+ | то же относится к анализу достигающих определений, и т. д. | ||
+ | |||
+ | Самый простой способ анализа, лектор назовёт его так, это даже не способ анализа, а некоторой ..., консервативнй анализ алиасов. Мы делаем его, когда не хотим делать никаких сложных уравнений, анализа данных. | ||
+ | |||
+ | *pa – может обращаться ко всему. | ||
+ | |||
+ | Понятно, что это грубый подход. Это очень негативно влияет на интервалы жизни, никакую оптимизацию провести н омжем. | ||
+ | |||
+ | Откуда такой негативный эффект – поскольку обращ ко всему, то присваивание b = *pa; эквивалентно b=a1, b=a2 ... и строя решение уравнения потока, мы получим очень грубое решение, которое не позволит ничего сделать. | ||
+ | |||
+ | Такой консервативнй анализ мы делаем, если не можем сделать ничего больше. | ||
+ | |||
+ | Следующий способ: анализ алиаса, базирующийся на типах (type-based alias analysis). | ||
+ | |||
+ | t * pa – может алиасить всё, имеющее тип t. | ||
+ | |||
+ | Если мы рассмотрим Си, то такое поведение оговорено в стандарте. | ||
+ | |||
+ | Типы void * и char * могут указывать на всё, что угодно. | ||
+ | |||
+ | В том же языке Си есть некрые средства, которые позволяют облегчить процесс анализа. В язык Си ввведено ключ слово restrict. оно может использоваться только в ... . void f (void * restrict a, void * restrict b) – необходимо, чтобы a и b не указывали на одну и ту же область памяти.Например, многие функции стандартной библиотеки являются такими. | ||
+ | |||
+ | Простенький пример: | ||
+ | void f(int n) | ||
+ | { | ||
+ | int a, b, c; | ||
+ | int *p1 = &a, *p2; | ||
+ | L1: ... | ||
+ | if (n>0) | ||
+ | { | ||
+ | p2 = &b; | ||
+ | L2: ... | ||
+ | } | ||
+ | else | ||
+ | { | ||
+ | p2 = &c; | ||
+ | L3: ... | ||
+ | } | ||
+ | L4: ... | ||
+ | } | ||
+ | |||
+ | Варианты: | ||
+ | # flow-insensitive must alias analysis – ведём анализ безотносительно потока управления. must – явл. обязательными. Например: (*p1, a) – пара must alias, про другое сказать уже ничего не можем. | ||
+ | alias принадлжеит V x V, V – множество переменных | ||
+ | # flow-insensitive may alias – отношние алиасинга может выолняться в некрой точке функции. (*p1, a), (*p1, b), (*p1, c). | ||
+ | Полныйй анализ алиасов алгоритмически неразрешим. | ||
+ | # flow-sensitive must – теперь, помимо пары переменных появляется третье измерениеп – точка программы. Что можно вычислить про точку 1..4: | ||
+ | #* L1: (*p1, a) | ||
+ | #* L2: (*p1, a), (*p2, b) | ||
+ | #* L3: (*p1, a), (*p2, c) | ||
+ | #* L4: (*p1, a) | ||
+ | #* Теперь для каждой точки программы можно гарантированно знать, является ли переменная алиасом. | ||
+ | # flow-sensitive may | ||
+ | L4: (*p1, a), (*p2, b), (*p2, c) | ||
+ | |||
+ | Самый информативный из них последний. | ||
+ | |||
+ | Если переходим на межпроцедурный уровень, то появляется понятие context sensitive/insensitive. | ||
+ | |||
+ | Пусть есть процедура Р. Возможно, она вызывается из неск. мест и , возможно, она возвр. Значение. Когда context-in, сливаем все вызовы в один, и сливаем все контексты вызова (join). Получаем выходной контекст, и ставимего в места вызова. Тут два ист неопр – на входе и на выходе. | ||
+ | |||
+ | context-sensitive – каждый вызов рассматривается отдельно. Минус – всё это сильно разрастается. | ||
+ | |||
+ | Как правило, все совр реализации context-ins | ||
+ | |||
+ | Наиболее распрост вариант, который исп в продвинутых анализаторах – flow sens cotext insens alias analysis | ||
+ | |||
+ | Уже при реализации анализа есть выбор между двумя вариантами: | ||
+ | # Символические выражения, адресующие память и отношения между ними. *pa, a, b[10], pa->pb->p | ||
+ | # Абстрактные вычисления с исп. моделирования памяти. Мы вводим понятие абстрактной ячейки памяти (abstract memory location) для каждой переменной, которая сущ в программе, создаём отдельный AML. Кроме того, мы создаём ананомную память (anon) – память вообще, в куче. anon(t) – память в куче опред типа | ||
+ | AML: | ||
+ | name | ||
+ | type | ||
+ | value | ||
+ | |||
+ | bool+int – будем хранить стандартную реш тку продвижения констант (_|_, T, val) | ||
+ | pointers - _|_, T, множество расширенных AML(set of ext. AML). Сюда могут входить ве AML, созданные в программе, кроме того может попадать ананимная или типизир память, а также null. | ||
+ | |||
+ | Все остальные типы рассмотрим потом. | ||
+ | |||
+ | Принципиальные ограничеиня: | ||
+ | # Насколько глудоко заглядываем в структуру | ||
+ | # насколько глубоко хотим различать дин. объекты | ||
+ | # размер мн. вл для указателей | ||
+ | |||
+ | Естественно, что такого рода ограничения неизбежно понижают точность анализа. | ||
+ | |||
+ | Итак, появились три типа ячеека памяти, ввели ограничения. Осталось пройти по программе и информацию получить. | ||
+ | |||
+ | Две фазы: | ||
+ | # Сбор алиасов. Мы идём по исх программе и в соотв с правилами языка мы помещаем некоторые точки, могут они быть алиасами или не могут. | ||
+ | # Распространение о функциям (языко-независимые, forward dfa). В один проход можно собирать алиасы и с помощью f. dfa их продвигать | ||
+ | |||
+ | Для начала для параметра функции генерируем AML. Значение неопр. Для лок переменных трёл то же, для p1 создаётся AML, у которого множ знач будет ссылаться на a, у p2 будет тоже неопределённость. | ||
+ | |||
+ | p = 0 – как изменяется AML? aml(p).value={null} | ||
+ | p = malloc(s) – aml(p).value = {anon(type(p))} | ||
+ | p = &a – aml(p).value = {aml(a)} | ||
+ | p2=p1 – aml(p2).value={aml(p1).value} | ||
+ | и так далее | ||
+ | |||
+ | Тонкости: | ||
+ | Разыменование | ||
+ | a=*p – aml(a) – если множество аэмелей указывает на множество аэмелей, у которых одно значение, то его присваиваем, иначе переопределённость | ||
+ | |||
+ | Всё, до чего может дотянуться вызываемая функция, становится переопределённым. | ||
+ | |||
+ | Слияние графа потока управления: | ||
+ | i L1: v1 i L2: v2 | ||
+ | L3: v1 объединение v2 | ||
+ | |||
+ | Можно выписать все правила для всех конструкций языка, итерирукем по функциям, в итоге всё сойдётся и получим все AML. В большинстве случаев там будет неопр. | ||
+ | |||
+ | Всё множество AML мы храним для каждой точки, и это весьма прожорливо. | ||
+ | |||
+ | Локальные хаки: | ||
+ | пока игнорировался такой аспект, как массивы. Чем плохи массивы. Массив это мало того, что имя, у него ещё есть индекс. a[i] и a[j] они могут быть при опр условиях алиасами, при опр не могут. Работа с массивами требует тонкой работы с индексами. Можно считать массивы как структуры одной большой помойкой. Массив можно взять и для каждого элемента массива хранить отдельный AML. Тогда операции слияния надо обрабатывать более тонко. Например: | ||
+ | Первое уточнение: | ||
+ | i: 5 i: 2 i: 4 | ||
+ | {5, 2, 4} | ||
+ | |||
+ | Второй вариант, хранить для чисел интервалы: | ||
+ | [2, 5] | ||
+ | Второе: | ||
+ | в языке Си есть замечательные конструкции типа *p++, то есть указатель может указывать в кусочек массива по какому-то смещению. Хранить множество AML недостаточно, мы можем хранить пары <AML offset>. Появляется инкремент указателей (раньше получ переопр), арифметика с указателями, возможность хоть как-т оотслеживать индексы, и т. д. | ||
+ | |||
+ | В результате точность улучшим, но будем тратить больше памяти и работатьмедленнее. | ||
+ | |||
+ | След вещи: | ||
+ | a=b+1; | ||
+ | В процессе работы может оказаться полезным сохранить это неравенство. В результате получим задачу целочисл линейного программирования. Если мы его решим, то получим некоторые свойства программы. Этих задач до полна. | ||
+ | |||
+ | Второй подход для повышения точности – в точке, где появилась ошибка, будем откручивать назад, строить простейшие предуслови и, возможно, какие-то интервалы пропадут. | ||
+ | |||
+ | Наука здесь кончается, дальше начинаются хаки. | ||
+ | |||
+ | {{Введение в теорию построения оптимизирующих компиляторов}} | ||
+ | {{Lection-stub}} |
Текущая версия
Предыдущая лекция | Следующая лекция
Список имеет важное сельскохозяйственное значение
Лектору на экзамене будет интересано, что мы поняли, какие выводы сделали, и вообще.
Alias analysis (анализ алиасов, указателей, синонимов)
Данные хранятся в адресуемых ячейках памяти. Ячейка может выстуцпать под несколькими именами. Есть переменная a , есть указатель pa:
int a; int pa; pa=*a;
алиас: *pa – a
Задача, определить, какие имена должеы адрес к одной ячейке памяти.
for (a=0; a<n; a++) - не можем брать переменную на регистр, потому, что исп под другим именем { *pa = }
Время жизни:
a=0 ... b = *pa – до сюда есть
то же относится к анализу достигающих определений, и т. д.
Самый простой способ анализа, лектор назовёт его так, это даже не способ анализа, а некоторой ..., консервативнй анализ алиасов. Мы делаем его, когда не хотим делать никаких сложных уравнений, анализа данных.
*pa – может обращаться ко всему.
Понятно, что это грубый подход. Это очень негативно влияет на интервалы жизни, никакую оптимизацию провести н омжем.
Откуда такой негативный эффект – поскольку обращ ко всему, то присваивание b = *pa; эквивалентно b=a1, b=a2 ... и строя решение уравнения потока, мы получим очень грубое решение, которое не позволит ничего сделать.
Такой консервативнй анализ мы делаем, если не можем сделать ничего больше.
Следующий способ: анализ алиаса, базирующийся на типах (type-based alias analysis).
t * pa – может алиасить всё, имеющее тип t.
Если мы рассмотрим Си, то такое поведение оговорено в стандарте.
Типы void * и char * могут указывать на всё, что угодно.
В том же языке Си есть некрые средства, которые позволяют облегчить процесс анализа. В язык Си ввведено ключ слово restrict. оно может использоваться только в ... . void f (void * restrict a, void * restrict b) – необходимо, чтобы a и b не указывали на одну и ту же область памяти.Например, многие функции стандартной библиотеки являются такими.
Простенький пример:
void f(int n) { int a, b, c; int *p1 = &a, *p2; L1: ... if (n>0) { p2 = &b; L2: ... } else { p2 = &c; L3: ... } L4: ... }
Варианты:
- flow-insensitive must alias analysis – ведём анализ безотносительно потока управления. must – явл. обязательными. Например: (*p1, a) – пара must alias, про другое сказать уже ничего не можем.
alias принадлжеит V x V, V – множество переменных
- flow-insensitive may alias – отношние алиасинга может выолняться в некрой точке функции. (*p1, a), (*p1, b), (*p1, c).
Полныйй анализ алиасов алгоритмически неразрешим.
- flow-sensitive must – теперь, помимо пары переменных появляется третье измерениеп – точка программы. Что можно вычислить про точку 1..4:
- L1: (*p1, a)
- L2: (*p1, a), (*p2, b)
- L3: (*p1, a), (*p2, c)
- L4: (*p1, a)
- Теперь для каждой точки программы можно гарантированно знать, является ли переменная алиасом.
- flow-sensitive may
L4: (*p1, a), (*p2, b), (*p2, c)
Самый информативный из них последний.
Если переходим на межпроцедурный уровень, то появляется понятие context sensitive/insensitive.
Пусть есть процедура Р. Возможно, она вызывается из неск. мест и , возможно, она возвр. Значение. Когда context-in, сливаем все вызовы в один, и сливаем все контексты вызова (join). Получаем выходной контекст, и ставимего в места вызова. Тут два ист неопр – на входе и на выходе.
context-sensitive – каждый вызов рассматривается отдельно. Минус – всё это сильно разрастается.
Как правило, все совр реализации context-ins
Наиболее распрост вариант, который исп в продвинутых анализаторах – flow sens cotext insens alias analysis
Уже при реализации анализа есть выбор между двумя вариантами:
- Символические выражения, адресующие память и отношения между ними. *pa, a, b[10], pa->pb->p
- Абстрактные вычисления с исп. моделирования памяти. Мы вводим понятие абстрактной ячейки памяти (abstract memory location) для каждой переменной, которая сущ в программе, создаём отдельный AML. Кроме того, мы создаём ананомную память (anon) – память вообще, в куче. anon(t) – память в куче опред типа
AML: name type value
bool+int – будем хранить стандартную реш тку продвижения констант (_|_, T, val) pointers - _|_, T, множество расширенных AML(set of ext. AML). Сюда могут входить ве AML, созданные в программе, кроме того может попадать ананимная или типизир память, а также null.
Все остальные типы рассмотрим потом.
Принципиальные ограничеиня:
- Насколько глудоко заглядываем в структуру
- насколько глубоко хотим различать дин. объекты
- размер мн. вл для указателей
Естественно, что такого рода ограничения неизбежно понижают точность анализа.
Итак, появились три типа ячеека памяти, ввели ограничения. Осталось пройти по программе и информацию получить.
Две фазы:
- Сбор алиасов. Мы идём по исх программе и в соотв с правилами языка мы помещаем некоторые точки, могут они быть алиасами или не могут.
- Распространение о функциям (языко-независимые, forward dfa). В один проход можно собирать алиасы и с помощью f. dfa их продвигать
Для начала для параметра функции генерируем AML. Значение неопр. Для лок переменных трёл то же, для p1 создаётся AML, у которого множ знач будет ссылаться на a, у p2 будет тоже неопределённость.
p = 0 – как изменяется AML? aml(p).value={null} p = malloc(s) – aml(p).value = {anon(type(p))} p = &a – aml(p).value = {aml(a)} p2=p1 – aml(p2).value={aml(p1).value}
и так далее
Тонкости: Разыменование
a=*p – aml(a) – если множество аэмелей указывает на множество аэмелей, у которых одно значение, то его присваиваем, иначе переопределённость
Всё, до чего может дотянуться вызываемая функция, становится переопределённым.
Слияние графа потока управления:
i L1: v1 i L2: v2 L3: v1 объединение v2
Можно выписать все правила для всех конструкций языка, итерирукем по функциям, в итоге всё сойдётся и получим все AML. В большинстве случаев там будет неопр.
Всё множество AML мы храним для каждой точки, и это весьма прожорливо.
Локальные хаки: пока игнорировался такой аспект, как массивы. Чем плохи массивы. Массив это мало того, что имя, у него ещё есть индекс. a[i] и a[j] они могут быть при опр условиях алиасами, при опр не могут. Работа с массивами требует тонкой работы с индексами. Можно считать массивы как структуры одной большой помойкой. Массив можно взять и для каждого элемента массива хранить отдельный AML. Тогда операции слияния надо обрабатывать более тонко. Например: Первое уточнение:
i: 5 i: 2 i: 4 {5, 2, 4}
Второй вариант, хранить для чисел интервалы:
[2, 5]
Второе: в языке Си есть замечательные конструкции типа *p++, то есть указатель может указывать в кусочек массива по какому-то смещению. Хранить множество AML недостаточно, мы можем хранить пары <AML offset>. Появляется инкремент указателей (раньше получ переопр), арифметика с указателями, возможность хоть как-т оотслеживать индексы, и т. д.
В результате точность улучшим, но будем тратить больше памяти и работатьмедленнее.
След вещи:
a=b+1;
В процессе работы может оказаться полезным сохранить это неравенство. В результате получим задачу целочисл линейного программирования. Если мы его решим, то получим некоторые свойства программы. Этих задач до полна.
Второй подход для повышения точности – в точке, где появилась ошибка, будем откручивать назад, строить простейшие предуслови и, возможно, какие-то интервалы пропадут.
Наука здесь кончается, дальше начинаются хаки.
Введение в теорию построения оптимизирующих компиляторов
Календарь
вт | вт | вт | вт | вт | |
Сентябрь
| 19 | 26 | |||
Октябрь
| 10 | 24 | 31 | ||
Ноябрь
| 07 | 14 | 21 | ||
Декабрь
| 05 | 12 |