كيف حاولت عمل محلل ثابت GLSL (وما الخطأ الذي حدث)

بمجرد أن كنت أستعد لودوم داري وقمت بعمل لعبة بسيطة حيث استخدمت تظليل بكسل (لم يتم جلب الآخرين إلى محرك Phaser).

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

بعد الاختبار ، رميت الرابط إلى صديق ، وتلقيت منه لقطة شاشة مع السؤال "هل هذا طبيعي؟"

لا ، لم يكن ذلك طبيعيا. بعد النظر بعناية في كود التظليل ، وجدت خطأ حسابي:

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

لأن نظرًا لأن الثابت R1 كان أقل من M ، في بعض الحالات كانت النتيجة في الوسيطة الأولى للأسرى رقمًا أقل من الصفر. الجذر التربيعي للرقم السالب شيء غامض ، على الأقل بالنسبة لمعيار GLSL. لم يتم الخلط بين بطاقة الفيديو الخاصة بي ، وبطريقة ما خرجت من هذا الموقف (على ما يبدو ، بعد إعادتها من الأسرى 0) ، ولكن تبين أنها أكثر وضوحًا بالنسبة لصديق.

ثم فكرت: هل يمكنني تجنب مثل هذه المشاكل في المستقبل؟ لا أحد في مأمن من الأخطاء ، خاصة تلك التي لا يتم إعادة إنتاجها محليًا. لا يمكنك كتابة اختبارات الوحدة لـ GLSL. في الوقت نفسه ، فإن التحولات داخل التظليل بسيطة للغاية - الضرب والقسمة والجيوب وجيب التمام ... هل من المستحيل تتبع قيم كل متغير والتأكد من أنه لا يتجاوز بأي حال من الأحوال الحدود المسموح بها للقيم؟

لذلك قررت أن أحاول إجراء تحليل ثابت لـ GLSL. ما جاء منها - يمكنك قراءتها تحت القطع.

سأحذرك على الفور: لم أستطع الحصول على أي منتج نهائي ، فقط نموذج تعليمي.

التحليل الأولي

بعد أن درست القليل من المقالات الموجودة حول هذا الموضوع (واكتشفت في الوقت نفسه أن الموضوع يسمى تحليل نطاق القيمة) ، كنت سعيدًا لأن لدي GLSL ، وليس لغة أخرى. احكم بنفسك:

• لا يوجد "ديناميكيات" - مراجع للوظائف والواجهات والأنواع المستنتجة تلقائيًا وما إلى ذلك.
• لا معالجة مباشرة للذاكرة
• لا توجد وحدات ، ربط ، ربط متأخر - يتوفر كود المصدر بالكامل للتظليل
  نطاقات معروفة بشكل عام لقيم المدخلات
• عدد قليل من أنواع البيانات ، والتي تدور حول تعويم. نادرًا ما يتم استخدام int / bool ، وليس من المهم متابعتها
• نادرًا ما يتم استخدام ifs و loops (بسبب مشاكل في الأداء). غالبًا ما تكون الحلقات ، إذا تم استخدامها ، عدادات بسيطة للذهاب من خلال مصفوفة أو تكرار تأثير معين عدة مرات. لن يكتب أحد مثل هذا الرعب في GLSL (آمل).

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

بشكل عام ، نظرًا لقيود GLSL ، يبدو أن المهمة قابلة للحل. الخوارزمية الرئيسية هي كما يلي:

1. تحليل كود التظليل وإنشاء سلسلة من الأوامر التي تغير قيم أي متغيرات
2. معرفة النطاقات الأولية للمتغيرات ، انتقل من خلال التسلسل ، وتحديث النطاقات عند تغييرها
3. إذا كان النطاق ينتهك أي حدود معينة (على سبيل المثال ، قد يأتي رقم سالب للأسرى ، أو سيأتي شيء أكبر من 1 إلى "لون الإخراج" gl_FragColor في المكون الأحمر) ، فأنت بحاجة إلى إظهار تحذير

