Phase 13: Tools & Protocols

Idiomes de compilateur: ce que l'optimisation fait à votre code et comment le lire

Type: Build

Languages: Python, C, x86-64 assembly, AArch64 assembly

Prerequisites: Phase 13 · 33 (disassembly and control flow), Phase 13 · 34 (lifting to pseudocode), Phase 13 · 38 (calling conventions)

Time: ~150 minutes

Objectifs d'apprentissage

• Dérivez le nombre magique et déplacez pour la division par une constante avec la limite Granlund-Montgomery, et récupérez le diviseur des constantes émises par le clang.
• Nombre des cinq façons dont LLVM réduit un switchet lire le nombre d'entrées, l'emplacement de la table et les entrées de l'objet.
• Lisez une boucle vectoriée sous forme de voies, d'accumulateurs, d'éléments par itération, de masque de triple-compte, de réduction et de boucle restante.
• Reconnaître les appels de queue, les appels en ligne, les sélections sans branches et les boucles qui sont devenues memsetou memcpy- Je suis désolé .
• Rapportez chaque langage avec ses instructions de preuve et sa forme source décodée, aux x86-64 et à AArch64, à -O0à travers -O3- Je suis désolé .
• Comparez le résultat avec ce que Ghidra, Angr, radar2, rizin et lldb montrent pour les mêmes octets.

Le problème

Vous avez compiléidioms.cà-O2et a demandé à un agent ce que div7uL'agent a luimulq $0x24924925, %rax, %raxet a répondu que la fonction se multiplie par 613566757, se déplace et ajoute.x / 7- Je suis désolé .

Le même objet contient un switchAvec sept cas qui n'ont pas de saut du tout, un switchavec cinq affaires qui est une table de saut, un switchavec deux cas qui est un seteet une cmovne, et une boucle à travers ndes entiers qui exécutent huit entiers par itération en deux xmmIl est donc possible de faire une analyse de la situation de l'entreprise.-O0la même source produite divl, des tables de saut à sept entrées, et une boucle escalare.-O1Le commutateur à sept cas est devenu un tableau de valeurs et la boucle vectorielle n'existait pas encore.

Ces formes sont des idiomes. Un compilateur émet chacune d'elles à partir d'une règle que vous pouvez lire dans sa source, et chacune peut être décodée à la construction d'où elle vient. Le décoding est arithmétique, et l'arithmétique peut être vérifiée.0x66666667Cette leçon construit le reconnaisseur pour tous, le traite sur 18 versions de notre code, et vérifie les 373 rapports contre la source C.

Un idiome est une forme avec une dérivation

Un idiome est une séquence d'instructions que le compilateur émet pour une construction de source. Trois choses le rendent reconnaissable. Il a une forme fixe, les opérands portent des constantes que la dérivation prédit, et la forme diffère de ce qu'un programmeur écrirait à la main.

Le reconnaisseur en code/main.pyLes travaux sur le texte de llvm-objdump -d -rIl analyse chaque fonction en instructions avec adresse, octets, mnemonique, opérands et la ligne de relocalisation qui la suit. Il lit le fichier objet pour deux choses seulement: les octets de.rodata, où les tableaux de valeurs sont présents, et le .rela.rodatales entrées, où les cibles de la table de saut vivent avant de se connecter.

Chaque détection est uneIdiomenregistrement avec un kind, un décodeur sourceforme, une liste evidenceadresses, une detailLe dictionnaire et unverifiedLe drapeau provient de la source C.parse_source()Il litidioms.c, trouve chaque fonction, et extrait les diviseurs après /et %, les multiplicateurs après *, le switchLes cas et leurs valeurs, les? :Les opérateurs, les forUn langage de division est vérifié lorsque son diviseur est dans la liste de division de la fonction. Une table de recherche est vérifiée lorsque ses entrées correspondent aux valeurs du cas, jusqu'à un facteur constant. Un appel de queue est vérifié lorsque le call est appelé dans la source. Le rapport de démo se termine par un unverifiedla liste, et la suite de tests affirme que la liste est vide pour les 18 constructions.

Le reconnaisseur exécute un petit évaluateur symbolique sur les blocs de base de chaque fonction, dans l'ordre de liste, avec les noms des paramètres de la source dans les registres d'arguments des conventions du système V et AAPCS64 de la leçon 38.-O0Le code se lit à travers ses déversements. À chaque entrée de bloc les états des prédécesseurs sont fusionnés, et où ils diffèrent un nom qu'une idiome antérieure attribuée gagne sur une constante.cmovll %edx, %eaxdans digestIl est écrit:sum % 10 < 5 ? sum % 10 : 5: l' idiome de la boucle nommé l' accumulateur sum, l' idiome de division nomme son quotient sum / 10, et le modulo idiome nommé son résultat sum % 10La source écrit:rem > 5 ? 5 : remLes deux expressions donnent le plus petit de remet 5, et ils sont d'accord à rem == 5- Je suis désolé .

Divisions par une constante

Le rapport Granlund et Montgomery, "Division par intégrales invariables à l'aide de la multiplication" (PLDI 1994), remplace n / dAvec un multiplicateur et un changement.set un multiplicateur m = ceil(2^s / d)- Alors ...floor(n * m / 2^s)égale floor(n / d)pour chaquendans la plage lorsque l'erreur e = m * d - 2^sest assez petit. Pour un non signé 32 bitsnLa limite est e <= 2^(s - 32)Pour les signataires .navec |n| < 2^31La limite est e <= 2^(s - 31), et une correction de signage ajoute 1 quand nest négatif, parce que le sol tourne dans le mauvais sens pour les quotients négatifs.

magic_numbers(d, bits, signed)dans main.pyLes recherches sLa recherche reproduit chaque clang constant émis dans les appareils.

10 non signé à la main

2^35 / 10 = 3435973836.8Le plafond est3435973837 = 0xCCCCCCCDL' erreur est0xCCCCCCCD * 10 - 2^35 = 2, et le bord à s = 35est 2^3 = 8À la .s = 34l'erreur serait 6 contre une limite de 4, donc 35 est le plus petit changement.n = 123Le numéro de la liste:123 * 3435973837 = 422624781951, et 422624781951 >> 35 = 12- Je suis désolé .

