اصطلاحات کامپایلر: بهینه‌سازی چگونه کد را دگرگون می‌کند و چطور آن را رمزگشایی کنیم

وقتی کد باینری حاصل از سطوح بهینه‌سازی مثل -O2 یا -O3 را بررسی می‌کنید، شباهت چندانی میان اسمبلی خروجی و منطق سورس اولیه نمی‌بینید؛ برای نمونه یک تقسیم ساده ممکن است به ضربی نامفهوم با یک عدد بزرگ و چند شیفت بیت تبدیل شود، یا یک دستور switch بدون هیچ پرشی در قالب یک نگاشت خطی یا جدول جستجو پیاده‌سازی شود. این الگوها تصادفی نیستند، بلکه اصطلاحات فنی کامپایلر (Compiler Idioms) به شمار می‌روند که هرکدام اثبات ریاضی و ساختار مشخصی دارند.

در پروژه‌های تحلیل بدافزار، مهندسی معکوس و ممیزی امنیتی نرم‌افزار، تکیه‌ی صِرف به دیکامپایلرها ریسک بالایی دارد؛ چرا که حتی ابزارهای معروفی چون Ghidra و angr گاهی این الگوها را تشخیص نمی‌دهند و محاسبات خام را تحویل می‌دهند. درک دقیق منطق این بهینه‌سازی‌ها به شما امکان می‌دهد با معکوس‌کردن محاسبات، ساختار اصلی کد C را مستقیماً از اسمبلی بازیابی کنید.

این درس به شما آموزش می‌دهد چطور الگوهای تبدیل تقسیم به ضرب، دگرگونی حلقه‌ها (برداری‌سازی و بازکردن)، انواع ساختارهای switch و فراخوانی‌های انتهایی را روی دو معماری x86-64 و AArch64 شناسایی کنید و با نوشتن یک ابزار ارزیابی، صحت هر الگو را در برابر کد مبدأ بسنجید.

کامپایلر بهینه‌ساز، ساختارهای کد منبع را با الگوهای دستورالعملی ارزان‌تر جایگزین می‌کند. هر الگو اثبات ریاضی (Derivation) خودش را دارد؛ در این درس ابزار شناسایی می‌سازیم که این روابط را معکوس اجرا می‌کند و درستی خروجی را با کد منبع می‌سنجد.

اهداف یادگیری

• به‌دست‌آوردن عدد جادویی (Magic number) و مقدار شیفت برای تقسیم بر هر ثابت با کران گرنلوند–مونتگومری (Granlund-Montgomery)، و بازیابی مقسوم‌علیه از ثابت‌هایی که clang تولید کرده است.
• نام بردن پنج روش تبدیل ساختار switch در LLVM و خواندن تعداد درگاه‌ها، آدرس جدول و درگاه‌ها از فایل شیء (Object file).
• تحلیل یک حلقه‌ی برداری‌شده در قالب خطوط پردازش موازی (Lanes)، انباره‌ها (Accumulators)، تعداد اعضا در هر تکرار، ماسک شمارش دفعات اجرای حلقه (Trip-count mask)، تقلیل (Reduction) و حلقه‌ی باقیمانده (Remainder loop).
• تشخیص فراخوانی‌های انتهایی (Tail calls)، توابع جای‌گذاری‌شده (Inlined callees)، گزینش‌های بدون انشعاب (Branchless selects) و حلقه‌هایی که به memset یا memcpy تبدیل شده‌اند.
• گزارش هر اصطلاح فنی (Idiom) همراه با دستورالعمل‌های شواهد (Evidence) و شکل رمزگشایی‌شده‌ی (Decoded) آن در کد منبع، روی x86-64 و AArch64، در سطوح -O0 تا -O3.
• مقایسه‌ی نتیجه با آنچه Ghidra، angr، radare2، rizin و lldb برای همان بایت‌ها نشان می‌دهند.

صورت مسئله

فایل idioms.c را با -O2 کامپایل کرده‌اید و از یک ایجنت (Agent) پرسیده‌اید تابع div7u چه می‌کند. ایجنت با خواندن imulq $0x24924925, %rax, %rax پاسخ داده که تابع در 613566757 ضرب می‌کند، شیفت می‌دهد و جمع می‌بندد. تک‌تک این کلمات درست است؛ تابع x / 7 را محاسبه می‌کند.

در همان فایل شیء، یک switch با هفت شرط وجود دارد که هیچ پرشی ندارد، یک switch با پنج شرط که یک جدول پرش (Jump table) است، یک switch با دو شرط که از sete و cmovne ساخته شده، و حلقه‌ای روی n عدد صحیح که در هر تکرار هشت عدد صحیح را در دو ثبات xmm پردازش می‌کند و بقیه را در حلقه‌ی دوم به پایان می‌رساند. در سطح -O0 همین منبع، دستور divl، جداول پرش هفت‌درگاهی و یک حلقه‌ی اسکالر تولید کرده بود. در سطح -O1 همان سوییچ هفت‌شرطی به جدول مقادیر تبدیل شد و حلقه‌ی برداری هنوز وجود نداشت.

این الگوها اصطلاح فنی هستند. کامپایلر هر کدام را بر اساس قاعده‌ای تولید می‌کند که می‌توانید در کد منبع آن بخوانید، و هر یک را می‌توان به ساختار منبع اولیه‌اش رمزگشایی کرد. این رمزگشایی حساب و کتاب ریاضی است، و ریاضی را می‌توان آزمود. درس 34 یکی از آن‌ها یعنی ضرب در 0x66666667 را اثبات کرد. در این درس ابزار شناسایی همه‌ی آن‌ها را می‌سازیم، آن را روی 18 بیلد از کدهای خودمان اجرا می‌کنیم و تمام 373 گزارش را با کد منبع C می‌سنجیم.

اصطلاح فنی الگویی با اثبات ریاضی است

اصطلاح فنی، دنباله‌ای از دستورالعمل‌ها است که کامپایلر برای یک ساختار منبع خاص تولید می‌کند. سه ویژگی آن را قابل تشخیص می‌کند: شکل ثابتی دارد، عملوندها مقادیر ثابتی دارند که با اثبات ریاضی پیش‌بینی می‌شوند، و ساختار آن با آنچه برنامه‌نویس دستی می‌نویسد فرق دارد.

ابزار شناسایی در code/main.py روی متن خروجی llvm-objdump -d -r کار می‌کند؛ ابزاری که در درس 33 به‌عنوان مرجع قطعی مرزهای دستورالعمل تعیین شد. این اسکریپت هر تابع را به دستورالعمل‌هایی همراه با آدرس، بایت‌ها، نماد دستوری (Mnemonic)، عملوندها و خط بازنشانی (Relocation) پس از آن تجزیه می‌کند. فایل شیء را تنها به دو منظور می‌خواند: بایت‌های بخش .rodata که جدول مقادیر در آن قرار دارد، و درگاه‌های .rela.rodata که مقصد جدول‌های پرش پیش از پیوند در آنجا ذخیره می‌شوند.

