Borland Assembler (BASM) уроки для начинающих
Delphi , Синтаксис , Assembler

взято здесь

Денис Христенсен
Из news://forums.borland.com
borland.public.Delphi.languages.basm
© Dennis Chistensen, 2003
© Anatoly Podgoretsky, 2003, Russian translations
Печатается с сокращениями​

Введение

Серия статей, названная “BASM for beginners” (built-in assembler уроки для начинающих) в данный момент состоит из 7 статей, статьи 8 и 9 находятся в стадии подготовки. Общее для этих статей и для тех, что в процессе подготовки то, что они объясняют некоторые вопросы использования BASM на примерах функций. Большинство из этих функций сначала реализуются на Паскале, затем сгенерированный компилятором ассемблерный код, копируется из окна CPU view в Delphi, затем анализируется и оптимизируется. Иногда оптимизация включает в себя и использование инструкций MMX, SSE или SSE2.
В самом начале рассматривается код сделанный компилятором, в котором использует только наиболее используемые инструкции из огромного набора инструкций 32-битной архитектуры Intel. Просматривая, сгенерированный компилятором код, мы получаем представление и об эффективности компилятора, в общем, и о компиляторе Delphi в целом.
Когда применимо, то приводятся обобщения по оптимизации ассемблерного кода. Эта общая оптимизация применима к компиляторам и большинство компиляторов, включая Delphi, ее имеют. Когда ни будь, в будущем будет разработан инструмент по автоматической оптимизации ассемблерного кода.
Знание об используемом процессоре очень необходимы при оптимизации кода и поэтому также разъясняются множество подробностей о CPU, таких как например конвейеры.
Насколько Я знаю, имеется очень мало литературы, в которой объясняются все эти особенности, на уровне, который был бы понятен начинающим. Я надеюсь, что эта серия статей сможет помочь им в этом.

С уважением,
Денис Христенсен
Dennis Kjaer Christensen.​

Содержание

1. Урок 1 (целочисленный код)
2. Урок 2 (код с плавающей запятой)
3. Урок 3 (MMX, SSE2 и 64-битная математика)
4. Урок 4 (ветвления)
5. Урок 5 (циклы)
6. Урок 6 (функция CharPos)
7. Урок 7

 

Урок 1

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

Код (Pascal):

1. function MulInt2(I : Integer) : Integer;
2. begin
3.           Result := I * 2;
4. end;

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

Код (ASM):

1. ;Result := I * 2;
2.         add eax,eax
3.         ret

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

Код (Pascal):

1. function MulInt2_BASM2(I : Integer) : Integer;
2. asm
3. //Result := I * 2;
4. add eax,eax
5. //ret
6. end;

Возврат из функции обеспечивается встроенным ассемблером.
Теперь посмотрит на код вызова функции.
Вот программа на Паскале:

Код (Pascal):

1. procedure TForm1.Button1Click(Sender: TObject);
2. var
3. I, J : Integer;
4.  
5. begin
6. I := StrToInt(IEdit.Text);
7. J := MulInt2_BASM2(I);
8. JEdit.Text := IntToStr(J);
9. end;

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

Код (Pascal):

1. J := MulInt2_BASM2(I);

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

Код (ASM):

1. call StrToInt
2. call MulInt2_BASM2
3. mov esi,eax

После вызова StrToInt из строки выше вызова нашей функции, значение I находится в регистре EAX. (StrToInt также следует соглашению о передаче параметров через регистры). Далее вызывается функция MulInt2_BASM2, которая возвращает результат своей работы через регистр EAX, значение из которого в следующей строке копируется в регистр ESI.
Замечание об оптимизации: Умножение на два может быть сделано несколькими путями. С помощью инструкции MUL/IMUL, через сложение или сдвигом влево на один разряд. Инструкция MUL умножает значение в регистре EAX на содержимое другого регистра или ячейки памяти, результат помещается в регистровую пару EDX:EAX.
Соглашение об использовании регистров, которые должны быть сохранены во время работы функции, и какие можно свободно изменять описано в справочной системе Дельфи.
"Выражения asm должны сохранять регистры EDI, ESI, ESP, EBP и EBX, но могут свободно изменять регистры EAX, ECX и EDX."

Код (Pascal):

1. function MulInt2_BASM3(I : Integer) : Integer;
2. asm
3. //Result := I * 2;
4. mov ecx, 2
5. mul ecx
6. end;

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

Код (Pascal):

1. function MulInt2_BASM4(I : Integer) : Integer;
2. asm
3. //Result := I * 2;
4. shl eax,1
5. 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. Функция выглядит так.

Код (Pascal):

1. function SecondOrderPolynomial1(X : Double) : Double;
2. const
3. A : Double = 1;
4. B : Double = 2;
5. C : Double = 3;
6. begin
7. Result := A*X*X + B*X + C;
8. end;

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

Код (Pascal):

1. function SecondOrderPolynomial2(X : Double) : Double;
2. const
3. A : Double = 1;
4. B : Double = 2;
5. C : Double = 3;
6. begin
7. {
8.               push  ebp
9.               mov   ebp,esp
10.              add   esp,-8
11. }
12. Result := A*X*X + B*X + C;
13. {
14.             fld   qword ptr [A]
15.            fmul  qword ptr [ebp+8]
16.            fmul  qword ptr [ebp+8]
17.            fld   qword ptr [В]
18.            fmul  qword ptr [ebp+8]
19.            faddp st(1)
20.            fadd  qword ptr [C]
21.            fstp  qword ptr [ebp-8]
22.            wait
23.            fld   qword ptr [ebp-8]
24. }
25. {
26.            pop   ecx
27.            pop   ecx
28.            pop   ebp
29. }
30. end;

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

Код (ASM):

1. ;begin
2.            push  ebp
3.            mov   ebp,esp
4.            add   esp,-8

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

Следующий фрагмент программы компилируется в 9 ассемблерных строк.

Код (Pascal):

1. Result := A*X*X + B*X + C;
2. {
3.       fld   qword ptr [A]
4.      fmul  qword ptr [ebp+8]
5.      fmul  qword ptr [ebp+8]
6.      fld   qword ptr [B]
7.      fmul  qword ptr [ebp+8]
8.      faddp st(1)
9.      fadd  qword ptr [C]
10.      fstp  qword ptr [ebp-8]
11.      wait
12.      fld   qword ptr [ebp-8]
13. }

В первой строке команда FLD QWORD PTR [A] загружает константу A в регистр FPU. В строке FMUL QWORD PTR [EBP+8] умножается A на X. Что означает "QWORD PTR [EBP+8]" ? QWORD PTR - "указатель на двойное слово размером double (64 бита). Значение указателя между квадратными скобками [EBP+8]. Регистр EBP это указатель базы, 8 это – просто 8 байт. Поскольку стек при увеличении движется вниз, то это смещение на 8 байт вверх относительно указателя базы в текущем фрейме. Здесь находится переданный параметр X, помещенный сюда вызывающей функцией. При соглашение о регистром вызове, значение не помещается в 32-разрядный регистр, но оно помещается в регистр с плавающей запятой. Borland передает параметры с плавающей запятой двойной точности через стек, но передача через регистры с плавающей запятой, была бы более эффективной. Следующие три строки не требуют специального пояснения, но инструкция FADDP ST(1), нуждается в объяснении. Все инструкции с плавающей запятой начинаются с префикса f. add это сложение. ST(1) это название второго регистра FPU с номером 1, первый регистр это ST(0)! Регистры FPU скомпонованы в стек и инструкции по умолчанию работаю с верхушкой стека FPU, которая равна 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). Результат и так уже там, поэтому две следующие строки кода излишни.

Код (ASM):

1. fstp  qword ptr [ebp-8]
2. fld   qword ptr [ebp-8]

Они просто копируют результат на стек и обратно. Такая затрата времени и энергии . Инструкция WAIT обеспечивает обработку возможных исключений при выполнении операций с плавающей запятой.
Осталось объяснить еще три строки кода.

Код (Pascal):

1. {
2. pop   ecx
3. pop   ecx
4. pop   ebp
5. }
6. end;

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

Код (ASM):

1. add esp, 4
2. pop ebp

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

Код (Text):

1. 00451E40 DD05803C4500     fld qword ptr [В]

00451E40 это адрес инструкции в exe файле. DD05803C4500 это машинный код строки FLD QWORD PTR [В], которая более понятна для человеческого разума. Код команды для FLD равен D9, DD, DB или D9C0, в зависимости от типа данных. DD это код для FLD DOUBLE. Остается еще 05803C4500. 05 это код операции, а 803C4500 это 32-битный адрес константы A.
Попробуем теперь преобразовать эту функцию в ассемблерный код.

