c++ - programacion - lenguaje c

¿Por qué los compiladores modernos de C++ no optimizan bucles simples como este?(Clang, MSVC)

Question

Cuando compilo y ejecuto este código con Clang ( -O3 ) o MSVC ( /O2 ) ...

#include <stdio.h>
#include <time.h>

static int const N = 0x8000;

int main()
{
    clock_t const start = clock();
    for (int i = 0; i < N; ++i)
    {
        int a[N];    // Never used outside of this block, but not optimized away
        for (int j = 0; j < N; ++j)
        {
            ++a[j];  // This is undefined behavior (due to possible
                     // signed integer overflow), but Clang doesn''t see it
        }
    }
    clock_t const finish = clock();
    fprintf(stderr, "%u ms/n",
        static_cast<unsigned int>((finish - start) * 1000 / CLOCKS_PER_SEC));
    return 0;
}

... el ciclo no se optimiza.

Además, ni Clang 3.6 ni Visual C ++ 2013 ni GCC 4.8.1 me dicen que la variable no está inicializada.

Ahora me doy cuenta de que la falta de una optimización no es un error per se, pero me parece sorprendente dado que se supone que los compiladores son bastante inteligentes hoy en día. Esto parece una pieza de código tan simple que incluso las técnicas de análisis de vida útil de hace una década deberían ser capaces de optimizar la variable a y, por lo tanto, todo el ciclo, sin importar el hecho de que incrementar la variable ya es un comportamiento indefinido.

Sin embargo, solo GCC puede darse cuenta de que no es operativo, y ninguno de los compiladores me dice que esta es una variable no inicializada.

¿Por qué es esto? ¿Qué impide que el análisis simple de liveness le diga al compilador que a no está siendo utilizado? Además, ¿por qué el compilador no detecta que a[j] no está inicializado en primer lugar? ¿Por qué los detectores de variables no inicializadas existentes en todos esos compiladores pueden detectar este error obvio?

Answer 1

++a[j];  // This is undefined behavior too, but Clang doesn''t see it

¿Estás diciendo que esto es un comportamiento indefinido porque los elementos de la matriz no están inicializados?

Si es así, aunque esta es una interpretación común de la cláusula 4.1 / 1 en el estándar, creo que es incorrecta. Los elementos no están inicializados en el sentido de que los programadores usualmente usan este término, pero no creo que esto corresponda exactamente con el uso del término en la especificación C ++.

En particular, C ++ 11 8.5 / 11 establece que estos objetos son, de hecho, inicializados por defecto, y esto me parece ser mutuamente excluyente sin ser inicializado. El estándar también establece que, para algunos objetos, la inicialización predeterminada significa que ''no se realiza inicialización''. Algunos podrían suponer que esto significa que no están inicializados, pero esto no está especificado y simplemente lo interpreto como que no se requiere dicho rendimiento.

La especificación deja en claro que los elementos de la matriz tendrán valores indeterminados. C ++ especifica, por referencia al estándar C, que los valores indeterminados pueden ser representaciones válidas, legales para acceder normalmente o trampas de representaciones. Si los valores indeterminantes particulares de los elementos de la matriz pasan a ser representaciones válidas (y ninguno es INT_MAX, evitando el desbordamiento), la línea anterior no desencadena ningún comportamiento indefinido en C ++ 11.

Como estos elementos de matriz podrían ser representaciones de trampa, sería perfectamente conforme para que clang actúe como si tuvieran la garantía de ser representaciones de trampas, eligiendo efectivamente hacer el código UB para crear una oportunidad de optimización.

Incluso si clang no hace eso, aún podría optar por optimizar en función del flujo de datos. Clang sí sabe cómo hacerlo, como lo demuestra el hecho de que si el lazo interno cambia ligeramente, los bucles se eliminan.

Entonces, ¿por qué la presencia (opcional) de UB parece obstaculizar la optimización, cuando UB generalmente se toma como una oportunidad para una mayor optimización?

Lo que puede estar pasando es que clang ha decidido que los usuarios quieren int trapping basado en el comportamiento del hardware. Entonces, en lugar de tomar trampas como una oportunidad de optimización, clang tiene que generar código que reproduce fielmente el comportamiento del programa en el hardware. Esto significa que los bucles no se pueden eliminar en función del flujo de datos, ya que hacerlo podría eliminar las trampas de hardware.

C ++ 14 actualiza el comportamiento de tal manera que el acceso a valores indeterminados produce un comportamiento indefinido, independientemente de si se considera la variable no inicializada o no: https://stackoverflow.com/a/23415662/365496

Answer 2

El comportamiento indefinido es irrelevante aquí. Reemplazando el lazo interno con:

    for (int j = 1; j < N; ++j)
    {
        a[j-1] = a[j];
        a[j] = j;
    }

... tiene el mismo efecto, al menos con Clang.

El problema es que el bucle interno se carga desde a[j] (para un poco de j ) y almacena a a[j] (para un poco de j ). No se puede eliminar ninguna de las tiendas, porque el compilador cree que pueden ser visibles para cargas posteriores, y ninguna de las cargas se puede eliminar, porque sus valores se utilizan (como entrada en las tiendas posteriores). Como resultado, el bucle todavía tiene efectos secundarios en la memoria, por lo que el compilador no ve que se puede eliminar.

Contrariamente a la respuesta de nm, reemplazar int por unsigned no hace que el problema desaparezca. El código generado por Clang 3.4.1 usando int y usando unsigned int es idéntico.

Answer 3

Es un problema interesante con respecto a la optimización. Me esperaba que en la mayoría de los casos, el compilador trataría cada elemento de la matriz como una variable individual al hacer un análisis de código muerto. Ans 0x8000 crea demasiadas variables individuales para rastrear, por lo que el compilador no intenta. El hecho de que a[j] no siempre acceda al mismo objeto podría causar problemas también para el optimizador.

Obviamente, los diferentes compiladores usan diferentes heurísticas; un compilador podría tratar la matriz como un solo objeto y detectar que nunca afectó la salida (comportamiento observable). Algunos compiladores pueden optar por no hacerlo, sin embargo, sobre la base de que, por lo general, es mucho trabajo con muy poca ganancia: ¿con qué frecuencia serían aplicables tales optimizaciones en el código real?

Answer 4

Eso es realmente muy interesante. Probé tu ejemplo con MSVC 2013. Mi primera idea fue que el hecho de que ++ a [j] esté algo indefinido es la razón por la que no se elimina el bucle, ya que eliminar esto definitivamente cambiaría el significado del programa de un modo indefinido. / Semántica incorrecta para algo significativo, así que traté de inicializar los valores antes, pero los bucles aún no desapareceban.

Luego reemplacé el ++ a [j]; con un a [j] = 0; que luego produjo una salida sin ningún bucle, por lo que se eliminó todo entre las dos llamadas a clock (). Solo puedo adivinar el motivo. Quizás el optimizador no puede probar que el operador ++ no tenga efectos secundarios por ningún motivo.