significado - ¿Por qué se permite a gcc cargar especulativamente desde una estructura?

especulativos significado

Question

Ejemplo que muestra la optimización de gcc y el código de usuario que pueden fallar

La función ''foo'' en el fragmento a continuación cargará solo uno de los miembros de estructura A o B; bueno, al menos esa es la intención del código no optimizado.

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;
}

Esto es lo que da gcc -O3:

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

Entonces parece que a gcc se le permite cargar especulativamente ambos miembros de la estructura para eliminar la ramificación. Pero entonces, ¿se considera el siguiente código comportamiento indefinido o es ilegal la optimización de gcc anterior?

#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 especulación de carga ocurrirá en el escenario anterior, existe la posibilidad de que cargar P-> B cause una excepción porque el último byte de P-> B puede estar en la memoria no asignada. Esta excepción no sucederá si la optimización está desactivada.

La pregunta

¿Es legal la optimización de gcc que se muestra arriba de la especulación de carga? ¿Dónde dice o implica la especificación que está bien? Si la optimización es legal, ¿cómo se convierte el código en ''naughtly_caller'' en un comportamiento indefinido?

Answer 1

Una expresión postfix seguida por el operador -> y un identificador designa un miembro de una estructura u objeto de unión. El valor es el del miembro nombrado del objeto al que apunta la primera expresión

Si se invoca la expresión P->A está bien definida, entonces P debe apuntar a un objeto de tipo struct Pair , y en consecuencia P->B también está bien definido.

Answer 2

Esto es perfectamente legal porque leer alguna ubicación de memoria no se considera un comportamiento observable en el caso general (la volatile cambiaría esto).

Su código de ejemplo es un comportamiento indefinido, pero no puedo encontrar ningún pasaje en los documentos estándar que explícitamente lo indique. Pero creo que es suficiente echar un vistazo a las reglas para tipos efectivos ... de N1570, §6.5 p6:

Si un valor se almacena en un objeto que no tiene un tipo declarado a través de un valor que tiene un tipo que no es un tipo de carácter, entonces el tipo del valor se convierte en el tipo efectivo del objeto para ese acceso y para accesos posteriores que no modifican el valor almacenado.

Entonces, su acceso de escritura a *P realidad le da a ese objeto el tipo Pair - por lo tanto, solo se extiende a la memoria que no asignó, el resultado es un acceso fuera de los límites.

Answer 3

Esto siempre está permitido bajo la regla "como si" si ningún programa conforme puede notar la diferencia. Por ejemplo, una implementación podría garantizar que después de cada bloque asignado con malloc, hay al menos ocho bytes a los que se puede acceder sin efectos secundarios. En esa situación, el compilador puede generar código que sería un comportamiento indefinido si lo escribiera en su código. Por lo tanto, sería legal que el compilador lea P [1] siempre que P [0] esté correctamente asignado, incluso si eso fuera un comportamiento indefinido en su propio código.

Pero en su caso, si no asigna suficiente memoria para una estructura, leer cualquier miembro es un comportamiento indefinido. Entonces, aquí el compilador puede hacer esto, incluso si la lectura P-> B falla.

Answer 4

La lectura de una variable (que no fue declarada como volatile ) no se considera un "efecto secundario" según lo especificado por el estándar C. Por lo tanto, el programa es libre de leer una ubicación y luego descartar el resultado, en lo que respecta al estándar C.

Esto es muy comun. Suponga que solicita 1 byte de datos de un entero de 4 bytes. El compilador puede leer los 32 bits completos si es más rápido (lectura alineada), y luego descartar todo menos el byte solicitado. Su ejemplo es similar a esto, pero el compilador decidió leer la estructura completa.

Formalmente esto se encuentra en el comportamiento de "la máquina abstracta", C11 capítulo 5.1.2.3. Dado que el compilador sigue las reglas especificadas allí, es libre de hacer lo que le plazca. Y las únicas reglas enumeradas se volatile objetos volatile y la secuencia de instrucciones. Leer un miembro de estructura diferente en una estructura volatile no estaría bien.

En cuanto al caso de asignar muy poca memoria para toda la estructura, ese es un comportamiento indefinido. Debido a que el diseño de memoria de la estructura generalmente no es para que el programador decida, por ejemplo, el compilador puede agregar relleno al final. Si no hay suficiente memoria asignada, puede terminar accediendo a la memoria prohibida aunque su código solo funcione con el primer miembro de la estructura.

