Comment j'ai essayé de faire un analyseur statique GLSL (et ce qui n'a pas fonctionné)

Une fois, je me préparais pour Ludum Dare et j'ai fait un jeu simple où j'utilisais des pixel shaders (d'autres n'étaient pas intégrés au moteur Phaser).

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

Après les tests, j'ai jeté le lien à un ami et reçu de lui une telle capture d'écran avec la question "est-ce normal?"

Non, ce n'était pas normal. Après avoir examiné attentivement le code du shader, j'ai trouvé une erreur de calcul:

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

Parce que Puisque la constante R1 était inférieure à M, dans certains cas, le résultat dans le premier argument de pow était un nombre inférieur à zéro. La racine carrée du nombre négatif est une chose mystérieuse, du moins pour la norme GLSL. Ma carte vidéo n'était pas confuse, et elle est en quelque sorte sortie de cette position (il semble l'avoir retournée de la puissance 0), mais elle s'est avérée plus lisible pour un ami.

Et puis j'ai pensé: puis-je éviter de tels problèmes à l'avenir? Personne n'est à l'abri des erreurs, en particulier celles qui ne sont pas reproduites localement. Vous ne pouvez pas écrire de tests unitaires pour GLSL. En même temps, les transformations à l'intérieur du shader sont assez simples - multiplication, division, sinus, cosinus ... Est-il vraiment impossible de suivre les valeurs de chaque variable et de s'assurer qu'en aucun cas elle ne dépasse les limites de valeurs autorisées?

J'ai donc décidé d'essayer de faire une analyse statique pour GLSL. Ce qui en est ressorti - vous pouvez le lire sous la coupe.

Je vous préviens tout de suite: je n'ai pu obtenir aucun produit fini, seulement un prototype pédagogique.

Analyse préliminaire

Après avoir étudié un peu des articles existants sur ce sujet (et découvert simultanément que le sujet s'appelle Value Range Analysis), j'étais heureux d'avoir GLSL, et pas une autre langue. Jugez par vous-même:

• pas de «dynamique» - références aux fonctions, interfaces, types déduits automatiquement, etc.
• pas de gestion directe de la mémoire
• pas de modules, liaison, liaison tardive - tout le code source du shader est disponible
  les plages sont généralement bien connues pour les valeurs d'entrée
• quelques types de données, et ceux-ci tournent autour d'un flotteur. int / bool sont rarement utilisés, et ce n'est pas si important de les suivre
• les ifs et les boucles sont rarement utilisés (en raison de problèmes de performances). les boucles, si elles sont utilisées, sont souvent de simples compteurs pour parcourir un tableau ou répéter un certain effet plusieurs fois. Personne n'écrira une telle horreur en GLSL (j'espère).

 //   - 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 général, étant donné les limites de GLSL, la tâche semble être résoluble. L'algorithme principal est le suivant:

1. analyser le code du shader et créer une séquence de commandes qui modifient les valeurs des variables
2. connaître les plages initiales des variables, parcourir la séquence, mettre à jour les plages lorsqu'elles changent
3. si la plage viole des limites données (par exemple, un nombre négatif peut arriver, ou quelque chose de plus grand que 1 arrivera à la "couleur de sortie" gl_FragColor dans le composant rouge), vous devez afficher un avertissement

Technologies utilisées

Ici, j'ai eu un choix long et douloureux. D'une part, mon objectif principal est de vérifier les shaders WebGL, alors pourquoi ne pas javascript pour tout exécuter dans le navigateur pendant le développement. D'un autre côté, j'ai prévu de quitter Phaser depuis longtemps et d'essayer un autre moteur comme Unity ou LibGDX. Il y aura également des shaders, mais javascript aura disparu.

Et d'autre part, la tâche a été faite principalement pour le divertissement. Et le meilleur divertissement au monde est le zoo. Par conséquent:

1. Analyse du code GLSL effectuée en javascript. C'est juste que j'ai trouvé assez rapidement la bibliothèque pour analyser GLSL dans AST, et l'interface utilisateur de test semble être plus familière avec le Web. AST se transforme en une séquence de commandes, qui est envoyée à ...
2. ... la deuxième partie, qui est écrite en C ++ et compilée dans WebAssembly. J'ai décidé de cette façon: si je veux soudainement fixer cet analyseur à un autre moteur, avec une bibliothèque C ++, cela devrait être fait le plus simplement.

Tout, maintenant vous pouvez partir.

En bref sur le modèle

L'analyseur conserve en mémoire une liste de variables qui se trouvent dans le shader, et pour chacune il stocke la plage de valeurs possible actuelle (comme [0,1] ou [1,∞) ).

L'analyseur reçoit un flux de travail comme celui-ci:

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

Ici, nous appelons la fonction sin, les variables avec id = 3 et 4 y sont introduites et le résultat est écrit dans les variables 1 et 2. Cet appel correspond à la GLSL-th:

 vec2 a = sin(b); 

Notez les arguments vides (marqués comme "-"). Dans GLSL, presque toutes les fonctions intégrées sont surchargées pour différents ensembles de types d'entrée, c'est-à-dire il y a le sin(float) , le sin(vec2) , le sin(vec3) , le sin(vec4) . Pour plus de commodité, sin(vec4) toutes les versions surchargées sous une seule forme - dans ce cas, sin(vec4) .

L'analyseur génère une liste de modifications pour chaque variable, comme

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

Ce qui signifie que "la variable 2 de la ligne 10 de la branche 1 a une plage de -1 à 1 inclus" (nous parlerons de la branche un peu plus loin). Maintenant, vous pouvez magnifiquement mettre en évidence des plages de valeurs dans le code source.

Bon début

Lorsque l'arborescence AST a déjà commencé à se transformer en une liste de commandes, il est temps d'implémenter des fonctions et des méthodes standard. Il y en a beaucoup (et ils ont aussi un tas de surcharges, comme je l'ai écrit ci-dessus), mais en général, ils ont des transformations de plage prévisibles. Disons que, pour un tel exemple, tout se passe assez clairement:

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

Le canal rouge de la couleur de sortie est dans la plage acceptable, il n'y a pas d'erreur.

Si vous couvrez plus de fonctions intégrées, alors pour la moitié des shaders, une telle analyse suffit. Mais qu'en est-il de la seconde moitié - avec des conditions, des boucles et des fonctions?

Succursales

Prenons par exemple un tel shader.

 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 est tirée de la texture, et donc la valeur de cette variable se situe de 0 à 1. Mais quelles valeurs peut k prendre?

Vous pouvez suivre la voie simple et «unir les branches» - calculer la plage dans chacun des cas et donner le total. Pour la branche if, nous obtenons k = [0,2] , et pour la branche else, k = [0,1] . Si vous combinez, il s'avère [0,2] , et vous devez donner une erreur, car les valeurs supérieures à 1 tombent dans la couleur de sortie de gl_FragColor .

Cependant, il s'agit d'une fausse alarme claire, et pour un analyseur statique, il n'y a rien de pire que les fausses alarmes - si elles ne sont pas désactivées après le premier cri de "loup", puis après le dixième à coup sûr.

Donc, nous devons traiter les deux branches séparément, et dans les deux branches, nous devons clarifier la plage de la variable a (bien qu'elle n'ait pas été officiellement modifiée). Voici à quoi cela pourrait ressembler:

Branche 1:

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

Branche 2:

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

Ainsi, lorsque l'analyseur rencontre une certaine condition qui se comporte différemment selon la plage, il crée des branches (brunchs) pour chacun des cas. Dans chaque cas, il affine la plage de la variable source et descend plus bas dans la liste des commandes.

Il convient de préciser que les branches dans ce cas ne sont pas liées à la construction if-else. Les branches sont créées lorsqu'une plage d'une variable est divisée en sous-plages, et la cause peut être une instruction conditionnelle facultative. Par exemple, la fonction step crée également des branches. Le shader GLSL suivant fait la même chose que le précédent, mais n'utilise pas de branchement (qui, soit dit en passant, est meilleur en termes de performances).

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

La fonction step doit retourner 0 si a <0,5 et 1 sinon. Par conséquent, des branches seront également créées ici - comme dans l'exemple précédent.

Affinement d'autres variables

Prenons un exemple précédent légèrement modifié:

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

Ici, la nuance est la suivante: la ramification se produit par rapport à la variable b et les calculs se produisent avec la variable a . Autrement dit, à l'intérieur de chaque branche, il y aura une valeur correcte de la plage b , mais complètement inutile, et la valeur d'origine de la plage a , complètement incorrecte.

Cependant, l'analyseur a vu que la plage b était obtenue en calculant à partir de a . Si vous vous souvenez de ces informations, lors de la ramification, l'analyseur peut parcourir toutes les variables source et affiner leur plage en effectuant le calcul inverse.

Fonctions et boucles

GLSL n'a pas de méthodes virtuelles, de pointeurs de fonction ou même d'appels récursifs, donc chaque appel de fonction est unique. Par conséquent, il est plus facile d'insérer le corps de la fonction à l'endroit de l'appel (en ligne, en d'autres termes). Cela sera parfaitement cohérent avec la séquence de commandes.

