Wie ich versucht habe, einen statischen GLSL-Analysator herzustellen (und was schief gelaufen ist)

Einmal bereitete ich mich auf Ludum Dare vor und machte ein einfaches Spiel, in dem ich Pixel-Shader verwendete (andere wurden nicht in die Phaser-Engine aufgenommen).

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

Nach dem Testen warf ich den Link zu einem Freund und erhielt von ihm einen solchen Screenshot mit der Frage "Ist das normal?"

Nein, das war nicht normal. Nachdem ich mir den Shader-Code genau angesehen hatte, stellte ich einen Berechnungsfehler fest:

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

Weil Da die Konstante R1 kleiner als M war, war in einigen Fällen das Ergebnis im ersten Argument von pow eine Zahl kleiner als Null. Die Quadratwurzel der negativen Zahl ist zumindest für den GLSL-Standard eine mysteriöse Sache. Meine Grafikkarte war nicht verwirrt und kam irgendwie aus dieser Position heraus (es scheint, als hätte sie von pow 0 zurückgegeben), aber es stellte sich heraus, dass sie für einen Freund besser lesbar war.

Und dann dachte ich: Kann ich solche Probleme in Zukunft vermeiden? Niemand ist vor Fehlern sicher, insbesondere solche, die nicht lokal reproduziert werden. Sie können keine Komponententests für GLSL schreiben. Gleichzeitig sind die Transformationen innerhalb des Shaders recht einfach - Multiplikation, Division, Sinus, Cosinus ... Ist es wirklich unmöglich, die Werte jeder Variablen zu verfolgen und sicherzustellen, dass sie unter keinen Umständen die zulässigen Werte überschreiten?

Deshalb habe ich mich entschlossen, eine statische Analyse für GLSL durchzuführen. Was dabei herauskam - Sie können es unter dem Schnitt lesen.

Ich warne Sie sofort: Ich konnte kein fertiges Produkt bekommen, nur einen pädagogischen Prototyp.

Vorläufige Analyse

Nachdem ich einige der vorhandenen Artikel zu diesem Thema studiert hatte (und gleichzeitig herausgefunden hatte, dass das Thema Wertbereichsanalyse heißt), war ich froh, dass ich GLSL und keine andere Sprache hatte. Überzeugen Sie sich selbst:

• keine "Dynamik" - Verweise auf Funktionen, Schnittstellen, automatisch abgeleitete Typen usw.
• Keine direkte Speicherbehandlung
• Keine Module, Verknüpfung, späte Bindung - der gesamte Quellcode des Shaders ist verfügbar
  Bereiche sind allgemein für Eingabewerte bekannt
• wenige Datentypen, und diese drehen sich um einen Float. int / bool werden selten verwendet und es ist nicht so wichtig, ihnen zu folgen
• ifs und Schleifen werden selten verwendet (aufgrund von Leistungsproblemen). Wenn Schleifen verwendet werden, handelt es sich häufig um einfache Zähler, mit denen Sie ein Array durchlaufen oder einen bestimmten Effekt mehrmals wiederholen können. Niemand wird solch einen Horror in GLSL schreiben (ich hoffe).

 //   - 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 

Angesichts der Einschränkungen von GLSL scheint die Aufgabe im Allgemeinen lösbar zu sein. Der Hauptalgorithmus lautet wie folgt:

1. Analysieren Sie den Shader-Code und erstellen Sie eine Folge von Befehlen, die die Werte beliebiger Variablen ändern
2. Wenn Sie die Anfangsbereiche für die Variablen kennen, gehen Sie die Sequenz durch und aktualisieren Sie die Bereiche, wenn sie sich ändern
3. Wenn der Bereich eine bestimmte Grenze überschreitet (z. B. kann eine negative Zahl zu pow kommen oder etwas größer als 1 zur "Ausgabefarbe" gl_FragColor in der roten Komponente), müssen Sie eine Warnung anzeigen

Verwendete Technologien

Hier hatte ich eine lange und schmerzhafte Wahl. Einerseits besteht mein Hauptbereich darin, WebGL-Shader zu überprüfen. Warum also nicht Javascript, um während der Entwicklung alles im Browser auszuführen? Andererseits habe ich schon lange vor, Phaser zu verlassen und eine andere Engine wie Unity oder LibGDX auszuprobieren. Es wird auch Shader geben, aber Javascript wird weg sein.

Und andererseits wurde die Aufgabe hauptsächlich zur Unterhaltung erledigt. Und die beste Unterhaltung der Welt ist der Zoo. Deshalb:

