کاهش سوئیچ در GCC

ما در پست قبلی دیدیم که دستورات سوئیچ پیچیده تر از آنچه به نظر می رسد هستند. کامپایلر می تواند آنها را به عنوان درخت تصمیم پیاده سازی کند (حتی اگر نباید). آیا این همه کاری است که می تواند انجام دهد؟

در این پست، من بر gcc تمرکز خواهم کرد. همه بهینه‌سازی‌ها، به جز کاهش بیت‌ست، به صدای زنگ ترجمه می‌شوند. من از پرچم بهینه سازی -O3 استفاده خواهم کرد مگر اینکه خلاف آن مشخص شده باشد.

من همچنین کمی کد gcc را ویرایش کرده و برخی ادعاها را برای اختصار حذف کرده ام.

اجازه دهید با یک مثال ساده شروع کنیم. تابعی که دو عدد صحیح x و val را می گیرد. بسته به مقدار x، تابع مربوطه (f0، f1 و غیره) را با val به عنوان آرگومان فراخوانی می کند و نتیجه را برمی گرداند. اگر این را به صورت دستی پیاده سازی می کردیم، از آرایه ای از نشانگرهای تابع استفاده می کردیم، جایی که ورودی به عنوان شاخص در آرایه عمل می کند.

کامپایلر با این رویکرد موافق است و دستور switch را به یک جدول پرش تبدیل می کند.

علاوه بر این، می تواند تشخیص دهد که چه زمانی مقادیر با یک ثابت جبران می شوند:

شهود ما نشان می‌دهد که هر چه مقادیر کم‌تر باشد، تبدیل جدول پرش سود کمتری دارد.

از طریق آزمایش، متوجه می‌شویم که gcc آستانه را حدود هشت ورودی جدول پرش در هر برچسب موردی در نظر می‌گیرد.

به عبارت دیگر، تابع زیر در جدول پرش کامپایل می شود:

اما این تابع دیگر به عنوان درختی از مقایسه ها گسترش می یابد:

در اینجا درخت مقایسه برای وضوح تصویر شده است:

تغییر مثال اول ما با گنجاندن یک مقدار پرت نشان می دهد که کامپایلر قادر به تشخیص زیرمجموعه های متراکم از موارد است.

کامپایلر یک شاخه برای مورد 100 منتشر می کند، اما یک جدول پرش برای موارد 1 تا 5 منتشر می کند.

در مثال‌های ما تاکنون، هر دستور case منجر به یک بلوک کد متفاوت می‌شود. بیایید آزمایش کنیم که چه اتفاقی می‌افتد وقتی چندین برچسب حروف یک تابع را فراخوانی می‌کنند.

ما 20 برچسب case داریم، با مقادیر بین 0 و 87. کامپایلر می تواند این سوئیچ را به یک جدول پرش با 88 ورودی کاهش دهد. فرضیه ما برای اکتشافی این است که تبدیل جدول پرش زمانی سودآور است که اندازه آن کوچکتر از 8 * num_case_labels باشد. از 88 < 20 * 8، تبدیل باید در این مورد سودآور باشد، با این حال gcc تصمیم گرفت سوئیچ را به دنباله ای از مقایسه ها کاهش دهد.

برای درک بهتر چرایی، اجازه دهید بلوک خاصی از برچسب های مورد را بررسی کنیم.

کامپایلر متوجه می شود که موارد به هم پیوسته هستند و می توانند به جای چهار مقایسه با دو مقایسه پیاده سازی شوند. اگر ورودی جدول پرش، تعداد مقایسه‌ها به جای برچسب‌های موردی باشد، همه چیز درست می‌شود:

ما در کل 10 مقایسه داریم. از 10 * 8 < 88، اکتشافی تجدید نظر شده ما نشان می دهد که تبدیل جدول پرش بی سود است.

کامپایلر کد ماشین غیر شهودی را منتشر می کند. چرا جدول های cmp و jump وجود ندارد؟ ثابت 2753205 از کجا می آید؟

یک اشاره از دستورالعمل bt می آید. طبق اسناد اینتل، bt:

بیت را در یک رشته بیت (مشخص شده با عملوند اول، به نام پایه بیت) در موقعیت بیت تعیین شده توسط بیت افست (مشخص شده توسط عملوند دوم) انتخاب می کند و مقدار بیت را در پرچم CF ذخیره می کند.

اگر نمایش دودویی 2753205 را بررسی کنیم، متوجه می شویم که در واقع یک مجموعه بیت است. بیت هایی که روی یک تنظیم می شوند با مقادیر ASCII برچسب های موردی مطابقت دارند و هر مقدار 48 کاهش می یابد.

ما با چندین استراتژی کاهش متمایز استفاده شده توسط gcc مواجه شده ایم. برای درک عمیق تر، می توانیم به کد منبع کامپایلر بپردازیم.

