डेटा प्रवाह विश्लेषण: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
 
(11 intermediate revisions by 3 users not shown)
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" />
कार्यक्रमों का आंकड़ा-प्रवाह विश्लेषण करने की आसान विधि नियंत्रण प्रवाह ग्राफ के प्रत्येक [[नोड (कंप्यूटर विज्ञान)|नोड]] के लिए आंकड़ा प्रवाह समीकरण स्थापित करना है और प्रत्येक नोड पर स्थानीय रूप से इनपुट से आउटपुट की बार-बार गणना करके उन्हें हल करना है। प्रणाली स्थिर हो जाती है, अर्थात यह निश्चित बिंदु पर पहुंच जाती है। यह सामान्य दृष्टिकोण, जिसे किल्डाल की विधि भी कहा जाता है, इसे [[गैरी किल्डाल]] द्वारा [[नौसेना स्नातकोत्तर स्कूल]] में पढ़ाने के समय विकसित किया गया था।<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}}


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


प्रत्येक ब्लॉक बी के लिए:
प्रत्येक खण्ड b के लिए:


: <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>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>.
इस में, <math> trans_b </math> खण्ड <math>b</math> का स्थानांतरण प्र कार्य है। यह प्रवेश अवस्था <math>in_b</math> पर काम करता है, तथा निकास अवस्था <math>out_b</math> प्रदान करता है। [[शामिल हों (गणित)|जोड़ संचालन(ज्वाइन ऑपरेशन) <math>join</math>]] <math>b</math> के पूर्ववर्तियों <math>p \in pred_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, जो नियत बिंदु है।
अवस्थाओं के मूल्य डोमेन के संयोजन, स्थानांतरण कार्यों और सम्मिलित होने के संचालन पर बाधाओं को प्रयुक्त करके इसकी गारंटी दी जा सकती है ।
 
मूल्य डोमेन सीमित ऊंचाई के साथ आंशिक क्रम होना चाहिए (अर्थात, कोई अनंत आरोही श्रृंखला नहीं है <math>x_1</math> < <math>x_2</math> <...). इस आंशिक क्रम के संबंध में स्थानांतरण प्रकार्य और जोड़ संचालन का संयोजन [[मोनोटोनिक|एकर -संबंधी(मोनोटोनिक)]] होना चाहिए। मोनोटोनिकिटी(दिष्टता) यह सुनिश्चित करती है कि प्रत्येक पुनरावृत्ति पर मान या तो समान रहेगा या बड़ा होगा, यद्यपि परिमित ऊंचाई सुनिश्चित करती है कि यह अनिश्चित काल तक नहीं बढ़ सकता है। इस प्रकार हम अंतत: एक ऐसी अवस्था पर पहुंच जाएंगे जहां सभी x के लिए T(x) = x, जो नियत बिंदु है।


=== कार्य सूची दृष्टिकोण ===
=== कार्य सूची दृष्टिकोण ===
ऊपर दिए गए एल्गोरिथम में सुधार करना आसान है, यह देखते हुए कि ब्लॉक की इन-स्टेट स्थिति नहीं बदलेगी यदि इसके पूर्ववर्तियों के बाहरी राज्य नहीं बदलते हैं। इसलिए, हम एक कार्य सूची प्रस्तुत करते हैं: उन ब्लॉकों की सूची जिन्हें अभी भी संसाधित करने की आवश्यकता है। जब भी किसी ब्लॉक की बाहरी स्थिति बदलती है, हम उसके उत्तराधिकारियों को कार्य सूची में जोड़ देते हैं। प्रत्येक पुनरावृत्ति में, कार्य सूची से एक ब्लॉक हटा दिया जाता है। इसकी आउट-स्टेट गणना की जाती है। यदि बाहरी राज्य बदल गया है, तो ब्लॉक के उत्तराधिकारी कार्य सूची में जुड़ जाते हैं। दक्षता के लिए, कार्य सूची में एक ब्लॉक एक से अधिक बार नहीं होना चाहिए।
ऊपर दिए गए कलन विधि में सुधार करना आसान है, यह देखते हुए कि खण्ड की आंतरिक-अवस्था अवस्था नहीं बदलेगी यदि इसके पूर्ववर्तियों की बाहरी अवस्था नहीं बदलते हैं। इसलिए, हम एक कार्य सूची प्रस्तुत करते हैं: उन [[बुनियादी ब्लॉक|खण्डों]] की सूची जिन्हें अभी भी संसाधित करने की आवश्यकता है। जब भी किसी खण्ड की बाहरी अवस्था बदलती है, हम उसके पुनरावृत्तियों को कार्य सूची में जोड़ देते हैं। प्रत्येक पुनरावृत्ति में, कार्य सूची से एक खण्ड हटा दिया जाता है। इसकी बाह्य-अवस्था(आउट-स्टेट) गणना की जाती है। यदि बाहरी अवस्था बदल गयी है, तो खण्ड के पूर्ववर्ती कार्य सूची में जुड़ जाते हैं। दक्षता के लिए, कार्य सूची में एक खण्ड एक से अधिक बार नहीं होना चाहिए।


एल्गोरिदम को कार्य सूची में सूचना-सृजन करने वाले ब्लॉक डालकर शुरू किया जाता है। यह समाप्त हो जाता है जब
कलन विधि को कार्य सूची में सूचना-सृजन करने वाले खण्ड डालकर प्रारंभ किया जाता है। यह समाप्त हो जाता है जब कार्य सूची खाली होती है।
कार्य सूची खाली है।


