BASM - Уроки для начинающих. Часть 1.

Содержание материала

Уроки для начинающих

Денис Христенсен

Из news://forums.borland.com

borland.public.Delphi.languages.basm

Введение

Серия статей, названная “BASM for beginners” (BASM уроки для начинающих) в данный момент состоит из 7 статей. Общее для этих статей и для тех, что в процессе подготовки то, что они объясняют некоторые вопросы использования BASM на примерах функций. Большинство из этих функций сначала реализуются на Паскале, затем сгенерированный компилятором ассемблерный код, копируется из окна CPU view в Delphi, затем анализируется и оптимизируется. Иногда оптимизация включает в себя и использование инструкций MMX, SSE или SSE2.

В самом начале рассматривается код сделанный компилятором, в котором использует только наиболее используемые инструкции из огромного набора инструкций 32-битной архитектуры Intel. Просматривая, сгенерированный компилятором код, мы получаем представление и об эффективности компилятора, в общем, и о компиляторе Delphi в целом.

Когда применимо, то приводятся обобщения по оптимизации ассемблерного кода. Эта общая оптимизация применима к компиляторам и большинство компиляторов, включая Delphi, ее имеют. Когда ни будь, в будущем будет разработан инструмент по автоматической оптимизации ассемблерного кода.

Знание об используемом процессоре очень необходимы при оптимизации кода и поэтому также разъясняются множество подробностей о CPU, таких как например конвейеры.

Насколько Я знаю, имеется очень мало литературы, в которой объясняются все эти особенности, на уровне, который был бы понятен начинающим. Я надеюсь, что эта серия статей сможет помочь им в этом.

С уважением,

Денис Христенсен
Dennis Kjaer Christensen.

Урок 1

Начнем с небольшого примера. Это простая функция Паскаля по умножению целого на константу 2.

Code:

function MulInt2(I : Integer) : Integer;

begin

Result := I * 2;

end;

Посмотрим сгенерированный код в окне CPU view. Я компилировал с включенной оптимизацией.

Code:

function MulInt2_BASM(I : Integer) : Integer;

begin

Result := I * 2;

{

add eax,eax

ret

}

end;

Здесь мы видим, что параметр передается в функцию в регистре EAX и результат возвращается в том же регистре. Это соглашение по передаче параметров через регистры (register calling convention), которое является соглашением по умолчанию в Delphi. Актуальный код очень простой, умножение на 2 заменяется сложением операнда с самим собой, I + I = 2I. Инструкция RET возвращает управление в строку, следующую за вызовом функции.

Сделаем тот же код, как чистую asm функцию.

Code:

function MulInt2_BASM2(I : Integer) : Integer;

asm

//Result := I * 2;

add eax,eax

//ret

end;

Заметим, что возврат из функции обеспечивается встроенным ассемблером.

Теперь посмотрит на код вызова функции.

Вот Паскаль код:

Code:

procedure TForm1.Button1Click(Sender: TObject);

var

I, J : Integer;

begin

I := StrToInt(IEdit.Text);

J := MulInt2_BASM2(I);

JEdit.Text := IntToStr(J);

end;

Важная для нас строка следующая

J := MulInt2_BASM2(I);

В окне CPU мы видим

Code:

call StrToInt

call MulInt2_BASM2

mov esi,eax

После вызова StrToInt из строки выше вызова нашей функции, I находится в регистре EAX. (StrToInt также следует соглашению о передаче параметров через регистры). Функция MulInt2_BASM2 вызывается, и возвращает свой результат в регистре EAX, который в следующей строке копируется в регистр ESI.

Замечание об оптимизации: Умножение на два может быть сделано двумя различными путями. С помощью инструкции MUL или сдвигом влево на один разряд. Инструкция MUL описана в руководстве разработчика (Intel IA32 SW developers manual 2) на странице 536. Данная инструкция умножает значение в регистре EAX на другой регистр, результат помещается в регистровую пару EDX:EAX. Регистровая пара необходима, потому что в результате умножения двух 32-битных регистров получается 64-бита, подобно 9*9=81 – два однозначных числа дают результат из двух цифр.

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

"Выражения asm должны сохранять регистры EDI, ESI, ESP, EBP и EBX, но могут свободно изменять регистры EAX, ECX и EDX."

Отсюда мы делаем вывод, что у нас не будет проблем с изменением регистра EDX в инструкции MUL и наша функция может быть реализована следующим образом.

Code:

function MulInt2_BASM3(I : Integer) : Integer;

asm

//Result := I * 2;

mov ecx, 2

mul ecx

end;

Также используется регистр ECX, но с этим тоже все в порядке. Так как результат меньше, чем диапазон для integer, то это также корректно возвращается в EAX. Но если I больше половины диапазона integer, то произойдет переполнение и результат будет неверным.

Реализация с помощью сдвига влево на один разряд

Code:

function MulInt2_BASM4(I : Integer) : Integer;

asm

//Result := I * 2;

shl eax,1

end;

Время выполнения в данном случае меньше. Мы можем также проконсультироваться с документацией Intel или AMD по таблицам латентности (latency) и по пропускной способности (throughput). От переводчика: в дальнейшем в документе будут использоваться термины - latency и throughput без перевода или латентность, поскольку нет хорошего эквивалента этим терминам или же будет использоваться термин пенальти. Смысл этих терминов следующий, команда может быть выполнена без пенальти (throughput). За минимальное время и с пенальти (latency) за полное, это особенность работы с конвейерами, на мой взгляд, автору стоило заострить эту особенность в данном месте, возможно, это будет сделано позже. Инструкции ADD и MOV выполняются за 0.5 цикла в обоих случаях, Инструкции MUL за 14-18 циклов (latency) и 5 циклов (throughput). Инструкции SHL за 4 цикла (latency) и 1 цикл (throughput). Версия, выбранная в Delphi наиболее эффективна для процессоров P4 и вероятно также для Athlon и P3.

Не рассматриваются: версия MUL против IMUL, контроль диапазона, другие соглашения о вызове, измерение производительности, подсчет тактов для других процессоров, подсчет тактов для CALL + RET, расположение адреса возврата и другое.

Урок 2

Это вторая глава введения в программирование с помощью BASM в Delphi. В первой главе было короткое введение в целочисленный код, а в этой главе введение в код с плавающей запятой. В нашем примере мы рассчитаем полином второго порядка. Параметры A, B и C, которые определяют полином, закодированы как локальные константы. В функцию передается переменная X типа double и результат также типа double. Функция выглядит так.

Code:

function SecondOrderPolynomial1(X : Double) : Double;

const

A : Double = 1;

B : Double = 2;

C : Double = 3;

begin

Result := A*X*X + B*X + C;

end;

Просмотр кода в окне CPU показывает следующее.

Code:

function SecondOrderPolynomial2(X : Double) : Double;

const

A : Double = 1;

B : Double = 2;

C : Double = 3;

begin

{

push ebp

mov ebp,esp

add esp,-$08

}

Result := A*X*X + B*X + C;

{

fld qword ptr [A]

fmul qword ptr [ebp+$08]

fld qword ptr [B]

fmul qword ptr [ebp+$08]

faddp st(1)

fadd qword ptr [C]

fstp qword ptr [ebp-$08]

wait

fld qword ptr [ebp-$08]

}

{

pop ecx

pop ebp

}

end;

Попробую объяснить ассемблерный код, строка за строкой. Код begin выглядит в коде так.

Code:

begin

{

push ebp

mov ebp,esp

add esp,-$08

}

Здесь устанавливается фрейм стека для функции. Фрейм стека просто часть памяти, которая выделена в стеке. Фрейм стека доступен через два указателя, указатель базы и указатель стека. Указатель базы это регистр EBP и указатель стека это регистр ESP. Эти два регистра резервированы только для использования в качестве этих указателей. Первая инструкция PUSH EBP сохраняет указатель базы. В строке MOV EBP, ESP устанавливается новая база для адресации по стеку. В строке ADD ESP, -$08 указатель стека смещается на 8 вниз. Как курьез, стек увеличивается вниз, и более понятной командой было бы его установка с помощью инструкции SUB ESP, 8. Новый фрейм стека устанавливается с помощью этих трех строк, поверх старого фрейма, который был размещен функцией, которая вызвала нашу функцию SecondOrderPolynomial.

Следующая строка Паскаля компилируется в 9 строк на ассемблере.