هر مورد شناسایی‌شده یک رکورد Idiom با فیلدهای kind، شکل منبع رمزگشایی‌شده‌ی source، فهرستی از آدرس‌های شواهد evidence، دیکشنری detail و پرچم verified است. مقدار این پرچم از کد منبع C می‌آید. تابع parse_source() فایل idioms.c را می‌خواند، هر تابع را می‌یابد و مقسوم‌علیه‌های بعد از / و %، ضرایب بعد از *، حالت‌های switch و مقادیرشان، عملگرهای ? :، حلقه‌های for و توابع فراخوانی‌شده را بیرون می‌کشد. اصطلاح تقسیم زمانی تأیید می‌شود که مقسوم‌علیه آن در فهرست تقسیم‌های تابع در منبع وجود داشته باشد. جدول جستجو (Lookup table) زمانی تأیید می‌شود که درگاه‌های آن با مقادیر case در منبع (با احتساب یک ضریب ثابت) همخوانی داشته باشند. یک فراخوانی انتهایی زمانی تأیید می‌شود که تابع مقصد در متن منبع فراخوانی شده باشد. گزارش نهایی دمو با فهرستی از موارد تأییدنشده (unverified) تمام می‌شود، و مجموعه‌ی آزمون‌ها بررسی می‌کند که این فهرست برای هر 18 بیلد کاملاً خالی باشد.

رمزگشایی نیازمند نام‌گذاری است. ابزار شناسایی یک ارزیاب نمادین (Symbolic evaluator) کوچک را روی بلوک‌های پایه‌ای (Basic blocks) هر تابع و به ترتیب فهرست خروجی اجرا می‌کند، در حالی که نام پارامترهای کد منبع را در ثبات‌های آرگومان طبق قراردادهای System V و AAPCS64 (از درس 38) قرار داده است. اسلات‌های استک با متن عملوندشان ردیابی می‌شوند تا کد کامپایل‌شده در -O0 بتواند مقادیر ریخته‌شده روی استک (Spills) را بازشناسی کند. در ورودی هر بلوک، وضعیت‌های بلوک‌های قبلی ادغام (Merge) می‌شوند؛ جایی که مقادیر تفاوت دارند، نامی که یک اصطلاح فنی قبلی تخصیص داده بر یک مقدار ثابت برتری می‌یابد. به همین دلیل است که دستور cmovll %edx, %eax در تابع digest به‌شکل sum % 10 < 5 ? sum % 10 : 5 بازخوانی می‌شود: اصطلاح حلقه‌، انباره را sum نامید، اصطلاح تقسیم خارج‌قسمت آن را sum / 10 نام گذاشت، و اصطلاح باقیمانده خروجی را sum % 10 تعیین کرد. کد منبع به‌صورت rem > 5 ? 5 : rem نوشته شده است. هر دو عبارت مقدار کوچک‌تر بین rem و 5 را برمی‌گردانند و در نقطه‌ی rem == 5 یکسان‌اند.

تقسیم بر یک مقدار ثابت

گرنلوند و مونتگومری در مقاله‌ی «Division by Invariant Integers using Multiplication» (PLDI 1994) عمل n / d را با یک ضرب و یک شیفت جایگزین می‌کنند. مقدار شیفت s و ضریب m = ceil(2^s / d) را انتخاب کنید. در این حالت اگر خطای e = m * d - 2^s به‌اندازه‌ی کافی کوچک باشد، مقدار floor(n * m / 2^s) برای تمام مقادیر n در دامنه‌ی مورد نظر برابر با floor(n / d) خواهد بود. برای n بدون علامت 32 بیتی، کران مجاز e <= 2^(s - 32) است. برای n علامت‌دار با شرط |n| < 2^31 این کران e <= 2^(s - 31) است و در صورت منفی بودن n، اصلاح علامت با افزودن 1 انجام می‌شود؛ چون جزء صحیح (Floor) برای خارج‌قسمت‌های منفی تقریب را در جهت عکس اعمال می‌کند.

تابع magic_numbers(d, bits, signed) در main.py مقدار s را از 32 به بالا جستجو می‌کند و اولین جفتی را که در شرط کران صدق کند برمی‌گرداند. این جستجو تمام ثابت‌هایی را که clang در نمونه‌های آزمایشی تولید کرده بازتولید می‌کند.

محاسبه‌ی دستی برای عدد 10 بدون علامت

2^35 / 10 = 3435973836.8. سقف آن (Ceil) برابر با 3435973837 = 0xCCCCCCCD است. میزان خطا 0xCCCCCCCD * 10 - 2^35 = 2 است، و مقدار کران در s = 35 برابر با 2^3 = 8 خواهد بود. در s = 34 خطا برابر با 6 در برابر کران 4 می‌شد، پس 35 کوچک‌ترین شیفت ممکن است. بررسی با n = 123: حاصل‌ضرب 123 * 3435973837 = 422624781951 است و 422624781951 >> 35 = 12.

کامپایلر clang دقیقاً همین را برای div10u در سطح -O2 روی معماری x86-64 تولید می‌کند:

       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

مقدار 0x23 برابر 35 است. دستور movl %edi, %ecx با گسترش صفر (Zero-extension)، آرگومان 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 انجام می‌گیرد و شیفت در مبنای 10 نوشته می‌شود. ابزار شناسایی دو نیمه را سرهم کرده و همان مقسوم‌علیه را گزارش می‌کند.

محاسبه‌ی دستی برای عدد 7 بدون علامت، همراه با اصلاح جمع

