मैंने GLSL स्टेटिक एनालाइज़र बनाने की कोशिश की (और क्या गलत हुआ)

एक बार जब मैं लुदुम डेयर की तैयारी कर रहा था और एक साधारण गेम बनाया, जहां मैंने पिक्सेल शेड्स का इस्तेमाल किया (अन्यों को फेजर इंजन में नहीं लाया गया)।

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

परीक्षण के बाद, मैंने एक दोस्त के लिए लिंक को फेंक दिया, और उससे इस तरह के स्क्रीनशॉट को प्रश्न के साथ प्राप्त किया "क्या यह सामान्य है?"

नहीं, यह सामान्य नहीं था। Shader कोड को ध्यान से देखने के बाद, मुझे एक गणना त्रुटि मिली:

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

क्योंकि चूँकि निरंतर R1 M से कम था, इसलिए कुछ मामलों में pow के पहले तर्क में परिणाम शून्य से भी कम था। नकारात्मक संख्या का वर्गमूल एक रहस्यमयी चीज है, कम से कम जीएलएसएल मानक के लिए। मेरा वीडियो कार्ड भ्रमित नहीं था, और यह किसी तरह इस स्थिति से बाहर निकल गया (ऐसा लगता है, इसे पॉव 0 से लौटा दिया गया), लेकिन यह एक दोस्त के लिए अधिक सुपाठ्य हो गया।

और फिर मैंने सोचा: क्या मैं भविष्य में ऐसी समस्याओं से बच सकता हूं? कोई भी गलतियों से सुरक्षित नहीं है, विशेष रूप से वे जो स्थानीय रूप से पुन: पेश नहीं किए जाते हैं। आप GLSL के लिए इकाई परीक्षण नहीं लिख सकते। इसी समय, शेडर के अंदर रूपांतरण काफी सरल हैं - गुणा, भाग, साइन, कोसाइन ... क्या प्रत्येक चर के मूल्यों को ट्रैक करना और यह सुनिश्चित करना असंभव है कि किसी भी परिस्थिति में यह मूल्यों की स्वीकार्य सीमा से आगे नहीं जाता है?

इसलिए मैंने GLSL के लिए स्थैतिक विश्लेषण करने की कोशिश करने का फैसला किया। इसका क्या हुआ - आप इसे कट के नीचे पढ़ सकते हैं।

मैं आपको तुरंत चेतावनी दूंगा: मुझे कोई तैयार उत्पाद नहीं मिला, केवल एक शैक्षिक प्रोटोटाइप।

प्रारंभिक विश्लेषण

इस विषय पर मौजूदा लेखों का थोड़ा अध्ययन किया है (और इस तरह से पता चला है कि विषय को मूल्य श्रेणी विश्लेषण कहा जाता है), मुझे खुशी थी कि मेरे पास GLSL थी, न कि कुछ अन्य भाषा। खुद के लिए न्यायाधीश:

• कोई "गत्यात्मकता" - कार्यों, इंटरफेस, स्वचालित रूप से अनुमानित प्रकार आदि के संदर्भ में।
• कोई डायरेक्ट मेमोरी हैंडलिंग नहीं
• कोई मॉड्यूल, लिंकिंग, देर से बाध्यकारी - shader का संपूर्ण स्रोत कोड उपलब्ध है
  रेंज आम तौर पर इनपुट मूल्यों के लिए अच्छी तरह से जानी जाती हैं
• कुछ डेटा प्रकार, और वे एक फ्लोट के चारों ओर घूमते हैं। इंट / बूल का उपयोग शायद ही कभी किया जाता है, और उनका पालन करना इतना महत्वपूर्ण नहीं है
• ifs और लूप्स का उपयोग शायद ही कभी किया जाता है (प्रदर्शन समस्याओं के कारण)। छोरों, यदि उपयोग किया जाता है, तो अक्सर एक सरणी के माध्यम से जाने या एक निश्चित प्रभाव को कई बार दोहराने के लिए सरल काउंटर होते हैं। जीएलएसएल (मुझे आशा है) में कोई भी इतना डरावना नहीं लिखेगा।

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

सामान्य तौर पर, जीएलएसएल की सीमाओं को देखते हुए, कार्य हल करने योग्य लगता है। मुख्य एल्गोरिथ्म इस प्रकार है:

1. shader कोड को पार्स करें और किसी भी वैरिएबल के मूल्यों को बदलने वाले आदेशों का एक क्रम बनाएं
2. वैरिएबल के लिए शुरुआती रेंज को जानना, अनुक्रम के माध्यम से जाना, जब वे बदलते हैं, तो श्रेणियों को अपडेट करना
3. यदि सीमा किसी भी दी गई सीमाओं का उल्लंघन करती है (उदाहरण के लिए, एक नकारात्मक संख्या पाउ में आ सकती है, या 1 से अधिक कुछ "आउटपुट रंग" gl_FragColor लाल घटक में आ जाएगा), तो आपको एक चेतावनी दिखाने की आवश्यकता है

