स्थानीय अनुकूलन व आँकड़ा-प्रवाह विश्लेषण

अनुकूलन वहाँ है जहाँ संकलक अनुवाद बंद कर तर्क आरंभ करता है, और तर्क का आकार सदा वही है: प्रत्येक प्रोग्राम-बिंदु पर एक तथ्य निकालें, फिर उससे किसी पुनर्लेखन को न्यायोचित करें। तथ्य आँकड़ा-प्रवाह विश्लेषण से आते हैं, और पाठ्यक्रम तीन नामित करता है, जो मिलकर विश्लेषण की दोनों दिशाएँ ढकते हैं। जीवंतता पश्चगामी विश्लेषण है: कोई चर किसी बिंदु पर जीवित है यदि वहाँ से कोई पथ उसे लिखने से पूर्व पढ़े, और अतः सूचना प्रोग्राम के अंत से आरंभ की ओर बहती है। वही एक तथ्य दो अनुकूलन अनुमत करता है — जो मान जीवित नहीं उसे रजिस्टर में रखना आवश्यक नहीं, और ऐसे चर को निर्दिष्टीकरण जो उसके पश्चात् कभी जीवित न हो वह मृत कोड है और सीधे हटाया जा सकता है। उपलब्ध व्यंजक, जो सामान्य उप-व्यंजक उन्मूलन को न्यायोचित करते हैं, अग्रगामी विश्लेषण है: कोई व्यंजक किसी बिंदु पर उपलब्ध है यदि वह उस बिंदु तक पहुँचते प्रत्येक पथ पर निकाला गया हो और तब से उसका कोई प्रचालक न बदला हो। अचर प्रसार भी अग्रगामी है, चर को शब्दशः मान से बदलते हुए जहाँ विश्लेषण सिद्ध कर सके कि केवल एक मान पहुँचता है। दिशा सुनने से अधिक महत्व रखती है: वह तय करती है कि आप खंड के आरंभ में मिलते हैं या अंत में और आप प्रवेश की ओर पुनरावृत्त होते हैं या निर्गम की ओर, और उसे उलटा लेना ऐसा आत्मविश्वासी उत्तर देता है जो सरलतः गलत चीज़ के विषय में है। और एक सीमा शीघ्र स्थिर करने योग्य है: स्थानीय अनुकूलन एकल मूल खंड के भीतर काम करता है, जहाँ नियंत्रण-प्रवाह सीधी रेखा है और विश्लेषण एक चाल है; वैश्विक अनुकूलन नियंत्रण-प्रवाह ग्राफ पर काम करता है और उसे नियत-बिंदु पुनरावृत्ति चाहिए, क्योंकि चक्र का अर्थ है कि किसी खंड का निवेश उसके अपने निर्गम पर निर्भर है।

विश्लेषण किस दिशा में चलता है?

पाठ्यक्रम द्वारा नामित तीनों विश्लेषण, दिशा से
विश्लेषणदिशावह क्या अनुमत करता है
जीवंततापश्चगामी — निर्गम सेरजिस्टर आवंटन, तथा मृत-कोड उन्मूलन
उपलब्ध व्यंजकअग्रगामी — प्रवेश सेसामान्य उप-व्यंजक उन्मूलन
अचर प्रसारअग्रगामीचर को शब्दशः मान से बदलना; अचर संवलन
पहुँचती परिभाषाएँअग्रगामीप्रतिलिपि प्रसार, तथा use–def शृंखलाएँ
🎯 जीवंतता को पीछे की ओर क्यों चलना पड़ता है
जीवित की परिभाषा भविष्य के विषय में है: कोई चर किसी बिंदु पर जीवित है यदि वहाँ से आगे कोई पथ उसका वर्तमान मान अधिलिखित करने से पूर्व प्रयोग करे। अतः प्रत्येक बिंदु पर प्रश्न का उत्तर तभी दिया जा सकता है जब उसके उत्तरवर्तियों का उत्तर ज्ञात हो, और गणना निर्गम से आरंभ होकर पीछे चलनी चाहिए। जिस भी विश्लेषण की परिभाषा बाद के प्रयोग का उल्लेख करे वह उसी कारण पश्चगामी है। उपलब्ध व्यंजकों से विरोध करें, जिनकी परिभाषा भूत के विषय में है — यह यहाँ पहुँचते प्रत्येक पथ पर निकाला गया है क्या — अतः वे प्रवेश से आरंभ होकर आगे चलते हैं। व्यावहारिक कसौटी, जब आपको याद न रहे कि कौन कौन-सा है, यह है कि परिभाषा पढ़ें और पूछें कि वह "प्रयुक्त होगा" कहती है या "निकाला गया है": काल दिशा बता देता है, और उसे सही करना अधिकांश काम है।

