موضوع مقاله: تخصیص ثبات | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # تخصیص ثبات | مقدمه: تخصیص ثبات یکی از مراحل پایانی کامپایل کدهای برنامه‌نویسی است که مهم‌ترین مرحله برای افزایش کارایی کد تولید شده به‌وسیلهٔ کامپایلر می‌باشد. | ## بخش 1: تخصیص ثبات | اهمیت این مرحله با توجه به افزایش سرعت پردازنده‌ها و هم‌چنین افزایش زمان دسترسی به حافظه، روز به روز بیش‌تر می‌شود و تأثیر آن را به وضوح می‌توان بر روی حجم کد تولید شده و هم چنین کارایی آن مشاهده نمود. کامپایلرها به‌طور کلی به سه بخش تقسیم می‌شوند: بخش ابتدایی که زبان سطح بالا را به یک زبان سطح میانی تبدیل می‌کند. بخش میانی که در این بخش روش‌های زیادی برای بهبود کد به کار گرفته می‌شوند و در نهایت بخش پایانی کامپایلر که وظیفهٔ تبدیل کد میانی به کد ماشین را بر عهده دارد. در تمامی کامپایلرها، در بخش میانی این فرض وجود دارد که بی‌نهایت ثبات وجود دارد (و این ثبات‌ها را ثبات‌های مجازی می‌نامند) و هیچ نگرانی‌ای در مورد کمبود ثبات وجود ندارد. اما از آن‌جایی که تمامی ماشین‌ها دارای تعداد محدودی ثبات هستند باید در بخش پایانی تمامی ثبات‌های مجازی به ثبات‌های واقعی نگاشت شوند.Aho, Alfred V. در حال حاضر نیز تعداد بسیار زیادی از کامپایلرها از این روش برای تخصیص ثبات استفاده می‌کنند. تخصیص ثبات در سطوح متفاوتی از کد میانی می‌تواند انجام شود: در سطح عبارات کد در سطح بلوک‌های پایهٔ کد و در سطح یک روال از کد. تعریف مسئله در طراحی تمامی کامپایلرها این فرض وجود دارد که در بخش میانی کامپایلر که وظیفهٔ بهبود کد را به عهده دارد، بی‌نهایت ثبات برای نگهداری متغیرها وجود دارد. حال مسئلهٔ تخصیص ثبات این‌گونه مطرح می‌شود: «طی تبدیل کد میانیِ کامپایلر به کد ماشین باید با روشی بهینه تمامی ثبات‌های مجازی بر روی ثبات‌های واقعیِ ماشین مورد نظر نگاشت شوند یا در صورت محدودیت ثبات‌های واقعی از حافظهٔ اصلیِ ماشین برای نگهداری آن‌ها استفاده کنیم.» روش‌های مختلف تخصیص ثبات همان‌طور گه در مقدمه گفته شد، تمامی روش‌های کلی تخصیص ثبات به دو دسته تقسیم می‌شوند: سراسری و غیر سراسری. تخصیص ثبات سراسری رنگ‌آمیزی گراف اولین روشی که برای تخصیص ثبات استفاده شد و هم‌چنین محبوب‌ترین روش است، تخصیص ثبات با استفاده از مسئلهٔ معروف رنگ‌آمیزی گراف است. | ## بخش 2: تخصیص ثبات | در این روش برای هر متغیر (و یا همان ثبات‌های مجازی) بازه‌هایی که زنده هستند مشخص می‌شوند؛ یا به عبارتی برای هر متغیر مشخص می‌شود که چه زمانی مقدار آن ارزش دارد که این همان بازهٔ میان تعریف و استفاده از آن متغیر است. حال با استفاده از تعریف بازه‌های زندگی هر متغیر، مسئلهٔ تخصیص ثبات را بر روی مسئلهٔ رنگ‌آمیزی گراف نگاشت می‌کنیم. یال‌های این گراف نیز این‌گونه مشخص می‌شوند: «دو راس در گراف برخورد به هم متصل هستند اگر نقطه‌ای در برنامه وجود داشته باشد که متغیرهای متناظر آن راس‌ها همزمان زنده باشند.» اکنون که گراف برخورد را تعریف کردیم می‌توانیم مسئلهٔ تخصیص ثبات را به عنوان یک مسئلهٔ رنگ‌آمیزی گراف مطرح کنیم. مدل‌سازی مسئلهٔ تخصیص ثبات به عنوان مسئلهٔ رنگ‌آمیزی گراف فرض کنید که به تعداد ثبات‌های ماشین رنگ در اختیار داریم. اگر در نهایت به یک رنگ‌آمیزی معتبر رسیدیم، هر دو راس مجاور رنگ‌های متفاوتی خواهند داشت و این بدین معنا است که هر دو متغیر همزمان زنده در ثبات‌های مختلفی قرار می‌گیرند و با یکدیگر برخوردی نخواهند داشت. اما از آن‌جا که مسئلهٔ رنگ‌آمیزی گراف ان‌پی کامل است، از یک روش مکاشفه‌ای برای تخصیص ثبات استفاده می‌شود. در شکل زیر به‌طور خلاصه پیاده‌سازی تخصیص ثبات با استفاده از رنگ‌آمیزی گراف را مشاهده می‌کنید. در این روش تمامی دستورهای برنامه با هر ترتیب دلخواهی مرتب می‌شوند (که البته در تمامی کامپایلرها ار همان ترتیبی که دستورها در برنامه آمده‌است استفاده می‌شود). سپس بازه‌های زندگیِ هر متغیر ساخته می‌شود که نقطهٔ شروع این بازه دستوری است که آن متغیر را تعریف می‌کند و نقطهٔ پایانی بازه دستوری است که برای آخرین بار از آن متغیر استفاده کرده‌است. پس از ساخت بازه‌های زندگی متغیرها، آن‌ها را بر اساس نقطهٔ شروعشان مرتب می‌کنیم و به همان ترتیب شروع می‌کنیم به تخصیص ثبات؛ اگر ثباتی برای تخصیص وجود داشته که آن را در اختیار آن بازه قرار می‌دهیم و اگر تمامی ثبات‌ها تخصیص یافته باشند باید یکی از متغیرها در حافظهٔ اصلی نگهداری شود. | ## بخش 3: تخصیص ثبات | برای این کار نیز متغیری انتخاب می‌شود که دیرتر از همه استفاده شود (نقطهٔ پایانی بازهٔ آن متغیر از همه بیش‌تر باشد) این روش به صورت خطی تخصیص ثبات را انجام می‌دهد و سربار زمانی آن خیلی کم‌تر از روش رنگ‌آمیزی گراف است و همان‌طور که گفته شد در کامپایلرهای درجا بسیار کاربرد دارد. تخصیص ثبات بر اساس کد میانی با فرم SSA در این روش ابتدا کد میانی کامپایلر به فرم SSA در می‌آید. گراف برخورد حاصل از این کد یک ویژگی شاخص دارد که در رنگ‌آمیزی آن بسیار به ما کمک می‌کند. تخصیص ثبات غیر سراسری روش‌های تخصیص ثبات غیر سراسری، روش‌هایی هستند که کد را به چندین بخش تقسیم می‌کنند (به عنوان مثال این قسمت‌ها می‌توانند همان بلوک‌های پایهٔ کد باشند) و برای هر یک از این بخش‌ها به صورت جداگانه تخصیص ثبات انجام می‌دهند. روش‌های کمی به صورت غیر سراسری پیاده‌سازی شده‌اند و یکی از دلایل آن هماهنگ‌کردن بخش‌های مختلفی هستند که به صورت جداگانه تخصیص ثبات انجام داده‌اند. اما در ادامه یکی از روش‌های غیر سراسری آمده‌است که توانسته‌است کد با کیفیت خوبی تولید کند و در بسیاری از برنامه‌ها کارایی را نسبت دیگر روش‌های سراسری افزایش دهد.Eisl, Josef. تخصیص ثبات ردیابی ایدهٔ کلی این روش بدین گونه است که کد را به دو بخش کلی تقسیم می‌کند: (۱) بخش داغ که قسمت‌هایی از کد را شامل می‌شود که با فرکانس زیادی انجام می‌شود، (۲) بخش سرد که شامل قسمت‌هایی است که کم‌تر استفاده می‌شوند. پس از تقسیم‌بندی کد، برای هر کدام از قسمت‌های کد از روش تخصیص ثبات متناسب آن استفاده می‌کنیم؛ یا به عبارتی سعی می‌کنیم برای بخش‌های داغ کد از روش‌های بسیار دقیق تخصیص ثبات استفاده کنیم تا کارایی کد هنگام اجرا پایین نیاید و برای بخش‌های سرد کد از روش‌های معمولی و سریع استفاده کنیم؛ در نتیجه برای بخش‌هایی از کد که تأثیر چندانی در کارایی ندارند، زمان زیادی را صرف نمی‌کنیم؛ بنابراین بدون از دست دادن کارایی، سربار کامپایل را نیز پایین می‌آوریم. | ## جمع‌بندی | همان‌طور که مشخص است این روش تنها در کامپایلرهای درجا می‌تواند به کار رود (تنها با استفاده از اجرا کردن برنامه می‌توانیم قسمت‌های داغ و سرد آن را مشخص کینم).