निर्भरता विश्लेषण

संकलक सिद्धांत में, निर्भरता विश्लेषण कथन/निर्देशों के मध्य निष्पादन-क्रम बाधाओं का उत्पादन करता है। विस्तीर्णता से, एक कथन S2 S1 पर आश्रित करता है यदि S1 को S2 से पहले निष्पादित किया जाना चाहिए। विस्तीर्णता से, निर्भरता के दो वर्ग हैं - नियंत्रण निर्भरता और डेटा निर्भरता।

निर्भरता विश्लेषण यह निर्धारित करता है कि कथनो को पुन: क्रमबद्ध या समानांतर करना सुरक्षित है या नहीं।

नियंत्रण निर्भरता

नियंत्रण निर्भरता एक ऐसी स्थिति है जिसमें एक प्रोग्राम निर्देश निष्पादित करता है यदि पूर्व निर्देश इस तरह से मूल्यांकन करते है जो इसके निष्पादन की अनुमति देते है।

एक कथन S2 S1 पर नियंत्रण निर्भर है (लिखित $S1\ \delta ^{c}\ S2$) अगर और केवल अगर S2 का निष्पादन सशर्त रूप से S1 द्वारा संरक्षित है। S2 नियंत्रण S1 पर निर्भर है अगर और केवल अगर $S1\in PDF(S2)$ जहां $PDF(S)$ कथन $S$ का पद प्रमुखता सीमांत है। निम्नलिखित ऐसी नियंत्रण निर्भरता का एक उदाहरण है:

S1       if x > 2 goto L1
S2       y := 3   
S3   L1: z := y + 1

यहाँ, S2 तभी चलता है जब S1 में विधेय असत्य हो।

अधिक विवरण के लिए डेटा निर्भरता देखें।

डेटा निर्भरता

एक डेटा निर्भरता दो कथनों से उत्पन्न होती है जो एक ही संसाधन तक पहुँचते हैं या संशोधित करते हैं।

प्रवाह (सत्य) निर्भरता

एक कथन S2 प्रवाह S1 पर निर्भर है (लिखित $S1\ \delta ^{f}\ S2$) यदि और केवल यदि S1 एक संसाधन को संशोधित करता है जिसे S2 पढ़ता है और S1 निष्पादन में S2 से पहले आता है। निम्नलिखित प्रवाह निर्भरता का एक उदाहरण है (RAW: लिखने के बाद पढ़ना):

S1   x:= 10
S2   y:= x + c

प्रति-निर्भरता

एक कथन S2, S1 (लिखित $S1\ \delta ^{a}\ S2$) पर प्रति-निर्भर है यदि और केवल यदि S2 एक संसाधन को संशोधित करता है जिसे S1 पढ़ता है और S1 निष्पादन में S2 से पहले आता है। निम्नलिखित एक प्रति-निर्भरता का एक उदाहरण है (WAR: पढ़ने के बाद लिखें):

S1   x:= y + c
S2   y:= 10

यहाँ, S2yका मान समुच्चय करता है लेकिन S1yका एक पूर्व मान पढ़ता है।

निर्गम निर्भरता

एक कथन S2 निर्गम S1 पर निर्भर है (लिखित $S1\ \delta ^{o}\ S2$) यदि और केवल यदि S1 और S2 एक ही संसाधन को संशोधित करते हैं और S1 निष्पादन में S2 से पहले आता है। निम्नलिखित निर्गम निर्भरता का एक उदाहरण है (WAW: लिखने के बाद लिखें):

S1   x:= 10
S2   x:= 20

यहाँ, S2 और S1 दोनों ने चरxसमुच्चय किया है।

निविष्ट निर्भरता

एक कथन S2, S1 पर निर्भर निविष्ट है (लिखित $S1\ \delta ^{i}\ S2$) यदि और केवल यदि S1 और S2 समान संसाधन पढ़ते हैं और S1 निष्पादन में S2 से पहले आता है। निम्नलिखित निविष्ट निर्भरता का एक उदाहरण है (RAR: पढ़ें-बाद में-पढ़ें):

S1   y:= x + 3
S2   z:= x + 5

यहाँ, S2 और S1 दोनों ही चरxको अभिगम करते है। यह निर्भरता पुन: व्यवस्थित करने पर निषेध नहीं लगाती है।

लूप निर्भरता

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

यह भी देखें

• कार्यक्रम विश्लेषण (अभिकलित्र विज्ञान)
• स्वचालित समांतरता
• स्वचालित वैश्वीकरण
• लूप निर्भरता विश्लेषण
• बहुफलकीय मॉडल का समर्थन करने वाले फ्रेमवर्क
• खतरा (अभिकलित्र संरचना)
• प्रोग्राम स्तरकर्तन
• पूर्ण कूट उन्मूलन

अग्रिम पठन

• Cooper, Keith D.; Torczon, Linda. (2005). Engineering a Compiler. Morgan Kaufmann. ISBN 1-55860-698-X.
• Kennedy, Ken; Allen, Randy. (2001). Optimizing Compilers for Modern Architectures: A Dependence-based Approach. Morgan Kaufmann. ISBN 1-55860-286-0.
• Muchnick, Steven S. (1997). Advanced Compiler Design and Implementation. Morgan Kaufmann. ISBN 1-55860-320-4.