Use-Def Chain — dasturdagi har bir variable foydalanishini unga yetib kelishi mumkin bo‘lgan definitionlar bilan bog‘laydigan data-flow tuzilma. U qiymat qayerdan kelganini ko‘rsatadi va constant propagation, slicing hamda diagnostikada ishlatiladi.
Qurish algoritmi
Control-flow graph bo‘yicha reaching definitions tahlili bajariladi. Bir variable yozilganida oldingi definitionlar kill qilinadi, yangi definition gen to‘plamiga qo‘shiladi. Block kirishidagi definitionlar predecessor chiqishlarining birlashmasidir; fixed point topilgach, block ichidagi har use uchun amaldagi definitionlar qayd etiladi.
Yo‘llar bo‘yicha misol
if (p) x=1; else x=2; print(x); da print ichidagi x use’i ikkala assignmentga bog‘lanadi. x=0; x=1; print(x); da esa birinchi definition ikkinchisi tomonidan kill qilinadi. Uninitialized use uchun zanjir bo‘sh qolishi mumkin va bu diagnostika signalidir.
SSA bilan aloqa
SSA formda ko‘p yo‘ldan kelgan qiymatlar phi instruction orqali bitta yangi definitionga birlashtiriladi. Shunda har use odatda bitta dominating definitionga ega bo‘ladi. Oddiy mutable IRda esa bitta use bir nechta reaching definitionga ega bo‘lishi tabiiy.
Xotira amallari
Memory use-def chain pointer aliaslari sabab register variable’dan murakkabroq. *p yozuvi *q o‘qishiga ta’sir qilishi mumkin bo‘lsa, memory SSA yoki conservative alias edge kerak. Function callning noma’lum side effectlari ham global va heap definitionlarini o‘zgartiruvchi deb qaralishi mumkin.
Invariantlar
Tekshiruvda har chain bo‘ylab definitiondan use’gacha kill qiluvchi yozuvsiz kamida bitta CFG yo‘li mavjudligi nazorat qilinadi. Dead blocklar ajratiladi, phi operandlari predecessor edge kontekstida tekshiriladi. Kichik graf uchun exhaustive path etaloni fixed-point natijasi bilan solishtiriladi.
Use-Def Chain 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
Use-def ma’lumotini qurishda variable nomi yetarli emas: lexical scope va SSA versioni bir xil yozilgan identifierlarni ajratadi. Debugger “bu qiymat qayerdan keldi” so‘rovini chain orqali source declaration va assignmentgacha olib borishi mumkin. Taint analysisda sink use’dan orqaga yurib, mumkin bo‘lgan source definitionlar topiladi. Interprocedural holatda actual argument formal parameter definitioniga, return use esa callee return definitionlariga summary edge orqali bog‘lanadi. Full inlining qilmasdan summary ishlatish scalabilityni saqlaydi. Recursive call fixed point talab qiladi; contextni haddan tashqari birlashtirish esa foydasiz ko‘p definition qaytarishi mumkin.
Use-def query natijasida definitionlar tartibi deterministik bo‘lishi debug va test uchun muhim; odatda block yoki instruction tartibi ishlatiladi. Chain cache’i CFG va alias-analysis revisioniga bog‘lanadi. Source edit yangi assignment qo‘shsa, faqat lokal blockni yangilash yetmasligi mumkin, chunki definition successorlar orqali uzoq use’larga yetib boradi.
Bog‘liq tushunchalar
reaching definitions, def-use chain, SSA, data-flow analysis, symbol use, program slicing