Code:

Result := A*X*X + B*X + C;

{

fld qword ptr [A]

fmul qword ptr [ebp+$08]

fld qword ptr [B]

fmul qword ptr [ebp+$08]

faddp st(1)

fadd qword ptr [C]

fstp qword ptr [ebp-$08]

wait

fld qword ptr [ebp-$08]

}

Для тех, кто использует калькуляторы HP для расчетов с плавающей запятой, данный код очень прост для понимания. В первой строке, FLD QWORD PTR [A], загружается константа A в регистр стека с плавающей запятой. Строка, FMUL QWORD PTR [EBP+$08], умножает A на X. Это понятно при просмотре Паскаль кода, но что означает "QWORD PTR [EBP+$08]". QWORD PTR означает "указатель на двойное слово, которое размером с double (64 бита). Значение указателя между квадратными скобками [EBP+$08]. Регистр EBP это указатель базы и $08 это – да просто 8. Поскольку стек при увеличении движется вниз, то это смещение на 8 байт вверх относительно указателя базы в текущем фрейме. Здесь находится переданный параметр X, помещенный сюда вызывающей функцией. При соглашение о регистром вызове, значение не помещается в 32-разрядный регистр, но оно хорошо помещается в регистр с плавающей запятой. Borland решил передавать параметры с плавающей запятой двойной точности через стек, но передача через регистры с плавающей запятой, была бы более эффективной. Следующие три строки не требуют специального пояснения, but the line, но инструкция FADDP ST(1), нуждается в объяснении. Все инструкции с плавающей запятой начинаются с префикса f. add это сложение. ST(1) это название регистра с плавающей запятой номер 1, который является вторым, поскольку первый регистр это ST(0)! Регистры с плавающей запятой скомпонованы в стек и инструкции по умолчанию работаю с верхушкой стека, которая равна ST(0). FADDP ST(1) идентична инструкции FADDP ST(0), ST(1) - складывает содержимое регистров ST(0) и ST(1), результат помещается в регистр ST(1). P в FADDP означает POP ST(0) из стека. Таким путем результат помещается в ST(0). Строка FADD QWORD PTR [C] заканчивает вычисление, и единственная вещь, которая осталась, это помещения результата в ST(0). Результат и так уже там, поэтому две следующие строки кода излишни.

fstp qword ptr [ebp-$08]

fld qword ptr [ebp-$08]

Они просто копируют результат на стек и обратно. Такая затрата времени и энергии :-). Инструкция WAIT обеспечивает обработку возможных исключений при выполнении операций с плавающей запятой. Смотри руководство Intel SW Developers Manual Volume 2, страницу 822 для полного понимания этого.

Осталось объяснить еще три строки кода.

Code:

{

pop ecx

pop ebp

}

end;

Они возвращают фрейм стека, путем восстановления старого содержимого регистров ESP и EBP. Понятнее был бы следующий код.

add esp, 4

pop ebp

это также было бы более эффективным, и я не понимаю, почему компилятор увеличивает указатель стека таким странным методом. Вспоминаем, что регистр ECX можно использоваться свободно, назначать ему любые значения, поскольку они все равно не будет использовано далее.

Осталось также объяснить, что скрывается за [A] в строке fld qword ptr [A]. Мы знаем, что A должен быть указателем на место, где хранится само A в памяти. Адрес A закодирован в инструкции. Вот полная строка из окна CPU.

00451E40 DD05803C4500 fld qword ptr [B]

00451E40 это адрес инструкции в exe файле. DD05803C4500 это машинный код строки FLD QWORD PTR [B], которая более понятна для человеческого разума. При просмотре руководства Intel SW Developers Manual Volume 2, страница 280, мы увидим, что код команды для FLD равен D9, DD, DB или D9C0, в зависимости от типа данных. Мы узнаем, что DD это код для FLD DOUBLE. Остается еще 05803C4500. 05 это (Не знаю, может быть, кто-то поможет мне!), а 803C4500 это 32-битный адрес константы A.

Попробуем теперь преобразовать эту функцию в чистый ассемблерный код.

Code:

function SecondOrderPolynomial3(X : Double) : Double;

const

A : Double = 1;

B : Double = 2;

C : Double = 3;

asm

push ebp

mov ebp,esp

add esp,-$08

//Result := A*X*X + B*X + C;

fld qword ptr [A]

fmul qword ptr [ebp+$08]

fld qword ptr [B]

fmul qword ptr [ebp+$08]

faddp //st(1)

fadd qword ptr [C]

fstp qword ptr [ebp-$08]

wait

fld qword ptr [ebp-$08]

pop ecx

pop ebp

end;

Но мы теперь получили несколько сюрпризов. Во-первых, функция не компилируется. FADDP ST(1) не распознается, как допустимая комбинация команды и операндов. Снова консультируемся с руководством от Интел, мы узнаем, что FADDP существует только в одной версии. Она работает с ST(0), ST(1) и нет необходимости писать FADDP ST(0), ST(1) и только краткая форма FADDP единственно допустимая. После маскирования ST(1) наконец стало компилироваться.

Второй сюрприз. Вызов функции с X = 2 должен рассчитать Y = 2^2+2*2+3 = 11. Но SecondOrderPolynomial3 возвращает 3! Снова открываем окно просмотра FPU, так как окно CPU и трассируем код, наблюдая, что происходит. Видно, что A=1 корректно загружается в ST(0) в строке 4, но в строке 5, которая производит умножение A на X, 1 на 2, результат в ST(0) что-то очень маленький, в действительности 0. Это означает, что X близок к 0 вместо 2. Могут быть неверным две вещи. Вызывающий код передает неверное значение X или мы неправильно адресуем X. Сравнивая код вызова функций SecondOrderPolynomial3 и SecondOrderPolynomial1, мы видим, что он одинаков и поэтому не может быть причиной ошибки. Было бы большим сюрпризом, если бы Delphi делала это неверно! Пробуем опять трассировать код вызова, наблюдая за окном просмотра памяти в окне просмотра CPU. Зеленая стрелочка показывает позицию стека. Код вызова выглядит так:

Code:

push dword ptr [ebp-$0c]

push dword ptr [ebp-$10]

call SecondOrderPolynomial1

Два указателя помещаются на стек. Один из них это указатель на X. Но что за второй указатель. Просматриваем окно памяти и видим, что первый указатель это указатель на X, а второй нулевой указатель. При трассировке внутрь функции мы видим, что первые две строки повторяются. Компилятор автоматически вставляет инструкции PUSH EBP и MOV EBP, ESP. Поскольку инструкция PUSH уменьшает указатель стека на 4, то ссылка на X оказывается неверной. После того, как были убраны две первые строки, все пришло в норму.

Теперь после окончания анализа кода и понимания, что он делает, мы можем приступить к его оптимизации.

Для начала уберем два строки FSTP/FLD поскольку они лишние.

Code:

function SecondOrderPolynomial4(X : Double) : Double;

const

A : Double = 1;

B : Double = 2;

C : Double = 3;

asm

//push ebp

//mov ebp,esp

add esp,-$08

//Result := A*X*X + B*X + C;

fld qword ptr [A]

fmul qword ptr [ebp+$08]

fld qword ptr [B]

fmul qword ptr [ebp+$08]

faddp //st(1)

fadd qword ptr [C]

//fstp qword ptr [ebp-$08]

wait

//fld qword ptr [ebp-$08]

pop ecx

pop ebp

end;

Есть также одна ссылка на фрейм стека, которая не нужна.

Code:

function SecondOrderPolynomial5(X : Double) : Double;

const

A : Double = 1;

B : Double = 2;

C : Double = 3;

asm

//push ebp

//mov ebp,esp

//add esp,-$08

//Result := A*X*X + B*X + C;

fld qword ptr [A]

fmul qword ptr [ebp+$08]

fld qword ptr [B]

fmul qword ptr [ebp+$08]

faddp //st(1)

fadd qword ptr [C]

wait

//pop ecx

//pop ebp

end;

После удаления этих шести строк, наша функция уменьшилась до следующего:

Code:

function SecondOrderPolynomial6(X : Double) : Double;

const

A : Double = 1;

B : Double = 2;

C : Double = 3;

asm

//Result := A*X*X + B*X + C;

fld qword ptr [A]

fmul qword ptr [ebp+$08]

fld qword ptr [B]

fmul qword ptr [ebp+$08]

faddp