2^35 / 7 = 4908534052.57. سقف آن 4908534053 = 0x124924925 است که به 33 بیت نیاز دارد. میزان خطا 3 در مقابل کران 8 است، بنابراین شیفت برابر 35 است و هیچ شیفت کوچک‌تری جواب نمی‌دهد. ضرب 32 بیتی نمی‌تواند این ضریب را نگه دارد؛ بنابراین کامپایلر در 32 بیت پایینی 0x24924925 ضرب می‌کند و مقسوم را طی یک توالی ثابت به حاصل بازمی‌گرداند:

      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 = 100: مقدار t = 14، سپس (100 - 14) >> 1 = 43، بعد 43 + 14 = 57 و در نهایت 57 >> 2 = 14. ابزار شناسایی توالی پایانی sub، shr، add و shr را پس از شیفت 32 بیتی تشخیص می‌دهد، مقدار 2^32 را به ضریب برمی‌گرداند و به مقسوم‌علیه 7 می‌رسد. تابع evaluate_division() دقیقاً همین توالی را اجرا می‌کند و آزمون مربوطه آن را روی مقادیر مرزی 32 بیتی با n // 7 می‌سنجد. قالب 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 است و clang از shrq $0x20 استفاده می‌کند. برای n = -7: حاصل‌ضرب -10021590362 می‌شود، شیفت حسابی در 32 نتیجه‌ی -3 را می‌دهد، بیت علامت 1 است، بنابراین گام اصلاحی 1 واحد اضافه می‌کند و نتیجه -2 می‌شود که برابر با -7 / 3 در C است. توابع نمونه‌ی علامت‌دار div10s و div3s هر دو این اصلاح را به‌صورت shrq $0x3f روی کپی حاصل‌ضرب و به‌دنبال آن addl پیاده می‌کنند.

نکاتی درباره‌ی مقادیر ثابت

یک ضریب به‌تنهایی مقسوم‌علیه را مشخص نمی‌کند. مقدار 0x66666667 با شیفت 34 به معنای عدد 10 است. همین ضریب با شیفت 33 مقسوم‌علیه 5 را نشان می‌دهد، همان‌طور که در درس 34 دیدیم. به همین دلیل، ابزار شناسایی همیشه ضریب را با مجموع شیفت جفت می‌کند، و فیلد clangMatchesAlgorithm ثبت می‌کند که آیا این جفت همانی است که الگوریتم جستجو تولید می‌کند یا نه. توان‌های 2 هرگز از ضرب استفاده نمی‌کنند. تابع magic_numbers() آن‌ها را رد می‌کند، چون کامپایلر به‌جای آن یک شیفت با بایاس علامت (Sign bias) تولید می‌کند؛ تابعی مثل mod8s در بخش بعد این شکل را نشان می‌دهد.

این اصطلاح فنی به گزینشگر دستورالعمل تعلق دارد

در سطح -O0، تابع div10u به‌صورت movl $0xa, %ecx; xorl %edx, %edx; divl %ecx کامپایل می‌شود. تابع div10s به‌شکل cltd; idivl %ecx درمی‌آید. در همان فایل شیء، تابع digest مجموع حلقه‌ی خود را با imulq $0x66666667 بر 10 تقسیم می‌کند. یک فلگ این تفاوت را توضیح می‌دهد: فایل نمونه‌ی idioms-x86_64-nofastisel-O0.o با آرگومان‌های -O0 -mllvm -fast-isel=false بیلد شده و در آن تمام تقسیم‌ها از نوع ضرب هستند، از جمله div10u با دستورات movl $0xcccccccd, %ecx; imulq %rcx, %rax; shrq $0x23. تقسیم سخت‌افزاری، انتخاب گزینشگر سریع دستورالعمل (Fast instruction selector) در -O0 است. ضرب، تبدیل سطح‌پایین‌تر SelectionDAG است؛ همان چیزی که UnsignedDivisionByConstantInfo و SignedDivisionByConstantInfo در LLVM تولید می‌کنند. بلوک digest که تقسیم را در بر دارد شامل یک switch نیز بود و آن بلوک تحویل SelectionDAG شد. ابزار شناسایی هر دو شکل یعنی 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 حساب کرده و هم برای اندیس switch و هم برای محاسبه‌ی باقیمانده به کار می‌برد. روی x86-64 حتی خارج‌قسمت را دو بار ترکیب می‌کند: leal (%rax,%rsi), %edi برای باقیمانده و addl %esi, %eax برای سوییچ. ابزار شناسایی یک تقسیم و یک باقیمانده گزارش می‌دهد و خارج‌قسمت را مشترک (Shared) علامت می‌زند. گزارشی که تقسیم را در اینجا جا بیندازد، خواندن اندیس switch را ناممکن می‌کند.

باقیمانده‌ی علامت‌دار بر توان‌های 2 الگوی ویژه‌ای دارد، چون خارج‌قسمت اصلاً محاسبه نمی‌شود:

      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 واحد بایاس اضافه می‌کند تا عمل هرس (Truncation) همان‌طور که استاندارد C الزام کرده به سمت صفر گرد شود. مقدار ماسک‌شده همان x گردشده به مضربی از 8 است و تفریق، مقدار x % 8 را باقی می‌گذارد. معماری AArch64 این کار را با negs w8, w0; and w9, w0, #0x7; and w8, w8, #0x7; csneg w0, w9, w8, mi انجام می‌دهد: هر دو مقدار x و -x را ماسک می‌کند، سپس بر اساس علامت یکی را برمی‌گزیند و اگر منفی بود قرینه می‌کند. ابزار Ghidra قاعده‌ی بهینه‌سازی خود را برای این مورد RuleSignMod2nOpt نام‌گذاری کرده و خلاصه‌ی آن چنین است: «تبدیل ساختارهای INT_SREM: فرم (V + (sign >> (64-n)) & (2^n-1)) - (sign >> (64-n)) => V s% 2^n».

در سطح -O0، معماری AArch64 باقیمانده را به‌شکل sdiv w9, w8, w10; mul w9, w9, w10; subs w0, w8, w9 می‌نویسد. ابزار شناسایی این الگو را نیز تشخیص می‌دهد و آن را hardware sdiv + mul + subs گزارش می‌کند.

پنج روش برای تبدیل دستور switch

محیط 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 و تحت گزینه‌ی -Os برابر 40 است. مابقی حالت‌ها به یک جستجوی دودویی روی مقادیر ثابت case تبدیل می‌شوند که در آن تابع splitWorkItem عنصر محوری (Pivot) را انتخاب می‌کند. فایل‌های نمونه برای هر یک از این حالات یک تابع دارند.

جدول جستجو، خوانده‌شده از فایل شیء

بررسی table_switch در سطح -O2:

      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 نشان‌دهنده‌ی 7 درگاه معتبر است. مقدار افزوده‌ی بازنشانی (Relocation addend) برابر با 0x24 به‌اضافه‌ی 4 بایت از فیلد وابسته به RIP، جدول را در آدرس .rodata+0x28 مستقر می‌کند؛ قاعده‌ای که در درس 33 به‌دست آمد. بایت‌های آن بخش 0a 00 00 00 14 00 00 00 ... هستند، بنابراین مقادیر درگاه‌ها [10, 20, 30, 40, 50, 60, 71] است که دقیقاً با مقادیر case در کد منبع مطابقت دارد. اسمبلر این جدول را در فایل .s با عنوان .Lswitch.table.table_switch و کامنت @switch.table.table_switch نام‌گذاری کرده بود. در فایل شیء تنها اطلاعات بازنشانی و بایت‌ها باقی می‌مانند. هیچ پرشی در کار نیست، در نتیجه گراف جریان کنترل (Control-flow graph) فقط سه بلوک دارد.

