Register allocation — kompilyatorning dasturdagi vaqtinchalik qiymatlar va o‘zgaruvchilarni protsessor registrlariga joylashtirish jarayonidir. Registrlar xotiradan tezroq va soni cheklangan bo‘lgani uchun, qaysi qiymat qachon registrda turishi ishlab chiqarilgan kod tezligi hamda hajmiga sezilarli ta’sir qiladi. Sig‘magan qiymat stack yoki boshqa xotiraga vaqtincha yoziladi.
Live range va to‘qnashuv
Qiymat aniqlangan nuqtadan oxirgi ishlatilishigacha uning live range’i hisoblanadi. Ikki qiymat bir vaqtda kerak bo‘lsa, ular bir xil fizik registrni bo‘lisha olmaydi. Kompilyator control-flow graph bo‘ylab liveness analysis bajarib, qaysi nuqtalarda qiymatlar tirik ekanini aniqlaydi.
Interference graphda har tugun virtual registrni, qirra esa ikki qiymatning bir vaqtda tirikligini bildiradi. Register allocation graph coloring masalasiga o‘xshatiladi: qo‘shni tugunlarga turli fizik registr beriladi. Umumiy masala murakkab bo‘lgani sabab amaliy kompilyatorlar heuristika va taxminiy algoritmlardan foydalanadi.
Asosiy algoritmlar
Graph-coloring allocator global sifatli taqsimot topishga intiladi. Linear scan esa live interval’larni tartiblab, ularni bir marta yoki kam sonli o‘tishda registrlarga joylaydi. U tez kompilyatsiya talab qiladigan JIT tizimlarida keng qo‘llanadi, garchi ayrim holatda ko‘proq spill yaratishi mumkin.
Kompilyator region, loop yoki basic block darajasida turli strategiyani birlashtirishi mumkin. Issiq sikldagi qiymatni registrda saqlash sovuq xato yo‘lidagi qiymatdan foydaliroq. Profil ma’lumoti allocatorga bajarilish chastotasini hisobga olish imkonini beradi.
Spill va qayta yuklash
Registr yetishmaganda qiymat memory slotga spill qilinadi va kerak bo‘lganda reload qilinadi. Bu qo‘shimcha load/store ko‘rsatmalari, stack joyi va ba’zan cache bosimini keltirib chiqaradi. Spill cost qiymatning ishlatilish soni, loop chuqurligi va qayta hisoblash narxiga qarab baholanadi.
Rematerialization oddiy konstant yoki manzilni xotiradan yuklash o‘rniga qayta hisoblaydi. Live range splitting qiymatning faqat kerakli qismida registr band qilishiga imkon beradi. Coalescing esa move bilan bog‘langan virtual registrlarni bitta fizik registrga berib, keraksiz ko‘chirishni olib tashlaydi.
Arxitektura cheklovlari
Calling convention ayrim registrlarni caller-saved, boshqalarini callee-saved deb belgilaydi. Function call atrofida tirik qiymat uchun qaysi turdagi registr arzonligi shunga bog‘liq. Ayrim ko‘rsatmalar operandni aniq registrda talab qiladi yoki registr juftligidan foydalanadi. Integer, floating-point, vector va predicate registrlari alohida sinflarga ega bo‘lishi mumkin.
Register allocation instruction scheduling bilan o‘zaro ta’sirlashadi. Ko‘proq parallelizm uchun qiymatlarni uzoqroq tirik saqlash register pressure’ni oshiradi. Yaxshi backend scheduling, allocation va spill qarorlarini maqsad arxitektura latency hamda throughput xususiyatlari bilan muvofiqlashtiradi.
Natijani baholash
Disassemblydagi ortiqcha load/storelar va katta stack frame spill belgisi bo‘lishi mumkin. Compiler reportlari register pressure hamda vectorization muvaffaqiyatsizligi sababini ko‘rsatadi. Biroq manba kodni faqat registr uchun murakkablashtirishdan oldin profiler bilan haqiqiy bottleneck tasdiqlanadi.
SSA bilan aloqa
Static Single Assignment shaklida har virtual qiymat bir marta aniqlanadi, bu data flow va live range’ni tahlil qilishni soddalashtiradi. Control-flow yo‘llari qo‘shilgandagi phi qiymatlar keyinchalik parallel move’larga aylantiriladi. Allocator bu move’larni coalesce qilishga urinadi, biroq interference mavjud bo‘lsa registrlarni ajratadi. Debug buildda o‘zgaruvchining qiymati optimallashtirish sabab turli vaqtda registr, stack yoki umuman hisoblab bo‘lmaydigan holatda bo‘lishi mumkin. Debug location list shu o‘zgarishni debuggerga tasvirlaydi.
Bog‘liq tushunchalar
Compiler backend, Liveness analysis, Graph coloring, Spill, Calling convention, Instruction scheduling