Введение в теорию построения оптимизирующих компиляторов, 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:	...
}

Варианты:

1. flow-insensitive must alias analysis – ведём анализ безотносительно потока управления. must – явл. обязательными. Например: (*p1, a) – пара must alias, про другое сказать уже ничего не можем.

alias принадлжеит V x V, V – множество переменных

1. flow-insensitive may alias – отношние алиасинга может выолняться в некрой точке функции. (*p1, a), (*p1, b), (*p1, c).

Полныйй анализ алиасов алгоритмически неразрешим.

1. flow-sensitive must – теперь, помимо пары переменных появляется третье измерениеп – точка программы. Что можно вычислить про точку 1..4:
   • L1: (*p1, a)
   • L2: (*p1, a), (*p2, b)
   • L3: (*p1, a), (*p2, c)
   • L4: (*p1, a)
   • Теперь для каждой точки программы можно гарантированно знать, является ли переменная алиасом.
2. 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

Уже при реализации анализа есть выбор между двумя вариантами:

1. Символические выражения, адресующие память и отношения между ними. *pa, a, b[10], pa->pb->p
2. Абстрактные вычисления с исп. моделирования памяти. Мы вводим понятие абстрактной ячейки памяти (abstract memory location) для каждой переменной, которая сущ в программе, создаём отдельный AML. Кроме того, мы создаём ананомную память (anon) – память вообще, в куче. anon(t) – память в куче опред типа

AML:
 name
 type
 value

bool+int – будем хранить стандартную реш тку продвижения констант (_|_, T, val) pointers - _|_, T, множество расширенных AML(set of ext. AML). Сюда могут входить ве AML, созданные в программе, кроме того может попадать ананимная или типизир память, а также null.

Все остальные типы рассмотрим потом.

Принципиальные ограничеиня:

1. Насколько глудоко заглядываем в структуру
2. насколько глубоко хотим различать дин. объекты
3. размер мн. вл для указателей

Естественно, что такого рода ограничения неизбежно понижают точность анализа.

Итак, появились три типа ячеека памяти, ввели ограничения. Осталось пройти по программе и информацию получить.

Две фазы:

1. Сбор алиасов. Мы идём по исх программе и в соотв с правилами языка мы помещаем некоторые точки, могут они быть алиасами или не могут.
2. Распространение о функциям (языко-независимые, 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;

В процессе работы может оказаться полезным сохранить это неравенство. В результате получим задачу целочисл линейного программирования. Если мы его решим, то получим некоторые свойства программы. Этих задач до полна.

Второй подход для повышения точности – в точке, где появилась ошибка, будем откручивать назад, строить простейшие предуслови и, возможно, какие-то интервалы пропадут.

Наука здесь кончается, дальше начинаются хаки.