نسخه‌ی AArch64 آدرس جدول را با استفاده از adrp x8 و add x8, x8, #0x0 سرهم می‌کند که هر کدام بازنشانی اختصاصی خود را به .rodata دارند، و داده‌ها با دستور ldr w0, [x8, w0, uxtw #2] خوانده می‌شوند. ابزار شناسایی مقدار افزوده را از بخش بازنشانی دستور add می‌خواند.

نگاشت خطی، بدون نیاز به جدول

تابع linear_switch برای k در بازه‌ی 0 تا 6 مقدار 10 * (k + 1) را برمی‌گرداند. تابع simplifySwitchLookup این رابطه‌ی همگرای خطی (Affine) را شناسایی کرده و مستقیماً دستورات حسابی تولید می‌کند:

      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 می‌خواند. سپس ابزار شناسایی، این فرمول را با تک‌تک حالت‌های کد منبع تطبیق می‌دهد و اصطلاح را تأییدشده علامت می‌زند. معماری AArch64 به همین خروجی با دستورات madd w8, w0, w8, w9 و csinv w0, w8, wzr, lo می‌رسد؛ جایی که csinv همراه با wzr مقدار -1 را برای مسیر پیش‌فرض تولید می‌کند.

جدول پرش، خوانده‌شده از بخش بازنشانی‌ها

تابع call_switch در سطح -O2 همان ساختاری را دارد که در درس 33 برای تابع grade در سطح -O0 دیدیم: دستور cmpl $4; ja، یک leaq به .rodata-0x4، یک movslq برای خواندن درگاه 4 بایتی، addq و در نهایت jmpq *%rax. پنج درگاه موجود همان رکوردهای بازنشانی در .rela.rodata هستند، و رابطه‌ی target = addend - 4k مقادیر 0x10c, 0x107, 0x10e, 0x110, 0x109 را به‌دست می‌دهد؛ پنج بلوک مجزا که هر یک پرش انتهایی را از طریق یک اشاره‌گر تابع اجرا می‌کنند. فایل نمونه‌ی dispatch این روند را به 16 حالت تعمیم می‌دهد: 16 درگاه بازنشانی در x86-64، و در AArch64 یک جدول فشرده از 16 تک‌بایت که با ldrb w11, [x9, x8] خوانده شده، با add x10, x10, x11, lsl #2 در 4 ضرب می‌شود و مبنای آن یک دستور adr از اولین بلوک case است. ابزار شناسایی، آرایه‌ی [0x24, 0x74, 0x54, ...] را از جدول بایتی رمزگشایی کرده و گزینه‌ی compressed: true را گزارش می‌کند.

یک دستور switch در چهار سطح بهینه‌سازی مختلف

تابع digest یک سوییچ روی sum / 10 با حالت‌های 6 تا 10 و مقادیر 1، 2، 4، 8، 8 دارد و سپس حاصل را در 16 ضرب می‌کند. روی x86-64 در سطح -O0 یک جدول پرش است؛ در سطح -O1 به یک جدول جستجو با مقادیر [16, 32, 64, 128, 128] تبدیل می‌شود، و در سطوح -O2 و -O3 دوباره به یک جدول پرش تبدیل می‌شود که چهار بلوک case آن مقادیر 0x10، 0x20، 0x40 و 0x80 را ذخیره می‌کنند. از سطح -O1 به بالا ضرب در 16 به داخل caseها منتقل شده است. در سطح -O0 حالت‌ها مقادیر 1، 2، 4 و 8 را ذخیره می‌کنند و عملیات ضرب پس از سوییچ باقی می‌ماند. برای جدول جستجوی سطح -O1، ابزار شناسایی ورودی‌ها را با مقادیر منبع مقایسه می‌کند، نسبت ثابت را می‌یابد و foldedFactor: 16 را گزارش می‌دهد. در AArch64 ساختار سطح -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 و سوییچ تابع digest در معماری x86-64 به درخت مقایسه تبدیل شوند که در تابع هفت‌حالته از عناصر محوری 2 و 4 استفاده می‌کند. در AArch64 فلگ -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 وارد عمل می‌شوند، و آستانه (Threshold) جدول پرش از case-values-threshold گرفته می‌شود که مقدار پیش‌فرض آن وابسته به معماری ماشین است. روی این سیستم کامپایلر GCC نصب نیست، بنابراین این اسامی مستقیماً از سورس‌کد و مستندات GCC نقل شده‌اند و Compiler Explorer بهترین بستر برای آزمودن آن‌هاست.

حلقه‌ها: برداری‌شده، بازشده یا جایگزین‌شده

برداری‌ساز حلقه‌ی LLVM در سطوح -O2، -O3 و -Os فعال و در سطوح -O0 و -O1 غیرفعال است؛ این قاعده از زمان انتشار LLVM 3.4 در ژانویه‌ی 2014 برقرار بوده است. تابع sum_n در سطح -O2 تمام اجزای این ساختار را نشان می‌دهد:

     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 و فاکتور درهم‌تنیدگی (Interleave factor) برابر 2 است. پس از پایان حلقه، یک دستور paddd، دو pshufd، دو paddd دیگر و یک movd، هشت خط پردازش موازی را به یک عدد صحیح منفرد تقلیل می‌دهند. حلقه‌ی مستقر در آدرس 0x270 همان حلقه‌ی باقیمانده‌ی اسکالر برای پردازش 0 تا 7 عضو آخر است. ابزار شناسایی با کمک یال برگشتی (Back edge)، حلقه را پیدا می‌کند، ثبات‌های SIMD را می‌بیند، تعداد خطوط پردازش را از روی paddd می‌خواند، انباره‌های مجزا را می‌شمارد، گام 0x20 را بر 4 تقسیم می‌کند و مقدار 4 lanes x 2 accumulators = 8 elements per iteration را به همراه ماسک، شرط محافظ، بخش تقلیل و حلقه‌ی باقیمانده در فیلدهای گزارش درج می‌کند. معماری AArch64 همین کار را با ldp q2, q3، دو دستور add v.4s، یک دستور addv s0, v0.4s و در نهایت fmov w8, s0 انجام می‌دهد.