प्रयुक्त प्रौद्योगिकियाँ

यहां मेरे पास एक लंबी और दर्दनाक पसंद थी। एक तरफ, मेरा मुख्य दायरा WebGL shaders की जाँच कर रहा है, तो क्यों नहीं विकास के दौरान ब्राउज़र में सब कुछ चलाने के लिए जावास्क्रिप्ट किया जाए। दूसरी ओर, मैं लंबे समय से फेजर से बाहर निकलने और यूनिटी या लीबीडीएक्स जैसे दूसरे इंजन को आजमाने की योजना बना रहा हूं। शेड भी होंगे, लेकिन जावास्क्रिप्ट चला जाएगा।

और तीसरे हाथ पर, कार्य मुख्य रूप से मनोरंजन के लिए किया गया था। और दुनिया में सबसे अच्छा मनोरंजन चिड़ियाघर है। इसलिए:

1. जावास्क्रिप्ट में किया गया GLSL कोड पार्सिंग। यह सिर्फ इतना है कि मुझे बहुत जल्दी से एएसटी पर GLSL को पार्स करने के लिए पुस्तकालय मिल गया, और परीक्षण यूआई वेब आधारित होने के साथ अधिक परिचित लगता है। एएसटी आदेशों के अनुक्रम में बदल जाता है, जिसे ...
2. ... दूसरा भाग, जो C ++ में लिखा गया है और WebAssembly में संकलित है। मैंने इस तरह से फैसला किया: अगर मैं अचानक इस विश्लेषक को किसी अन्य इंजन में बांधना चाहता हूं, तो सी ++ लाइब्रेरी के साथ यह सबसे सरल तरीके से किया जाना चाहिए।

सब कुछ, अब आप जा सकते हैं।

संक्षेप में मॉडल के बारे में

विश्लेषक स्मृति में उन चरों की सूची रखता है जो शैडर में पाए जाते हैं, और प्रत्येक के लिए यह वर्तमान संभावित मानों (जैसे [0,1] या [1,∞) संग्रहीत करता है।

विश्लेषक इस तरह एक वर्कफ़्लो प्राप्त करता है:

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

यहां हम पाप फ़ंक्शन कहते हैं, आईडी = 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] 

जिसका अर्थ है "शाखा 1 में लाइन 10 में चर 2 में -1 से 1 समावेशी की सीमा है" (हम शाखा के बारे में थोड़ी देर बाद बात करेंगे)। अब आप स्रोत कोड में मानों की श्रेणी को खूबसूरती से उजागर कर सकते हैं।

अच्छी शुरुआत

जब एएसटी पेड़ पहले ही आदेशों की सूची में बदलना शुरू कर चुका है, तो मानक कार्यों और विधियों को लागू करने का समय है। उनमें से बहुत सारे हैं (और उनके पास ओवरलोड का एक गुच्छा भी है, जैसा कि मैंने ऊपर लिखा है), लेकिन सामान्य तौर पर उनके पास अनुमानित रेंज ट्रांसफॉर्मेशन हैं। आइए, ऐसे उदाहरण के लिए, सब कुछ स्पष्ट रूप से सामने आता है:

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

आउटपुट रंग का लाल चैनल स्वीकार्य सीमा के भीतर है, कोई त्रुटि नहीं है।

यदि आप अधिक निर्मित कार्यों को कवर करते हैं, तो आधे शेड्स के लिए, ऐसा विश्लेषण पर्याप्त है। लेकिन दूसरी छमाही के बारे में क्या - शर्तों, छोरों और कार्यों के साथ?

शाखाओं में

उदाहरण के लिए एक ऐसे 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; } 

चर को बनावट से लिया जाता है, और इसलिए इस चर का मूल्य 0 से 1 तक है।

आप सरल तरीके से जा सकते हैं और "शाखाओं को एकजुट कर सकते हैं" - प्रत्येक मामलों में सीमा की गणना करें और कुल को दें। यदि शाखा के लिए, हमें k = [0,2] , और दूसरी शाखा के लिए, k = [0,1] । यदि आप गठबंधन करते हैं, तो यह बदल जाता है [0,2] , और आपको एक त्रुटि देने की आवश्यकता है, क्योंकि 1 से अधिक मूल्य gl_FragColor के आउटपुट रंग में 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; } 

