Pourquoi est-il permis à gcc de charger de manière spéculative à partir d'une structure?

Question

Exemple Montrant l'Optimisation gcc et le Code de l'Utilisateur qui Peut se mettre en Défaut

La fonction " foo " dans l'extrait de code ci-dessous va se charger seul de la les membres de la structure A ou B; eh bien au moins qui est l'intention de la unoptimized code.

typedef struct {
  int A;
  int B;
} Pair;

int foo(const Pair *P, int c) {
  int x;
  if (c)
    x = P->A;
  else
    x = P->B;
  return c/102 + x;
}

Voici ce que gcc-O3 donne:

mov eax, esi
mov edx, -1600085855
test esi, esi
mov ecx, DWORD PTR [rdi+4]   <-- ***load P->B**
cmovne ecx, DWORD PTR [rdi]  <-- ***load P->A***
imul edx
lea eax, [rdx+rsi]
sar esi, 31
sar eax, 6
sub eax, esi
add eax, ecx
ret

Il semble donc que gcc est autorisé à la spéculation charge à la fois les membres de la structure, afin d'éliminer la ramification. Mais alors, le code suivant considérée comme un comportement non défini ou est la gcc d'optimisation ci-dessus illégal?

#include <stdlib.h>  

int naughty_caller(int c) {
  Pair *P = (Pair*)malloc(sizeof(Pair)-1); // *** Allocation is enough for A but not for B ***
  if (!P) return -1;

  P->A = 0x42; // *** Initializing allocation only where it is guaranteed to be allocated ***

  int res = foo(P, 1); // *** Passing c=1 to foo should ensure only P->A is accessed? ***

  free(P);
  return res;
}

Si la charge de la spéculation qui va se passer dans le scénario ci-dessus, il ya une chance que le chargement P->B provoquera une exception parce que le dernier octet de la P->B réside peut-être dans la mémoire non allouée. Cette exception ne se produira pas si l'optimisation est éteint.

La Question

Est l'optimisation gcc montré au-dessus de la charge de la spéculation juridique? D'où vient le spec dire ou laisser entendre que c'est ok? Si l'optimisation est légal, quel est le code dans 'naughtly_caller' avérer être un comportement indéfini?

Answer 1

La lecture d'une variable (qui n'a pas été déclarée volatile) n'est pas considéré comme un "effet secondaire", comme spécifié par la norme. Ainsi, le programme est gratuit pour lire un emplacement, puis jeter le résultat, aussi loin que la norme C est concerné.

C'est très commun. Supposons que vous demande 1 octet de données à partir d'un 4 octets entier. Le compilateur peut alors lire l'entier de 32 bits si c'est plus rapide (aligné à lire), et puis tout jeter, mais la demande d'un octet. Votre exemple est semblable à cela, mais le compilateur décidé de lire l'ensemble de la structure.

Formellement, cela se retrouve dans le comportement de la "machine abstraite", C11 chapitre 5.1.2.3. Étant donné que le compilateur suit les règles qui y sont mentionnées, il est libre de faire comme il lui plaît. Et les seules règles énumérées à l'égard volatile des objets et de l'ordonnancement des instructions. La lecture d'un autre struct membre en volatile struct ne serait pas ok.

Comme pour le cas de l'allocation de trop peu de mémoire pour l'ensemble de la structure, c'est un comportement indéfini. Parce que la disposition de la mémoire de la structure est généralement pas pour le programmeur de décider - par exemple le compilateur est autorisé à ajouter du rembourrage à la fin. Si il n'y a pas assez de mémoire allouée, vous pourriez vous retrouver interdit l'accès de la mémoire même si votre code ne fonctionne qu'avec le premier membre de la structure.

Answer 2

Non, si *P est alloué correctement P->B ne seront jamais dans la mémoire non allouée. Il pourrait ne pas être initialisé, c'est tout.

Le compilateur a le droit de faire ce qu'ils font. La seule chose qui n'est pas autorisé est de oops sur l'accès des P->B avec l'excuse qu'il n'est pas initialisé. Mais quoi et comment ils le font tous, c'est en vertu de la discrétion de la mise en œuvre et non pas votre préoccupation.

Si vous avez jeté un pointeur vers un bloc retourné par malloc de Pair* qui n'est pas garanti d'être assez large pour contenir un Pair le comportement de votre programme n'est pas défini.

Answer 3

Une expression postfixée suivie de l'opérateur -> et d'un identifiant désigne un membre d'une structure ou d'un objet d'union. La valeur est celle du membre nommé de l'objet sur lequel pointe la première expression.

Si l'invocation de l'expression P->A est bien définie, alors P doit en fait pointer sur un objet de type struct Pair , et par conséquent P->B est bien défini aussi.

Answer 4

Un -> de l'opérateur sur un Pair * implique qu'il y a tout un Pair objet entièrement alloué. (@Hurkyl cite la norme.)

