Comment multiplier un registre par 37 en utilisant seulement 2 instructions de leal consécutives en x86?

Question

Dites% edi contient x et je veux finir avec 37 * x en utilisant seulement 2 instructions de leal consécutives, comment j'y arriverais?

Par exemple, pour obtenir 45x vous feriez

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

Je ne peux pas pour la vie de me comprendre ce que le nombre de mettre en place des 8 et 4, de sorte que le résultat (% eax) sera 37x

Answer 1

At -O3, gcc will emit:

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

    leal (%rdi,%rdi,8), %eax 
    leal (%rdi,%rax,4), %eax 
    ret 

C'est en utilisant 37 = 9*4 + 1

Vous êtes en bonne compagnie en ne notant pas celui-ci, cependant: clang récent utilisera normalement 2 instructions lea au lieu d'un imul (par ex. pour *15), mais il manque celui-ci et utilise:

imull $37, %edi, %eax 
    ret 

Il ne fait *21 avec le même schéma que les usages gcc, comme 5*4 + 1. (Clang3.6 et toujours utilisé plus tôt imul moins qu'il y ait une alternative simple instruction shl ou lea)

CPI et MSVC utilisent également imul, mais ils ne semblent pas aimer à l'aide en utilisant 2 lea instructions, de sorte que le imul est "à dessein" là-bas.

Voir le lien godbolt pour une variété de multiplicateurs avec gcc7.2 vs clang5.0. Il est intéressant d'essayer gcc -m32 -mtune=pentium ou même pentium3 pour voir combien d'instructions supplémentaires gcc voulait utiliser à l'époque. Bien que P2/P3 ait une latence de 4 cycles pour imul r, r, i, c'est un peu fou. Pentium a 9 imul cycle et pas de OOO pour cacher la latence, il est donc logique d'essayer de l'éviter.

mtune=silvermont devrait probablement être prêt à remplacer 32 bits imul avec une seule instruction, car il a une latence/débit de 3 1c cycle de multiplication, mais décodage est souvent le goulot d'étranglement (selon Agner Fog, http://agner.org/optimize/). Vous pouvez même envisager imul $64, %edi, %eax (ou d'autres puissances de 2) au lieu de mov/shl, car imul-immédiat est une copie-et-multiplier.

---

Paradoxalement, gcc manque le x45 cas, et utilise imul, tandis que clang utilise 2 lea s. Supposons qu'il est temps de déposer des rapports de bug d'optimisation manquée. Si 2 leas sont meilleurs que 1 imul, ils devraient être utilisés autant que possible.