fadd qword ptr [C]

wait

end;

X загружается из памяти в FPU три раза. Было бы более эффективным загрузить его один раз и повторно использовать.

Code:

function SecondOrderPolynomial7(X : Double) : Double;

const

A : Double = 1;

B : Double = 2;

C : Double = 3;

asm

//Result := A*X*X + B*X + C;

fld qword ptr [ebp+$08]

fld qword ptr [A]

fmul st(0), st(1)

fld qword ptr [B]

fmul st(0), st(2)

ffree st(2)

faddp

fadd qword ptr [C]

wait

end;

Расскажем о магии данного кода. Во-первых, в первой строке загружаем X. Во второй строке загружаем A. В третьей строке умножаем A на X. В четвертой строке умножаем a*X, расположено в ST(0) на X. Так мы выполнили первое вычисление. Загружаем B и умножаем его на X, этим выполняем второе вычисление. Это последняя необходимость в X и мы освобождаем регистр ST(2), в котором оно хранится. Теперь складываем вычисления 1 и 2 и выкидываем вычисление 2 из стека. Единственно, что нам осталось, это прибавить C. Результат теперь в регистре ST(0) и все остальные регистры освобождены. Теперь мы проверяем на возможные ошибки вычислений и заканчиваем. Теперь кажется, что лишних операций нет и код вполне оптимальный.

Осталась еще инструкции для загрузки часто используемых констант в арифметический сопроцессор, одна из них это 1которая может быть загружена инструкцией fld1. Использование ее убирает одну загрузку из памяти, которая может привести к потерям тактов, если данные неверно выровнены.

Code:

function SecondOrderPolynomial8(X : Double) : Double;

const

//A : Double = 1;

B : Double = 2;

C : Double = 3;

asm

//Result := A*X*X + B*X + C;

fld qword ptr [ebp+$08]

//fld qword ptr [A]

fld1

fmul st(0), st(1)

fld qword ptr [B]

fmul st(0), st(2)

ffree st(2)

faddp

fadd qword ptr [C]

wait

end;

Урок 3

Тема третьего урока MMX и SSE2, одновременно будет обсуждена 64-битная математика. И мы впервые обратим внимание на зависимость оптимизации оп процессорам.

Пример выглядит следующим образом.

Code:

function AddInt64_1(A, B : Int64) : Int64;

begin

Result := A + B;

end;

Посмотрим теперь ассемблерный код.

Code:

function AddInt64_2(A, B : Int64) : Int64;

begin

{

push ebp

mov ebp,esp

add esp,-$08

}

Result := A + B;

{

mov eax,[ebp+$10]

mov edx,[ebp+$14]

add eax,[ebp+$08]

adc edx,[ebp+$0c]

mov [ebp-$08],eax

mov [ebp-$04],edx

mov eax,[ebp-$08]

mov edx,[ebp-$04]

}

{

pop ecx

pop ebp

//ret

}

end;

Первые три строки устанавливают фрейм стека, так же как в предыдущих уроках. В данный момент мы уже знаем, что компилятор самостоятельно добавляет первые две строки. Последние три строки так же хорошо знакомы нам. Опять строку POP EBP компилятор добавляет сам. Теперь посмотри, что же это за восемь строк.

Code:

Result := A + B;

{

mov eax,[ebp+$10]

mov edx,[ebp+$14]

add eax,[ebp+$08]

adc edx,[ebp+$0c]

mov [ebp-$08],eax

mov [ebp-$04],edx

mov eax,[ebp-$08]

mov edx,[ebp-$04]

}

Анализ показывает, что они работают парами, осуществляя 64-битную математику на основе 32-битных регистров. Первые две строки загружают параметр A в регистровую пару EAX:EDX. Команды загружают непрерывный 64-битный блок данных из предыдущего стекового фрейма, показывая нам, что A был помещен на стек. Указатели отличаются на 4 байта. Первый из них указывает на младшую часть A и другой на старшую часть A. Затем производится два сложения. Первое это обычное сложение, а второе сложение с переносом. Указатели в данном случае относятся к параметру B по тем же правилам, как и параметр A. Первое сложение добавляет младшие 32 бита операнда B к младшим битам операнда A. При этом может возникнуть перенос, если результат больше, чем может поместиться в 32 битах. Это перенос включается в сложение старших 32 бит. Что бы сделать это окончательно понятным рассмотрим на простом примере для десятичных чисел. При сложении 1 + 2 = 3. Для наших воображаемых чисел, наш мозговой «CPU» будет двухразрядным процессором. Это означает, что сложение реально выглядит как 01 + 02 = 03. Пока еще нет переноса из младшей цифры в старшею, которая равная 0. Пример номер 2 для десятичных чисел. 13+38=?. Сначала мы складываем 3 + 8 = 11. Теперь результат имеет перенос и 1 в младшем разряде. Затем мы складываем Перенос + 1 + 3 = 1 + 1 + 3 = 5. Результат равен 51. В третьем примере мы рассмотрим случай с переполнением. 50 + 51 = 101. 101 слишком велик, что бы разместиться в двух разрядах и наш «CPU» не сможет выполнить расчет. Здесь также получился перенос при сложении двух старших цифр. Вернем в код. Могут произойти две вещи. Если мы компилировали без проверки диапазонов, то результат будет обрезан. При включенной проверке диапазонов будет возбуждено исключение. Мы не видим проверки на диапазон в нашем коде, и поэтому будет производиться усечение результата.

Следующие две строки помещают результат обратно на стек. А затем следующие две строки возвращают результат обратно в EAX и EDX, который и так уже здесь. Эти 4 строки абсолютно излишни. Они могут быть удалены и также не требуется и фрейм стека. Это так просто для оптимизатора ;-)

Code:

function AddInt64_6(A, B : Int64) : Int64;

asm

mov eax,[ebp+$10]

mov edx,[ebp+$14]

add eax,[ebp+$08]

adc edx,[ebp+$0c]

end;

Теперь это прекрасная маленькая функция. Компилятор сгенерировал код из 16 строк, а мы его уменьшили до 4. Сегодня Delphi реально слепая.

Теперь подумаем так: Если бы мы имели 64-битные регистры, то сложение могло бы быть выполнено с помощью двух строк кода. Но MMX регистры уже 64-битные и может быть, мы получим преимущества при их использовании. В руководстве Intel SW Developers Manual для инструкций не указана принадлежность к IA32, MMX, SSE или SSE2. Было бы превосходно иметь эту информацию, но мы должны искать ее где-то в другом месте. Я обычно использую три маленькие программы от Intel. Они называются «computer based tutorials on MMX, SSE & SSE2». Я не знаю где их можно найти на Интеловском Веб сайте, но Вы можете написать мне, если они очень вам нужны. Они простые и удобные – очень иллюстративные. В них я нашел, что инструкция MOV для 64-битных операндов из памяти в MMX регистр, называется MOVQ. Символ Q означает QUAD WORD (четыре слова). MMX именуются, как MM0, MM1...MM7. В отличие от регистров FPU они не организованы в стек, и вы можете их использовать их как вам угодно. Попробуем загрузить регистр MM0. Инструкция выглядит так:

movq mm0, [ebp+$10]

Есть два пути. Мы можем загрузить операнд B также в регистр. Очень просто посмотреть, как это происходит при помощи окна просмотра FPU. Регистры MMX сделаны псевдонимами к FP регистрам и окно FPU может показывать оба набора. Переключение между просмотром FP и MMX делается выбором "Display as words/Display as extendeds" в меню. Второй путь использовать шаблоны из «IA32 implementation» и выполнить сложение с ячейкой памяти B как источник. Два решения идентичны, поскольку CPU должен загрузить операнд B в регистр до выполнения операции сложения и сделать это явно с помощью инструкции MOV или неявно с помощью инструкции ADD, количество выполненных микроинструкций будет одинаковым. Мы используем более наглядный первый путь. Поэтому следующая строка снова MOVQ

movq mm1, [ebp+$08]

Затем взглянем на инструкцию сложения, которая выглядит так: PADDQ. P означает MMX, ADD означает сложение, а Q означает QUAD WORD. И снова мы в недоумении, поскольку здесь нет таких MMX инструкций. А что насчет SSE. Опять разочарование. В конце концов, SSE2 имеет это и мы счастливы или нет? Да если мы используем это на P4 и не запускаем на P3 или на Athlon. Так как мы почитатели P4 мы продолжаем все равно.

