Урок 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, даже если он не модифицируется внутри функции.
Просьба писать ваши замечания, наблюдения и все остальное,
что поможет улучшить предоставляемую информацию на этом сайте.
ВСЕ КОММЕНТАРИИ МОДЕРИРУЮТСЯ ВРУЧНУЮ, ТАК ЧТО СПАМИТЬ БЕСПОЛЕЗНО!