1. GLSL-Code-Analyse in Javascript. Es ist nur so, dass ich ziemlich schnell die Bibliothek zum Parsen von GLSL in AST gefunden habe und die Test-Benutzeroberfläche vertrauter zu sein scheint als das Web. AST wird zu einer Folge von Befehlen, die an ...
2. ... der zweite Teil, der in C ++ geschrieben und in WebAssembly kompiliert ist. Ich habe mich folgendermaßen entschieden: Wenn ich diesen Analysator plötzlich an einer anderen Engine befestigen möchte, sollte dies mit einer C ++ - Bibliothek am einfachsten erfolgen.

Alles, jetzt kannst du gehen.

Kurz zum Modell

Der Analysator speichert eine Liste der im Shader gefundenen Variablen im Speicher und speichert für jede Variable den aktuell möglichen Wertebereich (z. B. [0,1] oder [1,∞) ).

Der Analysator erhält einen Workflow wie folgt:

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

Hier rufen wir die sin-Funktion auf, die Variablen mit id = 3 und 4 werden ihr zugeführt, und das Ergebnis wird in die Variablen 1 und 2 geschrieben. Dieser Aufruf entspricht dem GLSL-ten:

 vec2 a = sin(b); 

Beachten Sie die leeren Argumente (markiert als "-"). In GLSL sind fast alle integrierten Funktionen für verschiedene Sätze von Eingabetypen überladen, d. H. Es gibt sin(float) , sin(vec2) , sin(vec3) , sin(vec4) . Der sin(vec4) bringe ich alle überladenen Versionen in eine Form - in diesem Fall sin(vec4) .

Der Analysator gibt eine Liste von Änderungen für jede Variable aus, wie z

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

Dies bedeutet, dass "die Variable 2 in Zeile 10 in Zweig 1 einen Bereich von -1 bis einschließlich 1 hat" (wir werden etwas später über Zweig sprechen). Jetzt können Sie Wertebereiche im Quellcode wunderschön hervorheben.

Guter Start

Wenn der AST-Baum bereits zu einer Liste von Befehlen geworden ist, ist es an der Zeit, Standardfunktionen und -methoden zu implementieren. Es gibt ziemlich viele von ihnen (und sie haben auch eine Reihe von Überlastungen, wie ich oben geschrieben habe), aber im Allgemeinen haben sie vorhersehbare Bereichstransformationen. Nehmen wir an, für ein solches Beispiel ist alles ziemlich offensichtlich:

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

Der rote Kanal der Ausgabefarbe liegt im akzeptablen Bereich, es liegen keine Fehler vor.

Wenn Sie mehr integrierte Funktionen abdecken, reicht eine solche Analyse für die Hälfte der Shader aus. Aber was ist mit der zweiten Hälfte - mit Bedingungen, Schleifen und Funktionen?

Zweige

Nehmen Sie zum Beispiel einen solchen 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; } 

Die Variable a wird aus der Textur entnommen, und daher liegt der Wert dieser Variablen zwischen 0 und 1. Aber welche Werte kann k annehmen?

Sie können den einfachen Weg gehen und „die Zweige vereinen“ - berechnen Sie die Reichweite in jedem Fall und geben Sie die Summe aus. Für den if-Zweig erhalten wir k = [0,2] und für den else-Zweig k = [0,1] . Wenn Sie kombinieren, stellt sich heraus, dass [0,2] und Sie einen Fehler machen müssen, weil Werte größer als 1 fallen in die Ausgabefarbe von gl_FragColor .

Dies ist jedoch ein eindeutiger Fehlalarm, und für einen statischen Analysator gibt es nichts Schlimmeres als Fehlalarme - wenn er nicht nach dem ersten Schrei des "Wolfs" ausgeschaltet wird, dann sicher nach dem zehnten.

Wir müssen also beide Zweige getrennt verarbeiten und in beiden Zweigen den Bereich der Variablen a klären (obwohl sie formal nicht geändert wurde). So könnte es aussehen:

Zweig 1:

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

Zweig 2:

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

Wenn der Analysator auf eine bestimmte Bedingung stößt, die sich je nach Bereich unterschiedlich verhält, werden für jeden Fall Verzweigungen (Brunchs) erstellt. In jedem Fall verfeinert er den Bereich der Quellvariablen und bewegt sich weiter unten in der Befehlsliste.

Es ist klarstellbar, dass die Zweige in diesem Fall nicht mit dem if-else-Konstrukt zusammenhängen. Verzweigungen werden erstellt, wenn ein Bereich einer Variablen in Unterbereiche unterteilt ist. Die Ursache kann eine optionale bedingte Anweisung sein. Beispielsweise erstellt die Schrittfunktion auch Zweige. Der nächste GLSL-Shader macht dasselbe wie der vorherige, verwendet jedoch keine Verzweigung (was übrigens in Bezug auf die Leistung besser ist).

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

