Kodning o'zgarmas harakati - Loop-invariant code motion

Yilda kompyuter dasturlash, o'zgarmas kod iboralar yoki iboralardan iborat (an. da majburiy dasturlash tili ) dasturning semantikasiga ta'sir qilmasdan tsikl tanasi tashqarisiga ko'chirilishi mumkin. Kodning o'zgarmas harakati (shuningdek, deyiladi ko'tarish yoki skalar targ'iboti) a kompilyatorni optimallashtirish bu harakatni avtomatik ravishda amalga oshiradigan.

Misol

Quyidagi kod namunasida ikkita optimallashtirish qo'llanilishi mumkin. 

int men = 0;esa (men < n) {    x = y + z;    a[men] = 6 * men + x * x;    ++men;}

Hisoblash bo'lsa-da x = y + z va x * x loop-invariant hisoblanadi, kodni tsikl tashqarisiga ko'chirishdan oldin ehtiyot choralarini ko'rish kerak. Bu ilmoqning holati bo'lishi mumkin yolg'on (masalan, agar n manfiy qiymatga ega) va bunday holatda tsikl tanasi umuman bajarilmasligi kerak. To'g'ri xatti-harakatni kafolatlashning usullaridan biri bu tsikldan tashqarida shartli filialdan foydalanishdir. Loop holatini baholash bo'lishi mumkin yon effektlar, shuning uchun. tomonidan qo'shimcha baholash agar o'rnini bosish bilan qurish kompensatsiya qilinishi kerak esa a bilan pastadir bajaring {} while. Agar ishlatilgan kod bo'lsa bajaring {} while birinchi navbatda, butun qo'riqlash jarayoni kerak emas, chunki pastadir tanasi kamida bir marta bajarilishi kafolatlanadi. 

int men = 0;agar (men < n) {    x = y + z;    int konst t1 = x * x;    qil {        a[men] = 6 * men + t1;        ++men;    } esa (men < n);}

Ushbu kodni yanada optimallashtirish mumkin. Masalan, quvvatni kamaytirish pastadir ichidagi ikkita ko'paytmani olib tashlashi mumkin (6 * i va a [i]) va induksiya o'zgaruvchisi keyinchalik yo'q qilish mumkin men to'liq. Beri 6 * i bilan blokirovka qilish kerak men o'zi, ikkalasiga ham ega bo'lishning hojati yo'q.

O'zgarmas kodni aniqlash

Odatda, a ta'riflarni tahlil qilish ibora yoki ifoda tsiklining o'zgarmasligini aniqlash uchun ishlatiladi.

Masalan, ba'zi bir oddiy ifodalarning operandlari bo'yicha erishiladigan barcha ta'riflar tsikldan tashqarida bo'lsa, ifoda tsikldan tashqariga chiqarilishi mumkin.

Ma'lumotlar oqimiga bog'liqlikni tahlil qilish yordamida so'nggi ish [1] nafaqat o'zgarmas buyruqlarni, balki ichki tsikl kabi kattaroq kod fragmentlarini aniqlashga imkon beradi. Tahlil shuningdek, ixtiyoriy darajadagi kvazinvariantlarni, ya'ni buyruqlar yoki tsikl tanasining belgilangan miqdordagi takrorlanishidan so'ng o'zgarmas bo'ladigan kod fragmentlarini aniqlaydi.

Foyda

Loop-invariant kodi ko'chadan chiqarilib, tezroq tezlikni ta'minlaydi. Ushbu transformatsiyaning yana bir ta'siri - bu doimiylikni registrlarda saqlashga imkon beradi va manzilni hisoblashi va har bir takrorlashda xotiraga (yoki kesh liniyasiga) kirishga hojat yo'q.

Ammo, agar juda ko'p o'zgaruvchilar yaratilsa, yuqori bo'ladi bosimni ro'yxatdan o'tkazing, ayniqsa, 32-bit kabi bir nechta registrga ega protsessorlarda x86. Agar kompilyatorning registrlari tugasa, ba'zi o'zgaruvchilar bo'ladi to'kilgan. Bunga qarshi turish uchun teskari optimallashtirish amalga oshirilishi mumkin, qayta moddiylashtirish.

Shuningdek qarang

Qo'shimcha o'qish

  • Aho, Alfred V.; Seti, Ravi; & Ullman, Jeffri D. (1986). Tuzuvchilar: printsiplar, usullar va vositalar. Addison Uesli. ISBN  0-201-10088-6.

Tashqi havolalar

  1. ^ Moyen, Jan-Iv; Rubiano, Tomas; Seiller, Tomas (2017). "Loop kvazi-invariant qismlarini aniqlash". Tekshirish va tahlil qilishning avtomatlashtirilgan texnologiyasi. 10482: 91–108. doi:10.1007/978-3-319-68167-2_7.