Bagaimana saya mencoba membuat analisa statis GLSL (dan apa yang salah)

Suatu ketika saya sedang mempersiapkan Ludum Dare dan membuat game sederhana di mana saya menggunakan pixel shaders (yang lain tidak dibawa ke mesin Phaser).

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

Setelah pengujian, saya melemparkan tautan ke seorang teman, dan menerima tangkapan layar darinya dengan pertanyaan "apakah ini normal?"

Tidak, itu tidak normal. Setelah memperhatikan kode shader dengan cermat, saya menemukan kesalahan perhitungan:

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

Karena Karena R1 konstan kurang dari M, dalam beberapa kasus hasil dalam argumen pertama pow adalah angka kurang dari nol. Akar kuadrat dari angka negatif adalah hal yang misterius, setidaknya untuk standar GLSL. Kartu video saya tidak bingung, dan entah bagaimana ia keluar dari posisi ini (tampaknya, setelah kembali dari pow 0), tetapi ternyata lebih terbaca oleh seorang teman.

Dan kemudian saya berpikir: bisakah saya menghindari masalah seperti itu di masa depan? Tidak ada yang aman dari kesalahan, terutama yang tidak direproduksi secara lokal. Anda tidak dapat menulis unit test untuk GLSL. Pada saat yang sama, transformasi di dalam shader cukup sederhana - perkalian, pembagian, sinus, cosinus ... Apakah benar-benar mustahil untuk melacak nilai-nilai setiap variabel dan memastikan bahwa dalam keadaan apa pun ia melampaui batas-batas nilai yang diizinkan?

Jadi saya memutuskan untuk mencoba melakukan analisis statis untuk GLSL. Apa yang terjadi - Anda dapat membacanya di bawah potongan.

Saya akan segera memperingatkan Anda: Saya tidak bisa mendapatkan produk jadi, hanya prototipe pendidikan.

Analisis pendahuluan

Setelah mempelajari sedikit artikel yang ada tentang topik ini (dan menemukan bahwa topik tersebut disebut Analisis Rentang Nilai), saya senang bahwa saya memiliki GLSL, dan bukan bahasa lain. Nilailah sendiri:

• no "dynamics" - referensi ke fungsi, antarmuka, tipe yang disimpulkan secara otomatis, dll.
• tidak ada penanganan memori langsung
• tidak ada modul, yang menghubungkan, mengikat akhir - seluruh kode sumber shader tersedia
  rentang umumnya dikenal untuk nilai input
• beberapa tipe data, dan yang berputar di sekitar float. int / bool jarang digunakan, dan tidak begitu penting untuk mengikutinya
• seandainya loop jarang digunakan (karena masalah kinerja). loop, jika digunakan, sering kali merupakan penghitung sederhana untuk melalui array atau mengulangi efek tertentu beberapa kali. Tidak ada yang akan menulis kengerian seperti itu di GLSL (saya harap).

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

Secara umum, mengingat keterbatasan GLSL, tugas tampaknya dapat dipecahkan. Algoritma utamanya adalah sebagai berikut:

1. parsing kode shader dan buat urutan perintah yang mengubah nilai variabel apa pun
2. mengetahui rentang awal untuk variabel, melalui urutan, memperbarui rentang ketika mereka berubah
3. jika rentang melanggar batas apa pun yang diberikan (misalnya, angka negatif mungkin muncul, atau sesuatu yang lebih besar dari 1 akan sampai pada "warna keluaran" gl_FragColor dalam komponen merah), Anda perlu menampilkan peringatan

Teknologi yang digunakan

Di sini saya punya pilihan yang panjang dan menyakitkan. Di satu sisi, ruang lingkup utama saya adalah memeriksa shader WebGL, jadi mengapa tidak javascript untuk menjalankan semua yang ada di browser selama pengembangan. Di sisi lain, saya telah berencana untuk turun dari Phaser untuk waktu yang lama dan mencoba mesin lain seperti Unity atau LibGDX. Akan ada shader, tetapi javascript akan hilang.

Dan di pihak ketiga, tugas itu dilakukan terutama untuk hiburan. Dan hiburan terbaik di dunia adalah kebun binatang. Oleh karena itu:

1. Penguraian kode GLSL dilakukan dalam javascript. Hanya saja saya cukup cepat menemukan perpustakaan untuk mem-parsing GLSL di AST di atasnya, dan tes UI tampaknya lebih akrab dengan yang berbasis web. AST berubah menjadi urutan perintah, yang dikirim ke ...
2. ... bagian kedua, yang ditulis dalam C ++ dan dikompilasi ke dalam WebAssembly. Saya memutuskan dengan cara ini: jika saya tiba-tiba ingin mempercepat penganalisis ini ke mesin lain, dengan perpustakaan C ++ ini harus dilakukan paling sederhana.