C'est plus compliqué avec les cycles, car formellement, GLSL prend entièrement en charge la boucle for de type C. Cependant, le plus souvent, les boucles sont utilisées sous la forme la plus simple, comme ceci:

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

De tels cycles sont faciles à «déployer», c'est-à-dire insérer le corps de la boucle 12 fois l'un après l'autre. En conséquence, après avoir réfléchi, j'ai décidé jusqu'à présent de ne soutenir qu'une telle option.

L'avantage de cette approche est que des commandes peuvent être émises dans un flux vers l'analyseur sans qu'il soit nécessaire de mémoriser des fragments (tels que des corps de fonction ou des boucles) pour une réutilisation ultérieure.

Problèmes pop-up

Problème n ° 1: difficulté ou incapacité à clarifier

Ci-dessus, nous avons examiné des cas où, lors du raffinement des valeurs d'une variable, nous avons tiré des conclusions sur les valeurs d'une autre variable. Et ce problème est résolu lorsque des opérations telles que l'addition / la soustraction sont impliquées. Mais, disons, que faire de la trigonométrie? Par exemple, une telle condition:

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

Comment calculer la portée d' a intérieur si? Il s'avère qu'un ensemble infini de plages avec des étapes pi, qui sera alors très gênant pour travailler avec.

Et il peut y avoir une telle situation:

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

Clarifier les plages a et b dans le cas général sera irréaliste. Et, par conséquent, les faux positifs sont possibles.

Problème n ° 2: plages dépendantes

Considérez cet exemple:

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

Pour commencer, l'analyseur considère la plage de la variable val2 - et elle devrait être [0,1] - 1 == [-1, 0]

Cependant, compte tenu de la value - val2 , l'analyseur ne tient pas compte du fait que val2 été obtenu à partir de la value et fonctionne avec des plages comme si elles étaient indépendantes les unes des autres. Obtient [0,1] - [-1,0] = [0,2] et signale une erreur. Bien qu'en réalité, il aurait dû avoir un 1 constant.

Solution possible: pour stocker pour chaque variable non seulement l'historique des plages, mais aussi l'ensemble de «l'arbre généalogique» - de quelles variables dépendaient, de quelles opérations, etc. Une autre chose est que «déplier» ce pedigree ne sera pas facile.

Problème n ° 3: plages implicitement dépendantes

Voici un exemple:

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

Ici, l'analyseur supposera que la plage k = [-1,1] + [-1,1] = [-2,2] . Ce qui est faux, car sin(a) + cos(a) pour tout a se situe dans la plage [-√2, √2] .

Le résultat du calcul de sin(a) ne dépend pas formellement du résultat du calcul de cos(a) . Cependant, ils dépendent de la même plage de a .

Résumé et conclusions