Clang émet exactement ça pour div10uà-O2sur x86-64:

textCopy       0: 89 f9                        	movl	%edi, %ecx
       2: b8 cd cc cc cc               	movl	$0xcccccccd, %eax
       7: 48 0f af c1                  	imulq	%rcx, %rax
       b: 48 c1 e8 23                  	shrq	$0x23, %rax

0x23Il est 35.movl %edi, %ecxLe reconnaisseur lit le multiplicateur de la variable movl $immqui nourrit le double-opérand imulq, lit le quart, et appelle divisor_from_magic(0xCCCCCCCD, 35)Cette fonction essaie .2^35 // m = 10et 11, et accepte 10 parce que magic_numbers(10)donne le même multiplicateur et recule.

Sur AArch64 la même fonction est mov w8, #0xcccd; movk w8, #0xcccc, lsl #16; umull x8, w0, w8; lsr x0, x8, #35La constante arrive en deux halves de 16 bits, le multiplicateur est umullLe reconnaisseur rassemble les demi-parties et rapporte le même divisor.

7 non signé à la main, avec la correction additive

2^35 / 7 = 4908534052.57Le plafond est4908534053 = 0x124924925, qui a besoin de 33 bits. L'erreur est 3 contre une limite de 8, donc le changement est 35, et aucun changement plus petit ne fonctionne. Un multiplicateur de 32 bits ne peut pas contenir le multiplicateur, donc le compilateur se multiplie par les 32 bits bas0x24924925et ajoute le dividende dans une séquence fixe:

textCopy      32: 48 69 c0 25 49 92 24         	imulq	$0x24924925, %rax, %rax
      39: 48 c1 e8 20                  	shrq	$0x20, %rax
      3d: 29 c7                        	subl	%eax, %edi
      3f: d1 ef                        	shrl	%edi
      41: 01 f8                        	addl	%edi, %eax
      43: c1 e8 02                     	shrl	$0x2, %eax

Lisez comme t = (n * 0x24924925) >> 32Alors ...q = (((n - t) >> 1) + t) >> 2Le changement total est32 + 1 + 2 = 35Avec n = 100Le numéro de la liste:t = 14- Je suis là .(100 - 14) >> 1 = 43- Je suis là .43 + 14 = 57- Je suis là .57 >> 2 = 14Le reconnaisseur détecte le sub- Je suis là .shr- Je suis là .add- Je suis là .shrla queue après un changement de 32 bits, ajoute 2^32retour au multiplicateur, et récupère 7. evaluate_division()Il est utilisé pour la séquence exacte et le test le vérifie contren // 7Le formulaire AArch64 est sub w9, w0, w8; add w8, w8, w9, lsr #1; lsr w0, w8, #2, une instruction plus courte parce que le déplacé add est une instruction.

Signature 3 à la main

2^32 / 3 = 1431655765.33, plafond 1431655766 = 0x55555556, erreur 2, et la liaison signée à s = 32est 2^1 = 2Le bouton est fermement fermé, donc le quart est 32 et clang utiliseshrq $0x20Avec n = -7: le produit est -10021590362, le changement arithmétique par 32 donne -3, le bit de sign est réglé, donc la fixation ajoute 1 et le résultat est -2, qui est -7 / 3dans C. Les appareils signés div10set div3sIls portent tous les deux la réparation comme shrq $0x3fsur une copie du produit suivie de addl- Je suis désolé .

Ce que les constantes ne sont pas

Le multiplicateur seul ne nomme aucun divisor. 0x66666667Le même multiplicateur avec le changement 33 est 5, comme l'a montré la leçon 34.clangMatchesAlgorithmLes pouvoirs de deux ne font jamais usage du multiplicateur.magic_numbers()les rejette, parce que le compilateur émet un changement avec un biais de signe à la place, et mod8sDans la section suivante, on voit cette forme.

L'idiome appartient au sélecteur d'instructions

À -O0- Je suis là .div10uest movl $0xa, %ecx; xorl %edx, %edx; divl %ecx- Je suis là .div10sest cltd; idivl %ecxDans le même objet,digestdivise sa somme de boucle par 10 avec imulq $0x66666667Un drapeau explique la différence.idioms-x86_64-nofastisel-O0.oa été construit avec -O0 -mllvm -fast-isel=false, et dans chaque division est le multiplicateur, y compris div10uavec movl $0xcccccccd, %ecx; imulq %rcx, %rax; shrq $0x23Le partage matériel est le choix du sélecteur d'instructions rapide à -O0. Le multiplicateur est la diminution de SelectionDAG, ce qui est ce que LLVM UnsignedDivisionByConstantInfoet SignedDivisionByConstantInfoLes produits de ladigestLe bloc qui tient la division tient aussi unswitchLe reconnaisseur rapporte les deux formulaires,hardware idivlet magic multiply, et la figure montre le mélange -O0fonction.

Modulo suit le quotient

x % dest x - (x / d) * dLe compilateur calcule le quotient avec l'idiome ci-dessus, le multiplie et le soustrait.addl %ecx, %ecx; leal (%rcx,%rcx,4), %ecx, qui est 2 * q * 5Sur AArch64, il y a une instruction.msub w0, w8, w9, w0, qui compute w0 - w8 * w9avec w9 = 10. Le reconnaisseur suit le registre des quotients à travers des copies, suit le facteur accumulé à travers add- Je suis là .lea- Je suis là .shl, et imul, et accepte unesublorsque le facteur est égal au divisor.

Lorsque le même quotient donne aussi une autre expression, les deux expressions restent dans le rapport.-O1le compilateur compute sum / 10Une fois dans la vie .digestet l' utilise pour le switchIl est même combiné le quotient 2 fois,leal (%rax,%rsi), %edipour le modulo et addl %esi, %eaxLe reconnaisseur rapporte une division et un module et marque le quotient comme partagé.switchl'indice est illisible.

Le modulo signé par une puissance de deux a sa propre forme, car le quotient n'est jamais calculé:

textCopy      92: 8d 48 07                     	leal	0x7(%rax), %ecx
      95: 85 ff                        	testl	%edi, %edi
      97: 0f 49 cf                     	cmovnsl	%edi, %ecx
      9a: 83 e1 f8                     	andl	$-0x8, %ecx
      9d: 29 c8                        	subl	%ecx, %eax

