Cómo Clang compila una función

Planeaba escribir un artículo sobre cómo LLVM optimiza una función, pero primero debes escribir cómo Clang traduce C o C ++ a LLVM.




Considere los aspectos de alto nivel sin sumergirse en las profundidades de Clang. Quiero prestar atención a cómo la salida de Clang está relacionada con la entrada, mientras que no consideraremos las características no triviales de C ++. Utilizamos esta pequeña función, que tomé prestada de excelentes conferencias sobre optimizaciones cíclicas :

bool is_sorted(int *a, int n) { for (int i = 0; i < n - 1; i++) if (a[i] > a[i + 1]) return false; return true; } 

Como Clang no realiza ninguna optimización, y dado que LLVM IR se diseñó originalmente para trabajar con C y C ++, la conversión es relativamente fácil. Usaré Clang 6.0.1 (o una versión cerrada, ya que esta aún no se ha lanzado) en x86-64.

La línea de comando es la siguiente:

 clang++ is_sorted.cpp -O0 -S -emit-llvm 

En otras palabras: compilamos el archivo is_sorted.cpp como C ++ y luego le decimos a la cadena de herramientas LLVM lo siguiente: no optimizar, generar el ensamblador como una representación textual de LLVM IR. LLVM IR es voluminoso, y no se puede mostrar o analizar rápidamente; un formato de código de bits binario siempre es preferible si una persona no necesita mirar este código. Aquí está el IR LLVM completo, lo revisaremos en partes.

Comencemos en la parte superior del archivo:

 ; ModuleID = 'is_sorted.cpp' source_filename = "is_sorted.cpp" target datalayout = "em:e-i64:64-f80:128-n8:16:32:64-S128" target triple = "x86_64-unknown-linux-gnu" 

El texto completo entre el punto y coma y el final de la línea es un comentario, lo que significa que la primera línea no hace nada, pero si está interesado, en LLVM el "módulo" es una unidad de compilación, un contenedor de código y datos. La segunda línea tampoco debería molestarnos. La tercera línea describe algunas suposiciones hechas por el compilador, no juegan un papel en este artículo, pero puede leer más aquí . El objetivo tres es el legado de gcc y ya no nos necesita.

La función LLVM tiene atributos opcionales:

 ; Function Attrs: noinline nounwind optnone uwtable 

Algunos de ellos (como estos) son compatibles con el front-end, otros se agregan más tarde mediante pases de optimización. Estos atributos no tienen nada que ver con el significado del código, no los discutiré aquí, pero puede leer sobre ellos aquí si está interesado.

Y finalmente, nuestra función:

 define zeroext i1 @_Z9is_sortedPii(i32* %a, i32 %n) #0 { 

"Zeroext" significa que el valor de retorno de la función (i1, un entero de un solo bit) debe expandirse con ceros en el backend al ancho que requiere la ABI. Luego viene el nombre de la función "destrozada", luego la lista de parámetros es básicamente la misma que en el código C ++, excepto que i32 define una variable de 32 bits. # 0 conecta la función al grupo de atributos al final del archivo.

Aquí está la primera unidad base:

 entry: %retval = alloca i1, align 1 %a.addr = alloca i32*, align 8 %n.addr = alloca i32, align 4 %i = alloca i32, align 4 store i32* %a, i32** %a.addr, align 8 store i32 %n, i32* %n.addr, align 4 store i32 0, i32* %i, align 4 br label %for.cond 

Cada instrucción LLVM debe ubicarse dentro de la unidad base: un conjunto de instrucciones que tiene una entrada al principio y una salida al final. La última instrucción de la unidad base debe ser una instrucción de terminación : "fallar" en la siguiente unidad base es inaceptable. Cada función debe tener un bloque de entrada que no tenga predecesores que realicen la transición a este bloque. Esta y otras propiedades se verifican cuando se analiza IR, estas "verificaciones" también se pueden llamar varias veces durante el proceso de compilación. El verificador es útil para la depuración cuando un pase genera un IR no válido.

Las primeras cuatro instrucciones en este bloque base son "alloca": asignación de memoria de pila. Las tres primeras crean variables creadas implícitamente durante la compilación, la cuarta, una variable de bucle. Solo se puede acceder a las variables asignadas de esta manera a través de las instrucciones de carga y almacenamiento. Las siguientes tres instrucciones inicializan las tres ranuras de la pila, a.addr y n.addr se inicializan utilizando los valores pasados ​​a la función como parámetros, e i se inicializa a cero. El valor de retorno no necesita inicializarse, cualquier código que no esté indefinido en C y C ++ tendrá que ocuparse de esto. La última instrucción es una transición incondicional a la siguiente unidad base (aún no estamos preocupados por esto, el back-end LLVM eliminará la mayoría de las transiciones innecesarias).

