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

From Vigyanwiki
No edit summary
No edit summary
 
(5 intermediate revisions by 4 users not shown)
Line 1: Line 1:
{{Short description|Graphical representation of a computer program or algorithm}}
{{Short description|Graphical representation of a computer program or algorithm}}[[File:Some types of control flow graphs.svg|thumb|कुछ सीएफजी उदाहरण:<br />(a) अगर-तब-या<br />(b) एक वाहिल लूप<br />(c) दो निकासों वाला एक प्राकृतिक लूप, उदा. वाहिल इफ...बीच में ब्रेक के साथ; गैर-संरचित लेकिन कम करने योग्य<br />(d) एक अलघुकरणीय सीएफजी : एक लूप जिसमें दो प्रवेश बिंदु होते हैं, उदा. वाहिल और फॉर लूप मैं जाने के लिए ]]
{{multiple issues|
[[File:Rust_MIR_CFG.svg|thumb|कोडेन करने के लिए पुराने अनुभाषक(कंपाइलर) द्वारा उपयोग किया जाने वाला एक नियंत्रण प्रवाह लेखाचित्र।]][[कंप्यूटर विज्ञान]] में, एक नियंत्रण-प्रवाह लेखाचित्र(सीएफजी) एक [[चित्रण]] है, जो [[ग्राफ (असतत गणित)|लेखाचित्र(ग्राफ)]] अंकन का उपयोग करते हुए, उन सभी रास्तों का है, जो इसके [[निष्पादन (कंप्यूटिंग)]] के दौरान एक [[कंप्यूटर प्रोग्राम]] के माध्यम से हो सकते हैं। नियंत्रण-प्रवाह लेखाचित्र की खोज फ्रांसिस ई. एलन ने की थी,<ref>{{cite journal
{{More citations needed|date=January 2009}}
{{expert needed|Computer science|reason=many bad/unclear definitions and dubious claims.|date=February 2015}}
}}
 
[[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
| author = Frances E. Allen
| author = Frances E. Allen
| title = Control flow analysis
| title = Control flow analysis
Line 26: Line 20:


== परिभाषा ==
== परिभाषा ==
एक नियंत्रण-प्रवाह लेखाचित्र में लेखाचित्र में प्रत्येक बिंदु एक [[बुनियादी ब्लॉक|बुनियादी ढांचे]] का प्रतिनिधित्व करता है, यानी बिना किसी विषयांतर या [[कूद लक्ष्य (कंप्यूटिंग)|लक्ष्य]] के सरल रेखीय कोड का अंश; विषयांतर लक्ष्य एक ढांचा शुरू करते हैं, और विषयांतर एक ढांचे को समाप्त करता हैं। निर्देशित किनारों का उपयोग नियंत्रण प्रवाह में विषयांतर का प्रतिनिधित्व करने के लिए किया जाता है। अधिकांश प्रस्तुतियों में, दो विशेष रूप से निर्दिष्ट ढांचे होते हैं: प्रविष्टि ढांचा, जिसके माध्यम से प्रवाह लेखाचित्र में नियंत्रण प्रवेश करता है, और निकास ढांचा, जिसके माध्यम से सभी नियंत्रण प्रवाह निकल जाते हैं।<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>
: [[outdegree]](A) > 1 or indegree(B) > 1 (or both).<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 41: Line 44:
1: (A) if t0 mod 2 == 0
1: (A) if t0 mod 2 == 0


2: (B)   print t0 + " is even."
2: (B) print t0 + " is even."


3: (B)   goto 5
3: (B) goto 5


4: (C) print t0 + " is odd."
4: (C) print t0 + " is odd."
Line 73: Line 76:
इसी तरह, तत्काल बाद में हावी होने की एक धारणा है, जो तत्काल हावी होने के समान है।
इसी तरह, तत्काल बाद में हावी होने की एक धारणा है, जो तत्काल हावी होने के समान है।


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


एक बाद में हावी पेड़ प्रभावी पेड़ के अनुरूप होता है। यह पेड़ निकास ढांचे ब्लॉक पर जड़ जमाए हुए है।
एक बाद में हावी पेड़ प्रभावी पेड़ के अनुरूप होता है। यह पेड़ निकास ढांचे ब्लॉक पर जड़ जमाए हुए है।
Line 79: Line 82:
== विशेष किनारा ==
== विशेष किनारा ==


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


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


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


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


== लूप प्रबंधन ==
== लूप प्रबंधन ==


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


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


== न्यूनीकरण ==
== न्यूनीकरण ==
Line 97: Line 100:
एक कम करने योग्य सीएफजी किनारों के साथ एक है जिसे दो अलग-अलग सेटों में विभाजित किया जा सकता है: आगे के किनारे और पीछे के किनारे, जैसे कि:<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]] जैसे कथनों की आवश्यकता होती है। इरेड्यूसिबल लेखाचित्र कुछ कंपाइलर ऑप्टिमाइज़ेशन द्वारा भी तैयार किए जा सकते हैं।
[[संरचित प्रोग्रामिंग]] भाषाओं को अक्सर इस तरह अभिकल्पित किया जाता है कि उनके द्वारा उत्पादित सभी सीएफजी कम करने योग्य होते हैं, और सामान्य संरचित प्रोग्रामिंग वर्णन जैसे इफ, फॉर, वाहिल, ब्रेक, और कंटिन्यू कम करने योग्य लेखाचित्र उत्पन्न करते हैं। अलघुकरणीय रेखांकन तैयार करने के लिए [[GOTO]] जैसे कथनों की आवश्यकता होती है। अलघुकरणीय लेखाचित्र कुछ कंपाइलर अनुकूलीकरण द्वारा भी तैयार किए जा सकते हैं।


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


CFG में किनारे जो एक नोड से अपने DFST पूर्वज (स्वयं सहित) तक चलते हैं, उन्हें बैक एज कहा जाता है।
सीएफजी में किनारे जो एक नोड से अपने सीएफजी पूर्वज (स्वयं सहित) तक चलते हैं, उन्हें पिछला किनारा कहा जाता है।
 
लूप शृंखला सीएफजी के किसी भी चक्र-मुक्त पथ में पाए जाने वाले पिछले किनारे की सबसे बड़ी संख्या है। कम करने योग्य सीएफजी में, लूप जुड़ाव चुने गए डीएफएसटी से स्वतंत्र होता है।<ref name=":0">{{Cite journal|last1=Kam|first1=John B.|last2=Ullman|first2=Jeffrey D.|date=1976-01-01|title=Global Data Flow Analysis and Iterative Algorithms|journal=Journal of the ACM|volume=23|issue=1|pages=158–171|doi=10.1145/321921.321938|s2cid=162375 |issn=0004-5411}}</ref><ref>{{Cite web|url=https://www.cs.umb.edu/~offner/files/flow_graph.pdf |archive-url=https://web.archive.org/web/20080725053222/http://www.cs.umb.edu/~offner/files/flow_graph.pdf |archive-date=2008-07-25 |url-status=live|title=Notes on Graph Algorithms Used in Optimizing Compilers|last=Offner|first=Carl|access-date=13 April 2018}}</ref>
 
डेटा-प्रवाह विश्लेषण की समय जटिलता के कारण के लिए लूप शृंखला का उपयोग किया गया है।<ref name=":0" />


लूप कनेक्टिविटी CFG के किसी भी चक्र-मुक्त पथ में पाए जाने वाले बैक एज की सबसे बड़ी संख्या है। कम करने योग्य सीएफजी में, लूप जुड़ाव चुने गए डीएफएसटी से स्वतंत्र होता है।<ref name=":0">{{Cite journal|last1=Kam|first1=John B.|last2=Ullman|first2=Jeffrey D.|date=1976-01-01|title=Global Data Flow Analysis and Iterative Algorithms|journal=Journal of the ACM|volume=23|issue=1|pages=158–171|doi=10.1145/321921.321938|s2cid=162375 |issn=0004-5411}}</ref><ref>{{Cite web|url=https://www.cs.umb.edu/~offner/files/flow_graph.pdf |archive-url=https://web.archive.org/web/20080725053222/http://www.cs.umb.edu/~offner/files/flow_graph.pdf |archive-date=2008-07-25 |url-status=live|title=Notes on Graph Algorithms Used in Optimizing Compilers|last=Offner|first=Carl|access-date=13 April 2018}}</ref>
डेटा-प्रवाह विश्लेषण की समय जटिलता के कारण के लिए लूप कनेक्टिविटी का उपयोग किया गया है।<ref name=":0" />




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


जबकि नियंत्रण प्रवाह लेखाचित्ऱ एकल प्रक्रिया के नियंत्रण प्रवाह का प्रतिनिधित्व करते हैं, अंतर-प्रक्रियात्मक नियंत्रण प्रवाह लेखाचित्ऱ पूरे कार्यक्रमों के नियंत्रण प्रवाह का प्रतिनिधित्व करते हैं।<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 133: Line 138:


==बाहरी संबंध==
==बाहरी संबंध==
{{Commons category}}
*[https://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15745-s02/public/doc/cfg.html The Machine-SUIF Control Flow Graph Library]
*[https://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15745-s02/public/doc/cfg.html The Machine-SUIF Control Flow Graph Library]
*[https://gcc.gnu.org/onlinedocs/gccint/Control-Flow.html GNU Compiler Collection Internals]
*[https://gcc.gnu.org/onlinedocs/gccint/Control-Flow.html GNU Compiler Collection Internals]
Line 140: Line 144:
;Examples
;Examples
*[http://compilers.cs.ucla.edu/avrora/cfg.html Avrora – Control-Flow Graph Tool]
*[http://compilers.cs.ucla.edu/avrora/cfg.html Avrora – Control-Flow Graph Tool]
[[Category: संकलक निर्माण]] [[Category: नियंत्रण-प्रवाह विश्लेषण|*]] [[Category: एप्लिकेशन-विशिष्ट रेखांकन]] [[Category: मॉडलिंग भाषाएँ]]


[[Category: Machine Translated Page]]
[[Category:Articles with hatnote templates targeting a nonexistent page]]
[[Category:CS1 maint]]
[[Category:Created On 17/02/2023]]
[[Category:Created On 17/02/2023]]
[[Category:Lua-based templates]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Short description with empty Wikidata description]]
[[Category:Template documentation pages|Short description/doc]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates that add a tracking category]]
[[Category:Templates that generate short descriptions]]
[[Category:Templates using TemplateData]]
[[Category:एप्लिकेशन-विशिष्ट रेखांकन]]
[[Category:नियंत्रण-प्रवाह विश्लेषण|*]]
[[Category:मॉडलिंग भाषाएँ]]
[[Category:संकलक निर्माण]]

Latest revision as of 16:32, 2 March 2023

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

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

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

परिभाषा

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

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

outdegree(A) > 1 or indegree(B) > 1 (or both).[4]

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







उदाहरण

कोड के निम्नलिखित खंड पर विचार करें:

0: (A) t0 = read_num

1: (A) if t0 mod 2 == 0

2: (B) print t0 + " is even."

3: (B) goto 5

4: (C) print t0 + " is odd."

5: (D) end program

उपरोक्त में, हमारे पास 4 मूल खंड हैं: ए 0 से 1 तक, बी 2 से 3 तक, सी 4 पर और डी 5 पर। विशेष रूप से, इस मामले में, ए "प्रवेश खंड" है, डी "निकास खंड" है और पंक्ति 4 और 5 लक्ष्य हैं। इस खंड के लिए एक लेखाचित्र में ए से बी, ए से सी, बी से डी और सी से डी के किनारे हैं।

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

Main article: अभिगम्यता

गम्यता एक लेखाचित्र गुण धर्म है जो अनुकूलीकरण में उपयोगी है।

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

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

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

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

Main article: प्रभावी(लेखाचित्र सिद्धांत)

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

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

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

इसी तरह, तत्काल बाद में हावी होने की एक धारणा है, जो तत्काल हावी होने के समान है।

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

एक बाद में हावी पेड़ प्रभावी पेड़ के अनुरूप होता है। यह पेड़ निकास ढांचे ब्लॉक पर जड़ जमाए हुए है।

विशेष किनारा

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

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

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

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

लूप प्रबंधन

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

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

न्यूनीकरण

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

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

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

लूप जुड़ाव

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

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

लूप शृंखला सीएफजी के किसी भी चक्र-मुक्त पथ में पाए जाने वाले पिछले किनारे की सबसे बड़ी संख्या है। कम करने योग्य सीएफजी में, लूप जुड़ाव चुने गए डीएफएसटी से स्वतंत्र होता है।[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.


बाहरी संबंध

Examples
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=नियंत्रण-प्रवाह_ग्राफ&oldid=99285’