پاس کامپایلر که مسئول پایین آوردن عبارات سوئیچ است pass_lower_switch (با نام مناسب) است که به نوبه خود analyzy_switch_statement را فراخوانی می کند.

از آنجایی که دنبال کردن منبع gcc می‌تواند دلهره‌آور باشد، من یک نسخه نظردهی گام به گام را در زیر ارائه خواهم کرد. پس از این، من هر بخش را برای توضیح عملکرد آن تجزیه می کنم.

چند کد مقدمه m_switch به یک شی ساده اشاره می کند. Gimple نمایش داخلی استفاده شده توسط gcc است. از این طریق، تعداد کلی موارد و تعداد مجزای موارد را برای هر لبه خروجی استخراج می کنیم.

ما همچنین یک بردار اختصاص می دهیم که استراتژی کاهش انتخاب شده برای هر برچسب مورد را ثبت می کند.

کد راه اندازی بیشتر متوجه شدیم که gimple برای هر برچسب مفهومی از ارزش بالا و پایین دارد. به این معنا که در این مرحله برچسب‌های موردی پیوسته به هم پیوسته‌اند.

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

بردار خوشه هایی را که ایجاد کرده ایم تبدیل می کنیم. نام bit_test_cluster به استراتژی کاهش بیت‌ست که قبلا دیده بودیم اشاره می‌کند.

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

اساسا، در این بخش ما به دنبال دنباله‌هایی از برچسب‌های موردی هستیم که نمی‌توانند به خوشه‌های بیت‌ست تبدیل شوند.

ما سعی می کنیم این برچسب های متوالی را به یک جدول پرش تبدیل کنیم و نتیجه را به خروجی اضافه کنیم.

هر چه باقی می ماند از یک پاس دیگر می گذرد که دستور switch را به درخت تصمیم تبدیل می کند. بیت‌ها و جدول پرش برگ‌های درخت تصمیم هستند.

بیایید بیشتر به bit_test_cluster::find_bit_tests بپردازیم. ساختار سطح بالای کد به شرح زیر است.

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

متعاقبا، روی بیت‌ها تکرار می‌کنیم و یک اکتشافی سودآوری را اعمال می‌کنیم. اگر بیت‌ها با این اکتشافی مطابقت داشته باشند، یک bit_test_cluster منتشر می‌کنیم. در غیر این صورت، s اصلی simple_cluster را نگه می داریم.

برای برنامه نویسی پویا، از بردار ساختارهای min_cluster_item استفاده می کنیم. هر min_cluster_item دارای سه جزء است:

برنامه نویسی پویا به شرح زیر است. ما می‌خواهیم حداقل تعداد بیت‌ها را برای نشان دادن اولین برچسب‌های i case پیدا کنیم.

حالت پایه ساده است، یک برچسب موردی منفرد را می توان با یک بیت واحد نشان داد.

فرض کنید ما قبلا تعداد بهینه بیت‌ها را برای اولین برچسب j موردی، برای همه پیدا کرده‌ایم. ما تعداد بهینه تقسیم‌ها را برای اولین عناصر i تعریف می‌کنیم. این بدان معنی است که ما قبلا محاسبه کرده ایم و اکنون به دنبال آن هستیم.

اگر محدوده برچسب‌های موردی را بتوان به صورت یک خوشه بیت‌ست نمایش داد، باید درست باشد

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

این شرایط دقیقا همان چیزی است که عبارت if در کد بالا آن را بررسی می کند.

تابع can_be_handled کنترل می‌کند که آیا محدوده‌ای از برچسب‌ها را می‌توان به تست بیت‌ست تبدیل کرد یا خیر. این دو معیار را آزمایش می کند:

اگر بیش از یک یال وجود داشته باشد، ما یک آبشار از آزمایش بیت را منتشر می کنیم.

اکنون فقط بیت هایی را تبدیل می کنیم که تست is_beneficial را برآورده می کنند. در کد شمارش تعداد برچسب‌های موردی را نشان می‌دهد که توسط خوشه مدیریت می‌شود، در حالی که uniq تعداد یال‌های خروجی مجزا را نشان می‌دهد.

منطق تبدیل جدول پرش همان چیزی است که برای تبدیل تست بیت استفاده می شود. از برنامه نویسی پویا برای شناسایی «خوشه هایی» استفاده می کند که می توانند به طور سودآوری به جدول پرش تبدیل شوند.

ما با تخصیص یک بردار از min_cluster_item شروع می کنیم. ما از این بردار برای پیگیری بهترین تکالیف جدول پرش برای خوشه‌های موردی متوالی استفاده خواهیم کرد.

ما همچنین برای برنامه نویسی پویا، کیس پایه را فشار می دهیم. این مربوط به استفاده از یک جدول پرش برای کل سوئیچ است.

حلقه برنامه نویسی پویا همان چیزی است که ما برای بیت ست ها استفاده کردیم. ما می خواهیم حداقل تعداد جدول های پرش را برای نشان دادن اولین برچسب های موردی i پیدا کنیم.

