उपयोग-परिभाषित श्रृंखला

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

यूडी चेन का प्रतिरूप एक डेफिनिशन-यूज चेन (डीयू चेन) है, जिसमें एक वेरिएबल की परिभाषा, डी, और सभी उपयोग, यू, उस परिभाषा से बिना किसी अन्य के पहुंच योग्य हैं। हस्तक्षेप करने वाली परिभाषाएँ।

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

उद्देश्य

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

कोड के निम्नलिखित स्निपेट पर विचार करें: <वाक्यविन्यास प्रकाश लैंग = सी>

इंट एक्स = 0; /* ए */
एक्स = एक्स + वाई; /* बी */
/* 1, x के कुछ उपयोग */
एक्स = 35; /* सी */
/* 2, x के कुछ और उपयोग */

</वाक्यविन्यास हाइलाइट>

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

<वाक्यविन्यास प्रकाश लैंग = सी>

इंट एक्स = 0; /* ए */
एक्स = एक्स + वाई; /* बी */
/* 1, x के कुछ उपयोग */
int x2 = 35; /* सी */
/* 2, x2 के कुछ उपयोग */

</वाक्यविन्यास हाइलाइट>

बंटवारे की प्रक्रिया x दो अलग-अलग वेरिएबल्स में लाइव रेंज विभाजन कहा जाता है। स्टेटिक सिंगल असाइनमेंट फॉर्म भी देखें।

सेटअप

बयानों की सूची बयानों के बीच एक मजबूत क्रम निर्धारित करती है।

• निम्नलिखित परिपाटियों का उपयोग करते हुए कथनों को लेबल किया गया है: $s(i)$, जहाँ i एक पूर्णांक है $[1,n]$; और n बुनियादी ब्लॉक में स्टेटमेंट्स की संख्या है
• वैरिएबल को इटैलिक में पहचाना जाता है (जैसे, v,u और t)
• प्रत्येक चर को संदर्भ या दायरे में एक परिभाषा माना जाता है। (स्थिर एकल असाइनमेंट फॉर्म में, यूज-डिफाइन चेन स्पष्ट हैं क्योंकि प्रत्येक चेन में एक ही तत्व होता है।)

एक चर के लिए, जैसे v, इसकी घोषणा की पहचान V (इटैलिक कैपिटल लेटर) के रूप में की जाती है, और संक्षेप में, इसकी घोषणा के रूप में पहचान की जाती है $s(0)$. सामान्य तौर पर, एक चर की घोषणा बाहरी दायरे में हो सकती है (उदाहरण के लिए, एक वैश्विक चर)।

एक चर की परिभाषा

जब एक चर, v, एक असाइनमेंट स्टेटमेंट के समीकरण के बाईं ओर और दाईं ओर होता है, जैसे कि $s(j)$, तब $s(j)$ v की एक परिभाषा है। प्रत्येक चर (v) की घोषणा (V) (या आरंभीकरण) द्वारा कम से कम एक परिभाषा है।

एक चर का प्रयोग

यदि चर, v, कथन के दाएँ पक्ष में है $s(j)$, एक बयान है, $s(i)$ मैं <जे और के साथ $\min(j-i)$, कि यह v की परिभाषा है और इसका उपयोग at है $s(j)$ (या, संक्षेप में, जब एक चर, v, एक कथन के दाएँ पक्ष पर है $s(j)$, तो v का कथन पर उपयोग है $s(j)$).

निष्पादन

कथनों की सूची के क्रमिक निष्पादन पर विचार करें, $s(i)$, और अब कथन पर गणना के रूप में क्या देखा जा सकता है, जे:

• बयान पर एक परिभाषा $s(i)$ i <j के साथ j पर 'जीवित' है, अगर इसका किसी कथन पर उपयोग होता है $s(k)$ के ≥ जे के साथ। बयान में जीवित परिभाषाओं का सेट i के रूप में दर्शाया गया है $A(i)$ और जीवित परिभाषाओं की संख्या के रूप में $|A(i)|$. ($A(i)$ एक सरल लेकिन शक्तिशाली अवधारणा है: अंतरिक्ष जटिलता सिद्धांत में सैद्धांतिक और व्यावहारिक परिणाम, पहुंच जटिलता (I/O जटिलता), रजिस्टर आवंटन और स्मृति स्थानीयता शोषण पर आधारित हैं $A(i)$.)
• बयान पर एक परिभाषा $s(i)$ पिछली सभी परिभाषाओं को मारता है ($s(k)$ k <i) के साथ समान चर के लिए।

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

<वाक्यविन्यास लैंग = सी लाइन> /**

* @param(a, b) विभाजक की गणना करने के लिए उपयोग किए जाने वाले मान।
* @return a और b का महत्तम समापवर्तक है।
*/

इंट जीसीडी (इंट ए, इंट बी) {

   इंट सी = ए;
   इंट डी = बी;
   अगर (सी == 0)
       वापसी घ;
   जबकि (डी! = 0) {
       अगर (सी> डी)
           सी = सी - डी;
       अन्य
           डी = डी - सी;
   }
   वापसी सी;

} </वाक्यविन्यास हाइलाइट>

वेरिएबल d के लिए सभी डीफ़-यूज़-चेन का पता लगाने के लिए, निम्न चरणों का पालन करें:

1. पहली बार वेरिएबल को परिभाषित करने के लिए खोजें (एक्सेस लिखें)।

   इस मामले में यह हैd=b(एल.7)

2. पहली बार वेरिएबल को पढ़ने के लिए खोजें।

   इस मामले में यह हैreturn d# इस जानकारी को निम्न शैली में लिखें: [उस चर का नाम जिसके लिए आप एक डीफ़-यूज़-चेन बना रहे हैं, कंक्रीट राइट एक्सेस, कंक्रीट रीड एक्सेस]

   इस मामले में यह है: [d, d=b, return d]

निम्नलिखित चरणों में इन चरणों को दोहराएं: प्रत्येक पढ़ने की पहुंच के साथ प्रत्येक लेखन पहुंच को संयोजित करें (लेकिन दूसरे तरीके से नहीं)।

परिणाम होना चाहिए: <वाक्यविन्यास लैंग = सी लाइन>

[डी, डी = बी, रिटर्न डी]
[डी, डी=बी, जबकि(डी!=0)]
[डी, डी = बी, अगर (सी> डी)]
[डी, डी=बी, सी=सी-डी]
[डी, डी=बी, डी=डी-सी]
[डी, डी = डी-सी, जबकि (डी! = 0)]
[डी, डी = डी-सी, अगर (सी> डी)]
[डी, डी=डी-सी, सी=सी-डी]
[डी, डी=डी-सी, डी=डी-सी]

</वाक्यविन्यास हाइलाइट> आपको ध्यान रखना होगा, यदि चर समय के अनुसार बदल जाता है।

उदाहरण के लिए: स्रोत कोड में पंक्ति 7 नीचे से पंक्ति 13 तक, d पुनर्परिभाषित / परिवर्तित नहीं किया गया है। लाइन 14 पर, d पुनर्परिभाषित किया जा सकता है। यही कारण है कि आपको इस राइट एक्सेस को फिर से जोड़ना होगा d सभी संभावित पठन पहुंचों के साथ जिन तक पहुंचा जा सकता है। इस स्थिति में, केवल पंक्ति 10 के बाद का कोड प्रासंगिक है। लाइन 7, उदाहरण के लिए, फिर से नहीं पहुँचा जा सकता। आपकी समझ के लिए, आप 2 अलग-अलग चरों की कल्पना कर सकते हैं d: <वाक्यविन्यास लैंग = सी लाइन>

[डी1, डी1=बी, रिटर्न डी1]
[डी 1, डी 1 = बी, जबकि (डी 1! = 0)]
[डी 1, डी 1 = बी, अगर (सी> डी 1)]
[डी1, डी1=बी, सी=सी-डी1]
[डी1, डी1=बी, डी1=डी1-सी]
[डी2, डी2=डी2-सी, जबकि (डी2!=0)]
[डी2, डी2=डी2-सी, अगर(सी>डी2)]
[डी2, डी2=डी2-सी, सी=सी-डी2]
[डी2, डी2=डी2-सी, डी2=डी2-सी]

</वाक्यविन्यास हाइलाइट>

नतीजतन, आपको ऐसा कुछ मिल सकता है। चर d1 द्वारा प्रतिस्थापित किया जाएगा b <वाक्यविन्यास लैंग = सी लाइन> /**

* @param(a, b) विभाजक की गणना करने के लिए उपयोग किए जाने वाले मान।
* @return a और b का महत्तम समापवर्तक है।
**/

इंट जीसीडी (इंट ए, इंट बी) {

   इंट सी = ए;
   इंट डी;
   अगर (सी == 0)
       वापसी बी;
   अगर (बी! = 0) {
       अगर (सी> बी) {
           सी = सी - बी;
           डी = बी;
       }
       अन्य
           डी = बी - सी;
       जबकि (डी! = 0) {
           अगर (सी> डी)
               सी = सी - डी;
           अन्य
               डी = डी - सी;
       }
   }
   वापसी सी;

} </वाक्यविन्यास हाइलाइट>

उपयोग-डीईएफ़ (या ud) श्रृंखला बनाने की विधि

1. कथन में परिभाषाएँ निर्धारित करें $s(0)$
2. प्रत्येक के लिए i में $[1,n]$, लाइव परिभाषाएँ खोजें जिनका उपयोग कथन में किया गया है $s(i)$
3. परिभाषाओं और उपयोगों के बीच संबंध बनाएं
4. स्टेटमेंट सेट करें $s(i)$, परिभाषा कथन के रूप में
5. पिछली परिभाषाओं को मारें

इस एल्गोरिथम के साथ, दो चीजें पूरी होती हैं:

1. एक निर्देशित विश्वकोश ग्राफ (DAG) चर उपयोगों और परिभाषाओं पर बनाया गया है। डीएजी असाइनमेंट कथनों के साथ-साथ आंशिक आदेश (इसलिए बयानों के बीच समानता) के बीच डेटा निर्भरता निर्दिष्ट करता है।
2. कब बयान $s(i)$ तक पहुँच गया है, तो लाइव वेरिएबल असाइनमेंट की एक सूची है। यदि केवल एक असाइनमेंट लाइव है, उदाहरण के लिए, निरंतर प्रसार का उपयोग किया जा सकता है।

श्रेणी:संकलक अनुकूलन श्रेणी:डेटा प्रवाह विश्लेषण