Die Schrittfunktion sollte 0 zurückgeben, wenn a <0,5 und andernfalls 1. Daher werden hier auch Zweige angelegt - ähnlich wie im vorherigen Beispiel.

Verfeinerung anderer Variablen

Betrachten Sie ein leicht modifiziertes vorheriges Beispiel:

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

Hier ist die Nuance wie folgt: Verzweigung tritt in Bezug auf Variable b , und Berechnungen erfolgen in Bezug auf Variable b . Das heißt, in jedem Zweig gibt es einen korrekten Wert des Bereichs b , der jedoch völlig unnötig ist, und den ursprünglichen Wert des Bereichs a ist völlig falsch.

Der Analysator sah jedoch, dass der Bereich b durch Berechnen aus a . Wenn Sie sich an diese Informationen erinnern, kann der Analysator beim Verzweigen alle Quellvariablen durchgehen und ihren Bereich durch Ausführen der inversen Berechnung verfeinern.

Funktionen und Schleifen

GLSL verfügt nicht über virtuelle Methoden, Funktionszeiger oder sogar rekursive Aufrufe, sodass jeder Funktionsaufruf eindeutig ist. Daher ist es am einfachsten, den Funktionskörper am Ort des Aufrufs einzufügen (mit anderen Worten inline). Dies stimmt vollständig mit der Reihenfolge der Befehle überein.

Bei Zyklen ist es komplizierter, weil Formal unterstützt GLSL die C-ähnliche for-Schleife vollständig. In den meisten Fällen werden Schleifen jedoch in der einfachsten Form verwendet:

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

Solche Zyklen sind leicht "bereitzustellen", d.h. Führen Sie den Körper der Schleife 12 Mal nacheinander ein. Nachdem ich darüber nachgedacht hatte, entschied ich mich bisher, nur eine solche Option zu unterstützen.

Der Vorteil dieses Ansatzes besteht darin, dass Befehle in einem Stream an den Analysator ausgegeben werden können, ohne dass Fragmente (wie Funktionskörper oder Schleifen) zur weiteren Wiederverwendung gespeichert werden müssen.

Pop-up-Probleme

Problem Nr. 1: Schwierigkeit oder Unfähigkeit zu klären

Oben haben wir Fälle untersucht, in denen wir beim Verfeinern der Werte einer Variablen Schlussfolgerungen über die Werte einer anderen Variablen gezogen haben. Und dieses Problem wird gelöst, wenn Operationen wie Addition / Subtraktion beteiligt sind. Aber was tun mit Trigonometrie? Zum Beispiel eine solche Bedingung:

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

Wie berechnet man die Reichweite a Innenraums, wenn? Es stellt sich eine endlose Reihe von Bereichen mit pi-Schritten heraus, mit denen dann sehr unpraktisch gearbeitet werden kann.

Und es kann eine solche Situation geben:

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

Die Klärung der Bereiche a und b im allgemeinen Fall ist unrealistisch. Und deshalb sind Fehlalarme möglich.

Problem Nr. 2: Abhängige Bereiche

Betrachten Sie dieses Beispiel:

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

Zunächst berücksichtigt der Analysator den Bereich der Variablen val2 - und es wird erwartet, dass er [0,1] - 1 == [-1, 0] beträgt.

In value - val2 des value - val2 berücksichtigt der Analysator jedoch nicht, dass val2 aus dem value , und arbeitet mit Bereichen, als ob sie unabhängig voneinander wären. Ruft [0,1] - [-1,0] = [0,2] und meldet einen Fehler. Obwohl er in Wirklichkeit eine Konstante 1 haben sollte.

Mögliche Lösung: Speichern Sie für jede Variable nicht nur den Verlauf der Bereiche, sondern auch den gesamten „Stammbaum“ - von welchen Variablen abhängig war, von welchen Operationen usw. Eine andere Sache ist, dass es nicht einfach sein wird, diesen Stammbaum zu „entfalten“.

Problem Nr. 3: Implizit abhängige Bereiche

Hier ist ein Beispiel:

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

Hier nimmt der Analysator an, dass der Bereich k = [-1,1] + [-1,1] = [-2,2] . Welches ist falsch, weil sin(a) + cos(a) für jedes a liegt im Bereich [-√2, √2] .

Das Ergebnis der formalen Berechnung von sin(a) hängt nicht vom Ergebnis der Berechnung von cos(a) . Sie hängen jedoch vom gleichen Bereich von a .

Zusammenfassung und Schlussfolgerungen