=== आदेश देना ===
=== आदेश '''देना''' ===
डेटा-फ्लो समीकरणों को क्रमिक रूप से हल करने की दक्षता उस क्रम से प्रभावित होती है जिस पर स्थानीय नोड्स का दौरा किया जाता है।<ref name="Cooper_2004"/>इसके अलावा, यह इस बात पर निर्भर करता है कि सीएफजी पर आगे या पीछे डेटा प्रवाह विश्लेषण के लिए डेटा प्रवाह समीकरणों का उपयोग किया जाता है या नहीं। सहजता से, आगे प्रवाह की समस्या में, यह सबसे तेज़ होगा यदि ब्लॉक के सभी पूर्ववर्तियों को ब्लॉक से पहले संसाधित किया गया हो, तब से पुनरावृति नवीनतम जानकारी का उपयोग करेगी। लूप के अभाव में ब्लॉक को इस तरह से ऑर्डर करना संभव है कि प्रत्येक ब्लॉक को केवल एक बार संसाधित करके सही आउट-स्टेट्स की गणना की जाती है।
आंकड़ा-प्रवाह समीकरणों को क्रमिक रूप से हल करने की दक्षता उस क्रम से प्रभावित होती है जिस पर स्थानीय नोड्स का भ्रमण किया जाता है।<ref name="Cooper_2004"/> इसके अतिरिक्त, यह इस बात पर निर्भर करता है कि सीएफजी पर आगे या पीछे आंकड़ा प्रवाह विश्लेषण के लिए आंकड़ा प्रवाह समीकरणों का उपयोग किया जाता है या नहीं किया जाता है। सहजता से, अग्रगामी प्रवाह की समस्या में, यह सबसे तेज़ होगा यदि खण्ड के सभी पूर्ववर्तियों को खण्ड से पहले संसाधित किया गया हो, तब से पुनरावृति नवीनतम जानकारी का उपयोग करेगी। लूप के अभाव में खण्ड को इस प्रकार से ऑर्डर करना संभव है कि प्रत्येक खण्ड को मात्र एक बार संसाधित करके सही बाह्य-अवस्थाओं की गणना की जाती है।


निम्नलिखित में, डेटा-प्रवाह समीकरणों को हल करने के लिए कुछ पुनरावृति क्रमों पर चर्चा की गई है
निम्नलिखित में, आंकड़ा-प्रवाह समीकरणों को हल करने के लिए कुछ पुनरावृति क्रमों पर चर्चा की गई है(एक नियंत्रण-प्रवाह ग्राफ के पुनरावृति क्रम से संबंधित अवधारणा a [[ट्री ट्रैवर्सल|वृक्ष]] का [[ट्री ट्रैवर्सल]] है)।
(एक नियंत्रण-प्रवाह ग्राफ के पुनरावृति क्रम से संबंधित अवधारणा a का [[ट्री ट्रैवर्सल]] है
[[वृक्ष (ग्राफ सिद्धांत)]])।


* यादृच्छिक क्रम - यह पुनरावृत्ति क्रम इस बात से अवगत नहीं है कि डेटा-प्रवाह समीकरण आगे या पीछे की डेटा-प्रवाह समस्या को हल करते हैं या नहीं। इसलिए, विशिष्ट पुनरावृति आदेशों की तुलना में प्रदर्शन अपेक्षाकृत खराब है।
* यादृच्छिक क्रम - यह पुनरावृत्ति क्रम इस बात से अवगत नहीं है कि आंकड़ा-प्रवाह समीकरण आगे या पीछे की आंकड़ा-प्रवाह समस्या को हल करते हैं या नहीं करते हैं। इसलिए, विशिष्ट पुनरावृति आदेशों की तुलना में प्रदर्शन अपेक्षाकृत खराब है।
* [[मेल आदेश]] - यह बैकवर्ड डेटा-फ्लो समस्याओं के लिए एक विशिष्ट पुनरावृत्ति क्रम है। 'पोस्टऑर्डर इटरेशन' में, एक नोड का दौरा उसके सभी उत्तराधिकारी नोड्स का दौरा करने के बाद किया जाता है। विशिष्ट रूप से, ''पोस्टऑर्डर पुनरावृत्ति'' को गहराई-प्रथम रणनीति के साथ कार्यान्वित किया जाता है।
* [[मेल आदेश]] - यह पश्चगामी आंकड़ा-प्रवाह समस्याओं के लिए एक विशिष्ट पुनरावृत्ति क्रम है। 'पश्चक्रम पुनरावृति' में, एक नोड का भ्रमण उसके सभी पूर्ववर्ती नोड्स का भ्रमण करने के पश्चात किया जाता है। विशिष्ट रूप से, पश्चक्रम पुनरावृत्ति को गहराई-प्रथम रणनीति के साथ कार्यान्वित किया जाता है।
* डेप्थ-फर्स्ट सर्च # वर्टेक्स ऑर्डरिंग - यह फॉरवर्ड डेटा-फ्लो समस्याओं के लिए एक विशिष्ट पुनरावृत्ति क्रम है। रिवर्स-पोस्टऑर्डर पुनरावृति में, इसके किसी भी उत्तराधिकारी नोड का दौरा करने से पहले एक नोड का दौरा किया जाता है, सिवाय इसके कि जब उत्तराधिकारी पीछे के किनारे तक पहुंच जाता है। (ध्यान दें कि रिवर्स पोस्टऑर्डर डेप्थ-फर्स्ट सर्च#वर्टेक्स ऑर्डरिंग के समान नहीं है।)
* डेप्थ-फर्स्ट सर्च अथवा वर्टेक्स ऑर्डरिंग - यह अग्रगामी आंकड़ा-प्रवाह समस्याओं के लिए एक विशिष्ट पुनरावृत्ति क्रम है। रिवर्स-पोस्टऑर्डर पुनरावृति में, इसके किसी भी पूर्ववर्ती नोड का भ्रमण करने से पहले एक नोड का भ्रमण किया जाता है, अतिरिक्त इसके कि जब पूर्ववर्ती पीछे के किनारे तक पहुंच जाता है। (ध्यान दें कि रिवर्स पोस्टऑर्डर डेप्थ-फर्स्ट सर्च अथवा वर्टेक्स ऑर्डरिंग के समान नहीं है।)


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


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


=== आगे का विश्लेषण ===
=== आगे का विश्लेषण ===
[[परिभाषा तक पहुँचना]] एनालिसिस प्रत्येक प्रोग्राम पॉइंट के लिए परिभाषाओं के सेट की गणना करता है
[[परिभाषा तक पहुँचना]] एनालिसिस प्रत्येक कार्यक्रम पॉइंट के लिए परिभाषाओं के समुच्चयकी गणना करता है
 
संभावित रूप से इस कार्यक्रम बिंदु तक पहुँच सकते हैं।
संभावित रूप से इस कार्यक्रम बिंदु तक पहुँच सकते हैं।


{{col-begin|width=auto}}
लाइन 7 पर चर a की पहुंच परिभाषा कार्यभारों(असाइनमेंट्स) का समुच्चय a = 5 लाइन 2 पर और a = 3 लाइन 4 पर  है ।<syntaxhighlight>
{{col-break|width=200px}}
if b == 4 then
<वाक्यविन्यास हाइलाइट लैंग = टेक्स्ट लाइन हाइलाइट = 2,4,7>
     a = 5;
  अगर बी == 4 तो
   else
     = 5;
     a = 3;
   अन्य
   endif
     = 3;
   अगर अंत
   
   
   अगर एक <4 तो
   if a < 4 then
     ...
     ...