Il s'est avéré que faire une analyse de la plage de valeurs même pour un langage aussi simple et hautement spécialisé que GLSL n'est pas une tâche facile. La couverture des fonctionnalités du langage peut encore être renforcée: la prise en charge des tableaux, des matrices et de toutes les opérations intégrées est une tâche purement technique qui nécessite simplement beaucoup de temps. Mais comment résoudre des situations avec des dépendances entre variables - la question n'est toujours pas claire pour moi. Sans résoudre ces problèmes, les faux positifs sont inévitables, dont le bruit peut finalement l'emporter sur les avantages de l'analyse statique.

Compte tenu de ce que j'ai rencontré, je ne suis pas particulièrement surpris de l'absence d'outils bien connus pour l'analyse de la plage de valeurs dans d'autres langues - il y a clairement plus de problèmes en eux que dans le GLSL relativement simple. Dans le même temps, vous pouvez écrire au moins des tests unitaires dans d'autres langues, mais ici vous ne pouvez pas le faire.

Une solution alternative pourrait être la compilation à partir d'autres langues dans GLSL - récemment, il y avait un article sur la compilation à partir de kotlin . Ensuite, vous pouvez écrire des tests unitaires pour le code source et couvrir toutes les conditions aux limites. Ou créez un «analyseur dynamique» qui exécutera les mêmes données qui vont au shader via le code kotlin d'origine et avertira des problèmes possibles.

Alors à ce stade, je me suis arrêté. La bibliothèque, hélas, n'a pas fonctionné, mais peut-être que ce prototype est utile à quelqu'un.

Dépôt sur github, pour examen:

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

Pour essayer:

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

Bonus: fonctionnalités d'assemblage Web avec différents drapeaux de compilation

Au départ, j'ai fait l'analyseur sans utiliser stdlib - à l'ancienne, avec des tableaux et des pointeurs. A cette époque, j'étais très inquiet de la taille du fichier wasm de sortie, je voulais qu'il soit petit. Mais à partir d'un moment donné, j'ai commencé à ressentir de l'inconfort et j'ai donc décidé de tout transférer vers stdlib - des pointeurs intelligents, des collections normales, c'est tout.

En conséquence, j'ai eu l'occasion de comparer les résultats de l'assemblage de deux versions de la bibliothèque - avec et sans stdlib. Eh bien, voyez également comment le bon / mauvais cheerp (et le bruit qu'il utilise) optimise le code.

Par conséquent, j'ai compilé les deux versions avec différents ensembles d'indicateurs d'optimisation ( -O0 , -O1 , -O2 , -O3 , -Os et -Oz ), et pour certaines de ces versions, j'ai mesuré la vitesse d'analyse de 3000 opérations avec 1000 branches. Je suis d'accord, pas le plus grand exemple, mais à mon humble avis est suffisant pour une analyse comparative.

Que s'est-il passé en fonction de la taille du fichier wasm:

Étonnamment, l'option de taille avec l'optimisation «zéro» est meilleure que presque toutes les autres. Je suppose que dans O3 y a une ligne agressive de tout dans le monde, ce qui gonfle le binaire. La version attendue sans stdlib est plus compacte, mais pas tant que supporter une telle humiliation pour vous priver du plaisir de travailler avec des collections pratiques.

Par vitesse d'exécution:

Maintenant, je peux voir que -O3 ne mange pas en vain son pain, par rapport à -O0 . En même temps, la différence entre les versions avec et sans stdlib est pratiquement absente (j'ai fait 10 mesures, je pense qu'avec un plus grand nombre la différence disparaîtrait complètement).

Il convient de noter 2 points:

• Le graphique montre les valeurs moyennes de 10 exécutions consécutives de l'analyse, mais dans tous les tests, la toute première analyse a duré 2 fois plus longtemps que les autres (c'est-à-dire, 120 ms, et les suivantes étaient déjà autour de 60 ms). Il y a probablement eu une initialisation de WebAssembly.
• Avec le drapeau -O3 , j'ai attrapé des bugs terriblement étranges que je n'ai pas attrapés pour d'autres drapeaux. Par exemple, les fonctions min et max ont soudainement commencé à fonctionner de la même manière - comme min.

Conclusion

Merci à tous pour votre attention.
Ne laissez jamais les valeurs de vos variables dépasser les limites.
Et voilà.