Как умножить регистр на 37, используя только две последовательные инструкции в x86?

Question

Скажем,%edi содержит x, и я хочу получить 37*x, используя только 2 последовательные инструкции по обучению, как бы мне поступить?

Например, чтобы получить 45x вы бы сделали

leal (%edi, %edi, 8), %edi   
leal (%edi, %edi, 4), %eax (to be returned)

Я не могу на всю жизнь выяснить, какие числа поставить вместо 8 и 4, чтобы результат (%eax) был 37x

Answer 1

В -O3 , GCC будет излучать (проводник компилятора Godbolt):

int mul37(int a)  { return a*37; }

    leal    (%rdi,%rdi,8), %eax      # eax = a * 9
    leal    (%rdi,%rax,4), %eax      # eax = a + 4*(a*9)
    ret

Это с помощью 37 = 9*4 + 1, не уничтожая оригинал a значение с первым lea так что можно использовать как во 2-м.

Вы в хорошей компании, не заметив этого, хотя: недавний clang (3.8 и новее) будет обычно использовать 2 lea инструкции вместо imul (например, для *15), но он пропускает этот и использует:

    imull   $37, %edi, %eax
    ret

Это делает *21 с тем же шаблоном, который использует gcc, как 5*4 + 1, (clang3.6 и ранее всегда используется imul если не было альтернативы одной инструкции shl или же lea)

ICC и MSVC также используют imul, но им не нравится использовать 2 lea инструкции, поэтому imul "намеренно" там.

См. Ссылку на Godbolt для различных множителей с gcc7.2 против clang5.0. Интересно попробовать gcc -m32 -mtune=pentium или даже pentium3 чтобы увидеть, сколько еще инструкций собирался использовать gcc тогда. Хотя P2/P3 имеет 4-тактную задержку для imul r, r, i так что это довольно безумно Pentium имеет 9 цикла imul и нет ООО, чтобы скрыть задержку, поэтому имеет смысл постараться избежать этого.

mtune=silvermont вероятно, стоит только заменить 32-битный imul с одной инструкцией, потому что она имеет умножение задержки на 3 цикла / 1c, но декодирование часто является узким местом (согласно Agner Fog, http://agner.org/optimize/). Вы могли бы даже рассмотреть imul $64, %edi, %eax (или другие полномочия 2) вместо mov / shl потому что imul-немедленное является копией и умножением.

---

Как ни странно, gcc пропускает * 45 случай, и использует imul в то время как лязг использует 2 lea s. Похоже, пришло время подать несколько отчетов об ошибках при пропущенной оптимизации. Если 2 LEA лучше, чем 1 IMUL, их следует использовать везде, где это возможно.

Более старый Clang (3.7 и старше) использует imul если только один lea сделает свое дело. Я не просматривал журнал изменений, чтобы увидеть, сделали ли они тесты, чтобы решить, предпочитают ли задержки пропускную способность.

---

Связанный: Использование LEA на значениях, которые не являются адресами / указателями? канонический ответ о том, почему LEA использует синтаксис операндов памяти и машинное кодирование, даже если это инструкция shift+add (и выполняется в ALU, а не AGU в большинстве современных микроархитектур).