</वाक्यविन्यास हाइलाइट>
</syntaxhighlight>
{{col-break|gap=2em}}
 
चर की पहुँच परिभाषा {{code|a}} पंक्ति 7 पर असाइनमेंट का सेट है {{code|1=a = 5}} लाइन 2 पर और {{code|1=a = 3}} लाइन 4 पर।
{{col-end}}
=== पिछड़ा विश्लेषण ===
=== पिछड़ा विश्लेषण ===
लाइव वेरिएबल विश्लेषण प्रत्येक प्रोग्राम के लिए उन चरों की गणना करता है जो हो सकते हैं
प्रत्यक्ष चर विश्लेषण प्रत्येक कार्यक्रम के लिए उन चरों की गणना करता है जो हो सकते हैं , संभावित रूप से उनके अगले लेखन अद्यतन से पहले पश्चात में पढ़ें। परिणाम सामान्यतः द्वारा उपयोग किया जाता है।
संभावित रूप से उनके अगले लेखन अद्यतन से पहले बाद में पढ़ें। परिणाम आमतौर पर द्वारा उपयोग किया जाता है
 
[[मृत कोड उन्मूलन]] उन बयानों को हटाने के लिए जो एक चर को असाइन करते हैं जिसका मूल्य बाद में उपयोग नहीं किया जाता है।
[[मृत कोड उन्मूलन]] उन वर्णनों को हटाने के लिए जो एक चर को निर्दिष्ट करते हैं जिसका मूल्य पश्चात में उपयोग नहीं किया जाता है।


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


प्रारंभिक कोड:
प्रारंभिक कोड:<syntaxhighlight>
Initial code:


{{col-begin|width=auto}}
b1: a = 3;  
{{col-break}}
    b = 5;
बी 1: = 3;
    d = 4;
    बी = 5;
    x = 100;
    डी = 4;
    if a > b then
    एक्स = 100;
b2:   c = a + b;
    अगर ए> बी तो
      d = 2;
बी 2: सी = + बी;
b3: endif
        डी = 2;
    c = 4;
बी3: एंडिफ
    return b * d + c;
    सी = 4;
</syntaxhighlight>पिछड़ा विश्लेषण:<syntaxhighlight>
    वापसी बी * डी + सी;
// in: {}
{{col-end}}
b1: a = 3;
पिछड़ा विश्लेषण:
    b = 5;
    d = 4;
    x = 100; //x is never being used later thus not in the out set {a,b,d}
    if a > b then
// out: {a,b,d}   //union of all (in) successors of b1 => b2: {a,b}, and b3:{b,d} 


{{col-begin|width=auto}}
// in: {a,b}
{{col-break}}
b2: c = a + b;
// में: {}
    d = 2;
बी 1: ए = 3;
// out: {b,d}
    बी = 5;
 
    डी = 4;
// in: {b,d}
    एक्स = 100; // x का उपयोग बाद में कभी नहीं किया जा रहा है इसलिए आउट सेट {ए, बी, डी} में नहीं
b3: endif
    अगर ए> बी तो
    c = 4;
// बाहर: {ए, बी, डी} // बी 1 => बी 2 के सभी (इन) उत्तराधिकारियों का संघ: {ए, बी}, और बी 3: {बी, डी}
    return b * d + c;
// out:{}
// में: {ए, बी}
</syntaxhighlight>b3 की आंतरिक-अवस्था में मात्र b और d होते हैं, क्योंकि c लिखा गया है। b1 का बाह्य-अवस्था b2 और b3 के आंतरिक-अवस्थाओं का संघ है। b2 में c की परिभाषा को हटाया जा सकता है, क्योंकि c कथन के तुरंत पश्चात प्रत्यक्ष नहीं होता है।
बी 2: सी = ए + बी;
    डी = 2;
// बाहर: {बी, डी}
// में: {बी, डी}
बी3: एंडिफ
    सी = 4;
    वापसी बी * डी + सी;
// बाहर:{}
{{col-end}}
b3 की इन-स्टेट में केवल b और d होते हैं, क्योंकि c लिखा गया है। बी 1 का आउट-स्टेट बी 2 और बी 3 के इन-स्टेट्स का संघ है। b2 में c की परिभाषा को हटाया जा सकता है, क्योंकि c स्टेटमेंट के तुरंत बाद लाइव नहीं होता है।


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


{| class="wikitable"
{| class="wikitable"
|-
|-
! processing
! प्रसंस्करण
! out-state
! बाह्य-अवस्था
! old in-state
! पूर्व आंतरिक-अवस्था
! new in-state
! नवीन आंतरिक-अवस्था
! work list
! कार्य सूची
|-
|-
| b3
| b3
Line 168: Line 161:
| ()
| ()
|}
|}
ध्यान दें कि b1 को b2 से पहले सूची में दर्ज किया गया था, जिसने b1 को दो बार संसाधित करने के लिए मजबूर किया (b1 को b2 के पूर्ववर्ती के रूप में फिर से दर्ज किया गया था)। b1 से पहले b2 डालने से पहले पूरा हो जाता।
ध्यान दें कि b1 को b2 से पहले सूची में अंकित किया गया था, जिसने b1 को दो बार संसाधित करने के लिए बाध्य किया (b1 को b2 के पूर्ववर्ती के रूप में फिर से अंकित किया गया था)। b1 से पहले b2 डालने से पहले पूरा हो जाता।


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