ما روی انشعابات در برچسب مورد j برای j < i تکرار می کنیم. در طول هر تکرار ما بهترین تقسیم امتیاز را دنبال می کنیم. حالت ویژه j == 0 یک جدول پرش واحد را برای کل دستور سوئیچ نشان می دهد.

در داخل این حلقه داخلی نیز موارد زیر را پیگیری می کنیم:

نقطه 1. و 2. مشابه با بیت مجموعه گذر پایین است، در حالی که 3. جدید و مختص جداول پرش است.

یعنی، به دلیل پرش غیرمستقیم و نیاز به بررسی مرزها، مقداری هزینه برای اعزام به میز پرش وجود دارد. بنابراین gcc برای ایجاد یک جدول پرش به حداقل مقدار مورد نیاز دارد.

اگر یک تقسیم یک جدول پرش خیلی کوچک ایجاد کند، اندازه جدول پرش به یک انباشته s اضافه می شود که به عنوان یک جداکننده بین نامزدهای مختلف تقسیم استفاده می شود.

برای محاسبه امتیازدهی، به تعداد مقایسه بین j -th و i -th برچسب مورد نیاز داریم. ما آن را با جمع‌بندی تعداد مقایسه‌ها برای همه برچسب‌ها محاسبه می‌کنیم و با پیشروی در حلقه داخلی، تعداد آن‌ها را کاهش می‌دهیم.

ما همچنین به تعدادی لیبل کیس بدون کنترل نیاز داریم. ما آن را با مقایسه اندازه جدول پرش با نتیجه تابع case_values_threshold تعیین می کنیم. این تابع وابسته به معماری است و وجود دستورالعمل‌های مخصوص کیس سوئیچ را در نظر می‌گیرد، اما در ماشین‌های مدرن x64 و Arm64، پیش‌فرض آن 5 است.

بیایید اکنون بر روی اکتشافی اصلی تمرکز کنیم و از نحوه محاسبه max_ratio شروع کنیم. من در زیر حلقه اصلی بازتولید کرده‌ام، خطوط غیرمرتبط با اکتشافی اصلی را حذف کرده‌ام.

در بخش مثال‌ها دیده‌ایم که gcc از نسبت بین ورودی‌های جدول پرش و مقایسه‌ها به عنوان معیاری برای کاهش اکتشافی استفاده می‌کند. کد زیر نشان می دهد که نسبت های متمایز هنگام بهینه سازی سرعت (پرچم -O[123|سریع]) یا اندازه (پرچم -Os) استفاده می شود. به طور خاص، هنگام بهینه سازی سرعت از نسبت 8 استفاده می شود، در حالی که هنگام بهینه سازی برای اندازه از نسبت 2 استفاده می شود.

حالا وارد حلقه اصلی شوید. با توجه به دو تقسیم، ما ترجیح می دهیم جداول پرش کمتری منتشر شود. یا، اگر تعداد جدول های پرش یکسانی را به همراه داشته باشند، ما آن را ترجیح می دهیم که بیشترین برچسب ها را انجام دهد. همچنین تقسیم‌هایی را که منجر به جداول پرش بی‌سود می‌شوند، نادیده می‌گیریم، جایی که سودآوری توسط تابع can_be_handled بررسی می‌شود.

شرط can_be_handled، سرریز را بررسی می‌کند و نسبت برچسب‌ها به ورودی‌های جدول پرش را مقایسه می‌کند:

کد تابع نیز منعکس کننده ی خوشه های بیت است. روی تمام جدول‌های پرش به ترتیب معکوس تکرار می‌شود و آنهایی را که در بررسی is_beneficial شکست می‌خورند، هرس می‌کند.

چک is_beneficial برای میزهای پرش با هدف هرس جداول پرش کوچک است. این تعداد برچسب‌های موردی را با case_values_threshold مقایسه می‌کند.

اگر gcc نتواند یک خوشه بیت‌ست یا یک جدول پرش منتشر کند، به درخت مقایسه دودویی برمی‌گردد.

در انتشار درخت، احتمال هر خوشه برچسب موردی را در نظر می گیرد. این احتمال را می‌توان از طریق بهینه‌سازی هدایت‌شده با نمایه یا با تعبیه __builtin_expect_with_probability به دست آورد.

لیست برچسب موردی را طوری تقسیم کنید که هر دو نیمه احتمال برابری داشته باشند.

برای ساختن درخت باینری در هر دو نیمه تکرار کنید.

ما استراتژی‌های اکتشافی و کاهشی را دیده‌ایم که gcc هنگام کامپایل دستورات سوئیچ استفاده می‌کند، از جمله:

برای هر کسی که علاقه مند به کاوش عمیق تر است، پیشنهاد می کنم کد منبع gcc را بررسی کرده و این مقاله را بخوانید.

در پایان می خواهم از B.X.V.، C.P. و V.P تشکر کنم. برای بازخورد آنها هنگام نوشتن این پست