Segalanya, sekarang Anda bisa pergi.

Secara singkat tentang model

Penganalisis menyimpan dalam memori daftar variabel yang ditemukan di shader, dan untuk masing-masing menyimpan rentang nilai saat ini yang mungkin (seperti [0,1] atau [1,∞) ).

Penganalisa menerima alur kerja seperti ini:

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

Di sini kita memanggil fungsi sin, variabel dengan id = 3 dan 4 diumpankan ke dalamnya, dan hasilnya ditulis ke variabel 1 dan 2. Panggilan ini sesuai dengan GLSL-th:

 vec2 a = sin(b); 

Perhatikan argumen kosong (ditandai sebagai "-"). Di GLSL, hampir semua fungsi bawaan kelebihan beban untuk set tipe input yang berbeda, mis. ada sin(float) , sin(vec2) , sin(vec3) , sin(vec4) . Untuk kenyamanan, saya membawa semua versi kelebihan beban ke satu bentuk - dalam hal ini sin(vec4) .

Analyzer mengeluarkan daftar perubahan untuk setiap variabel, seperti

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

Yang berarti "variabel 2 pada baris 10 di cabang 1 memiliki kisaran dari -1 hingga 1 inklusif" (kita akan berbicara tentang cabang sedikit kemudian). Sekarang Anda dapat dengan indah menyoroti rentang nilai dalam kode sumber.

Awal yang bagus

Ketika pohon AST sudah mulai berubah menjadi daftar perintah, sekarang saatnya untuk mengimplementasikan fungsi dan metode standar. Ada cukup banyak dari mereka (dan mereka juga memiliki banyak kelebihan, seperti yang saya tulis di atas), tetapi secara umum mereka memiliki transformasi rentang yang dapat diprediksi. Katakanlah, untuk contoh seperti itu, semuanya ternyata cukup jelas:

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

Saluran merah dari warna output berada dalam kisaran yang dapat diterima, tidak ada kesalahan.

Jika Anda membahas lebih banyak fungsi bawaan, maka untuk setengah shader, analisis seperti itu sudah cukup. Tetapi bagaimana dengan babak kedua - dengan kondisi, putaran, dan fungsi?

Cabang

Ambil contoh shader semacam itu.

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

Variabel a diambil dari tekstur, dan oleh karena itu nilai variabel ini terletak dari 0 hingga 1. Tetapi nilai apa yang dapat diambil k ?

Anda dapat pergi dengan cara sederhana dan "satukan cabang-cabang" - hitung kisaran dalam setiap kasus dan berikan totalnya. Untuk cabang if, kita mendapatkan k = [0,2] , dan untuk cabang lain, k = [0,1] . Jika Anda menggabungkan, ternyata [0,2] , dan Anda harus memberikan kesalahan, karena nilai yang lebih besar dari 1 termasuk dalam warna keluaran gl_FragColor .

Namun, ini adalah alarm palsu yang jelas, dan untuk analisa statis tidak ada yang lebih buruk daripada alarm palsu - jika tidak dimatikan setelah teriakan pertama "serigala", maka setelah kesepuluh pasti.

Jadi, kita perlu memproses kedua cabang secara terpisah, dan di kedua cabang kita perlu memperjelas kisaran variabel a (walaupun secara resmi belum diubah). Begini tampilannya:

Cabang 1:

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

Cabang 2:

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

Dengan demikian, ketika penganalisa menemukan suatu kondisi tertentu yang berperilaku berbeda tergantung pada kisaran, itu menciptakan cabang (brunch) untuk masing-masing kasus. Dalam setiap kasus, ia memperbaiki kisaran variabel sumber dan bergerak lebih jauh ke bawah daftar perintah.

Perlu diperjelas bahwa cabang-cabang dalam kasus ini tidak terkait dengan konstruksi if-else. Cabang dibuat ketika rentang variabel dibagi menjadi sub-rentang, dan penyebabnya mungkin merupakan pernyataan kondisional opsional. Misalnya, fungsi langkah juga membuat cabang. Shader GLSL berikutnya melakukan hal yang sama dengan yang sebelumnya, tetapi tidak menggunakan percabangan (yang, omong-omong, lebih baik dalam hal kinerja).

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