== अन्य दृष्टिकोण ==
== अन्य दृष्टिकोण ==
2002 में, मार्कस मोहनेन ने डेटा-फ्लो विश्लेषण की एक नई विधि का वर्णन किया जिसमें डेटा-फ्लो ग्राफ के स्पष्ट निर्माण की आवश्यकता नहीं है,<ref name="Mohnen_2002"/>इसके बजाय कार्यक्रम की अमूर्त व्याख्या पर भरोसा करना और प्रोग्राम काउंटरों का एक कार्यशील सेट रखना। प्रत्येक सशर्त शाखा में, दोनों लक्ष्य कार्य सेट में जोड़े जाते हैं। यथासंभव अधिक से अधिक निर्देशों के लिए प्रत्येक पथ का अनुसरण किया जाता है (कार्यक्रम के अंत तक या जब तक कि यह बिना किसी बदलाव के लूप हो जाता है), और फिर सेट से हटा दिया जाता है और अगले प्रोग्राम काउंटर को पुनः प्राप्त कर लिया जाता है।
2002 में, मार्कस मोहनेन ने आंकड़ा-प्रवाह विश्लेषण की एक नई विधि का वर्णन किया जिसमें आंकड़ा-प्रवाह ग्राफ के स्पष्ट निर्माण की आवश्यकता नहीं है,<ref name="Mohnen_2002"/> इसके अतिरिक्त कार्यक्रम की अमूर्त व्याख्या पर निर्भर करता है और प्रोग्राम विरोधों का एक कार्यशील समुच्चय रखता है। प्रत्येक सनिबंधन शाखा में, दोनों लक्ष्य कार्य समुच्चय में जोड़े जाते हैं। यथासंभव अधिक से अधिक निर्देशों के लिए प्रत्येक पथ का अनुसरण किया जाता है (कार्यक्रम के अंत तक या जब तक कि यह बिना किसी बदलाव के लूप हो जाता है), और फिर समुच्चय से हटा दिया जाता है और अगले कार्यक्रम विरोध को पुनः प्राप्त कर लिया जाता है।


[[नियंत्रण प्रवाह विश्लेषण]] और डेटा प्रवाह विश्लेषण का एक संयोजन सिस्टम की कार्यात्मकताओं को लागू करने वाले एकजुट स्रोत कोड क्षेत्रों की पहचान करने में उपयोगी और पूरक साबित हुआ है ([[उदाहरण]] के लिए, सॉफ़्टवेयर सुविधा, आवश्यकताएं या उपयोग के मामले)।<ref name="Kuang_2015"/>
[[नियंत्रण प्रवाह विश्लेषण]] और आंकड़ा प्रवाह विश्लेषण का एक संयोजन प्रणाली की कार्यात्मकताओं को प्रयुक्त करने वाले एकजुट स्रोत कोड क्षेत्रों की पहचान करने में उपयोगी और पूरक सिद्ध हुआ है ([[उदाहरण]] के लिए, सॉफ़्टवेयर सुविधा, आवश्यकताएं या उपयोग के अवस्थायों)।<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>
:<math> in_b = (out_b - kill_b) \cup gen_b </math>
:<math> in_b = (out_b - kill_b) \cup gen_b </math>
तार्किक संचालन में, यह इस रूप में पढ़ता है
तार्किक संचालन में, यह इस रूप में पढ़ता है,<syntaxhighlight>
out(b) = 0
for s in succ(b)
    out(b) = out(b) or in(s)
in(b) = (out(b) and not kill(b)) or gen(b)
</syntaxhighlight>आंकड़ा प्रवाह समस्याएं जिनमें आंकड़ा-प्रवाह मानों के समुच्चय होते हैं जिन्हें बिट वैक्टर के रूप में प्रदर्शित किया जा सकता है, उन्हें 'बिट वेक्टर समस्याएं', 'जेन-किल समस्याएं', या 'स्थानीय रूप से भिन्न करने योग्य समस्याएं' कहा जाता है।<ref name="Reps_1995"/> ऐसी समस्याओं के सामान्य बहुपद-समय समाधान हैं।<ref name="Knoop_1996"/>


बाहर (बी) = 0
ऊपर बताई गई पहुंच परिभाषाओं और प्रत्यक्ष चर समस्याओं के अतिरिक्त, निम्नलिखित समस्याएं बिटवेक्टर समस्याओं के उदाहरण हैं:<ref name="Knoop_1996"/>
'फॉर' एस 'इन' सक्सेस (बी)
* उपलब्ध भाव
    आउट (बी) = आउट (बी) 'या' इन (एस)
*बहुत व्यस्त भाव
इन (बी) = (बाहर (बी) 'और नहीं' मारना (बी)) 'या' जीन (बी)
* यूज-डिफाइन चेन (उपयोग-परिभाषा श्रृंखला)
 
डेटा प्रवाह समस्याएं जिनमें डेटा-प्रवाह मानों के सेट होते हैं जिन्हें बिट वैक्टर के रूप में प्रदर्शित किया जा सकता है, उन्हें 'बिट वेक्टर समस्याएं', 'जेन-किल समस्याएं', या 'स्थानीय रूप से अलग करने योग्य समस्याएं' कहा जाता है।<ref name="Reps_1995"/>ऐसी समस्याओं के सामान्य बहुपद-समय समाधान हैं।<ref name="Knoop_1996"/>
 
ऊपर बताई गई पहुंच परिभाषाओं और लाइव चर समस्याओं के अलावा, निम्नलिखित समस्याएं बिटवेक्टर समस्याओं के उदाहरण हैं:<ref name="Knoop_1996"/>* उपलब्ध भाव
* बहुत व्यस्त भाव
* यूज-डिफाइन चेन | यूज-डेफिनिशन चेन


=== आईएफडीएस समस्याएं ===
=== आईएफडीएस समस्याएं ===
अंतर-प्रक्रियात्मक, परिमित, वितरणात्मक, सबसेट समस्याएँ या IFDS समस्याएँ सामान्य बहुपद-समय समाधान के साथ समस्या का एक अन्य वर्ग हैं।<ref name="Reps_1995"/><ref name="Naeem_2010"/>इन समस्याओं के समाधान संदर्भ-संवेदनशील और प्रवाह-संवेदनशील डेटा प्रवाह विश्लेषण प्रदान करते हैं।
अंतर-प्रक्रियात्मक, परिमित, वितरणात्मक, सब समुच्चय समस्याएँ या आईएफडीएस समस्याएँ सामान्य बहुपद-समय समाधान के साथ समस्या का एक अन्य वर्ग हैं।<ref name="Reps_1995"/><ref name="Naeem_2010"/> इन समस्याओं के समाधान संदर्भ-संवेदनशील और प्रवाह-संवेदनशील आंकड़ा प्रवाह विश्लेषण प्रदान करते हैं।