इस प्रकार, जब विश्लेषक एक निश्चित स्थिति का सामना करता है जो सीमा के आधार पर अलग-अलग व्यवहार करता है, तो यह प्रत्येक मामले के लिए शाखाएं (ब्रंच) बनाता है। प्रत्येक मामले में, वह स्रोत चर की सीमा को परिष्कृत करता है और आदेशों की सूची को और नीचे ले जाता है।

यह स्पष्ट करने योग्य है कि इस मामले में शाखाएं इफ-निर्माण के साथ संबंधित नहीं हैं। जब एक वैरिएबल की एक श्रेणी को उप-श्रेणियों में विभाजित किया जाता है, तो शाखाएं बनाई जाती हैं और इसका कारण वैकल्पिक सशर्त विवरण हो सकता है। उदाहरण के लिए, चरण फ़ंक्शन भी शाखाएं बनाता है। अगला GLSL शेडर पिछले एक के समान है, लेकिन ब्रांचिंग का उपयोग नहीं करता है (जो, वैसे, प्रदर्शन के मामले में बेहतर है)।

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

चरण फ़ंक्शन 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 संबंध में होती है, और चर के साथ गणनाएँ होती हैं। यही है, प्रत्येक शाखा के अंदर रेंज b का एक सही मूल्य होगा, लेकिन पूरी तरह से अनावश्यक है, और रेंज का मूल मूल्य, पूरी तरह से गलत है।

हालांकि, विश्लेषक ने देखा कि रेंज b को a से गणना करके प्राप्त किया गया था। यदि आपको यह जानकारी याद है, तो ब्रांच करते समय, विश्लेषक सभी स्रोत चर के माध्यम से जा सकता है और अदृश्य गणना करके अपनी सीमा को परिष्कृत कर सकता है।

कार्य और लूप्स

GLSL में वर्चुअल मेथड्स, फंक्शन पॉइंटर्स या रिकर्सिव कॉल्स भी नहीं हैं, इसलिए हर फंक्शन कॉल अद्वितीय है। इसलिए, कॉल (इनलाइन, दूसरे शब्दों में) के स्थान पर फ़ंक्शन के शरीर को सम्मिलित करना सबसे आसान है। यह पूरी तरह से आदेशों के अनुक्रम के अनुरूप होगा।

यह साइकिल के साथ अधिक जटिल है, क्योंकि औपचारिक रूप से, जीएलएसएल लूप के लिए सी-लाइक का पूरी तरह से समर्थन करता है। हालांकि, सबसे अधिक बार, छोरों का उपयोग सबसे सरल रूप में किया जाता है, जैसे:

 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 की सीमा को val2 - और यह होने की उम्मीद है [0,1] - 1 == [-1, 0]

हालांकि, फिर, value - val2 पर विचार करते 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] । जो गलत है, क्योंकि सीमा [-√2, √2] में किसी भी झूठ के लिए sin(a) + cos(a) ।

कंप्यूटिंग sin(a) का परिणाम औपचारिक रूप से कंप्यूटिंग cos(a) के परिणाम पर निर्भर नहीं करता है। हालाँकि, वे एक ही श्रेणी पर निर्भर करते हैं।

सारांश और निष्कर्ष

जैसा कि यह निकला, ऐसी सरल और अति विशिष्ट भाषा के लिए भी मूल्य श्रेणी विश्लेषण करना, क्योंकि GLSL एक आसान काम नहीं है। भाषा सुविधाओं के कवरेज को अभी भी मजबूत किया जा सकता है: सहायक सरणियों, मैट्रिस और सभी अंतर्निहित ऑपरेशन एक विशुद्ध रूप से तकनीकी कार्य है जिसमें बस समय लेने की आवश्यकता होती है। लेकिन चर के बीच निर्भरता के साथ स्थितियों को कैसे हल किया जाए - सवाल अभी भी मेरे लिए अस्पष्ट है। इन समस्याओं को हल किए बिना, झूठी सकारात्मकताएं अपरिहार्य हैं, जिनमें से शोर अंततः स्थैतिक विश्लेषण के लाभों से आगे निकल सकता है।

यह ध्यान में रखते हुए कि मैं क्या आया था, मैं विशेष रूप से अन्य भाषाओं में मूल्य श्रेणी विश्लेषण के लिए कुछ प्रसिद्ध उपकरणों की अनुपस्थिति पर आश्चर्यचकित नहीं हूं - अपेक्षाकृत सरल जीएलएसएल की तुलना में उनमें स्पष्ट रूप से अधिक समस्याएं हैं। उसी समय, आप अन्य भाषाओं में कम से कम इकाई परीक्षण लिख सकते हैं, लेकिन यहां आप ऐसा नहीं कर सकते।