paddq mm0, mm1

Это строка очень понятна. Сложить MM1 с MM0.

Последнее действие это скопировать результат из MM0 в EAX:EDX. Для выполнения этого нам нужно инструкция пересылки двойного слова из MMX регистра, как источника, в регистр IA32, как приемник.

movd eax, mm0

Данная MMX инструкция выполняет эту работу. Она копирует младшие 32 бита регистра MM0 в EAX. Затем мы должны скопировать старшие 32 бита результата в регистр EDX. Я не нашел инструкции, которая могла бы сделать это и взамен этого воспользовался сдвигом старших 32 бит в младшие, с помощью 64-битной MMX инструкции сдвига.

psrlq mm0, 32

Затем копируя в регистр

movd edx, mm0

Что же мы сделали? В действительности мы использовали расширенные EMMS инструкции, поскольку нам нужны были MMX инструкции. Это очистило FP стек и оставило его в определенном чистом состоянии. EMMS на выполнение затрачивает 23 такта на процессоре P4. Совместно со сдвигом, который также не эффективен (2 цикла для throughput и latency) на P4. Наше решение не особенно быстро и работает только на P4, а на AMD этих вещей пока нет :-(

На этом мы заканчиваем третий урок. Мы оставили мяч повисшим в воздухе. Можем мы прийти к более эффективному решению? Передача данных между MMX регистрами и IA32 регистрами очень накладна. Соглашение о вызове не очень подходящее, поскольку данные перемещаются на стек, а не в регистры. EAX->MM0 занимает 2 такта. Другой путь занимает 5 циклов. EMMS требует 23 такта. Сложение только 2 cycles. Перегрузка налицо.

Урок 4

В данном уроке мы посмотрим насчет ветвления, рассматривая это на примере конструкции IF-ELSE. Условное перемещение для плавающей запятой также будет рассмотрено.

Примером для данного урока будет функция Min из модуля Delphi Math.

Code:

function Min1(const A, B: Single) : Single;

begin

if A < B then

Result := A

else

Result := B;

end;

Компилятор генерирует следующий ассемблерный код.

Code:

function Min2(const A, B: Single) : Single;

begin

{

00452458 55 push ebp

00452459 8BEC mov ebp,esp

0045245B 51 push ecx

}

if A < B then

{

0045245C D9450C fld dword ptr [ebp+$0c]

0045245F D85D08 fcomp dword ptr [ebp+$08]

00452462 DFE0 fstsw ax

00452464 9E sahf

00452465 7308 jnb +$08

}

Result := A

{

00452467 8B450C mov eax,[ebp+$0c]

0045246A 8945FC mov [ebp-$04],eax

0045246D EB06 jmp +$06

}

else

Result := B;

{

0045246F 8B4508 mov eax,[ebp+$08]

00452472 8945FC mov [ebp-$04],eax

}

{

00452475 D945FC fld dword ptr [ebp-$04]

00452478 59 pop ecx

00452479 5D pop ebp

}

end;

В данный момент я включил колонку address и opcode, поскольку они потребуются нам позже. Попробуем проанализировать строка за строкой, также как мы это делали ранее.

Code:

function Min3(const A, B: Single) : Single;

begin

{

push ebp // Save ebp on stack

mov ebp,esp // New basepointer is the old stackpointer

push ecx // subtract 4 from esp

}

if A < B then

{

fld dword ptr [ebp+$0c] // Load A on FP stack

fcomp dword ptr [ebp+$08] // FP compare A to B and pop A from stack

fstsw ax // Store FP statusword in ax

sahf // Store ah into EFlags register

jnb +$08 // If not below jump 8 bytes forward

}

Result := A

{

mov eax,[ebp+$0c] // Copy A into eax

mov [ebp-$04],eax // Copy A into stackframe

jmp +$06 // Jmp 6 bytes forward

}

else

Result := B;

{

mov eax,[ebp+$08] // Copy B into eax

mov [ebp-$04],eax // Copy B into stackframe

}

{

fld dword ptr [ebp-$04] // Load A or B from stackframe onto FP stack

pop ecx // Add 4 to esp

pop ebp // Restore ebp

}

end;

Я сделал комментарии для каждой строки кода. Детали немного ниже. Первая новая инструкция, обсуждаемая здесь это инструкция FCOMP. F как всегда означает инструкции с плавающей запятой. СOM означает сравнение и P означает POP из стека FP. FCOM сравнивает два операнда с плавающей запятой и устанавливает флаги по результату сравнения, именуемые как C0, C1, C2 и C3. Эти флаги эквивалентны регистру EFlags CPU. Данные флаги проверяются инструкциями условного перехода, в зависимости от их состояния производится или не производится переход. Инструкции условного перехода проверяют флаги CPU, а не FPU и поэтому необходимо копировать эти влаги из FPU в CPU. Это делается с помощью двух следующих инструкции. FSTSW записывает флаги FP в регистр AX и SAHF копирует 8-бит из регистра AH в регистр EFlags. Это длинный путь для флагов, перед тем как они смогут быть использованы в инструкции JNB. JNB означает JUMP NOT BELOW (переход если не меньше). В руководстве «Intel SW Developers Manual Vol 2» на странице 394 есть таблица, в которой описаны все инструкции переходов с объяснением используемых ими флагов. Здесь мы видим, что инструкция JNB делает переход, если установлен флаг переноса (CF=1) и флаг нуля (ZF=1). Попробуйте протрассировать код в просмотром в окне FPU и в окне CPU. Смотрите, как устанавливаются флаги FPU, затем их значения копируются в регистр CPU EFlags.

Если по инструкции JNB переход не выполняется, то выполнение продолжается на следующей за ней строке. Это часть конструкции IF-ELSE. Если же переход происходит, то выполнение будет продолжено по адресу на 8 далее. В этой точке начинается часть ELSE. Части IF и ELSE очень похожи. Как видно в Паскаль коде, A или B копируется в переменную RESULT, в зависимости от условия IF. Вместо копирования A или B напрямую на верхушку FP стека, который является местом для результата функции, в соответствии с соглашением о вызове, компилятор Delphi помещает его на стек как временное хранилище. Инструкция FLD DWORD PTR [EBP-$04] затем копирует результат в правильное место.

Добавим, что в конце блока IF требуется инструкция безусловного перехода, чтобы выполнение не распространилось на блок ELSE. Это делается вне зависимости, от того какой переход избран. Несколько слов о предсказании переходов. Предсказание переходов бывает статическое и динамическое. При первом выполнении перехода в CPU отсутствуют знания насчет вероятности, будет совершен переход или нет. В данной ситуации используется статическое предсказание, которое гласит, что прямой переход не будет выполнен, а обратный будет. В нашем примере прямой переход не предсказан при первом выполнении. Если бы мы имели знания насчет значений A и B, мы могли бы использовать это в конструкции IF-ELSE так, что бы IF часть была бы наиболее часто исполнимой, и статическое предсказание было бы оптимизировано. Безусловный переход не требует предсказания – это всегда имеет место быть ;-). Обратный переход часто используется в циклах, и большинство циклов исполняются более одного раза. Это объясняет, почему для статического предсказания выбран именно этот путь. При динамическом предсказании накапливаются знания насчет вероятности, того какой переход более вероятен, и сделать предсказание наиболее корректным.

Теперь пришло время преобразовать данную функцию в чистую ассемблерную.

Code:

function Min4(const A, B: Single) : Single;

asm

//push ebp

//mov ebp,esp

push ecx

//if A < B then

fld dword ptr [ebp+$0c]

fcomp dword ptr [ebp+$08]

fstsw ax

sahf

jnb @ElseBegin

//Result := A

mov eax,[ebp+$0c]

mov [ebp-$04],eax

jmp @ElseEnd

//else

//Result := B;

@ElseBegin :

mov eax,[ebp+$08]

mov [ebp-$04],eax

@ElseEnd :

fld dword ptr [ebp-$04]

pop ecx

//pop ebp

end;

Мы видим две новых вещи – это метки. Наш анализ функции делает более понятным, куда мы переходим при переходе. В действительности это хорошая вещь, использовать метки, это делает более понятной структуру кода. Вы можете открыть окно FPU и просто пройтись по коду, наблюдая, когда происходит переход или нет. Если вы устанавливать адрес перехода без меток, то используйте математику. Пример ниже.

