Однако такие компиляторы как Borland и WATCOM не умеют заменять деление более быстрым умножением для чисел отличных от степени двойки. В подтверждении тому рассмотрим результат компиляции того же примера компилятором Borland C++: _main proc near ; DATA XREF: DATA:00407044 o push ebpmov ebp, esp; Открываем кадр стека push ebx; Сохраняем EBX mov eax, ecx; Копируем в EAX содержимое неинициализированной регистровой переменной ECX mov ebx, 0Ah; Заносим в EBX значение 0xA cdq; Расширяем EAX до четверного слова EDX:EAX idiv ebx; Делим ECX на 0xA (примерно 20 тактов) push eax; Передаем полученное значение функции printf test ecx, ecxjns short loc_401092; Если делимое не отрицательно, то переход на loc_401092 add ecx, 1Fh; Если делимое положительно, то добавляем к нему 0x1F для округления loc_401092: ; CODE XREF: _main+11 jsar ecx, 5; Сдвигом на пять позиций вправо делим число на 32 push ecxpush offset aXX ; "%x %x\n"call _printfadd esp, 0Ch; printf("%x %x\n", var_a / 10, var_a / 32) xor eax, eax; Возвращаем ноль pop ebxpop ebp; Закрываем кадр стека retn _main endp

1.4 Идентификация оператора "%"

Специальной инструкции для вычисления остатка в наборе команд микропроцессоров серии 80x86 нет, - вместо этого остаток вместе с частным возвращается инструкциями деления DIV, IDIV и FDIVx. Если делитель представляет собой степень двойки (2^N = b), а делимое беззнаковое число, то остаток будет равен N младшим битам делимого числа. Если же делимое - знаковое, необходимо установить все биты, кроме первых N равными знаковому биту для сохранения знака числа. Причем, если N первых битов равно нулю, все биты результата должны быть сброшены независимо от значения знакового бита.

Таким образом, если делимое - беззнаковое число, то выражение a % 2^N транслируется в конструкцию: "AND a, N", в противном случае трансляция становится неоднозначна - компилятор может вставлять явную проверку на равенство нулю с ветвлением, а может использовать хитрые математические алгоритмы, самый популярный из которых выглядит так: DEC x\ OR x, -N\ INC x. Весь фокус в том, что если первые N бит числа x равны нулю, то все биты результата кроме старшего, знакового бита, будут гарантированно равны одному, а OR x, -N принудительно установит в единицу и старший бит, т.е. получится значение, равное, -1. А INC -1 даст ноль! Напротив, если хотя бы один из N младших битов равен одному, заема из старших битов не происходит и INC x возвращает значению первоначальный результат.

Продвинутые оптимизирующие компиляторы могут путем сложных преобразований заменять деление на ряд других, более быстродействующих операций. К сожалению, алгоритмов для быстрого вычисления остатка для всех делителей не существует и делитель должен быть кратен k * 2^t, где k и t - некоторые целые числа. Тогда остаток можно вычислить по следующей формуле: a % b = a % k*2^t = a -((2^N/k * a/2^N) & -2^t)*k

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

Рассмотрим следующий пример: main(){ int a;printf("%x %x\n",a % 16, a % 10); }

Идентификация оператора "%"

Результат его компиляции компилятором Microsoft Visual C++ с настройками по умолчанию должен выглядеть так: main proc near ; CODE XREF: start+AF p var_4 = dword ptr -4push ebpmov ebp, esp; Открываем кадр стека push ecx; Резервируем память для локальной переменной mov eax, [ebp+var_a]; Заносим в EAX значение переменной var_a cdq; Расширяем EAX до четвертного слова EDX:EAX mov ecx, 0Ah; Заносим в ECX значение 0xA idiv ecx; Делим EDX:EAX (var_a) на ECX (0xA) push edx; Передаем остаток от деления var_a на 0xA функции printf mov edx, [ebp+var_a]; Заносим в EDX значение переменной var_a and edx, 8000000Fh; "Вырезаем" знаковый бит и четыре младших бита числа; в четырех младших битах содержится остаток от деления EDX на 16 jns short loc_401020; Если число не отрицательно, то прыгаем на loc_401020 dec edxor edx, 0FFFFFFF0hinc edx; Эта последовательность, как говорилось выше, характера для быстрого; расчета остатка знакового числа; Следовательно, последние шесть инструкций расшифровываются как:; EDX = var_a % 16 loc_401020: ; CODE XREF: main+19 jpush edxpush offset aXX ; "%x %x\n"call _printfadd esp, 0Ch; printf("%x %x\n",var_a % 0xA, var_a % 16) mov esp, ebppop ebp; Закрываем кадр стекаretn main endp

