नियंत्रण-प्रवाह ग्राफ
 | This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages)
(Learn how and when to remove this template message)
|
कंप्यूटर विज्ञान में, एक नियंत्रण-प्रवाह लेखाचित्र(सीएफजी) एक चित्रण है, जो लेखाचित्र(ग्राफ) अंकन का उपयोग करते हुए, उन सभी रास्तों का है, जो इसके निष्पादन (कंप्यूटिंग) के दौरान एक कंप्यूटर प्रोग्राम के माध्यम से हो सकते हैं। नियंत्रण-प्रवाह लेखाचित्र की खोज फ्रांसिस ई. एलन ने की थी,[1] जिन्होंने ध्यान दिया कि रीज़ टी. प्रॉसेर ने पहले प्रवाह विश्लेषण के लिए बूलियन संबद्धता मैट्रिसेस का उपयोग किया था।[2]
सीएफजी कई संकलक अनुकूलीकरण और स्थिर कोड विश्लेषण टूल्स के लिए जरूरी है।
परिभाषा
एक नियंत्रण-प्रवाह लेखाचित्र में लेखाचित्र में प्रत्येक बिंदु एक बुनियादी ढांचे का प्रतिनिधित्व करता है, यानी बिना किसी विषयांतर या लक्ष्य के सरल रेखीय कोड का अंश; विषयांतर लक्ष्य एक ढांचा शुरू करते हैं, और विषयांतर एक ढांचे को समाप्त करता हैं। निर्देशित किनारों का उपयोग नियंत्रण प्रवाह में विषयांतर का प्रतिनिधित्व करने के लिए किया जाता है। अधिकांश प्रस्तुतियों में, दो विशेष रूप से निर्दिष्ट ढांचे होते हैं: प्रविष्टि ढांचा, जिसके माध्यम से प्रवाह लेखाचित्र में नियंत्रण प्रवेश करता है, और निकास ढांचा, जिसके माध्यम से सभी नियंत्रण प्रवाह निकल जाते हैं।[3]
इसकी निर्माण प्रक्रिया के कारण, एक सीएफजी में, प्रत्येक किनारे ए → बी में संपत्ति है:
- आगे की डिग्री (ए)> 1 या अंतःकोटि(बी)> 1 (या दोनों)।[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 लक्ष्य हैं। इस खंड के लिए एक लेखाचित्र में ए से बी, ए से सी, बी से डी और सी से डी के किनारे हैं।
पहुंच योग्यता
गम्यता एक लेखाचित्र गुण धर्म है जो अनुकूलीकरण में उपयोगी है।
यदि उपलेखाचित्र प्रविष्टि ढांचे वाले उपलेखाचित्र से जुड़ा नहीं है, तो वह उपलेखाचित्र किसी भी निष्पादन के दौरान पहुंच योग्य नहीं है, और इसलिए पहुंच योग्य कोड नहीं है; सामान्य परिस्थितियों में इसे सुरक्षित रूप से हटाया जा सकता है।
यदि प्रविष्टि ढांचे से निकास ढांचा अगम्य है, तो एक अनंत लूप मौजूद हो सकता है। सभी अनंत लूपों का पता नहीं लगाया जा सकता है, हॉल्टिंग समस्या देखें। वहां पर रोक लगाने का आदेश भी हो सकता है।
अगम्य कोड और अनंत लूप तब भी संभव हैं जब प्रोग्रामर उन्हें स्पष्ट रूप से कोड नहीं करता है: निरंतर प्रचार और निरंतर वलन के बाद जंप थ्रेडिंग जैसे अनुकूलन कई बुनियादी ढांचों को एक में ढहा सकते हैं, जिससे किनारों को सीएफजी से हटाया जा सकता है, आदि., इस प्रकार संभवतः लेखाचित्र के हिस्सों को अलग करता है।
वर्चस्व संबंध
ए ढांचा एम एक ढांचे एन पर हावी हो जाता है यदि ढांचा एन तक पहुंचने वाले प्रत्येक पथ को ढांचा एम से गुजरना पड़ता है। प्रवेश ढांचा सभी ढांचों पर हावी है।
विपरीत दिशा में, ढांचा एम ढांचा एन पर बाद में हावी होता है यदि एन से बाहर निकलने के लिए हर पथ को ढांचा एम से गुजरना पड़ता है। निकास ढांचे सभी ढांचों पर बाद में हावी होता है।
ऐसा कहा जाता है कि यदि एम, एन पर हावी है तो एक ढांचा एम तुरंत ढांचा एन पर हावी हो जाता है, और कोई हस्तक्षेप करने वाला ढांचा पी नहीं है जैसे कि एम, पी पर हावी हो और पी एन पर हावी हो। दूसरे शब्दों में, एन में प्रवेश से सभी रास्तों पर एम अंतिम प्रभुत्व है। प्रत्येक ढांचे में एक अद्वितीय तत्काल प्रभुत्व होता है।
इसी तरह, तत्काल बाद में हावी होने की एक धारणा है, जो तत्काल हावी होने के समान है।
द डोमिनेटर (लेखाचित्र थ्योरी) एक सहायक डेटा संरचना है जो प्रभावी संबंधों को दर्शाती है। ढांचा एम से ढांचा एन तक एक चाप है यदि एम एन का तत्काल प्रभुत्व है। यह लेखाचित्र एक पेड़ है, क्योंकि प्रत्येक ढांचे में एक अद्वितीय तत्काल प्रभुत्व है। इस पेड़ की जड़ें प्रविष्टि ढांचे में हैं। प्रभावी पेड़ की गणना लेंगौएर-टारजन के कलन विधि का उपयोग करके कुशलतापूर्वक की जा सकती है।
एक बाद में हावी पेड़ प्रभावी पेड़ के अनुरूप होता है। यह पेड़ निकास ढांचे ब्लॉक पर जड़ जमाए हुए है।
विशेष किनारा
एक बैक एज एक ऐसा किनारा है जो एक ब्लॉक को इंगित करता है जो लेखाचित्र के गहराई-पहले (गहराई-पहली खोज) ट्रैवर्सल के दौरान पहले ही मिल चुका है। पीछे के किनारे लूप के विशिष्ट हैं।
एक महत्वपूर्ण किनारा एक किनारा है जो न तो अपने स्रोत ब्लॉक को छोड़ने वाला एकमात्र किनारा है और न ही अपने गंतव्य ब्लॉक में प्रवेश करने वाला एकमात्र किनारा है। इन किनारों को विभाजित किया जाना चाहिए: किसी अन्य किनारों को प्रभावित किए बिना किनारे पर संगणना सम्मिलित करने के लिए किनारे के बीच में एक नया ब्लॉक बनाया जाना चाहिए।
एक असामान्य किनारा एक किनारा है जिसका गंतव्य अज्ञात है। अपवाद हैंडलिंग निर्माण उन्हें उत्पन्न कर सकते हैं। ये किनारे अनुकूलन को बाधित करते हैं।
एक असंभव बढ़त (एक नकली बढ़त के रूप में भी जाना जाता है) एक किनारा है जिसे पूरी तरह से उस संपत्ति को संरक्षित करने के लिए लेखाचित्ऱ में जोड़ा गया है जो निकास ब्लॉक सभी ब्लॉकों को पोस्टडोमिनेट करता है। इसे कभी भी पार नहीं किया जा सकता है।
लूप प्रबंधन
लूप हेडर (कभी-कभी लूप का प्रवेश बिंदु कहा जाता है) एक डोमिनेटर होता है जो लूप बनाने वाले बैक एज का लक्ष्य होता है। लूप हेडर लूप बॉडी में सभी ब्लॉकों पर हावी है। एक ब्लॉक एक से अधिक लूप के लिए लूप हेडर हो सकता है। एक लूप में कई प्रवेश बिंदु हो सकते हैं, जिस स्थिति में इसका कोई लूप हेडर नहीं होता है।
मान लीजिए ब्लॉक एम कई आने वाले किनारों के साथ एक प्रमुख है, उनमें से कुछ पीछे के किनारे हैं (इसलिए एम लूप हेडर है)। एम को दो ब्लॉक एम में तोड़ने के लिए कई अनुकूलन पासों के लिए यह फायदेमंद है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]
यह भी देखें
- सार वाक्य रचना का पेड़
- फ़्लोचार्ट
- नियंत्रण-प्रवाह आरेख
- नियंत्रण-प्रवाह विश्लेषण
- डेटा प्रवाह विश्लेषण
- अंतराल (लेखाचित्र सिद्धांत)
- कार्यक्रम निर्भरता लेखाचित्र
- साइक्लोमेटिक कम्पलेक्सिटी
- स्टेटिक सिंगल असाइनमेंट
- संकलक निर्माण
- मध्यवर्ती प्रतिनिधित्व
संदर्भ
- ↑ Frances E. Allen (July 1970). "Control flow analysis". SIGPLAN Notices. 5 (7): 1–19. doi:10.1145/390013.808479.
- ↑ 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.
- ↑ 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.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.
- ↑ "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.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.
- ↑ Offner, Carl. "Notes on Graph Algorithms Used in Optimizing Compilers" (PDF). Archived (PDF) from the original on 2008-07-25. Retrieved 13 April 2018.
- ↑ "Control Flow Analysis" (PDF). 2016. Archived (PDF) from the original on 2016-12-19.
बाहरी संबंध
- The Machine-SUIF Control Flow Graph Library
- GNU Compiler Collection Internals
- Paper "Infrastructure for Profile Driven Optimizations in GCC Compiler" by Zdeněk Dvořák et al.
- Examples