Wie sich herausstellte, ist es keine leichte Aufgabe, eine Wertebereichsanalyse auch für eine so einfache und hochspezialisierte Sprache wie GLSL durchzuführen. Die Abdeckung von Sprachfunktionen kann noch verbessert werden: Die Unterstützung von Arrays, Matrizen und allen integrierten Operationen ist eine rein technische Aufgabe, die lediglich zeitaufwändig ist. Aber wie man Situationen mit Abhängigkeiten zwischen Variablen löst - die Frage ist mir noch unklar. Ohne diese Probleme zu lösen, sind Fehlalarme unvermeidlich, deren Rauschen letztendlich die Vorteile der statischen Analyse überwiegen kann.

Angesichts dessen, was mir begegnet ist, wundert es mich nicht besonders, dass einige bekannte Tools für die Wertebereichsanalyse in anderen Sprachen fehlen - sie weisen eindeutig mehr Probleme auf als die relativ einfache GLSL. Gleichzeitig können Sie mindestens Komponententests in anderen Sprachen schreiben, aber hier können Sie dies nicht tun.

Eine alternative Lösung könnte das Kompilieren aus anderen Sprachen in GLSL sein - hier gab es kürzlich einen Artikel über das Kompilieren aus Kotlin . Anschließend können Sie Unit-Tests für den Quellcode schreiben und alle Randbedingungen abdecken. Oder erstellen Sie einen „dynamischen Analysator“, der dieselben Daten ausführt, die über den ursprünglichen Kotlin-Code an den Shader gesendet werden, und vor möglichen Problemen warnt.

Also hörte ich an diesem Punkt auf. Die Bibliothek hat leider nicht funktioniert, aber vielleicht ist dieser Prototyp für jemanden nützlich.

Repository auf Github, zur Überprüfung:

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

Um zu versuchen:

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

Bonus: Webassembly-Funktionen mit verschiedenen Compiler-Flags

Anfangs habe ich den Analysator ohne Verwendung von stdlib durchgeführt - auf altmodische Weise mit Arrays und Zeigern. Zu dieser Zeit war ich sehr besorgt über die Größe der Ausgabe-Wasm-Datei, ich wollte, dass sie klein ist. Aber ab einem bestimmten Zeitpunkt fühlte ich mich unwohl und beschloss daher, alles auf stdlib zu übertragen - intelligente Zeiger, normale Sammlungen, das ist alles.

Dementsprechend hatte ich die Möglichkeit, die Ergebnisse der Zusammenstellung von zwei Versionen der Bibliothek zu vergleichen - mit und ohne stdlib. Sehen Sie auch, wie guter / schlechter Cheerp (und das von ihm verwendete Klirren) den Code optimiert.

Daher habe ich beide Versionen mit unterschiedlichen Sätzen von Optimierungsflags ( -O0 , -O1 , -O2 , -O3 , -Os und -Oz ) -Oz und für einige dieser Versionen die Analysegeschwindigkeit von 3.000 Operationen mit 1.000 Zweigen gemessen. Ich stimme zu, nicht das größte Beispiel, aber IMHO reicht für eine vergleichende Analyse.

Was geschah je nach Größe der WASM-Datei:

Überraschenderweise ist die Größenoption mit der "Null" -Optimierung besser als fast alle anderen. Ich gehe davon aus, dass es in O3 eine aggressive Inline von allem auf der Welt gibt, die die Binärdatei aufbläst. Die erwartete Version ohne stdlib ist kompakter, aber nicht so sehr solche Demütigung ertragen um sich der Freude zu berauben, mit praktischen Sammlungen zu arbeiten.

Nach Ausführungsgeschwindigkeit:

Jetzt kann ich sehen, dass -O3 im Vergleich zu -O0 nicht umsonst sein Brot -O0 . Gleichzeitig fehlt der Unterschied zwischen Versionen mit und ohne stdlib praktisch (ich habe 10 Messungen durchgeführt, ich denke, bei einer größeren Zahl würde der Unterschied insgesamt verschwinden).

Es ist erwähnenswert, 2 Punkte:

• Das Diagramm zeigt die Durchschnittswerte aus 10 aufeinanderfolgenden Durchläufen der Analyse. In allen Tests dauerte die allererste Analyse jedoch zweimal länger als die übrigen (d. H. 120 ms, und die nächsten waren bereits etwa 60 ms). Es gab wahrscheinlich eine Initialisierung von WebAssembly.
• Mit der -O3 Flagge habe ich einige schrecklich seltsame Fehler entdeckt, die ich für andere Flaggen nicht gefunden habe. Zum Beispiel begannen die Min- und Max-Funktionen plötzlich auf die gleiche Weise zu funktionieren - wie Min.

Fazit

Vielen Dank für Ihre Aufmerksamkeit.
Lassen Sie die Werte Ihrer Variablen niemals über die Grenzen hinausgehen.
Und los geht's.