Cómo intenté hacer un analizador estático GLSL (y qué salió mal)

Una vez que me estaba preparando para Ludum Dare e hice un juego simple en el que usaba sombreadores de píxeles (otros no fueron incorporados al motor Phaser).

color = pixelShader(x, y, ...other attributes) 

Después de la prueba, le tiré el enlace a un amigo y recibí de él una captura de pantalla con la pregunta "¿es esto normal?"

No, eso no era normal. Después de mirar cuidadosamente el código del sombreador, encontré un error de cálculo:

 if (t < M) { realColor = mix(color1,color2, pow(1. - t / R1, 0.5)); } 

Porque Como la constante R1 era menor que M, en algunos casos el resultado en el primer argumento de pow fue un número menor que cero. La raíz cuadrada del número negativo es algo misterioso, al menos para el estándar GLSL. Mi tarjeta de video no estaba confundida, y de alguna manera salió de esta posición (parece haber regresado de pow 0), pero resultó ser más legible para un amigo.

Y luego pensé: ¿puedo evitar tales problemas en el futuro? Nadie está a salvo de errores, especialmente aquellos que no se reproducen localmente. No puede escribir pruebas unitarias para GLSL. Al mismo tiempo, las transformaciones dentro del sombreador son bastante simples: multiplicación, división, senos, cosenos ... ¿Es realmente imposible rastrear los valores de cada variable y asegurarse de que bajo ninguna circunstancia vaya más allá de los límites permisibles de los valores?

Así que decidí intentar hacer un análisis estático para GLSL. Lo que surgió de esto: puedes leerlo debajo del corte.

Te avisaré de inmediato: no pude obtener ningún producto terminado, solo un prototipo educativo.

Análisis preliminar

Habiendo estudiado un poco de los artículos existentes sobre este tema (y descubrí en el camino que el tema se llama Análisis de Rango de Valor), me alegré de tener GLSL y no otro idioma. Juzga por ti mismo:

• sin "dinámica": referencias a funciones, interfaces, tipos inferidos automáticamente, etc.
• sin manejo directo de memoria
• sin módulos, enlaces, enlace tardío: el código fuente completo del sombreador está disponible
  los rangos son generalmente conocidos por los valores de entrada
• pocos tipos de datos, y esos giran en torno a un flotador. raramente se usan int / bool, y no es tan importante seguirlos
• raramente se usan ifs y bucles (debido a problemas de rendimiento). los bucles, si se usan, a menudo son contadores simples para pasar por una matriz o repetir un cierto efecto varias veces. Nadie escribirá tal horror en GLSL (espero).

 //   - https://homepages.dcc.ufmg.br/~fernando/classes/dcc888/ementa/slides/RangeAnalysis.pdf k = 0 while k < 100: i = 0 j = k while i < j: i = i + 1 j = j – 1 k = k + 1 

En general, dadas las limitaciones de GLSL, la tarea parece ser solucionable. El algoritmo principal es el siguiente:

1. analiza el código del sombreador y crea una secuencia de comandos que cambian los valores de cualquier variable
2. conociendo los rangos iniciales para las variables, vaya a través de la secuencia, actualizando los rangos cuando cambian
3. Si el rango viola cualquier límite dado (por ejemplo, un número negativo puede llegar a pow, o algo mayor que 1 llegará al "color de salida" gl_FragColor en el componente rojo), debe mostrar una advertencia

Tecnologías utilizadas

Aquí tuve una elección larga y dolorosa. Por un lado, mi ámbito principal es verificar los sombreadores WebGL, entonces, ¿por qué no javascript para ejecutar todo en el navegador durante el desarrollo? Por otro lado, he planeado salir de Phaser durante mucho tiempo y probar otro motor como Unity o LibGDX. También habrá sombreadores, pero JavaScript desaparecerá.

Y, por otro lado, la tarea se realizó principalmente para el entretenimiento. Y el mejor entretenimiento del mundo es el zoológico. Por lo tanto:

1. Análisis de código GLSL realizado en javascript. Es solo que rápidamente encontré la biblioteca para analizar GLSL en AST, y la interfaz de usuario de prueba parece estar más familiarizada con estar basada en la web. AST se convierte en una secuencia de comandos, que se envía a ...
2. ... la segunda parte, que está escrita en C ++ y compilada en WebAssembly. Decidí de esta manera: si de repente quiero fijar este analizador a algún otro motor, con una biblioteca C ++, esto debería hacerse de la manera más simple.

