تخصیص ثبات
تخصیص ثبات (به انگلیسی: Register Allocation) یکی از مراحل پایانی کامپایل کدهای برنامه‌نویسی است که مهم‌ترین مرحله برای افزایش کارایی کد تولید شده به‌وسیلهٔ کامپایلر می‌باشد. اهمیت این مرحله با توجه به افزایش سرعت پردازنده‌ها و هم‌چنین افزایش زمان دسترسی به حافظه، روز به روز بیش‌تر می‌شود و تأثیر آن را به وضوح می‌توان بر روی حجم کد تولید شده و هم چنین کارایی آن مشاهده نمود.
کامپایلرها به‌طور کلی به سه بخش تقسیم می‌شوند: بخش ابتدایی که زبان سطح بالا را به یک زبان سطح میانی تبدیل می‌کند. تحلیل لغوی، نحوی، و معنایی در این بخش انجام می‌شود. بخش میانی که در این بخش روش‌های زیادی برای بهبود کد به کار گرفته می‌شوند و در نهایت بخش پایانی کامپایلر که وظیفهٔ تبدیل کد میانی به کد ماشین را بر عهده دارد. در تمامی کامپایلرها، در بخش میانی این فرض وجود دارد که بی‌نهایت ثبات وجود دارد (و این ثبات‌ها را ثبات‌های مجازی می‌نامند) و هیچ نگرانی‌ای در مورد کمبود ثبات وجود ندارد. اما از آن‌جایی که تمامی ماشین‌ها دارای تعداد محدودی ثبات هستند باید در بخش پایانی تمامی ثبات‌های مجازی به ثبات‌های واقعی نگاشت شوند.[1]
اولین روش بهینه برای تخصیص ثبات به‌وسیلهٔ آقای Chaitin و همکارانشان در سال ۱۹۸۱ میلادی ارائه شد که از مسئلهٔ معروف رنگ‌آمیزی گراف استفاده کردند.[2] در سال ۱۹۹۲ میلادی نیز آقای Briggs در رسالهٔ دکترای خود همان روش Chaitin را بهبود بخشید و امروزه به روش Chaitin-Briggs معروف است.[3] در حال حاضر نیز تعداد بسیار زیادی از کامپایلرها از این روش برای تخصیص ثبات استفاده می‌کنند. اما از آن‌جایی که این روش سربار بالایی دارد (هم از لحاظ زمان کامپایل و هم از لحاظ پیچیدگی مسئله) در ادامه روش‌های دیگری مانند اسکن خطی[4] و تخصیص ثبات بر پایهٔ کد میانی با فرم SSA ارائه شدند.[5]
تخصیص ثبات در سطوح متفاوتی از کد میانی می‌تواند انجام شود: در سطح عبارات کد در سطح بلوک‌های پایهٔ کد و در سطح یک روال از کد. به مورد اخیر تخصیص ثبات سراسری نیز می‌گویند. اکثر روش‌های ارائه شده سراسری هستند.[1]
تعریف مسئله
در طراحی تمامی کامپایلرها این فرض وجود دارد که در بخش میانی کامپایلر که وظیفهٔ بهبود کد را به عهده دارد، بی‌نهایت ثبات برای نگهداری متغیرها وجود دارد. به این ثبات‌ها، «ثبات‌های مجازی» می‌گویند. حال مسئلهٔ تخصیص ثبات این‌گونه مطرح می‌شود:
«طی تبدیل کد میانیِ کامپایلر به کد ماشین باید با روشی بهینه تمامی ثبات‌های مجازی بر روی ثبات‌های واقعیِ ماشین مورد نظر نگاشت شوند یا در صورت محدودیت ثبات‌های واقعی از حافظهٔ اصلیِ ماشین برای نگهداری آن‌ها استفاده کنیم.»
روش‌های مختلف تخصیص ثبات
همان‌طور گه در مقدمه گفته شد، تمامی روش‌های کلی تخصیص ثبات به دو دسته تقسیم می‌شوند: سراسری و غیر سراسری. در ادامه مهم‌ترین روش‌های تخصیص ثبات در هر یک از این تقسیم‌بندی‌ها می‌آید.
رنگ‌آمیزی گراف
اولین روشی که برای تخصیص ثبات استفاده شد و هم‌چنین محبوب‌ترین روش است، تخصیص ثبات با استفاده از مسئلهٔ معروف رنگ‌آمیزی گراف است. در این روش برای هر متغیر (و یا همان ثبات‌های مجازی) بازه‌هایی که زنده هستند مشخص می‌شوند؛ یا به عبارتی برای هر متغیر مشخص می‌شود که چه زمانی مقدار آن ارزش دارد که این همان بازهٔ میان تعریف و استفاده از آن متغیر است. حال با استفاده از تعریف بازه‌های زندگی هر متغیر، مسئلهٔ تخصیص ثبات را بر روی مسئلهٔ رنگ‌آمیزی گراف نگاشت می‌کنیم.
گراف برخورد
اولین قدم ساخت «گراف برخورد» است. راس‌های این گراف همان بازه‌های زندگی متغیرها هستند. یال‌های این گراف نیز این‌گونه مشخص می‌شوند: «دو راس در گراف برخورد به هم متصل هستند اگر نقطه‌ای در برنامه وجود داشته باشد که متغیرهای متناظر آن راس‌ها همزمان زنده باشند.» اکنون که گراف برخورد را تعریف کردیم می‌توانیم مسئلهٔ تخصیص ثبات را به عنوان یک مسئلهٔ رنگ‌آمیزی گراف مطرح کنیم.
مدل‌سازی مسئلهٔ تخصیص ثبات به عنوان مسئلهٔ رنگ‌آمیزی گراف
فرض کنید که به تعداد ثبات‌های ماشین رنگ در اختیار داریم. حال با این رنگ‌ها به رنگ‌آمیزی گراف برخورد می‌پردازیم. اگر در نهایت به یک رنگ‌آمیزی معتبر رسیدیم، هر دو راس مجاور رنگ‌های متفاوتی خواهند داشت و این بدین معنا است که هر دو متغیر همزمان زنده در ثبات‌های مختلفی قرار می‌گیرند و با یکدیگر برخوردی نخواهند داشت. اما از آن‌جا که مسئلهٔ رنگ‌آمیزی گراف ان‌پی کامل است، از یک روش مکاشفه‌ای برای تخصیص ثبات استفاده می‌شود. در شکل زیر به‌طور خلاصه پیاده‌سازی تخصیص ثبات با استفاده از رنگ‌آمیزی گراف را مشاهده می‌کنید.
اسکن خطی
این روش سریع‌ترین روش موجود برای تخصیص ثبات است و تقریباً در تمامی کامپایلرهای درجا از آن استفاده می‌شود. در این روش تمامی دستورهای برنامه با هر ترتیب دلخواهی مرتب می‌شوند (که البته در تمامی کامپایلرها ار همان ترتیبی که دستورها در برنامه آمده‌است استفاده می‌شود). سپس بازه‌های زندگیِ هر متغیر ساخته می‌شود که نقطهٔ شروع این بازه دستوری است که آن متغیر را تعریف می‌کند و نقطهٔ پایانی بازه دستوری است که برای آخرین بار از آن متغیر استفاده کرده‌است. پس از ساخت بازه‌های زندگی متغیرها، آن‌ها را بر اساس نقطهٔ شروعشان مرتب می‌کنیم و به همان ترتیب شروع می‌کنیم به تخصیص ثبات؛ اگر ثباتی برای تخصیص وجود داشته که آن را در اختیار آن بازه قرار می‌دهیم و اگر تمامی ثبات‌ها تخصیص یافته باشند باید یکی از متغیرها در حافظهٔ اصلی نگهداری شود. برای این کار نیز متغیری انتخاب می‌شود که دیرتر از همه استفاده شود (نقطهٔ پایانی بازهٔ آن متغیر از همه بیش‌تر باشد)
این روش به صورت خطی تخصیص ثبات را انجام می‌دهد و سربار زمانی آن خیلی کم‌تر از روش رنگ‌آمیزی گراف است و همان‌طور که گفته شد در کامپایلرهای درجا بسیار کاربرد دارد.
تخصیص ثبات بر اساس کد میانی با فرم SSA
در این روش ابتدا کد میانی کامپایلر به فرم SSA در می‌آید. گراف برخورد حاصل از این کد یک ویژگی شاخص دارد که در رنگ‌آمیزی آن بسیار به ما کمک می‌کند. گراف برخورد در کدهای به فرم SSA همواره وتری هستند. گراف‌های وتری در زمان چند جمله‌ای قابل رنگ‌آمیزی هستند[6] و این موضوع تخصیص ثبات را بسیار تسریع می‌کند.
تخصیص ثبات غیر سراسری
روش‌های تخصیص ثبات غیر سراسری، روش‌هایی هستند که کد را به چندین بخش تقسیم می‌کنند (به عنوان مثال این قسمت‌ها می‌توانند همان بلوک‌های پایهٔ کد باشند) و برای هر یک از این بخش‌ها به صورت جداگانه تخصیص ثبات انجام می‌دهند. روش‌های کمی به صورت غیر سراسری پیاده‌سازی شده‌اند و یکی از دلایل آن هماهنگ‌کردن بخش‌های مختلفی هستند که به صورت جداگانه تخصیص ثبات انجام داده‌اند. اما در ادامه یکی از روش‌های غیر سراسری آمده‌است که توانسته‌است کد با کیفیت خوبی تولید کند و در بسیاری از برنامه‌ها کارایی را نسبت دیگر روش‌های سراسری افزایش دهد.[7]
تخصیص ثبات ردیابی[7]
ایدهٔ کلی این روش بدین گونه است که کد را به دو بخش کلی تقسیم می‌کند: (۱) بخش داغ که قسمت‌هایی از کد را شامل می‌شود که با فرکانس زیادی انجام می‌شود، (۲) بخش سرد که شامل قسمت‌هایی است که کم‌تر استفاده می‌شوند. پس از تقسیم‌بندی کد، برای هر کدام از قسمت‌های کد از روش تخصیص ثبات متناسب آن استفاده می‌کنیم؛ یا به عبارتی سعی می‌کنیم برای بخش‌های داغ کد از روش‌های بسیار دقیق تخصیص ثبات استفاده کنیم تا کارایی کد هنگام اجرا پایین نیاید و برای بخش‌های سرد کد از روش‌های معمولی و سریع استفاده کنیم؛ در نتیجه برای بخش‌هایی از کد که تأثیر چندانی در کارایی ندارند، زمان زیادی را صرف نمی‌کنیم؛ بنابراین بدون از دست دادن کارایی، سربار کامپایل را نیز پایین می‌آوریم.
همان‌طور که مشخص است این روش تنها در کامپایلرهای درجا می‌تواند به کار رود (تنها با استفاده از اجرا کردن برنامه می‌توانیم قسمت‌های داغ و سرد آن را مشخص کینم).
منابع
- Aho, Alfred V. , Ravi Sethi, and Jeffrey D. Ullman. Compilers, Principles, Techniques. Boston: Addison wesley, 1986.
- Chaitin, Gregory J. , et al. "Register allocation via coloring." Computer languages 6.1 (1981): 47-57
- Briggs, Preston. Register allocation via graph coloring. Diss. Rice University, 1992.
- Poletto, Massimiliano, and Vivek Sarkar. "Linear scan register allocation." ACM Transactions on Programming Languages and Systems (TOPLAS) 21.5 (1999): 895-913.
- Hack, Sebastian, Daniel Grund, and Gerhard Goos. "Register allocation for programs in SSA-form." International Conference on Compiler Construction. Springer Berlin Heidelberg, 2006.
- Blair, Jean RS, and Barry Peyton. "An introduction to chordal graphs and clique trees." Graph theory and sparse matrix computation. Springer New York, 1993. 1-29.
- Eisl, Josef. "Trace register allocation." Companion Proceedings of the 2015 ACM SIGPLAN International Conference on Systems, Programming, Languages and Applications: Software for Humanity. ACM, 2015.