Phase 13: Tools & Protocols

कंपाइलर इडिओंः ऑप्टिमाइज़ेशन आपके कोड पर क्या करता है और इसे कैसे वापस पढ़ें

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

Type: Build

Languages: Python, C, x86-64 assembly, AArch64 assembly

Prerequisites: Phase 13 · 33 (disassembly and control flow), Phase 13 · 34 (lifting to pseudocode), Phase 13 · 38 (calling conventions)

Time: ~150 minutes

सीखने के लक्ष्य

ग्रेनलंड-मोंटगोमरी सीमा के साथ किसी भी निरंतर द्वारा विभाजन के लिए जादुई संख्या और स्थानांतरण प्राप्त करें, और उत्सर्जित निरंतरों से विभाजक को पुनर्प्राप्त करें।
LLVM द्वारा ए को कम करने के पांच तरीके बताएँ switchऔर प्रविष्टि संख्या, तालिका स्थान, और वस्तु से प्रविष्टियों को पढ़ें।
वेक्टरलाइज्ड लूप को लेन, accumulators, तत्व प्रति पुनरावृत्ति, trip-count mask, reduction और remainder loop के रूप में पढ़ें।
पूंछ कॉल, इनलाइन कॉल, शाखाहीन चयन, और लूप जो बन गए पहचानेंmemsetया memcpy. .
प्रत्येक भाषा के बारे में सूचनाएँ और उसके स्रोत के रूप में रिपोर्ट करें, x86-64 और AArch64 पर, -O0पार-O3. .
परिणाम की तुलना उसी बाइट्स के लिए गिद्रा, एंग्र, रडार2, रिज़िन और एलएलडीबी के साथ करें।

समस्या

आप संकलित किया idioms.cपर-O2और एक एजेंट से पूछा कि क्या div7uएजेंट ने पढ़ाimulq $0x24924925, %rax, %raxऔर जवाब दिया कि समारोह 613566757 से गुणा, स्थानांतरित, और जोड़ता है। हर शब्द सच है। समारोह गणना करता हैx / 7. .

एक ही वस्तु में एक switchसात मामलों के साथ जो किसी भी कूद नहीं है, एक switchपांच मामलों के साथ जो एक कूद टेबल है, एक switchदो मामलों के साथ जो एक है seteऔर एक cmovne, और एक लूप के ऊपर nदो में प्रति पुनरावृत्ति आठ पूर्णांक चलाता है जो पूर्णांक xmmरजिस्टर करता है और फिर दूसरे लूप में शेष समाप्त करता है।-O0एक ही स्रोत से उत्पादित divl, सात प्रविष्टि कूद टेबल, और एक स्केलर लूप.-O1सात-केस स्विच मानों की तालिका बन गया और वेक्टर लूप अभी मौजूद नहीं था।

इन आकारों को व्यंग्य कहते हैं। एक संकलक प्रत्येक को एक नियम से निकालता है जिसे आप अपने स्रोत में पढ़ सकते हैं, और प्रत्येक को उस निर्माण में वापस डिकोड किया जा सकता है जहां से यह आया था। डिकोड अंकगणितीय है, और अंकगणितीय की जांच की जा सकती है। पाठ 34 उनमें से एक साबित हुआ, गुणा द्वारा 0x66666667यह सबक उन सभी के लिए पहचानकर्ता बनाता है, इसे हमारे अपने कोड के 18 निर्माणों पर चलाता है, और सभी 373 रिपोर्टों को C स्रोत के खिलाफ सत्यापित करता है।

एक व्यंग्य एक उत्पत्ति वाला रूप है

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

पहचानकर्ता में code/main.pyllvm-objdump -d -r, जो पाठ 33 निर्देश सीमाओं के लिए प्राचार्य के रूप में स्थापित किया गया है। यह पता, बाइट्स, mnemonic, परिमाणों और इसके बाद स्थानांतरण रेखा के साथ निर्देशों में प्रत्येक समारोह को पार्स करता है। यह केवल दो चीजों के लिए ऑब्जेक्ट फ़ाइल पढ़ता हैः बाइट्स.rodata, जहां मूल्य तालिकाएँ रहती हैं, और .rela.rodataप्रविष्टियाँ, जहां लिंक करने से पहले कूदने की मेज लक्ष्य रहते हैं।

प्रत्येक पता लगाने एक हैIdiomएक के साथ रिकॉर्डkind, एक डिकोड sourceफॉर्म, सूची evidenceपते, एक detailशब्दकोश, और एक verifiedझंडा C स्रोत से आता है।parse_source()पढ़ता है idioms.c, प्रत्येक फ़ंक्शन को ढूंढता है, और डिवीज़रों को निकालता है/और %, गुणक के बाद *, switchमामले और उनके मूल्य, ? :प्रसंशकों, forएक विभाजन भाषा की पुष्टि तब की जाती है जब उसका विभाजक फ़ंक्शन के विभाजन सूची में होता है। एक खोज तालिका की पुष्टि तब की जाती है जब उसके प्रविष्टियाँ केस मानों से मेल खाती हैं, एक निरंतर कारक तक। एक पूंछ कॉल की पुष्टि तब की जाती है जब स्रोत में कॉल को बुलाया जाता है। डेमो रिपोर्ट एक unverifiedसूची, और परीक्षण सूट का दावा है कि सूची सभी 18 निर्माण के लिए खाली है.

डिकोडिंग नामों की आवश्यकता होती है। पहचानकर्ता प्रत्येक फ़ंक्शन के बुनियादी ब्लॉकों पर एक छोटा सा प्रतीकात्मक मूल्यांकनकर्ता चलाता है, सूचीबद्ध क्रम में, सिस्टम V और AAPCS64 सम्मेलनों के तर्क रजिस्टरों में स्रोत से पैरामीटर नामों के साथ पाठ 38 से। स्टैक स्लॉट को उनके ऑपरेंड पाठ द्वारा ट्रैक किया जाता है।-O0प्रत्येक ब्लॉक प्रविष्टि पर पूर्ववर्ती राज्यों को मिलाया जाता है, और जहां वे अलग हैं एक नाम है कि एक पहले की बोली दिया है एक निरंतर पर जीतता है।cmovll %edx, %eaxमें digestवापस पढ़ता है sum % 10 < 5 ? sum % 10 : 5: लूप इडियॉम accumulator नाम दिया sum, विभाजन की भाषा ने अपने गुणक का नाम दिया sum / 10, और मॉड्यूलो शब्द इसका परिणाम नामित किया गयाsum % 10स्रोत लिखता हैrem > 5 ? 5 : rem. दोनों अभिव्यक्ति से छोटे का पता चलता है remऔर पांच, और वे सहमत हैं rem == 5. .

एक निरंतर द्वारा विभाजन

ग्रैनलंड और मोंटगोरी, "बहुकरण का उपयोग करके अपरिवर्तित पूर्णांक द्वारा विभाजन" (PLDI 1994), के स्थान पर n / dएक गुणा और एक शिफ्ट के साथ. एक शिफ्ट चुनेंsऔर एक गुणक m = ceil(2^s / d). . तो floor(n * m / 2^s)बराबर floor(n / d)प्रत्येक के लिएnत्रुटि के समय सीमा में e = m * d - 2^sअसीमित 32-बिट के लिए पर्याप्त छोटा है।nसीमा है e <= 2^(s - 32). हस्ताक्षरित के लिए .nके साथ|n| < 2^31सीमा है e <= 2^(s - 31), और एक साइन फिक्सअप 1 जोड़ता है जब nनकारात्मक है, क्योंकि तल नकारात्मक गुणांक के लिए गलत तरीके से घुमाता है.

magic_numbers(d, bits, signed)में main.pyखोजें s32 से ऊपर और पहली जोड़ी वापस मिलता है जो सीमा को संतुष्ट करता है। यह खोज हर निरंतर फ्लैश फिक्स्चर में उत्सर्जित को पुनः प्रस्तुत करता है।

हाथ से हस्ताक्षरित 10

