Loop Unswitching — sikl davomida o‘zgarmaydigan shartni loop tashqarisiga chiqarib, shartning har qiymati uchun alohida loop nusxasi yaratadigan optimallashtirish. Natijada ichki iteratsiyadagi branch yo‘qoladi.
Transformatsiya shakli
for i { if (flag) A(i); else B(i); } da flag loop-invariant bo‘lsa, tashqarida if (flag) tanlanib, biri faqat A, ikkinchisi faqat B bajaradigan ikki loop hosil qilinadi. Bu branch overheadni kamaytiradi va har nusxada constant propagation hamda vectorizationni kuchaytiradi.
Invariantlik isboti
Shart loop body tomonidan o‘zgartirilmasligi va chaqiriqlar orqali bilvosita yozilmasligi isbotlanadi. Agar predicate o‘qilishi exception, volatile yoki atomic observable effectga ega bo‘lsa, uni bir marta o‘qish semantikani o‘zgartirishi mumkin. Alias analysis invariantlikni tasdiqlashda muhim.
Kod hajmi
Asosiy salbiy tomon code size o‘sishidir. Bir nechta invariant branch kombinatsiyasi loop nusxalarini eksponential ko‘paytirishi mumkin. Compiler threshold va profile yordamida faqat issiq, foydali branchni unswitch qiladi; sovuq yo‘l alohida saqlanishi mumkin.
Variantlar
Partial unswitching murakkab predicate’ning faqat invariant qismini tashqariga chiqaradi. Guarded versioning esa runtime condition asosida optimized va original loop orasidan tanlaydi. Bu usullar static isbot yetarli bo‘lmagan, lekin tez-tez uchraydigan holatni optimallashtiradi.
Nazorat
Sinov flagning true/false holati, zero trip count, body ichidagi hidden alias write va exceptionli predicate bilan bajariladi. Branch counter kamayishi performance foydasini ko‘rsatadi, binary size esa xarajatni o‘lchaydi. Originaldagi predicate evaluation soni semantik jihatdan observable bo‘lmasligi shart.
Loop Unswitching 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
Unswitch qilingan ikki loopdan keyingi qiymatlar control-flow merge’da phi orqali birlashtiriladi. Loopda multiple exit bo‘lsa har nusxaning exit edge’lari va live-out qiymatlari mos ravishda klonlanadi. Debug locationlar klon instructionlarda saqlansa breakpoint bir source satrining bir nechta machine addressiga mos keladi. Profile probability tashqi branchga ko‘chiriladi; original per-iteration probabilityni bevosita nusxalash noto‘g‘ri frequency beradi. Deoptimization yoki OSR entry mavjud JITda loopni klonlash state mappingni ham takrorlashni talab qiladi. Shu sabab transformatsiya faqat CFG nusxalash emas, runtime metadata operatsiyasi hamdir.
Unswitchingdan oldin loop body hajmi va predicate frequency estimate qilinadi. Bir nusxa deyarli hech qachon ishlamasa, cold loop out-of-line joylashtirilishi mumkin. Klonlangan alias scope va access-group metadata yangi instructionlarga to‘g‘ri ko‘chiriladi. Metadata tashlab yuborilsa keyingi vectorization imkoniyati yo‘qoladi; noto‘g‘ri ko‘chirilsa soundness xavfi tug‘iladi.
Compiler statistikasi klonlangan block va instruction sonini, tashqariga chiqarilgan predicate hamda keyingi soddalashtirishlarni qayd etadi. Bu code-size limitini sozlashga yordam beradi.
Bog‘liq tushunchalar
loop-invariant code motion, loop versioning, branch prediction, code size, alias analysis, vectorization