लोकप्रिय प्रोग्रामिंग भाषाओं के लिए IFDS- आधारित डेटा प्रवाह विश्लेषण के कई कार्यान्वयन हैं, उदा। सूत में<ref name="Bodden_2012"/>और कुछ नहीं<ref name="Rapoport_2015"/>जावा विश्लेषण के लिए रूपरेखा।
लोकप्रिय कार्यक्रमिंग भाषाओं के लिए आईएफडीएस - आधारित आंकड़ा प्रवाह विश्लेषण के कई कार्यान्वयन हैं, उदा। सूत में<ref name="Bodden_2012"/> और कुछ नहीं<ref name="Rapoport_2015"/> जावा विश्लेषण के लिए रूपरेखा।


प्रत्येक बिटवेक्टर समस्या भी एक IFDS समस्या है, लेकिन कई महत्वपूर्ण IFDS समस्याएँ हैं जो बिटवेक्टर समस्याएँ नहीं हैं, जिनमें वास्तविक-लाइव चर और संभवतः-अनियंत्रित चर शामिल हैं।
प्रत्येक बिटवेक्टर समस्या भी एक आईएफडीएस समस्या है, किन्तु कई महत्वपूर्ण आईएफडीएस समस्याएँ हैं जो बिटवेक्टर समस्याएँ नहीं हैं, जिनमें वास्तविक-प्रत्यक्ष चर और संभवतः-अनियंत्रित चर सम्मिलित हैं।


== संवेदनशीलता ==
== संवेदनशीलता ==
डेटा-प्रवाह विश्लेषण आमतौर पर पथ-असंवेदनशील होता है, हालांकि डेटा-प्रवाह समीकरणों को परिभाषित करना संभव है जो पथ-संवेदनशील विश्लेषण उत्पन्न करते हैं।
आंकड़ा-प्रवाह विश्लेषण सामान्यतः पथ-असंवेदनशील होता है, चूंकि आंकड़ा-प्रवाह समीकरणों को परिभाषित करना संभव है जो पथ-संवेदनशील विश्लेषण उत्पन्न करते हैं।


* एक प्रवाह-संवेदनशील विश्लेषण एक कार्यक्रम में बयानों के क्रम को ध्यान में रखता है। उदाहरण के लिए, एक प्रवाह-असंवेदनशील सूचक उपनाम विश्लेषण चर ''x'' और ''y'' को निर्धारित कर सकता है जो एक ही स्थान को संदर्भित कर सकता है, जबकि एक प्रवाह-संवेदनशील विश्लेषण कथन 20 के बाद निर्धारित कर सकता है, चर ''x'' और ''y'' उसी स्थान को संदर्भित कर सकता है।
* एक प्रवाह-संवेदनशील विश्लेषण एक कार्यक्रम में वर्णनों के क्रम को ध्यान में रखता है। उदाहरण के लिए, एक प्रवाह-असंवेदनशील सूचक उपनाम विश्लेषण चर ''x'' और ''y'' को निर्धारित कर सकता है जो एक ही स्थान को संदर्भित कर सकता है, यद्यपि एक प्रवाह-संवेदनशील विश्लेषण कथन 20 के पश्चातनिर्धारित कर सकता है, चर ''x'' और ''y'' उसी स्थान को संदर्भित कर सकता है।
* एक पथ-संवेदनशील विश्लेषण सशर्त शाखा निर्देशों पर विधेय पर निर्भर विश्लेषण जानकारी के विभिन्न टुकड़ों की गणना करता है। उदाहरण के लिए, यदि किसी शाखा में कोई शर्त है {{code|x>0}}, तो फ़ॉल-थ्रू पथ पर, विश्लेषण यह मान लेगा {{code|1=x<=0}} और शाखा के निशाने पर यह मान लिया जाएगा कि वास्तव में {{code|x>0}} रखती है।
* एक पथ-संवेदनशील विश्लेषण सनिबंधन शाखा निर्देशों पर विधेय पर निर्भर विश्लेषण जानकारी के विभिन्न टुकड़ों की गणना करता है। उदाहरण के लिए, यदि किसी शाखा में कोई निबंधन है {{code|x>0}}, तो फ़ॉल-थ्रू पथ पर, विश्लेषण यह मान लेगा {{code|1=x<=0}} और शाखा के निशाने पर यह मान लिया जाएगा कि वास्तव में {{code|x>0}} रखती है।
* एक संदर्भ-संवेदनशील विश्लेषण एक ''अंतरप्रक्रियात्मक'' विश्लेषण है जो फ़ंक्शन कॉल के लक्ष्य का विश्लेषण करते समय कॉलिंग संदर्भ पर विचार करता है। विशेष रूप से, संदर्भ जानकारी का उपयोग करके कोई भी मूल कॉल साइट पर वापस जा सकता है, जबकि उस जानकारी के बिना, विश्लेषण जानकारी को सभी संभावित कॉल साइटों पर वापस प्रचारित करना पड़ता है, संभावित रूप से सटीकता खो देता है।
* एक संदर्भ-संवेदनशील विश्लेषण एक ''अंतरप्रक्रियात्मक'' विश्लेषण है जो प्रकार्य कॉल के लक्ष्य का विश्लेषण करते समय कॉलिंग संदर्भ पर विचार करता है। विशेष रूप से, संदर्भ जानकारी का उपयोग करके कोई भी वास्तविककॉल साइट पर वापस जा सकता है, यद्यपि उस जानकारी के बिना, विश्लेषण जानकारी को सभी संभावित कॉल साइटों पर वापस प्रचारित करना पड़ता है, संभावित रूप से नियतता खो देता है।


== डेटा-प्रवाह विश्लेषणों की सूची ==
== आंकड़ा-प्रवाह विश्लेषणों की सूची ==
* परिभाषाओं तक पहुँचना
* परिभाषाओं तक पहुँचना
* [[जीवंतता विश्लेषण]]
* [[जीवंतता विश्लेषण]]
Line 250: Line 243:


{{Compiler optimizations}}
{{Compiler optimizations}}
[[Category: डेटा प्रवाह विश्लेषण | डेटा प्रवाह विश्लेषण ]] [[Category: संकलक अनुकूलन]]