2^35 / 10 = 3435973836.8छत है3435973837 = 0xCCCCCCCD. . गलती है0xCCCCCCCD * 10 - 2^35 = 2, और पर बंधाs = 35है 2^3 = 8.s = 34त्रुटि 4 के सीमा के खिलाफ 6 होगा, तो 35 सबसे छोटा बदलाव है.n = 123123 * 3435973837 = 422624781951और 422624781951 >> 35 = 12. .

क्लिंग के लिए ठीक यही उत्सर्जन करता है div10uपर-O2x86-64 परः

text       0: 89 f9                        	movl	%edi, %ecx
       2: b8 cd cc cc cc               	movl	$0xcccccccd, %eax
       7: 48 0f af c1                  	imulq	%rcx, %rax
       b: 48 c1 e8 23                  	shrq	$0x23, %rax

0x2335 है।movl %edi, %ecxशून्य 32-बिट तर्क को 64-बिट रजिस्टर में बढ़ाता है, जो कि हस्ताक्षरित रूप है। पहचानकर्ता से गुणक पढ़ता हैmovl $immजो दो-ओपरैंड को खिलाता है imulq, शिफ्ट पढ़ता है, और कॉल करता है divisor_from_magic(0xCCCCCCCD, 35). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2^35 // m = 10और 11 और 10 स्वीकार करता है क्योंकि magic_numbers(10)एक ही गुणक देता है और वापस शिफ्ट.

AArch64 पर एक ही फ़ंक्शन है mov w8, #0xcccd; movk w8, #0xcccc, lsl #16; umull x8, w0, w8; lsr x0, x8, #35. निरंतर दो 16-बिट आधे में आता है, गुणा है umullपहचानकर्ता आधे को इकट्ठा करता है और एक ही विभाजक रिपोर्ट करता है।

हाथ से हस्ताक्षरित 7, जोड़ी-फिक्स के साथ

2^35 / 7 = 4908534052.57छत है4908534053 = 0x124924925, जो 33 बिट्स की आवश्यकता है। त्रुटि 3 है 8 की सीमा के खिलाफ, इसलिए शिफ्ट 35 है, और कोई छोटी शिफ्ट काम नहीं करती है। एक 32-बिट गुणाकार गुणक को नहीं पकड़ सकता है, इसलिए संकलक कम 32 बिट्स से गुणा करता है0x24924925और डिविडेंड को एक निश्चित क्रम में वापस जोड़ता हैः

text      32: 48 69 c0 25 49 92 24         	imulq	$0x24924925, %rax, %rax
      39: 48 c1 e8 20                  	shrq	$0x20, %rax
      3d: 29 c7                        	subl	%eax, %edi
      3f: d1 ef                        	shrl	%edi
      41: 01 f8                        	addl	%edi, %eax
      43: c1 e8 02                     	shrl	$0x2, %eax

इसे पढ़ें t = (n * 0x24924925) >> 32, तो q = (((n - t) >> 1) + t) >> 2. कुल शिफ्ट है 32 + 1 + 2 = 35. के साथ n = 100t = 14,(100 - 14) >> 1 = 43,43 + 14 = 57,57 >> 2 = 14. पहचानकर्ता पहचानता है sub,shr,add,shr32 बिट शिफ्ट के बाद पूंछ, जोड़े 2^32गुणक पर वापस, और 7 वापस आ जाता है।evaluate_division()इस सटीक अनुक्रम चलाता है और परीक्षण यह के खिलाफ जांच करता हैn // 732 बिट किनारे मानों पर। AArch64 फॉर्म है sub w9, w0, w8; add w8, w8, w9, lsr #1; lsr w0, w8, #2, एक निर्देश छोटा क्योंकि स्थानांतरित जोड़ एक निर्देश है.

हाथ से हस्ताक्षरित 3

2^32 / 3 = 1431655765.33, छत 1431655766 = 0x55555556, त्रुटि 2 और हस्ताक्षरित लिंटेड s = 32है 2^1 = 2. बंड को कोई जगह नहीं है, इसलिए शिफ्ट 32 है और क्लिंग का उपयोग करता है shrq $0x20. के साथ n = -7: उत्पाद -10021590362, 32 से अंकगणित परिवर्तन देता है -3, संकेत बिट सेट है, तो फिक्सअप 1 जोड़ता है और परिणाम है -2, जो है -7 / 3सी. हस्ताक्षरित फिक्स्चर div10sऔर div3sदोनों को ठीक करने के लिए ले जाते हैं shrq $0x3fउत्पाद की प्रति पर addl. .

स्थिर क्या नहीं हैं

गुणक अकेले कोई विभाजक नहीं नामित करता है।0x66666667शिफ्ट 34 के साथ 10 है। शिफ्ट 33 के साथ एक ही गुणक 5 है, जैसा कि पाठ 34 में दिखाया गया है। इसलिए पहचानकर्ता हमेशा गुणक को कुल शिफ्ट के साथ जोड़ेगा, और clangMatchesAlgorithmदो की शक्तियों कभी भी गुणा का उपयोग नहीं करते हैं।magic_numbers()उन्हें अस्वीकार करता है, क्योंकि संकलक एक बदलाव के साथ एक संकेत पूर्वाग्रह जारी करता है, और mod8sअगले खंड में यह आकार दिखाता है।

भाषा निर्देश चयनकर्ता से संबंधित है

-O0,div10uहै movl $0xa, %ecx; xorl %edx, %edx; divl %ecx. .div10sहै cltd; idivl %ecx. एक ही वस्तु में,digest से 10 से उसके लूप की राशि को विभाजित करता हैimulq $0x66666667एक ध्वज अंतर को समझाता है।idioms-x86_64-nofastisel-O0.oके साथ बनाया गया था -O0 -mllvm -fast-isel=false, और इसमें प्रत्येक विभाजन गुणा है, सहित div10uके साथmovl $0xcccccccd, %ecx; imulq %rcx, %rax; shrq $0x23. हार्डवेयर विभाजन त्वरित निर्देश चयनकर्ता की पसंद है -O0. गुणा चयन DAG की घटती है, जो LLVM की है UnsignedDivisionByConstantInfoऔर SignedDivisionByConstantInfoउत्पादित करें।digestखंड जो विभाजन को पकड़ता है भी एक रखता है switch, और उस ब्लॉक चयन दिवस गया. पहचानकर्ता दोनों रूपों की रिपोर्ट,hardware idivlऔर magic multiply, और आंकड़ा मिश्रित दिखाता है -O0कार्य।

मॉड्यूलो कोटिंटर का पालन करता है

x % dहै x - (x / d) * d. संकलक उपरोक्त शब्द के साथ गुणांक की गणना करता है, इसे वापस गुणा करता है, और घटाता है। x86-64 पर 10 से वापस गुणा होता है addl %ecx, %ecx; leal (%rcx,%rcx,4), %ecx, जो है 2 * q * 5. AArch64 पर यह एक निर्देश है,msub w0, w8, w9, w0, जो गणना करता है w0 - w8 * w9के साथw9 = 10. पहचानकर्ता प्रतिलिपि के माध्यम से गुणांक रजिस्टर का अनुसरण करता है, जमा कारक को add,lea,shlऔर imul, और स्वीकार करता है subजब कारक विभाजक के बराबर है।

जब एक ही गुणांक एक और अभिव्यक्ति को भी खिलाता है, तो दोनों शब्द रिपोर्ट में बने रहते हैं।-O1संकलक गणना करता है sum / 10एक बार में digestऔर इसका उपयोग switchx86-64 पर यह गुणांक को दो बार जोड़ता है,leal (%rax,%rsi), %ediमॉड्यूल और addl %esi, %eaxएक विभाजन और एक मॉड्यूल की रिपोर्ट और एक भाग को साझा के रूप में चिह्नित करता है। एक रिपोर्ट जो यहाँ विभाजन खो दिया होगाswitchसूचकांक अपठनीय है।