x86 (comme toute architecture normale) n'ont pas d'effets secondaires pour accéder à la normale de la mémoire allouée, alors x86 mémoire sémantique sont compatibles avec le C machine abstraite de la sémantique pour les non-volatile de la mémoire. Les compilateurs peuvent éventuellement en charge si/quand ils pensent que ce sera un rendement à la victoire sur la cible de la microarchitecture ils sont de réglage pour dans une situation donnée.

Notez que sur x86 de protection de la mémoire fonctionne avec la page de granularité. Le compilateur pourrait se dérouler d'une boucle ou d'vectoriser avec SIMD d'une manière qui lit à l'extérieur d'un objet, aussi longtemps que toutes les pages touché contiennent certains des octets de l'objet. Est-il sécuritaire de le lire après la fin d'un tampon à l'intérieur de la même page sur x86 et x64?. libc strlen() des implémentations écrite à la main à l'assemblée de le faire, mais autant que je sache, gcc n'a pas, au lieu d'utiliser scalaire boucles pour les restes des éléments à la fin d'une auto-vectorisé en boucle même où elle a déjà aligné les pointeurs avec un (entièrement déroulé) démarrage de la boucle. (Peut-être parce qu'il ferait d'exécution vérification de limites avec valgrind difficile.)

---

Pour obtenir le comportement que vous attendiez, utiliser un const int * arg.

Un tableau est un objet unique, mais les pointeurs sont différents tableaux. (Même avec inline dans un contexte où les deux éléments du tableau sont connus pour être accessible, je n'ai pas pu obtenir de gcc pour émettre un code comme il le fait pour la structure, donc si c'est struct code est une victoire, c'est un raté l'optimisation de ne pas le faire sur les tableaux quand il est aussi sûr.).

En C, vous êtes autorisé à passer à cette fonction un pointeur vers un seul int, tant que c est non-nul. Lors de la compilation pour les architectures x86, gcc a supposer qu'il pourrait être pointer à la dernière int dans une page, la page suivante non cartographiées.

Source + gcc et clang sortie pour cela et d'autres variations sur le Godbolt compilateur explorer

// exactly equivalent to  const int p[2]
int load_pointer(const int *p, int c) {
  int x;
  if (c)
    x = p[0];
  else
    x = p[1];  // gcc missed optimization: still does an add with c known to be zero
  return c + x;
}

load_pointer:    # gcc7.2 -O3
    test    esi, esi
    jne     .L9
    mov     eax, DWORD PTR [rdi+4]
    add     eax, esi         # missed optimization: esi=0 here so this is a no-op
    ret
.L9:
    mov     eax, DWORD PTR [rdi]
    add     eax, esi
    ret

---

En C, vous pouvez passer sorte de passer un tableau d'objet (par référence) à une fonction, garantissant à la fonction qu'il est permis de toucher à tous, la mémoire, même si le C machine abstraite qui ne fonctionne pas. La syntaxe est - int p[static 2]

int load_array(const int p[static 2], int c) {
  ... // same body
}

Mais gcc ne pas prendre parti, et émet un code identique à load_pointer.

---

Hors sujet: clang compile toutes les versions (struct et tableau) de la même manière, à l'aide d'un cmov de branchlessly calculer une adresse de chargement.

    lea     rax, [rdi + 4]
    test    esi, esi
    cmovne  rax, rdi
    add     esi, dword ptr [rax]
    mov     eax, esi            # missed optimization: mov on the critical path
    ret

Ce n'est pas nécessairement une bonne chose: il a une latence plus élevée que gcc de la structure du code, parce que l'adresse de chargement dépend d'un couple supplémentaire ALU uop. Il est assez bon si les deux adresses ne sont pas sûrs à lire et une branche de prévoir le mal.

Nous pouvons obtenir un meilleur code pour la même stratégie de gcc et clang, à l'aide de setcc (1 uop avec 1c latence sur tous les Processeurs à l'exception de quelques très anciennes), au lieu de cmovcc (2 uop sur Intel avant de Skylake). xor-réduction à zéro est toujours moins cher qu'un LEA, trop.

int load_pointer_v3(const int *p, int c) {
  int offset = (c==0);
  int x = p[offset];
  return c + x;
}

    xor     eax, eax
    test    esi, esi
    sete    al
    add     esi, dword ptr [rdi + 4*rax]
    mov     eax, esi
    ret

gcc et clang les deux mis la dernière mov sur le chemin critique. Et sur Intel Sandybridge-famille, de l'indexation mode d'adressage ne reste pas de micro-fusion avec l' add. Donc, ce serait mieux, à l'instar de ce qu'il fait dans la ramification version:

    xor     eax, eax
    test    esi, esi
    sete    al
    mov     eax, dword ptr [rdi + 4*rax]
    add     eax, esi
    ret

De simples modes d'adressage, comme [rdi] ou [rdi+4] ont 1c latence plus faible que les autres sur Intel banque nationale, de la famille des Processeurs, donc cela pourrait effectivement être pire temps de latence sur Skylake (où cmov n'est pas cher). L' test et lea peuvent s'exécuter en parallèle.

Après l'in-lining, que final mov n'existe pas, et il pourrait juste add en esi.