Puede preguntar: ¿por qué Clang asigna ranuras de pila para ayn? ¿Por qué no solo usa estos valores directamente? En esta función, dado que a y n no cambian, dicha estrategia funcionará, pero el optimizador tendrá en cuenta este caso y queda fuera de la competencia de Calng. Si a y n pueden modificarse, deberían estar en la memoria y no deberían ser valores SSA, que, por definición, solo pueden tomar valor en un punto del programa. Las celdas de memoria están fuera del mundo SSA y se pueden modificar en cualquier momento. Esto puede parecer extraño, pero tal solución le permite organizar el trabajo de todas las partes del compilador de una manera natural y eficiente.

Pienso en Clang como un generador de código SSA degenerado que satisface todos los requisitos de SSA, pero solo porque el intercambio de información entre las unidades base ocurre a través de la memoria. Generar código no degenerado requiere un poco de atención y un análisis, y los desarrolladores de Clang se negaron a hacerlo para separar las responsabilidades de generar y optimizar el código. No vi los resultados de la medición, pero en mi opinión, se generan muchas operaciones de memoria, y luego, casi de inmediato, el optimizador elimina la mayoría de ellas, sin generar grandes gastos generales de tiempo de compilación,

Considere cómo se traduce el bucle for. En términos generales, se ve así:

 for (initializer; condition; modifier) { body } 

Esto se traduce en algo como esto:

  initializer goto COND COND: if (condition) goto BODY else goto EXIT BODY: body modifier goto COND EXIT: 

Por supuesto, dicha traducción no es específica de Clang, cualquier compilador de C y C ++ hace lo mismo.

En nuestro ejemplo, el inicializador de bucle se contrae en el bloque base de entrada. La siguiente unidad base es una verificación de condición de bucle:

 for.cond: ; preds = %for.inc, %entry %0 = load i32, i32* %i, align 4 %1 = load i32, i32* %n.addr, align 4 %sub = sub nsw i32 %1, 1 %cmp = icmp slt i32 %0, %sub br i1 %cmp, label %for.body, label %for.end 

Clang también hace un comentario útil de que se puede llegar a este bloque base desde for.inc o desde el bloque base de entrada. Este bloque carga i y n de la memoria, reduce n (el indicador nsw refleja la propiedad del lenguaje C que el desbordamiento de signos no está definido; sin este indicador LLVM usa la semántica del código adicional), compara el valor reducido con i usando el slt (firmado menos que, firmar menos que) y luego finalmente ramificarse en la base para.cuerpo o para.bloque final.

La entrada al cuerpo del bucle solo es posible desde el bloque for.cond:

 for.body: %2 = load i32*, i32** %a.addr, align 8 %3 = load i32, i32* %i, align 4 %idxprom = sext i32 %3 to i64 %arrayidx = getelementptr inbounds i32, i32* %2, i64 %idxprom %4 = load i32, i32* %arrayidx, align 4 %5 = load i32*, i32** %a.addr, align 8 %6 = load i32, i32* %i, align 4 %add = add nsw i32 %6, 1 %idxprom1 = sext i32 %add to i64 %arrayidx2 = getelementptr inbounds i32, i32* %5, i64 %idxprom1 %7 = load i32, i32* %arrayidx2, align 4 %cmp3 = icmp sgt i32 %4, %7 br i1 %cmp3, label %if.then, label %if.end 

Las dos primeras líneas cargan ayi en los registros SSA; Luego me expando a 64 bits y puedo participar en el cálculo de la dirección. El comando getelementptr (o gep para abreviar) es el comando LLVM conocido por su pretensión; incluso tiene su propia sección de ayuda . A diferencia del lenguaje de máquina, LLVM no trata los punteros como enteros. Esto facilita el análisis de alias y otras optimizaciones de memoria. Este código carga un [i] y un [i + 1], los compara y realiza una ramificación según el resultado.

El bloque if.then guarda 0 en la ranura de la pila para el valor de retorno de la función y salta incondicionalmente al bloque de salida de la función:

 if.then: store i1 false, i1* %retval, align 1 br label %return 

El bloque else es trivial:

 if.end: br label %for.inc 

Y el bloque para agregar uno a la variable de bucle también es muy simple:

 for.inc: %8 = load i32, i32* %i, align 4 %inc = add nsw i32 %8, 1 store i32 %inc, i32* %i, align 4 br label %for.cond 

Este código salta hacia atrás para verificar las condiciones del bucle.

Si el ciclo se completa normalmente, devolvemos verdadero:

 for.end: store i1 true, i1* %retval, align 1 br label %return 

Y finalmente, lo que cargamos en la ranura de la pila del valor de retorno se carga y devuelve:

 return: %9 = load i1, i1* %retval, align 1 ret i1 %9 

No hay nada especial al final de la función. La publicación resultó ser más larga de lo que pensaba, en la próxima publicación consideraremos optimizar el nivel de IR para esta función.

(Gracias a Xi Wang y Alex Rosenberg por las correcciones enviadas)