التقنيات المستخدمة

هنا كان لدي خيار طويل ومؤلم. من ناحية ، فإن نطاقي الرئيسي هو التحقق من تظليل WebGL ، فلماذا لا جافا سكريبت لتشغيل كل شيء في المتصفح أثناء التطوير. من ناحية أخرى ، كنت أخطط للخروج من Phaser لفترة طويلة وتجربة محرك آخر مثل Unity أو LibGDX. سيكون هناك أيضا تظليل ، ولكن سوف تختفي جافا سكريبت.

ومن ناحية أخرى ، تم تنفيذ المهمة في المقام الأول للترفيه. وأفضل ترفيه في العالم هو حديقة الحيوانات. لذلك:

1. تم تحليل رمز GLSL في جافا سكريبت. لمجرد أنني عثرت بسرعة على مكتبة لتحليل GLSL في AST عليها ، ويبدو أن واجهة المستخدم الاختبارية أكثر دراية بكونها مستندة إلى الويب. يتحول AST إلى سلسلة من الأوامر التي يتم إرسالها إلى ...
2. ... الجزء الثاني المكتوب بلغة C ++ وتجميعه في WebAssembly. قررت بهذه الطريقة: إذا أردت فجأة ربط هذا المحلل بمحرك آخر ، مع مكتبة C ++ ، فيجب أن يتم ذلك ببساطة.

كل شيء ، الآن يمكنك الذهاب.

باختصار حول النموذج

يحتفظ المحلل في الذاكرة بقائمة من المتغيرات الموجودة في التظليل ، ولكل منها يخزن نطاق القيم المحتملة الحالي (مثل [0,1] أو [1,∞) ).

يتلقى المحلل سير عمل مثل هذا:

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

هنا نسمي دالة sin ، ويتم تغذيتها بالمتغيرات id = 3 و 4 ، والنتيجة مكتوبة للمتغيرين 1 و 2. هذا الاستدعاء يتوافق مع GLSL-th:

 vec2 a = sin(b); 

لاحظ الوسيطات الفارغة (المميزة بعلامة "-"). في GLSL ، يتم تحميل جميع الوظائف المدمجة تقريبًا فوق طاقتها لمجموعات مختلفة من أنواع الإدخال ، أي هناك sin(float) ، sin(vec2) ، sin(vec3) ، sin(vec4) . من أجل الراحة ، أحمل جميع الإصدارات المحملة إلى شكل واحد - في هذه الحالة sin(vec4) .

يخرج المحلل قائمة بالتغييرات لكل متغير ، مثل

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

مما يعني أن "المتغير 2 في السطر 10 في الفرع 1 له نطاق من -1 إلى 1 شامل" (سنتحدث عن الفرع بعد ذلك بقليل). يمكنك الآن تسليط الضوء بشكل جميل على نطاقات القيم في شفرة المصدر.

بداية جيدة

عندما تبدأ شجرة AST بالفعل في التحول إلى قائمة أوامر ، فقد حان الوقت لتنفيذ الوظائف والأساليب القياسية. هناك الكثير منها (ولديهم أيضًا مجموعة من الأحمال الزائدة ، كما كتبت أعلاه) ، ولكن بشكل عام لديهم تحويلات نطاق يمكن التنبؤ بها. دعنا نقول ، على سبيل المثال ، كل شيء يتضح بشكل واضح:

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

القناة الحمراء للون الإخراج ضمن النطاق المقبول ، لا توجد أخطاء.

إذا قمت بتغطية المزيد من الوظائف المضمنة ، فإن هذا التحليل يكفي لنصف التظليل. ولكن ماذا عن النصف الثاني - بالظروف والحلقات والوظائف؟

الفروع

خذ على سبيل المثال مثل هذا التظليل.

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

المتغير a مأخوذ من النسيج ، وبالتالي فإن قيمة هذا المتغير تقع من 0 إلى 1. ولكن ما هي القيم التي يمكن أن تأخذ k ؟