दो की शक्ति से हस्ताक्षरित मॉड्यूल का अपना आकार होता है, क्योंकि गुणांक कभी भी गणना नहीं किया जाता हैः

text      92: 8d 48 07                     	leal	0x7(%rax), %ecx
      95: 85 ff                        	testl	%edi, %edi
      97: 0f 49 cf                     	cmovnsl	%edi, %ecx
      9a: 83 e1 f8                     	andl	$-0x8, %ecx
      9d: 29 c8                        	subl	%ecx, %eax

नकारात्मक के लिए xकोड को मास्क करने से पहले 7 से पूर्वाग्रह, ताकि ट्रंकशन शून्य की ओर घुमाता है के रूप में सी की आवश्यकता है।x8 के गुणक के रूप में गोल, और घटाने leaves x % 8. AArch64 के साथ यह करता है .negs w8, w0; and w9, w0, #0x7; and w8, w8, #0x7; csneg w0, w9, w8, mi: दोनों का मुखौटा xऔर -xइस के लिए गिदरा ने अपना नियम नामित किया हैRuleSignMod2nOpt, संक्षिप्त "INT_SREM फॉर्म कन्वर्ट करेंः (V + (sign >> (64-n)) & (2^n-1)) - (sign >> (64-n)) => V s% 2^n"।

-O0AArch64 modulo लिखता है sdiv w9, w8, w10; mul w9, w9, w10; subs w0, w8, w9. पहचानकर्ता उस फॉर्म को भी स्वीकार करता है और रिपोर्ट करता है hardware sdiv + mul + subs. .

स्विच को कम करने के पांच तरीके

LLVM एक switchदो जगहों पर।SimplifyCFG::simplifySwitchLookup-O1और ऊपर और एक स्विच को बदल देता है जिसका सभी मामले स्थिरांक उत्पन्न करते हैं एक मान तालिका में, जब कम से कम तीन मामले होते हैं और लक्ष्य खोज तालिकाओं का निर्माण कर सकता है।SingleValueKind,LinearMapKind,BitMapKindऔर ArrayKind. . .-O0पाइपलाइन कभी भी इस पास नहीं चलाता है। शेष स्विच पहुंचSwitchLowering::findJumpTablesनिर्देश चयन में, जो एक कूद तालिका बनाता है जब क्लस्टर कम से कम है min-jump-table-entriesप्रविष्टियाँ, डिफ़ॉल्ट रूप से 4 और पर्याप्त घनी हैः NumCases * 100 >= Range * MinDensityके साथjump-table-densityसामान्य कार्यों के लिए 10 और 40 से कम -Os. जो कुछ भी शेष है, वह केस स्थिरांक पर द्विआधारी खोज बन जाता है,splitWorkItemपिवोट चुनना. फिक्स्चर प्रति परिणाम एक समारोह है.

Function	Source	`-O0` x86-64	`-O2` x86-64	`-O2` AArch64
`linear_switch`	cases 0 to 6 return 10 to 70	jump table, 7 entries	linear map `10*k + 10`, default -1	`madd` and `csinv`
`table_switch`	cases 0 to 6 return 10 to 60 then 71	jump table, 7 entries	lookup table at `.rodata+0x28`	lookup table at `.rodata+0x0`
`call_switch`	cases 0 to 4 call one of five pointers	jump table, 5 entries	jump table, 5 entries	comparison tree, pivot 1
`sparse_switch`	cases 1, 100, 10000, 1000000, 100000000	compare chain	comparison tree, pivot 9999	comparison tree, pivot 9999
`two_cases`	cases 3 and 4 return 7 and 9	compare chain	select chain `k != 3 ? (k == 4)*9 : 7`	two `csel`

वस्तु से पढ़ी गई खोज तालिका

table_switchपर-O2:

text      d0: b8 ff ff ff ff               	movl	$0xffffffff, %eax
      d5: 83 ff 06                     	cmpl	$0x6, %edi
      d8: 77 0c                        	ja	0xe6 <table_switch+0x16>
      da: 89 f8                        	movl	%edi, %eax
      dc: 48 8d 0d 00 00 00 00         	leaq	(%rip), %rcx
		00000000000000df:  R_X86_64_PC32	.rodata+0x24
      e3: 8b 04 81                     	movl	(%rcx,%rax,4), %eax
      e6: c3                           	retq

सीमाओं की जांचcmpl $6; jaस्थानांतरण अनुपूरक0x24और RIP-संबंधी क्षेत्र के 4 बाइट्स तालिका पर डालता है .rodata+0x28, नियम पाठ 33 व्युत्पन्न. वहाँ बाइट्स हैं0a 00 00 00 14 00 00 00 ..., तो प्रविष्टियाँ हैं [10, 20, 30, 40, 50, 60, 71], और वे स्रोत मामले के मानों के बराबर हैं. असेंबलर इस तालिका का नाम दिया.Lswitch.table.table_switch.sएक टिप्पणी के साथ फ़ाइल @switch.table.table_switchवस्तु में केवल स्थानांतरण और बाइट्स शेष हैं. कोई कूद नहीं है, इसलिए नियंत्रण प्रवाह ग्राफ में तीन ब्लॉक हैं.

AArch64 फ़ॉर्म में तालिका का पता के साथ मिलाया गया है।adrp x8और add x8, x8, #0x0, प्रत्येक अपने स्वयं के स्थानांतरण ले .rodata, और लोड के साथ ldr w0, [x8, w0, uxtw #2]. पहचानकर्ता से addend पढ़ता है addस्थानांतरण।

रेखाचित्र, जिसमें कोई तालिका नहीं है

linear_switchरिटर्न 10 * (k + 1)के लिएk0 से 6 तक।simplifySwitchLookupसापेक्षता का पता लगाता है और अंकगणित जारी करता हैः

text      b0: 83 ff 07                     	cmpl	$0x7, %edi
      b3: 8d 04 bf                     	leal	(%rdi,%rdi,4), %eax
      b6: 8d 4c 00 0a                  	leal	0xa(%rax,%rax), %ecx
      ba: b8 ff ff ff ff               	movl	$0xffffffff, %eax
      bf: 0f 42 c1                     	cmovbl	%ecx, %eax

मूल्यांकनकर्ता पढ़ता है leal (%rdi,%rdi,4)जैसे 5*k,leal 0xa(%rax,%rax)जैसे 10*k + 10, और cmovbके बादcmpl $7जैसे k < 7 ? 10*k + 10 : -1. पहचानकर्ता फिर प्रत्येक स्रोत मामले के साथ सूत्र की जांच करता है और सत्यापित बोली को चिह्नित करता है।madd w8, w0, w8, w9और csinv w0, w8, wzr, lo, जहां csinvके साथwzrउपज -1डिफ़ॉल्ट पथ पर।

स्थानांतरण से पढ़ी गई कूदने की तालिका

call_switchपर-O2आकार पाठ 33 में बरामद किया गया है gradeपर-O0cmpl $4; ja, ए leaq.rodata-0x4, ए movslq4 बाइट प्रविष्टि का, addqऔर jmpq *%rax. पांच प्रविष्टियाँ स्थानान्तरण हैं .rela.rodataऔर target = addend - 4kदेता है0x10c, 0x107, 0x10e, 0x110, 0x109, पांच अलग-अलग ब्लॉक जो प्रत्येक पूंछ एक समारोह पॉइंटर के माध्यम से कूद।dispatchफिक्स्चर 16 मामलों के लिए यह स्केल करता हैः 16 स्थानांतरण प्रविष्टियों पर x86-64, और AArch64 पर 16 एकल बाइट्स की एक संपीड़ित तालिका के साथ पढ़ा ldrb w11, [x9, x8], 4 से बढ़ाया गया add x10, x10, x11, lsl #2, और एक पर आधारित हैadrपहले केस ब्लॉक का पहचानकर्ता डिकोड करता है[0x24, 0x74, 0x54, ...]बाइट तालिका और रिपोर्ट से compressed: true. .

चार स्तरों पर एक ही स्विच