Код (Pascal):

1. function SecondOrderPolynomial3(X : Double) : Double;
2. const
3. A : Double = 1;
4. B : Double = 2;
5. C : Double = 3;
6.  
7. asm
8. push  ebp
9. mov   ebp,esp
10. add   esp,-8
11. //Result := A*X*X + B*X + C;
12. fld   qword ptr [A]
13. fmul  qword ptr [ebp+8]
14. fmul  qword ptr [ebp+8]
15. fld   qword ptr [B]
16. fmul  qword ptr [ebp+8]
17. faddp //st(1)
18. fadd  qword ptr [C]
19. fstp  qword ptr [ebp-8]
20. wait
21. fld   qword ptr [ebp-8]
22. pop   ecx
23. pop   ecx
24. pop   ebp
25. end;

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

Код (ASM):

1. push dword ptr [ebp-0Ch]
2. push dword ptr [ebp-10h]
3. call SecondOrderPolynomial1

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

 

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

Код (Pascal):

1. function SecondOrderPolynomial4(X : Double) : Double;
2. const
3. A : Double = 1;
4. B : Double = 2;
5. C : Double = 3;
6.  
7. asm
8. //push  ebp
9. //mov   ebp,esp
10. add   esp,-$08
11. //Result := A*X*X + B*X + C;
12. fld   qword ptr [A]
13. fmul  qword ptr [ebp+8]
14. fmul  qword ptr [ebp+8]
15. fld   qword ptr [B]
16. fmul  qword ptr [ebp+8]
17. faddp //st(1)
18. fadd  qword ptr [C]
19. //fstp  qword ptr [ebp-8]
20. wait
21. //fld   qword ptr [ebp-8]
22. pop   ecx
23. pop   ecx
24. pop   ebp
25. end;

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

Код (Pascal):

1. function SecondOrderPolynomial5(X : Double) : Double;
2. const
3. A : Double = 1;
4. B : Double = 2;
5. C : Double = 3;
6.  
7. asm
8. //push  ebp
9. //mov   ebp,esp
10. //add   esp,-8
11. //Result := A*X*X + B*X + C;
12. fld   qword ptr [A]
13. fmul  qword ptr [ebp+8]
14. fmul  qword ptr [ebp+8]
15. fld   qword ptr [B]
16. fmul  qword ptr [ebp+8]
17. faddp //st(1)
18. fadd  qword ptr [C]
19. wait
20. //pop   ecx
21. //pop   ecx
22. //pop   ebp
23. end;

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

Код (Pascal):

1. function SecondOrderPolynomial6(X : Double) : Double;
2. const
3. A : Double = 1;
4. B : Double = 2;
5. C : Double = 3;
6.  
7. asm
8. //Result := A*X*X + B*X + C;
9. fld   qword ptr [A]
10. fmul  qword ptr [ebp+8]
11. fmul  qword ptr [ebp+8]
12. fld   qword ptr [B]
13. fmul  qword ptr [ebp+8]
14. faddp
15. fadd  qword ptr [C]
16. wait
17. end;

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

Код (Pascal):

1. function SecondOrderPolynomial7(X : Double) : Double;
2. const
3. A : Double = 1;
4. B : Double = 2;
5. C : Double = 3;
6.  
7. asm
8. //Result := A*X*X + B*X + C;
9. fld   qword ptr [ebp+8]
10. fld   qword ptr [A]
11. fmul  st(0), st(1)
12. fmul  st(0), st(1)
13. fld   qword ptr [B]
14. fmul  st(0), st(2)
15. ffree st(2)
16. faddp
17. fadd  qword ptr [C]
18. wait
19. end;

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

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

Код (Pascal):

1. function SecondOrderPolynomial8(X : Double) : Double;
2. const
3. //A : Double = 1;
4. B : Double = 2;
5. C : Double = 3;
6.  
7. asm
8. //Result := A*X*X + B*X + C;
9. fld   qword ptr [ebp+8]
10. //fld   qword ptr [A]
11. fld1
12. fmul  st(0), st(1)
13. fmul  st(0), st(1)
14. fld   qword ptr [B]
15. fmul  st(0), st(2)
16. ffree st(2)
17. faddp
18. fadd  qword ptr [C]
19. wait
20. end;

 

Урок 3

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

Код (Pascal):

1. function AddInt64_1(A, B : Int64) : Int64;
2. begin
3. Result := A + B;
4. end;

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

Код (Pascal):

1. function AddInt64_2(A, B : Int64) : Int64;
2. begin
3. {
4. push ebp
5. mov ebp,esp
6. add esp,-8
7. }
8. Result := A + B;
9. {
10. mov eax,[ebp+10h]
11. mov edx,[ebp+14h]
12. add eax,[ebp+8]
13. adc edx,[ebp+0Ch]
14. mov [ebp-8],eax
15. mov [ebp-4],edx
16. mov eax,[ebp-8]
17. mov edx,[ebp-4]
18. }
19. {
20. pop ecx
21. pop ecx
22. pop ebp
23. //ret
24. }
25. end;

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

Код (Pascal):

1. Result := A + B;
2. {
3. mov eax,[ebp+10h]
4. mov edx,[ebp+14h]
5. add eax,[ebp+8]
6. adc edx,[ebp+0Ch]
7. mov [ebp-8],eax
8. mov [ebp-4],edx
9. mov eax,[ebp-8]
10. mov edx,[ebp-4]
11. }

Анализ показывает, что они работают парами, осуществляя 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 строки абсолютно излишни. Они могут быть удалены и также не требуется и фрейм стека. Это так просто для оптимизатора

Код (Pascal):

1. function AddInt64_6(A, B : Int64) : Int64;
2. asm
3. mov eax,[ebp+10h]
4. mov edx,[ebp+14h]
5. add eax,[ebp+8]
6. adc edx,[ebp+0Ch]
7. end;

Теперь это прекрасная маленькая функция. Компилятор сгенерировал код из 16 строк, а мы его уменьшили до 4. Сегодня Delphi реально слепая.
Теперь подумаем так: Если бы мы имели 64-битные регистры, то сложение могло бы быть выполнено с помощью двух строк кода. Но MMX регистры уже 64-битные и может быть, мы получим преимущества при их использовании. В руководстве Intel SW Developers Manual для инструкций не указана принадлежность к IA32, MMX, SSE или SSE2. Было бы превосходно иметь эту информацию, но мы должны искать ее где-то в другом месте. Я обычно использую три маленькие программы от Intel. Они называются «computer based tutorials on MMX, SSE & SSE2». Я не знаю где их можно найти на Intel'овском Веб сайте, но Вы можете написать мне, если они очень вам нужны. Они простые и удобные – очень иллюстративные. В них я нашел, что инструкция MOV для 64-битных операндов из памяти в MMX регистр, называется MOVQ. Символ Q означает QUAD WORD (четыре слова). MMX именуются, как MM0, MM1...MM7. В отличие от регистров FPU они не организованы в стек, и вы можете их использовать их как вам угодно. Попробуем загрузить регистр MM0. Инструкция выглядит так:
movq mm0, [ebp+10h]
Есть два пути. Мы можем загрузить операнд B также в регистр. Очень просто посмотреть, как это происходит при помощи окна просмотра FPU. Регистры MMX сделаны псевдонимами к FP регистрам и окно FPU может показывать оба набора. Переключение между просмотром FP и MMX делается выбором "Display as words/Display as extendeds" в меню. Второй путь использовать шаблоны из «IA32 implementation» и выполнить сложение с ячейкой памяти B как источник. Два решения идентичны, поскольку CPU должен загрузить операнд B в регистр до выполнения операции сложения и сделать это явно с помощью инструкции MOV или неявно с помощью инструкции ADD, количество выполненных микроинструкций будет одинаковым. Мы используем более наглядный первый путь. Поэтому следующая строка снова MOVQ
movq mm1, [ebp+8]
Затем взглянем на инструкцию сложения, которая выглядит так: 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.

Код (Pascal):

1. function Min1(const A, B: Single) : Single;
2. begin
3. if A < B then
4. Result := A
5. else
6. Result := B;
7. end;

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

Код (Pascal):

