Comment l'entier 128 bits `i128` de Rust fonctionne-t-il sur un système 64 bits?

128

Rust a des entiers de 128 bits, ceux-ci sont indiqués avec le type de données i128(et u128pour les entiers non signés):

let a: i128 = 170141183460469231731687303715884105727;

Comment Rust fait fonctionner ces i128valeurs sur un système 64 bits; par exemple, comment fait-il de l'arithmétique sur ces derniers?

Puisque, pour autant que je sache, la valeur ne peut pas tenir dans un registre d'un processeur x86-64, le compilateur utilise-t-il en quelque sorte 2 registres pour une i128valeur? Ou utilisent-ils plutôt une sorte de grande structure entière pour les représenter?

rouohola
la source
54
Comment fonctionne un entier à deux chiffres lorsque vous n'avez que 10 doigts?
Jörg W Mittag
27
@JorgWMittag: Ah - le vieux stratagème "numéro à deux chiffres avec seulement dix doigts". Heh-heh. Je pensais que tu pouvais me tromper avec cette vieille, hein? Eh bien, mon ami, comme n'importe quel élève de deuxième année pourrait vous le dire, c'est à ça que servent les orteils! ( Avec des excuses abjectes à Peter Sellers ... et Lady Lytton :-)
Bob Jarvis - Réintègre Monica
1
FWIW la plupart des machines x86 ont des registres spéciaux de 128 bits ou plus pour les opérations SIMD. Voir en.wikipedia.org/wiki/Streaming_SIMD_Extensions Edit: J'ai en quelque sorte manqué le commentaire de @ eckes
Ryan1729
4
@ JörgWMittag Nah, les informaticiens comptent en binaire en abaissant ou en étendant les doigts individuels. Et maintenant, 132 vous tous, je rentre à la maison ;-D
Marco13

Réponses:

141

Tous les types entiers de Rust sont compilés en entiers LLVM . La machine abstraite LLVM autorise les entiers de n'importe quelle largeur de bits de 1 à 2 ^ 23 - 1. * Les instructions LLVM fonctionnent généralement sur des entiers de n'importe quelle taille.

De toute évidence, il n'y a pas beaucoup d'architectures 8388607 bits, donc lorsque le code est compilé en code machine natif, LLVM doit décider comment l'implémenter. La sémantique d'une instruction abstraite comme addest définie par LLVM lui-même. En règle générale, les instructions abstraites qui ont un équivalent à instruction unique dans le code natif seront compilées dans cette instruction native, tandis que celles qui ne le sont pas seront émulées, éventuellement avec plusieurs instructions natives. La réponse de mcarton montre comment LLVM compile les instructions natives et émulées.

(Cela ne s'applique pas seulement aux entiers qui sont plus grands que la machine native ne peut prendre en charge, mais aussi à ceux qui sont plus petits. Par exemple, les architectures modernes peuvent ne pas prendre en charge l'arithmétique native 8 bits, donc une addinstruction sur deux i8s peut être émulée avec une instruction plus large, les bits supplémentaires sont supprimés.)

Le compilateur utilise-t-il en quelque sorte 2 registres pour une i128valeur? Ou utilisent-ils une sorte de grande structure entière pour les représenter?

Au niveau de LLVM IR, la réponse n'est ni l'un ni l'autre: i128s'inscrit dans un seul registre, comme tout autre type à valeur unique . D'un autre côté, une fois traduit en code machine, il n'y a pas vraiment de différence entre les deux, car les structures peuvent être décomposées en registres comme des entiers. Lorsque vous faites de l'arithmétique, cependant, il y a fort à parier que LLVM chargera simplement le tout dans deux registres.