Pour un négatif xLe code s'écarte de 7 avant de masquer, de sorte que la tranchée tourne vers zéro comme C le demande.xronde à un multiple de 8, et la soustraction laisse x % 8AArch64 le fait avec negs w8, w0; and w9, w0, #0x7; and w8, w8, #0x7; csneg w0, w9, w8, mi: masquer les deux xet -xGhidra appelle sa règle pour cela.RuleSignMod2nOpt, avec le bref "Convertir les formulaires INT_SREM: (V + (sign >> (64-n)) & (2^n-1)) - (sign >> (64-n)) => V s% 2^n" " Je suis là.

À -O0AArch64 écrit modulo comme sdiv w9, w8, w10; mul w9, w9, w10; subs w0, w8, w9Le reconnaisseur accepte également ce formulaire et rapportehardware sdiv + mul + subs- Je suis désolé .

Cinq façons de réduire le bouton

La LVM décide de la forme d' uneswitchDans deux endroits.SimplifyCFG::simplifySwitchLookupIl est à -O1et de plus en plus et fait tourner un interrupteur dont tous les cas produisent des constantes dans une table de valeurs, quand il y a au moins trois cas et que le but peut construire des tables de recherche.SingleValueKind- Je suis là .LinearMapKind- Je suis là .BitMapKind, et ArrayKind- Le .-O0Le pipeline ne passe jamais par ce passage.SwitchLowering::findJumpTablesdans la sélection des instructions, qui crée une table de saut lorsque le cluster a au moins min-jump-table-entriesles entrées, 4 par défaut, et suffisamment denses: NumCases * 100 >= Range * MinDensityavec jump-table-density10 pour les fonctions normales et 40 sous -OsCe qui reste devient une recherche binaire sur les constantes de cas, avec splitWorkItemLes appareils ont une fonction par résultat.

La table de recherche, lue à partir de l'objet

table_switchà-O2- Le numéro de la liste:

textCopy      d0: b8 ff ff ff ff               	movl	$0xffffffff, %eax
      d5: 83 ff 06                     	cmpl	$0x6, %edi
      d8: 77 0c                        	ja	0xe6 <table_switch+0x16>
      da: 89 f8                        	movl	%edi, %eax
      dc: 48 8d 0d 00 00 00 00         	leaq	(%rip), %rcx
		00000000000000df:  R_X86_64_PC32	.rodata+0x24
      e3: 8b 04 81                     	movl	(%rcx,%rax,4), %eax
      e6: c3                           	retq

Les limites sont vérifiées .cmpl $6; jaLe recensement est le plus important.0x24plus les 4 octets du champ relatif à la RIP met la table à .rodata+0x28Les octets sont0a 00 00 00 14 00 00 00 ..., donc les entrées sont [10, 20, 30, 40, 50, 60, 71], et ils sont égaux aux valeurs de cas source..Lswitch.table.table_switchdans le .sfichier, avec un commentaire @switch.table.table_switchIl n'y a pas de saut, donc le graphique de contrôle-flux a trois blocs.

Le formulaire AArch64 met l' adresse du tableau avec adrp x8et add x8, x8, #0x0, chacun portant sa propre relocalisation à .rodata, et chargés de ldr w0, [x8, w0, uxtw #2]Le reconnaisseur lit l' addendum de laadddéménagement.

La carte linéaire, sans table du tout

linear_switchRetour 10 * (k + 1)pour kdans 0 à 6. simplifySwitchLookupdétecte la relation affine et émet l'arithmétique:

textCopy      b0: 83 ff 07                     	cmpl	$0x7, %edi
      b3: 8d 04 bf                     	leal	(%rdi,%rdi,4), %eax
      b6: 8d 4c 00 0a                  	leal	0xa(%rax,%rax), %ecx
      ba: b8 ff ff ff ff               	movl	$0xffffffff, %eax
      bf: 0f 42 c1                     	cmovbl	%ecx, %eax

L' évaluateur lit leal (%rdi,%rdi,4)comme 5*k- Je suis là .leal 0xa(%rax,%rax)comme 10*k + 10, et le cmovbaprès cmpl $7comme k < 7 ? 10*k + 10 : -1Le reconnaisseur vérifie ensuite la formule contre chaque cas source et marque l'idiome vérifié.madd w8, w0, w8, w9et csinv w0, w8, wzr, loOù ?csinvavec wzrrendements -1sur le chemin par défaut.

La table de saut, lue à partir de délocalisations

call_switchà-O2est la leçon de forme 33 récupéré en gradeà-O0Le numéro de la liste:cmpl $4; ja, une leaqà .rodata-0x4, une movslqd'une entrée de 4 octets, addq, et jmpq *%raxLes cinq entrées sont des délocalisations en.rela.rodata, et target = addend - 4kdonne0x10c, 0x107, 0x10e, 0x110, 0x109, cinq blocs distincts qui sautent chacun à travers un pointeur de fonction.dispatchLe fixture étalonne ceci à 16 cas: 16 entrées de relocalisation sur x86-64, et sur AArch64 une table comprimée de 16 octets uniques lues avec ldrb w11, [x9, x8], étalé par 4 avec add x10, x10, x11, lsl #2, et basé sur unadrLe reconnaisseur décode[0x24, 0x74, 0x54, ...]du tableau en octets et des rapports compressed: true- Je suis désolé .

Le même interrupteur à quatre niveaux

digestIl tient un interrupteur allumé .sum / 10Avec les cas 6 à 10 et les valeurs 1, 2, 4, 8, 8, puis multipliez le résultat par 16. sur x86-64 il est une table de saut à -O0, une table de recherche à -O1avec des entrées [16, 32, 64, 128, 128], et une table de saut à nouveau à -O2et -O3dont quatre blocs de coffre sont stockés 0x10- Je suis là .0x20- Je suis là .0x40- Je suis là .0x80- De la .-O1Le taux de multiplication par 16 a augmenté.-O0Les cas stockent 1, 2, 4 et 8, et la multiplication reste après le commutateur.-O1Tableau de recherche le reconnaisseur compare les entrées avec les valeurs de source, trouve un ratio constant et rapporte foldedFactor: 16Sur l' arche 64 , le-O2forme est un arbre de comparaison avec un pivot à 8, tests d'égalité pour 6, 7 et 8, et un test de plage sub w9, w9, #9; cmp w9, #2; b.hsLe reconnaisseur rapporte que les cas 9 et 10 sont couverts par deux instructions.rangeTests: [[9, 10]]- Je suis désolé .