digestएक स्विच पर रखता है sum / 10मामले 6 से 10 और मान 1, 2, 4, 8, 8 के साथ, तो 16 से परिणाम गुणा है। x86-64 पर यह एक कूद तालिका है -O0, एक खोज तालिका -O1प्रविष्टियों के साथ [16, 32, 64, 128, 128], और एक कूद टेबल फिर से -O2और -O3जिसके चार केस ब्लॉक स्टोर 0x10,0x20,0x40,0x80. से -O116 से गुणा करने के मामले में ऊपर चला गया है।-O0मामले 1, 2, 4 और 8 को स्टोर करते हैं और गुणा स्विच के बाद रहता है।-O1खोज तालिका में पहचानकर्ता स्रोत मानों के साथ प्रविष्टियों की तुलना करता है, एक निरंतर अनुपात पाता है, और रिपोर्ट foldedFactor: 16. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .-O2रूप एक तुलना पेड़ है, जिसमें 8 पर पिवोट है, 6, 7 और 8 के लिए समानता परीक्षण और एक रेंज परीक्षण sub w9, w9, #9; cmp w9, #2; b.hsजो दो निर्देशों में मामलों 9 और 10 को कवर करता है।rangeTests: [[9, 10]]. .

दो ध्वज इन सीमाओं को स्थानांतरित करते हैं।-fno-jump-tablesघूमते हैंtable_switch,call_switch, और digest7 मामले के लिए प्वाइंट 2 और 4 के साथ x86-64 पर तुलना के पेड़ों में स्विच करें।-mllvm -min-jump-table-entries=4पत्तेcall_switchएक तुलना के पेड़ के रूप में, तो उस लक्ष्य पर प्रवेश संख्या अप्रत्यक्ष कॉल के पांच-कदम स्विच के लिए निर्णायक इनपुट नहीं थी।idioms-arm64-jt4-O2.oरिकॉर्ड जो चल रहे हैं.

GCC दोनों निर्णयों को लागू करता है tree-switch-conversion.cc, कक्षाओं के साथ jump_table_cluster,bit_test_cluster,switch_decision_treeऔर switch_conversion. . यह है .-ftree-switch-conversionपर है -O2,-fjump-tablesऔर -fbit-testsपर-O1, और कूद तालिका की सीमा से आता है case-values-thresholdइस मशीन पर कोई जीसीसी स्थापित नहीं है, तो उन नामों जीसीसी स्रोत और मैनुअल से आते हैं, और संकलक एक्सप्लोरर है जहां आप उन्हें जांच करने के लिए है।

लूप्सः वेक्टरिज़्ड, अनरोल्ड या रिप्लेस

LLVM के लूप वेक्टरिजर पर है -O2,-O3और -Os, और बंद करने के लिए -O0और -O1, एक नियम जो जनवरी 2014 में LLVM 3.4 से दिनांकित है। sum_nपर-O2आकार के प्रत्येक भाग को दिखाता हैः

text     1f6: 83 fe 07                     	cmpl	$0x7, %esi
     1f9: 77 09                        	ja	0x204 <sum_n+0x14>
     206: 81 e2 f8 ff ff 7f            	andl	$0x7ffffff8, %edx
     230: f3 0f 6f 14 37               	movdqu	(%rdi,%rsi), %xmm2
     235: 66 0f fe c2                  	paddd	%xmm2, %xmm0
     239: f3 0f 6f 54 37 10            	movdqu	0x10(%rdi,%rsi), %xmm2
     23f: 66 0f fe ca                  	paddd	%xmm2, %xmm1
     243: 48 83 c6 20                  	addq	$0x20, %rsi
     24a: 75 e4                        	jne	0x230 <sum_n+0x40>
     24c: 66 0f fe c8                  	paddd	%xmm0, %xmm1
     250: 66 0f 70 c1 ee               	pshufd	$0xee, %xmm1, %xmm0
     262: 66 0f 7e c8                  	movd	%xmm1, %eax
     270: 03 04 97                     	addl	(%rdi,%rdx,4), %eax
     279: 75 f5                        	jne	0x270 <sum_n+0x80>

गार्ड cmpl $7; jaस्केलर लूप में 8 से नीचे यात्रा गिनती भेजता है।andl $0x7ffffff8राउंड्स यात्रा को 8 के गुणक तक गिना जाता है। शरीर प्रति पुनरावृत्ति 32 बाइट्स को दो में लोड करता है।xmmसंचय, चार 32-बिट लेन प्रत्येक, तो वेक्टरिज़ेशन कारक 4 है और इंटरलेव कारक 2 है.padddदो pshufd, दो और padddऔर movdआठ लेन को एक पूर्णांक में कम करें।0x270यह अंतिम 0 से 7 तत्वों के लिए स्केलर शेष है। पहचानकर्ता अपने पीछे के किनारे से लूप ढूंढता है, SIMD रजिस्टर देखता है, लेन गिनती को पढ़ता हैpaddd, अलग-अलग संचयकों की गिनती करता है, चरण को विभाजित करता है 0x204 द्वारा और रिपोर्ट 4 lanes x 2 accumulators = 8 elements per iteration, मास्क, गार्ड, कमी और शेष लूप के साथ क्षेत्र के रूप में।ldp q2, q3दो add v.4s,addv s0, v0.4sऔर fmov w8, s0. .

एक निश्चित यात्रा गिनती लूप को हटा देता है।sum4एक हैmovdqu, कमी और movd, बिना पीछे के किनारे के.poly8वेक्टरिज़ नहीं कर सकते, क्योंकि प्रत्येक पुनरावृत्ति पिछले संचयकर्ता पर निर्भर करती है, इसलिए संकलक इसे आठ बार अनरोल करता हैः 0 से तक ऑफसेट पर आठ भार0x1cसे%rdi, प्रत्येक 5 से एक शिफ्ट और एक घटाने के साथ जो गणना के बाद acc * 31. पहचानकर्ता एक आधार से लगातार ऑफसेट पर भारों की गणना करता है और रिपोर्ट करता है loop unrolled by 8, no back edge. AArch64 पर एक ही भार चार के रूप में आते हैं .ldpजोड़े।

वेक्टरराइज़र को बंद करें -fno-vectorize -fno-slp-vectorizeऔर sum_nएक स्केलर लूप बन जाता है जो 8 से अनरोल्ड होता है, जिसमें 8 होता है addl k(%rdi,%rdx,4), %eaxऔर addq $8, प्लस एक शेष लूप। sum4पहचानकर्ता रिपोर्ट करता हैunrolled loopके साथcopies: 8और indexStep: 8पहली और copies: 4दूसरे के लिए.

पाठ 33 में दो पीछे के किनारे पाया totalपर-O2और उन्हें दो लूप कहा। इस पाठ में उन्हें नाम दिया गया हैः एक वेक्टर शरीर और एक स्कालर शेष उसी स्रोत लूप। एक बैक एज केवल एक लूप है जब इसका लक्ष्य इसे फिर से प्राप्त कर सकता है। is_loop()यह जाँचें, क्योंकि digestAArch64 पर साझा डिफ़ॉल्ट ब्लॉक के लिए पीछे की शाखाएं हैं जो लूप नहीं हैं, और पहचानकर्ता के पहले संस्करण ने उन्हें वेक्टर लूप के रूप में गिना।

लूप जो लाइब्रेरी कॉल बन जाते हैं

LoopIdiomRecognizeएक लूप को बदल देता है जो प्रत्येक बाइट में शून्य को स्टोर करता है एक कॉल करने के लिएmemset, से -O1ऊपर।fillपर-O2है testl %esi, %esi; jle; movl %esi, %edx; xorl %esi, %esi; jmp memset@PLT. कॉल स्थानांतरण के साथ एक पूंछ कूद है .R_X86_64_PLT32 memset-0x4, और फ़ंक्शन की retqकेवल खाली पथ पर है। पहचानकर्ता रिपोर्टstore loop recognized as memset(...)और स्रोत लूप के खिलाफ यह सत्यापित करता है, क्योंकि स्रोत कभी नाम नहीं memset. .