1. function Min2(const A, B: Single) : Single;
2. begin
3. {
4. 00452458 55               push ebp
5. 00452459 8BEC             mov ebp,esp
6. 0045245B 51               push ecx
7. }
8. if A < B then
9. {
10. 0045245C D9450C           fld dword ptr [ebp+0Ch]
11. 0045245F D85D08           fcomp dword ptr [ebp+8]
12. 00452462 DFE0             fstsw ax
13. 00452464 9E               sahf
14. 00452465 7308             jnb +8
15. }
16. Result := A
17. {
18. 00452467 8B450C           mov eax,[ebp+0Ch]
19. 0045246A 8945FC           mov [ebp-4],eax
20. 0045246D EB06             jmp +6
21. }
22. else
23. Result := B;
24. {
25. 0045246F 8B4508           mov eax,[ebp+8]
26. 00452472 8945FC           mov [ebp-4],eax
27. }
28. {
29. 00452475 D945FC           fld dword ptr [ebp-4]
30. 00452478 59               pop ecx
31. 00452479 5D               pop ebp
32. }
33. end;

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

Код (Pascal):

1. function Min3(const A, B: Single) : Single;
2. begin
3. {
4. push ebp                     // Save ebp on stack
5. mov ebp,esp                  // New basepointer is the old stackpointer
6. push ecx                     // subtract 4 from esp
7. }
8. if A < B then
9. {
10. fld dword ptr [ebp+0Ch]      // Load A on FP stack
11. fcomp dword ptr [ebp+8]    // FP compare A to B and pop A from stack
12. fstsw ax                     // Store FP statusword in ax
13. sahf                         // Store ah into EFlags register
14. jnb +8                     // If not below jump 8 bytes forward
15. }
16. Result := A
17. {
18. mov eax,[ebp+0Ch]           // Copy A into eax
19. mov [ebp-4],eax           // Copy A into stackframe
20. jmp +6                    // Jmp 6 bytes forward
21. }
22. else
23. Result := B;
24. {
25. mov eax,[ebp+8]           // Copy B into eax
26. mov [ebp-4],eax           // Copy B into stackframe
27. }
28. {
29. fld dword ptr [ebp-4]     // Load A or B from stackframe onto FP stack
30. pop ecx                     // Add 4 to esp
31. pop ebp                     // Restore ebp
32. }
33. 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» есть таблица, в которой описаны все инструкции переходов с объяснением используемых ими флагов. Здесь мы видим, что инструкция 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-4] затем копирует результат в правильное место.

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

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

Код (Pascal):

1. function Min4(const A, B: Single) : Single;
2. asm
3. //push  ebp
4. //mov   ebp,esp
5. push  ecx
6. //if A < B then
7. fld   dword ptr [ebp+0Ch]
8. fcomp dword ptr [ebp+8]
9. fstsw ax
10. sahf
11. jnb   @ElseBegin
12. //Result := A
13. mov   eax,[ebp+0Ch]
14. mov   [ebp-4],eax
15. jmp   @ElseEnd
16. //else
17. //Result := B;
18. @ElseBegin :
19. mov   eax,[ebp+8]
20. mov   [ebp-4],eax
21. @ElseEnd :
22. fld   dword ptr [ebp-4]
23. pop   ecx
24. //pop   ebp
25. end;

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

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

Код (Text):

1. 00452465 7308             jnb +8

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

Код (Text):

1. 00452467 8B450C           mov eax,[ebp+0Ch]

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

Код (Text):

1. 0045246F 8B4508           mov eax,[ebp+8]

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

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

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

Код (Pascal):

1. function Min5(const A, B: Single) : Single;
2. asm
3. push  ecx
4. //if A < B then
5. fld   dword ptr [ebp+0Ch]
6. fcomp dword ptr [ebp+8]
7. fstsw ax
8. sahf
9. jnb   @ElseBegin
10. //Result := A
11. mov   eax,[ebp+0Ch]
12. mov   [ebp-4],eax
13. jmp   @ElseEnd
14. //else
15. //Result := B;
16. @ElseBegin :
17. mov   eax,[ebp+8]
18. mov   [ebp-4],eax
19. @ElseEnd :
20. fld   dword ptr [ebp-4]
21. pop   ecx
22. end;

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

 

Код (Pascal):

1. function Min6(const A, B: Single) : Single;
2. asm
3. //push  ecx
4. sub   esp, 4
5. //if A < B then
6. fld   dword ptr [ebp+0Ch]
7. fcomp dword ptr [ebp+8]
8. fstsw ax
9. sahf
10. jnb   @ElseBegin
11. //Result := A
12. mov   eax,[ebp+0Ch]
13. mov   [ebp-4],eax
14. jmp   @ElseEnd
15. //else
16. //Result := B;
17. @ElseBegin :
18. mov   eax,[ebp+8]
19. mov   [ebp-4],eax
20. @ElseEnd :
21. fld   dword ptr [ebp-4]
22. //pop   ecx
23. add esp, 4
24. end;

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

Код (ASM):

1. fcomp dword ptr [ebp+8]
2. fstsw ax
3. sahf

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

Код (ASM):

1. fcomip dword ptr [ebp+8]

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

Код (ASM):

1. fld    dword ptr [ebp+0Ch]
2. fcomip st(0), st(1)

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

Код (ASM):

1. fld    dword ptr [ebp+0Ch]
2. fcomip st(0), st(1)
3. ffree  st(0)

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

Код (Pascal):

1. function Min7(const A, B: Single) : Single;
2. asm
3.   sub    esp, 4
4.  //if A < B then
5.   fld    dword ptr [ebp+8]
6.   fld    dword ptr [ebp+0Ch]
7.   fcomip st(0), st(1)
8.   ffree  st(0)
9.  //fstsw ax
10.  //sahf
11.   jnb    @ElseBegin
12.  //Result := A
13.   mov    eax,[ebp+0Ch]
14.   mov    [ebp-4],eax
15.   jmp    @ElseEnd
16.  //else
17.  //Result := B;
18. @ElseBegin :
19.   mov    eax,[ebp+8]
20.   mov    [ebp-4],eax
21. @ElseEnd :
22.   fld    dword ptr [ebp-4]
23.   add    esp, 4
24. end;

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

Код (Pascal):

1. function Min8(const A, B: Single) : Single;
2. asm
3.   sub    esp, 4
4.  //if A < B then
5.   fld    dword ptr [ebp+8]
6.   fld    dword ptr [ebp+0Ch]
7.  //fcomip  st(0), st(1)
8.   fcomi  st(0), st(1)
9.  //ffree  st(0)
10.   jnb    @ElseBegin
11.  //Result := A
12.  //mov    eax,[ebp+0Ch]
13.  //mov    [ebp-4],eax
14.   ffree st(1)
15.   jmp    @ElseEnd
16.  //else
17.  //Result := B;
18. @ElseBegin :
19.  //mov    eax,[ebp+8]
20.  //mov    [ebp-4],eax
21.   fxch
22.   ffree st(1)
23. @ElseEnd :
24.  //fld    dword ptr [ebp-4]
25.   add    esp, 4
26. 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 циклов), поскольку вместо реальной пересылки данных используется переименование регистров.

Код (Pascal):

1. function Min9(const A, B: Single) : Single;
2. asm
3.  //sub    esp, 4
4.  //if A < B then
5.   fld    dword ptr [ebp+8]
6.   fld    dword ptr [ebp+0Ch]
7.   fcomi  st(0), st(1)
8.   jnb    @ElseBegin
9.  //Result := A
10.   ffree st(1)
11.   jmp    @ElseEnd
12.  //else
13.  //Result := B;
14. @ElseBegin :
15.   fxch
16.   ffree st(1)
17. @ElseEnd :
18.  //add    esp, 4
19. end;

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

Код (Pascal):

1. function Min10(const A, B: Single) : Single;
2. asm
3.  //if A < B then
4.   fld    dword ptr [ebp+8]
5.   fld    dword ptr [ebp+0Ch]
6.   fcomi  st(0), st(1)
7.   jnb    @ElseBegin
8.  //Result := A
9.   ffree st(1)
10.   jmp    @ElseEnd
11.  //else
12.  //Result := B;
13. @ElseBegin :
14.   fxch
15.   ffree st(1)
16. @ElseEnd :
17. end;

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

Код (Pascal):

1. function Min11(const A, B: Single) : Single;
2. asm
3.   fld     dword ptr [ebp+8]
4.   fld     dword ptr [ebp+0Ch]
5.   fcomi   st(0), st(1)
6.   fcmovnb st(0), st(1)
7.   ffree   st(1)
8. end;

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

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

 

Урок 5

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

Код (Pascal):

