Range Analysis — dastur nuqtalarida sonli o‘zgaruvchi olishi mumkin bo‘lgan qiymatlar diapazonini statik ravishda hisoblaydigan tahlil. U bounds checkni yo‘qotish, overflowni aniqlash, branchni soddalashtirish va optimizatsiya qonuniyligini isbotlashda ishlatiladi.
Interval hisobi
Interval domain qiymatni [lower, upper] bilan ifodalaydi. x∈[0,9] va y=x+2 bo‘lsa, oddiy interval arithmetic y∈[2,11] beradi. Branch x<5 true yo‘lda x diapazonini [0,4], false yo‘lda [5,9] qilib refine qilishi mumkin.
Fixed point
Join turli control-flow yo‘llar diapazonini qamrab oladigan hull yaratadi. Loopda chegaralar har iteratsiyada kengayib ketishi mumkin; widening fixed pointni tez kafolatlaydi, narrowing esa keyin ayrim aniqlikni qaytaradi. Juda qo‘pol interval o‘zgaruvchilar orasidagi x<y kabi relationni yo‘qotadi.
Son semantikasi
Wrapping integer semantics muhim: unsigned qo‘shish modulo bo‘lsa [250,255]+[1,2] 8 bitda bitta oddiy interval bilan aniq ifodalanmaydi. Compiler IRdagi poison, undefined signed overflow yoki saturating arithmetic alohida transfer function talab qiladi. Floating-point NaN ham ordered intervaldan tashqari holat sifatida saqlanadi.
Aniqlik darajasi
Relational domain, congruence yoki symbolic range intervaldan aniqroq, lekin qimmatroq. Scalar Evolution loop induction variable va trip count uchun yopiq formulalarni topadi. Analyzer maqsadga qarab tez local range va qimmat interprocedural isbotni uyg‘unlashtiradi.
Soundness tekshiruvi
Tekshiruv kichik bit-widthda barcha concrete qiymatlarni exhaustive bajarib, static range ularni qamrashini tekshiradi. Boundary, wraparound, division by zero, shift count va infeasible branchlar qamrab olinadi. Range torligi precision metrikasi, concrete qiymatning tashqarida qolishi esa soundness xatosidir.
Range 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
Range ma’lumoti branch eliminationda predicate doim true yoki false ekanini isbotlaydi. 0≤i<N va N≤len(a) bo‘lsa a[i] bounds checki olib tashlanishi mumkin, lekin N va len orasidagi constraint yo‘qolsa oddiy interval yetmaydi. Path sensitivity branch refinementni saqlaydi, ammo yo‘llar soni eksponential o‘sishi mumkin; merge va predicate abstraction muvozanat beradi. Assumption yoki sanitizer checkdan keyingi yo‘lda range torayadi. Optimizer bu faktni check dominate qilgan hududdagina ishlatishi kerak. Speculative execution xavfsizligi ayrim bounds optimizatsiyalarida alohida hardening talab qilishi mumkin.
Range factning provenance’i branch, assumption yoki arithmetic transferdan kelganini ko‘rsatadi. Bu optimizer noto‘g‘ri bound ishlatganda tashxisni osonlashtiradi. Interprocedural range parameter contractga tayanishi mumkin; caller contractni buzishi mumkin bo‘lgan tilda runtime check kerak. Profile range statik proof emas va faqat speculative guard bilan ishlatiladi.
Range report har program point uchun top va bottom holatlarini oddiy cheksiz intervaldan ajratadi. Bottom unreachable yo‘lni, top esa foydali chegara topilmaganini bildiradi.
Bog‘liq tushunchalar
interval analysis, abstract interpretation, value range propagation, bounds checking, widening, scalar evolution