Todo, ahora puedes irte.

Brevemente sobre el modelo.

El analizador guarda en la memoria una lista de variables que se encuentran en el sombreador, y para cada una almacena el rango de valores actual posible (como [0,1] o [1,∞) ).

El analizador recibe un flujo de trabajo como este:

 cmdId: 10 opCode: sin arguments: [1,2,-,-,3,4,-,-] 

Aquí llamamos a la función sin, las variables con id = 3 y 4 se alimentan a ella, y el resultado se escribe en las variables 1 y 2. Esta llamada corresponde al GLSL-th:

 vec2 a = sin(b); 

Tenga en cuenta los argumentos vacíos (marcados como "-"). En GLSL, casi todas las funciones integradas están sobrecargadas para diferentes conjuntos de tipos de entrada, es decir. hay sin(float) , sin(vec2) , sin(vec3) , sin(vec4) . Por conveniencia, traigo todas las versiones sobrecargadas a una forma, en este caso sin(vec4) .

El analizador genera una lista de cambios para cada variable, como

 cmdId: 10 branchId: 1 variable: 2 range: [-1,1] 

Lo que significa que "la variable 2 en la línea 10 en la rama 1 tiene un rango de -1 a 1 inclusive" (hablaremos de la rama un poco más adelante). Ahora puede resaltar hermosos rangos de valores en el código fuente.

Buen comienzo

Cuando el árbol AST ya ha comenzado a convertirse en una lista de comandos, es hora de implementar funciones y métodos estándar. Hay muchos de ellos (y también tienen un montón de sobrecargas, como escribí anteriormente), pero en general tienen transformaciones de rango predecibles. Digamos, por ejemplo, que todo resulta bastante obvio:

 uniform float angle; // -> (-∞,∞) //... float y = sin(angle); // -> [-1,1] float ynorm = 1 + y; // -> [0,2] gl_FragColor.r = ynorm / 2.; // -> [0,1] 

El canal rojo del color de salida está dentro del rango aceptable, no hay errores.

Si cubre más funciones incorporadas, entonces para la mitad de los sombreadores, tal análisis es suficiente. Pero, ¿qué pasa con la segunda mitad, con condiciones, bucles y funciones?

Ramas

Tomemos por ejemplo tal sombreador.

 uniform sampler2D uSampler; uniform vec2 uv; // [0,1] void main() { float a = texture2D(uSampler, uv).a; // -> [0,1] float k; // -> ? if (a < 0.5) { k = a * 2.; } else { k = 1. - a; } gl_FragColor = vec4(1.) * k; } 

La variable a se toma de la textura y, por lo tanto, el valor de esta variable se encuentra entre 0 y 1. Pero, ¿qué valores puede tomar k ?

Puede seguir el camino simple y “unir las ramas”: calcule el rango en cada uno de los casos y dé el total. Para la rama if, obtenemos k = [0,2] , y para la rama else, k = [0,1] . Si combina, resulta [0,2] , y necesita dar un error, porque los valores mayores que 1 caen en el color de salida de gl_FragColor .

Sin embargo, esta es una falsa alarma clara, y para un analizador estático no hay nada peor que las falsas alarmas: si no se apaga después del primer grito de "lobo", entonces seguramente después del décimo.

Por lo tanto, debemos procesar ambas ramas por separado, y en ambas ramas debemos aclarar el rango de la variable a (aunque formalmente no se ha cambiado). Así es como podría verse:

Rama 1:

 if (a < 0.5) { //a = [0, 0.5) k = a * 2.; //k = [0, 1) gl_FragColor = vec4(1.) * k; } 

Rama 2:

 if (a >= 0.5) { //a = [0.5, 1] k = 1. - a; //k = [0, 0.5] gl_FragColor = vec4(1.) * k; } 

Por lo tanto, cuando el analizador encuentra una determinada condición que se comporta de manera diferente según el rango, crea ramas (brunches) para cada uno de los casos. En cada caso, refina el rango de la variable fuente y se mueve hacia abajo en la lista de comandos.

Vale la pena aclarar que las ramas en este caso no están relacionadas con la construcción if-else. Las ramas se crean cuando un rango de una variable se divide en subrangos, y la causa puede ser una declaración condicional opcional. Por ejemplo, la función de paso también crea ramas. El siguiente sombreador GLSL hace lo mismo que el anterior, pero no usa ramificación (que, por cierto, es mejor en términos de rendimiento).

 float a = texture2D(uSampler, uv).a; float k = mix(a * 2., 1. - a, step(0.5, a)); gl_FragColor = vec4(1.) * k; 

La función de paso debería devolver 0 si a <0.5 y 1 de lo contrario. Por lo tanto, también se crearán ramas aquí, similar al ejemplo anterior.

Refinamiento de otras variables.

Considere un ejemplo anterior ligeramente modificado:

 float a = texture2D(uSampler, uv).a; // -> [0,1] float b = a - 0.5; // -> [-0.5, 0.5] if (b < 0.) { k = a * 2.; // k,a -> ? } else { k = 1. - a; } 

Aquí el matiz es el siguiente: la ramificación ocurre con respecto a la variable b , y los cálculos ocurren con la variable a . Es decir, dentro de cada rama habrá un valor correcto del rango b , pero completamente innecesario, y el valor original del rango a , completamente incorrecto.

Sin embargo, el analizador vio que el rango b se obtuvo calculando a partir de a . Si recuerda esta información, cuando ramifica, el analizador puede revisar todas las variables de origen y refinar su rango realizando el cálculo inverso.

Funciones y bucles

GLSL no tiene métodos virtuales, punteros de función o incluso llamadas recursivas, por lo que cada llamada de función es única. Por lo tanto, es más fácil insertar el cuerpo de la función en el lugar de la llamada (en línea, en otras palabras). Esto será completamente consistente con la secuencia de comandos.

Es más complicado con los ciclos, porque formalmente, GLSL es totalmente compatible con el bucle C-like. Sin embargo, con mayor frecuencia, los bucles se usan en la forma más simple, como esta:

 for (int i = 0; i < 12; i++) {} 

Dichos ciclos son fáciles de "desplegar", es decir inserte el cuerpo del bucle 12 veces uno tras otro. Como resultado, después de pensarlo, hasta ahora decidí apoyar solo esa opción.

La ventaja de este enfoque es que los comandos se pueden emitir en un flujo al analizador sin requerir que memorice ningún fragmento (como cuerpos de funciones o bucles) para su posterior reutilización.

Problemas emergentes

Problema # 1: dificultad o incapacidad para aclarar

Arriba, examinamos casos cuando, al refinar los valores de una variable, sacamos conclusiones sobre los valores de otra variable. Y este problema se resuelve cuando se involucran operaciones como la suma / resta. Pero, digamos, ¿qué hacer con la trigonometría? Por ejemplo, tal condición:

 float a = getSomeValue(); if (sin(a) > 0.) { //    a? } 

¿Cómo calcular el rango de a interior si? Resulta un conjunto interminable de rangos con pasos pi, que luego serán muy inconvenientes para trabajar.

Y puede haber tal situación:

 float a = getSomeValue(); // [-10,10] float b = getAnotherValue(); //[-20, 30] float k = a + b; if (k > 0) { //a? b? } 

Aclarar los rangos b en el caso general no será realista. Y, por lo tanto, los falsos positivos son posibles.

Problema # 2: rangos dependientes

Considere este ejemplo:

 uniform float value //-> [0,1]; void main() { float val2 = value - 1.; gl_FragColor = vec4(value - val2); } 

Para empezar, el analizador considera el rango de la variable val2 , y se espera que sea [0,1] - 1 == [-1, 0]

Sin embargo, entonces, considerando el value - val2 , el analizador no tiene en cuenta que val2 se obtuvo del value , y trabaja con rangos como si fueran independientes entre sí. Obtiene [0,1] - [-1,0] = [0,2] e informa un error. Aunque en realidad debería haber obtenido un 1 constante.

Posible solución: almacenar para cada variable no solo el historial de rangos, sino también todo el “árbol genealógico”: qué variables dependían, qué operaciones, etc. Otra cosa es que "desplegar" este pedigrí no será fácil.

Problema # 3: rangos implícitamente dependientes

Aquí hay un ejemplo:

 float k = sin(a) + cos(a); 

Aquí, el analizador supondrá que el rango k = [-1,1] + [-1,1] = [-2,2] . Lo cual está mal, porque sin(a) + cos(a) para cualquier a encuentra en el rango [-√2, √2] .

El resultado de calcular sin(a) formalmente no depende del resultado de calcular cos(a) . Sin embargo, dependen del mismo rango de a .

Resumen y conclusiones

Al final resultó que, hacer un análisis de rango de valores incluso para un lenguaje tan simple y altamente especializado como GLSL no es una tarea fácil. La cobertura de las características del lenguaje aún se puede fortalecer: admitir matrices, matrices y todas las operaciones integradas es una tarea puramente técnica que simplemente requiere mucho tiempo. Pero, ¿cómo resolver situaciones con dependencias entre variables? La pregunta todavía no está clara para mí. Sin resolver estos problemas, los falsos positivos son inevitables, cuyo ruido en última instancia puede superar los beneficios del análisis estático.

Dado lo que encontré, no estoy particularmente sorprendido por la ausencia de algunas herramientas bien conocidas para el análisis del rango de valores en otros idiomas: claramente hay más problemas en ellas que en el relativamente simple GLSL. Al mismo tiempo, puede escribir al menos pruebas unitarias en otros idiomas, pero aquí no puede hacerlo.

Una solución alternativa podría ser la compilación de otros idiomas en GLSL: aquí recientemente hubo un artículo sobre compilación de kotlin . Luego puede escribir pruebas unitarias para el código fuente y cubrir todas las condiciones de contorno. O haga un "analizador dinámico" que ejecute los mismos datos que van al sombreador a través del código kotlin original y advierte sobre posibles problemas.

Entonces en este punto me detuve. La biblioteca, por desgracia, no funcionó, pero tal vez este prototipo sea útil para alguien.

Repositorio en github, para su revisión:

• https://github.com/AlexeyGrishin/glsl-value-range-analysis

Para probar:

• https://alexeygrishin.imtqy.com/glsl-value-range-analysis/html/

Bonificación: características de ensamblaje web con diferentes indicadores de compilación

Inicialmente, hice el analizador sin usar stdlib, a la antigua usanza, con matrices y punteros. En ese momento estaba muy preocupado por el tamaño del archivo wasm de salida, quería que fuera pequeño. Pero a partir de algún punto comencé a sentir incomodidad y, por lo tanto, decidí transferir todo a stdlib: punteros inteligentes, colecciones normales, eso es todo.

En consecuencia, tuve la oportunidad de comparar los resultados de ensamblaje de dos versiones de la biblioteca, con y sin stdlib. Bueno, también vea cómo el buen / mal cheerp (y el sonido que usa) optimiza el código.

Por lo tanto, compilé ambas versiones con diferentes conjuntos de indicadores de optimización ( -O0 , -O0 , -O1 , -O2 , -Os y -Oz ), y para algunas de estas versiones -Oz la velocidad de análisis de 3000 operaciones con 1000 ramas. Estoy de acuerdo, no es el mejor ejemplo, pero en mi humilde opinión es suficiente para un análisis comparativo.

Lo que sucedió según el tamaño del archivo wasm:

Sorprendentemente, la opción de tamaño con la optimización "cero" es mejor que casi todas las demás. Asumiré que en O3 una línea agresiva de todo en el mundo, que infla el binario. La versión esperada sin stdlib es más compacta, pero no tanto que soportar tal humillación para privarse del placer de trabajar con colecciones convenientes.

Por velocidad de ejecución:

Ahora puedo ver que -O3 no -O3 en vano comer su pan, en comparación con -O0 . Al mismo tiempo, la diferencia entre versiones con y sin stdlib está prácticamente ausente (hice 10 mediciones, creo que con un número mayor la diferencia desaparecería por completo).

Vale la pena señalar 2 puntos:

• El gráfico muestra los valores promedio de 10 ejecuciones consecutivas del análisis, pero en todas las pruebas el primer análisis duró 2 veces más que el resto (es decir, 120 ms, y las siguientes ya estaban alrededor de 60 ms). Probablemente hubo alguna inicialización de WebAssembly.
• Con la bandera -O3 , agarré algunos errores terriblemente extraños que no atrapé para otras banderas. Por ejemplo, las funciones min y max de repente comenzaron a funcionar de la misma manera, como min.

Conclusión

Gracias a todos por su atención.
Deje que los valores de sus variables nunca vayan más allá de los límites.
Y aqui tienes.