Deux drapeaux déplacent ces frontières.-fno-jump-tablestourne table_switch- Je suis là .call_switch, et le digestPour la fonction de sept cas, il faut passer à des arbres de comparaison sur x86-64, avec des pivots 2 et 4.-mllvm -min-jump-table-entries=4feuillescall_switchEn effet, le nombre d'appels indirects ne désigne pas un nombre de cas de conversion.idioms-arm64-jt4-O2.oDes enregistrements qui fonctionnent.

Le CCG met en œuvre les deux décisions tree-switch-conversion.cc, avec les cours jump_table_cluster- Je suis là .bit_test_cluster- Je suis là .switch_decision_tree, et switch_conversion- C' est ...-ftree-switch-conversionest en train de-O2- Je suis là .-fjump-tableset -fbit-testsà-O1, et le seuil de saut de table vient de case-values-thresholdIl n'y a pas de GCC installé sur cette machine, donc ces noms proviennent de la source et du manuel du GCC, et le compiler Explorer est là où vous les vérifiez.

Boucles: vectoriées, déroulées ou remplacées

Le vectorificateur de boucle de LLVM est allumé à -O2- Je suis là .-O3, et -Os, et de l' éteindre à -O0et -O1, une règle datant de LLVM 3.4 en janvier 2014. sum_nà-O2montre chaque partie de la forme:

textCopy     1f6: 83 fe 07                     	cmpl	$0x7, %esi
     1f9: 77 09                        	ja	0x204 <sum_n+0x14>
     206: 81 e2 f8 ff ff 7f            	andl	$0x7ffffff8, %edx
     230: f3 0f 6f 14 37               	movdqu	(%rdi,%rsi), %xmm2
     235: 66 0f fe c2                  	paddd	%xmm2, %xmm0
     239: f3 0f 6f 54 37 10            	movdqu	0x10(%rdi,%rsi), %xmm2
     23f: 66 0f fe ca                  	paddd	%xmm2, %xmm1
     243: 48 83 c6 20                  	addq	$0x20, %rsi
     24a: 75 e4                        	jne	0x230 <sum_n+0x40>
     24c: 66 0f fe c8                  	paddd	%xmm0, %xmm1
     250: 66 0f 70 c1 ee               	pshufd	$0xee, %xmm1, %xmm0
     262: 66 0f 7e c8                  	movd	%xmm1, %eax
     270: 03 04 97                     	addl	(%rdi,%rdx,4), %eax
     279: 75 f5                        	jne	0x270 <sum_n+0x80>

Le garde .cmpl $7; jaEnvoie le nombre de déplacements inférieur à 8 à la boucle scalaire.andl $0x7ffffff8Les rounds du voyage comptent jusqu'à un multiple de 8. Le corps charge 32 octets par itération en deux.xmmLes accumulateurs, quatre voies de 32 bits chacune, donc le facteur de vectorisation est 4 et le facteur d'interleaving est 2.paddd, deux pshufd, deux autres .paddd, et movdréduire les huit voies à un entier.0x270Le reconnaisseur trouve la boucle depuis son bord arrière, voit les registres SIMD, lit le nombre de voies de paddd, compte des accumulateurs distincts, divise l'étape 0x20par 4, et des rapports 4 lanes x 2 accumulators = 8 elements per iteration, avec le masque, la garde, la réduction et le reste de la boucle comme champs.ldp q2, q3, deux add v.4s- Je suis là .addv s0, v0.4s, et fmov w8, s0- Je suis désolé .

Un nombre fixe de déplacements supprime la boucle. sum4est unmovdqu, la réduction et movd, sans bord arrière. poly8ne peut pas vectorier, parce que chaque itération dépend de l'accumulatrice précédente, donc le compilateur le déroulera huit fois: huit charges à des compensations de 0 à 0x1cde %rdi, suivie de 5 et d' un soustrait qui compte acc * 31. Le reconnaisseur compte les charges à des décompenses consécutives à partir d' une base et rapporte loop unrolled by 8, no back edgeSur l' AArch64 , les mêmes charges arrivent que quatre .ldp- Les deux.

Éteignez le vectorificateur avec -fno-vectorize -fno-slp-vectorizeet sum_ndevient une boucle écalier déroulée par 8, avec huit addl k(%rdi,%rdx,4), %eaxet addq $8, plus une boucle restante. sum4Le reconnaisseur rapporteunrolled loopavec copies: 8et indexStep: 8pour la première fois et copies: 4Pour la seconde fois.

Leçon 33 a trouvé deux bords arrière dans totalà-O2Cette leçon les nomme: un corps vectoriel et un reste escalier de la même boucle source.is_loop()Il y a une question de sécurité.digestsur AArch64 contient des branches arrière vers un bloc par défaut partagé qui ne sont pas des boucles, et la première version du reconnaisseur les a comptées comme des boucles vectorielles.

Les boucles qui deviennent des appels de bibliothèque

LoopIdiomRecognizetransforme une boucle qui stocke zéro dans chaque octet en un appel à memset, à partir de -O1- Je suis en train de monter.fillà-O2est testl %esi, %esi; jle; movl %esi, %edx; xorl %esi, %esi; jmp memset@PLTL' appel est un saut de queue avec le déménagementR_X86_64_PLT32 memset-0x4, et la fonction est retqLe reconnaisseur rapporte que le système est en voie de disparition.store loop recognized as memset(...)et le vérifie contre la boucle source, parce que la source ne nomme jamais memset- Je suis désolé .

