क्या एक कंपाइलर या एक असेंबलर को केवल आरआईपी-रिश्तेदार एड्रेसिंग कोड उत्पन्न करने के लिए मजबूर करने का कोई तरीका है?

मैं पारंपरिक प्रोग्रामिंग मॉडल से गणना के ट्यूरिंग पूर्ण सार मॉडल में मैपिंग प्रदान करने का एक तरीका खोजने का प्रयास कर रहा हूं।

0
polcott 26 अगस्त 2020, 03:38

1 उत्तर

सबसे बढ़िया उत्तर

ऐसा लगता है कि यह
. पर टिप्पणियों में आपकी चर्चा से संबंधित है क्या C वास्तव में ट्यूरिंग-पूर्ण है? cs.SE पर (जो मैंने हाल ही में आपके द्वारा इसे पोस्ट करने से पहले देखा था)।

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

मैंने सोचा था कि आप ऐसे पॉइंटर्स रखने का सुझाव दे रहे थे जो उनके अपने पते (कोड के लिए नहीं) के सापेक्ष थे, जिन्हें अभी भी पारंपरिक आईएसए जैसे x86-64 के लिए असीमित रजिस्टर चौड़ाई की आवश्यकता होगी ताकि आप रैंडम एक्सेस मशीन अभिकलन का सार मॉडल। x86-64 को एक रजिस्टर में पूरे निरपेक्ष पते की आवश्यकता होती है, या कम से कम 2 भागों की आवश्यकता होती है जो पूर्ण पते के योग होते हैं। ([base + idx*scale] जहां स्केल 2-बिट लेफ्ट शिफ्ट है)। add rdi, [rdi] एक पॉइंटर (जैसे C ptr += *ptr) में एक पॉइंट-टू ऑफ़सेट जोड़ता है, लेकिन फिर भी एक रजिस्टर में फिट होने के लिए परिणाम की आवश्यकता होती है।


यदि आपका मतलब स्थिर डेटा के लिए पूर्ण मेमोरी एड्रेसिंग का उपयोग करने से कंपाइलर्स को रोकना है, तो हाँ, यह आसान है, gcc -fPIE या -fPIC का उपयोग करें।

लेकिन अगर आपका मतलब केवल [rip + rel32] एड्रेसिंग का उपयोग करना है, तो कभी भी [reg] या [RIP + rel32] के विकल्प के लिए सामान्य [base + idx*scale + disp0/8/32] के किसी सबसेट का उपयोग नहीं करना है, तो नहीं, बिल्कुल नहीं वास्तविक दुनिया के कंपाइलर्स के लिए नहीं। RIP-रिलेटिव एड्रेसिंग केवल स्टैटिक स्टोरेज को एक्सेस कर सकता है, इसलिए खुद को उस तक सीमित रखने का मतलब कोई स्टैक स्पेस और कोई पॉइंटर नहीं होगा। x86-64 का एकमात्र RIP-रिलेटिव एड्रेसिंग मोड [rip + rel32] है, जहां rel32 मशीन कोड में एक निरंतर एम्बेडेड, रजिस्टर मान नहीं।

(शायद आप RIP+rel32 एड्रेसिंग मोड के rel32 को संशोधित करने के लिए स्व-संशोधित कोड का उपयोग कर सकते हैं, लेकिन कोई मुख्यधारा का कंपाइलर ऐसा नहीं करेगा। यह स्पष्ट नहीं है कि आप केवल एक के साथ स्टैक स्पेस के लिए पुन: प्रवेश कैसे प्रबंधित करेंगे। किसी फ़ंक्शन के मशीन कोड की प्रतिलिपि जिसे आप संशोधित कर रहे हैं, लेकिन शायद स्टैक स्पेस में सही डेटा रखने से आप कॉलर के rel32 ऑफ़सेट को पुनर्स्थापित कर सकेंगे)।

हस्तलिखित एएसएम में, आप निश्चित रूप से जो चाहें कर सकते हैं, लेकिन rel32 विस्थापन को फिर से लिखने के लिए खुद को सीमित करना इसे (सख्ती से?) वेनिला x86-64 से कम शक्तिशाली बनाता है, ट्यूरिंग पूर्ण नहीं।


यदि आप [PC + other_register] जैसे एड्रेसिंग मोड की तलाश में हैं, तो मुझे लगता है कि 32-बिट एआरएम में वह है। इसमें एड्रेसिंग को अनुक्रमित किया गया है, और प्रोग्राम काउंटर 16 सामान्य-उद्देश्य रजिस्टरों में से एक के रूप में सुलभ है (AArch64 के विपरीत)। ताकि आप स्थिर सरणियों के पीसी-सापेक्ष अनुक्रमण कर सकें। दोबारा, ऐसा नहीं है कि यह किसी भी स्पष्ट तरीके से मदद करता है। किसी भी असीमित संख्या में स्मृति स्थानों को संबोधित करने के लिए एक निश्चित पीसी पर दिए गए किसी भी निर्देश के लिए, "अन्य रजिस्टर" में असीमित चौड़ाई होनी चाहिए।


अनबाउंड ट्यूरिंग-पूर्ण C:

मेरा मानना ​​​​है कि यह तब तक असंभव है जब तक आप इस तथ्य को दूर करने के लिए भाषा को ढीला नहीं करते हैं कि प्रत्येक प्रकार (पॉइंटर्स सहित) की कुछ निश्चित चौड़ाई समय से पहले तय की जाती है, न कि उस इनपुट के आकार के आधार पर जिसे आप निपटना चाहते हैं।

एक ट्यूरिंग-पूर्ण सी कार्यान्वयन एक लूप में malloc को असीमित संख्या में कॉल कर सकता है, उदाहरण के लिए fgets के साथ इनपुट की पंक्तियों को पढ़ना और प्रत्येक पंक्ति को जोड़ना क्योंकि यह एक मानक पुनरावर्ती दृष्टिकोण के साथ एक बाइनरी ट्री में आता है। . C पॉइंटर्स पर आधारित एक मानक नोड लेआउट का उपयोग करना:
struct node { struct node *left, *right; const char *str; };. फिर बाद में उस पेड़ को पार करें और क्रमबद्ध क्रम में लाइनों को आउटपुट करें।

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


टिप्पणियों में आप जो वर्णन करते हैं वह x86 asm में UTM स्टेट मशीन के स्थानीय भागों को लिख रहा है, प्रत्येक राज्य का अपना 2GiB मेमोरी स्पेस है और अगले राज्य में आगे या पीछे कूदने की क्षमता है। केवल एक राज्य के कोड के भीतर, वास्तविक यादृच्छिक पहुंच या वास्तविक पॉइंटर्स रखने का कोई स्पष्ट तरीका नहीं है।

यूटीएम के प्रत्येक चरण के लिए एक सीमित सी कार्यान्वयन का उपयोग करने से आपको एक समग्र ट्यूरिंग-पूर्ण सी कार्यान्वयन नहीं मिलता है, यह आपको एक ट्यूरिंग मशीन देता है जिसमें टेप जैसी गैर-यादृच्छिक-पहुंच होती है जब आपकी समस्या का आकार होता है आप एक "राज्य" या "मेमोरी बैंक" या जो भी आप इसे कहते हैं, उससे अधिक कर सकते हैं।

4
Peter Cordes 26 अगस्त 2020, 04:22