1. function ForLoop(Start, Stop : Integer) : Integer;
2. var
3. I : Integer;
4.  
5. begin
6. Result := 0;
7. for I := Start to Stop do
8. begin
9.    Result := Result + I;
10. end;
11. end;

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

Код (Pascal):

1. function ForLoopNonOpt(Start, Stop : Integer) : Integer;
2. var
3. I : Integer;
4.  
5. begin
6. {
7. push ebp
8. mov ebp,esp
9. add esp,-14h
10. mov [ebp-8],edx
11. mov [ebp-4],eax
12. }
13. Result := 0;
14. {
15. xor eax,eax
16. mov [ebp-0Ch],eax
17. }
18. for I := Start to Stop do
19. {
20. mov eax,[ebp-4]
21. mov edx,[ebp-8]
22. sub edx,eax
23. jl +15h
24. inc edx
25. mov [ebp-14h],edx
26. mov [ebp-10h],eax
27. }
28. begin
29.    Result := Result + I;
30.    {
31.    mov eax,[ebp-10h]
32.    add [ebp-0Ch],eax
33.    inc dword ptr [ebp-10h]
34.    }
35. end;
36. {
37. dec dword ptr [ebp-14h]
38. jnz -0Eh
39. mov eax,[ebp-0Ch]
40. }
41. {
42. mov esp,ebp
43. pop ebp
44. ret
45. }
46. end;

Как мы видим, компилятор сгенерировал кучу кода, где или совсем нет оптимизации или ее мало. Как обычно первые три строки это установка стекового фрейма. В данном примере он на 20 байт больше (16 hex). Две следующие строки копируют переменные Start и Stop на стек. Start передается в EAX и Stop передается в EDX, в соответствии с соглашением об вызове. Следующие две строки создают значение 0 и копируют его на стек [EBP-0Ch], это место для хранения переменной Result. Теперь мы готовы к выполнению тела цикла. Перед началом цикла необходимо убедиться, что цикл действительно должен выполняться. Если Stop больше чем Start, то это как раз тот случай. Start и Stop извлекаются из стека в регистры EAX и EDX. Мы вычисляем выражение Stop-Start и если результат отрицательный, то цикл не выполняется и управление передается в конец цикла инструкцией JL (jump low). В следующей строке увеличивается значение Stop, и оно копируется на стек [EBP-14h]. У нас нет имени для этой локальной переменной в данной точке. Данная особенность потребует дополнительных объяснений. Эта переменная (NoName) введена компилятором для оптимизации и это немного странно, поскольку мы отключили оптимизацию. Доступ до этой неименованной переменной есть в строке DEC DWORD PTR [EBP-14h]. Эта строка уменьшает ее значение на единицу, в конце каждой итерации и проверяется, что она не достигла нуля. Инструкция 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-10h], EAX. Она копирует переменную I на стек. Тело цикла состоит из одной строки Паскаля Result := Result + I. Она транслируется в три строки на ассемблере. Первые две строки загружают переменную I в регистр EAX и затем прибавляют ее к переменной Result на стеке [EBP-0Ch]. Третья строка увеличивает переменную I. На этом мы заканчиваем объяснения кода цикла и у нас остались только две вещи. Переменная Result должна быть скопирована в регистр EAX, который используется для возврата результата из функции, в соответствии с соглашением о вызове. Последние три строки восстанавливают фрейм стека и возвращают управление обратно в программу.

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

Код (Pascal):

1. function ForLoopBASM1(Start, Stop : Integer) : Integer;
2. asm
3. push ebp
4. mov ebp,esp
5. add esp,-14h
6. mov [ebp-8],edx
7. mov [ebp-4],eax
8. //Result := 0;
9. xor eax,eax
10. mov [ebp-0Ch],eax
11. //for I := Start to Stop do
12. mov eax,[ebp-4]
13. mov edx,[ebp-8]
14. sub edx,eax
15. jl @LoopEnd
16. inc edx
17. mov [ebp-14h],edx
18. mov [ebp-10h],eax
19.  //begin
20.   @LoopStart :
21.     //Result := Result + I;
22.     mov eax,[ebp-10h]
23.     add [ebp-0Ch],eax
24.     inc dword ptr [ebp-10h]
25.  //end;
26.   dec dword ptr [ebp-14h]
27.   jnz @LoopStart
28. @LoopEnd :
29.   mov eax,[ebp-0Ch]
30. mov esp,ebp
31. pop ebp
32. //ret
33. end;

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

Код (Pascal):

1. function ForLoopBASM2(Start, Stop : Integer) : Integer;
2. asm
3. push ebp
4. push ebx                      //New
5. mov ebp,esp
6. add esp,-14h
7. mov [ebp-8],edx
8. mov [ebp-4],eax
9. //Result := 0;
10. xor eax,eax
11. mov [ebp-0Ch],eax
12. //for I := Start to Stop do
13. mov eax,[ebp-4]
14. mov edx,[ebp-8]
15. sub edx,eax
16. jl @LoopEnd
17. //inc edx                    //NoName intialize
18. //mov [ebp-14h],edx          //NoName intialize
19. mov [ebp-10h],eax
20.  //begin
21.   @LoopStart :
22.     //Result := Result + I;
23.     mov eax,[ebp-10h]
24.     add [ebp-0Ch],eax
25.     inc dword ptr [ebp-10h]
26.  //end;
27.  //dec dword ptr [ebp-14h]  //NoName decrement
28.   mov ebx, [ebp-10h]         //New
29.   mov ecx, [ebp-8]         //New
30.   cmp ebx, ecx               //New
31.  //jnz @LoopStart
32.   jbe @LoopStart             //New
33. @LoopEnd :
34.   mov eax,[ebp-0Ch]
35. mov esp,ebp
36. pop ebx                     //New
37. pop ebp
38. //ret
39. end;

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

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

Код (Pascal):

1. function ForLoopBASM4(Start, Stop : Integer) : Integer;
2. asm
3. push ebp
4. push ebx
5. mov ebp,esp
6. add esp,-14h
7. mov [ebp-8],edx
8. mov [ebp-4],eax
9. //Result := 0;
10. xor eax,eax
11. mov [ebp-0Ch],eax
12. //for I := Start to Stop do
13. mov eax,[ebp-4]
14. mov edx,[ebp-8]
15. //sub edx,eax
16. //jl @LoopEnd
17. mov [ebp-10h],eax
18.  //begin
19.   @LoopStart :
20.     mov ebx, [ebp-10h]
21.     mov ecx, [ebp-8]
22.     cmp ebx, ecx
23.     ja  @LoopEnd
24.     //Result := Result + I;
25.     mov eax,[ebp-10h]
26.     add [ebp-0Ch],eax
27.     inc dword ptr [ebp-10h]
28.  //end;
29.  //mov ebx, [ebp-10h]
30.  //mov ecx, [ebp-8]
31.  //cmp ebx, ecx
32.  //jbe @LoopStart
33.   jmp @LoopStart
34. @LoopEnd :
35.   mov eax,[ebp-0Ch]
36. mov esp,ebp
37. pop ebx
38. pop ebp
39. end;

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

Код (ASM):

1. mov ecx, [ebp-8]
2. cmp ebx, ecx

на

Код (ASM):

1. mov edx, [ebp-8]
2. cmp ebx, edx

 

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

Код (ASM):

1. mov eax,[ebp-10h]
2. add [ebp-0Ch],eax
3. inc dword ptr [ebp-10h]

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

Код (ASM):

1. mov ecx,[ebp-10h]
2. add [ebp-0Ch],ecx
3. inc dword ptr [ebp-10h]

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

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

Код (Pascal):

1. function ForLoopBASM6(Start, Stop : Integer) : Integer;
2. asm
3. push ebp
4. push ebx
5. mov ebp,esp
6. add esp,-14h
7. //mov [ebp-8],edx
8. mov edx,edx
9. mov [ebp-4],eax
10. //Result := 0;
11. xor eax,eax
12. mov [ebp-0Ch],eax
13. //for I := Start to Stop do
14. mov eax,[ebp-4]
15. //mov edx,[ebp-8]
16. mov edx,edx
17. mov [ebp-10h],eax
18.  //begin
19.   @LoopStart :
20.     mov ebx, [ebp-10h]
21.     //mov edx, [ebp-8]
22.     mov edx, edx
23.     cmp ebx, edx
24.     ja  @LoopEnd
25.     //Result := Result + I;
26.     mov ecx,[ebp-10h]
27.     add [ebp-0Ch],ecx
28.     inc dword ptr [ebp-10h]
29.  //end;
30.   jmp @LoopStart
31. @LoopEnd :
32.   mov eax,[ebp-0Ch]
33. mov esp,ebp
34. pop ebx
35. pop ebp
36. end;

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