يمكنك الذهاب بطريقة بسيطة و "توحيد الفروع" - حساب النطاق في كل حالة وإعطاء المجموع. بالنسبة للفرع if ، نحصل على k = [0,2] ، k = [0,2] الآخر ، k = [0,1] . إذا قمت بدمج ، اتضح [0,2] ، وتحتاج إلى إعطاء خطأ ، لأن تقع القيم الأكبر من 1 في لون الإخراج gl_FragColor .

ومع ذلك ، فهذا إنذار كاذب واضح ، وبالنسبة للمحلل الساكن ، ليس هناك ما هو أسوأ من الإنذارات الكاذبة - إذا لم يتم إيقاف تشغيله بعد صرخة الذئب الأولى ، ثم بعد العاشرة بالتأكيد.

لذا ، نحتاج إلى معالجة كلا الفرعين بشكل منفصل ، وفي كلا الفرعين نحتاج إلى توضيح نطاق المتغير a (على الرغم من أنه لم يتم تغييره رسميًا). إليك ما قد يبدو عليه:

الفرع 1:

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

الفرع 2:

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

وبالتالي ، عندما يواجه المحلل شرطًا معينًا يتصرف بشكل مختلف اعتمادًا على النطاق ، فإنه ينشئ فروعًا (وجبات غداء) لكل حالة من الحالات. في كل حالة ، يقوم بتحسين نطاق متغير المصدر وينتقل إلى أسفل قائمة الأوامر.

تجدر الإشارة إلى أن الفروع في هذه الحالة لا تتعلق ببنية if-else. يتم إنشاء الفروع عندما يتم تقسيم نطاق المتغير إلى نطاقات فرعية ، وقد يكون السبب عبارة شرطية اختيارية. على سبيل المثال ، تقوم وظيفة الخطوة أيضًا بإنشاء فروع. يعمل جهاز تظليل GLSL التالي مثل السابق ، ولكنه لا يستخدم التفرع (وهو ، بالمناسبة ، أفضل من حيث الأداء).

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

يجب أن ترجع الدالة step 0 إذا كان <0.5 و 1 خلاف ذلك. لذلك ، سيتم أيضًا إنشاء الفروع هنا - على غرار المثال السابق.

صقل المتغيرات الأخرى

خذ بعين الاعتبار مثال سابق معدّل قليلاً:

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

هنا الفروق الدقيقة على النحو التالي: يحدث التفرع فيما يتعلق بالمتغير b ، وتحدث الحسابات مع المتغير a . أي أنه داخل كل فرع ستكون هناك قيمة صحيحة للنطاق b ، ولكنها غير ضرورية تمامًا ، والقيمة الأصلية للنطاق a ، غير صحيحة تمامًا.

ومع ذلك ، رأى المحلل أن النطاق b تم الحصول عليه بالحساب من a . إذا كنت تتذكر هذه المعلومات ، فعند التفرع ، يمكن للمحلل أن يمر بجميع المتغيرات المصدر ويحسن نطاقها عن طريق إجراء الحساب العكسي.

وظائف وحلقات

لا تحتوي GLSL على طرق افتراضية أو مؤشرات وظائف أو حتى مكالمات متكررة ، لذا فإن كل استدعاء دالة فريد. لذلك ، من الأسهل إدراج نص الوظيفة في مكان المكالمة (مضمنة ، بكلمات أخرى). سيكون هذا متسقًا تمامًا مع تسلسل الأوامر.

لأنه أكثر تعقيدًا مع الدورات ، لأنه رسميًا ، يدعم GLSL تمامًا C-like للحلقة. ومع ذلك ، في معظم الأحيان ، يتم استخدام الحلقات في أبسط شكل ، مثل هذا:

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

من السهل "نشر" هذه الدورات ، أي أدخل جسم الحلقة 12 مرة واحدة تلو الأخرى. ونتيجة لذلك ، بعد التفكير ، قررت حتى الآن دعم مثل هذا الخيار فقط.