एक जीवंतता गणना, चलाई गई

खंड a = b + c, d = a * 2, b = d + 1, e = a + b लें, और मानें कि निर्गम पर b व e जीवित हैं। ऊपर की ओर चलें, और प्रत्येक कथन पर परिभाषित होते चर को हटाएँ तथा प्रयुक्त होते चर जोड़ें:

जीवित समुच्चय, नीचे से ऊपर निकाले गए
कथनजीवित OUTजीवित IN
e = a + b{ b, e }{ a, b }
b = d + 1{ a, b }{ a, d }
d = a * 2{ a, d }{ a }
a = b + c{ a }{ b, c }
🧠 सम्पूर्ण खंड का जीवित-IN वह है जो उसे बाहर से चाहिए
अंतिम पंक्ति पढ़ें: खंड के शीर्ष पर केवल b व c जीवित हैं, जो कहता है कि खंड को अपने पूर्ववर्तियों से ठीक वही दो मान चाहिए और कुछ नहीं। शेष सब — a, d, e — भीतर उत्पन्न होते हैं। सम्पूर्ण गणना का उपयोगी निर्गम वही है, क्योंकि रजिस्टर आवंटक व अंतर-खंड विश्लेषण वस्तुतः उसी का उपभोग करते हैं। तालिका में दो विवरण ध्यान देने योग्य हैं। b, जीवित-OUT व जीवित-IN दोनों में आता है भिन्न कारणों से: वह शीर्ष पर पढ़ा जाता है और तीसरे कथन पर पुनर्परिभाषित होता है। तथा d केवल कथन 2 व 3 के बीच जीवित है — अत्यंत छोटा परिसर, और ठीक वही उसे स्मृति के बजाय रजिस्टर में रखने योग्य अच्छा अभ्यर्थी बनाता है। किसी चर का जीवित-परिसर, उसका विस्तार नहीं, यह तय करता है कि उसे संचयन चाहिए या नहीं।
⚠️ मृत कोड जीवंतता से परिभाषित है, अप्रयुक्त दिखने से नहीं
कोई निर्दिष्टीकरण मृत है जब वह जो चर लिखता है वह तुरंत पश्चात् जीवित न हो, और वह उस बिंदु से सभी पथों के विषय में कथन है, आसपास की पंक्तियों के विषय में नहीं। अतः कोई निर्दिष्टीकरण प्रयुक्त दिख सकता है — चर बाद में पुनः आता है — और फिर भी मृत हो, यदि उस बाद के प्रयोग तक प्रत्येक पथ पहले किसी अन्य निर्दिष्टीकरण से गुजरे। विलोमतः केवल एक विरल शाखा पर प्रयुक्त चर फिर भी जीवित है और उसका निर्दिष्टीकरण हटाया नहीं जा सकता। ऊपर के खंड में कुछ मृत नहीं: d कथन 3 पर पढ़ा जाता है और a कथन 2 व 4 पर। परंतु अंत में d = 7 जोड़ें और वह मृत हो जाता है, क्योंकि d खंड के जीवित-OUT समुच्चय में नहीं — जो केवल जीवंतता गणना से ज्ञात हो सकता है, और इसीलिए विश्लेषण अनुकूलन से पूर्व आता है, पश्चात् नहीं।

