नियंत्रण-प्रवाह ग्राफ: Difference between revisions

From Vigyanwiki
(Created page with "{{Short description|Graphical representation of a computer program or algorithm}} {{multiple issues| {{More citations needed|date=January 2009}} {{expert needed|Computer scien...")
 
(Text)
Line 5: Line 5:
}}
}}


[[File:Some types of control flow graphs.svg|thumb|कुछ CFG उदाहरण:<br />(a) if-then-else<br />(b) a while लूप<br />(c) दो निकासों वाला एक प्राकृतिक लूप, उदा. जबकि if...बीच में ब्रेक के साथ; गैर-संरचित लेकिन कम करने योग्य<br />(d) एक इर्रिड्यूसिबल CFG: एक लूप जिसमें दो प्रवेश बिंदु होते हैं, उदा. गोटो थोड़ी देर में या पाश के लिए]]
[[File:Some types of control flow graphs.svg|thumb|कुछ सीएफजी उदाहरण:<br />(a) अगर-तब-या<br />(b) एक वाहिल लूप<br />(c) दो निकासों वाला एक प्राकृतिक लूप, उदा. वाहिल इफ...बीच में ब्रेक के साथ; गैर-संरचित लेकिन कम करने योग्य<br />(d) एक अलघुकरणीय सीएफजी : एक लूप जिसमें दो प्रवेश बिंदु होते हैं, उदा. वाहिल और फॉर लूप मैं जाने के लिए ]]
[[File:Rust_MIR_CFG.svg|thumb|कोडेन करने के लिए रस्ट कंपाइलर द्वारा उपयोग किया जाने वाला एक नियंत्रण प्रवाह ग्राफ।]][[कंप्यूटर विज्ञान]] में, एक कंट्रोल-फ्लो ग्राफ (सीएफजी) एक [[चित्रण]] है, जो [[ग्राफ (असतत गणित)]] अंकन का उपयोग करते हुए, उन सभी रास्तों का है, जो इसके [[निष्पादन (कंप्यूटिंग)]] के दौरान एक [[कंप्यूटर प्रोग्राम]] के माध्यम से हो सकते हैं। नियंत्रण-प्रवाह ग्राफ की खोज फ्रांसिस ई. एलन ने की थी,<ref>{{cite journal
[[File:Rust_MIR_CFG.svg|thumb|कोडेन करने के लिए पुराने अनुभाषक(कंपाइलर) द्वारा उपयोग किया जाने वाला एक नियंत्रण प्रवाह लेखाचित्र।]][[कंप्यूटर विज्ञान]] में, एक नियंत्रण-प्रवाह लेखाचित्र(सीएफजी) एक [[चित्रण]] है, जो [[ग्राफ (असतत गणित)|लेखाचित्र(ग्राफ)]] अंकन का उपयोग करते हुए, उन सभी रास्तों का है, जो इसके [[निष्पादन (कंप्यूटिंग)]] के दौरान एक [[कंप्यूटर प्रोग्राम]] के माध्यम से हो सकते हैं। नियंत्रण-प्रवाह लेखाचित्र की खोज फ्रांसिस ई. एलन ने की थी,<ref>{{cite journal
| author = Frances E. Allen
| author = Frances E. Allen
| title = Control flow analysis
| title = Control flow analysis
Line 15: Line 15:
| pages = 1–19
| pages = 1–19
| doi=10.1145/390013.808479| author-link = Frances E. Allen
| doi=10.1145/390013.808479| author-link = Frances E. Allen
}}</ref> जिन्होंने नोट किया कि Reese Prosser|Reese T. Prosser ने इससे पहले प्रवाह विश्लेषण के लिए Adjacency मैट्रिक्स का उपयोग किया था।<ref>{{cite conference  
}}</ref> जिन्होंने ध्यान दिया कि रीज़ टी. प्रॉसेर ने पहले प्रवाह विश्लेषण के लिए बूलियन संबद्धता मैट्रिसेस का उपयोग किया था।<ref>{{cite conference  
| author = Reese T. Prosser
| author = Reese T. Prosser
| title = Applications of Boolean matrices to the analysis of flow diagrams
| title = Applications of Boolean matrices to the analysis of flow diagrams
Line 23: Line 23:
| author-link = Reese Prosser
| author-link = Reese Prosser
}}</ref>
}}</ref>
CFG कई कंपाइलर ऑप्टिमाइजेशन # डेटा-फ्लो ऑप्टिमाइजेशन और [[स्थिर कोड विश्लेषण]] | स्टैटिक-एनालिसिस टूल्स के लिए जरूरी है।
सीएफजी कई संकलक अनुकूलीकरण और [[स्थिर कोड विश्लेषण]] टूल्स के लिए जरूरी है।                                                                                                                                                      