copy16Les appelsmemcpyavec une constante 16, et le backend x86 l'agrandit en ligne comme movups (%rsi), %xmm0; movups %xmm0, (%rdi), dans sa limite de 8 magasins parmemcpyÀ la .-O0le même appel est deux 8 octets movqavec -fno-builtinl'appel reste un appel, jmp memcpy@PLTavec movl $0x10, %edx, et fillconserve sa boucle, que le vectorificateur transforme ensuite en une boucle de deux 16 bytes movupsLes rapports du reconnaisseur vectorized store loop: 2 x 16-byte stores = 32 bytes per iterationPour cette construction.

Des appels qui disparaissent ou deviennent des sauts

tail_callerRetour tail_target(x + 1)À la .-O0C' est vrai .addl $0x1, %edi; callq tail_target@PLT; addq $0x10, %rsp; popq %rbp; retqÀ la .-O2C' est vrai .incl %edi; jmp tail_target@PLTLe cadre de l'appelant est parti et l'appelant revient à l'appelant.b tail_targetavec R_AARCH64_JUMP26Le reconnaisseur traite unjmpou bLa descente récursive de la leçon 33 doit la traiter comme une sortie de fonction, car la cible est en dehors de la fonction.

twice_sumLes appelsleaf_addÀ la .-O0L'appel est là.callq leaf_add@PLT- De la .-O1le corps de leaf_add- Je suis là .leal (%rdi,%rsi), %eax, apparaît à l' intérieur twice_sumIl n'y a plus d'appel.-O0Clang marque chaque fonction optnoneet noinlineLe reconnaisseur sait par la source quetwice_sumLes appelsleaf_add, ne trouve pas d'appel ou de saut de queue à elle, et cherche ensuite la forme du corps de l'appelant dans l'appelant: le mnemonique et la source opérands avec la destination enlevée, donc add w8, w1, w0dans les correspondances d' appel d' AArch64 add w0, w1, w0Une correspondance est la preuve.

dispatchcombine les deux: une table de saut à 16 entrées dont chaque cas estmovl %esi, %edi; jmp fN@PLTLe reconnaisseur rapporte un interrupteur et 16 appels de retard, tous vérifiés par rapport aux 16 appels de la source.

Les branches qui sont devenues des données se déplacent

clamp_maxest movl %esi, %eax; cmpl %esi, %edi; cmovgl %edi, %eaxLes noms des évaluateurs%edicomme aet %esicomme b, enregistre la comparaison et lit lacmovgcomme a > b ? a : b, qui est le texte source. abs_intest movl %edi, %eax; negl %eax; cmovsl %edi, %eaxet se lit comme -x < 0 ? x : -x; AArch64 l' écrit comme cmp w0, #0; cneg w0, w0, miet se lit comme x < 0 ? -x : x- Je suis là .is_posest xorl %eax, %eax; testl %edi, %edi; setg %al, qui se lit comme (x > 0)- Ce sont ...-fif-conversionDans les termes du CCG et cmovLa sélection dans les LLVM.X86CmovConversionPasse peut tourner un cmovIl est possible de revenir à des branches quand il juge que rentable, c'est pourquoi la même source peut montrer l'une ou l'autre forme dans une boucle.

À -O0Aucune d'entre elles n'existe. clamp_maxest une comparaison, une jleLe reconnaisseur ne rapporte rien à la poste.-O0et branchless selectde -O1, qui est l'un des faits que le chiffre rend visible.

mul9est unleal (%rdi,%rdi,8), %eax, et les rapports du reconnaisseur strength reductionavec x * 9, parce que la source se multiplie par 9. Il ne le fait que lorsque la source a le facteur; a leaqui équivaut à un index de table n'est pas une multiplication.

Deux caractéristiques durcis qui ressemblent à des idiomes

Le protecteur de pile est une fonctionnalité de compilateur, et il laisse une forme qu'un agent peut autrement lire comme logique de programme. canary.ccompilé avec -fstack-protector-strongpour x86-64 Linux donne:

textCopy       7: 64 48 8b 04 25 28 00 00 00   	movq	%fs:0x28, %rax
      10: 48 89 44 24 40               	movq	%rax, 0x40(%rsp)
      26: 64 48 8b 0c 25 28 00 00 00   	movq	%fs:0x28, %rcx
      2f: 48 3b 4c 24 40               	cmpq	0x40(%rsp), %rcx
      34: 75 05                        	jne	0x3b <with_canary+0x3b>
      3b: e8 00 00 00 00               	callq	0x40 <plain_leaf>
		000000000000003c:  R_X86_64_PLT32	__stack_chk_fail-0x4

%fs:0x28est stack_guarddans le glibc's tcbhead_t, à byte offset 40, et à LLVM getIRStackGuardLe prologue copie la garde au-dessus du tampon, l'épilogue compare et le chemin d'échec appelle__stack_chk_failSur AArch64 Linux , la garde vient du monde entier .__stack_chk_guardpar le GOT avec adrpet ldr, et l' échec est bl __stack_chk_failLe reconnaisseur rapporte la source de garde, la fente, la comparaison et l'appel d'échec.plain_leaf, qui n'a pas de filet, n'a pas de canary sousstrong, qui protège les fonctions avec des matrices,allocaLes notes de recherche enregistrent également le formulaire MSVC sous/GS, un biscuit mélangé avec %rspet vérifiée par __security_check_cookie; il n'existe aucun connecteur MSVC sur cette machine, de sorte que cette forme est décrite uniquement à partir de la sortie de l'assemblage du compilateur.

-fcf-protection=full- Il metendbr64, octets f3 0f 1e faIl s'agit d'une piste d'atterrissage pour les branches indirectes sur les processeurs avec contrôle de débit, et il s'exécute comme unnopLes modèles de démarrage de fonction x86-64 de Ghidra incluent leendbr64variantes préfixes de push rbp; mov rbp, rspLe reconnaisseur le rapporte comme:cet landing pad, donc une fonction qui commence par quatre octets inhabituels ne doit pas être confondue avec des données.

Ce que les décompilateurs déploient