[[Category: Machine Translated Page]]
[[Category:All articles with dead external links]]
[[Category:Articles with dead external links from July 2019]]
[[Category:Articles with permanently dead external links]]
[[Category:Collapse templates]]
[[Category:Created On 18/02/2023]]
[[Category:Created On 18/02/2023]]
[[Category:Lua-based templates]]
[[Category:Machine Translated Page]]
[[Category:Navigational boxes| ]]
[[Category:Navigational boxes without horizontal lists]]
[[Category:Pages with script errors]]
[[Category:Pages with syntax highlighting errors]]
[[Category:Short description with empty Wikidata description]]
[[Category:Sidebars with styles needing conversion]]
[[Category:Template documentation pages|Documentation/doc]]
[[Category:Templates Translated in Hindi]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates generating microformats]]
[[Category:Templates that add a tracking category]]
[[Category:Templates that are not mobile friendly]]
[[Category:Templates that generate short descriptions]]
[[Category:Templates using TemplateData]]
[[Category:Wikipedia metatemplates]]
[[Category:डेटा प्रवाह विश्लेषण| डेटा प्रवाह विश्लेषण ]]
[[Category:संकलक अनुकूलन]]

Latest revision as of 16:56, 3 March 2023

आंकड़ा-प्रवाह विश्लेषण(डेटा-फ्लो एनालिसिस) कंप्यूटर कार्यक्रम में विभिन्न बिंदुओं पर गणना किए गए मानों के संभावित समुच्चय के विषय में जानकारी एकत्र करने की विधि है। कार्यक्रम(प्रोग्राम) के नियंत्रण-प्रवाह ग्राफ (सीएफजी) का उपयोग कार्यक्रम के उन भागों को निर्धारित करने के लिए किया जाता है, जिनके लिए चर को निर्दिष्ट विशेष मान प्रचारित हो सकता है। एकत्र की गई जानकारी का उपयोग प्रायः संकलक द्वारा कार्यक्रम को अनुकूलित करते समय किया जाता है। आंकड़ा-प्रवाह विश्लेषण का प्रामाणिक उदाहरण परिभाषाओं तक पहुँच रहा है।

कार्यक्रमों का आंकड़ा-प्रवाह विश्लेषण करने की आसान विधि नियंत्रण प्रवाह ग्राफ के प्रत्येक नोड के लिए आंकड़ा प्रवाह समीकरण स्थापित करना है और प्रत्येक नोड पर स्थानीय रूप से इनपुट से आउटपुट की बार-बार गणना करके उन्हें हल करना है। प्रणाली स्थिर हो जाती है, अर्थात यह निश्चित बिंदु पर पहुंच जाती है। यह सामान्य दृष्टिकोण, जिसे किल्डाल की विधि भी कहा जाता है, इसे गैरी किल्डाल द्वारा नौसेना स्नातकोत्तर स्कूल में पढ़ाने के समय विकसित किया गया था।[1][2][3][4]

मूलरूप सिद्धांत

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

प्रत्येक खण्ड b के लिए:

इस में, खण्ड का स्थानांतरण प्र कार्य है। यह प्रवेश अवस्था पर काम करता है, तथा निकास अवस्था प्रदान करता है। जोड़ संचालन(ज्वाइन ऑपरेशन) के पूर्ववर्तियों के निकास अवस्थाओं को जोड़ती है , जो की प्रवेश अवस्था प्रदान करता है।

समीकरणों के इस समुच्चय को हल करने के पश्चात, खण्ड सीमाओं पर कार्यक्रम के गुणों को प्राप्त करने के लिए खण्ड के प्रवेश अथवा निकास अवस्थाओं का उपयोग किया जा सकता है। मूलभूत खण्ड के अंदर बिंदु पर जानकारी प्राप्त करने के लिए भिन्न-भिन्न प्रत्येक वर्णन के हस्तांतरण प्रकार्य को अलग से प्रयुक्त किया जा सकता है।

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

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

एक पुनरावृत्त कलन विधि

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

आंकड़ा-प्रवाह समीकरणों को हल करने के लिए एक मूलभूत कलन विधि राउंड-रॉबिन पुनरावृत्ति कलन विधि है:

i के लिए ← 1 से N
नोड i प्रारंभ करें
यद्यपि (समुच्चय अभी भी बदल रहे हैं)
i के लिए ← 1 से N
नोड i पर पुनर्गणना समुच्चय करता है

अभिसरण

प्रयोग करने योग्य होने के लिए, पुनरावृत्त दृष्टिकोण वास्तव में एक निश्चित बिंदु तक पहुंचना चाहिए।

अवस्थाओं के मूल्य डोमेन के संयोजन, स्थानांतरण कार्यों और सम्मिलित होने के संचालन पर बाधाओं को प्रयुक्त करके इसकी गारंटी दी जा सकती है ।

मूल्य डोमेन सीमित ऊंचाई के साथ आंशिक क्रम होना चाहिए (अर्थात, कोई अनंत आरोही श्रृंखला नहीं है < <...). इस आंशिक क्रम के संबंध में स्थानांतरण प्रकार्य और जोड़ संचालन का संयोजन एकर -संबंधी(मोनोटोनिक) होना चाहिए। मोनोटोनिकिटी(दिष्टता) यह सुनिश्चित करती है कि प्रत्येक पुनरावृत्ति पर मान या तो समान रहेगा या बड़ा होगा, यद्यपि परिमित ऊंचाई सुनिश्चित करती है कि यह अनिश्चित काल तक नहीं बढ़ सकता है। इस प्रकार हम अंतत: एक ऐसी अवस्था पर पहुंच जाएंगे जहां सभी x के लिए T(x) = x, जो नियत बिंदु है।

कार्य सूची दृष्टिकोण

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

कलन विधि को कार्य सूची में सूचना-सृजन करने वाले खण्ड डालकर प्रारंभ किया जाता है। यह समाप्त हो जाता है जब कार्य सूची खाली होती है।

आदेश देना

आंकड़ा-प्रवाह समीकरणों को क्रमिक रूप से हल करने की दक्षता उस क्रम से प्रभावित होती है जिस पर स्थानीय नोड्स का भ्रमण किया जाता है।[5] इसके अतिरिक्त, यह इस बात पर निर्भर करता है कि सीएफजी पर आगे या पीछे आंकड़ा प्रवाह विश्लेषण के लिए आंकड़ा प्रवाह समीकरणों का उपयोग किया जाता है या नहीं किया जाता है। सहजता से, अग्रगामी प्रवाह की समस्या में, यह सबसे तेज़ होगा यदि खण्ड के सभी पूर्ववर्तियों को खण्ड से पहले संसाधित किया गया हो, तब से पुनरावृति नवीनतम जानकारी का उपयोग करेगी। लूप के अभाव में खण्ड को इस प्रकार से ऑर्डर करना संभव है कि प्रत्येक खण्ड को मात्र एक बार संसाधित करके सही बाह्य-अवस्थाओं की गणना की जाती है।