تعداد تکرار ثابت، خودِ حلقه را به‌کلی حذف می‌کند. تابع sum4 تنها از یک movdqu، بخش تقلیل و movd تشکیل شده و یال برگشتی ندارد. تابع poly8 نمی‌تواند برداری شود، زیرا هر تکرار به مقدار انباره در تکرار قبلی وابسته است؛ به همین دلیل کامپایلر آن را هشت بار باز (Unroll) می‌کند: هشت دستور بارگذاری در آفست‌های 0 تا 0x1c نسبت به %rdi، که هر کدام با یک شیفت 5 بیتی و یک تفریق دنبال می‌شوند تا مقدار acc * 31 را محاسبه کنند. ابزار شناسایی، بارگذاری‌ها را در آفست‌های متوالی از یک مبنا می‌شمارد و loop unrolled by 8, no back edge را گزارش می‌کند. در AArch64 همین مقادیر به‌صورت چهار جفت دستور ldp ظاهر می‌شوند.

اگر برداری‌ساز را با -fno-vectorize -fno-slp-vectorize غیرفعال کنید، تابع sum_n به یک حلقه‌ی اسکالر بازشده با فاکتور 8 تبدیل می‌شود که شامل هشت دستور addl k(%rdi,%rdx,4), %eax، یک addq $8 و یک حلقه‌ی باقیمانده خواهد بود. تابع sum4 نیز به چهار دستور جمع تبدیل می‌شود. ابزار شناسایی گزارش unrolled loop را همراه با copies: 8 و indexStep: 8 برای تابع اول و copies: 4 را برای تابع دوم ثبت می‌کند.

درس 33 دو یال برگشتی در تابع total در سطح -O2 پیدا کرد و آن‌ها را دو حلقه نامید. این درس ماهیت واقعی آن‌ها را مشخص می‌کند: یکی بدنه‌ی برداری و دیگری باقیمانده‌ی اسکالرِ همان حلقه‌ی واحد در کد منبع است. یک یال برگشتی تنها زمانی حلقه محسوب می‌شود که مقصد بتواند مجدداً به آن برسد. تابع is_loop() این موضوع را بررسی می‌کند؛ چون تابع digest در AArch64 انشعاب‌های رو به عقبی به یک بلوک پیش‌فرض مشترک دارد که حلقه نیستند، و نسخه‌ی اولیه‌ی ابزار شناسایی آن‌ها را به اشتباه حلقه‌ی برداری شمرده بود.

حلقه‌هایی که به توابع کتابخانه‌ای تبدیل می‌شوند

پاس LoopIdiomRecognize حلقه‌ای را که مقدار صفر را در تک‌تک بایت‌ها می‌نویسد، از سطح -O1 به بالا به فراخوانی تابع memset تبدیل می‌کند. تابع 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 فراخوانی می‌کند، و بخش Backend معماری x86 آن را در قالب سقف 8 ذخیره‌سازی به ازای هر memcpy، به‌صورت درون‌خطی و با دستورات movups (%rsi), %xmm0; movups %xmm0, (%rdi) پیاده‌سازی می‌کند. در سطح -O0 همین فراخوانی به‌صورت دو جفت movq با اندازه‌ی 8 بایت انجام می‌شود. با افزودن -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. از سطح -O1 به بعد، بدنه‌ی leaf_add یعنی leal (%rdi,%rsi), %eax به داخل twice_sum منتقل می‌شود و هیچ فراخوانی باقی نمی‌ماند. در سطح -O0، کامپایلر clang همه‌ی توابع را با optnone و noinline نشانه‌گذاری کرده و فقط توابعی را که صراحتاً باید همیشه جای‌گذاری شوند درون‌خطی می‌کند. ابزار شناسایی از روی کد منبع متوجه می‌شود که twice_sum تابع leaf_add را صدا می‌زند، پرش یا فراخوانی به آن پیدا نمی‌کند و در ادامه به دنبال ساختار بدنه‌ی تابع مقصد در تابع مبدأ می‌گردد: یعنی نماد دستوری و عملوندهای مبدأ، با حذف عملوند مقصد؛ بنابراین دستور add w8, w1, w0 در فراخواننده‌ی AArch64 با add w0, w1, w0 در تابع فراخوانی‌شده تطبیق داده می‌شود. وجود یک مورد تطبیق، شواهد کافی است.

تابع dispatch هر دو مفهوم را تلفیق می‌کند: یک جدول پرش 16 ورودی که هر کدام از caseهای آن دستورات 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) رمزگشایی می‌شود. این تغییرات در ادبیات GCC به نام تبدیل -fif-conversion و در LLVM تحت عنوان گزینش cmov شناخته می‌شوند. پاس X86CmovConversion در LLVM می‌تواند در صورت به‌صرفه بودن، cmov را دوباره به انشعاب تبدیل کند؛ به همین دلیل کد منبع یکسان ممکن است در یک حلقه هر یک از این دو الگو را نشان دهد.

در سطح -O0 هیچ‌کدام از این بهینه‌سازی‌ها رخ نمی‌دهد. تابع clamp_max شامل یک مقایسه، یک jle، دو عمل ذخیره در یک خانه و در نهایت یک بارگذاری است. ابزار شناسایی برای این تابع در سطح -O0 چیزی گزارش نمی‌کند، اما از سطح -O1 به بعد آن را branchless select تشخیص می‌دهد؛ این یکی از تفاوت‌هایی است که نمودار به‌خوبی نشان می‌دهد.

دستور mul9 تنها یک leal (%rdi,%rdi,8), %eax است و ابزار شناسایی آن را به‌صورت strength reduction با عبارت x * 9 ثبت می‌کند، چرا که در متن کد منبع ضرب در 9 آمده است. ابزار تنها زمانی این کار را می‌کند که ضریب در کد منبع وجود داشته باشد؛ دستور lea که مقیاس اندیس یک جدول را تنظیم می‌کند ضرب حسابی نیست.

دو ویژگی امنیتی که شبیه اصطلاحات فنی به نظر می‌رسند

محافظ استک (Stack protector) قابلیتی در کامپایلر است و الگویی بر جای می‌گذارد که اگر مراقب نباشید، یک ایجنت آن را به‌اشتباه منطق اصلی برنامه تحلیل می‌کند. کامپایل فایل canary.c با فلگ -fstack-protector-strong برای لینوکس x86-64 خروجی زیر را می‌دهد:

       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_guard در ساختار tcbhead_t کتابخانه‌ی glibc در آفست بایتی 40 است و متد getIRStackGuard در LLVM این خانه را برای glibc، bionic و Fuchsia مشخص می‌کند. بخش مقدمه (Prologue) تابع، مقدار گارد را بالای بافر کپی می‌کند، بخش خاتمه (Epilogue) آن را مقایسه می‌کند و مسیر شکست، تابع __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 را به‌عنوان نخستین دستورالعمل هر تابع قرار می‌دهد. این دستور یک پد فرود (Landing pad) برای پرش‌های غیرمستقیم روی پردازنده‌های مجهز به فناوری اجرای کنترل جریان (CET) است و روی سایر پردازنده‌ها مانند nop عمل می‌کند. الگوهای شروع تابع در Ghidra به همین دلیل گونه‌های دارای پیشوند endbr64 قبل از push rbp; mov rbp, rsp را شامل می‌شوند. ابزار شناسایی، این الگو را به‌صورت cet landing pad گزارش می‌دهد تا تابعی که با این چهار بایت غیرمعمول آغاز می‌شود، اشتباهاً داده تشخیص داده نشود.