تتمثل ميزة هذا النهج في أنه يمكن إصدار الأوامر في دفق إلى المحلل دون الحاجة إلى حفظ أي أجزاء (مثل الهيئات الوظيفية أو الحلقات) لمزيد من إعادة الاستخدام.

مشاكل منبثقة

المشكلة رقم 1: صعوبة أو عدم القدرة على التوضيح

أعلاه ، درسنا الحالات التي ، عند تنقيح قيم متغير واحد ، استخلصنا استنتاجات حول قيم متغير آخر. ويتم حل هذه المشكلة عندما يتعلق الأمر بعمليات مثل الجمع / الطرح. ولكن ، قل ، ماذا تفعل مع علم المثلثات؟ على سبيل المثال ، مثل هذا الشرط:

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

كيف تحسب مدى الداخل إذا؟ اتضح مجموعة لا حصر لها من النطاقات مع خطوات باي ، والتي ستكون غير ملائمة للعمل معها.

وقد يكون هناك مثل هذا الموقف:

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

توضيح النطاقين a و b في الحالة العامة سيكون غير واقعي. وبالتالي ، فإن الإيجابيات الكاذبة ممكنة.

المشكلة رقم 2: النطاقات التابعة

تأمل هذا المثال:

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

بادئ ذي بدء ، ينظر المحلل في نطاق المتغير val2 - ومن المتوقع أن يكون [0,1] - 1 == [-1, 0]

ومع ذلك ، عند النظر في value - val2 ، لا يأخذ المحلل في الاعتبار أن val2 قد تم الحصول عليه من value ، ويعمل مع النطاقات كما لو كانت مستقلة عن بعضها البعض. يحصل على [0,1] - [-1,0] = [0,2] ، ويبلغ عن خطأ. على الرغم من أنه في الواقع كان يجب أن يحصل على ثابت 1.

الحل الممكن: تخزين كل متغير ليس فقط تاريخ النطاقات ، ولكن أيضًا "شجرة العائلة" بالكامل - أي المتغيرات كانت تعتمد عليها ، والعمليات ، وما إلى ذلك. شيء آخر هو أن "تتكشف" هذه النسب لن تكون سهلة.

المشكلة رقم 3: النطاقات التابعة ضمنيًا

هنا مثال:

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

هنا ، يفترض المحلل أن النطاق k = [-1,1] + [-1,1] = [-2,2] . وهذا خطأ لأنه sin(a) + cos(a) لأي كذب في النطاق [-√2, √2] .

لا تعتمد نتيجة الحوسبة sin(a) رسميًا على نتيجة الحوسبة cos(a) . ومع ذلك ، فإنها تعتمد على نفس النطاق.

الملخص والاستنتاجات

كما اتضح ، فإن إجراء تحليل نطاق القيمة حتى بالنسبة لهذه اللغة البسيطة والمتخصصة للغاية مثل GLSL ليس مهمة سهلة. لا يزال من الممكن تعزيز تغطية ميزات اللغة: دعم المصفوفات والمصفوفات وجميع العمليات المدمجة هي مهمة فنية بحتة تتطلب ببساطة وقتًا طويلاً. ولكن كيفية حل المواقف بالتبعيات بين المتغيرات - السؤال لا يزال غير واضح بالنسبة لي. بدون حل هذه المشاكل ، فإن الإيجابيات الكاذبة لا مفر منها ، والضوضاء التي يمكن أن تفوق في نهاية المطاف فوائد التحليل الثابت.

بالنظر إلى ما صادفته ، لم أكن متفاجئًا بشكل خاص لغياب بعض الأدوات المعروفة جيدًا لتحليل نطاق القيم بلغات أخرى - من الواضح أن هناك مشاكل أكثر منها في GLSL البسيط نسبيًا. في الوقت نفسه ، يمكنك كتابة اختبارات الوحدة على الأقل بلغات أخرى ، ولكن هنا لا يمكنك القيام بذلك.