copy16कॉलmemcpyएक निरंतर के साथ 16, और x86 बैकेंड इसे विस्तारित करने के लिए इनलाइन के रूप में movups (%rsi), %xmm0; movups %xmm0, (%rdi), प्रति memcpy.-O0एक ही कॉल दो 8 बाइट है movqजोड़े के साथ।-fno-builtinकॉल कॉल रहता है,jmp memcpy@PLTके साथmovl $0x10, %edxऔर fillअपने लूप बनाए रखता है, जो वेक्टरराइज़र फिर दो 16-बाइट के लूप में बदल देता है movupsप्रति पुनरावृत्ति स्टोर. पहचानकर्ता रिपोर्ट vectorized store loop: 2 x 16-byte stores = 32 bytes per iterationउस निर्माण के लिए.

गायब होने या कूदने वाले कॉल

tail_callerरिटर्न tail_target(x + 1).-O0यह हैaddl $0x1, %edi; callq tail_target@PLT; addq $0x10, %rsp; popq %rbp; retq.-O2यह हैincl %edi; jmp tail_target@PLTऔर कुछ नहीं. कॉल करने वाले के फ्रेम गायब हो गया है और कॉल करने वाले के कॉल करने वाले के लिए वापस आता है. AArch64 पर कूद हैb tail_targetके साथR_AARCH64_JUMP26. पहचानकर्ता एक jmpया bपाठ 33 की पुनरावर्ती अवतरण इसे एक समारोह के रूप में माना जाना चाहिए, क्योंकि लक्ष्य समारोह के बाहर है.

twice_sumकॉलleaf_add.-O0कॉल वहाँ है, callq leaf_add@PLT. से -O1leaf_add,leal (%rdi,%rsi), %eax, अंदर दिखाई देता है twice_sumऔर कोई कॉल नहीं बचा है.-O0क्लांग प्रत्येक फ़ंक्शन को चिह्नित करता है optnoneऔर noinlineऔर केवल हमेशा-इनलाइनर चलाता है। पहचानकर्ता स्रोत से जानता है किtwice_sumकॉलleaf_add, कोई कॉल या पूंछ कूद नहीं है, और फिर कॉल करने वाले में कॉलली के शरीर के आकार की तलाश करता हैः लक्ष्य को हटा दिया गया है के साथ mnemonic और स्रोत ऑपरेन्ड, तो add w8, w1, w0AArch64 कॉलर्स मैचों में add w0, w1, w0एक मैच सबूत है।

dispatchदोनों को जोड़ता हैः एक 16 प्रविष्टि कूद टेबल जिसका प्रत्येक मामला है movl %esi, %edi; jmp fN@PLT. पहचानकर्ता एक स्विच और 16 टेल कॉल रिपोर्ट करता है, सभी स्रोत में 16 कॉल के खिलाफ सत्यापित।

शाखाएँ जो डेटा बन गईं

clamp_maxहै movl %esi, %eax; cmpl %esi, %edi; cmovgl %edi, %eax. मूल्यांकनकर्ता के नाम %ediजैसे aऔर %esiजैसे b, तुलना रिकॉर्ड करता है, और पढ़ता है cmovgजैसे a > b ? a : b, जो स्रोत पाठ है। abs_intहै movl %edi, %eax; negl %eax; cmovsl %edi, %eaxऔर यह पढ़ता है -x < 0 ? x : -x; AArch64 इसे लिखता है cmp w0, #0; cneg w0, w0, miऔर यह पढ़ता है x < 0 ? -x : x. .is_posहै xorl %eax, %eax; testl %edi, %edi; setg %al, जो कि पढ़ता है (x > 0). . ये हैं .-fif-conversionजीसीसी के शब्दों में और cmovLLVM में चयन। LLVM में X86CmovConversionपास एक बदल सकता है cmovशाखाओं में वापस जब यह मुनाफादायक का न्याय, यही कारण है कि एक ही स्रोत लूप में किसी भी आकार दिखा सकते हैं।

-O0इनमें से कोई भी अस्तित्व में नहीं है।clamp_maxतुलना है, एक jleएक ही स्लॉट में दो दुकानें, और एक लोड. पहचानकर्ता के लिए रिपोर्ट नहीं करता है।-O0और branchless selectसे-O1, जो आंकड़े के दृश्यता के तथ्यों में से एक है।

mul9एक हैleal (%rdi,%rdi,8), %eax, और पहचानकर्ता रिपोर्ट strength reductionके साथx * 9, क्योंकि स्रोत 9 से गुणा करता है यह केवल जब स्रोत में कारक है; एक leaजो एक तालिका सूचकांक पैमाने पर है एक गुणा नहीं है।

दो कठोर विशेषताएं जो मूर्खता की तरह दिखती हैं

स्टैक प्रोटेक्टर एक संकलक सुविधा है, और यह एक आकार छोड़ देता है कि एक एजेंट अन्यथा प्रोग्राम तर्क के रूप में पढ़ता है। canary.c-fstack-protector-strongx86-64 के लिए लिनक्स देता हैः

text       7: 64 48 8b 04 25 28 00 00 00   	movq	%fs:0x28, %rax
      10: 48 89 44 24 40               	movq	%rax, 0x40(%rsp)
      26: 64 48 8b 0c 25 28 00 00 00   	movq	%fs:0x28, %rcx
      2f: 48 3b 4c 24 40               	cmpq	0x40(%rsp), %rcx
      34: 75 05                        	jne	0x3b <with_canary+0x3b>
      3b: e8 00 00 00 00               	callq	0x40 <plain_leaf>
		000000000000003c:  R_X86_64_PLT32	__stack_chk_fail-0x4

%fs:0x28है stack_guardglibc में tcbhead_t, बाइट ऑफसेट 40 पर, और LLVM के getIRStackGuardप्रोग्यू बफर के ऊपर की गार्ड को कॉपी करता है, एपिलॉग तुलना करता है, और विफलता पथ कॉल करता है__stack_chk_fail. AArch64 लिनक्स पर गार्ड वैश्विक से आता है .__stack_chk_guardके माध्यम से GOT के साथ adrpऔर ldr, और विफलता है bl __stack_chk_fail. पहचानकर्ता गार्ड स्रोत, स्लॉट, तुलना, और विफलता कॉल रिपोर्ट करता है. plain_leaf, जिसमें कोई सरणी नहीं है, कोई कैनरी नीचे नहीं है strong, जो सरणी के साथ कार्यों की रक्षा करता है, allocaशोध नोट्स में MSVC फॉर्म भी दर्ज किया गया है।/GS, एक कुकी मिश्रित %rspऔर द्वारा जाँच की गई__security_check_cookie; इस मशीन पर कोई MSVC लिंकर मौजूद नहीं है, इसलिए उस आकार को केवल संकलक के असेंबली आउटपुट से वर्णित किया जाता है।

-fcf-protection=fullडालता हैendbr64, बाइट्स f3 0f 1e faयह नियंत्रण प्रवाह प्रवर्तन के साथ प्रोसेसर पर अप्रत्यक्ष शाखाओं के लिए एक लैंडिंग पैड है, और यह एक के रूप में निष्पादित करता हैnopअन्य जगहों पर. Ghidra के x86-64 समारोह-शुरू पैटर्न में शामिल हैं endbr64 के पूर्ववर्ती संस्करणpush rbp; mov rbp, rspइस कारण से. पहचानकर्ता इसे रिपोर्ट करता हैcet landing pad, तो एक फ़ंक्शन जो चार असामान्य बाइट्स से शुरू होता है डेटा के लिए गलत नहीं है.

जो विघटनकारी फोल्ड करते हैं