دیکامپایلرها چه چیزهایی را ساده می‌کنند؟

تمام دیکامپایلرهای بررسی‌شده در درس 37 برخی از این روابط ریاضی را در قالب قواعد بازنویسی اجرا می‌کنند. دیکامپایلر Ghidra این قواعد را در فایل 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 را روی تابع grade از درس 33 در سطح -O1 ثبت کرد که به‌صورت uVar2 = param_1 / 10 - 6; خوانده می‌شد؛ عملیات تقسیم در اینجا کاملاً ادغام و ساده (Fold) شده است.

ورودی این قواعد بدون نیاز به محیط جاوا هم قابل مشاهده است. پکیج pypcode نسخه‌ی 4.0.1 در محیط مجازی، تبدیل سطح‌پایین (Lift) را با همان مشخصات SLEIGH مورد استفاده در Ghidra انجام می‌دهد، و فایل code/fixtures/idioms-x86_64-O2.lifts.json کد خام P-code را برای 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]. دستور shrq شامل 41 عملیات و دستور sarq شامل 40 عملیات است که اغلب آن‌ها صرفاً فلگ‌های پردازنده را محاسبه می‌کنند. قاعده‌ی RuleDivOpt با ضرب و دو شیفت در این جریان تطبیق پیدا می‌کند، و فرآیند حذف کدهای مرده (DCE)، فلگ‌هایی را که خوانده نمی‌شوند کنار می‌گذارد.

دیکامپایلر 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 را تولید می‌کند که در آن عبارات اصلاحی به‌شکل محاسبات عادی باقی مانده‌اند. این دیکامپایلر تابع mul9 را به a0 * 9، سوییچ linear_switch را به (a0 < 7 ? a0 * 10 + 10 : 0xffffffff)، گزینش clamp_max را به ((int)a1 < (int)a0 ? a0 : a1)، شرط is_pos را به a0 > 0، و fill را به return 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 *)(...)) همراه با فرمول جدول تبدیل می‌شود.

ابزارهای radare2 نسخه‌ی 6.2.4 و rizin نسخه‌ی 0.9.1 که از سورس بیلد شده و در حافظه‌ی موقت پژوهش قرار دارند، روی همان فایل اجرا شدند. دستور pdc در radare2 تابع div10s را به‌صورت rax = rax * 0x66666667; rcx >>>= 0x3f; rax >>= 0x22; eax += ecx برمی‌گرداند؛ یک شبه‌کد C در سطح ثبات‌ها و بدون هیچ ساده‌سازی. همچنین table_switch را به‌صورت eax = dword [rcx + rax*4] با یک کامنت RELOC 32 .rodata روی دستور lea نشان می‌دهد. ابزار rizin دیکامپایلر داخلی ندارد؛ دستور aoi آن زبان واسط RzIL دستور imul را به‌شکل یک ضرب 128 بیتی نمایش می‌دهد. ابزار lldb-1703.0.236.21 فایل شیء ELF را بارگذاری کرده و دستور disassemble -n div10s آن همان هفت دستور خروجی llvm-objdump را چاپ می‌کند، چون هر دو از دیزاسمبلر LLVM استفاده می‌کنند. کتابخانه‌ی Capstone نسخه‌ی 5.0.7 همین بایت‌ها را پردازش کرده و گروه‌هایی مانند ret و mode64 را گزارش می‌دهد؛ کار این کتابخانه صرفاً رمزگشایی (Decode) است و اصطلاح فنی هیچ‌گاه در خروجی یک دیکودر ظاهر نمی‌شود. ابزارهای IDA Pro و Binary Ninja در این آزمایش تست نشدند. مستندات آن‌ها مراحلی را که این بازنویسی‌ها در آن‌ها انجام می‌شوند شرح می‌دهد (مانند بهینه‌سازی Microcode و پاس‌های تبدیل MLIL به HLIL)، اما این درس ادعایی درباره‌ی ساده‌سازی این الگوها در آن‌ها مطرح نمی‌کند.

وب‌سایت Compiler Explorer ابزار اصلی برای بررسی مسیر مستقیم است. کد idioms.c را داخل آن قرار دهید، کامپایلری مانند «x86-64 clang 18.1.0» یا «ARM64 GCC 14.2.0» را انتخاب کرده و گزینه‌ها را مشخص کنید. این سرویس حدود 1050 کامپایلر C را در بر می‌گیرد و API اختصاصی دارد: درخواست GET /api/compilers/c شناسه‌ها را برمی‌گرداند و POST /api/compiler/<id>/compile خروجی اسمبلی را در قالب JSON تحویل می‌دهد. مت گادبولت (Matt Godbolt) در مقاله‌ی سال 2019 خود در مجله‌ی ACM Queue با استفاده از همین ابزار، الگوهای تقسیم، شمارش بیت‌ها (Popcount)، شرط‌های زنجیره‌ای و تجمیع را بررسی می‌کند. از این ابزار برای بررسی خروجی‌های GCC که روی این سیستم نصب نیست استفاده کنید و مقادیر آستانه‌ی جدول پرش و تنظیمات پیش‌فرض برداری‌سازی در -O2 را از GCC 12 با خروجی‌های clang در فایل‌های نمونه بسنجید.

ساخت ابزار

دمو را اجرا کنید:

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

خروجی یک گزارش JSON است. این اسکریپت برای هر یک از 18 بیلد، تمام توابع و اصطلاحات فنی آن‌ها را با نوع، فرم مبدأ، آدرس‌های شواهد، وضعیت تأیید و فیلدهای جزئیات برمی‌شمارد. در پایان نیز یک ماتریس مقایسه‌ای از نوع الگوها در هر بیلد، مقایسه‌ی سطوح -O2 در برابر -O3 برای هر دو معماری، و فهرست موارد تأییدنشده (unverified) ارائه می‌شود.

شکل مورد انتظار:

{
  "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 را به این ترتیب بخوانید:

1. تابع parse_listing() خروجی متنی llvm-objdump -d -r را برای هر دو معماری به توابع، دستورالعمل‌ها و بازنشانی‌های متصل به آن‌ها تجزیه می‌کند.
2. کلاس ElfFile بخش‌ها، نمادها و درگاه‌های .rela.* را می‌خواند و متد words() درگاه‌های جداول را دریافت می‌کند.
3. توابع magic_numbers()، divisor_from_magic() و evaluate_division() اثبات گرنلوند–مونتگومری را در جهت مستقیم، معکوس و در قالب دنباله‌ی دستورالعمل پیاده‌سازی می‌کنند.
4. تابع parse_source() ساختارهای مورد نیاز برای اعتبارسنجی را از فایل منبع C استخراج می‌کند.
5. کلاس Evaluator پاس نمادین بلوک‌به‌بلوک است که ثبات‌ها و اسلات‌های استک را نام‌گذاری می‌کند.
6. توابع find_divisions() و find_modulos() الگوهای ضرب، شیفت، اصلاح جمع، ضرب معکوس و حالت‌های توان دو را ارزیابی می‌کنند.
7. تابع find_switches() جدول‌های پرش، جدول‌های جستجو، نگاشت‌های خطی، زنجیره‌های گزینش، درخت‌های مقایسه و زنجیره‌های مقایسه را دسته‌بندی می‌کند.
8. توابع 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() بقیه‌ی موارد را پوشش می‌دهند.
9. تابع analyze_function() این بررسی‌ها را به ترتیب اجرا می‌کند و نام خروجی هر اصطلاح را به پاس بعدی ارزیاب تحویل می‌دهد.

سه دستور دیگر نیز وجود دارد. دستور python3 code/main.py scan FILE.objdump.txt [FUNCTION] ابزار شناسایی را روی یک فایل دیس‌اسمبل خاص اجرا می‌کند، در حالی که فایل شیء و فایل C متناظر را در کنار آن می‌یابد. دستور python3 code/main.py magic DIVISOR [signed] ضریب، مقدار شیفت، میزان خطا و برقراری برابری روی مقادیر مرزی را چاپ می‌کند. دستور python3 code/main.py figure-data داده‌هایی را که در تصویر تعاملی درج می‌شوند در خروجی می‌آورد.

استفاده از ابزار

روی هر فایل شیء جدیدی که ساختید، ابزار شناسایی را طبق این مراحل اجرا کنید:

1. خروجی llvm-objdump -d -r را از فایل شیء بگیرید و دستور دقیق کامپایلر را در کنار آن نگه دارید. ابزار شناسایی، معماری را از هدر خروجی تشخیص می‌دهد.
2. دستور scan را روی خروجی متنی اجرا کنید و اول موارد unverified را بخوانید. هر مورد تأییدنشده یا ساختاری است که پارسر منبع ندیده یا الگویی است که ابزار شناسایی اشتباه خوانده است؛ در هر دو حالت باید آدرس‌های شواهد را بررسی کرد.
3. برای تمام تقسیم‌ها فیلد algorithm را بررسی کنید. اگر clangMatchesAlgorithm برابر با true باشد، کامپایلر کوچک‌ترین شیفت معتبر را برگزیده است. اگر false باشد، کامپایلر دلیلی داشته که هنوز آن را نمی‌دانید؛ مقادیر ثابت را یادداشت کنید.
4. برای تمام دستورات switch، نوع تبدیل lowering را در سطوح مختلفی که ساخته‌اید مقایسه کنید. جدولی که به درخت تبدیل شده، یا درختی که به جدول بدل گشته، حد آستانه‌ای را نشان می‌دهد که می‌توانید آن را از سورس LLVM نام ببرید.
5. برای تمام حلقه‌ها فیلدهای elementsPerIteration و scalarRemainderLoop را بررسی کنید، سپس تأیید کنید که دو یال برگشتی گزارش‌شده در درس 33 در واقع مربوط به یک حلقه‌ی واحد در کد منبع هستند.
6. یک دیکامپایلر را روی همان فایل شیء اجرا کنید، خروجی متنی آن را در کنار هر اصطلاح نقل‌قول کنید و مواردی را که ساده‌سازی کرده ثبت نمایید. این ثبت، خط مبنا (Baseline) برای درس 45 خواهد بود.

آزمایشگاه تعاملی

آزمایش الف: محاسبه‌ی یک عدد جادویی و سپس یافتن آن

از دایرکتوری code، پایتون را باز کنید:

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

این دستورات را اجرا کنید:

from 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 اضافه کنید، آن را با دستور موجود در build_fixtures.sh در سطح -O2 بیلد کنید و مقدار ثابت در خروجی اسمبلی را با خروجی magic_numbers(13) بسنجید.

آزمایش ب: جدول و درخت

listing = 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)

در یک نسخه‌ی کپی از تابع table_switch، مقدار 71 را دوباره به 70 تغییر دهید، مجدداً در سطح -O2 بیلد کنید و ببینید چطور جدول جستجو به یک نگاشت خطی تبدیل می‌شود. سپس مقدار یکی از caseها را به 1000 تغییر دهید و مشاهده کنید که چگونه ساختار آن به‌صورت یک جدول از نوع ArrayKind باقی می‌ماند.

آزمایش ج: تحلیل حلقه در سه پیکربندی

for 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 تطبیق دهید.

آزمایش د: خارج‌قسمت مشترک

for 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)])

خروجی دیس‌اسمبل تابع digest در سطح -O1 را بررسی کنید و دو دستوری را که در x86-64 خارج‌قسمت را با اصلاح علامت ترکیب می‌کنند بیابید. سپس توضیح دهید چرا بیلد AArch64 تنها به یک دستور نیاز دارد.

تمرین عملی

ترفندهای بیتی را به فایل‌های نمونه اضافه کنید و ابزار شناسایی را گسترش دهید.

الزامات:

• توابع popcount، ctz و rotl را با توابع درونی کامپایلر GCC و چرخش بیت‌ها با عملگرهای شیفت و OR بنویسید، آن‌ها را در سطح -O2 یک‌بار با گزینه‌های -mpopcnt -mbmi و یک‌بار بدون آن‌ها بیلد کنید، و فایل‌های شیء را همراه با خروجی دیس‌اسمبل آن‌ها commit کنید.
• دنباله‌ی شمارش بیت‌های فعال با ثابت‌های 0x55555555، 0x33333333، 0x0f0f0f0f و 0x01010101 را که توسط تابع TargetLowering::expandCTPOP تولید می‌شود شناسایی کرده و آن را به‌صورت popcount با این چهار ثابت به‌عنوان شواهد گزارش کنید.
• توالی rep bsfl را به‌عنوان کدگذاری معادل tzcnt یا bsf و دستور roll %cl را به‌عنوان چرخش بیت‌ها شناسایی کرده و هر دو را به تابع درونی مربوطه رمزگشایی کنید.
• انواع جدید را به بخش اعتبارسنجی parse_source() اضافه کنید، به‌طوری که الگوی popcount فقط زمانی تأیید شود که کد منبع واقعاً __builtin_popcount را فراخوانی کرده باشد.
• برای هر اصطلاح یک آزمون بنویسید که مقادیر ثابت را از خروجی دیس‌اسمبل فایل نمونه بخواند.