Код (Pascal):

1. function ForLoopBASM7(Start, Stop : Integer) : Integer;
2. asm
3. push ebp
4. push ebx
5. mov ebp,esp
6. add esp,-14h
7. mov edx,edx
8. mov [ebp-4],eax
9. //Result := 0;
10. xor eax,eax
11. mov [ebp-0Ch],eax
12. //for I := Start to Stop do
13. mov eax,[ebp-4]
14. mov edx,edx
15. //mov [ebp-10h],eax
16. mov ecx,eax
17.  //begin
18.   @LoopStart :
19.     //mov ebx, [ebp-10h]
20.     mov ebx, ecx
21.     mov edx, edx
22.     cmp ebx, edx
23.     ja  @LoopEnd
24.     //Result := Result + I;
25.     //mov ecx,[ebp-10h]
26.     mov ecx,ecx
27.     add [ebp-0Ch],ecx
28.     //inc dword ptr [ebp-10h]
29.     inc ecx
30.  //end;
31.   jmp @LoopStart
32. @LoopEnd :
33.   mov eax,[ebp-0Ch]
34. mov esp,ebp
35. pop ebx
36. pop ebp
37. end;

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

 

Код (Pascal):

1. function ForLoopBASM8(Start, Stop : Integer) : Integer;
2. asm
3. push ebp
4. push ebx
5. mov ebp,esp
6. add esp,-14h
7. mov edx,edx
8. mov [ebp-4],eax
9. //Result := 0;
10. xor eax,eax
11. mov [ebp-0Ch],eax
12. //for I := Start to Stop do
13. mov eax,[ebp-4]
14. mov edx,edx
15. mov ecx,eax
16. mov eax, [ebp-0Ch]                //New
17.  //begin
18.   @LoopStart :
19.     mov ebx, ecx
20.     mov edx, edx
21.     cmp ebx, edx
22.     ja  @LoopEnd
23.     //Result := Result + I;
24.     mov ecx,ecx
25.     //add [ebp-0Ch],ecx
26.     add eax,ecx
27.     inc ecx
28.  //end;
29.   jmp @LoopStart
30. @LoopEnd :
31.  //mov eax,[ebp-0Ch]
32.   mov eax,eax
33. mov esp,ebp
34. pop ebx
35. pop ebp
36. end;

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

Код (Pascal):

1. function ForLoopBASM9(Start, Stop : Integer) : Integer;
2. asm
3. push ebp
4. push ebx
5. mov ebp,esp
6. add esp,-14h
7. //mov edx,edx
8. mov [ebp-4],eax
9. //Result := 0;
10. xor eax,eax
11. mov [ebp-0Ch],eax
12. //for I := Start to Stop do
13. mov eax,[ebp-4]
14. //mov edx,edx
15. mov ecx,eax
16. mov eax, [ebp-0Ch]            
17.  //begin
18.   @LoopStart :
19.     mov ebx, ecx
20.     //mov edx, edx
21.     cmp ebx, edx
22.     ja  @LoopEnd
23.     //Result := Result + I;
24.     //mov ecx,ecx
25.     add eax,ecx
26.     inc ecx
27.  //end;
28.   jmp @LoopStart
29. @LoopEnd :
30.  //mov eax,eax
31. mov esp,ebp
32. pop ebx
33. pop ebp
34. end;

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

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

Код (Pascal):

1. function ForLoopBASM10(Start, Stop : Integer) : Integer;
2. asm
3. push ebp
4. push ebx
5. push esi
6. push edi
7. mov ebp,esp
8. add esp,-14h
9. //mov [ebp-4],eax
10. mov esi,eax
11. //Result := 0;
12. xor eax,eax
13. //mov [ebp-0Ch],eax
14. mov edi,eax
15. //for I := Start to Stop do
16. //mov eax,[ebp-4]
17. mov eax,esi
18. mov ecx,eax
19. //mov eax, [ebp-0Ch]
20. mov eax, edi
21.  //begin
22.   @LoopStart :
23.     mov ebx, ecx
24.     cmp ebx, edx
25.     ja  @LoopEnd
26.     //Result := Result + I;
27.     add eax,ecx
28.     inc ecx
29.  //end;
30.   jmp @LoopStart
31. @LoopEnd :
32. mov esp,ebp
33. pop edi
34. pop esi
35. pop ebx
36. pop ebp
37. end;

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

Код (ASM):

1. mov eax,esi
2. mov ecx,eax

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

Код (ASM):

1. mov ecx, esi

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

Код (Pascal):

1. function ForLoopBASM11(Start, Stop : Integer) : Integer;
2. asm
3. //push ebp
4. push ebx
5. push esi
6. push edi
7. //mov ebp,esp
8. //add esp,-14h
9. mov esi,eax
10. //Result := 0;
11. xor eax,eax
12. mov edi,eax
13. //for I := Start to Stop do
14. //mov eax,esi
15. //mov ecx,eax
16. mov ecx, esi
17. mov eax, edi
18.  //begin
19. @LoopStart :
20. //mov ebx, ecx
21. //cmp ebx, edx
22. cmp ecx, edx
23. ja  @LoopEnd
24.  //Result := Result + I;
25. add eax,ecx
26. inc ecx
27.  //end;
28. jmp @LoopStart
29. @LoopEnd :
30. //mov esp,ebp
31. pop edi
32. pop esi
33. pop ebx
34. //pop ebp
35. end;

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

Код (Pascal):

1. function ForLoopBASM12(Start, Stop : Integer) : Integer;
2. asm
3. push ebx
4. push esi
5. push edi
6. mov esi,eax
7. //for I := Start to Stop do
8. mov ecx, esi
9. //Result := 0;
10. xor eax,eax
11. //mov edi,eax
12. //mov eax, edi
13.  //begin
14.   @LoopStart :
15.     cmp ecx, edx
16.     ja  @LoopEnd
17.     //Result := Result + I;
18.     add eax,ecx
19.     inc ecx
20.  //end;
21.   jmp @LoopStart
22. @LoopEnd :
23. pop edi
24. pop esi
25. pop ebx
26. end;

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

 

Код (Pascal):

1. function ForLoopBASM13(Start, Stop : Integer) : Integer;
2. asm
3. push ebx
4. //push esi
5. push edi
6. //mov esi,eax
7. //for I := Start to Stop do
8. //mov ecx, esi
9. mov ecx, eax
10. //Result := 0;
11. xor eax,eax
12.  //begin
13.   @LoopStart :
14.     cmp ecx, edx
15.     ja  @LoopEnd
16.     //Result := Result + I;
17.     add eax,ecx
18.     inc ecx
19.  //end;
20.   jmp @LoopStart
21. @LoopEnd :
22. pop edi
23. //pop esi
24. pop ebx
25. end;

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

Код (Pascal):

1. function ForLoopBASM14(Start, Stop : Integer) : Integer;
2. asm
3. //push ebx
4. //push edi
5. //for I := Start to Stop do
6. mov ecx, eax
7. //Result := 0;
8. xor eax,eax
9.  //begin
10.   @LoopStart :
11.     cmp ecx, edx
12.     ja  @LoopEnd
13.     //Result := Result + I;
14.     add eax,ecx
15.     inc ecx
16.  //end;
17.   jmp @LoopStart
18. @LoopEnd :
19. //pop edi
20. //pop ebx
21. end;

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

Код (Pascal):

1. function ForLoopBASM15(Start, Stop : Integer) : Integer;
2. asm
3. mov ecx, eax
4. //Result := 0;
5. xor eax,eax
6. //for I := Start to Stop do
7. @LoopStart :
8. cmp ecx, edx
9. ja  @LoopEnd
10. //Result := Result + I;
11. add eax,ecx
12. inc ecx
13. jmp @LoopStart
14. @LoopEnd :
15. end;

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

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

Код (Pascal):

1. function ForLoopOpt(Start, Stop : Integer) : Integer;
2. var
3. I : Integer;
4.  
5. begin
6. {
7. }
8. Result := 0;
9. {
10. xor ecx,ecx
11. }
12. for I := Start to Stop do
13. {
14. sub edx,eax
15. jl +$08
16. inc edx
17. xchg eax,edx
18. }
19. begin
20.   Result := Result + I;
21.  {
22.   add ecx,edx
23.   inc edx
24.   }
25. end;
26. {
27. dec eax
28. jnz -$06
29. }
30. {
31. mov eax,ecx
32. }
33. end;

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

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

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