Здесь у нас переход

00452465 7308 jnb +$08

Это следующая за ним строка

00452467 8B450C mov eax,[ebp+$0c]

А это строка на 8 байт далее ее

0045246F 8B4508 mov eax,[ebp+$08]

Возьмите адрес в строке после строки с переходом и добавьте к ней смещение до строки, в которую осуществляется переход. Математически это: 00452467 + 8 = 0045246F.

Почему мы должны добавлять смещение к адресу после команды перехода, а не к адресу с инструкцией?

Теперь приступаем к оптимизации.

Code:

function Min5(const A, B: Single) : Single;

asm

push ecx

//if A < B then

fld dword ptr [ebp+$0c]

fcomp dword ptr [ebp+$08]

fstsw ax

sahf

jnb @ElseBegin

//Result := A

mov eax,[ebp+$0c]

mov [ebp-$04],eax

jmp @ElseEnd

//else

//Result := B;

@ElseBegin :

mov eax,[ebp+$08]

mov [ebp-$04],eax

@ElseEnd :

fld dword ptr [ebp-$04]

pop ecx

end;

Это улучшенная версия функции. Изменены инструкции PUSH ECX, POP ECX для манипуляции регистром ESP напрямую и не нужно перемещать данные между ECX и стеком.

Code:

function Min6(const A, B: Single) : Single;

asm

//push ecx

sub esp, 4

//if A < B then

fld dword ptr [ebp+$0c]

fcomp dword ptr [ebp+$08]

fstsw ax

sahf

jnb @ElseBegin

//Result := A

mov eax,[ebp+$0c]

mov [ebp-$04],eax

jmp @ElseEnd

//else

//Result := B;

@ElseBegin :

mov eax,[ebp+$08]

mov [ebp-$04],eax

@ElseEnd :

fld dword ptr [ebp-$04]

//pop ecx

add esp, 4

end;

При анализе кода мы заметили, что флаги перемещаются длинным путем и требуется для выполнения два цикла. Как насчет инструкций сравнения для плавающей запятой, которые бы напрямую устанавливали регистр EFlags? Такая инструкция есть, это FCOMI, которая описана в архитектуре P6. Попробуем использовать ее, но выбросим эти старые CPU, более старые, чем Pro. Эти строки

fcomp dword ptr [ebp+$08]

fstsw ax

sahf

должно быть заменены на следующую

fcomip dword ptr [ebp+$08]

Инструкция FCOMI не воспринимает указатели на операнд в памяти. Поэтому необходимо загрузить данные до ее использования.

fld dword ptr [ebp+$0c]

fcomip st(0), st(1)

Поскольку мы загрузили данные, то мы и должны их удалить, с помощью FFREE инструкции. Хотелось бы иметь инструкцию fcomipp.

fld dword ptr [ebp+$0c]

fcomip st(0), st(1)

ffree st(0)

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

Code:

function Min7(const A, B: Single) : Single;

asm

sub esp, 4

//if A < B then

fld dword ptr [ebp+$08]

fld dword ptr [ebp+$0c]

fcomip st(0), st(1)

ffree st(0)

//fstsw ax

//sahf

jnb @ElseBegin

//Result := A

mov eax,[ebp+$0c]

mov [ebp-$04],eax

jmp @ElseEnd

//else

//Result := B;

@ElseBegin :

mov eax,[ebp+$08]

mov [ebp-$04],eax

@ElseEnd :

fld dword ptr [ebp-$04]

add esp, 4

end;

Теперь можно и подумать. Зачем нам копировать результат? Оба A и B уже на стеке для использования в сравнении с помощью FCOM и результат также должен остаться на стеке. Единственно, что нужно, так это удалить или A или B и оставить наименьшее из них на стеке.

Code:

function Min8(const A, B: Single) : Single;

asm

sub esp, 4

//if A < B then

fld dword ptr [ebp+$08]

fld dword ptr [ebp+$0c]

//fcomip st(0), st(1)

fcomi st(0), st(1)

//ffree st(0)

jnb @ElseBegin

//Result := A

//mov eax,[ebp+$0c]

//mov [ebp-$04],eax

ffree st(1)

jmp @ElseEnd

//else

//Result := B;

@ElseBegin :

//mov eax,[ebp+$08]

//mov [ebp-$04],eax

fxch

ffree st(1)

@ElseEnd :

//fld dword ptr [ebp-$04]

add esp, 4

end;

Инструкция FCOMIP заменяется инструкцией FCOMI, поскольку мы не хотим, удалять B со стека в данный момент. FFREE поскольку она удаляет A. Затем удалены все строки, которые копируют результат туда/обратно. В блоке IF A является результатом и B должно быть удалено. B находится в ST(1) и FFREE ST(1) сделает эту работу. В блоке ELSE мы должны удалить A и поставить B в ST(0). Обмениваем местами A и B, с помощью инструкции FXCH и затем удаляем A в ST(1) с помощью FFREE. FXCH ничего не стоит (занимает 0 циклов), поскольку вместо реальной пересылки данных используется переименование регистров.

Code:

function Min9(const A, B: Single) : Single;

asm

//sub esp, 4

//if A < B then

fld dword ptr [ebp+$08]

fld dword ptr [ebp+$0c]

fcomi st(0), st(1)

jnb @ElseBegin

//Result := A

ffree st(1)

jmp @ElseEnd

//else

//Result := B;

@ElseBegin :

fxch

ffree st(1)

@ElseEnd :

//add esp, 4

end;

Теперь фрейм стека более не нужен и мы удалим код его установки.

Code:

function Min10(const A, B: Single) : Single;

asm

//if A < B then

fld dword ptr [ebp+$08]

fld dword ptr [ebp+$0c]

fcomi st(0), st(1)

jnb @ElseBegin

//Result := A

ffree st(1)

jmp @ElseEnd

//else

//Result := B;

@ElseBegin :

fxch

ffree st(1)

@ElseEnd :

end;

Это достаточно прекрасная функция, но кто-то в группе новостей говорил об условных пересылках. FCMOVNB именно такая функция - floating point conditional move not below. Она пересылает данные из ST(1)-ST(7) в ST(0) если выполняется условие. Для проверки условия проверяются флаги Eflags. FCMOV приводится в архитектуре P6 наряду с FCOMI.

Code:

function Min11(const A, B: Single) : Single;

asm

fld dword ptr [ebp+$08]

fld dword ptr [ebp+$0c]

fcomi st(0), st(1)

fcmovnb st(0), st(1)

ffree st(1)

end;

Вместо всех переходов и пересылок мы копируем A на верхушку стека, где сейчас находится B, но только если A меньше B. Удаляем B и заканчиваем.

Это почти отличная функция, кроме того, что компилятор все равно создает пролог и эпилог функции, копируя и восстанавливая регистр EBP, даже если он не модифицируется внутри функции.

Урок 5

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

Code:

function ForLoop(Start, Stop : Integer) : Integer;

var

I : Integer;

begin

Result := 0;

for I := Start to Stop do

begin

Result := Result + I;

end;

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

Code:

function ForLoopNonOpt(Start, Stop : Integer) : Integer;

var

I : Integer;

begin

{

push ebp

mov ebp,esp

add esp,-$14

mov [ebp-$08],edx

mov [ebp-$04],eax

}

Result := 0;

{

xor eax,eax

mov [ebp-$0c],eax

}

for I := Start to Stop do

{

mov eax,[ebp-$04]

mov edx,[ebp-$08]

sub edx,eax

jl +$15

inc edx

mov [ebp-$14],edx

mov [ebp-$10],eax

}

begin

Result := Result + I;

{

mov eax,[ebp-$10]

add [ebp-$0c],eax

inc dword ptr [ebp-$10]

}

end;

{

dec dword ptr [ebp-$14]

jnz -$0e

mov eax,[ebp-$0c]

}

{

mov esp,ebp

pop ebp

ret

}

end;

