डेटा प्रवाह विश्लेषण: Difference between revisions
No edit summary |
No edit summary |
||
Line 1: | Line 1: | ||
{{Short description|Method of analyzing variables in software}} | {{Short description|Method of analyzing variables in software}} | ||
डेटा-फ्लो विश्लेषण एक [[कंप्यूटर प्रोग्राम]] में विभिन्न बिंदुओं पर गणना किए गए मानों के संभावित | डेटा-फ्लो विश्लेषण एक [[कंप्यूटर प्रोग्राम]] में विभिन्न बिंदुओं पर गणना किए गए मानों के संभावित समुच्चयके बारे में जानकारी एकत्र करने की एक विधि है। एक प्रोग्राम के [[नियंत्रण-प्रवाह ग्राफ]] (CFG) का उपयोग प्रोग्राम के उन हिस्सों को निर्धारित करने के लिए किया जाता है, जिनके लिए एक चर को निर्दिष्ट एक विशेष मान प्रचारित हो सकता है। एकत्र की गई जानकारी का उपयोग प्रायः [[संकलक]] द्वारा प्रोग्राम को अनुकूलित करते समय किया जाता है। डेटा-प्रवाह विश्लेषण का एक प्रामाणिक उदाहरण परिभाषाओं तक पहुँच रहा है। | ||
कार्यक्रमों के डेटा प्रवाह विश्लेषण करने का एक आसान | कार्यक्रमों के डेटा प्रवाह विश्लेषण करने का एक आसान विधि नियंत्रण प्रवाह ग्राफ के प्रत्येक [[नोड (कंप्यूटर विज्ञान)]] के लिए डेटा प्रवाह समीकरण स्थापित करना है और प्रत्येक नोड पर स्थानीय रूप से इनपुट से आउटपुट की बार-बार गणना करके उन्हें हल करना है। प्रणाली स्थिर हो जाता है, अर्थात यह एक निश्चित बिंदु पर पहुंच जाता है। यह सामान्य दृष्टिकोण, जिसे किल्डाल की विधि भी कहा जाता है, [[गैरी किल्डाल]] द्वारा [[नौसेना स्नातकोत्तर स्कूल]] में पढ़ाने के समय विकसित किया गया था।<ref name="Kildall_1972_Optimization" /><ref name="Kildall_1973_Optimization" /><ref name="Cortesi_1999" /><ref name="Laws_2014_IEEE" /> | ||
{{Software development process}} | {{Software development process}} | ||
== | == वास्तविक सिद्धांत == | ||
डेटा-फ्लो विश्लेषण कार्यक्रम में चर को परिभाषित और उपयोग करने के | डेटा-फ्लो विश्लेषण कार्यक्रम में चर को परिभाषित और उपयोग करने के विधियों के बारे में जानकारी एकत्र करने की प्रक्रिया है। यह एक प्रक्रिया में प्रत्येक बिंदु पर विशेष जानकारी प्राप्त करने का प्रयास करता है। सामान्यतः, यह जानकारी [[बुनियादी ब्लॉक|मूलभूत खण्डों]] ों की सीमाओं पर प्राप्त करने के लिए पर्याप्त है, क्योंकि इससे मूलभूत खण्ड में बिंदुओं पर जानकारी की गणना करना आसान हो जाता है। आगे प्रवाह विश्लेषण में, खण्ड की निकास स्थिति खण्ड की प्रवेश स्थिति का एक कार्य है। यह कार्य खण्ड में बयानों के प्रभाव की संरचना है। एक खण्ड की प्रवेश स्थिति उसके पूर्ववर्तियों के निकास राज्यों का एक कार्य है। इससे डेटा-फ्लो समीकरणों का एक समुच्चय प्राप्त होता है: | ||
प्रत्येक | प्रत्येक खण्ड बी के लिए: | ||
: <math> out_b = trans_b (in_b) </math> | : <math> out_b = trans_b (in_b) </math> | ||
: <math> in_b = join_{p \in pred_b}(out_p) </math> | : <math> in_b = join_{p \in pred_b}(out_p) </math> | ||
इस में, <math> trans_b </math> | इस में, <math> trans_b </math> खण्ड का स्थानांतरण कार्य है <math>b</math>. यह प्रवेश अवस्था पर काम करता है <math>in_b</math>, बाहर निकलने की स्थिति प्रदान करना <math>out_b</math>. [[शामिल हों (गणित)|सम्मिलित हों]] <math>join</math> पूर्ववर्तियों के निकास राज्यों को जोड़ती है <math>p \in pred_b</math> का <math>b</math>, की प्रवेश स्थिति प्रदान करना <math>b</math>. | ||
समीकरणों के इस | समीकरणों के इस समुच्चय को हल करने के पश्चात, खण्ड सीमाओं पर कार्यक्रम के गुणों को प्राप्त करने के लिए खण्ड के प्रवेश और/या निकास राज्यों का उपयोग किया जा सकता है। एक मूलभूत खण्ड के अंदर एक बिंदु पर जानकारी प्राप्त करने के लिए अलग-अलग प्रत्येक बयान के हस्तांतरण प्रकार्य को अलग से प्रयुक्त किया जा सकता है। | ||
प्रत्येक विशेष प्रकार के डेटा-प्रवाह विश्लेषण का अपना विशिष्ट स्थानांतरण कार्य होता है और संचालन में | प्रत्येक विशेष प्रकार के डेटा-प्रवाह विश्लेषण का अपना विशिष्ट स्थानांतरण कार्य होता है और संचालन में सम्मिलित होता है। कुछ डेटा-फ्लो समस्याओं के लिए बैकवर्ड फ्लो विश्लेषण की आवश्यकता होती है। यह एक ही योजना का पालन करता है, अतिरिक्त इसके कि स्थानांतरण प्रकार्य प्रवेश राज्य को उत्पन्न करने वाली निकास स्थिति पर प्रयुक्त होता है, और ज्वाइन ऑपरेशन उत्तराधिकारी के प्रवेश राज्यों पर बाहर निकलने की स्थिति उत्पन्न करने के लिए काम करता है। | ||
[[प्रवेश बिंदु]] (आगे प्रवाह में) एक महत्वपूर्ण भूमिका निभाता है: चूंकि इसका कोई पूर्ववर्ती नहीं है, इसकी प्रवेश स्थिति विश्लेषण की | [[प्रवेश बिंदु]] (आगे प्रवाह में) एक महत्वपूर्ण भूमिका निभाता है: चूंकि इसका कोई पूर्ववर्ती नहीं है, इसकी प्रवेश स्थिति विश्लेषण की प्रारंभ में अच्छी प्रकार से परिभाषित है। उदाहरण के लिए, ज्ञात मान वाले स्थानीय चर का समुच्चयखाली है। यदि नियंत्रण-प्रवाह ग्राफ़ में चक्र नहीं हैं (प्रक्रिया में कोई स्पष्ट या अंतर्निहित नियंत्रण प्रवाह#लूप नहीं थे) तो समीकरणों को हल करना सीधा है। नियंत्रण-प्रवाह ग्राफ तब [[टोपोलॉजिकल सॉर्ट]] हो सकता है; इस प्रकार के क्रम में चल रहे, प्रत्येक खण्ड की प्रारंभ में प्रवेश राज्यों की गणना की जा सकती है, क्योंकि उस खण्ड के सभी पूर्ववर्तियों को पहले ही संसाधित किया जा चुका है, इसलिए उनके निकास राज्य उपलब्ध हैं। यदि नियंत्रण-प्रवाह ग्राफ़ में चक्र होते हैं, तो अधिक उन्नत एल्गोरिथम की आवश्यकता होती है। | ||
== एक पुनरावृत्त एल्गोरिथम == | == एक पुनरावृत्त एल्गोरिथम == | ||
डेटा-प्रवाह समीकरणों को हल करने का सबसे आम | डेटा-प्रवाह समीकरणों को हल करने का सबसे आम विधि पुनरावृत्त एल्गोरिथम का उपयोग करना है। यह प्रत्येक खण्ड के इन-स्टेट के अनुमान से प्रारंभ होता है। इसके पश्चातबाहरी राज्यों की गणना इन-स्टेट्स पर स्थानांतरण प्रकार्यों को प्रयुक्त करके की जाती है। इनमें से, इन-स्टेट्स को ज्वाइन ऑपरेशंस प्रयुक्त करके अपडेट किया जाता है। पश्चातके दो चरणों को तब तक दोहराया जाता है जब तक कि हम तथाकथित निश्चित बिंदु तक नहीं पहुंच जाते हैं: ऐसी स्थिति जिसमें इन-स्टेट्स (और परिणाम में आउट-स्टेट्स) नहीं बदलते हैं। | ||
डेटा-प्रवाह समीकरणों को हल करने के लिए एक | डेटा-प्रवाह समीकरणों को हल करने के लिए एक मूलभूत एल्गोरिथम राउंड-रॉबिन पुनरावृत्ति एल्गोरिथम है: | ||
:''i'' के लिए ← 1 से ''N'' | :''i'' के लिए ← 1 से ''N'' | ||
::''नोड i प्रारंभ करें'' | ::''नोड i प्रारंभ करें'' | ||
: जबकि ( | : जबकि (समुच्चय अभी भी बदल रहे हैं) | ||
::''i'' के लिए ← 1 से ''N'' | ::''i'' के लिए ← 1 से ''N'' | ||
:::'' नोड i पर पुनर्गणना | :::'' नोड i पर पुनर्गणना समुच्चयकरता है'' | ||
=== अभिसरण === | === अभिसरण === | ||
प्रयोग करने योग्य होने के लिए, पुनरावृत्त दृष्टिकोण वास्तव में एक निश्चित बिंदु तक पहुंचना चाहिए। इसकी गारंटी दी जा सकती है | प्रयोग करने योग्य होने के लिए, पुनरावृत्त दृष्टिकोण वास्तव में एक निश्चित बिंदु तक पहुंचना चाहिए। इसकी गारंटी दी जा सकती है | ||
राज्यों के मूल्य डोमेन के संयोजन, स्थानांतरण कार्यों और | राज्यों के मूल्य डोमेन के संयोजन, स्थानांतरण कार्यों और सम्मिलित होने के संचालन पर बाधाओं को प्रयुक्त करके। | ||
मूल्य डोमेन सीमित ऊंचाई के साथ आंशिक क्रम होना चाहिए ( | मूल्य डोमेन सीमित ऊंचाई के साथ आंशिक क्रम होना चाहिए (अर्थात, कोई अनंत आरोही श्रृंखला नहीं है <math>x_1</math> < <math>x_2</math> <...). इस आंशिक क्रम के संबंध में स्थानांतरण प्रकार्य और जॉइन ऑपरेशन का संयोजन [[मोनोटोनिक]] होना चाहिए। मोनोटोनिकिटी यह सुनिश्चित करती है कि प्रत्येक पुनरावृत्ति पर मान या तो समान रहेगा या बड़ा होगा, जबकि परिमित ऊंचाई सुनिश्चित करती है कि यह अनिश्चित काल तक नहीं बढ़ सकता है। इस प्रकार हम अंतत: एक ऐसी स्थिति पर पहुंच जाएंगे जहां सभी x के लिए T(x) = x, जो नियत बिंदु है। | ||
=== कार्य सूची दृष्टिकोण === | === कार्य सूची दृष्टिकोण === | ||
ऊपर दिए गए एल्गोरिथम में सुधार करना आसान है, यह देखते हुए कि | ऊपर दिए गए एल्गोरिथम में सुधार करना आसान है, यह देखते हुए कि खण्ड की इन-स्टेट स्थिति नहीं बदलेगी यदि इसके पूर्ववर्तियों के बाहरी राज्य नहीं बदलते हैं। इसलिए, हम एक कार्य सूची प्रस्तुत करते हैं: उन [[बुनियादी ब्लॉक|खण्डों]] की सूची जिन्हें अभी भी संसाधित करने की आवश्यकता है। जब भी किसी खण्ड की बाहरी स्थिति बदलती है, हम उसके उत्तराधिकारियों को कार्य सूची में जोड़ देते हैं। प्रत्येक पुनरावृत्ति में, कार्य सूची से एक खण्डहटा दिया जाता है। इसकी आउट-स्टेट गणना की जाती है। यदि बाहरी राज्य बदल गया है, तो खण्डके उत्तराधिकारी कार्य सूची में जुड़ जाते हैं। दक्षता के लिए, कार्य सूची में एक खण्ड एक से अधिक बार नहीं होना चाहिए। | ||
एल्गोरिदम को कार्य सूची में सूचना-सृजन करने वाले | एल्गोरिदम को कार्य सूची में सूचना-सृजन करने वाले खण्ड डालकर प्रारंभ किया जाता है। यह समाप्त हो जाता है जब | ||
कार्य सूची खाली है। | कार्य सूची खाली है। | ||
=== आदेश देना === | === आदेश देना === | ||
डेटा-फ्लो समीकरणों को क्रमिक रूप से हल करने की दक्षता उस क्रम से प्रभावित होती है जिस पर स्थानीय नोड्स का | डेटा-फ्लो समीकरणों को क्रमिक रूप से हल करने की दक्षता उस क्रम से प्रभावित होती है जिस पर स्थानीय नोड्स का भ्रमण किया जाता है।<ref name="Cooper_2004"/> इसके अतिरिक्त, यह इस बात पर निर्भर करता है कि सीएफजी पर आगे या पीछे डेटा प्रवाह विश्लेषण के लिए डेटा प्रवाह समीकरणों का उपयोग किया जाता है या नहीं। सहजता से, आगे प्रवाह की समस्या में, यह सबसे तेज़ होगा यदि खण्डके सभी पूर्ववर्तियों को खण्डसे पहले संसाधित किया गया हो, तब से पुनरावृति नवीनतम जानकारी का उपयोग करेगी। लूप के अभाव में खण्ड को इस प्रकार से ऑर्डर करना संभव है कि प्रत्येक खण्ड को केवल एक बार संसाधित करके सही आउट-स्टेट्स की गणना की जाती है। | ||
निम्नलिखित में, डेटा-प्रवाह समीकरणों को हल करने के लिए कुछ पुनरावृति क्रमों पर चर्चा की गई है | निम्नलिखित में, डेटा-प्रवाह समीकरणों को हल करने के लिए कुछ पुनरावृति क्रमों पर चर्चा की गई है | ||
(एक नियंत्रण-प्रवाह ग्राफ के पुनरावृति क्रम से संबंधित अवधारणा a का [[ट्री ट्रैवर्सल]] है | (एक नियंत्रण-प्रवाह ग्राफ के पुनरावृति क्रम से संबंधित अवधारणा a का [[ट्री ट्रैवर्सल]] है | ||
[[वृक्ष (ग्राफ सिद्धांत)]])। | [[वृक्ष (ग्राफ सिद्धांत)]])। | ||
* यादृच्छिक क्रम - यह पुनरावृत्ति क्रम इस बात से अवगत नहीं है कि डेटा-प्रवाह समीकरण आगे या पीछे की डेटा-प्रवाह समस्या को हल करते हैं या नहीं। इसलिए, विशिष्ट पुनरावृति आदेशों की तुलना में प्रदर्शन अपेक्षाकृत खराब है। | * यादृच्छिक क्रम - यह पुनरावृत्ति क्रम इस बात से अवगत नहीं है कि डेटा-प्रवाह समीकरण आगे या पीछे की डेटा-प्रवाह समस्या को हल करते हैं या नहीं। इसलिए, विशिष्ट पुनरावृति आदेशों की तुलना में प्रदर्शन अपेक्षाकृत खराब है। | ||
* [[मेल आदेश]] - यह बैकवर्ड डेटा-फ्लो समस्याओं के लिए एक विशिष्ट पुनरावृत्ति क्रम है। 'पोस्टऑर्डर इटरेशन' में, एक नोड का | * [[मेल आदेश]] - यह बैकवर्ड डेटा-फ्लो समस्याओं के लिए एक विशिष्ट पुनरावृत्ति क्रम है। 'पोस्टऑर्डर इटरेशन' में, एक नोड का भ्रमण उसके सभी उत्तराधिकारी नोड्स का भ्रमण करने के पश्चातकिया जाता है। विशिष्ट रूप से, ''पोस्टऑर्डर पुनरावृत्ति'' को गहराई-प्रथम रणनीति के साथ कार्यान्वित किया जाता है। | ||
* डेप्थ-फर्स्ट सर्च # वर्टेक्स ऑर्डरिंग - यह फॉरवर्ड डेटा-फ्लो समस्याओं के लिए एक विशिष्ट पुनरावृत्ति क्रम है। रिवर्स-पोस्टऑर्डर पुनरावृति में, इसके किसी भी उत्तराधिकारी नोड का | * डेप्थ-फर्स्ट सर्च # वर्टेक्स ऑर्डरिंग - यह फॉरवर्ड डेटा-फ्लो समस्याओं के लिए एक विशिष्ट पुनरावृत्ति क्रम है। रिवर्स-पोस्टऑर्डर पुनरावृति में, इसके किसी भी उत्तराधिकारी नोड का भ्रमण करने से पहले एक नोड का भ्रमण किया जाता है, अतिरिक्त इसके कि जब उत्तराधिकारी पीछे के किनारे तक पहुंच जाता है। (ध्यान दें कि रिवर्स पोस्टऑर्डर डेप्थ-फर्स्ट सर्च#वर्टेक्स ऑर्डरिंग के समान नहीं है।) | ||
=== प्रारंभ === | === प्रारंभ === | ||
सही और | सही और स्पष्ट परिणाम प्राप्त करने के लिए इन-स्टेट्स का प्रारंभिक मूल्य महत्वपूर्ण है। | ||
यदि परिणामों का उपयोग संकलक अनुकूलन के लिए किया जाता है, तो उन्हें रूढ़िवादी जानकारी प्रदान करनी चाहिए, अर्थात सूचना को | |||
फिक्सपॉइंट एल्गोरिथ्म का पुनरावृत्ति मूल्यों को अधिकतम तत्व की दिशा में ले जाएगा। इसलिए अधिकतम तत्व वाले सभी | यदि परिणामों का उपयोग संकलक अनुकूलन के लिए किया जाता है, तो उन्हें रूढ़िवादी जानकारी प्रदान करनी चाहिए, अर्थात सूचना को प्रयुक्त करते समय, कार्यक्रम को शब्दार्थ नहीं बदलना चाहिए। | ||
डेटा-प्रवाह समस्या। यदि न्यूनतम तत्व पूरी | |||
फिक्सपॉइंट एल्गोरिथ्म का पुनरावृत्ति मूल्यों को अधिकतम तत्व की दिशा में ले जाएगा। इसलिए अधिकतम तत्व वाले सभी खण्डों को प्रारंभ करना उपयोगी नहीं है। अधिकतम से कम मान वाले राज्य में कम से कम एक खण्ड प्रारंभ होता है। विवरण पर निर्भर करता है | |||
डेटा-प्रवाह समस्या। यदि न्यूनतम तत्व पूरी प्रकार से रूढ़िवादी जानकारी का प्रतिनिधित्व करता है, तो परिणाम डेटा-प्रवाह पुनरावृत्ति के समय भी सुरक्षित रूप से उपयोग किए जा सकते हैं। यदि यह सबसे स्पष्ट जानकारी का प्रतिनिधित्व करता है, तो परिणामों को प्रयुक्त करने से पहले फिक्सपॉइंट तक पहुंचना चाहिए। | |||
== उदाहरण == | == उदाहरण == | ||
निम्नलिखित कंप्यूटर प्रोग्राम के गुणों के उदाहरण हैं जिनकी गणना डेटा-प्रवाह विश्लेषण द्वारा की जा सकती है। | निम्नलिखित कंप्यूटर प्रोग्राम के गुणों के उदाहरण हैं जिनकी गणना डेटा-प्रवाह विश्लेषण द्वारा की जा सकती है। | ||
ध्यान दें कि डेटा-प्रवाह विश्लेषण द्वारा परिकलित गुण | |||
ध्यान दें कि डेटा-प्रवाह विश्लेषण द्वारा परिकलित गुण सामान्यतः वास्तविक के केवल अनुमान होते हैं | |||
गुण। ऐसा इसलिए है क्योंकि डेटा-प्रवाह विश्लेषण बिना CFG के सिंटैक्टिकल स्ट्रक्चर पर काम करता है | गुण। ऐसा इसलिए है क्योंकि डेटा-प्रवाह विश्लेषण बिना CFG के सिंटैक्टिकल स्ट्रक्चर पर काम करता है | ||
कार्यक्रम के | |||
कार्यक्रम के स्पष्ट नियंत्रण प्रवाह का अनुकरण करना। | |||
चूंकि, अभ्यास में अभी भी उपयोगी होने के लिए, डेटा प्रवाह विश्लेषण एल्गोरिदम को सामान्यतः गणना करने के लिए डिज़ाइन किया गया है | |||
वास्तविक कार्यक्रम गुणों का एक ऊपरी क्रमशः निचला सन्निकटन। | वास्तविक कार्यक्रम गुणों का एक ऊपरी क्रमशः निचला सन्निकटन। | ||
=== आगे का विश्लेषण === | === आगे का विश्लेषण === | ||
[[परिभाषा तक पहुँचना]] एनालिसिस प्रत्येक प्रोग्राम पॉइंट के लिए परिभाषाओं के | [[परिभाषा तक पहुँचना]] एनालिसिस प्रत्येक प्रोग्राम पॉइंट के लिए परिभाषाओं के समुच्चयकी गणना करता है | ||
संभावित रूप से इस कार्यक्रम बिंदु तक पहुँच सकते हैं। | संभावित रूप से इस कार्यक्रम बिंदु तक पहुँच सकते हैं। | ||
Line 88: | Line 99: | ||
{{col-end}} | {{col-end}} | ||
=== पिछड़ा विश्लेषण === | === पिछड़ा विश्लेषण === | ||
प्रत्यक्ष चर विश्लेषण प्रत्येक प्रोग्राम के लिए उन चरों की गणना करता है जो हो सकते हैं | |||
संभावित रूप से उनके अगले लेखन अद्यतन से पहले | संभावित रूप से उनके अगले लेखन अद्यतन से पहले पश्चातमें पढ़ें। परिणाम सामान्यतः द्वारा उपयोग किया जाता है | ||
[[मृत कोड उन्मूलन]] उन बयानों को हटाने के लिए जो एक चर को असाइन करते हैं जिसका मूल्य | [[मृत कोड उन्मूलन]] उन बयानों को हटाने के लिए जो एक चर को असाइन करते हैं जिसका मूल्य पश्चात में उपयोग नहीं किया जाता है। | ||
खण्ड की इन-स्टेट चरों का समुच्चय है जो इसके प्रारंभ में प्रत्यक्ष हैं। स्थानांतरण प्रकार्य प्रयुक्त होने से पहले और वास्तविक निहित मानों की गणना करने से पहले, इसमें प्रारंभिक रूप से खण्डमें सभी चर प्रत्यक्ष (निहित) होते हैं। इस खण्डके अंदर लिखे गए चरों को मारकर स्टेटमेंट का स्थानांतरण प्रकार्य प्रयुक्त किया जाता है (उन्हें प्रत्यक्ष चरों के समुच्चय से हटा दें)। खण्ड की आउट-स्टेट चरों का समुच्चय है जो खण्ड के अंत में रहते हैं और खण्ड के उत्तराधिकारियों के इन-स्टेट्स के संघ द्वारा गणना की जाती है। | |||
प्रारंभिक कोड: | प्रारंभिक कोड: | ||
Line 132: | Line 143: | ||
// बाहर:{} | // बाहर:{} | ||
{{col-end}} | {{col-end}} | ||
b3 की इन-स्टेट में केवल b और d होते हैं, क्योंकि c लिखा गया है। बी 1 का आउट-स्टेट बी 2 और बी 3 के इन-स्टेट्स का संघ है। b2 में c की परिभाषा को हटाया जा सकता है, क्योंकि c स्टेटमेंट के तुरंत | b3 की इन-स्टेट में केवल b और d होते हैं, क्योंकि c लिखा गया है। बी 1 का आउट-स्टेट बी 2 और बी 3 के इन-स्टेट्स का संघ है। b2 में c की परिभाषा को हटाया जा सकता है, क्योंकि c स्टेटमेंट के तुरंत पश्चातप्रत्यक्ष नहीं होता है। | ||
डेटा-फ्लो समीकरणों को हल करना सभी इन-स्टेट्स और आउट-स्टेट्स को खाली | डेटा-फ्लो समीकरणों को हल करना सभी इन-स्टेट्स और आउट-स्टेट्स को खाली समुच्चयमें इनिशियलाइज़ करने से प्रारंभ होता है। कार्य सूची (बैकवर्ड फ्लो के लिए विशिष्ट) में निकास बिंदु (b3) सम्मिलित करके कार्य सूची को आरंभीकृत किया जाता है। इसकी गणना इन-स्टेट पिछले एक से भिन्न होती है, इसलिए इसके पूर्ववर्ती b1 और b2 सम्मिलित किए जाते हैं और प्रक्रिया जारी रहती है। प्रगति को नीचे दी गई तालिका में संक्षेपित किया गया है। | ||
{| class="wikitable" | {| class="wikitable" | ||
Line 168: | Line 179: | ||
| () | | () | ||
|} | |} | ||
ध्यान दें कि b1 को b2 से पहले सूची में | ध्यान दें कि b1 को b2 से पहले सूची में अंकित किया गया था, जिसने b1 को दो बार संसाधित करने के लिए बाध्य किया (b1 को b2 के पूर्ववर्ती के रूप में फिर से अंकित किया गया था)। b1 से पहले b2 डालने से पहले पूरा हो जाता। | ||
खाली | खाली समुच्चयके साथ आरंभ करना एक आशावादी आरंभीकरण है: सभी चर मृत के रूप में प्रारंभ होते हैं। ध्यान दें कि आउट-स्टेट्स एक पुनरावृत्ति से अगले तक सिकुड़ नहीं सकते हैं, चूंकि आउट-स्टेट इन-स्टेट से छोटा हो सकता है। यह इस तथ्य से देखा जा सकता है कि पहले पुनरावृत्ति के पश्चातराज्य के अंदर के परिवर्तन से ही बाहरी राज्य बदल सकता है। चूंकि इन-स्टेट खाली समुच्चयके रूप में प्रारंभ होता है, यह केवल आगे के पुनरावृत्तियों में बढ़ सकता है। | ||
== अन्य दृष्टिकोण == | == अन्य दृष्टिकोण == | ||
2002 में, मार्कस मोहनेन ने डेटा-फ्लो विश्लेषण की एक नई विधि का वर्णन किया जिसमें डेटा-फ्लो ग्राफ के स्पष्ट निर्माण की आवश्यकता नहीं है,<ref name="Mohnen_2002"/>इसके | 2002 में, मार्कस मोहनेन ने डेटा-फ्लो विश्लेषण की एक नई विधि का वर्णन किया जिसमें डेटा-फ्लो ग्राफ के स्पष्ट निर्माण की आवश्यकता नहीं है,<ref name="Mohnen_2002"/>इसके अतिरिक्त कार्यक्रम की अमूर्त व्याख्या पर भरोसा करना और प्रोग्राम काउंटरों का एक कार्यशील समुच्चयरखना। प्रत्येक सनिबंधन शाखा में, दोनों लक्ष्य कार्य समुच्चयमें जोड़े जाते हैं। यथासंभव अधिक से अधिक निर्देशों के लिए प्रत्येक पथ का अनुसरण किया जाता है (कार्यक्रम के अंत तक या जब तक कि यह बिना किसी बदलाव के लूप हो जाता है), और फिर समुच्चयसे हटा दिया जाता है और अगले प्रोग्राम काउंटर को पुनः प्राप्त कर लिया जाता है। | ||
[[नियंत्रण प्रवाह विश्लेषण]] और डेटा प्रवाह विश्लेषण का एक संयोजन | [[नियंत्रण प्रवाह विश्लेषण]] और डेटा प्रवाह विश्लेषण का एक संयोजन प्रणाली की कार्यात्मकताओं को प्रयुक्त करने वाले एकजुट स्रोत कोड क्षेत्रों की पहचान करने में उपयोगी और पूरक सिद्ध हुआ है ([[उदाहरण]] के लिए, सॉफ़्टवेयर सुविधा, आवश्यकताएं या उपयोग के स्थितियों)।<ref name="Kuang_2015"/> | ||
== समस्याओं का विशेष वर्ग == | == समस्याओं का विशेष वर्ग == | ||
डेटा प्रवाह समस्याओं के कई विशेष वर्ग हैं जिनके कुशल या सामान्य समाधान हैं। | डेटा प्रवाह समस्याओं के कई विशेष वर्ग हैं जिनके कुशल या सामान्य समाधान हैं। | ||
=== बिट वेक्टर समस्याएं === | === बिट वेक्टर समस्याएं === | ||
ऊपर दिए गए उदाहरण ऐसी समस्याएँ हैं जिनमें डेटा-प्रवाह मान एक | ऊपर दिए गए उदाहरण ऐसी समस्याएँ हैं जिनमें डेटा-प्रवाह मान एक समुच्चयहै, उदा. पहुँच परिभाषाओं का समुच्चय(प्रोग्राम में परिभाषा स्थिति के लिए बिट का उपयोग करके), या प्रत्यक्ष चरों का समुच्चय। इन समुच्चयों को कुशलतापूर्वक [[बिट सरणी]] के रूप में प्रदर्शित किया जा सकता है, जिसमें प्रत्येक बिट एक विशेष तत्व की समुच्चयसदस्यता का प्रतिनिधित्व करता है। इस प्रतिनिधित्व का उपयोग करते हुए, ज्वाइन और स्थानांतरण प्रकार्यों को बिटवाइज़ लॉजिकल ऑपरेशंस के रूप में प्रयुक्त किया जा सकता है। ज्वाइन ऑपरेशन सामान्यतः संघ या चौराहा है, जिसे बिटवाइज़ '' लॉजिकल या '' और '' लॉजिकल एंड '' द्वारा प्रयुक्त किया जाता है। | ||
प्रत्येक | |||
प्रत्येक खण्डके लिए स्थानांतरण प्रकार्य को तथाकथित 'जीन' और 'किल' समुच्चयमें विघटित किया जा सकता है। | |||
एक उदाहरण के रूप में, लाइव- | एक उदाहरण के रूप में, लाइव-चर विश्लेषण में, ज्वाइन ऑपरेशन यूनियन है। ''किल'' समुच्चयचरों का समुच्चयहै जो एक खण्डमें लिखे जाते हैं, जबकि ''जेन'' समुच्चय चरों का समुच्चय है जो पहले लिखे बिना पढ़े जाते हैं। डेटा प्रवाह समीकरण बन जाते हैं | ||
:<math> out_b = \bigcup_{s \in succ_b} in_s </math> | :<math> out_b = \bigcup_{s \in succ_b} in_s </math> | ||
Line 194: | Line 206: | ||
इन (बी) = (बाहर (बी) 'और नहीं' मारना (बी)) 'या' जीन (बी) | इन (बी) = (बाहर (बी) 'और नहीं' मारना (बी)) 'या' जीन (बी) | ||
डेटा प्रवाह समस्याएं जिनमें डेटा-प्रवाह मानों के | डेटा प्रवाह समस्याएं जिनमें डेटा-प्रवाह मानों के समुच्चयहोते हैं जिन्हें बिट वैक्टर के रूप में प्रदर्शित किया जा सकता है, उन्हें 'बिट वेक्टर समस्याएं', 'जेन-किल समस्याएं', या 'स्थानीय रूप से अलग करने योग्य समस्याएं' कहा जाता है।<ref name="Reps_1995"/> ऐसी समस्याओं के सामान्य बहुपद-समय समाधान हैं।<ref name="Knoop_1996"/> | ||
ऊपर बताई गई पहुंच परिभाषाओं और | ऊपर बताई गई पहुंच परिभाषाओं और प्रत्यक्ष चर समस्याओं के अतिरिक्त, निम्नलिखित समस्याएं बिटवेक्टर समस्याओं के उदाहरण हैं:<ref name="Knoop_1996"/>* उपलब्ध भाव | ||
* बहुत व्यस्त भाव | * बहुत व्यस्त भाव | ||
* यूज-डिफाइन चेन | यूज-डेफिनिशन चेन | * यूज-डिफाइन चेन | यूज-डेफिनिशन चेन | ||
=== आईएफडीएस समस्याएं === | === आईएफडीएस समस्याएं === | ||
अंतर-प्रक्रियात्मक, परिमित, वितरणात्मक, | अंतर-प्रक्रियात्मक, परिमित, वितरणात्मक, सब समुच्चय समस्याएँ या आईएफडीएस समस्याएँ सामान्य बहुपद-समय समाधान के साथ समस्या का एक अन्य वर्ग हैं।<ref name="Reps_1995"/><ref name="Naeem_2010"/> इन समस्याओं के समाधान संदर्भ-संवेदनशील और प्रवाह-संवेदनशील डेटा प्रवाह विश्लेषण प्रदान करते हैं। | ||
लोकप्रिय प्रोग्रामिंग भाषाओं के लिए | लोकप्रिय प्रोग्रामिंग भाषाओं के लिए आईएफडीएस - आधारित डेटा प्रवाह विश्लेषण के कई कार्यान्वयन हैं, उदा। सूत में<ref name="Bodden_2012"/> और कुछ नहीं<ref name="Rapoport_2015"/> जावा विश्लेषण के लिए रूपरेखा। | ||
प्रत्येक बिटवेक्टर समस्या भी एक | प्रत्येक बिटवेक्टर समस्या भी एक आईएफडीएस समस्या है, किन्तु कई महत्वपूर्ण आईएफडीएस समस्याएँ हैं जो बिटवेक्टर समस्याएँ नहीं हैं, जिनमें वास्तविक-प्रत्यक्ष चर और संभवतः-अनियंत्रित चर सम्मिलित हैं। | ||
== संवेदनशीलता == | == संवेदनशीलता == | ||
डेटा-प्रवाह विश्लेषण | डेटा-प्रवाह विश्लेषण सामान्यतः पथ-असंवेदनशील होता है, चूंकि डेटा-प्रवाह समीकरणों को परिभाषित करना संभव है जो पथ-संवेदनशील विश्लेषण उत्पन्न करते हैं। | ||
* एक प्रवाह-संवेदनशील विश्लेषण एक कार्यक्रम में बयानों के क्रम को ध्यान में रखता है। उदाहरण के लिए, एक प्रवाह-असंवेदनशील सूचक उपनाम विश्लेषण चर ''x'' और ''y'' को निर्धारित कर सकता है जो एक ही स्थान को संदर्भित कर सकता है, जबकि एक प्रवाह-संवेदनशील विश्लेषण कथन 20 के | * एक प्रवाह-संवेदनशील विश्लेषण एक कार्यक्रम में बयानों के क्रम को ध्यान में रखता है। उदाहरण के लिए, एक प्रवाह-असंवेदनशील सूचक उपनाम विश्लेषण चर ''x'' और ''y'' को निर्धारित कर सकता है जो एक ही स्थान को संदर्भित कर सकता है, जबकि एक प्रवाह-संवेदनशील विश्लेषण कथन 20 के पश्चातनिर्धारित कर सकता है, चर ''x'' और ''y'' उसी स्थान को संदर्भित कर सकता है। | ||
* एक पथ-संवेदनशील विश्लेषण | * एक पथ-संवेदनशील विश्लेषण सनिबंधन शाखा निर्देशों पर विधेय पर निर्भर विश्लेषण जानकारी के विभिन्न टुकड़ों की गणना करता है। उदाहरण के लिए, यदि किसी शाखा में कोई निबंधन है {{code|x>0}}, तो फ़ॉल-थ्रू पथ पर, विश्लेषण यह मान लेगा {{code|1=x<=0}} और शाखा के निशाने पर यह मान लिया जाएगा कि वास्तव में {{code|x>0}} रखती है। | ||
* एक संदर्भ-संवेदनशील विश्लेषण एक ''अंतरप्रक्रियात्मक'' विश्लेषण है जो | * एक संदर्भ-संवेदनशील विश्लेषण एक ''अंतरप्रक्रियात्मक'' विश्लेषण है जो प्रकार्य कॉल के लक्ष्य का विश्लेषण करते समय कॉलिंग संदर्भ पर विचार करता है। विशेष रूप से, संदर्भ जानकारी का उपयोग करके कोई भी वास्तविककॉल साइट पर वापस जा सकता है, जबकि उस जानकारी के बिना, विश्लेषण जानकारी को सभी संभावित कॉल साइटों पर वापस प्रचारित करना पड़ता है, संभावित रूप से नियतता खो देता है। | ||
== डेटा-प्रवाह विश्लेषणों की सूची == | == डेटा-प्रवाह विश्लेषणों की सूची == |
Revision as of 20:05, 25 February 2023
डेटा-फ्लो विश्लेषण एक कंप्यूटर प्रोग्राम में विभिन्न बिंदुओं पर गणना किए गए मानों के संभावित समुच्चयके बारे में जानकारी एकत्र करने की एक विधि है। एक प्रोग्राम के नियंत्रण-प्रवाह ग्राफ (CFG) का उपयोग प्रोग्राम के उन हिस्सों को निर्धारित करने के लिए किया जाता है, जिनके लिए एक चर को निर्दिष्ट एक विशेष मान प्रचारित हो सकता है। एकत्र की गई जानकारी का उपयोग प्रायः संकलक द्वारा प्रोग्राम को अनुकूलित करते समय किया जाता है। डेटा-प्रवाह विश्लेषण का एक प्रामाणिक उदाहरण परिभाषाओं तक पहुँच रहा है।
कार्यक्रमों के डेटा प्रवाह विश्लेषण करने का एक आसान विधि नियंत्रण प्रवाह ग्राफ के प्रत्येक नोड (कंप्यूटर विज्ञान) के लिए डेटा प्रवाह समीकरण स्थापित करना है और प्रत्येक नोड पर स्थानीय रूप से इनपुट से आउटपुट की बार-बार गणना करके उन्हें हल करना है। प्रणाली स्थिर हो जाता है, अर्थात यह एक निश्चित बिंदु पर पहुंच जाता है। यह सामान्य दृष्टिकोण, जिसे किल्डाल की विधि भी कहा जाता है, गैरी किल्डाल द्वारा नौसेना स्नातकोत्तर स्कूल में पढ़ाने के समय विकसित किया गया था।[1][2][3][4]
Part of a series on |
Software development |
---|
वास्तविक सिद्धांत
डेटा-फ्लो विश्लेषण कार्यक्रम में चर को परिभाषित और उपयोग करने के विधियों के बारे में जानकारी एकत्र करने की प्रक्रिया है। यह एक प्रक्रिया में प्रत्येक बिंदु पर विशेष जानकारी प्राप्त करने का प्रयास करता है। सामान्यतः, यह जानकारी मूलभूत खण्डों ों की सीमाओं पर प्राप्त करने के लिए पर्याप्त है, क्योंकि इससे मूलभूत खण्ड में बिंदुओं पर जानकारी की गणना करना आसान हो जाता है। आगे प्रवाह विश्लेषण में, खण्ड की निकास स्थिति खण्ड की प्रवेश स्थिति का एक कार्य है। यह कार्य खण्ड में बयानों के प्रभाव की संरचना है। एक खण्ड की प्रवेश स्थिति उसके पूर्ववर्तियों के निकास राज्यों का एक कार्य है। इससे डेटा-फ्लो समीकरणों का एक समुच्चय प्राप्त होता है:
प्रत्येक खण्ड बी के लिए:
इस में, खण्ड का स्थानांतरण कार्य है . यह प्रवेश अवस्था पर काम करता है , बाहर निकलने की स्थिति प्रदान करना . सम्मिलित हों पूर्ववर्तियों के निकास राज्यों को जोड़ती है का , की प्रवेश स्थिति प्रदान करना .
समीकरणों के इस समुच्चय को हल करने के पश्चात, खण्ड सीमाओं पर कार्यक्रम के गुणों को प्राप्त करने के लिए खण्ड के प्रवेश और/या निकास राज्यों का उपयोग किया जा सकता है। एक मूलभूत खण्ड के अंदर एक बिंदु पर जानकारी प्राप्त करने के लिए अलग-अलग प्रत्येक बयान के हस्तांतरण प्रकार्य को अलग से प्रयुक्त किया जा सकता है।
प्रत्येक विशेष प्रकार के डेटा-प्रवाह विश्लेषण का अपना विशिष्ट स्थानांतरण कार्य होता है और संचालन में सम्मिलित होता है। कुछ डेटा-फ्लो समस्याओं के लिए बैकवर्ड फ्लो विश्लेषण की आवश्यकता होती है। यह एक ही योजना का पालन करता है, अतिरिक्त इसके कि स्थानांतरण प्रकार्य प्रवेश राज्य को उत्पन्न करने वाली निकास स्थिति पर प्रयुक्त होता है, और ज्वाइन ऑपरेशन उत्तराधिकारी के प्रवेश राज्यों पर बाहर निकलने की स्थिति उत्पन्न करने के लिए काम करता है।
प्रवेश बिंदु (आगे प्रवाह में) एक महत्वपूर्ण भूमिका निभाता है: चूंकि इसका कोई पूर्ववर्ती नहीं है, इसकी प्रवेश स्थिति विश्लेषण की प्रारंभ में अच्छी प्रकार से परिभाषित है। उदाहरण के लिए, ज्ञात मान वाले स्थानीय चर का समुच्चयखाली है। यदि नियंत्रण-प्रवाह ग्राफ़ में चक्र नहीं हैं (प्रक्रिया में कोई स्पष्ट या अंतर्निहित नियंत्रण प्रवाह#लूप नहीं थे) तो समीकरणों को हल करना सीधा है। नियंत्रण-प्रवाह ग्राफ तब टोपोलॉजिकल सॉर्ट हो सकता है; इस प्रकार के क्रम में चल रहे, प्रत्येक खण्ड की प्रारंभ में प्रवेश राज्यों की गणना की जा सकती है, क्योंकि उस खण्ड के सभी पूर्ववर्तियों को पहले ही संसाधित किया जा चुका है, इसलिए उनके निकास राज्य उपलब्ध हैं। यदि नियंत्रण-प्रवाह ग्राफ़ में चक्र होते हैं, तो अधिक उन्नत एल्गोरिथम की आवश्यकता होती है।
एक पुनरावृत्त एल्गोरिथम
डेटा-प्रवाह समीकरणों को हल करने का सबसे आम विधि पुनरावृत्त एल्गोरिथम का उपयोग करना है। यह प्रत्येक खण्ड के इन-स्टेट के अनुमान से प्रारंभ होता है। इसके पश्चातबाहरी राज्यों की गणना इन-स्टेट्स पर स्थानांतरण प्रकार्यों को प्रयुक्त करके की जाती है। इनमें से, इन-स्टेट्स को ज्वाइन ऑपरेशंस प्रयुक्त करके अपडेट किया जाता है। पश्चातके दो चरणों को तब तक दोहराया जाता है जब तक कि हम तथाकथित निश्चित बिंदु तक नहीं पहुंच जाते हैं: ऐसी स्थिति जिसमें इन-स्टेट्स (और परिणाम में आउट-स्टेट्स) नहीं बदलते हैं।
डेटा-प्रवाह समीकरणों को हल करने के लिए एक मूलभूत एल्गोरिथम राउंड-रॉबिन पुनरावृत्ति एल्गोरिथम है:
- i के लिए ← 1 से N
- नोड i प्रारंभ करें
- जबकि (समुच्चय अभी भी बदल रहे हैं)
- i के लिए ← 1 से N
- नोड i पर पुनर्गणना समुच्चयकरता है
- i के लिए ← 1 से N
अभिसरण
प्रयोग करने योग्य होने के लिए, पुनरावृत्त दृष्टिकोण वास्तव में एक निश्चित बिंदु तक पहुंचना चाहिए। इसकी गारंटी दी जा सकती है राज्यों के मूल्य डोमेन के संयोजन, स्थानांतरण कार्यों और सम्मिलित होने के संचालन पर बाधाओं को प्रयुक्त करके।
मूल्य डोमेन सीमित ऊंचाई के साथ आंशिक क्रम होना चाहिए (अर्थात, कोई अनंत आरोही श्रृंखला नहीं है < <...). इस आंशिक क्रम के संबंध में स्थानांतरण प्रकार्य और जॉइन ऑपरेशन का संयोजन मोनोटोनिक होना चाहिए। मोनोटोनिकिटी यह सुनिश्चित करती है कि प्रत्येक पुनरावृत्ति पर मान या तो समान रहेगा या बड़ा होगा, जबकि परिमित ऊंचाई सुनिश्चित करती है कि यह अनिश्चित काल तक नहीं बढ़ सकता है। इस प्रकार हम अंतत: एक ऐसी स्थिति पर पहुंच जाएंगे जहां सभी x के लिए T(x) = x, जो नियत बिंदु है।
कार्य सूची दृष्टिकोण
ऊपर दिए गए एल्गोरिथम में सुधार करना आसान है, यह देखते हुए कि खण्ड की इन-स्टेट स्थिति नहीं बदलेगी यदि इसके पूर्ववर्तियों के बाहरी राज्य नहीं बदलते हैं। इसलिए, हम एक कार्य सूची प्रस्तुत करते हैं: उन खण्डों की सूची जिन्हें अभी भी संसाधित करने की आवश्यकता है। जब भी किसी खण्ड की बाहरी स्थिति बदलती है, हम उसके उत्तराधिकारियों को कार्य सूची में जोड़ देते हैं। प्रत्येक पुनरावृत्ति में, कार्य सूची से एक खण्डहटा दिया जाता है। इसकी आउट-स्टेट गणना की जाती है। यदि बाहरी राज्य बदल गया है, तो खण्डके उत्तराधिकारी कार्य सूची में जुड़ जाते हैं। दक्षता के लिए, कार्य सूची में एक खण्ड एक से अधिक बार नहीं होना चाहिए।
एल्गोरिदम को कार्य सूची में सूचना-सृजन करने वाले खण्ड डालकर प्रारंभ किया जाता है। यह समाप्त हो जाता है जब कार्य सूची खाली है।
आदेश देना
डेटा-फ्लो समीकरणों को क्रमिक रूप से हल करने की दक्षता उस क्रम से प्रभावित होती है जिस पर स्थानीय नोड्स का भ्रमण किया जाता है।[5] इसके अतिरिक्त, यह इस बात पर निर्भर करता है कि सीएफजी पर आगे या पीछे डेटा प्रवाह विश्लेषण के लिए डेटा प्रवाह समीकरणों का उपयोग किया जाता है या नहीं। सहजता से, आगे प्रवाह की समस्या में, यह सबसे तेज़ होगा यदि खण्डके सभी पूर्ववर्तियों को खण्डसे पहले संसाधित किया गया हो, तब से पुनरावृति नवीनतम जानकारी का उपयोग करेगी। लूप के अभाव में खण्ड को इस प्रकार से ऑर्डर करना संभव है कि प्रत्येक खण्ड को केवल एक बार संसाधित करके सही आउट-स्टेट्स की गणना की जाती है।
निम्नलिखित में, डेटा-प्रवाह समीकरणों को हल करने के लिए कुछ पुनरावृति क्रमों पर चर्चा की गई है
(एक नियंत्रण-प्रवाह ग्राफ के पुनरावृति क्रम से संबंधित अवधारणा a का ट्री ट्रैवर्सल है
- यादृच्छिक क्रम - यह पुनरावृत्ति क्रम इस बात से अवगत नहीं है कि डेटा-प्रवाह समीकरण आगे या पीछे की डेटा-प्रवाह समस्या को हल करते हैं या नहीं। इसलिए, विशिष्ट पुनरावृति आदेशों की तुलना में प्रदर्शन अपेक्षाकृत खराब है।
- मेल आदेश - यह बैकवर्ड डेटा-फ्लो समस्याओं के लिए एक विशिष्ट पुनरावृत्ति क्रम है। 'पोस्टऑर्डर इटरेशन' में, एक नोड का भ्रमण उसके सभी उत्तराधिकारी नोड्स का भ्रमण करने के पश्चातकिया जाता है। विशिष्ट रूप से, पोस्टऑर्डर पुनरावृत्ति को गहराई-प्रथम रणनीति के साथ कार्यान्वित किया जाता है।
- डेप्थ-फर्स्ट सर्च # वर्टेक्स ऑर्डरिंग - यह फॉरवर्ड डेटा-फ्लो समस्याओं के लिए एक विशिष्ट पुनरावृत्ति क्रम है। रिवर्स-पोस्टऑर्डर पुनरावृति में, इसके किसी भी उत्तराधिकारी नोड का भ्रमण करने से पहले एक नोड का भ्रमण किया जाता है, अतिरिक्त इसके कि जब उत्तराधिकारी पीछे के किनारे तक पहुंच जाता है। (ध्यान दें कि रिवर्स पोस्टऑर्डर डेप्थ-फर्स्ट सर्च#वर्टेक्स ऑर्डरिंग के समान नहीं है।)
प्रारंभ
सही और स्पष्ट परिणाम प्राप्त करने के लिए इन-स्टेट्स का प्रारंभिक मूल्य महत्वपूर्ण है।
यदि परिणामों का उपयोग संकलक अनुकूलन के लिए किया जाता है, तो उन्हें रूढ़िवादी जानकारी प्रदान करनी चाहिए, अर्थात सूचना को प्रयुक्त करते समय, कार्यक्रम को शब्दार्थ नहीं बदलना चाहिए।
फिक्सपॉइंट एल्गोरिथ्म का पुनरावृत्ति मूल्यों को अधिकतम तत्व की दिशा में ले जाएगा। इसलिए अधिकतम तत्व वाले सभी खण्डों को प्रारंभ करना उपयोगी नहीं है। अधिकतम से कम मान वाले राज्य में कम से कम एक खण्ड प्रारंभ होता है। विवरण पर निर्भर करता है
डेटा-प्रवाह समस्या। यदि न्यूनतम तत्व पूरी प्रकार से रूढ़िवादी जानकारी का प्रतिनिधित्व करता है, तो परिणाम डेटा-प्रवाह पुनरावृत्ति के समय भी सुरक्षित रूप से उपयोग किए जा सकते हैं। यदि यह सबसे स्पष्ट जानकारी का प्रतिनिधित्व करता है, तो परिणामों को प्रयुक्त करने से पहले फिक्सपॉइंट तक पहुंचना चाहिए।
उदाहरण
निम्नलिखित कंप्यूटर प्रोग्राम के गुणों के उदाहरण हैं जिनकी गणना डेटा-प्रवाह विश्लेषण द्वारा की जा सकती है।
ध्यान दें कि डेटा-प्रवाह विश्लेषण द्वारा परिकलित गुण सामान्यतः वास्तविक के केवल अनुमान होते हैं
गुण। ऐसा इसलिए है क्योंकि डेटा-प्रवाह विश्लेषण बिना CFG के सिंटैक्टिकल स्ट्रक्चर पर काम करता है
कार्यक्रम के स्पष्ट नियंत्रण प्रवाह का अनुकरण करना।
चूंकि, अभ्यास में अभी भी उपयोगी होने के लिए, डेटा प्रवाह विश्लेषण एल्गोरिदम को सामान्यतः गणना करने के लिए डिज़ाइन किया गया है
वास्तविक कार्यक्रम गुणों का एक ऊपरी क्रमशः निचला सन्निकटन।
आगे का विश्लेषण
परिभाषा तक पहुँचना एनालिसिस प्रत्येक प्रोग्राम पॉइंट के लिए परिभाषाओं के समुच्चयकी गणना करता है
संभावित रूप से इस कार्यक्रम बिंदु तक पहुँच सकते हैं।
<वाक्यविन्यास हाइलाइट लैंग = टेक्स्ट लाइन हाइलाइट = 2,4,7> अगर बी == 4 तो ए = 5; अन्य ए = 3; अगर अंत अगर एक <4 तो ... </वाक्यविन्यास हाइलाइट> |
चर की पहुँच परिभाषा |
पिछड़ा विश्लेषण
प्रत्यक्ष चर विश्लेषण प्रत्येक प्रोग्राम के लिए उन चरों की गणना करता है जो हो सकते हैं संभावित रूप से उनके अगले लेखन अद्यतन से पहले पश्चातमें पढ़ें। परिणाम सामान्यतः द्वारा उपयोग किया जाता है मृत कोड उन्मूलन उन बयानों को हटाने के लिए जो एक चर को असाइन करते हैं जिसका मूल्य पश्चात में उपयोग नहीं किया जाता है।
खण्ड की इन-स्टेट चरों का समुच्चय है जो इसके प्रारंभ में प्रत्यक्ष हैं। स्थानांतरण प्रकार्य प्रयुक्त होने से पहले और वास्तविक निहित मानों की गणना करने से पहले, इसमें प्रारंभिक रूप से खण्डमें सभी चर प्रत्यक्ष (निहित) होते हैं। इस खण्डके अंदर लिखे गए चरों को मारकर स्टेटमेंट का स्थानांतरण प्रकार्य प्रयुक्त किया जाता है (उन्हें प्रत्यक्ष चरों के समुच्चय से हटा दें)। खण्ड की आउट-स्टेट चरों का समुच्चय है जो खण्ड के अंत में रहते हैं और खण्ड के उत्तराधिकारियों के इन-स्टेट्स के संघ द्वारा गणना की जाती है।
प्रारंभिक कोड:
बी 1: ए = 3; बी = 5; डी = 4; एक्स = 100; अगर ए> बी तो बी 2: सी = ए + बी; डी = 2; बी3: एंडिफ सी = 4; वापसी बी * डी + सी;
|
पिछड़ा विश्लेषण:
// में: {} बी 1: ए = 3; बी = 5; डी = 4; एक्स = 100; // x का उपयोग बाद में कभी नहीं किया जा रहा है इसलिए आउट सेट {ए, बी, डी} में नहीं अगर ए> बी तो // बाहर: {ए, बी, डी} // बी 1 => बी 2 के सभी (इन) उत्तराधिकारियों का संघ: {ए, बी}, और बी 3: {बी, डी} // में: {ए, बी} बी 2: सी = ए + बी; डी = 2; // बाहर: {बी, डी} // में: {बी, डी} बी3: एंडिफ सी = 4; वापसी बी * डी + सी; // बाहर:{}
|
b3 की इन-स्टेट में केवल b और d होते हैं, क्योंकि c लिखा गया है। बी 1 का आउट-स्टेट बी 2 और बी 3 के इन-स्टेट्स का संघ है। b2 में c की परिभाषा को हटाया जा सकता है, क्योंकि c स्टेटमेंट के तुरंत पश्चातप्रत्यक्ष नहीं होता है।
डेटा-फ्लो समीकरणों को हल करना सभी इन-स्टेट्स और आउट-स्टेट्स को खाली समुच्चयमें इनिशियलाइज़ करने से प्रारंभ होता है। कार्य सूची (बैकवर्ड फ्लो के लिए विशिष्ट) में निकास बिंदु (b3) सम्मिलित करके कार्य सूची को आरंभीकृत किया जाता है। इसकी गणना इन-स्टेट पिछले एक से भिन्न होती है, इसलिए इसके पूर्ववर्ती b1 और b2 सम्मिलित किए जाते हैं और प्रक्रिया जारी रहती है। प्रगति को नीचे दी गई तालिका में संक्षेपित किया गया है।
processing | out-state | old in-state | new in-state | work list |
---|---|---|---|---|
b3 | {} | {} | {b,d} | (b1,b2) |
b1 | {b,d} | {} | {} | (b2) |
b2 | {b,d} | {} | {a,b} | (b1) |
b1 | {a,b,d} | {} | {} | () |
ध्यान दें कि b1 को b2 से पहले सूची में अंकित किया गया था, जिसने b1 को दो बार संसाधित करने के लिए बाध्य किया (b1 को b2 के पूर्ववर्ती के रूप में फिर से अंकित किया गया था)। b1 से पहले b2 डालने से पहले पूरा हो जाता।
खाली समुच्चयके साथ आरंभ करना एक आशावादी आरंभीकरण है: सभी चर मृत के रूप में प्रारंभ होते हैं। ध्यान दें कि आउट-स्टेट्स एक पुनरावृत्ति से अगले तक सिकुड़ नहीं सकते हैं, चूंकि आउट-स्टेट इन-स्टेट से छोटा हो सकता है। यह इस तथ्य से देखा जा सकता है कि पहले पुनरावृत्ति के पश्चातराज्य के अंदर के परिवर्तन से ही बाहरी राज्य बदल सकता है। चूंकि इन-स्टेट खाली समुच्चयके रूप में प्रारंभ होता है, यह केवल आगे के पुनरावृत्तियों में बढ़ सकता है।
अन्य दृष्टिकोण
2002 में, मार्कस मोहनेन ने डेटा-फ्लो विश्लेषण की एक नई विधि का वर्णन किया जिसमें डेटा-फ्लो ग्राफ के स्पष्ट निर्माण की आवश्यकता नहीं है,[6]इसके अतिरिक्त कार्यक्रम की अमूर्त व्याख्या पर भरोसा करना और प्रोग्राम काउंटरों का एक कार्यशील समुच्चयरखना। प्रत्येक सनिबंधन शाखा में, दोनों लक्ष्य कार्य समुच्चयमें जोड़े जाते हैं। यथासंभव अधिक से अधिक निर्देशों के लिए प्रत्येक पथ का अनुसरण किया जाता है (कार्यक्रम के अंत तक या जब तक कि यह बिना किसी बदलाव के लूप हो जाता है), और फिर समुच्चयसे हटा दिया जाता है और अगले प्रोग्राम काउंटर को पुनः प्राप्त कर लिया जाता है।
नियंत्रण प्रवाह विश्लेषण और डेटा प्रवाह विश्लेषण का एक संयोजन प्रणाली की कार्यात्मकताओं को प्रयुक्त करने वाले एकजुट स्रोत कोड क्षेत्रों की पहचान करने में उपयोगी और पूरक सिद्ध हुआ है (उदाहरण के लिए, सॉफ़्टवेयर सुविधा, आवश्यकताएं या उपयोग के स्थितियों)।[7]
समस्याओं का विशेष वर्ग
डेटा प्रवाह समस्याओं के कई विशेष वर्ग हैं जिनके कुशल या सामान्य समाधान हैं।
बिट वेक्टर समस्याएं
ऊपर दिए गए उदाहरण ऐसी समस्याएँ हैं जिनमें डेटा-प्रवाह मान एक समुच्चयहै, उदा. पहुँच परिभाषाओं का समुच्चय(प्रोग्राम में परिभाषा स्थिति के लिए बिट का उपयोग करके), या प्रत्यक्ष चरों का समुच्चय। इन समुच्चयों को कुशलतापूर्वक बिट सरणी के रूप में प्रदर्शित किया जा सकता है, जिसमें प्रत्येक बिट एक विशेष तत्व की समुच्चयसदस्यता का प्रतिनिधित्व करता है। इस प्रतिनिधित्व का उपयोग करते हुए, ज्वाइन और स्थानांतरण प्रकार्यों को बिटवाइज़ लॉजिकल ऑपरेशंस के रूप में प्रयुक्त किया जा सकता है। ज्वाइन ऑपरेशन सामान्यतः संघ या चौराहा है, जिसे बिटवाइज़ लॉजिकल या और लॉजिकल एंड द्वारा प्रयुक्त किया जाता है।
प्रत्येक खण्डके लिए स्थानांतरण प्रकार्य को तथाकथित 'जीन' और 'किल' समुच्चयमें विघटित किया जा सकता है।
एक उदाहरण के रूप में, लाइव-चर विश्लेषण में, ज्वाइन ऑपरेशन यूनियन है। किल समुच्चयचरों का समुच्चयहै जो एक खण्डमें लिखे जाते हैं, जबकि जेन समुच्चय चरों का समुच्चय है जो पहले लिखे बिना पढ़े जाते हैं। डेटा प्रवाह समीकरण बन जाते हैं
तार्किक संचालन में, यह इस रूप में पढ़ता है
बाहर (बी) = 0 'फॉर' एस 'इन' सक्सेस (बी) आउट (बी) = आउट (बी) 'या' इन (एस) इन (बी) = (बाहर (बी) 'और नहीं' मारना (बी)) 'या' जीन (बी)
डेटा प्रवाह समस्याएं जिनमें डेटा-प्रवाह मानों के समुच्चयहोते हैं जिन्हें बिट वैक्टर के रूप में प्रदर्शित किया जा सकता है, उन्हें 'बिट वेक्टर समस्याएं', 'जेन-किल समस्याएं', या 'स्थानीय रूप से अलग करने योग्य समस्याएं' कहा जाता है।[8] ऐसी समस्याओं के सामान्य बहुपद-समय समाधान हैं।[9]
ऊपर बताई गई पहुंच परिभाषाओं और प्रत्यक्ष चर समस्याओं के अतिरिक्त, निम्नलिखित समस्याएं बिटवेक्टर समस्याओं के उदाहरण हैं:[9]* उपलब्ध भाव
- बहुत व्यस्त भाव
- यूज-डिफाइन चेन | यूज-डेफिनिशन चेन
आईएफडीएस समस्याएं
अंतर-प्रक्रियात्मक, परिमित, वितरणात्मक, सब समुच्चय समस्याएँ या आईएफडीएस समस्याएँ सामान्य बहुपद-समय समाधान के साथ समस्या का एक अन्य वर्ग हैं।[8][10] इन समस्याओं के समाधान संदर्भ-संवेदनशील और प्रवाह-संवेदनशील डेटा प्रवाह विश्लेषण प्रदान करते हैं।
लोकप्रिय प्रोग्रामिंग भाषाओं के लिए आईएफडीएस - आधारित डेटा प्रवाह विश्लेषण के कई कार्यान्वयन हैं, उदा। सूत में[11] और कुछ नहीं[12] जावा विश्लेषण के लिए रूपरेखा।
प्रत्येक बिटवेक्टर समस्या भी एक आईएफडीएस समस्या है, किन्तु कई महत्वपूर्ण आईएफडीएस समस्याएँ हैं जो बिटवेक्टर समस्याएँ नहीं हैं, जिनमें वास्तविक-प्रत्यक्ष चर और संभवतः-अनियंत्रित चर सम्मिलित हैं।
संवेदनशीलता
डेटा-प्रवाह विश्लेषण सामान्यतः पथ-असंवेदनशील होता है, चूंकि डेटा-प्रवाह समीकरणों को परिभाषित करना संभव है जो पथ-संवेदनशील विश्लेषण उत्पन्न करते हैं।
- एक प्रवाह-संवेदनशील विश्लेषण एक कार्यक्रम में बयानों के क्रम को ध्यान में रखता है। उदाहरण के लिए, एक प्रवाह-असंवेदनशील सूचक उपनाम विश्लेषण चर x और y को निर्धारित कर सकता है जो एक ही स्थान को संदर्भित कर सकता है, जबकि एक प्रवाह-संवेदनशील विश्लेषण कथन 20 के पश्चातनिर्धारित कर सकता है, चर x और y उसी स्थान को संदर्भित कर सकता है।
- एक पथ-संवेदनशील विश्लेषण सनिबंधन शाखा निर्देशों पर विधेय पर निर्भर विश्लेषण जानकारी के विभिन्न टुकड़ों की गणना करता है। उदाहरण के लिए, यदि किसी शाखा में कोई निबंधन है
x>0
, तो फ़ॉल-थ्रू पथ पर, विश्लेषण यह मान लेगाx<=0
और शाखा के निशाने पर यह मान लिया जाएगा कि वास्तव मेंx>0
रखती है। - एक संदर्भ-संवेदनशील विश्लेषण एक अंतरप्रक्रियात्मक विश्लेषण है जो प्रकार्य कॉल के लक्ष्य का विश्लेषण करते समय कॉलिंग संदर्भ पर विचार करता है। विशेष रूप से, संदर्भ जानकारी का उपयोग करके कोई भी वास्तविककॉल साइट पर वापस जा सकता है, जबकि उस जानकारी के बिना, विश्लेषण जानकारी को सभी संभावित कॉल साइटों पर वापस प्रचारित करना पड़ता है, संभावित रूप से नियतता खो देता है।
डेटा-प्रवाह विश्लेषणों की सूची
- परिभाषाओं तक पहुँचना
- जीवंतता विश्लेषण
- निश्चित असाइनमेंट विश्लेषण
- उपलब्ध अभिव्यक्ति
- निरंतर प्रचार
यह भी देखें
- सार व्याख्या
- नियंत्रण प्रवाह विश्लेषण
- XLT86
संदर्भ
- ↑ Kildall, Gary Arlen (May 1972). Global expression optimization during compilation (Ph.D. dissertation). Seattle, Washington, USA: University of Washington, Computer Science Group. Thesis No. 20506, Technical Report No. 72-06-02.
- ↑ Kildall, Gary Arlen (1973-10-01). "A Unified Approach to Global Program Optimization" (PDF). Proceedings of the 1st Annual ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL). POPL '73. Boston, Massachusetts, USA: 194–206. doi:10.1145/512927.512945. hdl:10945/42162. S2CID 10219496. Archived (PDF) from the original on 2017-06-29. Retrieved 2006-11-20. ([1])
- ↑ Rüthing, Oliver; Knoop, Jens; Steffen, Bernhard (2003-07-31) [1999]. "Optimization: Detecting Equalities of Variables, Combining Efficiency with Precision". In Cortesi, Agostino; Filé, Gilberto (eds.). Static Analysis: 6th International Symposium, SAS'99, Venice, Italy, September 22–24, 1999, Proceedings. Lecture Notes in Computer Science. Vol. 1694 (illustrated ed.). Springer. pp. 232–247 [233]. ISBN 9783540664598. ISSN 0302-9743.
- ↑ Huitt, Robert; Eubanks, Gordon; Rolander, Thomas "Tom" Alan; Laws, David; Michel, Howard E.; Halla, Brian; Wharton, John Harrison; Berg, Brian; Su, Weilian; Kildall, Scott; Kampe, Bill (2014-04-25). Laws, David (ed.). "Legacy of Gary Kildall: The CP/M IEEE Milestone Dedication" (PDF) (video transscription). Pacific Grove, California, USA: Computer History Museum. CHM Reference number: X7170.2014. Retrieved 2020-01-19.
[…] Eubanks: […] Gary […] was an inventor, he was inventive, he did things. His Ph.D. thesis proved that global flow analysis converges. […] This is a fundamental idea in computer science. […] I took a […] summer course once from a guy named Dhamdhere […] they talked about optimization for like a week and then they put a slide up and said, "Kildall's Method," this is the real story. […] that's something that no one ever thinks about. […]
[2][3] (33 pages) - ↑ Cooper, Keith D.; Harvey, Timothy J.; Kennedy, Ken (2004-03-26) [November 2002]. "Iterative Data-Flow Analysis, Revisited" (PDF). PLDI 2003. ACM. TR04-432. Retrieved 2017-07-01.[permanent dead link]
- ↑ Mohnen, Markus (2002). A Graph-Free Approach to Data-Flow Analysis. Lecture Notes in Computer Science. Vol. 2304. pp. 185–213. doi:10.1007/3-540-45937-5_6. ISBN 978-3-540-43369-9.
- ↑ Kuang, Hongyu; Mäder, Patrick; Hu, Hao; Ghabi, Achraf; Huang, LiGuo; Lü, Jian; Egyed, Alexander (2015-11-01). "Can method data dependencies support the assessment of traceability between requirements and source code?". Journal of Software: Evolution and Process. 27 (11): 838–866. doi:10.1002/smr.1736. ISSN 2047-7481. S2CID 39846438.
- ↑ 8.0 8.1 Reps, Thomas; Horwitz, Susan; Sagiv, Mooly (1995). "Precise interprocedural dataflow analysis via graph reachability". Proceedings of the 22nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages - POPL '95. New York, New York, USA: ACM Press: 1, 49–61. doi:10.1145/199448.199462. ISBN 0-89791692-1. S2CID 5955667.
- ↑ 9.0 9.1 Knoop, Jens; Steffen, Bernhard; Vollmer, Jürgen (1996-05-01). "Parallelism for free: efficient and optimal bitvector analyses for parallel programs". ACM Transactions on Programming Languages and Systems. 18 (3): 268–299. doi:10.1145/229542.229545. ISSN 0164-0925. S2CID 14123780.
- ↑ Naeem, Nomair A.; Lhoták, Ondřej; Rodriguez, Jonathan (2010), "Practical Extensions to the IFDS Algorithm", Compiler Construction, Lecture Notes in Computer Science, vol. 6011, Berlin / Heidelberg, Germany: Springer Verlag, pp. 124–144, doi:10.1007/978-3-642-11970-5_8, ISBN 978-3-64211969-9
- ↑ Bodden, Eric (2012). "Inter-procedural data-flow analysis with IFDS/IDE and Soot". Proceedings of the ACM SIGPLAN International Workshop on State of the Art in Java Program Analysis - SOAP '12. New York, New York, USA: ACM Press: 3–8. doi:10.1145/2259051.2259052. ISBN 978-1-45031490-9. S2CID 3020481.
- ↑ Rapoport, Marianna; Lhoták, Ondřej; Tip, Frank (2015). Precise Data Flow Analysis in the Presence of Correlated Method Calls. International Static Analysis Symposium. Lecture Notes in Computer Science. Vol. 9291. Berlin / Heidelberg, Germany: Springer Verlag. pp. 54–71. doi:10.1007/978-3-662-48288-9_4. ISBN 978-3-66248287-2.
अग्रिम पठन
- Cooper, Keith D.; Torczon, Linda (2003) [2002-01-01]. Engineering a Compiler. Morgan Kaufmann. ISBN 978-1-55860-698-2.
- Muchnick, Steven Stanley (1997). Advanced Compiler Design and Implementation. Morgan Kaufmann Publishers. ISBN 978-1-55860-320-2.
- Hecht, Matthew S. (1977-05-03). Flow Analysis of Computer Programs. Programming Languages Series. Vol. 5. Elsevier North-Holland Inc. ISBN 978-0-44400210-5.
- Khedker, Uday P.; Sanyal, Amitabha; Karkare, Bageshri (2009). Data Flow Analysis: Theory and Practice. CRC Press (Taylor and Francis Group).
- Nielson, Flemming; Nielson, Hanne Riis; Hankin, Chris (2005). Principles of Program Analysis. Springer Science+Business Media.