Perfilado de código con LLVM

La maldición del no determinismo

Mi primer intento de escribir un pasaje LLVM: me encantan estos segfolty

Recientemente, me encontré con un problema interesante: necesitaba una forma determinista y multiplataforma para determinar el tiempo de ejecución del código C ++. Con la palabra "determinista" quiero decir que el mismo código se ejecutará por la misma cantidad de unidades de tiempo. Por multiplataforma, entiendo que el mismo código en Windows y Ubuntu se ejecutará por la misma cantidad de unidades de tiempo.

Naturalmente, medir el tiempo en la CPU no satisface estas condiciones. El código de la máquina varía según la arquitectura y el sistema operativo, y el mismo código tardará una cantidad diferente de tiempo en ejecutarse. Incluso en la misma máquina, factores como las fallas de caché jugarán un papel importante, lo suficiente como para distorsionar los resultados de medición del tiempo de ejecución del mismo código. Necesitaba algo más inteligente ...

Motivación

Me encontré con este problema cuando estaba trabajando en mi proyecto, Code Character. Code Character es una competencia de IA en línea en la que los participantes escriben bots para controlar un ejército en una estrategia por turnos. Quería limitar la cantidad de código que un participante puede ejecutar en un movimiento.

Mi primer pensamiento fue simplemente medir el tiempo de ejecución del código, pero, como podemos ver, esta estrategia no es determinista, y el participante que envió el mismo código dos veces obtendrá resultados completamente diferentes. De hecho, intentamos implementar esta solución, y los resultados cambian tanto que un participante puede ganar o perder con el mismo código. El resultado será completamente al azar, y descartamos la idea de medir el tiempo.

Código de bytes LLVM

Como no podemos medir el tiempo, decidimos medir el número de instrucciones ejecutadas. Por lo tanto, necesitamos instrumentar el código del participante. Si no está familiarizado con este término, esto está agregando algo de código a la aplicación, para monitorear algún parámetro, por ejemplo, el uso de la CPU o el tiempo de ejecución. Naturalmente, no esperamos que los participantes hagan esto por sí mismos, debemos automatizar el proceso.

Queríamos evitar los costos generales de las herramientas de tiempo de ejecución cuando trabajamos en nuestro servidor y, por lo tanto, algo como una herramienta de PIN no es adecuada para nuestros propósitos. En cambio, decidimos instruir directamente el código de los participantes para contar el número de instrucciones que se ejecutarían. En lugar de instrumentar binarios (código de máquina), decidimos usar Clang para compilar el código y el código de bytes LLVM del instrumento.

Si es nuevo en LLVM, es una colección de compiladores modulares y reutilizables y tecnologías de cadena de herramientas. Uno de los principales proyectos es LLVM IR y backend. En términos simples, se ha desarrollado una representación intermedia en la que una interfaz compiladora compila el código. Este código, LLVM IR, se compila en el código de la máquina por el backend LLVM. Por lo tanto, si está creando un nuevo idioma, puede decidir permitir que LLVM admita la generación y optimización de código de máquina, y escribir una interfaz para convertir su idioma a LLVM IR.


Clang convierte el código C ++ en LLVM IR, que luego se convierte en código máquina por el backend LLVM.

Clang es la interfaz de LLVM. Como necesitamos un método multiplataforma para medir el código, no podemos instrumentar el código binario. LLVM IR, sin embargo, es independiente de la plataforma, ya que es solo una representación intermedia del código. Instrumentar el código IR con bibliotecas LLVM es una solución multiplataforma simple.

Solución

Obviamente, un recuento de instrucciones IR LLVM simple no es adecuado, ya que necesitamos la cantidad de instrucciones que realmente se ejecutarán, y no solo la cantidad de instrucciones en el código. Al final, desarrollamos un algoritmo simple basado en el concepto de bloques básicos de código.

Una unidad base es un conjunto de instrucciones en el que solo la primera instrucción puede ser el punto de entrada, y solo la última instrucción puede ser el punto de salida. ( Cualquier transición dentro del bloque base también está prohibida - aprox. Transl. ) Para comprender esto, intente dividir el código en partes en las que las instrucciones de ramificación (transiciones, bucles y retornos) solo puedan ser las últimas en el conjunto, y la entrada al bloque (primera instrucción en función, bucle o bloque if / else) solo es posible en la primera instrucción. El resultado es un conjunto de bloques básicos: bloques de código secuencial que simplemente se ejecutan secuencialmente, sin decidir qué instrucción ejecutar a continuación.

¿Por qué no lo intentamos ahora? Este es un fragmento de código proporcionado por un colaborador de Code Character:

// Make the soldiers who aren't patrolling attack the enemy for (int i = NUM_SOLDIERS / 2; i < NUM_SOLDIERS; ++i) { auto &soldier = state.soldiers[i]; if (soldier.hp == 0) // If this soldier is dead, skip it continue; for (auto enemy_soldier : state.enemy_soldiers) { if (enemy_soldier.hp != 0) { // Ensure your prospective target has // not already been slain soldier.soldier_target = enemy_soldier.id; break; } } } 

Enlace Github: https://gist.github.com/JHurricane96/8c9c3a45ec5e969de4d9fecb47ebef69#file-player_code-cpp