Chaque décompilateur de la leçon 37 utilise certaines de ces dérivées comme règles de réécriture.ruleaction.cc- Je suis là .RuleDivOptest "Convertir INT_MULT et déplacer les formulaires en INT_DIV ou INT_SDIV", avec les formulaires sub( (zext(V)*c), d) >> e => V / (2^n/(c-1)) where n = d*8 + eet la variante signée avec sextet s>>- Je suis là .RuleModOptest "Simplifier les expressions qui optimisent INT_REM et INT_SREM". RuleDivTermAddgère le complément, RuleSignDiv2tourne (V + -1*(V s>> 31)) s>> 1dans V s/ 2, et RulePositiveDivLa leçon 37 a capturé Ghidra 12.1.4 sur la leçon 33's gradeà-O1, et la sortie est uVar2 = param_1 / 10 - 6;La division est détachée.

L'entrée de ces règles est visible sans Java.code/fixtures/idioms-x86_64-O2.lifts.jsondétient le code P brut pour div10s: 112 entrées pour sept instructions, dont 7 sont les instructions IMARKles marqueurs qui ouvrent chaque instruction, parmi eux RAX = RAX * unique[95a00:8]après unique[95a00:8] = sext(0x66666667)- Je suis là .RCX = RCX >> unique[d1a00:4], et RAX = RAX s>> unique[c5c00:4]- Le .shrqIl est chargé de réaliser 41 opérations et desarqIl y en a 40, et la plupart calculent les drapeaux.RuleDivOptcorrespond au multiplicateur et aux deux changements dans ce flux, et l'élimination du code mort supprime les drapeaux que rien ne lit.

Angr 10.0.3 a été lancé sur notre .-O2objet, et idioms-x86_64-O2.angr.jsonIl détient sa sortie de décompiler pour 20 fonctions. Il replie le formulaire non signé: div10uest return a0 / 10;Il ne plie pas le formulaire signé: div10sest v1 = a0 * 1717986919; return ((long long)(v1) >> 0x22) + (v1 >> 63);et mod10sest a0 - (...) * 2 * 5Pour ...div7uIl imprime .(a0 / 7 + ((a0 * 6 / 7 & 0xffffffff) >> 1 & 0xffffffff) & 0xffffffff) >> 2, où les termes de fixation survivent comme l'arithmétique.mul9à a0 * 9- Je suis là .linear_switchà (a0 < 7 ? a0 * 10 + 10 : 0xffffffff)- Je suis là .clamp_maxà ((int)a1 < (int)a0 ? a0 : a1)- Je suis là .is_posà a0 > 0, et fillà return memset(a0, 0, a1);- Il imprime .table_switchcomme une charge .*(int *)(4 * a0 + 4195400)sans les valeurs, sum_navec _mm_add_epi32et _mm_shuffle_epi32Les données de basetail_callercomme tail_target(); return;Le débat a été perdu.digestLa table de saut devient goto *((void *)(...))avec l'arithmétique de la table écrite.

Les radares2 6.2.4 et rizine 0.9.1, intégrés à partir de la source dans le cache de recherche, ont été exécutés sur le même objet.pdcdes empreintesdiv10scomme rax = rax * 0x66666667; rcx >>>= 0x3f; rax >>= 0x22; eax += ecx, pseudo-C au niveau du registre sans pliage, et table_switchcomme eax = dword [rcx + rax*4]avec un RELOC 32 .rodatacommentaire sur le lea. rizin n' a pas de décompilateur intégré; son aoiimprime le RzIL de la imulLldb-1703.0.236.21 charge l'objet ELF et sondisassemble -n div10sIl imprime les mêmes sept instructions que llvm-objdumpCapstone 5.0.7 décode les mêmes octets et rapporte des groupes tels que retet mode64Le code de décoder est un code de décodeur, et un langage n'est jamais dans la sortie d'un décodeur. IDA Pro et Binary Ninja n'ont pas été exécutés ici.

L'Explorateur de compilation est l'outil pour la direction avancée.idioms.c, choisissez une entrée de compilateur telle que "x86-64 clang 18.1.0" ou "ARM64 GCC 14.2.0", et définissez les drapeaux. Le service répertorie environ 1.050 entrées de compilateur C et dispose d'une API: GET /api/compilers/crenvoie les identifiants et POST /api/compiler/<id>/compileL'article ACM Queue de Matt Godbolt de 2019 traverse la division, le décompte de la population, les idiomes conditionnels enchaînés et de somme avec cet outil. Utilisez-le pour la sortie du GCC, que cette machine ne peut pas produire, et comparez les seuils de la table de saut du GCC et -O2vectorisation par défaut du CCG 12 avec la sortie de clang dans les fixtures.

Faites-le

Exécutez la démo:

bashCopycd phases/13-tools-and-protocols/39-compiler-idioms-and-optimization
python3 code/main.py

La sortie est un rapport JSON. Pour chacune des 18 constructions, il énumère chaque fonction et ses idiomes, avec type, forme source, adresses de preuve, vérification et les champs de détails.-O2contre -O3La comparaison des deux architectures et de launverifiedLa liste.

Forme attendue:

jsonCopy{
  "builds": {
    "idioms-x86_64-O2": {
      "arch": "x86_64", "level": "O2", "flags": "x86_64",
      "functions": {
        "div7u": [{"kind": "division", "source": "x / 7", "evidence": ["0x30", "0x32", "0x39", "0x3d", "0x3f", "0x41", "0x43"], "verified": true, "form": "magic multiply with add fix-up", "magic": "0x24924925", "effectiveMagic": "0x124924925", "shift": 35, "...": "..."}],
        "table_switch": [{"kind": "switch", "source": "switch (k) as lookup table", "table": ".rodata+0x28", "entries": 7, "values": [10, 20, 30, 40, 50, 60, 71], "...": "..."}],
        "sum_n": [{"kind": "vector loop", "lanes": 4, "accumulators": 2, "elementsPerIteration": 8, "...": "..."}]
      }
    }
  },
  "kindMatrix": {"idioms-x86_64-O2": {"division": 5, "modulo": 3, "switch": 6, "vector loop": 3, "...": "..."}},
  "sameCodeAtO2AndO3": {"x86_64": {"identical": true}, "arm64": {"identical": false, "differences": ["..."]}},
  "unverified": []
}

Lire code/main.pydans cet ordre:

1. parse_listing()tourne le llvm-objdump -d -rLes deux architectures doivent être intégrées à des fonctions, à des instructions et à des rélocalisations jointes.
2. ElfFileIl lit des sections, des symboles et .rela.*les entrées, et words()Il lit les entrées de table.
3. magic_numbers()- Je suis là .divisor_from_magic(), et evaluate_division()sont la dérivation Granlund-Montgomery vers l'avant, vers l'arrière, et comme la séquence d'instructions.
4. parse_source()extrait les constructions des besoins de vérification du dossier C.
5. Evaluatorest le bloc par bloc symbolique qui enregistrent les noms et les emplacements.
6. find_divisions()et find_modulos()correspondent au multiplication, au changement, au fixement, au multiplication et au pouvoir de deux formes.
7. find_switches()classe les tables de saut, les tables de recherche, les cartes linéaires, sélectionne les chaînes, compare les arbres et compare les chaînes.
8. find_vector_loops()- Je suis là .find_unrolled_loops()- Je suis là .find_tail_calls()- Je suis là .find_inlined_calls()- Je suis là .find_selects()- Je suis là .find_memory_builtins()- Je suis là .find_stack_protector()- Je suis là .find_cet(), et find_strength_reduction()Couvre le reste.
9. analyze_function()les organise dans l'ordre, en introduisant le nom du résultat de chaque idiome dans le prochain passe d'évaluation.

Il y a trois commandes de plus.python3 code/main.py scan FILE.objdump.txt [FUNCTION]Il utilise le reconnaisseur sur une liste, avec l'objet et le fichier C correspondant à côté. python3 code/main.py magic DIVISOR [signed]imprime le multiplicateur, le déplacement, l'erreur et si l'identité tient les valeurs de bord. python3 code/main.py figure-dataimprime les données que la figure intègre.

Utilisez-le

Utilisez le reconnaisseur dans cet ordre sur un nouvel objet que vous avez construit.

1. Capture llvm-objdump -d -rLe reconnaisseur lit l'architecture de l'en-tête de liste.
2. On court .scansur la liste et lire le unverifiedChacun est soit une construction que le parseur source n'a pas vue, soit une forme que le reconnaisseur a mal lue, et les deux méritent d'être examinés.
3. Pour chaque division, lisez lealgorithmLe champ.clangMatchesAlgorithmSi c'est faux, le compilateur a eu une raison que vous ne connaissez pas encore; écrivez les constantes.
4. Pour chaque commutateur, comparez le loweringUne table qui devient un arbre, ou un arbre qui devient une table, marque un seuil que vous pouvez nommer à partir de la source LLVM.
5. Pour chaque boucle, lisez elementsPerIterationet scalarRemainderLoop, puis confirmez que les deux doses de leçon 33 rapports sont une boucle source.
6. Exécutez un décompilateur sur le même objet, citez son texte à côté de chaque idiome, et enregistrez les autres.

Laboratoire interactif

Laboratoire A: déduire un nombre magique, puis le trouver

De la coderépertoire, ouverture Python:

bashCopycd phases/13-tools-and-protocols/39-compiler-idioms-and-optimization/code
python3 -q

Je vais courir .

pythonCopyfrom main import *
magic_numbers(10), magic_numbers(10, signed=True)
magic_numbers(7), magic_numbers(7, signed=True)
divisor_from_magic(0x66666667, 34, signed=True), divisor_from_magic(0x66666667, 33, signed=True)

Compte ceil(2^35 / 10)sur le papier avant le premier appel.unsigned div13(unsigned x) { return x / 13; }à une copie de idioms.c, construire à -O2avec le commandement en build_fixtures.sh, et vérifier la constante dans la liste contre magic_numbers(13)- Je suis désolé .

Laboratoire B: la table et l'arbre

pythonCopylisting = load_listing("idioms-x86_64-O2.objdump.txt")
elf = load_elf("idioms-x86_64-O2.o")
sources = load_source("idioms.c")
[i.to_dict() for i in analyze_function(listing, "table_switch", elf, sources)]
[i.to_dict() for i in analyze_function(listing, "sparse_switch", elf, sources)]
elf.words(".rodata", 0x28, 7)

Le changement71Retour à 70dans une copie de table_switch, reconstruire à-O2, et regarder la table de recherche devient une carte linéaire. Puis changer une valeur de cas à 1000 et regarder rester uneArrayKindLa table.

Laboratoire C: la boucle à trois réglages

pythonCopyfor name in ("idioms-x86_64-O1", "idioms-x86_64-O2", "idioms-x86_64-novec-O2"):
    print(name, [i.source for i in analyze_function(load_listing(name + ".objdump.txt"), "sum_n", load_elf(name + ".o"), sources)])

Dessinez le graphique de contrôle des flux de sum_nà-O2à la main, marquer le garde, le masque, le corps vectoriel, la réduction et le reste de la boucle, et comparer avec le detailles champs.

Laboratoire D: le quotient partagé

pythonCopyfor name in ("idioms-x86_64-O1", "idioms-arm64-O1"):
    print([(i.kind, i.source, i.detail.get("sharedQuotient")) for i in analyze_function(load_listing(name + ".objdump.txt"), "digest", load_elf(name + ".o"), sources)])

Lisez le -O1liste des digestet trouver les deux instructions qui combinent le quotient avec son signe fixation sur x86-64.

Laboratoire de pratique

Ajoutez des trucs à la lumière et étendons le reconnaisseur.

Les exigences:

• Écrivezpopcount- Je suis là .ctz, et rotlLes fonctionnalités de la construction du CCG et de la rotation de la position de la-O2avec et sans-mpopcnt -mbmi, et engager les objets avec leurs listes.
• Reconnaissez le0x55555555- Je suis là .0x33333333- Je suis là .0x0f0f0f0f- Je suis là .0x01010101séquence de dénombrement de la population qui TargetLowering::expandCTPOPémet et le rapporte comme popcountavec les quatre constantes comme preuve.
• Reconnaîtrerep bsflcomme le tzcnt- ou...bsfla codage et roll %clcomme le rotation, et décodez les deux à la construction.
• Ajoutez les nouveaux types à parse_source()la vérification, donc une popcountL' idiome n' est vérifié que lorsque la source appelle __builtin_popcount- Je suis désolé .
• Ajoutez un test par idiome qui lit les constantes de la liste des fichiers.

