تخصیص ثبات

تعریف مسئله

در طراحی تمامی کامپایلرها این فرض وجود دارد که در بخش میانی کامپایلر که وظیفهٔ بهبود کد را به عهده دارد، بی‌نهایت ثبات برای نگهداری متغیرها وجود دارد. به این ثبات‌ها، «ثبات‌های مجازی» می‌گویند. حال مسألهٔ تخصیص ثبات این‌گونه مطرح می‌شود:
«طی تبدیل کد میانیِ کامپایلر به کد ماشین باید با روشی بهینه تمامی ثبات‌های مجازی بر روی ثبات‌های واقعیِ ماشین مورد نظر نگاشت شوند یا در صورت محدودیت ثبات‌های واقعی از حافظهٔ اصلیِ ماشین برای نگهداری آن‌ها استفاده کنیم.»

روش‌های مختلف تخصیص ثبات

همان‌طور گه در مقدمه گفته شد، تمامی روش‌های کلی تخصیص ثبات به دو دسته تقسیم می‌شوند: (۱) سراسری و (۲) غیر سراسری. در ادامه مهم‌ترین روش‌های تخصیص ثبات در هر یک از این تقسیم‌بندی‌ها می‌آید.

رنگ‌آمیزی گراف

اولین روشی که برای تخصیص ثبات استفاده شد و هم‌چنین محبوب‌ترین روش است، تخصیص ثبات با استفاده از مسألهٔ معروف رنگ‌آمیزی گراف است. در این روش برای هر متغیر (و یا همان ثبات‌های مجازی) بازه‌هایی که زنده هستند مشخص می‌شوند؛ یا به عبارتی برای هر متغیر مشخص می‌شود که چه زمانی مقدار آن ارزش دارد که این همان بازهٔ میان تعریف و استفاده از آن متغیر است. حال با استفاده از تعریف بازه‌های زندگی هر متغیر، مسألهٔ تخصیص ثبات را بر روی مسألهٔ رنگ‌آمیزی گراف نگاشت می‌کنیم.

گراف برخورد

اولین قدم ساخت «گراف برخورد» است. راس‌های این گراف همان بازه‌های زندگی متغیرها هستند. یال‌های این گراف نیز این‌گونه مشخص می‌شوند: «دو راس در گراف برخورد به هم متصل هستند اگر نقطه‌ای در برنامه وجود داشته باشد که متغیرهای متناظر آن راس‌ها همزمان زنده باشند.» اکنون که گراف برخورد را تعریف کردیم می‌توانیم مسألهٔ تخصیص ثبات را به عنوان یک مسألهٔ رنگ‌آمیزی گراف مطرح کنیم.

مدل‌سازی مسألهٔ تخصیص ثبات به عنوان مسألهٔ رنگ‌آمیزی گراف

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

اسکن خطی

این روش سریع‌ترین روش موجود برای تخصیص ثبات است و تقریباً در تمامی کامپایلرهای درجا از آن استفاده می‌شود. در این روش تمامی دستورهای برنامه با هر ترتیب دلخواهی مرتب می‌شوند (که البته در تمامی کامپایلرها ار همان ترتیبی که دستورها در برنامه آمده‌است استفاده می‌شود). سپس بازه‌های زندگیِ هر متغیر ساخته می‌شود که نقطهٔ شروع این بازه دستوری است که آن متغیر را تعریف می‌کند و نقطهٔ پایانی بازه دستوری است که برای آخرین بار از آن متغیر استفاده کرده‌است. پس از ساخت بازه‌های زندگی متغیرها، آن‌ها را بر اساس نقطهٔ شروعشان مرتب می‌کنیم و به همان ترتیب شروع می‌کنیم به تخصیص ثبات؛ اگر ثباتی برای تخصیص وجود داشته که آن را در اختیار آن بازه قرار می‌دهیم و اگر تمامی ثبات‌ها تخصیص یافته باشند باید یکی از متغیرها در حافظهٔ اصلی نگهداری شود. برای این کار نیز متغیری انتخاب می‌شود که دیرتر از همه استفاده شود (نقطهٔ پایانی بازهٔ آن متغیر از همه بیش‌تر باشد)
این روش به صورت خطی تخصیص ثبات را انجام می‌دهد و سربار زمانی آن خیلی کم‌تر از روش رنگ‌آمیزی گراف است و همان‌طور که گفته شد در کامپایلرهای درجا بسیار کاربرد دارد.

تخصیص ثبات بر اساس کد میانی با فرم SSA

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

تخصیص ثبات غیر سراسری

روش‌های تخصیص ثبات غیر سراسری، روش‌هایی هستند که کد را به چندین بخش تقسیم می‌کنند (به عنوان مثال این قسمت‌ها می‌توانند همان بلوک‌های پایهٔ کد باشند) و برای هر یک از این بخش‌ها به صورت جداگانه تخصیص ثبات انجام می‌دهند. روش‌های کمی به صورت غیر سراسری پیاده‌سازی شده‌اند و یکی از دلایل آن هماهنگ‌کردن بخش‌های مختلفی هستند که به صورت جداگانه تخصیص ثبات انجام داده‌اند. اما در ادامه یکی از روش‌های غیر سراسری آمده‌است که توانسته‌است کد با کیفیت خوبی تولید کند و در بسیاری از برنامه‌ها کارایی را نسبت دیگر روش‌های سراسری افزایش دهد.

تخصیص ثبات ردیابی

ایدهٔ کلی این روش بدین گونه است که کد را به دو بخش کلی تقسیم می‌کند: (۱) بخش داغ که قسمت‌هایی از کد را شامل می‌شود که با فرکانس زیادی انجام می‌شود، (۲) بخش سرد که شامل قسمت‌هایی است که کم‌تر استفاده می‌شوند. پس از تقسیم‌بندی کد، برای هر کدام از قسمت‌های کد از روش تخصیص ثبات متناسب آن استفاده می‌کنیم؛ یا به عبارتی سعی می‌کنیم برای بخش‌های داغ کد از روش‌های بسیار دقیق تخصیص ثبات استفاده کنیم تا کارایی کد هنگام اجرا پایین نیاید و برای بخش‌های سرد کد از روش‌های معمولی و سریع استفاده کنیم؛ در نتیجه برای بخش‌هایی از کد که تأثیر چندانی در کارایی ندارند، زمان زیادی را صرف نمی‌کنیم؛ بنابراین بدون از دست دادن کارایی، سربار کامپایل را نیز پایین می‌آوریم.
همان‌طور که مشخص است این روش تنها در کامپایلرهای درجا می‌تواند به کار رود (تنها با استفاده از اجرا کردن برنامه می‌توانیم قسمت‌های داغ و سرد آن را مشخص کینم).