स्थानीय, वैश्विक, तथा चक्र पुनरावृत्ति क्यों बाध्य करते हैं

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

🎯 पुनरावृत्ति समाप्त क्यों होती है, तथा आरंभीकरण किस दिशा में
समुच्चय परिमित विश्व के उपसमुच्चय हैं — प्रोग्राम के चर, या व्यंजक — और प्रत्येक पुनरावृत्ति केवल एक दिशा में चलती है: may विश्लेषण हेतु एकदिष्ट रूप से बढ़ती, must हेतु एकदिष्ट रूप से घटती। परिमित जालक में एकदिष्ट अनुक्रम अनंत काल नहीं चल सकता, अतः पुनरावृत्ति नियत-बिंदु पर पहुँचती है। वह किस दिशा में चलती है यह आरंभीकरण तय करता है, और यहीं प्रश्न लोगों को पकड़ते हैं। जीवंतता "may" विश्लेषण है — जीवित यदि कोई पथ मान प्रयोग करे — अतः मिलन सम्मिलन है और समुच्चय रिक्त आरंभ होकर बढ़ते हैं। उपलब्ध व्यंजक "must" विश्लेषण है — उपलब्ध केवल यदि प्रत्येक पथ पर निकाला गया हो — अतः मिलन सर्वनिष्ठ है और आंतरिक समुच्चय पूर्ण आरंभ होकर घटते हैं। must-विश्लेषण को रिक्त आरंभ करना तुरंत नियत-बिंदु देता है और उत्तर तुच्छ रूप से गलत होता है, और वही पहचानने योग्य विफलता-विधि है: पुनरावृत्ति शीघ्रता से, कुछ नहीं पर अभिसरित हो जाती है।

मुख्य बिंदु

  • प्रत्येक अनुकूलन आँकड़ा-प्रवाह विश्लेषण से निकाला तथ्य तथा उससे अनुमत पुनर्लेखन है।
  • जीवंतता पश्चगामी है; उपलब्ध व्यंजक व अचर प्रसार अग्रगामी।
  • परिभाषा का काल पढ़ें: "प्रयुक्त होगा" पश्चगामी है, "निकाला गया है" अग्रगामी।
  • live-out {b,e} सहित a = b+c; d = a*2; b = d+1; e = a+b पर खंड का live-in {b, c} है।
  • कोई निर्दिष्टीकरण मृत है जब उसका लक्ष्य तुरंत पश्चात् जीवित न हो — सभी बाद के पथों के विषय में तथ्य।
  • किसी चर का जीवित-परिसर, उसका विस्तार नहीं, तय करता है कि उसे संचयन चाहिए या नहीं।
  • स्थानीय अनुकूलन मूल खंड में एक चाल है; वैश्विक को चक्रों के कारण नियत-बिंदु पुनरावृत्ति चाहिए।
  • may-विश्लेषण सम्मिलन से मिलता है व रिक्त आरंभ होता है; must-विश्लेषण सर्वनिष्ठ से व पूर्ण आरंभ होता है।

अभ्यास प्रश्न (8)