Le succès signifiepython3 code/main.pyrapporte les trois nouveaux types avec verified: trueDans les deux constructions, et la suite rapporte toujours un vide unverifiedLa liste.

Leçon d'artisanat

Cette leçon comprend outputs/skill-compiler-idioms-and-optimization.md. Utilisez-le pour transformer une liste, un objet et sa source en un rapport de langue vérifié avec une comparaison de décompilés. Il nécessite des adresses de preuve pour chaque revendication, la dérivée du nombre magique pour chaque division, le type de réduction et la source d'entrée pour chaque commutateur, et une ligne de décompilés citée pour chaque langue.

Vérifiez

Exécutez la démo et la suite déterministe:

bashCopycd phases/13-tools-and-protocols/39-compiler-idioms-and-optimization
python3 code/main.py
python3 -m unittest discover -s code/tests -v

La vérification doit prouver:

• Le parseur de liste lit 25 fonctions de la -O2Objet, conserve les octets, et attache R_X86_64_PC32 .rodata+0x24à la leaqdans table_switch
• le lecteur ELF retourne [10, 20, 30, 40, 50, 60, 71]de .rodata+0x28et dix délocalisations en .rela.rodata
• magic_numbersRetour 0xcccccccdavec la troisième,0x66666667avec 34, 0x124924925avec 35 et le formulaire additif, 0x55555556avec 32, et 0xaaaaaaabavec 33
• l'identité tient les valeurs de bord de 32 bits pour chaque divisor de 2 à 64 qui n'est pas une puissance de deux, signée et non signée
• divisor_from_magicrécupère 10, 5, 7 et 3 de leurs paires et rejette une mauvaise paire
• le calcul de la séquence de fixation additive n // 7exactement
• Les quatre divisions x86-64 indiquent le multiplicateur droit, le changement, le diviseur et la forme, et les quatre divisions AArch64 décodent movet movk
• -O0utilisations divlet idivl- Je suis là .-O0 -fast-isel=falseutilise le multiplicateur, et digestà-O0mélange les deux
• le modulo est reconnu comme un retour multiplicateur,msub, puissance à deux, sdivplus mulplus subs, et le matériel idivl
• Un quotient partagé maintient à la fois la division et le modulo à -O1
• Les cinq réductions sont classées en -O2sur les deux architectures, avec la formule, les valeurs, les objectifs, les pivots et l'expression sélectionnée
• -O0Les commutateurs sont des tables de saut sur x86-64 et comparer les chaînes sur AArch64
• le digestLe commutateur est une table de saut, puis une table de recherche avec le facteur 16 plié, puis une table de saut avec quatre cibles distinctes sur x86-64, et un arbre de comparaison avec le test d'intervalle 9 à 10 sur AArch64
• -fno-jump-tablesproduit des arbres de comparaison, et le cas 16 dispatchlisent ses objectifs à partir de délocalisations sur x86-64 et d'un tableau en octets comprimés sur AArch64
• le boucle vectorielle rapporte 4 voies, 2 accumulateurs, 8 éléments par itération, le masque, la garde, la réduction et le boucle restant
• Les boucles à trajet fixe sont entièrement vectoriées ou entièrement déroulées, et -fno-vectorizedéroulées à 8
• -O1n'a pas de vectorisation, -O2et -O3sont identiques sur x86-64, et sur AArch64 ils diffèrent seulement en call_switchOù ?-O3Il contient 17 instructions et -O2a 18
• -fno-builtintransforme la boucle de magasin en boucle de magasin vectoriée et garde memcpyun appel
• Les appels de la queue, le memsetle remplacement, la copie en ligne de 16 octets, et le -O0les copies à deux mouvements sont reconnues
• La callee en ligne est trouvée à partir de -O1par sa forme corporelle
• sélectionne le décode à a > b ? a : b- Je suis là .-x < 0 ? x : -x- Je suis là .(x > 0), et sum % 10 < 5 ? sum % 10 : 5
• le rapport de protection de pile %fs:0x28, la fente, et __stack_chk_fail, et endbr64est déclaré sur chaque fonction de la structure du CET
• le parseur source lit les paramètres du pointeur de fonction, les cas de commutateur, les appels et les noms de l'accumulateur
• chaque idiome dans chaque construction est vérifié et les matrices de type correspondent
• la figure interactive intègre les mêmes données que l'analyse produit

Mode de défaillance de la production

Règlement d'exploitation

Partagez la forme, faites revenir la dérivée et écrivez les constantes qui la prouvent. Rapportez chaque idiome avec ses adresses de preuve et sa forme source décodée, vérifiez chacun contre la source que vous avez compilée, et citons ce que chaque décompilateur a imprimé pour les mêmes octets.

Pour en savoir plus

• Granlund, Montgomery, "Division by Invariant Integers using Multiplication" (PLDI 1994)
• Warren, Hacker's Delight, 2nd edition, Chapter 10: Integer Division By Constants
• Lemire, Kaser, Kurz, "Faster Remainder by Direct Computation" (2019)
• libdivide, header-only division by runtime constants
• LLVM DivisionByConstantInfo.cpp
• LLVM SwitchLoweringUtils.cppet TargetLoweringBase.cpp
• LLVM SimplifyCFG.cpp, simplifySwitchLookup
• LLVM Auto-Vectorization documentationet LLVM 3.4 release notes
• LLVM LoopIdiomRecognize.cpp
• LLVM X86CmovConversion.cpp
• LLVM StackProtector.cppet X86ISelLoweringCall.cpp, getIRStackGuard
• glibc sysdeps/x86_64/nptl/tls.h, tcbhead_t
• GCC tree-switch-conversion.cc- Je suis là .GCC Optimize Options, et GCC 12 release notes
• Ghidra decompiler ruleaction.cc
• angr decompiler documentation
• radare2 book: decompilers
• Compiler Explorer API
• Godbolt, "Optimizations in C++ Compilers: A practical journey", ACM Queue 17(5), 2019
• Microsoft, /GS (Buffer Security Check)

This free lesson is part of the AI Engineering from Scratch curriculum. Read the full explanation, run the lesson code, and verify the result in the interactive reader or from the repository source.

Browse the complete course catalog or open this lesson on GitHub.