Инструкции MUL/DIV против MOV & SHL/SHR (Pentium Pro)

Question

Почему вы хотите использовать:

MOV EAX, 22 
SHL EAX, 2

... при умножении на 4 вместо использования MUL инструкция?
Я понимаю, что это также может быть сделано с SHR вместо DIV также.

Каковы преимущества этого?
Также вы можете сделать это с нечетными числами или это могут быть только четные числа?

Answer 1

С использованием SHL/SHR Инструкция, вообще говоря, намного быстрее, чем MUL/DIV,

Чтобы ответить на второй вопрос, вы также можете сделать это с нечетными числами, но вам нужно добавить еще одну инструкцию. Так что технически вы не можете просто сделать это, используя SHL/SHR,

Например: следующий код умножается на 5 без использования MUL инструкция:

mov num, 5
mov eax, num
mov ebx, num
shl eax, 2    ; MULs by 4
add eax, ebx  ; ADD the x1 to make = 5

Answer 2

Есть ряд кодовых идиом, которые быстрее, чем "константа MUL".

Современные процессоры x86 выполняют MUL за несколько часов, как минимум. Таким образом, любая кодовая последовательность, которая вычисляет произведение за 1-2 такта, будет превосходить MUL. Вы можете использовать быстрые инструкции (ADD, SHL, LEA, NEG) и тот факт, что процессор может выполнять некоторые из этих команд параллельно за один такт, чтобы заменить MUL. Возможно, это означает, что вы можете выполнить 4 из этих инструкций во многих комбинациях за 2 такта, если избегаете некоторых зависимостей данных.

Инструкция LEA особенно интересна, потому что она может умножаться на несколько небольших констант (1,2,3,4,5,8,9), а также перемещать продукт в другой регистр, что является одним из простых способов разорвать зависимости данных. Это позволяет вам вычислять субпродукт, не разрушая исходный операнд.

Некоторые примеры:

Умножьте EAX на 5, переместите продукт в ESI:

   LEA ESI, [EAX+4*EAX]    ; this takes 1 clock

Умножьте EAX на 18:

   LEA  EAX, [EAX + 8*EAX]
   SHL  EAX, 1

Умножьте EAX на 7, переместите результат в EBX:

   LEA  EBX, [8*EAX]
   SUB  EBX, EAX

Умножьте EAX на 28:

   LEA  EBX, [8*EAX]
   LEA  ECX, [EAX+4*EAX]  ; this and previous should be executed in parallel
   LEA  EAX, [EBX+4*ECX]

Умножьте на 1020:

   LEA  ECX, [4*EAX]
   SHL  EAX, 10         ; this and previous instruction should be executed in parallel
   SUB  EAX, ECX

Умножить на 35

   LEA  ECX, [EAX+8*EAX]
   NEG  EAX             ; = -EAX
   LEA  EAX, [EAX+ECX*4]

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

Примечательно, сколько умноженных на константы может быть получено таким способом. Вы можете подумать, что это полезно только для действительно маленьких констант, но, как вы можете видеть из приведенного выше примера 1020, вы также можете получить несколько удивительно средних. Это оказывается очень удобным при индексации массивов структур, потому что вы должны умножить индекс на размер структуры. Часто при индексации такого массива вы хотите вычислить адрес элемента и получить значение; в этом случае вы можете объединить окончательную инструкцию LEA с инструкцией MOV, чего нельзя сделать с настоящим MUL. Это дает вам дополнительный тактовый цикл (ы) для выполнения MUL по этому типу идиомы.

[Я создал компилятор, который вычисляет "наилучшее умножение на константу", используя эти инструкции, выполняя небольшой исчерпывающий поиск комбинаций команд; затем он кэширует этот ответ для последующего повторного использования].