Код (Pascal):

1. function ForLoopNoLoopInverNoNoName(Start, Stop : Integer) : Integer;
2. asm
3. mov ecx, eax
4. //Result := 0;
5. xor eax,eax
6. //for I := Start to Stop do
7. @LoopStart :
8. cmp ecx, edx
9. ja  @LoopEnd
10. inc ecx
11. jmp @LoopStart
12. @LoopEnd :
13. 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 = ? циклов.

Код (Pascal):

1. function ForLoopLoopInverNoNoName(Start, Stop : Integer) : Integer;
2. asm
3. mov ecx, eax
4. //Result := 0;
5. xor eax,eax
6. //for I := Start to Stop do
7. cmp ecx, edx
8. ja  @LoopEnd
9. @LoopStart :
10. inc ecx
11. cmp ecx, edx
12. jbe @LoopStart
13. @LoopEnd :
14. end;

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

Код (Pascal):

1. function ForLoopNoLoopInverNoName(Start, Stop : Integer) : Integer;
2. asm
3. //Result := 0;
4. xor ecx,ecx
5. //for I := Start to Stop do
6. sub edx,eax
7. cmp edx, 0
8. @LoopStart :
9. jz  @LoopEnd
10. inc eax
11. dec edx
12. jmp @LoopStart
13. @LoopEnd :
14. mov eax,ecx
15. end;

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

Код (Pascal):

1. function ForLoopLoopInverNoName(Start, Stop : Integer) : Integer;
2. asm
3. //Result := 0;
4. xor ecx,ecx
5. //for I := Start to Stop do
6. sub edx,eax
7. jl @LoopEnd
8. inc edx
9. @LoopStart :
10. inc eax
11. dec edx
12. jnz @LoopStart
13. @LoopEnd :
14. mov eax,ecx
15. end;

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

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

Код (Pascal):

1. var
2. Starttime, Endtime, Runtime : TDateTime;
3. I, LoopResult : Integer;
4. RunTimeSec, NoOfLoopsPerSec, NoOfLoops, ClockCount, LoopEnd2Float,
5. LoopEndFloat, LoopStartFloat : Double;
6.  
7. begin
8. Starttime := Time;
9. for I := 1 to LOOPEND2 do
10. begin
11.   LoopResult := ForLoopNoLoopInverNoName(LOOPSTART, LOOPEND);
12. end;
13. Endtime := Time;
14. Runtime := Endtime - Starttime;
15. CEdit.Text := IntToStr(LoopResult);
16. RuntimeEdit4.Text := TimeToStr(Runtime);
17. RunTimeSec := RunTime*24*60*60;
18. LoopEnd2Float := LOOPEND2;
19. LoopEndFloat := LOOPEND;
20. LoopStartFloat := LOOPSTART;
21. NoOfLoops := LoopEnd2Float * (LoopEndFloat - LoopStartFloat);
22. NoOfLoopsPerSec := NoOfLoops / RunTimeSec;
23. ClockCount := CLOCK / NoOfLoopsPerSec;
24. ClockCountEdit4.Text := FloatToStrf(ClockCount, ffFixed, 9, 1);
25. 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 на этом коде.

 

Урок 6

Это урок 6 и его тема CharPos. Данная функция ищет первое вхождение символа в строке, и возвращает его позицию когда найдет. Если ничего не найдено, то возвращается 0. функция из Delphi делает тоже самое, но с различием, что ищется вхождение подстроки в строке. Передача символа в Pos как подстроки возможна и это путь использования Pos как CharPos. В данном уроке мы разработаем CharPos, которая будет примерно в 4 раза быстрее, чем Pos.
Как обычно мы начнем с Паскаль реализации алгоритма.

Код (Pascal):

