कोड जनरेशन और ऑप्टिमाइजेशन

कोड जनरेशन और ऑप्टिमाइजेशन मध्यवर्ती प्रतिनिधित्व (intermediate representations) को कुशल लक्ष्य कोड (efficient target code) में परिवर्तित करते हैं, जिससे कार्यक्रमों को तेज़ी से चलाने या कम संसाधनों का उपयोग करने के लिए रूपांतरित किया जाता है, जबकि उनके अर्थ को संरक्षित रखा जाता है।

Definition

कोड जनरेशन एक मध्यवर्ती प्रतिनिधित्व से लक्ष्य (मशीन या बाइटकोड) निर्देशों का उत्पादन है, और ऑप्टिमाइजेशन अर्थ-संरक्षणकारी रूपांतरणों का अनुप्रयोग है जो एक कार्यक्रम की गति, आकार या संसाधन उपयोग में सुधार करते हैं।

Scope

यह विषय कंपाइलर के बैक एंड और मिडिल एंड को कवर करता है: स्टैटिक सिंगल असाइनमेंट (SSA) फॉर्म जैसे मध्यवर्ती प्रतिनिधित्व, डेटाफ्लो विश्लेषण, शास्त्रीय ऑप्टिमाइजेशन (स्थिर प्रसार (constant propagation), सामान्य-उप-अभिव्यक्ति उन्मूलन (common-sub-expression elimination), लूप ऑप्टिमाइजेशन), निर्देश चयन, निर्देश शेड्यूलिंग और रजिस्टर आवंटन। यह बताता है कि कैसे रूपांतरण कार्यक्रम के अर्थ को संरक्षित रखते हुए प्रदर्शन में सुधार करते हैं।

Core questions

• कार्यक्रम रूपांतरण व्यवहार को बदले बिना प्रदर्शन में कैसे सुधार कर सकते हैं?
• कौन से मध्यवर्ती प्रतिनिधित्व ऑप्टिमाइजेशन विश्लेषण को कुशल बनाते हैं?
• सीमित मशीन रजिस्टरों को कई कार्यक्रम मानों में कैसे आवंटित किया जाता है?
• आक्रामक ऑप्टिमाइजेशन में शुद्धता और प्रदर्शन के बीच कैसे समझौता किया जाता है?

Key theories

स्टैटिक सिंगल असाइनमेंट फॉर्म

साइट्रॉन और उनके सहयोगियों ने कार्यक्रमों को SSA फॉर्म में बदलने के लिए एक कुशल एल्गोरिथम दिया, जहाँ प्रत्येक चर को एक बार असाइन किया जाता है, जिससे कई डेटाफ्लो-आधारित ऑप्टिमाइजेशन नाटकीय रूप से सरल हो जाते हैं।

ग्राफ कलरिंग द्वारा रजिस्टर आवंटन

चैतिन ने रजिस्टर आवंटन को एक हस्तक्षेप ग्राफ (interference graph) की ग्राफ कलरिंग के रूप में प्रतिरूपित किया, जिससे कार्यक्रम मानों को सीमित मशीन रजिस्टरों के सेट में असाइन करने के लिए मूलभूत दृष्टिकोण प्रदान किया गया।

डेटाफ्लो-आधारित ऑप्टिमाइजेशन

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

Clinical relevance

कोड जनरेशन का ऑप्टिमाइजेशन यह निर्धारित करता है कि कार्यक्रम प्रोसेसर और मेमोरी का कितनी कुशलता से उपयोग करते हैं, जिसका ऊर्जा उपयोग और बड़े पैमाने पर लागत पर व्यापक प्रभाव पड़ता है। SSA फॉर्म और ग्राफ-कलरिंग रजिस्टर आवंटन उत्पादन कंपाइलरों और जस्ट-इन-टाइम सिस्टम के लिए केंद्रीय बने हुए हैं।

History

ऑप्टिमाइजेशन फोर्ट्रान कंपाइलर के साथ शुरू हुआ और 1970 के दशक में एलन और कॉक के डेटाफ्लो विश्लेषण के माध्यम से परिपक्व हुआ। चैतिन का 1981-82 का ग्राफ-कलरिंग रजिस्टर आवंटन और साइट्रॉन एट अल का 1991 का कुशल SSA निर्माण आधुनिक कंपाइलरों के आधारशिला बन गए, जिससे आज के टूलचेन में उपयोग की जाने वाली परिष्कृत ऑप्टिमाइजेशन पाइपलाइनें संभव हुईं।

Debates

ऑप्टिमाइजेशन की आक्रामकता बनाम शुद्धता और पूर्वानुमेयता

कंपाइलर डिजाइनर इस बात पर बहस करते हैं कि कितनी आक्रामक तरीके से ऑप्टिमाइज किया जाए, क्योंकि अपरिभाषित व्यवहार का फायदा उठाना और पुनर्व्यवस्था (reordering) गति प्रदान कर सकती है लेकिन आश्चर्यजनक या असुरक्षित परिणाम भी दे सकती है, जिससे सत्यापित और पूर्वानुमेय ऑप्टिमाइजेशन में रुचि पैदा हुई है।

Key figures

• Frances Allen
• Gregory Chaitin
• Ron Cytron
• Steven Muchnick
• Alfred Aho

Seminal works

• cytron1991
• chaitin1982
• muchnick1997
• aho2006

Frequently asked questions

SSA फॉर्म क्या है?

स्टैटिक सिंगल असाइनमेंट फॉर्म एक मध्यवर्ती प्रतिनिधित्व है जिसमें प्रत्येक चर को ठीक एक बार असाइन किया जाता है और उपयोग एक ही परिभाषा से जुड़े होते हैं, जो कई कंपाइलर ऑप्टिमाइजेशन को सरल और मजबूत करता है।

रजिस्टर आवंटन कठिन क्यों है?

कार्यक्रम आमतौर पर मशीन रजिस्टरों की तुलना में कहीं अधिक मानों का उपयोग करते हैं, इसलिए कंपाइलर को यह तय करना होगा कि कौन से मान रजिस्टर साझा करते हैं और कौन से मेमोरी में स्पिल किए जाते हैं; मुख्य समस्या ग्राफ कलरिंग के बराबर है, जो सामान्य तौर पर कम्प्यूटेशनल रूप से कठिन है।