تخصیص ثبات ( به انگلیسی: Register Allocation ) یکی از مراحل پایانی کامپایل کدهای برنامه نویسی است که مهم ترین مرحله برای افزایش کارایی کد تولید شده به وسیلهٔ کامپایلر می باشد. اهمیت این مرحله با توجه به افزایش سرعت پردازنده ها و هم چنین افزایش زمان دسترسی به حافظه، روز به روز بیش تر می شود و تأثیر آن را به وضوح می توان بر روی حجم کد تولید شده و هم چنین کارایی آن مشاهده نمود.
کامپایلرها به طور کلی به سه بخش تقسیم می شوند: بخش ابتدایی که زبان سطح بالا را به یک زبان سطح میانی تبدیل می کند. تحلیل لغوی، نحوی، و معنایی در این بخش انجام می شود. بخش میانی که در این بخش روش های زیادی برای بهبود کد به کار گرفته می شوند و در نهایت بخش پایانی کامپایلر که وظیفهٔ تبدیل کد میانی به کد ماشین را بر عهده دارد. در تمامی کامپایلرها، در بخش میانی این فرض وجود دارد که بی نهایت ثبات وجود دارد ( و این ثبات ها را ثبات های مجازی می نامند ) و هیچ نگرانی ای در مورد کمبود ثبات وجود ندارد. اما از آن جایی که تمامی ماشین ها دارای تعداد محدودی ثبات هستند باید در بخش پایانی تمامی ثبات های مجازی به ثبات های واقعی نگاشت شوند. [ ۱]
اولین روش بهینه برای تخصیص ثبات به وسیلهٔ آقای Chaitin و همکارانشان در سال ۱۹۸۱ میلادی ارائه شد که از مسئلهٔ معروف رنگ آمیزی گراف استفاده کردند. [ ۲] در سال ۱۹۹۲ میلادی نیز آقای Briggs در رسالهٔ دکترای خود همان روش Chaitin را بهبود بخشید و امروزه به روش Chaitin - Briggs معروف است. [ ۳] در حال حاضر نیز تعداد بسیار زیادی از کامپایلرها از این روش برای تخصیص ثبات استفاده می کنند. اما از آن جایی که این روش سربار بالایی دارد ( هم از لحاظ زمان کامپایل و هم از لحاظ پیچیدگی مسئله ) در ادامه روش های دیگری مانند اسکن خطی[ ۴] و تخصیص ثبات بر پایهٔ کد میانی با فرم SSA ارائه شدند. [ ۵]
تخصیص ثبات در سطوح متفاوتی از کد میانی می تواند انجام شود: در سطح عبارات کد در سطح بلوک های پایهٔ کد و در سطح یک روال از کد. به مورد اخیر تخصیص ثبات سراسری نیز می گویند. اکثر روش های ارائه شده سراسری هستند. [ ۱]
در طراحی تمامی کامپایلرها این فرض وجود دارد که در بخش میانی کامپایلر که وظیفهٔ بهبود کد را به عهده دارد، بی نهایت ثبات برای نگهداری متغیرها وجود دارد. به این ثبات ها، «ثبات های مجازی» می گویند. حال مسئلهٔ تخصیص ثبات این گونه مطرح می شود:
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفکامپایلرها به طور کلی به سه بخش تقسیم می شوند: بخش ابتدایی که زبان سطح بالا را به یک زبان سطح میانی تبدیل می کند. تحلیل لغوی، نحوی، و معنایی در این بخش انجام می شود. بخش میانی که در این بخش روش های زیادی برای بهبود کد به کار گرفته می شوند و در نهایت بخش پایانی کامپایلر که وظیفهٔ تبدیل کد میانی به کد ماشین را بر عهده دارد. در تمامی کامپایلرها، در بخش میانی این فرض وجود دارد که بی نهایت ثبات وجود دارد ( و این ثبات ها را ثبات های مجازی می نامند ) و هیچ نگرانی ای در مورد کمبود ثبات وجود ندارد. اما از آن جایی که تمامی ماشین ها دارای تعداد محدودی ثبات هستند باید در بخش پایانی تمامی ثبات های مجازی به ثبات های واقعی نگاشت شوند. [ ۱]
اولین روش بهینه برای تخصیص ثبات به وسیلهٔ آقای Chaitin و همکارانشان در سال ۱۹۸۱ میلادی ارائه شد که از مسئلهٔ معروف رنگ آمیزی گراف استفاده کردند. [ ۲] در سال ۱۹۹۲ میلادی نیز آقای Briggs در رسالهٔ دکترای خود همان روش Chaitin را بهبود بخشید و امروزه به روش Chaitin - Briggs معروف است. [ ۳] در حال حاضر نیز تعداد بسیار زیادی از کامپایلرها از این روش برای تخصیص ثبات استفاده می کنند. اما از آن جایی که این روش سربار بالایی دارد ( هم از لحاظ زمان کامپایل و هم از لحاظ پیچیدگی مسئله ) در ادامه روش های دیگری مانند اسکن خطی[ ۴] و تخصیص ثبات بر پایهٔ کد میانی با فرم SSA ارائه شدند. [ ۵]
تخصیص ثبات در سطوح متفاوتی از کد میانی می تواند انجام شود: در سطح عبارات کد در سطح بلوک های پایهٔ کد و در سطح یک روال از کد. به مورد اخیر تخصیص ثبات سراسری نیز می گویند. اکثر روش های ارائه شده سراسری هستند. [ ۱]
در طراحی تمامی کامپایلرها این فرض وجود دارد که در بخش میانی کامپایلر که وظیفهٔ بهبود کد را به عهده دارد، بی نهایت ثبات برای نگهداری متغیرها وجود دارد. به این ثبات ها، «ثبات های مجازی» می گویند. حال مسئلهٔ تخصیص ثبات این گونه مطرح می شود:
wiki: تخصیص ثبات