उत्तर खोलने से पहले प्रत्येक प्रश्न हल करें। हर व्याख्या सही विकल्प के साथ लुभावना गलत विकल्प भी बताती है, क्योंकि अंक वहीं जाते हैं।

  1. निर्गम पर b व e जीवित सहित खंड a = b + c; d = a * 2; b = d + 1; e = a + b हेतु, खंड के आरंभ पर जीवित चरों का समुच्चय है:

    1. { a, b, c }
    2. { b, c }
    3. { b, e }
    4. { a, d }
    उत्तर देखें

    उत्तर: B — { b, c }

    { b, c }। ऊपर की ओर चलें, प्रत्येक परिभाषित चर हटाते व प्रत्येक प्रयुक्त जोड़ते हुए। live-out { b, e } से: कथन 4 देता है { a, b }; कथन 3 देता है { a, d }; कथन 2 देता है { a }; कथन 1, a परिभाषित करता है व b तथा c प्रयोग करता है, जिससे { b, c }। वह समुच्चय सम्पूर्ण गणना का उपयोगी उत्पाद है — वह कहता है कि खंड को अपने पूर्ववर्तियों से ठीक b व c चाहिए, और वह a, d व e भीतर उत्पन्न करता है। विकल्प A गलत रूप से a को शीर्ष पर जीवित रखता है, पर कथन 1, a को परिभाषित करता है, अतः इस खंड से पूर्व a में जीवित कुछ भी अप्रासंगिक है। विकल्प C, live-out समुच्चय को live-in के रूप में देता है, जो सर्वाधिक सामान्य चूक है जब विश्लेषण की दिशा पहले स्थिर न की जाए।

  2. जीवंतता विश्लेषण पश्चगामी विश्लेषण है क्योंकि:

    1. वह पार्सिंग के पश्चात् निकाला जाता है
    2. किसी बिंदु पर जीवंतता उस बिंदु के पश्चात् जो होता है उस पर निर्भर है
    3. वह सर्वनिष्ठ को अपने मिलन संकारक के रूप में प्रयोग करता है
    4. रजिस्टर प्रोग्राम के अंत से आवंटित होते हैं
    उत्तर देखें

    उत्तर: B — किसी बिंदु पर जीवंतता उस बिंदु के पश्चात् जो होता है उस पर निर्भर है

    कोई चर किसी बिंदु पर जीवित है यदि वहाँ से आगे कोई पथ उसका वर्तमान मान अधिलिखित करने से पूर्व पढ़े — भविष्य के विषय में कथन — अतः प्रत्येक बिंदु पर उत्तर हेतु उसके उत्तरवर्तियों के उत्तर चाहिए, और गणना निर्गम से आरंभ होनी चाहिए। विकल्प C विशिष्टताओं में गलत है और सुधारने योग्य: जीवंतता may विश्लेषण है (जीवित यदि कोई पथ उसे प्रयोग करे), अतः उसका मिलन सम्मिलन है, और सर्वनिष्ठ से मिलने वाले उपलब्ध व्यंजक हैं। विकल्प A संकलक के चरण-क्रम को विश्लेषण की दिशा से भ्रमित करता है; बहुत से अग्रगामी विश्लेषण भी पार्सिंग के पश्चात् चलते हैं। विश्वसनीय कसौटी परिभाषा का काल है — "प्रयुक्त होगा" पश्चगामी है, "निकाला गया है" अग्रगामी।

  3. सामान्य उप-व्यंजक उन्मूलन किस विश्लेषण से न्यायोचित है?

    1. जीवंतता
    2. उपलब्ध व्यंजक
    3. पहुँचती परिभाषाएँ
    4. अचर प्रसार
    उत्तर देखें

    उत्तर: B — उपलब्ध व्यंजक

    उपलब्ध व्यंजक। b * c की पुनर्गणना को पूर्व-निकाले मान से बदलने हेतु आपको जानना होगा कि b * c इस बिंदु तक पहुँचते प्रत्येक पथ पर मूल्यांकित हुआ है और तब से न b न c को निर्दिष्ट किया गया — और उपलब्धता ठीक वही दावा करती है। जीवंतता भिन्न प्रश्न का उत्तर देती है, कि मान अभी चाहिए होगा या नहीं, और इसके बजाय मृत-कोड उन्मूलन तथा रजिस्टर आवंटन अनुमत करती है। परिभाषा में "प्रत्येक पथ" ही उपलब्धता को must विश्लेषण बनाता है, अतः उसका मिलन सर्वनिष्ठ है और उसके समुच्चय रिक्त के बजाय पूर्ण आरंभीकृत होते हैं — वह विवरण जो तय करता है कि नियत-बिंदु पुनरावृत्ति सही उत्तर देती है या तुरंत कुछ नहीं पर अभिसरित हो जाती है।

  4. निम्नलिखित में कौन अग्रगामी आँकड़ा-प्रवाह विश्लेषण हैं? (एक से अधिक सही हो सकते हैं।)

    1. उपलब्ध व्यंजक
    2. पहुँचती परिभाषाएँ
    3. अचर प्रसार
    4. जीवित चर विश्लेषण
    उत्तर देखें

    उत्तर: A — उपलब्ध व्यंजक; B — पहुँचती परिभाषाएँ; C — अचर प्रसार

    A, B व C। तीनों भूत के विषय में पूछते हैं — यह व्यंजक पहले ही निकाला गया है क्या, कौन-सी परिभाषाएँ पहले ही यहाँ पहुँच चुकी हैं, कौन-सा मान पहले ही स्थापित हो चुका है — अतः सूचना प्रवेश से निर्गम की ओर बहती है। D पश्चगामी है: जीवंतता पूछती है कि मान बाद में प्रयुक्त होगा या नहीं, अतः वह निर्गम से पीछे बहती है। दूसरा अक्ष स्वतंत्र है और पृथक् रखने योग्य: उपलब्ध व्यंजक must विश्लेषण है (सर्वनिष्ठ, पूर्ण आरंभीकरण) जबकि पहुँचती परिभाषाएँ may विश्लेषण (सम्मिलन, रिक्त आरंभीकरण), चाहे दोनों अग्रगामी हों। दिशा व मिलन संकारक दो पृथक् चुनाव हैं, और प्रश्न किसी को भी जाँच सकता है।

  5. निर्दिष्टीकरण x = e मृत कोड है जब:

    1. e का कोई पार्श्व-प्रभाव न हो
    2. निर्दिष्टीकरण के तुरंत पश्चात् x जीवित न हो
    3. x प्रोग्राम-पाठ में पुनः कभी न आए
    4. e अचर हो
    उत्तर देखें

    उत्तर: B — निर्दिष्टीकरण के तुरंत पश्चात् x जीवित न हो

    तुरंत पश्चात् x जीवित न हो। वही परिभाषा है, और वह उस बिंदु से सभी अग्रगामी पथों के विषय में कथन है, आसपास के पाठ के विषय में नहीं — और ठीक इसीलिए विकल्प C तुल्य नहीं। x बाद में पुनः आ सकता है और निर्दिष्टीकरण फिर भी मृत हो, यदि उस बाद के प्रयोग तक प्रत्येक पथ पहले x को किसी अन्य निर्दिष्टीकरण से गुजरे; और विलोमतः किसी विरल शाखा पर एक प्रयोग x को जीवित रखता है। विकल्प A कथन को वस्तुतः हटाने हेतु आवश्यक पार्श्व शर्त है, मृतता की कसौटी नहीं: यदि e पार्श्व-प्रभाव वाले फलन को बुलाए, तो मान मृत है पर कथन सरलतः हटाया नहीं जा सकता। "मान अप्रयुक्त है" को "कथन हटाने योग्य है" से पृथक् करना यहाँ व्यावहारिक विषय-वस्तु है।

  6. वैश्विक आँकड़ा-प्रवाह विश्लेषण को पुनरावृत्तीय नियत-बिंदु गणना चाहिए, जबकि मूल खंड के भीतर विश्लेषण को नहीं, क्योंकि:

    1. मूल खंड छोटे होते हैं
    2. चक्र किसी खंड के निवेश को उसके अपने निर्गम पर निर्भर बना देता है
    3. वैश्विक विश्लेषण अधिक चर प्रयोग करता है
    4. मूल खंडों में कोई निर्दिष्टीकरण नहीं होता
    उत्तर देखें

    उत्तर: B — चक्र किसी खंड के निवेश को उसके अपने निर्गम पर निर्भर बना देता है

    मूल खंड सीधी-रेखा कोड है, अतः सही दिशा में एक चाल प्रत्येक तथ्य ठीक एक बार निकाल देती है। चक्र वाला नियंत्रण-प्रवाह ग्राफ वर्तुल है: चक्र-निकाय में प्रवेश करते तथ्य उससे निकलते तथ्यों पर निर्भर हैं, जो बदले में प्रवेश करते तथ्यों पर। निकलने का एकमात्र मार्ग नियत-बिंदु तक पुनरावृत्ति है — और वह समाप्त होती है क्योंकि समुच्चय परिमित विश्व के उपसमुच्चय हैं और प्रत्येक चरण एकदिष्ट रूप से एक दिशा में चलता है। विकल्प A सत्य व अप्रासंगिक है: पुनरावृत्ति लंबाई नहीं, वर्तुलता बाध्य करती है, और अत्यंत लंबे सीधी-रेखा खंड को भी केवल एक पास चाहिए। उस एकदिष्ट गति की दिशा ही आरंभीकरण तय करती है — may विश्लेषण हेतु रिक्त, must हेतु पूर्ण।

  7. उपलब्ध-व्यंजक विश्लेषण आंतरिक समुच्चयों को रिक्त समुच्चय के बजाय व्यंजकों के पूर्ण समुच्चय पर आरंभीकृत करता है क्योंकि:

    1. वह अग्रगामी विश्लेषण है
    2. वह must विश्लेषण है जिसका मिलन सर्वनिष्ठ है
    3. व्यंजक प्रायः अनेक होते हैं
    4. वह जीवंतता से पूर्व चलता है
    उत्तर देखें

    उत्तर: B — वह must विश्लेषण है जिसका मिलन सर्वनिष्ठ है

    उपलब्धता को व्यंजक का किसी बिंदु तक पहुँचते प्रत्येक पथ पर निकाला होना चाहिए, अतः समुच्चय सर्वनिष्ठ से संयोजित होते हैं और पुनरावृत्ति बढ़ने पर केवल घट सकते हैं। उन्हें रिक्त आरंभ करना प्रत्येक सर्वनिष्ठ को रिक्त बना देता, पुनरावृत्ति तुरंत रुक जाती, और विश्लेषण बताता कि कुछ कभी उपलब्ध नहीं — एक नियत-बिंदु, शीघ्र पहुँचा, और गलत। पूर्ण आरंभ करना सर्वनिष्ठों को केवल वही काटने देता है जो वस्तुतः अनुपलब्ध है। विकल्प A गलत अक्ष का सही गुण नामित करता है: दिशा व मिलन संकारक स्वतंत्र चुनाव हैं, और पहुँचती परिभाषाएँ अग्रगामी हैं जबकि सम्मिलन से मिलती व रिक्त आरंभीकृत होती हैं। "प्रत्येक पथ" बनाम "कोई पथ" हेतु परिभाषा पढ़ना ही आरंभीकरण तय करता है।

  8. निर्गम पर b व e जीवित सहित खंड a = b + c; d = a * 2; b = d + 1; e = a + b में d किस परिसर पर जीवित है?

    1. सम्पूर्ण खंड भर
    2. केवल कथन 2 व 3 के बीच
    3. कथन 2 से खंड के अंत तक
    4. वह कभी जीवित नहीं
    उत्तर देखें

    उत्तर: B — केवल कथन 2 व 3 के बीच

    केवल कथन 2 व 3 के बीच। d, कथन 2 पर परिभाषित होता है और कथन 3 पर पढ़ा जाता है, और वह किसी बाद के कथन में तथा live-out समुच्चय में नहीं आता — अतः उसका जीवित-परिसर वही एक अंतराल है। विकल्प C स्वाभाविक त्रुटि है, यह मानने से कि चर अपने विस्तार के अंत तक जीवित रहता है; जीवित-परिसर व विस्तार भिन्न चीज़ें हैं, और विश्लेषण का सम्पूर्ण मूल्य यह है कि वह पहला निकालता है। व्यावहारिक परिणाम यह है कि d को रजिस्टर में रखने योग्य उत्कृष्ट अभ्यर्थी है, क्योंकि उसका परिसर अधिक अतिव्यापित नहीं: दो चर एक रजिस्टर ठीक तब साझा कर सकते हैं जब उनके जीवित-परिसर असंयुक्त हों, और इसीलिए रजिस्टर आवंटन इन परिसरों के व्यवधान पर ग्राफ-रंगन समस्या है।