निम्नलिखित में, आंकड़ा-प्रवाह समीकरणों को हल करने के लिए कुछ पुनरावृति क्रमों पर चर्चा की गई है(एक नियंत्रण-प्रवाह ग्राफ के पुनरावृति क्रम से संबंधित अवधारणा a वृक्ष का ट्री ट्रैवर्सल है)।

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

प्रारंभ

सही और स्पष्ट परिणाम प्राप्त करने के लिए आंतरिक-अवस्थाओं का प्रारंभिक मूल्य महत्वपूर्ण है।

यदि परिणामों का उपयोग संकलक अनुकूलन के लिए किया जाता है, तो उन्हें रूढ़िवादी जानकारी प्रदान करनी चाहिए, अर्थात सूचना को प्रयुक्त करते समय, कार्यक्रम को शब्दार्थ नहीं बदलना चाहिए।

फिक्सपॉइंट एल्गोरिथ्म(निश्चितबिंदु कलन विधि) का पुनरावृत्ति मूल्यों को अधिकतम तत्व की दिशा में ले जाएगा। इसलिए अधिकतम तत्व वाले सभी खण्डों को प्रारंभ करना उपयोगी नहीं है। अधिकतम से कम मान वाली अवस्था में कम से कम एक खण्ड प्रारंभ होता है। विवरण डेटा-प्रवाह समस्या पर निर्भर करते हैं।

यदि न्यूनतम तत्व पूर्णरूप से रूढ़िवादी जानकारी का प्रतिनिधित्व करता है, तो परिणाम आंकड़ा-प्रवाह पुनरावृत्ति के समय भी सुरक्षित रूप से उपयोग किए जा सकते हैं। यदि यह सबसे स्पष्ट जानकारी का प्रतिनिधित्व करते है, तो परिणामों को प्रयुक्त करने से पहले निश्चितबिंदु तक पहुंचना चाहिए।

उदाहरण

निम्नलिखित कंप्यूटर कार्यक्रम के गुणों के उदाहरण हैं जिनकी गणना आंकड़ा-प्रवाह विश्लेषण द्वारा की जा सकती है।

ध्यान दें कि आंकड़ा-प्रवाह विश्लेषण द्वारा परिकलित गुण सामान्यतः वास्तविक के मात्र सन्निकटन होते हैं।

ऐसा इसलिए है क्योंकि डेटा-फ्लो विश्लेषण प्रोग्राम के स्पष्ट नियंत्रण प्रवाह का अनुकरण किए बिना सीएफजी की सिंटैक्टिकल(वाक्यात्मक) संरचना पर काम करता है।

चूंकि, अभ्यास में अभी भी उपयोगी होने के लिए, एक डेटा-प्रवाह विश्लेषण एल्गोरिदम को विशेष रूप से वास्तविक प्रोग्राम गुणों के ऊपरी क्रमशः निचले सन्निकटन की गणना करने के लिए डिज़ाइन किया गया है।

आगे का विश्लेषण

परिभाषा तक पहुँचना एनालिसिस प्रत्येक कार्यक्रम पॉइंट के लिए परिभाषाओं के समुच्चयकी गणना करता है

संभावित रूप से इस कार्यक्रम बिंदु तक पहुँच सकते हैं।

लाइन 7 पर चर a की पहुंच परिभाषा कार्यभारों(असाइनमेंट्स) का समुच्चय a = 5 लाइन 2 पर और a = 3 लाइन 4 पर है ।

if b == 4 then
     a = 5;
  else 
     a = 3;
  endif
 
  if a < 4 then
     ...

पिछड़ा विश्लेषण

प्रत्यक्ष चर विश्लेषण प्रत्येक कार्यक्रम के लिए उन चरों की गणना करता है जो हो सकते हैं , संभावित रूप से उनके अगले लेखन अद्यतन से पहले पश्चात में पढ़ें। परिणाम सामान्यतः द्वारा उपयोग किया जाता है।

मृत कोड उन्मूलन उन वर्णनों को हटाने के लिए जो एक चर को निर्दिष्ट करते हैं जिसका मूल्य पश्चात में उपयोग नहीं किया जाता है।

खण्ड की आंतरिक-अवस्था चरों का समुच्चय है जो इसके प्रारंभ में प्रत्यक्ष हैं। स्थानांतरण प्रकार्य प्रयुक्त होने से पहले और वास्तविक निहित मानों की गणना करने से पूर्व, इसमें प्रारंभिक रूप से खण्ड में सभी चर प्रत्यक्ष होते हैं। इस खण्ड के अंदर लिखे गए चरों को मारकर कथन का स्थानांतरण प्रकार्य प्रयुक्त किया जाता है (उन्हें प्रत्यक्ष चरों के समुच्चय से हटा दें)। खण्ड की बाह्य-अवस्था चरों का समुच्चय है जो खण्ड के अंत में रहते हैं और खण्ड के पुनरावृत्तियों के आंतरिक-अवस्थाओं के संघ द्वारा गणना की जाती है।

प्रारंभिक कोड:

Initial code:

b1: a = 3; 
    b = 5;
    d = 4;
    x = 100;
    if a > b then
b2:    c = a + b;
       d = 2;
b3: endif
    c = 4;
    return b * d + c;

पिछड़ा विश्लेषण:

// in: {}
b1: a = 3; 
    b = 5;
    d = 4;
    x = 100; //x is never being used later thus not in the out set {a,b,d}
    if a > b then
// out: {a,b,d}    //union of all (in) successors of b1 => b2: {a,b}, and b3:{b,d}  

// in: {a,b}
b2: c = a + b;
    d = 2;
// out: {b,d}

// in: {b,d}
b3: endif
    c = 4;
    return b * d + c;
// out:{}

b3 की आंतरिक-अवस्था में मात्र b और d होते हैं, क्योंकि c लिखा गया है। b1 का बाह्य-अवस्था b2 और b3 के आंतरिक-अवस्थाओं का संघ है। b2 में c की परिभाषा को हटाया जा सकता है, क्योंकि c कथन के तुरंत पश्चात प्रत्यक्ष नहीं होता है।