1. function CharPos2(Chr : Char; const Str : AnsiString) : Cardinal;
2. var
3. I : Integer;
4. begin
5. if (Str <> '') then
6. begin
7.   I := 0;
8.   repeat
9.   Inc(I);
10.   until((Str[I] = Chr) or (Str[I] = #0));
11.   if (Str[I] <> #0) then
12.   Result := I
13.   else
14.   Result := 0;
15. end
16. else
17.   Result := 0;
18. end;

В функцию предаются два параметры типа Char и string. Параметр string передается как константа. Результат работы функции типа Cardinal. В начале в функции проверяется, что входная строка не пустая и если пустая, то возвращается 0. Если строка есть, то проходим по ней пока не найдем в цикле repeat until до тех пор пока не встретим совпадение с входным символом. Если встретился символ 0, он также является признаком окончания строки и цикла. Поскольку цикл может завершиться в случае нахождения символа и в случае достижения конца строки мы должны знать причину, что бы вернуть правильный результат. Если цикл закончился нахождением символа, то мы вернем переменную счетчика, а иначе вернем 0.
Также возможно использовать длину строки как условие для окончания цикла в случае неуспешного поиска. Этот код будет выглядеть так.

Код (Pascal):

1. function CharPos1(Chr : Char; const Str : AnsiString) : Cardinal;
2. var
3. StrLenght, I : Integer;
4. begin
5. StrLenght := Length(Str);
6. if StrLenght > 0 then
7. begin
8.   I := 0;
9.   repeat
10.   Inc(I);
11.   until((Str[I] = Chr) or (I > StrLenght));
12.   if I <= StrLenght then
13.   Result := I
14.   else
15.   Result := 0;
16. end
17. else
18.   Result := 0;
19. end;

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

Код (Pascal):

1. const
2. NOOFLOOPS : Cardinal = 200000;
3. SCALE : Cardinal = 1000;
4.  
5. procedure Benchmark;
6. var
7. lpPerformanceCount, StartCount, EndCount : TLargeInteger;
8. Succes : Boolean;
9. Str, Str1, FunctionName : AnsiString;
10. Chr1, Chr2 : Char;
11. I, CharPos, J, K, Bench, SumBench : Cardinal;
12. StringArray : array[1..255] of AnsiString;
13.  
14. begin
15. Series1.Clear;
16. Str1 := 'T';
17. for J := 1 to 255 do
18. begin
19.   StringArray[J] := Str1;
20.   Str1 := 'A' + Str1;
21. end;
22. SumBench := 0;
23. Chr1 := 'T';
24. Chr2 := 'X';
25. for K := 1 to 255 do
26. begin
27.   Str := StringArray[K];
28.   Succes := QueryPerformanceCounter(lpPerformanceCount);
29.   if Succes then
30.   StartCount := lpPerformanceCount
31.   else
32.   raise Exception.Create('QueryPerformanceCounter failed');
33.   for I := 1 to NOOFLOOPS dиo
34.   begin
35.   CharPos := CharPosFunction(Chr1, Str);
36.   end;
37.   for I := 1 to NOOFLOOPS do
38.   begin
39.   CharPos := CharPosFunction(Chr2, Str);
40.   end;
41.   Succes := QueryPerformanceCounter(lpPerformanceCount);
42.   if Succes then
43.   EndCount := lpPerformanceCount
44.   else
45.   raise Exception.Create('QueryPerformanceCounter failed');
46.   Bench := Round((EndCount - StartCount) / SCALE);
47.   Series1.AddXY(K, Bench, '', clBlue);
48.   Bench := Round(Bench / K);
49.   SumBench := SumBench + Bench;
50.   Update;
51. end;
52. FunctionName :=
53.   FunctionSelectRadioGroup.Items[FunctionSelectRadioGroup.ItemIndex];
54. ReportRichEdit.Lines.Add(FunctionName + #9 + IntToStr(SumBench));
55. end;

Программа измерения строит тестовый массив из 255 AnsiStrings. Первая строка 'T'. 'T' также символ для поиска. Поэтому строка номер 1 наиболее короткая для успешного поиска. Следующие строки равны 'AT', 'AAT' и 'AAAT'. Я надеюсь, что этот шаблон прост и понятен. Также важно провести измерение и для неуспешного поиска. В этом случае для поиска мы используем символ 'X'. Программа измерения делает некоторое количество (NOOFLOOPS) поисков по каждой строке и измеряет время на каждой строке. Поскольку мы хотим, что бы результат был аппроксимирован независимо от длины строки, то полученное время делится на длину строки.
В данном тесте CharPos1 получил результат 767 на P4 1600A, разогнанный до 1920 и CharPos2 получил результат 791. Для сравнения Delphi Pos получил результат всего 2637.
Поскольку CharPos1 незначительно лучше, чем CharPos2, то мы выбрали его для дальнейшей оптимизации. Это ассемблерный код на Delphi 6 откомпилированный с включенной оптимизацией.

Код (Pascal):

1. function CharPos14(Chr : Char; const Str : AnsiString) : Cardinal;
2. var
3. StrLenght, I : Integer;
4. begin
5. {
6. push ebx
7. push esi
8. mov  esi,edx
9. mov  ebx,eax
10. }
11. StrLenght := Length(Str);
12. {
13. mov  eax,esi
14. call @LStrLen
15. mov  edx,eax
16. }
17. if StrLenght > 0 then
18. {
19. test edx,edx
20. jle  @Else1Begin
21. }
22. begin
23.   I := 0;
24.  {
25.   xor eax,eax
26.   }
27.  repeat
28.   {
29.   @RepeatBegin :
30.   }
31.   Inc(I);
32.   {
33.   inc eax
34.   }
35.  until((Str[I] = Chr) or (I > StrLenght));
36.  {
37.   cmp bl,[esi+eax-$01]
38.   jz  @If2
39.   cmp edx,eax
40.   jnl @RepeatBegin :
41.   }
42.  if I <= StrLenght then
43.  {
44.   @If2 :
45.   cmp edx,eax
46.   jnl @Exit
47.   }
48.   Result := I
49.   {
50.   }
51.  else
52.   Result := 0;
53.   {
54.   xor eax,eax
55.   pop esi
56.   pop ebx
57.   ret
58.   }
59. end
60. else
61. Result := 0;
62. {
63. @Else1Begin :
64. xor eax,eax
65. }
66. {
67. @Exit :
68. pop esi
69. pop ebx
70. }
71. end;

 

В данный момент здесь нет фрейма стека. Регистры EBX и ESI используются, и поэтому требуется их сохранения и восстановление при выходе из функции. Поскольку функция не имеет своего собственно фрейма стека, то они просто помещаются на верхушку стека текущего фрейма. Входные параметры принимаются в регистрах EAX и EDX и они первым делом копируются в регистры ESI и EBX. Функция Length имеет внутренне секретное имя, которое LStrLen. В данную функцию передается параметр Str, который передается через регистр EAX. Отсюда мы видим, что функция LStrLen также следует регистровому соглашению о вызове. Str был получен через регистр EDX, затем был скопирован в регистр ESI и затем в EAX. LStrLen возвращает свой результат также в регистре EAX. Этот результат копируется в EDX и сравнивается с 0. TEST EDX,EDX, тоже самое, что и CMP EDX,0 и устанавливает флаги. Инструкция JLE проверяет флаги и передает управление в часть ELSE блока IF-ELSE, если StrLenght меньше или равен нулю. В части ELSE мы видим только одну Паскаль строку, которая Result := 0;. Поскольку наша функция должна вернуть результат в EAX мы создаем значение 0 как XOR EAX с самим собой. Если длина строки больше нуля, то управление продолжается в части блока IF. Первая строка этого блока устанавливает начальное значение счетчика I в ноль. Для этого снова используется инструкция XOR. Тело цикла имеет только одну строку, очень простую для понимания INC(I); = INC EAX. И ассемблерный, и Паскаль код делают одинаково
Реализация проверки цикла, это то место где проводится реальная работа. Это сделано с помощью четырех строк на ассемблере.

Код (ASM):

1. cmp bl,[esi+eax-1]
2. jz  @If2
3. cmp edx,eax
4. jnl @RepeatBegin :
5.  

Мы видим здесь две инструкции перехода. Последняя начинает цикла, а первая выходит из цикла. Здесь также две инструкции сравнения CMP для установки флагов. Вторая очень простая для понимания. Она сравнивает EAX с EDX. Быстрый взгляд на Паскаль код, показывает, что здесь StrLenght и I в этих регистрах. В действительности мы видим, что в eax находится I, а вверху функции мы видим, что StrLenght находится в EDX.
В строке 4 параметр Chr бил скопирован в регистр EBX, но char размером только в один байт. Поэтому первая инструкция CMP сравнивает, что с в BL, который содержит младший байт EBX. Мы предполагаем, что символ поиска - Chr – сравнивается с символом 1, 2, 3… входной строки. Поэтому выражение [ESI+EAX-1] должно быть указателем на эту строку. EAX это счетчик цикла I, который имеет значение 1, при первой итерации. Регистр ESI должен быть адресом параметра Str, который был принят через регистр EDX, и сразу был скопирован в регистр ESI. -1 это константа смещения, которая необходима, поскольку первый символ в AnsiString расположен по смещению 0. Это позиция, на которую указывает Str.
А куда же пропал OR из кода Паскаля? Для понимания этого мы должны поговорить насчет оптимизации, называемой частичное выполнение логических выражений. Эта оптимизация применяется к логическому оператору AND, и к логическому оператору OR.
Посмотрим это на примере таблицы истинности для AND.

A	B	A and B
false	false	false
false	true	false
true	true	false
true	true	true

Оператор AND возвращает значение TRUE только если оба операнда TRUE. В этом и содержится преимущество при оптимизации при частичном выполнении логических выражений. Если один из операндов FALSE, то нет необходимости проверять другой, поскольку результат все равно FALSE, вне зависимости от его значения.
Таблица истинности для оператора OR:

A	B	A or B
false	false	false
false	true	true
true	false	true
true	true	true

Результат для OR истинен, если хотя бы один из операндов или оба операнда также истинны. Если один из операндов истинен, то также нет нужды проверять другой.
Наша проверка прекращения цикла дает преимущество, при выходе из цикла, если первое сравнение будет успешным. Это случается если мы нашли вхождение символа в строке. Если найдено совпадение, то нет нужды проверять на символ ограничитель! Последнее сравнение выполняется в случае отсутствия равенства.
Если бы мы знали, что ни будь о строках и символах переданных нашей функции до вызова, то мы могли бы получить преимущества, просто сменив порядок тестов, так что бы получить значение TRUE первым.
Попробуйте сменить параметр компилятора "complete Boolean evaluation", в свойствах проекта, и посмотрите какой код будет сгенерирован.
Остаток кода уже разобран в более ранних уроках, и мы пропустим его объяснение, лучше сходите и выпейте взамен чашечку кофе

 

Теперь можно выполнить некоторую оптимизацию. В начале превратим функцию в чисто ассемблерную. Метки были объяснены в листинге предыдущего кода. Здесь видно, что они следуют Паскаль коду интуитивным образом.

Код (Pascal):

1. function CharPos15(Chr : Char; const Str : AnsiString) : Cardinal;
2. //var
3. //StrLenght, I : Integer;
4.  
5. asm
6. push ebx
7. push esi
8. mov  esi,edx
9. mov  ebx,eax
10. //StrLenght := Length(Str);
11. mov  eax,esi
12. call System.@LStrLen
13. mov  edx,eax
14. //if StrLenght > 0 then
15. test edx,edx
16. jle  @Else1Begin
17. //I := 0;
18. xor eax,eax
19. //repeat
20. @RepeatBegin :
21. //Inc(I);
22. inc  eax
23. //until((Str[I] = Chr) or (I > StrLenght));
24. cmp  bl,[esi+eax-1]
25. jz  @If2
26. cmp  edx,eax
27. jnl  @RepeatBegin
28. //if I <= StrLenght then
29. @If2 :
30. cmp  edx,eax
31. jnl  @Exit
32. //Result := I
33. //else
34. //Result := 0;
35. xor eax,eax
36. pop  esi
37. pop  ebx
38. ret
39. //else
40. //Result := 0;
41. @Else1Begin :
42. xor eax,eax
43. @Exit :
44. pop  esi
45. pop  ebx
46. end;

Вызов функции LStrLen сделан с префиксом System, иначе компилятор не сможет распознать ее. LStrLen реализована в модуле System.
Секция VAR удалена, поскольку мы не ссылаемся ни к каким переменным по имени.

Код (Pascal):

1. function CharPos16(Chr : Char; const Str : AnsiString) : Cardinal;
2.  asm
3. push ebx
4. push esi
5. mov  esi,edx
6. mov  ebx,eax
7. //StrLenght := Length(Str);
8. mov  eax,esi
9. //call System.@LStrLen
10. //*************
11. test eax,eax
12. jz  @LStrLenExit
13. mov eax,[eax-4]
14. @LStrLenExit :
15. //*************
16. mov  edx,eax
17. //if StrLenght > 0 then
18. test edx,edx
19. jle @Else1Begin
20. //I := 0;
21. xor eax,eax
22. //repeat
23. @RepeatBegin :
24. //Inc(I);
25. inc  eax
26. //until((Str[I] = Chr) or (I > StrLenght));
27. cmp  bl,[esi+eax-1]
28. jz  @If2
29. cmp  edx,eax
30. jnl  @RepeatBegin
31. //if I <= StrLenght then
32. @If2 :
33. cmp  edx,eax
34. jnl  @Exit
35. //Result := I
36. //else
37. //Result := 0;
38. xor eax,eax
39. pop  esi
40. pop  ebx
41. ret
42. //else
43. //Result := 0;
44. @Else1Begin :
45. xor eax,eax
46. @Exit :
47. pop  esi
48. pop  ebx
49. end;

Первая вещь, которую мы сделаем, это сделаем функцию LstrLen inline. Сделаем это путем трассировки и копированием ее тела из окна CPU view. Она состоит из четырех строк.

Код (ASM):

1. test eax,eax
2. [I][I]jz +3
3. mov eax,[eax-4]
4. ret

Если указатель, переданный через EAX, в функцию LStrLen имеет nil, то ничего не делается, а просто производится возврат из функции. Если же указатель действительный, то длина строки расположена, в 4 предшествующих строке байтах. Эти 4 байта возвращаются, через регистр EAX. Для превращения этой функции в inline функцию, мы заменим вызов этой функции этими четырьмя строками. Инструкция JZ передает управление на инструкцию RET. Взамен инструкции RET мы передадим управление на метку LStrLenExit. Инструкция RET осуществляет возврат из функции. Данная инструкция RET должна быть удалена, иначе она вернет управление в CharPos, это не то, что мы хотим. А вот так наша встроенная (inline) функция должна выглядеть.

Код (Pascal):

1. test eax,eax
2. jz  @LStrLenExit
3. mov eax,[eax-4]
4. @LStrLenExit :
5.  
6. function CharPos17(Chr : Char; const Str : AnsiString) : Cardinal;
7. asm
8. push ebx
9. push esi
10. mov  esi,edx
11. mov  ebx,eax
12. //StrLenght := Length(Str);
13. mov  eax,esi
14. //*************
15. test eax,eax
16. //jz  @LStrLenExit
17. jz  @Else1Begin
18. mov eax,[eax-4]
19. //@LStrLenExit :
20. //*************
21. mov  edx,eax
22. //if StrLenght > 0 then
23. //test edx,edx
24. //jle @Else1Begin
25. //I := 0;
26. xor eax,eax
27. //repeat
28. @RepeatBegin :
29. //Inc(I);
30. inc  eax
31. //until((Str[I] = Chr) or (I > StrLenght));
32. cmp  bl,[esi+eax-1]
33. jz  @If2
34. cmp  edx,eax
35. jnl  @RepeatBegin
36. //if I <= StrLenght then
37. @If2 :
38. cmp  edx,eax
39. jnl  @Exit
40. //Result := I
41. //else
42. //Result := 0;
43. xor eax,eax
44. pop  esi
45. pop  ebx
46. ret
47. //else
48. //Result := 0;
49. @Else1Begin :
50. xor eax,eax
51. @Exit :
52. pop  esi
53. pop  ebx
54. end;

Теперь мы видим, что Паскаль строка; IF STRLENGHT > 0 THEN, проверяет длину точно также, как первая строка во встроенной LStrLen. Проверка Str на nil вполне достаточно. Вторая строка удалена и первая изменена, чтобы переход был на @Else1Begin вместо простого выхода из встроенной StrLen функции, если Str равен nil. Теперь нет надобности в метке LStrLenExit.

Код (Pascal):

1. function CharPos18(Chr: Char; const Str: AnsiString) : Cardinal;
2.  asm
3. push ebx
4. push esi
5. mov  esi,edx
6. mov  ebx,eax
7. //StrLenght := Length(Str);
8. //mov  eax,esi
9. //if StrLenght > 0 then
10. //test eax,eax
11. test esi,esi
12. jz  @Else1Begin
13. //mov eax,[eax-4]
14. mov eax,[esi-4]
15. mov  edx,eax
16. //I := 0;
17. xor eax,eax
18. //repeat
19. @RepeatBegin :
20. //Inc(I);
21. inc  eax
22. //until((Str[I] = Chr) or (I > StrLenght));
23. cmp  bl,[esi+eax-1]
24. jz  @If2
25. cmp  edx,eax
26. jnl  @RepeatBegin
27. //if I <= StrLenght then
28. @If2 :
29. cmp  edx,eax
30. jnl  @Exit
31. //Result := I
32. //else
33. //Result := 0;
34. xor eax,eax
35. pop  esi
36. pop  ebx
37. ret
38. //else
39. //Result := 0;
40. @Else1Begin :
41. xor eax,eax
42. @Exit :
43. pop  esi
44. pop  ebx
45. end;

Мы переместили проверку STRLENGHT = 0 и комментарий //IF STRLENGHT > 0 также должен быть перемещен. После встраивания функции стало возможным избавиться от копирования ESI в этих строках.

Код (ASM):

1. mov  eax,esi
2. //*************
3. test eax,eax
4. jz  @Else1Begin
5. mov eax,[eax-4]

Последние строки переписывают EAX и последнее использованное значение в EAX, которое было скопировано из ESI.

Код (ASM):

1. mov  eax,esi
2. //*************
3. //test eax,eax
4. test esi,esi
5. jz  @Else1Begin
6. //mov eax,[eax-4]
7. mov eax,[esi-4]

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

Код (Pascal):

1. //mov  eax,esi
2.  test esi,esi
3. jz  @Else1Begin
4. mov eax,[esi-$04]
5.  
6. function CharPos19(Chr : Char; const Str : AnsiString) : Cardinal;
7. asm
8. push ebx
9. push esi
10. mov  esi,edx
11. mov  ebx,eax
12. //if StrLenght > 0 then
13. test esi,esi
14. jz  @Else1Begin
15. //StrLenght := Length(Str);
16. //mov eax,[esi-4]
17. mov edx,[esi-4]
18. //mov  edx,eax
19. //I := 0;
20. xor eax,eax
21. //repeat
22. @RepeatBegin :
23. //Inc(I);
24. inc  eax
25. //until((Str[I] = Chr) or (I > StrLenght));
26. cmp  bl,[esi+eax-1]
27. jz  @If2
28. cmp  edx,eax
29. jnl  @RepeatBegin
30. //if I <= StrLenght then
31. @If2 :
32. cmp  edx,eax
33. jnl  @Exit
34. //Result := I
35. //else
36. //Result := 0;
37. xor eax,eax
38. pop  esi
39. pop  ebx
40. ret
41. //else
42. //Result := 0;
43. @Else1Begin :
44. xor eax,eax
45. @Exit :
46. pop  esi
47. pop  ebx
48. end;

Как результат встраивания функции LStrLen мы можем также удалить одну инструкцию. Функция LStrLen возвращает свой результат в EAX, затем он копируется в EDX. MOV EAX, [ESI-4]. Это можно изменить на MOV EDX, [ESI-4], а инструкцию MOV EDX, EAX можно удалить.
После этого изменения сменим наш фокус на цикл. Это особенно важно, поскольку это выполняется множество раз, в зависимости от длины строки и позиции, в которой произойдет сравнение.

Код (Pascal):

1. function CharPos20(Chr : Char; const Str : AnsiString) : Cardinal;
2. asm
3. push ebx
4. push esi
5. mov  esi,edx
6. mov  ebx,eax
7. //if StrLenght > 0 then
8. test esi,esi
9. jz  @Else1Begin
10. //StrLenght := Length(Str);
11. mov edx,[esi-4]
12. //I := 0;
13. xor eax,eax
14. dec  esi
15. @RepeatBegin :
16. //Inc(I);
17. inc  eax
18. //until((Str[I] = Chr) or (I > StrLenght));
19. //cmp  bl,[esi+eax-1]
20. cmp  bl,[esi+eax]
21. jz  @If2
22. cmp  edx,eax
23. jnl  @RepeatBegin
24. //if I <= StrLenght then
25. @If2 :
26. cmp  edx,eax
27. jnl  @Exit
28. //Result := 0;
29. xor eax,eax
30. pop  esi
31. pop  ebx
32. ret
33. //Result := 0;
34. @Else1Begin :
35. xor eax,eax
36. @Exit :
37. pop  esi
38. pop  ebx
39. end;