Fungsi langkah harus mengembalikan 0 jika a <0,5 dan 1 sebaliknya. Oleh karena itu, cabang juga akan dibuat di sini - mirip dengan contoh sebelumnya.

Penyempurnaan variabel lainnya

Pertimbangkan contoh sebelumnya yang sedikit dimodifikasi:

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

Berikut nuansanya sebagai berikut: percabangan terjadi sehubungan dengan variabel b , dan perhitungan terjadi dengan variabel a . Artinya, di dalam setiap cabang akan ada nilai yang benar dari rentang b , tetapi sama sekali tidak perlu, dan nilai asli dari kisaran a , sepenuhnya salah.

Namun, penganalisa melihat bahwa rentang b diperoleh dengan menghitung dari a . Jika Anda mengingat informasi ini, maka saat bercabang, penganalisis dapat melalui semua variabel sumber dan menyempurnakan jangkauannya dengan melakukan perhitungan terbalik.

Fungsi dan Putaran

GLSL tidak memiliki metode virtual, pointer fungsi, atau bahkan panggilan rekursif, sehingga setiap panggilan fungsi unik. Oleh karena itu, paling mudah untuk memasukkan tubuh fungsi di tempat panggilan (inline, dengan kata lain). Ini akan sepenuhnya konsisten dengan urutan perintah.

Ini lebih rumit dengan siklus, karena secara formal, GLSL sepenuhnya mendukung C-like for loop. Namun, paling sering, loop digunakan dalam bentuk paling sederhana, seperti ini:

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

Siklus seperti itu mudah untuk "disebarkan", yaitu masukkan badan loop 12 kali satu demi satu. Akibatnya, setelah berpikir, saya memutuskan sejauh ini hanya mendukung opsi seperti itu.

Keuntungan dari pendekatan ini adalah bahwa perintah dapat dikeluarkan dalam aliran ke penganalisis tanpa harus menghafal setiap fragmen (seperti badan fungsi atau loop) untuk digunakan kembali lebih lanjut.

Muncul masalah

Masalah # 1: kesulitan atau ketidakmampuan untuk mengklarifikasi

Di atas, kami memeriksa kasus-kasus ketika, ketika memperbaiki nilai-nilai satu variabel, kami menarik kesimpulan tentang nilai-nilai variabel lain. Dan masalah ini diselesaikan ketika operasi seperti penambahan / pengurangan terlibat. Tapi, katakanlah, apa yang harus dilakukan dengan trigonometri? Misalnya, kondisi seperti itu:

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

Bagaimana cara menghitung rentang a dalam jika? Ternyata rangkaian rentang tak berujung dengan langkah pi, yang kemudian akan sangat tidak nyaman untuk digunakan.

Dan mungkin ada situasi seperti itu:

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

Klarifikasi rentang a dan b dalam kasus umum tidak realistis. Dan, oleh karena itu, positif palsu mungkin terjadi.

Masalah # 2: Ranges Bergantung

Pertimbangkan contoh ini:

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

Untuk memulainya, analisa mempertimbangkan kisaran variabel val2 - dan diharapkan menjadi [0,1] - 1 == [-1, 0]

Namun, kemudian, dengan mempertimbangkan value - val2 , penganalisa tidak memperhitungkan bahwa val2 diperoleh dari value , dan bekerja dengan rentang seolah - olah mereka saling independen. Mendapat [0,1] - [-1,0] = [0,2] , dan melaporkan kesalahan. Meskipun dalam kenyataannya ia seharusnya mendapat konstanta 1.

Kemungkinan solusi: untuk menyimpan untuk setiap variabel tidak hanya sejarah rentang, tetapi juga seluruh "pohon keluarga" - yang variabel bergantung, operasi mana, dan sebagainya. Hal lain adalah bahwa untuk "membuka" silsilah ini tidak akan mudah.

Masalah # 3: Kisaran tergantung secara implisit

Berikut ini sebuah contoh:

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

Di sini, penganalisa akan mengasumsikan bahwa kisaran k = [-1,1] + [-1,1] = [-2,2] . Yang salah, karena sin(a) + cos(a) untuk setiap kebohongan dalam kisaran [-√2, √2] .

Hasil perhitungan sin(a) secara formal tidak tergantung pada hasil perhitungan cos(a) . Namun, mereka bergantung pada kisaran a .

Ringkasan dan Kesimpulan