Как мы видим, компилятор сгенерировал кучу кода, где или совсем нет оптимизации или ее мало. Как обычно первые три строки это установка стекового фрейма. В данном примере он на 20 байт больше (16 hex). Две следующие строки копируют переменные Start и Stop на стек. Start передается в EAX и Stop передается в EDX, в соответствии с соглашением об вызове. Следующие две строки создают значение 0 и копируют его на стек [EBP-$0C], это место для хранения переменной Result. Теперь мы готовы к выполнению тела цикла. Перед началом цикла необходимо убедиться, что цикл действительно должен выполняться. Если Stop больше чем Start, то это как раз тот случай. Start и Stop извлекаются из стека в регистры EAX и EDX. Мы вычисляем выражение Stop-Start и если результат отрицательный, то цикл не выполняется и управление передается в конец цикла инструкцией JL (jump low). В следующей строке увеличивается значение Stop, и оно копируется на стек [EBP-$14]. У нас нет имени для этой локальной переменной в данной точке. Данная особенность потребует дополнительных объяснений. Эта переменная (NoName) введена компилятором для оптимизации и это немного странно, поскольку мы отключили оптимизацию. Доступ до этой неименованной переменной есть в строке DEC DWORD PTR [EBP-$14]. Эта строка уменьшает ее значение на единицу, в конце каждой итерации и проверяется, что она не достигла нуля. Инструкция DEC устанавливает флаги, и инструкция JNZ делает переход на начало цикла, при условии, что NoName <> 0. Мы должны считать, что это используется как счетчик цикла и что она бежит от Start до Stop. Это действительно делается так, но это не используется для управления циклом. Преимущество в том, что это сохраняет инструкции при сравнении I со Stop. Но это также и увеличивает стоимость инструкции DEC NoName. На P4 latency/throughput инструкции CMP составляет 0.5/0.5 цикла, а для DEC оно 1/0.5. Поэтому это можно считать «де оптимизацией». Значения latency и throughput для P4 можно найти в «Intel Pentium 4 and Xeon Processor Optimization» руководстве от Intel.

Вернемся к строке MOV [EBP-$10], EAX. Она копирует переменную I на стек. Тело цикла состоит из одной строки Паскаля Result := Result + I. Она транслируется в три строки на ассемблере. Первые две строки загружают переменную I в регистр EAX и затем прибавляют ее к переменной Result на стеке [EBP-$0C]. Третья строка увеличивает переменную I. На этом мы заканчиваем объяснения кода цикла и у нас остались только две вещи. Переменная Result должна быть скопирована в регистр EAX, который используется для возврата результата из функции, в соответствии с соглашением о вызове. Последние три строки восстанавливают фрейм стека и возвращают управление обратно в программу.

В упражнении мы превратим это в ассемблерный код, так что бы это соответствовало Паскаль коду и нашему пониманию циклов. Мы начнем с преобразования в чистый ассемблерный код. Сделаем это путем закомментирования Паскаль кода и раскомментирования ассемблерного кода. Определим две метки LoopEnd и LoopStart, которые нам потребуются. Изменим два перехода так, что бы они указывали на метки.

Code:

function ForLoopBASM1(Start, Stop : Integer) : Integer;

asm

push ebp

mov ebp,esp

add esp,-$14

mov [ebp-$08],edx

mov [ebp-$04],eax

//Result := 0;

xor eax,eax

mov [ebp-$0c],eax

//for I := Start to Stop do

mov eax,[ebp-$04]

mov edx,[ebp-$08]

sub edx,eax

jl @LoopEnd

inc edx

mov [ebp-$14],edx

mov [ebp-$10],eax

//begin

@LoopStart :

//Result := Result + I;

mov eax,[ebp-$10]

add [ebp-$0c],eax

inc dword ptr [ebp-$10]

//end;

dec dword ptr [ebp-$14]

jnz @LoopStart

@LoopEnd :

mov eax,[ebp-$0c]

mov esp,ebp

pop ebp

//ret

end;

первое, что мы сделаем, так это удалим локальную переменную NoName.

Code:

function ForLoopBASM2(Start, Stop : Integer) : Integer;

asm

push ebp

push ebx //New

mov ebp,esp

add esp,-$14

mov [ebp-$08],edx

mov [ebp-$04],eax

//Result := 0;

xor eax,eax

mov [ebp-$0c],eax

//for I := Start to Stop do

mov eax,[ebp-$04]

mov edx,[ebp-$08]

sub edx,eax

jl @LoopEnd

//inc edx //NoName intialize

//mov [ebp-$14],edx //NoName intialize

mov [ebp-$10],eax

//begin

@LoopStart :

//Result := Result + I;

mov eax,[ebp-$10]

add [ebp-$0c],eax

inc dword ptr [ebp-$10]

//end;

//dec dword ptr [ebp-$14] //NoName decrement

mov ebx, [ebp-$10] //New

mov ecx, [ebp-$08] //New

cmp ebx, ecx //New

//jnz @LoopStart

jbe @LoopStart //New

@LoopEnd :

mov eax,[ebp-$0c]

mov esp,ebp

pop ebx //New

pop ebp

//ret

end;

Строка, помеченная как "New" введена, для создания переменной цикла I. Строка MOV EBX, [EBP-$10] копирует переменную I в регистр EBX. Следующая строка копирует переменную Stop в регистр ECX. Затем в строке CMP EBX, ECX они сравниваются, и инструкцией JBE @LOOPSTART управление передается в начало цикла, если I меньше или равно Stop. Поскольку мы используем регистр EBX и он не разрешен для свободного использования, поэтому мы его сохраняем его в стеке.

Мы решили проверять окончания цикла в начале цикла. Данный тест разделен компилятором на две части. Перед входом в цикл проверяется, что цикл может выполниться как минимум один раз и реальное окончание цикла проверяется в конце. Такая техника оптимизации называется инверсия цикла. Теперь мы сменим цикл так, что бы такую оптимизацию. Потом мы увидим преимущества от этой оптимизации.

Code:

function ForLoopBASM4(Start, Stop : Integer) : Integer;

asm

push ebp

push ebx

mov ebp,esp

add esp,-$14

mov [ebp-$08],edx

mov [ebp-$04],eax

//Result := 0;

xor eax,eax

mov [ebp-$0c],eax

//for I := Start to Stop do

mov eax,[ebp-$04]

mov edx,[ebp-$08]

//sub edx,eax

//jl @LoopEnd

mov [ebp-$10],eax

//begin

@LoopStart :

mov ebx, [ebp-$10]

mov ecx, [ebp-$08]

cmp ebx, ecx

ja @LoopEnd

//Result := Result + I;

mov eax,[ebp-$10]

add [ebp-$0c],eax

inc dword ptr [ebp-$10]

//end;

//mov ebx, [ebp-$10]

//mov ecx, [ebp-$08]

//cmp ebx, ecx

//jbe @LoopStart

jmp @LoopStart

@LoopEnd :

mov eax,[ebp-$0c]

mov esp,ebp

pop ebx

pop ebp

end;

Проверка на окончания цикла была перемещена в начало и тест был инвертирован. На месте старой проверки теперь находится безусловный переход. Этот переход единственное, что сделано по отношению к инверсной оптимизации. В не оптимизированном цикле было два перехода, оптимизированным один. Проверка вверху, то что проверяется всегда. Start был на Stop и теперь лишнее и поэтому удалено. Перед проведением измерений по эффекту от двух оптимизаций, хорошей идеей будет оптимизировать часть или все, что возможно, стек в регистры, регистры в стек. Данный процесс называется – размещение в регистрах и это одна из самых важных оптимизаций на всех архитектурах, но это особенно важно для архитектуры Intel, поскольку в ней малое количество доступных регистров. Если нет места для всех переменных в регистрах, то важно определить какие переменные поместить в регистры. Инструкции MOV в теле цикла наиболее важные кандидаты на это. Они выполняются большое количество раз. Инструкции за пределами цикла выполняются только раз. Переменные внутри цикла первыми должны быть размещены в регистрах. Это переменные I, Stop и Result. Теперь рассмотрим использование регистров для временных переменных. Если переменная всегда копируется в тот же самый временный регистр, то ее желательно разместить в этом регистре. Переменная Stop в регистре EDX при входе в функцию и также используется как временный регистр, во всех строках, кроме двух строк. Здесь есть две строки в цикле, которые мы добавили, изменим их

mov ecx, [ebp-$08]

cmp ebx, ecx

на

mov edx, [ebp-$08]

cmp ebx, edx

Регистр EAX используется для Start вверху функции и как Result в остальной части функции. Если нет перекрытия по использованию, то мы можем использовать EAX для Result, как только Start прекратит его использования. После того, как Start назначен переменной I (MOV [EBP-$10], EAX), он больше нигде не используется и регистр EAX свободен для использования для Result, кроме тех строк, где EAX используется как временное хранилище для I.