एक वैकल्पिक समाधान जीएलएसएल में अन्य भाषाओं से संकलन किया जा सकता है - यहां हाल ही में कोटलिन से संकलन के बारे में एक लेख था। फिर आप स्रोत कोड के लिए इकाई परीक्षण लिख सकते हैं और सभी सीमा शर्तों को कवर कर सकते हैं। या एक "डायनेमिक एनालाइज़र" बनाएं जो उसी डेटा को चलाएगा जो मूल कोटलिन कोड के माध्यम से शेडर में जाता है और संभावित समस्याओं के बारे में चेतावनी देता है।

तो इस बिंदु पर मैं रुक गया। पुस्तकालय, अफसोस, काम नहीं किया, लेकिन शायद यह प्रोटोटाइप किसी के लिए उपयोगी है।

समीक्षा के लिए गितुब पर रिपोजिटरी:

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

कोशिश करने के लिए:

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

बोनस: अलग-अलग संकलक झंडे के साथ webassembly सुविधाएँ

प्रारंभ में, मैंने स्टैडलिब का उपयोग किए बिना विश्लेषक किया - पुराने ढंग का, सरणियों और संकेत के साथ। उस समय मैं आउटपुट wasm-file के आकार को लेकर बहुत चिंतित था, मैं चाहता था कि यह छोटा हो। लेकिन कुछ बिंदुओं से शुरू करके मुझे असुविधा महसूस होने लगी और इसलिए मैंने सब कुछ stdlib में स्थानांतरित करने का फैसला किया - स्मार्ट पॉइंटर्स, सामान्य संग्रह, वह सब।

तदनुसार, मुझे लाइब्रेरी के दो संस्करणों के विधानसभा के परिणामों की तुलना करने का अवसर मिला - स्टैडलिब के साथ और बिना। खैर, यह भी देखें कि कितना अच्छा / बुरा चीयरपैप (और इसके द्वारा इस्तेमाल किया गया क्लैंग) कोड का अनुकूलन करता है।

इसलिए, मैंने दोनों संस्करणों को अनुकूलन झंडे के विभिन्न सेटों ( -O0 , -O1 , -O0 , -O1 , -Os और -Oz ) के साथ संकलित किया, और इनमें से कुछ संस्करणों के लिए मैंने 1,000 शाखाओं के साथ 3,000 संचालन की विश्लेषण गति को मापा। मैं सहमत हूं, सबसे बड़ा उदाहरण नहीं है, लेकिन तुलनात्मक विश्लेषण के लिए आईएमएचओ पर्याप्त है।

Wasm फ़ाइल के आकार के अनुसार क्या हुआ:

हैरानी की बात है, "शून्य" अनुकूलन के साथ आकार विकल्प लगभग सभी दूसरों की तुलना में बेहतर है। मैं मान लूंगा कि O3 में दुनिया में हर चीज की आक्रामक इनलाइन है, जो बाइनरी को फुलाती है। स्टडलिब के बिना अपेक्षित संस्करण अधिक कॉम्पैक्ट है, लेकिन ऐसा नहीं है ऐसा अपमान सहना सुविधाजनक संग्रह के साथ काम करने की खुशी से खुद को वंचित करना।

निष्पादन की गति से:

अब मैं देख सकता हूं कि -O0 की तुलना में -O0 खाने में व्यर्थ नहीं है। इसी समय, स्टडलिब के साथ और बिना संस्करणों के बीच का अंतर व्यावहारिक रूप से अनुपस्थित है (मैंने 10 माप किए, मुझे लगता है कि बड़ी संख्या के साथ अंतर पूरी तरह से गायब हो जाएगा)।

यह ध्यान देने योग्य है 2 अंक:

• ग्राफ विश्लेषण के 10 लगातार रन से औसत मूल्यों को दिखाता है, लेकिन सभी परीक्षणों में बहुत पहले विश्लेषण बाकी की तुलना में 2 गुना लंबे समय तक रहता है (यानी, 120ms, और अगले वाले पहले से ही 60ms के आसपास थे)। शायद WebAssembly के कुछ प्रारंभिककरण थे।
• -O3 झंडे के साथ, मैंने कुछ अजीब तरह के कीड़े पकड़ लिए जिन्हें मैंने दूसरे झंडों के लिए नहीं पकड़ा। उदाहरण के लिए, न्यूनतम और अधिकतम कार्यों ने अचानक उसी तरह काम करना शुरू कर दिया - जैसे कि मिनट।

निष्कर्ष

ध्यान देने के लिए आप सभी का धन्यवाद।
अपने चरों के मूल्यों को सीमा से बाहर कभी न जाने दें।
और यहाँ तुम जाओ।