Анализ алиасов

Анализ алиасов (Alias Analysis) по своей сути не является методом оптимизации, однако позволяет повысить эффективность других алгоритмов оптимизации. Анализ предназначен для отслеживания обращения по указателю к той или иной переменной.

int *p;

int x,y;

…

y = 1;

*p = 10;

x = y;

Без выполнения анализа алиасов, отслеживающего адрес, на который указывает указатель p, компилятор не может знать, модифицирует ли команда *p=10 переменную y? Соответственно, он не может заменить последнюю инструкцию на более простую команду x=1 (для ее выполнения не нужно читать из памяти переменную y). Если выполненный анализ позволяет сделать вывод о том, что p не указывает на y, то компилятор заменяет последнюю инструкцию.

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

int x, y, j;

x = 5;

a[j] = 0;

y = x;

Для программиста совершенно очевидно, что операция a[j]=0 не может повлиять на значение переменной x. Но реализация массива обычно выполняется с использованием указателей, например, *(a+j) = 0. Без использования анализа алиасов компилятор не сможет заменить последнюю инструкцию на y=5 (кстати, использование анализа поможет только в том случае, если компилятор сможет однозначно определить диапазон изменения индекса j).

Результаты анализа используются при оптимизации порядка выполнения инструкций, распространения констант, распространения копирования, удаления общих подвыражений.

Распространение констант (constant propagation) выполняется путем замены переменной в выражении ее константным значением. Например, фрагмент

int x, y, z;

x = 2;

y = x * z;

после распространения констант будет выглядеть так:

int x, y, z;

x = 2;

y = 2 * z;

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

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

int x, y, z;

x = z;

y = x;

После применения:

int x, y, z;

x = z;

y = z;

После первого чтения переменной z из памяти оно может быть помещено в регистр и использоваться в последней операции присваивания, исключая тем самым лишнюю операцию чтения переменной x из памяти.

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

int a, b, c, x, y, z;

x = a * b;

y = a * b + 5;

z = a * b * c;

После применение алгоритма:

int a, b, c, x, y, z;

register int tmp;

x = tmp = a * b;

y = tmp + 5;

z = tmp * c;

Понятно, что эффективность описанных выше методик зависит от того, сколько раз компилятор сможет их применить. Анализ алиасов позволяет сделать более "прозрачными" случаи, когда запись нового значения в ячейку памяти, на которую указывает указатель, изменяет какую-либо переменную из тех, что компилятор собирается "распространять". Это дает возможность более широко применять рассмотренные методики.