mov eax,[ebp-$10]

add [ebp-$0c],eax

inc dword ptr [ebp-$10]

после того, как ECX прекращает использоваться, мы можем его использовать как временное хранилище для I, вместо EAX.

mov ecx,[ebp-$10]

add [ebp-$0c],ecx

inc dword ptr [ebp-$10]

Подведем итог по первой части оптимизации по использованию регистров: Result в EAX, I в ECX и Stop в EDX.

В начале заменим все строки со Stop. [EBP-$08] на использование EDX.

Code:

function ForLoopBASM6(Start, Stop : Integer) : Integer;

asm

push ebp

push ebx

mov ebp,esp

add esp,-$14

//mov [ebp-$08],edx

mov edx,edx

mov [ebp-$04],eax

//Result := 0;

xor eax,eax

mov [ebp-$0c],eax

//for I := Start to Stop do

mov eax,[ebp-$04]

//mov edx,[ebp-$08]

mov edx,edx

mov [ebp-$10],eax

//begin

@LoopStart :

mov ebx, [ebp-$10]

//mov edx, [ebp-$08]

mov edx, edx

cmp ebx, edx

ja @LoopEnd

//Result := Result + I;

mov ecx,[ebp-$10]

add [ebp-$0c],ecx

inc dword ptr [ebp-$10]

//end;

jmp @LoopStart

@LoopEnd :

mov eax,[ebp-$0c]

mov esp,ebp

pop ebx

pop ebp

end;

Затем распределим ECX для I, заменив [EBP-$10] на ECX.

Code:

function ForLoopBASM7(Start, Stop : Integer) : Integer;

asm

push ebp

push ebx

mov ebp,esp

add esp,-$14

mov edx,edx

mov [ebp-$04],eax

//Result := 0;

xor eax,eax

mov [ebp-$0c],eax

//for I := Start to Stop do

mov eax,[ebp-$04]

mov edx,edx

//mov [ebp-$10],eax

mov ecx,eax

//begin

@LoopStart :

//mov ebx, [ebp-$10]

mov ebx, ecx

mov edx, edx

cmp ebx, edx

ja @LoopEnd

//Result := Result + I;

//mov ecx,[ebp-$10]

mov ecx,ecx

add [ebp-$0c],ecx

//inc dword ptr [ebp-$10]

inc ecx

//end;

jmp @LoopStart

@LoopEnd :

mov eax,[ebp-$0c]

mov esp,ebp

pop ebx

pop ebp

end;

И на конец используем EAX для Result. Поскольку EAX также используется вверху функции для Start и как временный регистр для инициализации Result нулем, то мы должны добавить несколько строк для копирования Result в EAX после как EAX более нигде не будет использоваться для других целей.

Code:

function ForLoopBASM8(Start, Stop : Integer) : Integer;

asm

push ebp

push ebx

mov ebp,esp

add esp,-$14

mov edx,edx

mov [ebp-$04],eax

//Result := 0;

xor eax,eax

mov [ebp-$0c],eax

//for I := Start to Stop do

mov eax,[ebp-$04]

mov edx,edx

mov ecx,eax

mov eax, [ebp-$0c] //New

//begin

@LoopStart :

mov ebx, ecx

mov edx, edx

cmp ebx, edx

ja @LoopEnd

//Result := Result + I;

mov ecx,ecx

//add [ebp-$0c],ecx

add eax,ecx

inc ecx

//end;

jmp @LoopStart

@LoopEnd :

//mov eax,[ebp-$0c]

mov eax,eax

mov esp,ebp

pop ebx

pop ebp

end;

поскольку мы особо не обращали внимания при конвертировании на другие вещи, то у нас образовалось много строк типа MOV EAX, EAX. Сразу видно они излишни ;-). Просто удалим их.

Code:

function ForLoopBASM9(Start, Stop : Integer) : Integer;

asm

push ebp

push ebx

mov ebp,esp

add esp,-$14

//mov edx,edx

mov [ebp-$04],eax

//Result := 0;

xor eax,eax

mov [ebp-$0c],eax

//for I := Start to Stop do

mov eax,[ebp-$04]

//mov edx,edx

mov ecx,eax

mov eax, [ebp-$0c]

//begin

@LoopStart :

mov ebx, ecx

//mov edx, edx

cmp ebx, edx

ja @LoopEnd

//Result := Result + I;

//mov ecx,ecx

add eax,ecx

inc ecx

//end;

jmp @LoopStart

@LoopEnd :

//mov eax,eax

mov esp,ebp

pop ebx

pop ebp

end;

При оптимизации ассемблерного кода есть две линии поведения, которым мы можем следовать. Мы можем думать как человек, пытаясь проявлять сообразительность, используя информацию из кода. Мы поступили так, когда распределяли регистры. Другой путь – это пытаться использовать системный подход, так как поступает компилятор/оптимизатор. Это путь разработки алгоритмов. Данный подход позже даст многое для оптимизации, так мы поступали много раз выше. Удаление лишних строк кода, MOV EAX, EAX, был примером удаления мертвого кода, что является базисом для любых оптимизаторов.

Вверху функции мы еще имеем некоторые ссылки на стек. Для их удаления мы должны разместить эти переменные также в регистрах. В данное время мы выберем регистры EDI и ESI, поскольку они ни где не используются. Используем ESI для [EBP-$04] и EDI для [EBP-$0C]. Поскольку регистры ESI и EDI должны быть сохранены, мы поместим их в стек и потом восстановим.

Code:

function ForLoopBASM10(Start, Stop : Integer) : Integer;

asm

push ebp

push ebx

push esi

push edi

mov ebp,esp

add esp,-$14

//mov [ebp-$04],eax

mov esi,eax

//Result := 0;

xor eax,eax

//mov [ebp-$0c],eax

mov edi,eax

//for I := Start to Stop do

//mov eax,[ebp-$04]

mov eax,esi

mov ecx,eax

//mov eax, [ebp-$0c]

mov eax, edi

//begin

@LoopStart :

mov ebx, ecx

cmp ebx, edx

ja @LoopEnd

//Result := Result + I;

add eax,ecx

inc ecx

//end;

jmp @LoopStart

@LoopEnd :

mov esp,ebp

pop edi

pop esi

pop ebx

pop ebp

end;

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

mov eax,esi

mov ecx,eax

могут быть заменены одной.

mov ecx, esi

Это пример упрощения копирования с дальнейшим удалением мертвого кода. Любые другие строки не используют значения в EAX далее следующей строки, которая копирует обратно в ECX. Фактически это сразу переписывается строкой MOV EAX, EDI. Поэтому мы можем заменить вторую строку, на строку MOV ECX, ESI и удалить первую, которая становится мертвым кодом.

Code:

function ForLoopBASM11(Start, Stop : Integer) : Integer;

asm

//push ebp

push ebx

push esi

push edi

//mov ebp,esp

//add esp,-$14

mov esi,eax

//Result := 0;

xor eax,eax

mov edi,eax

//for I := Start to Stop do

//mov eax,esi

//mov ecx,eax

mov ecx, esi

mov eax, edi

//begin

@LoopStart :

//mov ebx, ecx

//cmp ebx, edx

cmp ecx, edx

ja @LoopEnd

//Result := Result + I;

add eax,ecx

inc ecx

//end;

jmp @LoopStart

@LoopEnd :

//mov esp,ebp

pop edi

pop esi

pop ebx

//pop ebp

end;

Строка XOR EAX, EAX присваивает начальное значение переменной Result в 0 и может быть перемещена на несколько строк ниже в место, где EAX будет использован в первый раз. Зато она никогда не должна быть помещена в тело цикла, что изменит логику функции, но может быть перед loopStart. Это убирает необходимость в копировании EAX в EDI и обратно в EAX в строке перед строкой комментария //FOR I := START TO STOP DO.

Code:

function ForLoopBASM12(Start, Stop : Integer) : Integer;

asm

push ebx

push esi

push edi

mov esi,eax

//for I := Start to Stop do

mov ecx, esi

//Result := 0;

xor eax,eax

//mov edi,eax

//mov eax, edi

//begin

@LoopStart :

cmp ecx, edx

ja @LoopEnd

//Result := Result + I;

add eax,ecx

inc ecx

//end;

jmp @LoopStart

@LoopEnd :

pop edi

pop esi

pop ebx

end;