पाठ 37 में हर डिसीम्पिलर इन व्युत्पन्नों में से कुछ को रीस्क्रिप्ट नियम के रूप में चलाता है।ruleaction.cc. .RuleDivOpt"INT_MULT को INT_DIV या INT_SDIV में परिवर्तित करें और फॉर्म को शिफ्ट करें", जिसमें फॉर्म sub( (zext(V)*c), d) >> e => V / (2^n/(c-1)) where n = d*8 + eऔर हस्ताक्षरित संस्करण sextऔर s>>. .RuleModOpt" INT_REM और INT_SREM को अनुकूलित करने वाले अभिव्यक्ति को सरल बनाना " है। RuleDivTermAddअतिरिक्त सुधार को संभालता है, RuleSignDiv2घूमते हैं(V + -1*(V s>> 31)) s>> 1मेंV s/ 2और RulePositiveDivपाठ 37 ने Ghidra 12.1.4 को पाठ 33 के लिए कैप्चर किया।gradeपर-O1, और आउटपुट पढ़ता है uVar2 = param_1 / 10 - 6;डिवीजन को ढँक दिया गया है।

इन नियमों के लिए इनपुट जावा के बिना दिखाई देता है। venv के पाइपकोड 4.0.1 उसी SLEIGH विनिर्देश के साथ उठता है जो Ghidra उपयोग करता है, और code/fixtures/idioms-x86_64-O2.lifts.jsonके लिए कच्चे पी-कोड रखता है div10s: सात निर्देशों के लिए 112 प्रविष्टियाँ, जिनमें से 7 हैं IMARKमार्कर जो प्रत्येक निर्देश को खोलते हैं, उनमें से RAX = RAX * unique[95a00:8]के बादunique[95a00:8] = sext(0x66666667),RCX = RCX >> unique[d1a00:4]और RAX = RAX s>> unique[c5c00:4]. . .shrq41 संचालन करता है और sarq40 पर है, और उनमें से अधिकांश ध्वज की गणना करते हैं।RuleDivOptइस धारा में गुणा और दो शिफ्ट के साथ मेल खाता है, और मृत कोड को समाप्त करने के लिए ध्वज है कि कुछ भी नहीं पढ़ता हटा देता है.

Angr 10.0.3 हमारे पर चला गया -O2वस्तु, तथाidioms-x86_64-O2.angr.jsonयह 20 कार्यों के लिए अपने डिकंपिलर आउटपुट रखता है। यह अनसीन रूप को तह करता हैः div10uहै return a0 / 10;. यह हस्ताक्षरित फॉर्म को नहीं लपेटता हैः div10sहै v1 = a0 * 1717986919; return ((long long)(v1) >> 0x22) + (v1 >> 63);और mod10sहै a0 - (...) * 2 * 5. . के लिए .div7uयह प्रिंट करता है (a0 / 7 + ((a0 * 6 / 7 & 0xffffffff) >> 1 & 0xffffffff) & 0xffffffff) >> 2, जहां फिक्सअप शब्द अंकगणित के रूप में जीवित रहते हैं। यह तहmul9a0 * 9,linear_switch(a0 < 7 ? a0 * 10 + 10 : 0xffffffff),clamp_max((int)a1 < (int)a0 ? a0 : a1),is_posa0 > 0और fillreturn memset(a0, 0, a1);. . यह प्रिंट करता है .table_switchएक भार के रूप में*(int *)(4 * a0 + 4195400)मानों के बिना, sum_nके साथ_mm_add_epi32और _mm_shuffle_epi32अंतर्निहित और tail_callerजैसे tail_target(); return;तर्क खो गया है।digestकूदने की मेज बन जाती है goto *((void *)(...))टेबल अंकगणित के साथ लिखा है।

रडार2 6.2.4 और रिज़िन 0.9.1 स्रोत से अनुसंधान कैश में निर्मित, एक ही वस्तु पर चलाया गया था।pdcछापें div10sजैसे rax = rax * 0x66666667; rcx >>>= 0x3f; rax >>= 0x22; eax += ecx, रजिस्टर स्तर के बिना तह के छद्म-सी, और table_switchजैसे eax = dword [rcx + rax*4]एक के साथ RELOC 32 .rodatalea. रिज़िन में कोई अंतर्निहित डिसीम्पिलर नहीं है; इसका aoi के RzIL को प्रिंट करता हैimulएक 128-बिट उत्पाद के रूप में. lldb-1703.0.236.21 ELF वस्तु और उसके disassemble -n div10sवही सात निर्देश प्रिंट करता है llvm-objdumpकैपस्टोन 5.0.7 एक ही बाइट्स को डिक्रिप्ट करता है और समूहों की रिपोर्ट करता है जैसे किretऔर mode64यह एक डिकोडर है, और एक भाषा कभी भी एक डिकोडर के आउटपुट में नहीं है। IDA प्रो और बाइनरी निंजा यहां नहीं चलाए गए थे। उनके दस्तावेज में ऐसे चरणों का वर्णन किया गया है जहां इस तरह का पुनर्लेखन होता है, माइक्रोकोड अनुकूलन और एमएलआईएल से एचएलआईएल पास होता है, और यह सबक यह दावा नहीं करता है कि वे किस भाषा को फोल्ड करते हैं।

संकलक एक्सप्लोरर आगे दिशा के लिए उपकरण है. पेस्ट idioms.c, "x86-64 clang 18.1.0" या "ARM64 GCC 14.2.0" जैसे संकलक प्रविष्टि चुनें, और ध्वज सेट करें। सेवा में लगभग 1,050 C संकलक प्रविष्टियों की सूची है और इसमें एक एपीआई हैः GET /api/compilers/cपहचानकर्ता लौटाता है और POST /api/compiler/<id>/compileमैट गोडबोल्ट के 2019 एसीएम कतार लेख में इस उपकरण के साथ विभाजन, जनसंख्या गणना, चेन सशर्त और योगात्मक बोलियों के माध्यम से चलता है। इसे जीसीसी आउटपुट के लिए उपयोग करें, जिसे यह मशीन उत्पन्न नहीं कर सकती है, और जीसीसी के कूद तालिका के सीमाओं और तुलना करें।-O2फिक्स्चर में क्लिंग आउटपुट के साथ GCC 12 से वेक्टरिज़ेशन डिफ़ॉल्ट।

इसे बनाओ

डेमो चलाएँः

bashcd phases/13-tools-and-protocols/39-compiler-idioms-and-optimization
python3 code/main.py

आउटपुट एक JSON रिपोर्ट है। 18 बिल्ड में से प्रत्येक के लिए यह प्रकार, स्रोत रूप, सबूत पते, सत्यापन और विवरण क्षेत्रों के साथ प्रत्येक फ़ंक्शन और इसके बोलियों की सूची देता है। यह प्रति बिल्ड एक प्रकार मैट्रिक्स के साथ समाप्त होता है, -O2बनाम -O3दोनों वास्तुकलाओं के लिए तुलना, और unverifiedसूची।

अपेक्षित आकारः

json{
  "builds": {
    "idioms-x86_64-O2": {
      "arch": "x86_64", "level": "O2", "flags": "x86_64",
      "functions": {
        "div7u": [{"kind": "division", "source": "x / 7", "evidence": ["0x30", "0x32", "0x39", "0x3d", "0x3f", "0x41", "0x43"], "verified": true, "form": "magic multiply with add fix-up", "magic": "0x24924925", "effectiveMagic": "0x124924925", "shift": 35, "...": "..."}],
        "table_switch": [{"kind": "switch", "source": "switch (k) as lookup table", "table": ".rodata+0x28", "entries": 7, "values": [10, 20, 30, 40, 50, 60, 71], "...": "..."}],
        "sum_n": [{"kind": "vector loop", "lanes": 4, "accumulators": 2, "elementsPerIteration": 8, "...": "..."}]
      }
    }
  },
  "kindMatrix": {"idioms-x86_64-O2": {"division": 5, "modulo": 3, "switch": 6, "vector loop": 3, "...": "..."}},
  "sameCodeAtO2AndO3": {"x86_64": {"identical": true}, "arm64": {"identical": false, "differences": ["..."]}},
  "unverified": []
}

पढ़िए code/main.pyइस क्रम मेंः