Ternyata, membuat analisis rentang nilai bahkan untuk bahasa yang sederhana dan sangat khusus seperti GLSL bukanlah tugas yang mudah. Cakupan fitur bahasa masih dapat diperkuat: mendukung array, matriks, dan semua operasi built-in adalah tugas teknis murni yang hanya membutuhkan waktu. Tetapi bagaimana mengatasi situasi dengan ketergantungan antar variabel - pertanyaannya masih belum jelas bagi saya. Tanpa menyelesaikan masalah-masalah ini, false positive tidak dapat dihindari, kebisingan yang akhirnya dapat melebihi manfaat analisis statis.

Mengingat apa yang saya temui, saya tidak terlalu terkejut dengan tidak adanya beberapa alat yang terkenal untuk analisis rentang nilai dalam bahasa lain - jelas ada lebih banyak masalah di dalamnya daripada di GLSL yang relatif sederhana. Pada saat yang sama, Anda dapat menulis setidaknya unit test dalam bahasa lain, tetapi di sini Anda tidak dapat melakukannya.

Solusi alternatif dapat dikompilasi dari bahasa lain ke dalam GLSL - di sini baru-baru ini ada artikel tentang kompilasi dari kotlin . Kemudian Anda dapat menulis tes unit untuk kode sumber dan mencakup semua kondisi batas. Atau buat "penganalisis dinamis" yang akan menjalankan data yang sama dengan yang pergi ke shader melalui kode kotlin asli dan memperingatkan tentang kemungkinan masalah.

Jadi pada titik ini saya berhenti. Perpustakaan, sayangnya, tidak berfungsi, tetapi mungkin prototipe ini berguna bagi seseorang.

Repositori di github, untuk ditinjau:

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

Untuk mencoba:

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

Bonus: fitur webassembly dengan berbagai flag compiler

Awalnya, saya melakukan analisa tanpa menggunakan stdlib - cara kuno, dengan array dan pointer. Pada saat itu saya sangat khawatir tentang ukuran file output wasm, saya ingin itu kecil. Tetapi mulai dari beberapa titik saya mulai merasa tidak nyaman dan karena itu memutuskan untuk mentransfer semuanya ke stdlib - pointer cerdas, koleksi normal, itu saja.

Oleh karena itu, saya mendapat kesempatan untuk membandingkan hasil perakitan dua versi perpustakaan - dengan dan tanpa stdlib. Nah, lihat juga seberapa baik / buruknya ciak (dan dentang yang digunakan olehnya) mengoptimalkan kode.

Oleh karena itu, saya mengkompilasi kedua versi dengan set flag optimasi yang berbeda ( -O1 , -O1 , -O2 , -O3 , -Os dan -Oz ), dan untuk beberapa versi ini saya mengukur kecepatan analisis 3.000 operasi dengan 1.000 cabang. Saya setuju, bukan contoh terbesar, tetapi IMHO cukup untuk analisis komparatif.

Apa yang terjadi sesuai dengan ukuran file wasm:

Anehnya, opsi ukuran dengan optimasi "nol" lebih baik daripada hampir semua yang lain. Saya akan berasumsi bahwa dalam O3 garis agresif segala sesuatu di dunia, yang mengembang biner. Versi yang diharapkan tanpa stdlib lebih ringkas, tetapi tidak terlalu banyak menanggung penghinaan seperti itu untuk menghilangkan kesenangan bekerja dengan koleksi yang nyaman.

Dengan kecepatan eksekusi:

Sekarang saya bisa melihat bahwa -O3 tidak sia-sia memakan rotinya, jika dibandingkan dengan -O0 . Pada saat yang sama, perbedaan antara versi dengan dan tanpa stdlib praktis tidak ada (saya melakukan 10 pengukuran, saya pikir dengan jumlah yang lebih besar perbedaannya akan hilang sama sekali).

Perlu dicatat 2 poin:

• Grafik menunjukkan nilai rata-rata dari 10 kali berturut-turut analisis, tetapi dalam semua tes analisis pertama berlangsung 2 kali lebih lama daripada yang lain (mis., Katakanlah, 120 ms, dan yang berikutnya sudah sekitar 60 ms). Mungkin ada beberapa inisialisasi WebAssembly.
• Dengan flag -O3 , saya mengambil beberapa bug yang sangat aneh yang tidak saya tangkap untuk flag lainnya. Misalnya, fungsi min dan maks tiba-tiba mulai bekerja dengan cara yang sama - seperti min.

Kesimpulan

Terima kasih atas perhatiannya.
Biarkan nilai-nilai variabel Anda tidak pernah melampaui batas.
Dan ini dia.