Любопытно, что оптимизация не влияет на алгоритм вычисления остатка. Увы, ни Microsoft Visual C++, ни остальные известные компиляторы не умеют вычислять остаток умножением.

1.5 Идентификация оператора "*"

В общем случае оператор "*" транслируется либо в машинную инструкцию "MUL" (беззнаковое целочисленное умножение), либо в "IMUL" (целочисленное умножение со знаком), либо в "FMULx" (вещественное умножение). Если один из множителей кратен степени двойки, то "MUL" ("IMUL") обычно заменяется командой битового сдвига влево "SHL" или инструкцией "LEA", способной умножать содержимое регистров на 2, 4 и 8. Обе последних команды выполняются за один такт, в то время как MUL требует в зависимости от модели процессора от двух до девяти тактов. К тому же LEA за тот же такт успевает сложить результат умножение с содержимым регистра общего назначения и/или константой. Это позволяет умножать на 3, 5 и 9 просто добавляя к умножаемому регистру его значение. Правда, у операции LEA есть один недочет - она может вызывать остановку AGI, в конечном счете весь выигрыш в быстродействии сводится на нет.

Рассмотрим следующий пример: main(){ int a;printf("%x %x %x\n",a * 16, a * 4 + 5, a * 13); }

Идентификация оператора "*"

Результат его компиляции компилятором Microsoft Visual C++ с настройками по умолчанию должен выглядеть так: main proc near ; CODE XREF: start+AF p var_a = dword ptr -4 push ebpmov ebp, esp; Открываем кадр стека push ecx; Резервируем место для локальной переменной var_a mov eax, [ebp+var_a]; Загружаем в EAX значение переменной var_a imul eax, 0Dh; Умножаем var_a на 0xD, записывая результат в EAX push eax; Передаем функции printf произведение var_a * 0xD mov ecx, [ebp+var_a]; Загружаем в ECX значение var_a lea edx, ds:5[ecx*4]; Умножаем ECX на 4 и добавляем к полученному результату 5, записывая его в EDX; И все это выполняется за один такт! push edx; Передаем функции printf результат var_a * 4 + 5 mov eax, [ebp+var_a]; Загружаем в EAX значение переменной var_a shl eax, 4; Умножаем var_a на 16 push eax; Передаем функции printf произведение var_a * 16 push offset aXXX ; "%x %x %x\n"call _printfadd esp, 10h; printf("%x %x %x\n", var_a * 16, var_a * 4 + 5, var_a * 0xD) mov esp, ebppop ebp; Закрываем кадр стекаretn main endp

За вычетом вызова функции printf и загрузки переменной var_a из памяти уходит всего лишь три такта процессора. Если скомпилировать этот пример с ключом "/Ox", то получится вот что: main proc near ; CODE XREF: start+AF ppush ecx; Выделяем память для локальной переменной var_a mov eax, [esp+var_a]; Загружаем в EAX значение переменной var_a lea ecx, [eax+eax*2]; ECX = var_a * 2 + var_a = var_a * 3 lea edx, [eax+ecx*4]; EDX = (var_a * 3)* 4 + var_a = var_a * 13!; Так компилятор ухитрился умножить var_a на 13,; причем всего за один (!) такт. Также следует отметить, что обе инструкции LEA ; прекрасно спариваются на Pentium MMX и Pentium Pro! lea ecx, ds:5[eax*4]; ECX = EAX*4 + 5 push edxpush ecx; Передаем функции printf var_a * 13 и var_a * 4 +5 shl eax, 4; Умножаем var_a на 16 push eaxpush offset aXXX ; "%x %x %x\n"call _printfadd esp, 14h; printf("%x %x %x\n", var_a * 16, var_a * 4 + 5, var_a * 13) retn main endp