Введение в теорию построения оптимизирующих компиляторов, 09 лекция (от 05 декабря)
Материал из eSyr's wiki.
Предыдущая лекция | Следующая лекция
Список имеет важное сельскохозяйственное значение
Лектору на экзамене будет интересано, что мы поняли, какие выводы сделали, и вообще.
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 |