يمكن أن يكون الحل البديل هو الترجمة من لغات أخرى إلى GLSL - هنا في الآونة الأخيرة كان هناك مقال حول الترجمة من kotlin . ثم يمكنك كتابة اختبارات الوحدة لشفرة المصدر وتغطية جميع شروط الحدود. أو قم بعمل "محلل ديناميكي" يقوم بتشغيل نفس البيانات التي تذهب إلى جهاز تظليل من خلال كود kotlin الأصلي ويحذر من المشاكل المحتملة.

لذا توقفت عند هذه النقطة. للأسف ، لم تعمل المكتبة ، ولكن ربما هذا النموذج الأولي مفيد لشخص ما.

مستودع على جيثوب للمراجعة:

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

للمحاولة:

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

المكافأة: ميزات تجميع الويب بأعلام مترجم مختلفة

في البداية ، قمت بالمحلل دون استخدام stdlib - بالطريقة القديمة ، مع المصفوفات والمؤشرات. في ذلك الوقت كنت قلقة للغاية بشأن حجم ملف الإخراج ، وأردت أن يكون صغيرًا. ولكن بدءًا من مرحلة ما ، بدأت أشعر بعدم الراحة ، وبالتالي قررت نقل كل شيء إلى stdlib - المؤشرات الذكية والمجموعات العادية ، هذا كل شيء.

وبناء على ذلك ، أتيحت لي الفرصة لمقارنة نتائج تجميع نسختين من المكتبة - مع stdlib أو بدونه. حسنًا ، انظر أيضًا كيف يعمل التحسين الجيد / السيئ (والكلمة التي يستخدمها) على تحسين الشفرة.

لذلك ، جمعت كلا الإصدارين بمجموعات مختلفة من علامات التحسين ( -O0 و -Oz و -Oz و -Oz و -Oz و -Oz ) ، وبالنسبة لبعض هذه الإصدارات ، قمت بقياس سرعة التحليل لـ 3000 عملية مع 1000 فرع. أوافق ، ليس أكبر مثال ، ولكن IMHO يكفي لإجراء تحليل مقارن.

ماذا حصل حسب حجم ملف wasm:

والمثير للدهشة أن خيار الحجم مع التحسين "صفر" أفضل من جميع الخيارات الأخرى تقريبًا. سأفترض أنه في O3 خط مضمن لكل شيء في العالم ، مما يؤدي إلى تضخيم ثنائي. الإصدار المتوقع بدون stdlib أكثر إحكاما ، ولكن ليس كثيرا تحمل مثل هذا الإذلال لحرمان نفسك من متعة العمل مع مجموعات مناسبة.

حسب سرعة التنفيذ:

الآن أستطيع أن أرى أن -O3 ليس عبثا أكل الخبز ، بالمقارنة مع -O0 . في نفس الوقت ، الفرق بين الإصدارات مع stdlib أو بدونه غير موجود عمليًا (أجريت 10 قياسات ، أعتقد أنه مع عدد أكبر سيختفي الفرق تمامًا).

تجدر الإشارة إلى نقطتين:

• يُظهر الرسم البياني متوسط ​​القيم من 10 عمليات متتالية للتحليل ، ولكن في جميع الاختبارات ، استمر التحليل الأول مرتين أطول من البقية (على سبيل المثال ، 120 مللي ثانية ، والعمليات التالية كانت بالفعل حول 60 مللي ثانية). ربما كان هناك بعض التهيئة ل WebAssembly.
• مع العلم -O3 ، أمسكت ببعض الحشرات الغريبة التي لم -O3 لأعلام أخرى. على سبيل المثال ، بدأت الدالتان min و max فجأة في العمل بنفس الطريقة - مثل min.

الخلاصة

شكرا لكم جميعا على اهتمامكم.
دع قيم المتغيرات الخاصة بك لا تتجاوز أبدًا الحدود.
وها أنت ذا.