parse_listing()llvm-objdump -d -rदोनों वास्तुकला के लिए कार्यों, निर्देशों और संलग्न स्थानों में पाठ।
ElfFileखंड, प्रतीकों को पढ़ता है, और .rela.*प्रविष्टियाँ, तथाwords()तालिका प्रविष्टियों को पढ़ता है।
magic_numbers(),divisor_from_magic()और evaluate_division()आगे, पीछे और निर्देश अनुक्रम के रूप में ग्रैनलंड-मोंटगोमी व्युत्पन्न हैं।
parse_source()C फ़ाइल से निर्माण की आवश्यकताओं को निकालना।
Evaluatorब्लॉक-दर-ब्लॉक प्रतीकात्मक पास है कि नाम रजिस्टर और स्टैक स्लॉट है।
find_divisions()और find_modulos()गुणा, शिफ्ट, फिक्स-अप, गुणा-बैक, और दो-शक्ति के रूपों के साथ मेल खाता है।
find_switches()कूद तालिकाओं, खोज तालिकाओं, रैखिक मानचित्रों, चयनित श्रृंखलाओं, तुलना पेड़ और तुलना श्रृंखलाओं को वर्गीकृत करता है।
find_vector_loops(),find_unrolled_loops(),find_tail_calls(),find_inlined_calls(),find_selects(),find_memory_builtins(),find_stack_protector(),find_cet()और find_strength_reduction()बाकी को कवर करें।
analyze_function()उन्हें क्रम में चलाता है, प्रत्येक भाषा के परिणाम नाम को अगले मूल्यांकनकर्ता पास में खिलाता है।

तीन और आदेश मौजूद हैं।python3 code/main.py scan FILE.objdump.txt [FUNCTION]एक सूची पर पहचानकर्ता चलाता है, वस्तु और इसके बगल में मिलान सी फ़ाइल के साथ. python3 code/main.py magic DIVISOR [signed]गुणक, शिफ्ट, त्रुटि, और क्या पहचान किनारे मान पर पकड़ता है प्रिंट करता है। python3 code/main.py figure-dataआंकड़े में एम्बेड किए गए डेटा को प्रिंट करता है।

इसका प्रयोग करें

इस क्रम में पहचानकर्ता का उपयोग करें एक नए वस्तु पर आप बनाया है।

पकड़ llvm-objdump -d -rऑब्जेक्ट से और इसके साथ सटीक संकलक कमांड रखें। पहचानकर्ता सूची हेडर से वास्तुकला पढ़ता है।
दौड़ेंscanसूची पर और पढ़ें unverifiedप्रत्येक या तो एक निर्माण स्रोत विश्लेषक नहीं देखा है या एक आकार पहचानकर्ता गलत पढ़ा है, और दोनों सबूत पते पर एक नज़र के लायक हैं.
प्रत्येक विभाग के लिए, पढ़ें algorithmक्षेत्र।clangMatchesAlgorithmसही है, संकलक ने सबसे छोटी वैध शिफ्ट का चयन किया है। जब यह गलत है, संकलक के पास एक कारण था जो आप अभी तक नहीं जानते हैं; स्थिरांक लिखें।
प्रत्येक स्विच के लिए, तुलना करें loweringएक तालिका जो एक पेड़ बन जाता है, या एक पेड़ जो एक तालिका बन जाता है, एक सीमा है कि आप LLVM स्रोत से नाम कर सकते हैं चिह्नित करता है।
हर लूप के लिए, पढ़ें elementsPerIterationऔर scalarRemainderLoop, तो पुष्टि दो पीछे किनारों पाठ 33 रिपोर्ट एक स्रोत लूप हैं.
एक ही वस्तु पर एक डिकोम्पाइलर चलाएं, प्रत्येक शब्द के बगल में उसका पाठ उद्धृत करें, और रिकॉर्ड करें कि उसने कौन से फोल्ड किए। यह रिकॉर्ड पाठ 45 के लिए आधार रेखा है।

इंटरैक्टिव लैब

लैब एः एक जादुई संख्या प्राप्त करें, फिर इसे खोजें

codeनिर्देशिका, खुला पायथनः

bashcd phases/13-tools-and-protocols/39-compiler-idioms-and-optimization/code
python3 -q

दौड़ें:

pythonfrom main import *
magic_numbers(10), magic_numbers(10, signed=True)
magic_numbers(7), magic_numbers(7, signed=True)
divisor_from_magic(0x66666667, 34, signed=True), divisor_from_magic(0x66666667, 33, signed=True)

गणना ceil(2^35 / 10)पहले कॉल से पहले कागज पर। फिर एक फ़ंक्शन जोड़ें unsigned div13(unsigned x) { return x / 13; }idioms.c, इसे निर्माण पर -O2आदेश के साथ build_fixtures.sh, और सूची में निरंतर की जाँच करें magic_numbers(13). .

लैब बीः टेबल और पेड़

pythonlisting = load_listing("idioms-x86_64-O2.objdump.txt")
elf = load_elf("idioms-x86_64-O2.o")
sources = load_source("idioms.c")
[i.to_dict() for i in analyze_function(listing, "table_switch", elf, sources)]
[i.to_dict() for i in analyze_function(listing, "sparse_switch", elf, sources)]
elf.words(".rodata", 0x28, 7)

परिवर्तन71वापस 70table_switch, पुनर्निर्माण में -O2, और देखने के लिए खोज तालिका एक रैखिक नक्शा बन जाता है. फिर एक मामले मूल्य को 1000 में बदलते हैं और देखने के लिए यह एक रहता हैArrayKindमेज.

लैब सीः तीन सेटिंग्स पर लूप

pythonfor name in ("idioms-x86_64-O1", "idioms-x86_64-O2", "idioms-x86_64-novec-O2"):
    print(name, [i.source for i in analyze_function(load_listing(name + ".objdump.txt"), "sum_n", load_elf(name + ".o"), sources)])

नियंत्रण प्रवाह ग्राफ को रेखांकित करें sum_nपर-O2हाथ से, गार्ड, मास्क, वेक्टर शरीर, घटाने, और शेष लूप को चिह्नित करें, और तुलना करें detailक्षेत्र।

लैब डीः साझा गुणांक

pythonfor name in ("idioms-x86_64-O1", "idioms-arm64-O1"):
    print([(i.kind, i.source, i.detail.get("sharedQuotient")) for i in analyze_function(load_listing(name + ".objdump.txt"), "digest", load_elf(name + ".o"), sources)])

-O1digestऔर x86-64 पर अपने संकेत फिक्स-अप के साथ गुणांक को जोड़ने के लिए दो निर्देशों को खोजने के लिए। फिर समझाएं कि AArch64 निर्माण केवल एक की आवश्यकता क्यों है।

अभ्यास प्रयोगशाला

फिक्स्चर में बिट ट्रिक्स जोड़ें और पहचानकर्ता को बढ़ाएं।

आवश्यकताएँः

लिखें popcount,ctzऔर rotlGCC के निर्माण और एक शिफ्ट-या घूर्णन के साथ कार्यों, उन्हें निर्माण पर -O2साथ और बिना-mpopcnt -mbmi, और अपनी सूची के साथ वस्तुओं को संलग्न करें.
0x55555555,0x33333333,0x0f0f0f0f,0x01010101जनसंख्या-गणना अनुक्रम जो TargetLowering::expandCTPOPउत्सर्जन करता है, और इसे रिपोर्ट करता हैpopcountचार स्थिरांक के साथ सबूत के रूप में।
पहचानें rep bsflके रूप में tzcnt- या ...bsfकोडिंग और roll %clके रूप में घूर्णन, और दोनों को बिल्डिन में डिकोड.
नई प्रजातियों को जोड़ें parse_source()सत्यापन, तो एक popcountभाषा केवल तभी सत्यापित की जाती है जब स्रोत कॉल करता है __builtin_popcount. .
प्रति भाषा एक परीक्षण जोड़ा जो फिक्स्चर सूची से स्थिरांक पढ़ता है।