* Cependant, tous les backends LLVM ne sont pas créés égaux. Cette réponse concerne x86-64. Je comprends que le support backend pour les tailles supérieures à 128 et les non-puissances de deux est irrégulier (ce qui peut expliquer en partie pourquoi Rust n'expose que des entiers de 8, 16, 32, 64 et 128 bits). Selon est31 sur Reddit , rustc implémente des entiers de 128 bits dans le logiciel lorsqu'il cible un backend qui ne les prend pas en charge nativement.

trentcl
la source
1
Euh, je me demande pourquoi c'est 2 ^ 23 au lieu du 2 ^ 32 plus typique (enfin, en termes généraux en termes de fréquence d'apparition de ces nombres, pas en termes de largeurs de bits maximales d'entiers pris en charge par les backends du compilateur ...)
Fond Le procès de Monica
26
@NicHartley Certaines des classes de base de LLVM ont un champ dans lequel les sous-classes peuvent stocker des données. Pour la Typeclasse, cela signifie qu'il y a 8 bits pour stocker le type de type (fonction, bloc, entier, ...) et 24 bits pour les données de sous-classe. La IntegerTypeclasse utilise ensuite ces 24 bits pour stocker la taille, ce qui permet aux instances de s'adapter parfaitement à 32 bits!
Todd Sewell
56

Le compilateur les stockera dans plusieurs registres et utilisera plusieurs instructions pour faire de l'arithmétique sur ces valeurs si nécessaire. La plupart des ISA ont une instruction add-with-carry comme celle de x86,adc ce qui rend assez efficace pour faire des add / sub entiers de précision étendue.

Par exemple, étant donné

fn main() {
    let a = 42u128;
    let b = a + 1337;
}

le compilateur génère les éléments suivants lors de la compilation pour x86-64 sans optimisation:
(commentaires ajoutés par @PeterCordes)

playground::main:
    sub rsp, 56
    mov qword ptr [rsp + 32], 0
    mov qword ptr [rsp + 24], 42         # store 128-bit 0:42 on the stack
                                         # little-endian = low half at lower address

    mov rax, qword ptr [rsp + 24]
    mov rcx, qword ptr [rsp + 32]        # reload it to registers

    add rax, 1337                        # add 1337 to the low half
    adc rcx, 0                           # propagate carry to the high half. 1337u128 >> 64 = 0

    setb    dl                           # save carry-out (setb is an alias for setc)
    mov rsi, rax
    test    dl, 1                        # check carry-out (to detect overflow)
    mov qword ptr [rsp + 16], rax        # store the low half result
    mov qword ptr [rsp + 8], rsi         # store another copy of the low half
    mov qword ptr [rsp], rcx             # store the high half
                             # These are temporary copies of the halves; probably the high half at lower address isn't intentional
    jne .LBB8_2                       # jump if 128-bit add overflowed (to another not-shown block of code after the ret, I think)

    mov rax, qword ptr [rsp + 16]
    mov qword ptr [rsp + 40], rax     # copy low half to RSP+40
    mov rcx, qword ptr [rsp]
    mov qword ptr [rsp + 48], rcx     # copy high half to RSP+48
                  # This is the actual b, in normal little-endian order, forming a u128 at RSP+40
    add rsp, 56
    ret                               # with retval in EAX/RAX = low half result

où vous pouvez voir que la valeur 42est stockée dans raxet rcx.

(Note de l'éditeur: les conventions d'appel x86-64 C renvoient des entiers de 128 bits dans RDX: RAX. Mais cela mainne renvoie pas du tout de valeur. Toute la copie redondante provient uniquement de la désactivation de l'optimisation, et que Rust vérifie en fait le dépassement de capacité lors du débogage mode.)

À titre de comparaison, voici l'asm pour les entiers Rust 64 bits sur x86-64 où aucun ajout avec report n'est nécessaire, juste un seul registre ou emplacement de pile pour chaque valeur.

playground::main:
    sub rsp, 24
    mov qword ptr [rsp + 8], 42           # store
    mov rax, qword ptr [rsp + 8]          # reload
    add rax, 1337                         # add
    setb    cl
    test    cl, 1                         # check for carry-out (overflow)
    mov qword ptr [rsp], rax              # store the result
    jne .LBB8_2                           # branch on non-zero carry-out

    mov rax, qword ptr [rsp]              # reload the result
    mov qword ptr [rsp + 16], rax         # and copy it (to b)
    add rsp, 24
    ret

.LBB8_2:
    call panic function because of integer overflow

Le setb / test est toujours totalement redondant: jc(sauter si CF = 1) fonctionnerait très bien.

Avec l'optimisation activée, le compilateur Rust ne vérifie pas le dépassement de capacité et +fonctionne donc comme .wrapping_add().

mcarton
la source
4
@Anush Non, rax / rsp / ... sont des registres 64 bits. Chaque nombre de 128 bits est stocké dans deux registres / emplacements de mémoire, ce qui entraîne les deux ajouts de 64 bits.
ManfP
5
@Anush: non, il utilise juste tellement d'instructions car il est compilé avec l'optimisation désactivée. Vous verriez du code beaucoup plus simple (comme simplement add / adc) si vous compiliez une fonction qui prenait deux u128arguments et renvoyait une valeur (comme celle-ci godbolt.org/z/6JBza0 ), au lieu de désactiver l'optimisation pour empêcher le compilateur de faire propagation constante sur les arguments à constante de compilation.
Peter Cordes
3
@ Le mode de sortie CAD97 utilise l' arithmétique d'emballage mais ne vérifie pas le débordement et la panique comme le fait le mode débogage. Ce comportement a été défini par la RFC 560 . Ce n'est pas UB.
trentcl
3
@PeterCordes: Plus précisément, Rust le langage spécifie que le débordement n'est pas spécifié, et rustc (le seul compilateur) spécifie deux comportements au choix: Panic ou Wrap. Idéalement, Panic serait utilisé par défaut. En pratique, en raison d'une génération de code sous-optimale, en mode Release, la valeur par défaut est Wrap, et un objectif à long terme est de passer à Panic lorsque (le cas échéant) la génération de code est «assez bonne» pour une utilisation grand public. De plus, tous les types d'intégrale de Rust prennent en charge les opérations nommées pour choisir un comportement: coché, enveloppant, saturant, ... afin que vous puissiez remplacer le comportement sélectionné par opération.
Matthieu M.
1
@MatthieuM .: Oui, j'adore les méthodes wrapping vs checked vs saturating add / sub / shift / any sur les types primitifs. Tellement mieux que l'emballage non signé de C, UB signé vous obligeant à choisir en fonction de cela. Quoi qu'il en soit, certains ISA pourraient fournir un support efficace pour Panic, par exemple un drapeau collant que vous pouvez vérifier après toute une séquence d'opérations. (Contrairement à OF ou CF de x86 qui sont écrasés par 0 ou 1.) Par exemple, le ForwardCom ISA proposé par Agner Fog ( agner.org/optimize/blog/read.php?i=421#478 ) Mais cela contraint toujours l'optimisation à ne jamais faire de calcul la source Rust n'a pas fait. : /
Peter Cordes
30

Oui, tout comme les entiers 64 bits sur les machines 32 bits ont été traités, ou les entiers 32 bits sur les machines 16 bits, ou même les entiers 16 et 32 ​​bits sur les machines 8 bits (toujours applicable aux microcontrôleurs! ). Oui, vous stockez le numéro dans deux registres, ou emplacements de mémoire, ou autre chose (cela n'a pas vraiment d'importance). L'addition et la soustraction sont triviales, prenant deux instructions et utilisant le drapeau de retenue. La multiplication nécessite trois multiplications et quelques ajouts (il est courant pour les puces 64 bits d'avoir déjà une opération de multiplication 64x64-> 128 qui sort sur deux registres). La division ... nécessite un sous-programme et est assez lente (sauf dans certains cas où la division par une constante peut être transformée en décalage ou en multiplication), mais cela fonctionne toujours. Bitwise et / ou / xor doivent simplement être effectués séparément sur les moitiés supérieure et inférieure. Les décalages peuvent être accomplis par rotation et masquage. Et cela couvre à peu près les choses.

Hobbs
la source
26

Pour fournir peut-être un exemple plus clair, sur x86_64, compilé avec l' -Oindicateur, la fonction

pub fn leet(a : i128) -> i128 {
    a + 1337
}

compile en

example::leet:
  mov rdx, rsi
  mov rax, rdi
  add rax, 1337
  adc rdx, 0
  ret

(Mon message d'origine avait u128plutôt que ce que i128vous avez demandé. La fonction compile le même code dans les deux cas, une bonne démonstration que l'ajout signé et non signé est le même sur un processeur moderne.)

L'autre liste a produit du code non optimisé. Il est sûr d'intervenir dans un débogueur, car cela garantit que vous pouvez placer un point d'arrêt n'importe où et inspecter l'état de n'importe quelle variable sur n'importe quelle ligne du programme. C'est plus lent et plus difficile à lire. La version optimisée est beaucoup plus proche du code qui fonctionnera réellement en production.

Le paramètre ade cette fonction est passé dans une paire de registres 64 bits, rsi: rdi. Le résultat est renvoyé dans une autre paire de registres, rdx: rax. Les deux premières lignes de code initialisent la somme à a.

La troisième ligne ajoute 1337 au mot bas de l'entrée. Si cela déborde, il porte le 1 dans le drapeau de retenue du CPU. La quatrième ligne ajoute zéro au mot haut de l'entrée, plus le 1 s'il a été porté.

Vous pouvez considérer cela comme une simple addition d'un nombre à un chiffre à un nombre à deux chiffres

  a  b
+ 0  7
______
 

mais en base 18 446 744 073 709 551 616. Vous ajoutez toujours le «chiffre» le plus bas en premier, en portant éventuellement un 1 à la colonne suivante, puis en ajoutant le chiffre suivant plus le report. La soustraction est très similaire.

La multiplication doit utiliser l'identité (2⁶⁴a + b) (2⁶⁴c + d) = 2¹²⁸ac + 2⁶⁴ (ad + bc) + bd, où chacune de ces multiplications renvoie la moitié supérieure du produit dans un registre et la moitié inférieure du produit dans un autre. Certains de ces termes seront supprimés, car les bits au-dessus du 128e ne rentrent pas dans a u128et sont supprimés. Même ainsi, cela nécessite un certain nombre d'instructions de la machine. La division prend également plusieurs étapes. Pour une valeur signée, la multiplication et la division auraient en outre besoin de convertir les signes des opérandes et le résultat. Ces opérations ne sont pas du tout très efficaces.

Sur d'autres architectures, cela devient plus facile ou plus difficile. RISC-V définit une extension de jeu d'instructions de 128 bits, bien qu'à ma connaissance personne ne l'ait implémentée en silicium. Sans cette extension, le manuel d'architecture RISC-V recommande une branche conditionnelle:addi t0, t1, +imm; blt t0, t1, overflow

SPARC a des codes de contrôle comme les indicateurs de contrôle de x86, mais vous devez utiliser une instruction spéciale,, add,ccpour les définir. MIPS, d'autre part, vous oblige à vérifier si la somme de deux entiers non signés est strictement inférieure à l'un des opérandes. Si tel est le cas, l'addition a débordé. Au moins, vous pouvez définir un autre registre à la valeur du bit de retenue sans branche conditionnelle.

Davislor
la source
1
dernier paragraphe: Pour détecter lequel des deux nombres non signés est le plus grand en regardant le bit haut d'un subrésultat, vous avez besoin d'un n+1sous-résultat de nbit pour les entrées de bit. c'est-à-dire que vous devez regarder le report, pas le bit de signe du résultat de même largeur. C'est pourquoi les conditions de branchement non signées x86 sont basées sur CF (bit 64 ou 32 du résultat logique complet), et non sur SF (bit 63 ou 31).
Peter Cordes
1
L'approche de re: divmod: AArch64 est de fournir une division et une instruction qui fait un entier x - (a*b), en calculant le reste à partir du dividende, du quotient et du diviseur. (Cela est utile même pour les diviseurs constants utilisant un inverse multiplicatif pour la partie de division). Je n'avais pas lu les ISA qui fusionnent les instructions div + mod en une seule opération divmod; c'est chouette.
Peter Cordes
1
re: flags: oui, une sortie d'indicateur est une 2ème sortie que OoO exec + register-renaming doit gérer d'une manière ou d'une autre. Les processeurs x86 le gèrent en conservant quelques bits supplémentaires avec le résultat entier sur lequel la valeur FLAGS est basée, donc probablement ZF, SF et PF sont générés à la volée en cas de besoin. Je pense qu'il y a un brevet Intel à ce sujet. Cela réduit le nombre de sorties qui doivent être suivies séparément à 1. (Dans les processeurs Intel, aucun uop ne peut jamais écrire plus d'un registre entier; par exemple, mul r642 uops, le deuxième écrivant la moitié haute du RDX).
Peter Cordes
1
Mais pour une précision étendue efficace, les drapeaux sont très bons. Le problème principal est l' absence de changement de nom de registre pour une exécution dans l'ordre superscalaire. les drapeaux sont un danger WAW (écriture après écriture). Bien sûr, les instructions d'ajout avec report sont à 3 entrées, et c'est également un problème important à suivre. Intel avant Broadwell décodé adc, sbbet cmovà 2 uops chacun. (Haswell a introduit des uops à 3 entrées pour FMA, Broadwell a étendu cela à un entier.)
Peter Cordes
1
Les ISA RISC avec des indicateurs rendent généralement la définition des indicateurs facultative, contrôlée par un bit supplémentaire. par exemple ARM et SPARC sont comme ça. PowerPC, comme d'habitude, rend tout plus compliqué: il a 8 registres de code de condition (regroupés dans un registre 32 bits pour sauvegarde / restauration) afin que vous puissiez comparer en cc0 ou en cc7 ou autre. Et puis les codes de condition ET ou OU ensemble! Les instructions de branche et cmov peuvent choisir le registre CR à lire. Cela vous donne donc la possibilité d'avoir plusieurs chaînes de drapeaux en vol à la fois, comme x86 ADCX / ADOX. alanclements.org/power%20pc.html
Peter Cordes