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

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

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

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

उद्देश्य

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

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

 int x = 0;    /* A */
 x = x + y;    /* B */
 /* 1, some uses of x */
 x = 35;       /* C */
 /* 2, some more uses of x */

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

 int x = 0;    /* A */
 x = x + y;    /* B */
 /* 1, some uses of x */
 int x2 = 35;  /* C */
 /* 2, some uses of x2 */

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

व्यवस्थापन

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

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

एक चर के लिए, जैसे 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(i)$, और अब कथन पर गणना के रूप में क्या देखा जा सकता है,:

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

डीफ़-यूज़-चेन के लिए कार्यान्वयन उदाहरण

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

/**
 * @param(a, b) The values used to calculate the divisor.
 * @return The greatest common divisor of a and b.
 */
int gcd(int a, int b) { 
    int c = a;
    int d = b; 
    if (c == 0)
        return d;
    while (d != 0) { 
        if (c > d)
            c = c - d;
        else
            d = d - c;
    } 
    return c; 
}

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

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

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

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

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

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

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

परिणाम होना चाहिए:

 [d, d=b, return d] 
 [d, d=b, while(d!=0)] 
 [d, d=b, if(c>d)] 
 [d, d=b, c=c-d] 
 [d, d=b, d=d-c]
 [d, d=d-c, while(d!=0)] 
 [d, d=d-c, if(c>d)] 
 [d, d=d-c, c=c-d] 
 [d, d=d-c, d=d-c]

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

उदाहरण के लिए: स्रोत कोड में पंक्ति 7 नीचे से पंक्ति 13 तक, d पुनर्परिभाषित / परिवर्तित नहीं किया गया है।

लाइन 14 पर, d पुनर्परिभाषित किया जा सकता है। यही कारण है कि आपको इस राइट एक्सेस को फिर से जोड़ना होगा d सभी संभावित पठन पहुंचों के साथ जिन तक पहुंचा जा सकता है।

इस स्थिति में, केवल पंक्ति 10 के बाद का कोड प्रासंगिक है। लाइन 7, उदाहरण के लिए, फिर से नहीं पहुँचा जा सकता। आपकी समझ के लिए, आप 2 अलग-अलग चरों की कल्पना कर सकते हैं

 [d1, d1=b, return d1] 
 [d1, d1=b, while(d1!=0)] 
 [d1, d1=b, if(c>d1)] 
 [d1, d1=b, c=c-d1] 
 [d1, d1=b, d1=d1-c]
 [d2, d2=d2-c, while(d2!=0)] 
 [d2, d2=d2-c, if(c>d2)] 
 [d2, d2=d2-c, c=c-d2] 
 [d2, d2=d2-c, d2=d2-c]

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

/**
 * @param(a, b) The values used to calculate the divisor.
 * @return The greatest common divisor of a and b.
 **/
int gcd(int a, int b) {
    int c = a;
    int d; 
    if (c == 0)
        return b;
    if (b != 0) {
        if (c > b) {
            c = c - b;
            d = b;
        }
        else
            d = b - c;
        while (d != 0) { 
            if (c > d)
                c = c - d;
            else
                d = d - c;
        }
    } 
    return c; 
}

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

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

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

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