== परिभाषा ==
== परिभाषा ==
एक नियंत्रण-प्रवाह ग्राफ में ग्राफ (असतत गणित) में प्रत्येक वर्टेक्स (ग्राफ सिद्धांत) एक [[बुनियादी ब्लॉक]] का प्रतिनिधित्व करता है, यानी बिना किसी छलांग या [[कूद लक्ष्य (कंप्यूटिंग)]] के कोड का एक सीधी रेखा का टुकड़ा; जंप लक्ष्य एक ब्लॉक शुरू करते हैं, और जंप एक ब्लॉक को समाप्त करते हैं। निर्देशित किनारे (ग्राफ सिद्धांत) का उपयोग नियंत्रण प्रवाह में छलांग का प्रतिनिधित्व करने के लिए किया जाता है। अधिकांश प्रस्तुतियों में, दो विशेष रूप से निर्दिष्ट ब्लॉक होते हैं: एंट्री ब्लॉक, जिसके माध्यम से प्रवाह ग्राफ में नियंत्रण प्रवेश करता है, और निकास ब्लॉक, जिसके माध्यम से सभी नियंत्रण प्रवाह निकल जाते हैं।<ref>{{cite conference |chapter=Masking wrong-successor Control Flow Errors employing data redundancy  |last1=Yousefi |first1=Javad |title=2015 5th International Conference on Computer and Knowledge Engineering (ICCKE) |date= 2015|publisher=IEEE |pages=201–205 |doi=10.1109/ICCKE.2015.7365827 |url=https://ieeexplore.ieee.org/document/7365827|isbn=978-1-4673-9280-8 }}</ref>
एक नियंत्रण-प्रवाह लेखाचित्र में लेखाचित्र में प्रत्येक बिंदु  एक [[बुनियादी ब्लॉक|बुनियादी ढांचे]] का प्रतिनिधित्व करता है, यानी बिना किसी विषयांतर या [[कूद लक्ष्य (कंप्यूटिंग)|लक्ष्य]] के सरल रेखीय कोड का अंश; विषयांतर लक्ष्य एक ढांचा  शुरू करते हैं, और विषयांतर एक ढांचे को समाप्त करता हैं। निर्देशित किनारों का उपयोग नियंत्रण प्रवाह में विषयांतर का प्रतिनिधित्व करने के लिए किया जाता है। अधिकांश प्रस्तुतियों में, दो विशेष रूप से निर्दिष्ट ढांचे होते हैं: प्रविष्टि ढांचा, जिसके माध्यम से प्रवाह लेखाचित्र में नियंत्रण प्रवेश करता है, और निकास ढांचा, जिसके माध्यम से सभी नियंत्रण प्रवाह निकल जाते हैं।<ref>{{cite conference |chapter=Masking wrong-successor Control Flow Errors employing data redundancy  |last1=Yousefi |first1=Javad |title=2015 5th International Conference on Computer and Knowledge Engineering (ICCKE) |date= 2015|publisher=IEEE |pages=201–205 |doi=10.1109/ICCKE.2015.7365827 |url=https://ieeexplore.ieee.org/document/7365827|isbn=978-1-4673-9280-8 }}</ref>
 
इसकी निर्माण प्रक्रिया के कारण, एक सीएफजी में, प्रत्येक किनारे ए → बी में संपत्ति है:
इसकी निर्माण प्रक्रिया के कारण, एक सीएफजी में, प्रत्येक किनारे ए → बी में संपत्ति है:
: [[आगे की डिग्री]] (ए)> 1 या इंडिग्री (बी)> 1 (या दोनों)।<ref name="TarrWolf2011">{{cite book|author1=Peri L. Tarr|author2=Alexander L. Wolf|title=Engineering of Software: The Continuing Contributions of Leon J. Osterweil|year=2011|publisher=Springer Science & Business Media|isbn=978-3-642-19823-6|page=58}}</ref>
: [[आगे की डिग्री]] (ए)> 1 या अंतःकोटि(बी)> 1 (या दोनों)।<ref name="TarrWolf2011">{{cite book|author1=Peri L. Tarr|author2=Alexander L. Wolf|title=Engineering of Software: The Continuing Contributions of Leon J. Osterweil|year=2011|publisher=Springer Science & Business Media|isbn=978-3-642-19823-6|page=58}}</ref>
सीएफजी इस प्रकार, कम से कम संकल्पनात्मक रूप से, कार्यक्रम के (पूर्ण) प्रवाह ग्राफ से शुरू करके प्राप्त किया जा सकता है - अर्थात। वह ग्राफ जिसमें प्रत्येक नोड एक व्यक्तिगत निर्देश का प्रतिनिधित्व करता है - और प्रत्येक किनारे के लिए एक किनारे का संकुचन करता है जो ऊपर दिए गए विधेय को गलत साबित करता है, यानी हर किनारे को अनुबंधित करता है जिसका स्रोत एक एकल निकास है और जिसका गंतव्य एक ही प्रविष्टि है। सीएफजी निर्माण को समझने के लिए विज़ुअलाइज़ेशन सहायता के अलावा, इस संकुचन-आधारित एल्गोरिदम का कोई व्यावहारिक महत्व नहीं है, क्योंकि सीएफजी को मूल ब्लॉक#क्रिएशन एल्गोरिदम द्वारा सीधे कार्यक्रम से अधिक कुशलतापूर्वक बनाया जा सकता है।<ref name="TarrWolf2011"/>
सीएफजी इस प्रकार, कम से कम संकल्पनात्मक रूप से, प्रोग्राम के (पूर्ण) प्रवाह लेखाचित्र से शुरू करके प्राप्त किया जा सकता है - अर्थात। वह लेखाचित्र जिसमें प्रत्येक नोड एक व्यक्तिगत निर्देश का प्रतिनिधित्व करता है - और प्रत्येक किनारे के लिए एक किनारे का संकुचन करता है जो ऊपर दिए गए विधेय को गलत साबित करता है, यानी हर किनारे को अनुबंधित करता है जिसका स्रोत एक एकल निकास है और जिसका गंतव्य एक ही प्रविष्टि है। सीएफजी निर्माण को समझने के लिए मानस दर्शन सहायता के अलावा, इस संकुचन-आधारित एल्गोरिदम(कलनविधि) का कोई व्यावहारिक महत्व नहीं है, क्योंकि सीएफजी को मूल ढांचा 'निर्माण कलनविधि द्वारा सीधे प्रोग्राम से अधिक कुशलतापूर्वक बनाया जा सकता है।<ref name="TarrWolf2011" />
 




Line 42: Line 44:
5: (डी) अंत कार्यक्रम
5: (डी) अंत कार्यक्रम
</पूर्व>
</पूर्व>
उपरोक्त में, हमारे पास 4 मूल ब्लॉक हैं: ए 0 से 1 तक, बी 2 से 3 तक, सी 4 पर और डी 5 पर। विशेष रूप से, इस मामले में, ए एंट्री ब्लॉक है, डी एग्जिट ब्लॉक और लाइन 4 है। और 5 जम्प टारगेट हैं। इस टुकड़े के लिए एक ग्राफ में ए से बी, ए से सी, बी से डी और सी से डी के किनारे हैं।
उपरोक्त में, हमारे पास 4 मूल ब्लॉक हैं: ए 0 से 1 तक, बी 2 से 3 तक, सी 4 पर और डी 5 पर। विशेष रूप से, इस मामले में, ए एंट्री ब्लॉक है, डी एग्जिट ब्लॉक और लाइन 4 है। और 5 जम्प टारगेट हैं। इस टुकड़े के लिए एक लेखाचित्र में ए से बी, ए से सी, बी से डी और सी से डी के किनारे हैं।


== पहुंच योग्यता ==
== पहुंच योग्यता ==
{{Main|Reachability}}
{{Main|Reachability}}
[[गम्यता]] एक ग्राफ प्रॉपर्टी है जो ऑप्टिमाइज़ेशन में उपयोगी है।
[[गम्यता]] एक लेखाचित्र प्रॉपर्टी है जो ऑप्टिमाइज़ेशन में उपयोगी है।


यदि सबग्राफ एंट्री ब्लॉक वाले सबग्राफ से जुड़ा नहीं है, तो वह सबग्राफ किसी भी निष्पादन के दौरान पहुंच योग्य नहीं है, और इसलिए पहुंच योग्य कोड नहीं है; सामान्य परिस्थितियों में इसे सुरक्षित रूप से हटाया जा सकता है।
यदि सबलेखाचित्र एंट्री ब्लॉक वाले सबलेखाचित्र से जुड़ा नहीं है, तो वह सबलेखाचित्र किसी भी निष्पादन के दौरान पहुंच योग्य नहीं है, और इसलिए पहुंच योग्य कोड नहीं है; सामान्य परिस्थितियों में इसे सुरक्षित रूप से हटाया जा सकता है।


यदि एंट्री ब्लॉक से एग्जिट ब्लॉक अगम्य है, तो एक [[अनंत लूप]] मौजूद हो सकता है। सभी अनंत लूपों का पता नहीं लगाया जा सकता है, हॉल्टिंग समस्या देखें। वहां पर रोक लगाने का आदेश भी हो सकता है।
यदि एंट्री ब्लॉक से एग्जिट ब्लॉक अगम्य है, तो एक [[अनंत लूप]] मौजूद हो सकता है। सभी अनंत लूपों का पता नहीं लगाया जा सकता है, हॉल्टिंग समस्या देखें। वहां पर रोक लगाने का आदेश भी हो सकता है।


अगम्य कोड और अनंत लूप तब भी संभव हैं जब प्रोग्रामर उन्हें स्पष्ट रूप से कोड नहीं करता है: निरंतर प्रचार और निरंतर फोल्डिंग के बाद [[जंप थ्रेडिंग]] जैसे अनुकूलन कई बुनियादी ब्लॉकों को एक में ढहा सकते हैं, जिससे किनारों को CFG से हटाया जा सकता है, आदि, इस प्रकार संभवतः ग्राफ के हिस्सों को डिस्कनेक्ट करना।
अगम्य कोड और अनंत लूप तब भी संभव हैं जब प्रोग्रामर उन्हें स्पष्ट रूप से कोड नहीं करता है: निरंतर प्रचार और निरंतर फोल्डिंग के बाद [[जंप थ्रेडिंग]] जैसे अनुकूलन कई बुनियादी ब्लॉकों को एक में ढहा सकते हैं, जिससे किनारों को CFG से हटाया जा सकता है, आदि, इस प्रकार संभवतः लेखाचित्र के हिस्सों को डिस्कनेक्ट करना।


== वर्चस्व संबंध ==
== वर्चस्व संबंध ==
{{Main|Dominator (graph theory)}}
{{Main|Dominator (graph theory)}}
ए ब्लॉक एम डोमिनेटर (ग्राफ थ्योरी) एक ब्लॉक एन यदि ब्लॉक एन तक पहुंचने वाले प्रवेश से प्रत्येक पथ को ब्लॉक एम से गुजरना पड़ता है। प्रवेश ब्लॉक सभी ब्लॉकों पर हावी है।
ए ब्लॉक एम डोमिनेटर (लेखाचित्र थ्योरी) एक ब्लॉक एन यदि ब्लॉक एन तक पहुंचने वाले प्रवेश से प्रत्येक पथ को ब्लॉक एम से गुजरना पड़ता है। प्रवेश ब्लॉक सभी ब्लॉकों पर हावी है।


विपरीत दिशा में, ब्लॉक एम ब्लॉक एन पर पोस्टडोमिनेट करता है यदि एन से बाहर निकलने के लिए हर पथ को ब्लॉक एम से गुजरना पड़ता है। निकास ब्लॉक सभी ब्लॉकों पर पोस्टडोमिनेट करता है।
विपरीत दिशा में, ब्लॉक एम ब्लॉक एन पर पोस्टडोमिनेट करता है यदि एन से बाहर निकलने के लिए हर पथ को ब्लॉक एम से गुजरना पड़ता है। निकास ब्लॉक सभी ब्लॉकों पर पोस्टडोमिनेट करता है।
Line 64: Line 66:
इसी तरह, तत्काल पोस्टडोमिनेटर की एक धारणा है, जो तत्काल डॉमिनेटर के समान है।
इसी तरह, तत्काल पोस्टडोमिनेटर की एक धारणा है, जो तत्काल डॉमिनेटर के समान है।


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


एक पोस्टडोमिनेटर ट्री डोमिनेटर ट्री के अनुरूप होता है। यह पेड़ एग्जिट ब्लॉक पर जड़ जमाए हुए है।
एक पोस्टडोमिनेटर ट्री डोमिनेटर ट्री के अनुरूप होता है। यह पेड़ एग्जिट ब्लॉक पर जड़ जमाए हुए है।
Line 70: Line 72:
== विशेष किनारा ==
== विशेष किनारा ==


एक बैक एज एक ऐसा किनारा है जो एक ब्लॉक को इंगित करता है जो ग्राफ के गहराई-पहले ([[गहराई-पहली खोज]]) ट्रैवर्सल के दौरान पहले ही मिल चुका है। पीछे के किनारे लूप के विशिष्ट हैं।
एक बैक एज एक ऐसा किनारा है जो एक ब्लॉक को इंगित करता है जो लेखाचित्र के गहराई-पहले ([[गहराई-पहली खोज]]) ट्रैवर्सल के दौरान पहले ही मिल चुका है। पीछे के किनारे लूप के विशिष्ट हैं।


एक महत्वपूर्ण किनारा एक किनारा है जो न तो अपने स्रोत ब्लॉक को छोड़ने वाला एकमात्र किनारा है और न ही अपने गंतव्य ब्लॉक में प्रवेश करने वाला एकमात्र किनारा है। इन किनारों को विभाजित किया जाना चाहिए: किसी अन्य किनारों को प्रभावित किए बिना किनारे पर संगणना सम्मिलित करने के लिए किनारे के बीच में एक नया ब्लॉक बनाया जाना चाहिए।
एक महत्वपूर्ण किनारा एक किनारा है जो न तो अपने स्रोत ब्लॉक को छोड़ने वाला एकमात्र किनारा है और न ही अपने गंतव्य ब्लॉक में प्रवेश करने वाला एकमात्र किनारा है। इन किनारों को विभाजित किया जाना चाहिए: किसी अन्य किनारों को प्रभावित किए बिना किनारे पर संगणना सम्मिलित करने के लिए किनारे के बीच में एक नया ब्लॉक बनाया जाना चाहिए।
Line 76: Line 78:
एक असामान्य किनारा एक किनारा है जिसका गंतव्य अज्ञात है। अपवाद हैंडलिंग निर्माण उन्हें उत्पन्न कर सकते हैं। ये किनारे अनुकूलन को बाधित करते हैं।
एक असामान्य किनारा एक किनारा है जिसका गंतव्य अज्ञात है। अपवाद हैंडलिंग निर्माण उन्हें उत्पन्न कर सकते हैं। ये किनारे अनुकूलन को बाधित करते हैं।


एक असंभव बढ़त (एक नकली बढ़त के रूप में भी जाना जाता है) एक किनारा है जिसे पूरी तरह से उस संपत्ति को संरक्षित करने के लिए ग्राफ़ में जोड़ा गया है जो निकास ब्लॉक सभी ब्लॉकों को पोस्टडोमिनेट करता है। इसे कभी भी पार नहीं किया जा सकता है।
एक असंभव बढ़त (एक नकली बढ़त के रूप में भी जाना जाता है) एक किनारा है जिसे पूरी तरह से उस संपत्ति को संरक्षित करने के लिए लेखाचित्ऱ में जोड़ा गया है जो निकास ब्लॉक सभी ब्लॉकों को पोस्टडोमिनेट करता है। इसे कभी भी पार नहीं किया जा सकता है।


== लूप प्रबंधन ==
== लूप प्रबंधन ==
Line 87: Line 89:


एक कम करने योग्य सीएफजी किनारों के साथ एक है जिसे दो अलग-अलग सेटों में विभाजित किया जा सकता है: आगे के किनारे और पीछे के किनारे, जैसे कि:<ref>{{Cite web |url=http://www.cs.colostate.edu/~mstrout/CS553Fall06/slides/lecture13-control.pdf |title=Archived copy |access-date=2018-03-24 |archive-date=2020-08-01 |archive-url=https://web.archive.org/web/20200801004407/https://www.cs.colostate.edu/~mstrout/CS553Fall06/slides/lecture13-control.pdf |url-status=dead }}</ref>
एक कम करने योग्य सीएफजी किनारों के साथ एक है जिसे दो अलग-अलग सेटों में विभाजित किया जा सकता है: आगे के किनारे और पीछे के किनारे, जैसे कि:<ref>{{Cite web |url=http://www.cs.colostate.edu/~mstrout/CS553Fall06/slides/lecture13-control.pdf |title=Archived copy |access-date=2018-03-24 |archive-date=2020-08-01 |archive-url=https://web.archive.org/web/20200801004407/https://www.cs.colostate.edu/~mstrout/CS553Fall06/slides/lecture13-control.pdf |url-status=dead }}</ref>
* आगे के किनारे प्रवेश नोड से पहुंचने योग्य सभी नोड्स के साथ एक निर्देशित चक्रीय ग्राफ बनाते हैं।
* आगे के किनारे प्रवेश नोड से पहुंचने योग्य सभी नोड्स के साथ एक निर्देशित चक्रीय लेखाचित्र बनाते हैं।
* सभी बैक किनारों (ए, बी), नोड बी डोमिनेटर (ग्राफ सिद्धांत) नोड ए के लिए।
* सभी बैक किनारों (ए, बी), नोड बी डोमिनेटर (लेखाचित्र सिद्धांत) नोड ए के लिए।


[[संरचित प्रोग्रामिंग]] भाषाओं को अक्सर इस तरह डिज़ाइन किया जाता है कि उनके द्वारा उत्पादित सभी CFG कम करने योग्य होते हैं, और सामान्य संरचित प्रोग्रामिंग स्टेटमेंट जैसे IF, FOR, WHILE, BREAK, और CONTINUE कम करने योग्य ग्राफ उत्पन्न करते हैं। अलघुकरणीय रेखांकन तैयार करने के लिए [[GOTO]] जैसे कथनों की आवश्यकता होती है। इरेड्यूसिबल ग्राफ कुछ कंपाइलर ऑप्टिमाइज़ेशन द्वारा भी तैयार किए जा सकते हैं।
[[संरचित प्रोग्रामिंग]] भाषाओं को अक्सर इस तरह डिज़ाइन किया जाता है कि उनके द्वारा उत्पादित सभी CFG कम करने योग्य होते हैं, और सामान्य संरचित प्रोग्रामिंग स्टेटमेंट जैसे IF, FOR, WHILE, BREAK, और CONTINUE कम करने योग्य लेखाचित्र उत्पन्न करते हैं। अलघुकरणीय रेखांकन तैयार करने के लिए [[GOTO]] जैसे कथनों की आवश्यकता होती है। इरेड्यूसिबल लेखाचित्र कुछ कंपाइलर ऑप्टिमाइज़ेशन द्वारा भी तैयार किए जा सकते हैं।


== लूप जुड़ाव ==
== लूप जुड़ाव ==
Line 101: Line 103:




== अंतर-प्रक्रियात्मक नियंत्रण प्रवाह ग्राफ ==
== अंतर-प्रक्रियात्मक नियंत्रण प्रवाह लेखाचित्र ==


जबकि नियंत्रण प्रवाह ग्राफ़ एकल प्रक्रिया के नियंत्रण प्रवाह का प्रतिनिधित्व करते हैं, अंतर-प्रक्रियात्मक नियंत्रण प्रवाह ग्राफ़ पूरे कार्यक्रमों के नियंत्रण प्रवाह का प्रतिनिधित्व करते हैं।<ref>{{Cite web|url=http://web.cs.iastate.edu/~weile/cs513x/4.ControlFlowAnalysis.pdf |archive-url=https://web.archive.org/web/20161219113226/http://web.cs.iastate.edu/~weile/cs513x/4.ControlFlowAnalysis.pdf |archive-date=2016-12-19 |url-status=live|title=Control Flow Analysis|date=2016}}</ref>
जबकि नियंत्रण प्रवाह लेखाचित्ऱ एकल प्रक्रिया के नियंत्रण प्रवाह का प्रतिनिधित्व करते हैं, अंतर-प्रक्रियात्मक नियंत्रण प्रवाह लेखाचित्ऱ पूरे कार्यक्रमों के नियंत्रण प्रवाह का प्रतिनिधित्व करते हैं।<ref>{{Cite web|url=http://web.cs.iastate.edu/~weile/cs513x/4.ControlFlowAnalysis.pdf |archive-url=https://web.archive.org/web/20161219113226/http://web.cs.iastate.edu/~weile/cs513x/4.ControlFlowAnalysis.pdf |archive-date=2016-12-19 |url-status=live|title=Control Flow Analysis|date=2016}}</ref>




Line 112: Line 114:
* नियंत्रण-प्रवाह विश्लेषण
* नियंत्रण-प्रवाह विश्लेषण
* डेटा प्रवाह विश्लेषण
* डेटा प्रवाह विश्लेषण
* [[अंतराल (ग्राफ सिद्धांत)]]
* [[अंतराल (ग्राफ सिद्धांत)|अंतराल (लेखाचित्र सिद्धांत)]]
* [[कार्यक्रम निर्भरता ग्राफ]]
* [[कार्यक्रम निर्भरता ग्राफ|कार्यक्रम निर्भरता लेखाचित्र]]
* [[साइक्लोमेटिक कम्पलेक्सिटी]]
* [[साइक्लोमेटिक कम्पलेक्सिटी]]
* [[स्टेटिक सिंगल असाइनमेंट]]
* [[स्टेटिक सिंगल असाइनमेंट]]

Revision as of 22:07, 24 February 2023

कुछ सीएफजी उदाहरण:
(a) अगर-तब-या
(b) एक वाहिल लूप
(c) दो निकासों वाला एक प्राकृतिक लूप, उदा. वाहिल इफ...बीच में ब्रेक के साथ; गैर-संरचित लेकिन कम करने योग्य
(d) एक अलघुकरणीय सीएफजी : एक लूप जिसमें दो प्रवेश बिंदु होते हैं, उदा. वाहिल और फॉर लूप मैं जाने के लिए
कोडेन करने के लिए पुराने अनुभाषक(कंपाइलर) द्वारा उपयोग किया जाने वाला एक नियंत्रण प्रवाह लेखाचित्र।

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

सीएफजी कई संकलक अनुकूलीकरण और स्थिर कोड विश्लेषण टूल्स के लिए जरूरी है।

परिभाषा

एक नियंत्रण-प्रवाह लेखाचित्र में लेखाचित्र में प्रत्येक बिंदु एक बुनियादी ढांचे का प्रतिनिधित्व करता है, यानी बिना किसी विषयांतर या लक्ष्य के सरल रेखीय कोड का अंश; विषयांतर लक्ष्य एक ढांचा शुरू करते हैं, और विषयांतर एक ढांचे को समाप्त करता हैं। निर्देशित किनारों का उपयोग नियंत्रण प्रवाह में विषयांतर का प्रतिनिधित्व करने के लिए किया जाता है। अधिकांश प्रस्तुतियों में, दो विशेष रूप से निर्दिष्ट ढांचे होते हैं: प्रविष्टि ढांचा, जिसके माध्यम से प्रवाह लेखाचित्र में नियंत्रण प्रवेश करता है, और निकास ढांचा, जिसके माध्यम से सभी नियंत्रण प्रवाह निकल जाते हैं।[3]

इसकी निर्माण प्रक्रिया के कारण, एक सीएफजी में, प्रत्येक किनारे ए → बी में संपत्ति है:

आगे की डिग्री (ए)> 1 या अंतःकोटि(बी)> 1 (या दोनों)।[4]

सीएफजी इस प्रकार, कम से कम संकल्पनात्मक रूप से, प्रोग्राम के (पूर्ण) प्रवाह लेखाचित्र से शुरू करके प्राप्त किया जा सकता है - अर्थात। वह लेखाचित्र जिसमें प्रत्येक नोड एक व्यक्तिगत निर्देश का प्रतिनिधित्व करता है - और प्रत्येक किनारे के लिए एक किनारे का संकुचन करता है जो ऊपर दिए गए विधेय को गलत साबित करता है, यानी हर किनारे को अनुबंधित करता है जिसका स्रोत एक एकल निकास है और जिसका गंतव्य एक ही प्रविष्टि है। सीएफजी निर्माण को समझने के लिए मानस दर्शन सहायता के अलावा, इस संकुचन-आधारित एल्गोरिदम(कलनविधि) का कोई व्यावहारिक महत्व नहीं है, क्योंकि सीएफजी को मूल ढांचा 'निर्माण कलनविधि द्वारा सीधे प्रोग्राम से अधिक कुशलतापूर्वक बनाया जा सकता है।[4]


उदाहरण

कोड के निम्नलिखित टुकड़े पर विचार करें: <पूर्व> 0: (ए) t0 = read_num 1: (ए) अगर टी 0 मॉड 2 == 0 2: (बी) प्रिंट t0 + सम है। 3: (बी) गोटो 5 4: (सी) प्रिंट t0 + विषम है। 5: (डी) अंत कार्यक्रम </पूर्व> उपरोक्त में, हमारे पास 4 मूल ब्लॉक हैं: ए 0 से 1 तक, बी 2 से 3 तक, सी 4 पर और डी 5 पर। विशेष रूप से, इस मामले में, ए एंट्री ब्लॉक है, डी एग्जिट ब्लॉक और लाइन 4 है। और 5 जम्प टारगेट हैं। इस टुकड़े के लिए एक लेखाचित्र में ए से बी, ए से सी, बी से डी और सी से डी के किनारे हैं।

पहुंच योग्यता

Main article: Reachability

गम्यता एक लेखाचित्र प्रॉपर्टी है जो ऑप्टिमाइज़ेशन में उपयोगी है।

यदि सबलेखाचित्र एंट्री ब्लॉक वाले सबलेखाचित्र से जुड़ा नहीं है, तो वह सबलेखाचित्र किसी भी निष्पादन के दौरान पहुंच योग्य नहीं है, और इसलिए पहुंच योग्य कोड नहीं है; सामान्य परिस्थितियों में इसे सुरक्षित रूप से हटाया जा सकता है।

यदि एंट्री ब्लॉक से एग्जिट ब्लॉक अगम्य है, तो एक अनंत लूप मौजूद हो सकता है। सभी अनंत लूपों का पता नहीं लगाया जा सकता है, हॉल्टिंग समस्या देखें। वहां पर रोक लगाने का आदेश भी हो सकता है।

अगम्य कोड और अनंत लूप तब भी संभव हैं जब प्रोग्रामर उन्हें स्पष्ट रूप से कोड नहीं करता है: निरंतर प्रचार और निरंतर फोल्डिंग के बाद जंप थ्रेडिंग जैसे अनुकूलन कई बुनियादी ब्लॉकों को एक में ढहा सकते हैं, जिससे किनारों को CFG से हटाया जा सकता है, आदि, इस प्रकार संभवतः लेखाचित्र के हिस्सों को डिस्कनेक्ट करना।

वर्चस्व संबंध

Main article: Dominator (graph theory)

ए ब्लॉक एम डोमिनेटर (लेखाचित्र थ्योरी) एक ब्लॉक एन यदि ब्लॉक एन तक पहुंचने वाले प्रवेश से प्रत्येक पथ को ब्लॉक एम से गुजरना पड़ता है। प्रवेश ब्लॉक सभी ब्लॉकों पर हावी है।

विपरीत दिशा में, ब्लॉक एम ब्लॉक एन पर पोस्टडोमिनेट करता है यदि एन से बाहर निकलने के लिए हर पथ को ब्लॉक एम से गुजरना पड़ता है। निकास ब्लॉक सभी ब्लॉकों पर पोस्टडोमिनेट करता है।

ऐसा कहा जाता है कि यदि M, N पर हावी है तो एक ब्लॉक M तुरंत ब्लॉक N पर हावी हो जाता है, और कोई हस्तक्षेप करने वाला ब्लॉक P नहीं है जैसे कि M, P पर हावी हो और P N पर हावी हो। दूसरे शब्दों में, N में प्रवेश से सभी रास्तों पर M अंतिम प्रभुत्व है। प्रत्येक ब्लॉक में एक अद्वितीय तत्काल प्रभुत्व होता है।

इसी तरह, तत्काल पोस्टडोमिनेटर की एक धारणा है, जो तत्काल डॉमिनेटर के समान है।

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

एक पोस्टडोमिनेटर ट्री डोमिनेटर ट्री के अनुरूप होता है। यह पेड़ एग्जिट ब्लॉक पर जड़ जमाए हुए है।

विशेष किनारा

एक बैक एज एक ऐसा किनारा है जो एक ब्लॉक को इंगित करता है जो लेखाचित्र के गहराई-पहले (गहराई-पहली खोज) ट्रैवर्सल के दौरान पहले ही मिल चुका है। पीछे के किनारे लूप के विशिष्ट हैं।

एक महत्वपूर्ण किनारा एक किनारा है जो न तो अपने स्रोत ब्लॉक को छोड़ने वाला एकमात्र किनारा है और न ही अपने गंतव्य ब्लॉक में प्रवेश करने वाला एकमात्र किनारा है। इन किनारों को विभाजित किया जाना चाहिए: किसी अन्य किनारों को प्रभावित किए बिना किनारे पर संगणना सम्मिलित करने के लिए किनारे के बीच में एक नया ब्लॉक बनाया जाना चाहिए।

एक असामान्य किनारा एक किनारा है जिसका गंतव्य अज्ञात है। अपवाद हैंडलिंग निर्माण उन्हें उत्पन्न कर सकते हैं। ये किनारे अनुकूलन को बाधित करते हैं।

एक असंभव बढ़त (एक नकली बढ़त के रूप में भी जाना जाता है) एक किनारा है जिसे पूरी तरह से उस संपत्ति को संरक्षित करने के लिए लेखाचित्ऱ में जोड़ा गया है जो निकास ब्लॉक सभी ब्लॉकों को पोस्टडोमिनेट करता है। इसे कभी भी पार नहीं किया जा सकता है।

लूप प्रबंधन

लूप हेडर (कभी-कभी लूप का प्रवेश बिंदु कहा जाता है) एक डोमिनेटर होता है जो लूप बनाने वाले बैक एज का लक्ष्य होता है। लूप हेडर लूप बॉडी में सभी ब्लॉकों पर हावी है। एक ब्लॉक एक से अधिक लूप के लिए लूप हेडर हो सकता है। एक लूप में कई प्रवेश बिंदु हो सकते हैं, जिस स्थिति में इसका कोई लूप हेडर नहीं होता है।

मान लीजिए ब्लॉक एम कई आने वाले किनारों के साथ एक प्रमुख है, उनमें से कुछ पीछे के किनारे हैं (इसलिए एम लूप हेडर है)। एम को दो ब्लॉक एम में तोड़ने के लिए कई अनुकूलन पासों के लिए यह फायदेमंद हैpre और एमloop. M और पिछले किनारों की सामग्री को M में ले जाया जाता हैloop, शेष किनारों को M में इंगित करने के लिए ले जाया जाता हैpre, और एम से एक नया किनाराpre एमloop डाला जाता है (ताकि Mpre M का तत्काल प्रभावी हैloop). शुरुआत में, एमpre खाली होगा, लेकिन लूप-इनवेरिएंट कोड मोशन जैसे पास इसे पॉप्युलेट कर सकता है। एमpre लूप प्री-हेडर कहा जाता है, और Mloop लूप हेडर होगा।

न्यूनीकरण

एक कम करने योग्य सीएफजी किनारों के साथ एक है जिसे दो अलग-अलग सेटों में विभाजित किया जा सकता है: आगे के किनारे और पीछे के किनारे, जैसे कि:[5]

  • आगे के किनारे प्रवेश नोड से पहुंचने योग्य सभी नोड्स के साथ एक निर्देशित चक्रीय लेखाचित्र बनाते हैं।
  • सभी बैक किनारों (ए, बी), नोड बी डोमिनेटर (लेखाचित्र सिद्धांत) नोड ए के लिए।

संरचित प्रोग्रामिंग भाषाओं को अक्सर इस तरह डिज़ाइन किया जाता है कि उनके द्वारा उत्पादित सभी CFG कम करने योग्य होते हैं, और सामान्य संरचित प्रोग्रामिंग स्टेटमेंट जैसे IF, FOR, WHILE, BREAK, और CONTINUE कम करने योग्य लेखाचित्र उत्पन्न करते हैं। अलघुकरणीय रेखांकन तैयार करने के लिए GOTO जैसे कथनों की आवश्यकता होती है। इरेड्यूसिबल लेखाचित्र कुछ कंपाइलर ऑप्टिमाइज़ेशन द्वारा भी तैयार किए जा सकते हैं।

लूप जुड़ाव

सीएफजी की लूप कनेक्टिविटी को सीएफजी के दिए गए डेप्थ-फर्स्ट सर्च ट्री (डीएफएसटी) के संबंध में परिभाषित किया गया है। इस DFST को स्टार्ट नोड पर रूट किया जाना चाहिए और CFG के प्रत्येक नोड को कवर करना चाहिए।

CFG में किनारे जो एक नोड से अपने DFST पूर्वज (स्वयं सहित) तक चलते हैं, उन्हें बैक एज कहा जाता है।

लूप कनेक्टिविटी CFG के किसी भी चक्र-मुक्त पथ में पाए जाने वाले बैक एज की सबसे बड़ी संख्या है। कम करने योग्य सीएफजी में, लूप जुड़ाव चुने गए डीएफएसटी से स्वतंत्र होता है।[6][7] डेटा-प्रवाह विश्लेषण की समय जटिलता के कारण के लिए लूप कनेक्टिविटी का उपयोग किया गया है।[6]


अंतर-प्रक्रियात्मक नियंत्रण प्रवाह लेखाचित्र

जबकि नियंत्रण प्रवाह लेखाचित्ऱ एकल प्रक्रिया के नियंत्रण प्रवाह का प्रतिनिधित्व करते हैं, अंतर-प्रक्रियात्मक नियंत्रण प्रवाह लेखाचित्ऱ पूरे कार्यक्रमों के नियंत्रण प्रवाह का प्रतिनिधित्व करते हैं।[8]


यह भी देखें

संदर्भ

  1. ↑ Frances E. Allen (July 1970). "Control flow analysis". SIGPLAN Notices. 5 (7): 1–19. doi:10.1145/390013.808479.
  2. ↑ Reese T. Prosser (1959). "Applications of Boolean matrices to the analysis of flow diagrams". Papers presented at the December 1–3, 1959, eastern joint IRE-AIEE-ACM computer conference. pp. 133–138.
  3. ↑ Yousefi, Javad (2015). "Masking wrong-successor Control Flow Errors employing data redundancy". 2015 5th International Conference on Computer and Knowledge Engineering (ICCKE). IEEE. pp. 201–205. doi:10.1109/ICCKE.2015.7365827. ISBN 978-1-4673-9280-8.
  4. ↑ 4.0 4.1 Peri L. Tarr; Alexander L. Wolf (2011). Engineering of Software: The Continuing Contributions of Leon J. Osterweil. Springer Science & Business Media. p. 58. ISBN 978-3-642-19823-6.
  5. ↑ "Archived copy" (PDF). Archived from the original (PDF) on 2020-08-01. Retrieved 2018-03-24.{{cite web}}: CS1 maint: archived copy as title (link)
  6. ↑ 6.0 6.1 Kam, John B.; Ullman, Jeffrey D. (1976-01-01). "Global Data Flow Analysis and Iterative Algorithms". Journal of the ACM. 23 (1): 158–171. doi:10.1145/321921.321938. ISSN 0004-5411. S2CID 162375.
  7. ↑ Offner, Carl. "Notes on Graph Algorithms Used in Optimizing Compilers" (PDF). Archived (PDF) from the original on 2008-07-25. Retrieved 13 April 2018.
  8. ↑ "Control Flow Analysis" (PDF). 2016. Archived (PDF) from the original on 2016-12-19.


बाहरी संबंध

Wikimedia Commons has media related to [[commons:Category:नियंत्रण-प्रवाह ग्राफ|नियंत्रण-प्रवाह ग्राफ]].
Examples
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=नियंत्रण-प्रवाह_ग्राफ&oldid=98448’