7. Методики оптимизации кода для risc-процессоров

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

Предназначен для отслеживания обращения по указателю к той или иной переменной.

int *p;

int x,y;

…

y = 1;

*p = 10;

x = y;

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

Передача параметров подпрограмм в регистрах.

В CISC-процессорах параметры в процедуры обычно передаются через программный. Наличие большого регистрового файла в большинстве RISC-процессоров позволяет передавать часть параметров через регистры. Такой подход обычно повышает производительность программы как при передаче параметров (не нужно обращаться к памяти, чтобы затолкнуть операнды в стек), так и при обращении к ним в вызванной подпрограмме (не нужно обращаться к памяти, чтобы прочитать операнды из стека; к тому же операции могут выполняться непосредственно над полученными регистрами).

Разворачивание циклов

Это способ оптимизации, при котором эффективность выполнения программы повышается за счет увеличения объема программного кода. Такой прием дает два преимущества:

- приводит к уменьшению числа проверок условия окончания цикла и выполнения условных переходов по сравнению с числом "полезных" команд тела цикла;

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

for (j=0; j<n; j++)

x += x;

После разворачивания цикл будет выглядеть так:

for (j=0; j<n; j+=4)

{

x += x;

x += x;

x += x;

x += x;

}

Межпроцедурный анализ (Interprocedural Analysis, IPA)

Используется технология, похожая на анализ алиасов и позволяющая компилятору максимально "быть в курсе" того, какие переменные и регистры модифицируются в конкретном участке кода. Если анализ алиасов предоставляет сведения, касающиеся возможной адресации указателя на ту или иную область памяти, IPA анализирует возможность модификации регистра или переменной в результате вызова функции.

int a[10], b[10], c;

void bar()

{

c++;

}

void foo()

{

int i;

for (i=1; i<10; i++)

{

b[0] =b[0] + a[i];

bar();

} }

Результат компиляции цикла без IPA-оптимизации (на промежуточном языке):

…

r5 = 1

loop_start:

r6 = r5 * 2

load r1, b

load r2, a[r6]

r1 = r1 + r2

save b, r1

call bar

r5 = r5 + 1

cmp r5, 10

if less jump loop_start

…

Результат компиляции цикла с IPA-оптимизацией (на промежуточном языке):

…

load r1, b

r5 = 1

loop_start:

r6 = r5 * 2

load r2, a[r6]

r1 = r1 + r2

call bar

r5 = r5 + 1

cmp r5, 10

if less jump loop_start

save b, r1

…

Использование IPA-анализа позволило отказаться от постоянного сохранения значения b[0] в память, поскольку компилятор имеет информацию о том, что функция bar() использует только глобальную переменную c и не работает с b[0]. Это привело к повышению производительности программы и сокращению программного кода.

Оптимизации на уровне архитектуры процессора или машинных команд

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

- сокращение накладных расходов на условные переходы: отказ от специальных команд проверки условий (типа cmp в ассемблере Intel), анализ флагов и выполнение условных переходов непосредственно по результатам арифметических и логических команд; выполнение операций по условию вместо выполнения условных переходов;

- замена доступа к элементам массива по индексам на доступ по указателям;

- замена условий в циклах по счетчику. Если переменная цикла не используется в теле цикла в качестве операнда, то для проверки условия завершения цикла вместо кода с проверкой переменной на равенство заданной константе выполнять сравнение ее с нулем:

До машинной оптимизации на уровне команд	После машинной оптимизации на уровне команд
for (i=0; i<100; i++) a += random();	for (i=100; i>0; i--) a += random();

Реализация второго варианта цикла всегда будет более эффективна, поскольку не требуется отдельная команда для сравнения с нулем. Каким является значение счетчика цикла после декрементирования можно определить сразу же по флагам. Это типичный пример Code Selection-оптимизации, когда две инструкции проверки и перехода заменяются на одну;

Управление порядком выполнения инструкций.

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

Оптимизация ветвлений

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

Исходный код	Код после оптимизации
flag = 0; while (!flag) { ...aaa... stml (); ...bbb... if (e1) break; ...ccc... if (e2) { ...ddd... flag = 1 ; ...eee... } } if (flag) { ...ttt... stm2 (); }	L1: ...ааа... stml (); ...bbb... if (e1) goto L2; /* через stm2,т.к. flag1=0 */ ...ccc... if (!e2) /* if !e2 в начало */ goto L1; ...ddd... ...eee... ...ttt... stm2 (); L2:

Компилятор определяет, что вход в цикл выполняется в любом случае, и поэтому функция stml() будет вызываться всегда. Компилятор также определяет, что stm2() никогда не будет выполнена, если flag=0 и если e1=1 – тогда flag "навсегда останется" равным "0". Эти сведения позволяют компилятору сгенерировать более эффективный код.