موفقیت در این تمرین یعنی اجرای python3 code/main.py این سه نوع جدید را با verified: true در هر دو حالت بیلد گزارش کند و مجموعه‌ی آزمون‌ها کماکان فهرست unverified خالی تحویل دهد.

دستاورد درس

این درس شامل فایل outputs/skill-compiler-idioms-and-optimization.md است. از آن برای تبدیل یک خروجی متنی اسمبلی، یک فایل شیء و سورس متناظر به یک گزارش تأییدشده از الگوهای بهینه‌سازی همراه با مقایسه‌ی دیکامپایلر استفاده کنید. این فایل برای هر ادعا نیازمند آدرس‌های شواهد، برای هر تقسیم نیازمند اثبات عدد جادویی، برای هر سوییچ نیازمند نوع تبدیل و منبع درگاه‌ها، و برای هر اصطلاح نیازمند ارائه‌ی خط معادل نقل‌شده از دیکامپایلر است.

اعتبارسنجی

برنامه‌ی دمو و مجموعه‌ی آزمون‌های معین را اجرا کنید:

cd 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+0x24 را به دستور leaq در table_switch متصل کند.
• بخش ELF-خوان، مقادیر [10, 20, 30, 40, 50, 60, 71] را از .rodata+0x28 و ده رکورد بازنشانی را در .rela.rodata بازیابی کند.
• تابع magic_numbers مقدار 0xcccccccd با شیفت 35، 0x66666667 با 34، 0x124924925 با 35 و قالب جمع، 0x55555556 با 32، و 0xaaaaaaab با 33 را برگرداند.
• این رابطه‌ی حسابی روی مقادیر مرزی 32 بیتی برای تمام مقسوم‌علیه‌های 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 در x86-64 ابتدا جدول پرش، سپس جدول جستجو با ضریب ادغام‌شده‌ی 16 و در نهایت جدول پرش با چهار مقصد مجزا باشد؛ و در AArch64 درخت مقایسه‌ای همراه با بررسی بازه‌ی 9 تا 10 باشد.
• گزینه‌ی -fno-jump-tables درخت مقایسه بسازد، و تابع 16حالته‌ی dispatch مقاصد خود را در x86-64 از بخش بازنشانی‌ها و در AArch64 از جدول بایتی فشرده بخواند.
• حلقه‌ی برداری، 4 خط پردازش، 2 ثبات انباره، 8 عنصر در هر تکرار، ماسک، شرط محافظ، بخش تقلیل و حلقه‌ی باقیمانده را ثبت کند.
• حلقه‌ها با تعداد تکرار ثابت، به‌طور کامل برداری یا به‌طور کامل باز شوند، و گزینه‌ی -fno-vectorize حلقه را با فاکتور 8 باز کند.
• سطح -O1 فاقد برداری‌سازی باشد، سطوح -O2 و -O3 در x86-64 کاملاً یکسان باشند و در AArch64 تنها در تابع call_switch تفاوت داشته باشند؛ جایی که -O3 شامل 17 دستور و -O2 شامل 18 دستور است.
• گزینه‌ی -fno-builtin حلقه‌ی ذخیره‌سازی داده را به حلقه‌ی ذخیره‌ی برداری تبدیل کرده و memcpy را در قالب فراخوانی حفظ کند.
• فراخوانی‌های انتهایی، جایگزینی memset، کپی درون‌خطی 16 بایتی و کپی دومرحله‌ای در سطح -O0 شناسایی شوند.
• تابع درون‌خطی‌شده از سطح -O1 به بالا بر اساس ساختار بدنه‌اش ردیابی شود.
• دستورات گزینش به‌صورت a > b ? a : b، -x < 0 ? x : -x، (x > 0) و sum % 10 < 5 ? sum % 10 : 5 رمزگشایی شوند.
• محافظ استک، مقدار %fs:0x28، اسلات استک و فراخوانی __stack_chk_fail را گزارش دهد، و دستور endbr64 در تمام توابع بیلدِ دارای CET ثبت شود.
• پارسر منبع، پارامترهای اشاره‌گر تابع، حالت‌های سوییچ، فراخوانی‌ها و نام انباره‌ها را استخراج کند.
• تمام اصطلاحات در تمام بیلدها تأیید شوند و ماتریس‌های تطبیق انواع همخوانی داشته باشند.
• تصویر تعاملی دقیقاً همان داده‌های تحلیل‌شده را بازنمایی کند.

حالت‌های شکست در محیط واقعی

قاعده‌ی عملیاتی

الگو را مطابقت دهید، اثبات ریاضی را معکوس اجرا کنید، و مقادیر ثابتی را که آن را اثبات می‌کنند بنویسید. هر اصطلاح فنی را با آدرس‌های شواهد و شکل رمزگشایی‌شده‌ی آن در کد منبع گزارش کنید، درستی هر کدام را در برابر کدی که کامپایل کرده‌اید بسنجید، و خروجی دیکامپایلرها برای همان بایت‌ها را در کنار آن نقل‌قول کنید.

برای مطالعه‌ی بیشتر

• Granlund, Montgomery, "Division by Invariant Integers using Multiplication" (PLDI 1994)
• Warren, Hacker's Delight, 2nd edition, Chapter 10: Integer Division By Constants
• Lemire, Kaser, Kurz, "Faster Remainder by Direct Computation" (2019)
• libdivide, header-only division by runtime constants
• LLVM DivisionByConstantInfo.cpp
• LLVM SwitchLoweringUtils.cpp and TargetLoweringBase.cpp
• LLVM SimplifyCFG.cpp, simplifySwitchLookup
• LLVM Auto-Vectorization documentation and LLVM 3.4 release notes
• LLVM LoopIdiomRecognize.cpp
• LLVM X86CmovConversion.cpp
• LLVM StackProtector.cpp and X86ISelLoweringCall.cpp, getIRStackGuard
• glibc sysdeps/x86_64/nptl/tls.h, tcbhead_t
• GCC tree-switch-conversion.cc, GCC Optimize Options, and GCC 12 release notes
• Ghidra decompiler ruleaction.cc
• angr decompiler documentation
• radare2 book: decompilers
• Compiler Explorer API
• Godbolt, "Optimizations in C++ Compilers: A practical journey", ACM Queue 17(5), 2019
• Microsoft, /GS (Buffer Security Check)