Liveness Analysis — dastur nuqtasida variable yoki virtual registerning joriy qiymati kelajakda qayta yozilishidan oldin o‘qilishi mumkinligini aniqlaydigan backward data-flow tahlili. Natija register allocation va dead code elimination uchun asos bo‘ladi.
Data-flow tenglamalari
Har basic block uchun USE — definitiondan oldin o‘qilgan nomlar, DEF — block yozgan nomlar. Tenglamalar OUT[B] = ⋃ IN[S] barcha successorlar bo‘yicha va IN[B] = USE[B] ∪ (OUT[B] − DEF[B]). Qiymatlar bo‘sh to‘plamdan fixed pointgacha iteratsiya qilinadi.
Sikl va fixed point
x=1; y=x+2; x=3; return y; da birinchi x qiymati ikkinchi operatorda live, ammo x=3 dan keyingi qiymat o‘qilmasa dead. Loop back-edge fixed-pointni zarur qiladi: keyingi iteratsiyadagi use oldingi iteratsiya oxiridagi qiymatni live qilishi mumkin.
Maxsus edge’lar
May analysis bo‘lgani uchun successorlar bo‘yicha union olinadi: hech bo‘lmaganda bitta yo‘lda use bo‘lsa, qiymat live. Exception edge, call clobber va phi operandlari modelga aniq kiritiladi. Phi use’i successor block boshida emas, tegishli predecessor edge oxirida sodir bo‘ladi.
Register bosimi
Interference graphda bir vaqtda live bo‘lgan virtual registerlar bir physical registerga joylashtirilmaydi. Juda ko‘p live qiymat register pressure va spillni oshiradi. Livenessning aniqligi performancega ta’sir qiladi, biroq konservativ ortiqcha live belgilash odatda correctnessni saqlaydi.
Natijani tekshirish
Sinovda instruction-level live-in/live-out to‘plamlari qo‘lda tuzilgan CFG bilan solishtiriladi. Dead block, loop, early return, exception va phi edge holatlari qamrab olinadi. Fixed pointdan so‘ng barcha tenglamalar aynan bajarilishi validator orqali qayta tekshiriladi.
Liveness Analysis bo‘yicha tahlil natijasi faqat yakuniy xulosa bilan emas, uni hosil qilgan IR versiyasi, target xususiyatlari va qo‘llangan taxminlar bilan birga saqlanadi. Compiler passlari ketma-ket o‘zgarganda oldingi natija avtomatik ravishda haqiqiy deb olinmaydi: tegishli dependencylar invalidatsiya qilinib, zarur qism qayta hisoblanadi. Debug rejimida asosiy invariant buzilgan nuqta va undan oldingi transformatsiya qayd etiladi; release rejimida esa tekshiruvlarning arzon qismi qoldiriladi. Shu yondashuv nazariy jihatdan qonuniy qoida implementatsiya xatosi yoki noto‘g‘ri cost model sabab zararli qarorga aylangan holatni ajratishga yordam beradi.
Kengaytirilgan jihatlar
Liveness va scope bir xil emas: source variable lexical scope ichida bo‘lsa ham, oxirgi use’dan keyin uning qiymati dead bo‘lishi mumkin. Aksincha, debug rejim compiler variable qiymatini kuzatish uchun artificial use qo‘shib, livenessni uzaytiradi. Call instruction atrofida ABI caller-saved va callee-saved registerlar modeli physical livenessga ta’sir qiladi. Sparse liveness faqat definition-use nuqtalari va dominance frontier atrofida hisoblab, zich bitset iteratsiyasini kamaytirishi mumkin. Katta functionda bitset compression, reverse postorder worklist va faqat o‘zgargan predecessorlarni qayta navbatga qo‘yish compile vaqtini sezilarli kamaytiradi.
Liveness natijasi register class bo‘yicha ajratilishi mumkin: integer va vector qiymatlar bir xil physical poolga da’vogarlik qilmaydi. Subregister va overlapping registerlar target-specific alias model talab qiladi. Live interval endpointining inclusive yoki exclusive talqini hujjatlashtiriladi; aks holda ketma-ket definition va use’lar keraksiz interference edge yaratadi.
Bog‘liq tushunchalar
data-flow analysis, live variable, register allocation, interference graph, dead code elimination, control-flow graph