Usando el hecho de que la unidad base tiene solo un punto de entrada (la primera instrucción), podemos dividir este fragmento en las siguientes unidades base:

 //-------------------------------- BB 1 ---------------------------------- for (int i = NUM_SOLDIERS / 2; i < NUM_SOLDIERS; ++i) { //-------------------------------- BB 2 ---------------------------------- auto &soldier = state.soldiers[i]; if (soldier.hp == 0) //-------------------------------- BB 3 ---------------------------------- continue; //-------------------------------- BB 4 ---------------------------------- for (auto enemy_soldier : state.enemy_soldiers) { //-------------------------------- BB 5 ---------------------------------- if (enemy_soldier.hp != 0) { //-------------------------------- BB 6 ---------------------------------- soldier.soldier_target = enemy_soldier.id; break; //-------------------------------- BB 7 ---------------------------------- } } } 

Enlace Github
Esto nos ayudó a entender cómo funcionan los bloques básicos, ahora veamos este algoritmo en LLVM IR:

 ; <label>:140: ; preds = %181, %139 %141 = load i32, i32* %19, align 4 %142 = sext i32 %141 to i64 %143 = icmp slt i64 %142, 20 br i1 %143, label %144, label %184 ; <label>:144: ; preds = %140 %145 = getelementptr inbounds %"struct.player_state::State", %"struct.player_state::State"* %2, i32 0, i32 1 %146 = load i32, i32* %19, align 4 %147 = sext i32 %146 to i64 %148 = call dereferenceable(72) %"struct.player_state::Soldier"* @_ZNSt5arrayIN12player_state7SoldierELm20EEixEm( %"struct.std::array.10"* %145, i64 %147) #3 store %"struct.player_state::Soldier"* %148, %"struct.player_state::Soldier"** %20, align 8 %149 = load %"struct.player_state::Soldier"*, %"struct.player_state::Soldier"** %20, align 8 %150 = getelementptr inbounds %"struct.player_state::Soldier", %"struct.player_state::Soldier"* %149, i32 0, i32 2 %151 = load i64, i64* %150, align 8 %152 = icmp eq i64 %151, 0 br i1 %152, label %153, label %154 ; <label>:153: ; preds = %144 br label %181 

Enlace Github

Si observa detenidamente, notará que el fragmento de código anterior es los primeros tres bloques del fragmento de código C ++ compilado en LLVM IR (cada línea es el comienzo del bloque base).

LLVM tiene bibliotecas que nos permiten escribir "pases" - código que puede transformar LLVM IR. La API LLVM nos permite leer y analizar fácilmente LLVM IR al iterar a través de módulos, funciones y bloques base, y modificar LLVM IR antes de que se compile en el código de máquina.

Ahora que tenemos los bloques básicos y la API LLVM, se está volviendo simple calcular la cantidad de instrucciones que se ejecutarán usando un algoritmo tan simple:

1. Escribimos la función IncrementCount, que toma un número entero e incrementa un número entero estático con este valor, cada vez que se llama. Debe estar vinculado al código de miembro.
2. Hacemos iteraciones sobre todos los bloques base. Para cada unidad base, realice los pasos 3 y 4.
3. Encontramos n - el número de instrucciones en esta unidad base.
4. Insertamos la llamada a la función IncrementCount antes de la última instrucción de la unidad base, con el argumento n.
5. El número entero estático con el que trabaja IncrementCount será el contador de instrucciones después de ejecutar el código. Se puede guardar en algún lugar y luego verificar.

Nuestro IR instrumentado funciona así:

 ; <label>:140: ; preds = %181, %139 %141 = load i32, i32* %19, align 4 %142 = sext i32 %141 to i64 %143 = icmp slt i64 %142, 20 call void @_Z14IncrementCountm(i32 4) br i1 %143, label %144, label %184 ; <label>:144: ; preds = %140 %145 = getelementptr inbounds %"struct.player_state::State", %"struct.player_state::State"* %2, i32 0, i32 1 %146 = load i32, i32* %19, align 4 %147 = sext i32 %146 to i64 %148 = call dereferenceable(72) %"struct.player_state::Soldier"* @_ZNSt5arrayIN12player_state7SoldierELm20EEixEm( %"struct.std::array.10"* %145, i64 %147) #3 store %"struct.player_state::Soldier"* %148, %"struct.player_state::Soldier"** %20, align 8 %149 = load %"struct.player_state::Soldier"*, %"struct.player_state::Soldier"** %20, align 8 %150 = getelementptr inbounds %"struct.player_state::Soldier", %"struct.player_state::Soldier"* %149, i32 0, i32 2 %151 = load i64, i64* %150, align 8 %152 = icmp eq i64 %151, 0 call void @_Z14IncrementCountm(i32 10) br i1 %152, label %153, label %154 ; <label>:153: ; preds = %144 call void @_Z14IncrementCountm(i32 1) br label %181 

Enlace Github

Como podemos ver, se realiza una llamada IncrementCount al final de cada bloque base, justo antes de la última instrucción. Usando el int estático con el que trabaja IncrementCount, podemos obtener el número de instrucciones al final del movimiento de cada participante. Este método es determinista y multiplataforma, como Se garantiza que el mismo código fuente generará el mismo LLVM IR si utilizamos la misma versión del compilador y los mismos indicadores.

Conclusión

La creación de perfiles de código no es tan simple como alguna vez pensé. En el proceso de trabajar en una tarea relativamente simple, me familiaricé con el funcionamiento del compilador y cómo escribir pases LLVM. Si está interesado en generar código y desea escribir sus propios pasajes, LLVM tiene una guía para principiantes . También hay un gran artículo de blog que solía escribir mi propio pasaje. Dado que la API LLVM no es compatible con versiones anteriores entre versiones principales, preste atención a qué versión de LLVM está utilizando.

Puede obtener el código fuente del pase aquí .