После всего этого мы видим две строки MOV, которые копируют EAX в ECX через ESI. Это оставляет копию EAX в ESI, которая не используется. Поэтому одна пересылка EAX directly into ECX может заменить эти две строки. Это также уменьшение копирования и удаление мертвого кода.

Code:

function ForLoopBASM13(Start, Stop : Integer) : Integer;

asm

push ebx

//push esi

push edi

//mov esi,eax

//for I := Start to Stop do

//mov ecx, esi

mov ecx, eax

//Result := 0;

xor eax,eax

//begin

@LoopStart :

cmp ecx, edx

ja @LoopEnd

//Result := Result + I;

add eax,ecx

inc ecx

//end;

jmp @LoopStart

@LoopEnd :

pop edi

//pop esi

pop ebx

end;

После удаления использования ESI, теперь нет необходимости в его сохранении и восстановлении.

Code:

function ForLoopBASM14(Start, Stop : Integer) : Integer;

asm

//push ebx

//push edi

//for I := Start to Stop do

mov ecx, eax

//Result := 0;

xor eax,eax

//begin

@LoopStart :

cmp ecx, edx

ja @LoopEnd

//Result := Result + I;

add eax,ecx

inc ecx

//end;

jmp @LoopStart

@LoopEnd :

//pop edi

//pop ebx

end;

Также, хоть и немного поздно мы видим, что EBX и EDI нигде не используются. После их удаления и удаления комментариев, в результате получилась следующая красивая функция.

Code:

function ForLoopBASM15(Start, Stop : Integer) : Integer;

asm

mov ecx, eax

//Result := 0;

xor eax,eax

//for I := Start to Stop do

@LoopStart :

cmp ecx, edx

ja @LoopEnd

//Result := Result + I;

add eax,ecx

inc ecx

jmp @LoopStart

@LoopEnd :

end;

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

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

Code:

function ForLoopOpt(Start, Stop : Integer) : Integer;

var

I : Integer;

begin

{

}

Result := 0;

{

xor ecx,ecx

}

for I := Start to Stop do

{

sub edx,eax

jl +$08

inc edx

xchg eax,edx

}

begin

Result := Result + I;

{

add ecx,edx

inc edx

}

end;

{

dec eax

jnz -$06

}

{

mov eax,ecx

}

end;

В данном случае Delphi действительно сделало прекрасную работу. Только две строки режут наши глаза. XCHG EAX, EDX простой обмен значениями в EAX и EDX, и MOV EAX, ECX копирует результат в EAX. Обе строки находятся за пределами цикла и не отнимают много времени. Теперь мы имеем две функции – одна без оптимизации цикла и одна с двумя. Для полного комплекта нам нужно еще две функции, одна с обратным циклом и одна с переменной NoName, только с оптимизацией. В начале урока мы видели, как удалить две оптимизации и это я сделал в двух оставшихся функциях. В Delphi оптимизированной выше функции, я оптимизировал инструкцию XCHG для обмена значений двух регистров.

Поскольку мы хотим увидеть максимальный эффект только от оптимизации циклов, я удалил тело цикла Result := Result + I;

Здесь четыре последние функции.

Code:

function ForLoopNoLoopInverNoNoName(Start, Stop : Integer) : Integer;

asm

mov ecx, eax

//Result := 0;

xor eax,eax

//for I := Start to Stop do

@LoopStart :

cmp ecx, edx

ja @LoopEnd

inc ecx

jmp @LoopStart

@LoopEnd :

end;

Цикл состоит их 4 инструкции. 1 CMP, 1 JA, 1 INC и 1 JMP. Latency и throughput для этих двух инструкции на P4 следующие: CMP 0.5/0.5, JA X/0.5, INC 0.5/1 и JMP X/0.5. X означает, что "latency is not applicable to this instruction" «Латентность не применима к данной инструкции». Дополнительная латентность, которую мы имеет: 0.5 + X + 0.5 + X = ? циклов.

Code:

function ForLoopLoopInverNoNoName(Start, Stop : Integer) : Integer;

asm

mov ecx, eax

//Result := 0;

xor eax,eax

//for I := Start to Stop do

cmp ecx, edx

ja @LoopEnd

@LoopStart :

inc ecx

cmp ecx, edx

jbe @LoopStart

@LoopEnd :

end;

Данный цикл состоит из 3 инструкций, также с неизвестной суммой латентности.

Code:

function ForLoopNoLoopInverNoName(Start, Stop : Integer) : Integer;

asm

//Result := 0;

xor ecx,ecx

//for I := Start to Stop do

sub edx,eax

cmp edx, 0

@LoopStart :

jz @LoopEnd

inc eax

dec edx

jmp @LoopStart

@LoopEnd :

mov eax,ecx

end;

Данный цикл состоит из 4 инструкций, также с неизвестной суммой латентности. Заметим, что две инструкции INC/DEC имеют возможность выполняться параллельно. Поскольку за DEC NoName инструкцией не следует условный переход JMP, это выглядит как преимущество, в отсутствии необходимости использования инструкций CMP или TEST для установки флагов, но инструкция JMP не изменяет значения флагов и они доступны, когда мы попадаем на инструкцию JZ в начале цикла. Только в первой итерации инструкция CMP EDX,0 необходима для этого.

Code:

function ForLoopLoopInverNoName(Start, Stop : Integer) : Integer;

asm

//Result := 0;

xor ecx,ecx

//for I := Start to Stop do

sub edx,eax

jl @LoopEnd

inc edx

@LoopStart :

inc eax

dec edx

jnz @LoopStart

@LoopEnd :

mov eax,ecx

end;

Данный цикл состоит из 3 инструкций, также с неизвестной суммой латентности. Здесь также есть независимая пара INC/DEC.

Это очень простая измерительная программа (benchmark), которую я использую для проверки производительности этих четырех функций.

Code:

var

Starttime, Endtime, Runtime : TDateTime;

I, LoopResult : Integer;

RunTimeSec, NoOfLoopsPerSec, NoOfLoops, ClockCount, LoopEnd2Float,

LoopEndFloat, LoopStartFloat : Double;

begin

Starttime := Time;

for I := 1 to LOOPEND2 do

begin

LoopResult := ForLoopNoLoopInverNoName(LOOPSTART, LOOPEND);

end;

Endtime := Time;

Runtime := Endtime - Starttime;

CEdit.Text := IntToStr(LoopResult);

RuntimeEdit4.Text := TimeToStr(Runtime);

RunTimeSec := RunTime*24*60*60;

LoopEnd2Float := LOOPEND2;

LoopEndFloat := LOOPEND;

LoopStartFloat := LOOPSTART;

NoOfLoops := LoopEnd2Float * (LoopEndFloat - LoopStartFloat);

NoOfLoopsPerSec := NoOfLoops / RunTimeSec;

ClockCount := CLOCK / NoOfLoopsPerSec;

ClockCountEdit4.Text := FloatToStrf(ClockCount, ffFixed, 9, 1);

end;

результаты на P4 1920 следующие:

No Loop Inversion and No NoName variable 00:00:55 (2.7 Clock cycles)

Loop Inversion but No NoName variable 00:00:39 (1.9 Clock cycles)

No Loop Inversion but NoName variable 00:01:02 (3.0 Clock cycles)

Loop Inversion + NoName 00:00:41 (2.0 Clock cycles)

результаты на P3 1400 следующие:

No Loop Inversion and No NoName variable 00:01:26 (3.0 Clock cycles)

Loop Inversion but No NoName variable 00:01:26 (3.0 Clock cycles)

No Loop Inversion but NoName variable 00:01:55 (4.0 Clock cycles)

Loop Inversion + NoName 00:01:26 (3.0 Clock cycles)

Конечно, clock count числа должны быть целыми. На P4 возможны пол цикла, в связи с double-clocked ALU. Наши измерения не так хороши, как хотелось бы, но для сравнения производительности циклов они достаточны.

Заключение для P4. Используйте только No Loop Inversion или loop inversion with NoName variable оптимизацией.

Заключение для P3. Не используйте No Loop Inversion but NoName variable оптимизацию.

Заключение для обеих платформ. Используйте обе оптимизации как делает Delphi.

Также обратите внимание насколько эффективен P4 на этом коде.

Новые статьи

BASM - Уроки для начинающих. Часть 2.

Случайные статьи

BASM - Уроки для начинающих. Часть 2.

BASM - Уроки для начинающих.