Answer 5

No, si *P se asigna correctamente P->B nunca estará en la memoria no asignada. Puede que no se inicialice, eso es todo.

El compilador tiene todo el derecho de hacer lo que hacen. Lo único que no está permitido es oops sobre el acceso de P->B con la excusa de que no está inicializado. Pero qué y cómo hacen todo esto está bajo la discreción de la implementación y no es de su incumbencia.

Si lanza un puntero a un bloque devuelto por malloc a Pair* que no se garantiza que sea lo suficientemente ancho como para contener un Pair el comportamiento de su programa no está definido.

Answer 6

Un operador -> en un Pair * implica que hay un objeto Pair completo completamente asignado. ( @Hurkyl cita el estándar ).

x86 (como cualquier arquitectura normal) no tiene efectos secundarios para acceder a la memoria asignada normal, por lo que la semántica de memoria x86 es compatible con la semántica de la máquina abstracta C para memoria no volatile . Los compiladores pueden cargar especulativamente si / cuando piensan que será una ganancia de rendimiento en la microarquitectura objetivo que están ajustando en cualquier situación dada.

Tenga en cuenta que en x86 la protección de memoria funciona con granularidad de página. El compilador podría desenrollar un bucle o vectorizarlo con SIMD de manera que se lea fuera de un objeto, siempre que todas las páginas tocadas contengan algunos bytes del objeto. ¿Es seguro leer más allá del final de un búfer dentro de la misma página en x86 y x64? . Las strlen() libc strlen() escritas a mano en ensamblado hacen esto, pero AFAIK gcc no lo hace, en su lugar usa bucles escalares para los elementos sobrantes al final de un bucle auto-vectorizado incluso donde ya alineó los punteros con un (completamente desenrollado) bucle de inicio (Quizás porque dificultaría la verificación de los límites de tiempo de ejecución con valgrind ).

Para obtener el comportamiento que esperaba, use un const int * arg .

Una matriz es un solo objeto, pero los punteros son diferentes de las matrices. (Incluso con la inclusión en un contexto en el que se sabe que ambos elementos de la matriz son accesibles, no pude hacer que gcc emitiera código como lo hace para la estructura, por lo que si su código de estructura es una victoria, es una optimización perdida para no hazlo en matrices cuando también sea seguro).

En C, puede pasar esta función un puntero a un solo int , siempre que c no sea cero. Al compilar para x86, gcc tiene que suponer que podría estar apuntando al último int en una página, con la siguiente página sin asignar.

Fuente + salida de gcc y clang para esta y otras variaciones en el explorador del compilador Godbolt

// 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, puede pasar una especie de paso de un objeto de matriz (por referencia) a una función , garantizando a la función que se permite tocar toda la memoria, incluso si la máquina abstracta C no lo hace. La sintaxis es int p[static 2]

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

Pero gcc no se aprovecha y emite un código idéntico a load_pointer.

Fuera de tema: clang compila todas las versiones (estructura y matriz) de la misma manera, usando un cmov para calcular sin ramificaciones una dirección de carga.

    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

Esto no es necesariamente bueno: tiene una latencia más alta que el código de estructura de gcc, porque la dirección de carga depende de un par de ALU adicionales. Es bastante bueno si ambas direcciones no son seguras de leer y una rama predeciría mal.

Podemos obtener un mejor código para la misma estrategia de gcc y clang, usando setcc (1 uop con latencia 1c en todas las CPU excepto algunas realmente antiguas), en lugar de cmovcc (2 uops en Intel antes de Skylake). xor cero también es siempre más barato que un LEA.

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

tanto gcc como clang ponen el mov final en el camino crítico. Y en la familia Intel Sandybridge, el modo de direccionamiento indexado no permanece micro-fusionado con el add . Entonces esto sería mejor, como lo que hace en la versión ramificada:

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

Los modos de direccionamiento simples como [rdi] o [rdi+4] tienen una latencia 1c menor que otros en las CPU de la familia Intel SnB, por lo que esto podría ser una latencia peor en Skylake (donde cmov es barato). La test y el lea pueden ejecutarse en paralelo.

Después de la alineación, ese mov final probablemente no existiría, y podría add a esi .