सफलता का अर्थ हैpython3 code/main.pyverified: trueदोनों निर्माण में, और सूट अभी भी एक खाली रिपोर्ट unverifiedसूची।

पाठ कलाकृतियाँ

इस सबक में शामिल है outputs/skill-compiler-idioms-and-optimization.md. इसका उपयोग किसी सूची, वस्तु और उसके स्रोत को एक सत्यापित भाषा रिपोर्ट में डिकोम्पाइलर तुलना के साथ बदलने के लिए करें. इसमें प्रत्येक दावे के लिए साक्ष्य पते, प्रत्येक विभाजन के लिए जादुई संख्या व्युत्पन्न, प्रत्येक स्विच के लिए घटाने के प्रकार और प्रवेश स्रोत और प्रत्येक भाषा के लिए उद्धृत डिकोम्पाइलर लाइन की आवश्यकता होती है।

जाँचें

डेमो और निर्धारक सूट चलाएंः

bashcd phases/13-tools-and-protocols/39-compiler-idioms-and-optimization
python3 code/main.py
python3 -m unittest discover -s code/tests -v

सत्यापन से साबित होना चाहिएः

सूची पार्सर से 25 फ़ंक्शन पढ़ता है -O2वस्तु, बाइट्स रखता है, और संलग्न करता है R_X86_64_PC32 .rodata+0x24leaqमें table_switch
ELF रीडर रिटर्न [10, 20, 30, 40, 50, 60, 71]से.rodata+0x28और दस स्थानान्तरण .rela.rodata
magic_numbersरिटर्न 0xcccccccdशिफ्ट 35 के साथ।0x6666666734 के साथ, 0x12492492535 और अतिरिक्त फॉर्म के साथ, 0x5555555632 के साथ, तथा0xaaaaaaab33 के साथ
पहचान प्रत्येक विभाजक के लिए 32 बिट किनारे मानों पर holds 2 से 64 जो दो की शक्ति नहीं है, हस्ताक्षरित और हस्ताक्षरित नहीं
divisor_from_magicअपने जोड़े से 10, 5, 7 और 3 को ठीक करता है और गलत जोड़े को अस्वीकार करता है
जोड़ फिक्स-अप अनुक्रम गणना n // 7ठीक है
चार x86-64 विभाजन दाएं गुणक, शिफ्ट, विभाजक और रूप, और चार AArch64 विभाजन को डिकोड रिपोर्ट movऔर movk
-O0उपयोगdivlऔर idivl,-O0 -fast-isel=falseगुणन का उपयोग करता है, और digestपर-O0दोनों को मिलाता है
मॉड्यूल को मल्टी-बैक के रूप में मान्यता प्राप्त है,msub, दो शक्ति, sdivऔर mulऔर subs, और हार्डवेयर idivl
एक साझा गुणांक दोनों विभाजन और मॉड्यूल पर रखता है -O1
पांच घटावों को वर्गीकृत किया गया है -O2दोनों वास्तुकला पर, सूत्र, मानों, लक्ष्यों, पिवोट और चयनित अभिव्यक्ति के साथ
-O0स्विच x86-64 पर कूद टेबल हैं और AArch64 पर श्रृंखला की तुलना करें
digestस्विच एक कूद तालिका है, फिर एक तह कारक 16 के साथ एक खोज तालिका, फिर एक कूद तालिका है चार अलग लक्ष्य पर x86-64, और एक तुलना पेड़ पर AArch64 पर रेंज परीक्षण 9 से 10 के साथ
-fno-jump-tablesतुलना के पेड़ पैदा करता है, और 16 मामले dispatchx86-64 पर स्थानांतरणों और AArch64 पर संपीड़ित बाइट तालिका से अपने लक्ष्य को पढ़ता है
वेक्टर लूप रिपोर्ट 4 लेन, 2 accumulators, 8 तत्व प्रति पुनरावृत्ति, मुखौटा, गार्ड, कमी, और शेष लूप
फिक्स्ड-ट्रिप लूप्स पूरी तरह से वेक्टरिज़ेड या पूरी तरह से अनरोल्ड हैं, और -fno-vectorize8 तक रोल
-O1कोई वेक्टरिज़ेशन नहीं है, -O2और -O3x86-64 पर समान हैं, और AArch64 पर वे केवल call_switch, जहां -O3इसमें 17 निर्देश हैं और -O218 है
-fno-builtinस्टोर लूप को वेक्टरized स्टोर लूप में बदल देता है और रखता है memcpyएक कॉल
पूंछ कॉल, memsetप्रतिस्थापन, इनलाइन 16-बाइट प्रति, और -O0दो-चलन प्रतिलिपि को पहचानना
इनलाइन की गई कॉल से पाया जाता है -O1शरीर के आकार से
से decode चुनता हैa > b ? a : b,-x < 0 ? x : -x,(x > 0)और sum % 10 < 5 ? sum % 10 : 5
स्टैक प्रोटेक्टर रिपोर्ट %fs:0x28, स्लॉट, और __stack_chk_failऔर endbr64सीईटी बिल्ड के प्रत्येक कार्य पर रिपोर्ट किया जाता है
स्रोत पार्सर फ़ंक्शन-पॉइंटर पैरामीटर, स्विच केस, कॉल और accumulator नाम पढ़ता है
हर निर्माण में हर बोली सत्यापित है और प्रकार मैट्रिक्स मेल खाते हैं
इंटरैक्टिव आंकड़ा विश्लेषण द्वारा उत्पन्न किए गए समान डेटा को शामिल करता है

उत्पादन विफलता मोड

Failure	What the weak tool reports	What the analysis must prove
Multiply by a large odd constant	"multiplies by 1717986919"	The constant is `ceil(2^s / d)` for one `d`, the error satisfies the bound, and the shift is the smallest valid one
Add fix-up after a 32-bit shift	Five arithmetic instructions	The multiplier is 33 bits wide and the tail is the add form of the same method
Same multiplier, different shift	The same divisor	The shift selects the divisor: 34 is 10, 33 is 5
Power-of-two signed modulo	"adds 7, masks, subtracts"	The bias rounds toward zero and the result is `x % 8`
Indexed load from `.rodata`	"a jump table"	A lookup table of values, with entries read from the bytes at addend plus 4
Affine arithmetic and a `cmov`	"computes 10k + 10"	A switch lowered as a linear map, verified against every source case
Compare chain with ordered splits	"a sequence of ifs"	A binary search over the case constants with the pivots named
Backward branch to a default block	"a loop"	The target leaves the region with an unconditional jump; it is a shared tail
Two back edges in one function	"two loops"	One source loop: the vector body and its scalar remainder
`jmp memset@PLT` with no `ret`	"the function has no return"	A tail call that returns through the callee, replacing a store loop
Callee missing from the call graph	"never called"	Inlined: the callee's body shape appears in the caller
`%fs:0x28` load and compare	"reads thread-local data"	The stack protector canary, with the fail path to `__stack_chk_fail`
Four odd bytes at function start	"data before the function"	`endbr64`, the CET landing pad
Decompiler shows raw arithmetic	"the tool is wrong"	The tool did not apply a fold; the derivation gives the source form and the quoted output records the gap

परिचालन नियम

आकार को मेल खाएं, व्युत्पन्न को पीछे की ओर चलाएं, और इसे साबित करने वाले स्थिर लिखें। हर बोली को उसके सबूत पते और उसके डिकोड स्रोत फॉर्म के साथ रिपोर्ट करें, प्रत्येक को आपके द्वारा संकलित स्रोत के खिलाफ सत्यापित करें, और उद्धृत करें कि प्रत्येक डिकोम्पिलर ने एक ही बाइट के लिए क्या प्रिंट किया है।

आगे पढ़ना

This free lesson is part of the AI Engineering from Scratch curriculum. Read the full explanation, run the lesson code, and verify the result in the interactive reader or from the repository source.

Browse the complete course catalog or open this lesson on GitHub.