Control Dependence — bir dastur nuqtasining bajarilishi boshqa branch yoki predicate natijasiga bog‘liq bo‘lishini ifodalovchi munosabat. Masalan, if (p) S; tuzilmasida S operatori p shartiga control-dependent hisoblanadi.
Formal ta’rif
Control-flow graphda bu munosabat post-dominance orqali aniqlanadi. Y tugun X ga control-dependent bo‘lishi uchun X ning bir successor yo‘lida Y post-dominate qilishi, boshqa successor yo‘lida esa qilmasligi kerak. Intuitiv ravishda X dagi branch Y bajariladimi yoki chetlab o‘tiladimi, shuni hal qiladi.
Post-dominance
Post-dominator tugun exitga boradigan har yo‘lda uchraydi. Immediate post-dominatorlar daraxti va dominance frontierga o‘xshash hisoblash control dependence graph qurishga yordam beradi. Multiple exit, exception edge va non-terminating loop modelga kiritilmasa, natija noto‘liq chiqishi mumkin.
Misol
if (x > 0) y = 1; else y = 2; misolida ikki assignment predicate’ga bog‘liq, undan keyingi print(y) esa odatda bog‘liq emas, chunki ikkala branch ham unga keladi. Nested branchlarda bitta instruction bir nechta predicate’ga transitive bog‘lanishi mumkin.
Tahlillardagi roli
Control dependence program slicing, parallelization, speculative execution va information-flow analysisda ishlatiladi. Data dependence bilan birga Program Dependence Graph hosil qiladi. Branchni ko‘chirish yoki predicationga aylantirishda faqat control edge emas, side effect va exception tartibi ham saqlanishi kerak.
Grafni tekshirish
Validator kichik CFGlar uchun barcha exit yo‘llarini sanab, post-dominator etalonini hisoblaydi. Unreachable blocklar oldindan ajratiladi. Exception, early return, loop break va switch fall-through testlari nazorat qilinadi; faqat structured source misollari arbitrary CFG xatolarini topmasligi mumkin.
Control Dependence 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
Control dependence ba’zan source nesting bilan mos kelmaydi. goto, exception va short-circuit expression sabab lexical block bir predicate ichida ko‘rinsa ham CFG bo‘yicha boshqa bog‘lanish chiqishi mumkin. Weak va strong control dependence tushunchalari infinite pathlarni qanday talqin qilishida farqlanadi. Securityda implicit flow if(secret) public=1 ko‘rinishida aynan control dependence orqali aniqlanadi, lekin termination-sensitive siyosat non-terminationni ham kuzatadi. Optimization branchni if-conversion bilan predicate instructionlarga aylantirganda dependence yo‘qolmaydi; u control edge’dan data-like predicate dependencega ko‘chadi. Tahlilchi representation o‘zgarganini hisobga olishi kerak.
Control-dependence graph edge’i predicate natijasining qaysi qiymati Y ga olib borishini ham belgilashi mumkin. Bu slicingda faqat condition node’ni emas, kerakli true yoki false yo‘lni tushuntiradi. Graph serialization CFG versiyasiga bog‘lanadi; block split yoki edge removaldan keyin incremental updater edge’larni tuzatmasa, natija qayta hisoblanadi.
Amaliy hisobotda predicate blocki, bog‘langan block, true/false edge va post-dominator dalili bir qatorda beriladi. Bu natijani CFG viewerda ko‘z bilan tekshirishni tezlashtiradi.
Bog‘liq tushunchalar
post-dominator, control-flow graph, program dependence graph, branch, program slicing, data dependence