आंकड़ा-प्रवाह समीकरणों को हल करना सभी आंतरिक-अवस्थाओं और बाह्य-अवस्थाओं को खाली समुच्चय में आरंभीकृत करने से प्रारंभ होता है। कार्य सूची (पश्चगामी प्रवाह के लिए विशिष्ट) में निकास बिंदु (b3) सम्मिलित करके कार्य सूची को आरंभीकृत किया जाता है। इसकी गणना आंतरिक-अवस्था पिछले एक से भिन्न होती है, इसलिए इसके पूर्ववर्ती b1 और b2 सम्मिलित किए जाते हैं और प्रक्रिया जारी रहती है। प्रगति को नीचे दी गई तालिका में संक्षेपित किया गया है।

प्रसंस्करण बाह्य-अवस्था पूर्व आंतरिक-अवस्था नवीन आंतरिक-अवस्था कार्य सूची
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]

समस्याओं का विशेष वर्ग

आंकड़ा प्रवाह समस्याओं के कई विशेष वर्ग हैं जिनके कुशल या सामान्य समाधान हैं।

बिट वेक्टर समस्याएं

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

प्रत्येक खण्ड के लिए स्थानांतरण प्रकार्य को तथाकथित 'जीन' और 'किल' समुच्चय में विघटित किया जा सकता है।

एक उदाहरण के रूप में, प्रत्यक्ष-चर विश्लेषण में, जोड़ संचालन यूनियन है। किल समुच्चय चरों का समुच्चयहै जो एक खण्ड में लिखे जाते हैं, यद्यपि जेन समुच्चय चरों का समुच्चय है जो पहले लिखे बिना पढ़े जाते हैं। आंकड़ा प्रवाह समीकरण बन जाते हैं

तार्किक संचालन में, यह इस रूप में पढ़ता है,

out(b) = 0
for s in succ(b)
    out(b) = out(b) or in(s)
in(b) = (out(b) and not kill(b)) or gen(b)

आंकड़ा प्रवाह समस्याएं जिनमें आंकड़ा-प्रवाह मानों के समुच्चय होते हैं जिन्हें बिट वैक्टर के रूप में प्रदर्शित किया जा सकता है, उन्हें 'बिट वेक्टर समस्याएं', 'जेन-किल समस्याएं', या 'स्थानीय रूप से भिन्न करने योग्य समस्याएं' कहा जाता है।[8] ऐसी समस्याओं के सामान्य बहुपद-समय समाधान हैं।[9]

ऊपर बताई गई पहुंच परिभाषाओं और प्रत्यक्ष चर समस्याओं के अतिरिक्त, निम्नलिखित समस्याएं बिटवेक्टर समस्याओं के उदाहरण हैं:[9]

  • उपलब्ध भाव
  • बहुत व्यस्त भाव
  • यूज-डिफाइन चेन (उपयोग-परिभाषा श्रृंखला)

आईएफडीएस समस्याएं

अंतर-प्रक्रियात्मक, परिमित, वितरणात्मक, सब समुच्चय समस्याएँ या आईएफडीएस समस्याएँ सामान्य बहुपद-समय समाधान के साथ समस्या का एक अन्य वर्ग हैं।[8][10] इन समस्याओं के समाधान संदर्भ-संवेदनशील और प्रवाह-संवेदनशील आंकड़ा प्रवाह विश्लेषण प्रदान करते हैं।

लोकप्रिय कार्यक्रमिंग भाषाओं के लिए आईएफडीएस - आधारित आंकड़ा प्रवाह विश्लेषण के कई कार्यान्वयन हैं, उदा। सूत में[11] और कुछ नहीं[12] जावा विश्लेषण के लिए रूपरेखा।

प्रत्येक बिटवेक्टर समस्या भी एक आईएफडीएस समस्या है, किन्तु कई महत्वपूर्ण आईएफडीएस समस्याएँ हैं जो बिटवेक्टर समस्याएँ नहीं हैं, जिनमें वास्तविक-प्रत्यक्ष चर और संभवतः-अनियंत्रित चर सम्मिलित हैं।

संवेदनशीलता

आंकड़ा-प्रवाह विश्लेषण सामान्यतः पथ-असंवेदनशील होता है, चूंकि आंकड़ा-प्रवाह समीकरणों को परिभाषित करना संभव है जो पथ-संवेदनशील विश्लेषण उत्पन्न करते हैं।

  • एक प्रवाह-संवेदनशील विश्लेषण एक कार्यक्रम में वर्णनों के क्रम को ध्यान में रखता है। उदाहरण के लिए, एक प्रवाह-असंवेदनशील सूचक उपनाम विश्लेषण चर x और y को निर्धारित कर सकता है जो एक ही स्थान को संदर्भित कर सकता है, यद्यपि एक प्रवाह-संवेदनशील विश्लेषण कथन 20 के पश्चातनिर्धारित कर सकता है, चर x और y उसी स्थान को संदर्भित कर सकता है।
  • एक पथ-संवेदनशील विश्लेषण सनिबंधन शाखा निर्देशों पर विधेय पर निर्भर विश्लेषण जानकारी के विभिन्न टुकड़ों की गणना करता है। उदाहरण के लिए, यदि किसी शाखा में कोई निबंधन है x>0, तो फ़ॉल-थ्रू पथ पर, विश्लेषण यह मान लेगा x<=0 और शाखा के निशाने पर यह मान लिया जाएगा कि वास्तव में x>0 रखती है।
  • एक संदर्भ-संवेदनशील विश्लेषण एक अंतरप्रक्रियात्मक विश्लेषण है जो प्रकार्य कॉल के लक्ष्य का विश्लेषण करते समय कॉलिंग संदर्भ पर विचार करता है। विशेष रूप से, संदर्भ जानकारी का उपयोग करके कोई भी वास्तविककॉल साइट पर वापस जा सकता है, यद्यपि उस जानकारी के बिना, विश्लेषण जानकारी को सभी संभावित कॉल साइटों पर वापस प्रचारित करना पड़ता है, संभावित रूप से नियतता खो देता है।

आंकड़ा-प्रवाह विश्लेषणों की सूची

यह भी देखें

  • सार व्याख्या
  • नियंत्रण प्रवाह विश्लेषण
  • XLT86

संदर्भ

  1. 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.
  2. 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])
  3. 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.
  4. 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)
  5. 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]
  6. 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.
  7. 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. 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. 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.
  10. 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
  11. 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.
  12. 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.

अग्रिम पठन