Instruction Selection — compiler backendida oraliq tasvirdagi amallarni target protsessorning machine instructionlari yoki instruction patternlariga moslashtirish bosqichi. Maqsad semantikani saqlagan holda tezlik, kod hajmi va target cheklovlariga mos ketma-ketlik tanlashdir.
Pattern qoplash
Oddiy tree covering IR expression tree’ni patternlar bilan qoplaydi. Masalan, add va memory load alohida instruction bo‘lishi yoki target addressing mode ularni bitta instructionda birlashtirishi mumkin. Har pattern costga ega; dynamic programming subtree uchun eng arzon qoplamani topadi.
DAG muammosi
IR aslida DAG bo‘lsa common subexpression bir nechta use’ga ega. Uni treega takrorlash hisobni ko‘paytirishi mumkin, shuning uchun DAG covering yoki oldindan materialization qarori kerak. Control-flow, flags, condition code va multi-result instructionlar oddiy tree modelini yanada boyitadi.
Target cheklovlari
Selection register allocationdan oldin yoki u bilan yaqin aloqada bajariladi. Pattern specific register class, immediate diapazoni, alignment yoki operand bog‘lanishini talab qilishi mumkin. Legalization target qo‘llamaydigan type va amallarni kichik instructionlarga yoki library callga ajratadi.
Tanlash strategiyasi
Greedy matcher tez, ammo local tanlov global eng yaxshi ketma-ketlikni bermasligi mumkin. Table-generated selector target descriptiondan avtomatik matcher yaratadi; global instruction selection ILP yoki graph usullaridan foydalanishi mumkin, lekin compile time qimmatroq. JIT compiler tezlik va code quality o‘rtasida boshqa muvozanat tanlaydi.
Backend sinovlari
Testlar boundary immediate, addressing mode, signed/unsigned comparison, vector type va atomic operationlarni qamraydi. Generated code emulator yoki target hardware’da IR reference bilan solishtiriladi. Disassembler pattern tanlovini, performance counter esa haqiqiy latency va throughputni ko‘rsatadi; instruction soni yolg‘iz metrika emas.
Instruction Selection 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
SelectionDAG, GlobalISel yoki shunga o‘xshash pipeline IRni targetga yaqin node’larga tushiradi. Chain yoki token edge memory side effect tartibini, glue edge esa flags kabi ajralmas natijalarni bog‘laydi. Pattern predicate target feature, operand type va immediate qiymatini tekshiradi; masalan instruction faqat ma’lum ISA extension yoqilganda tanlanadi. Fallback pattern bo‘lmasa compiler “cannot select” ichki xatosiga duch keladi, shu sabab har legal IR operation uchun coverage testi zarur. Post-selection pseudo-instruction keyin register va frame ma’lumoti paydo bo‘lganda expand qilinishi mumkin.
Instruction selector logi har IR node uchun mos kelgan candidate patternlar va tanlangan costni debug rejimida chiqaradi. Target descriptiondagi pattern priority cost teng bo‘lganda deterministik tie-break beradi. Machine verifier operand register classi, immediate constraint va memory operand metadata’ni tekshiradi; assemblerning qabul qilishi semantik to‘g‘rilik uchun yetarli emas.
Bog‘liq tushunchalar
compiler backend, machine instruction, tree covering, legalization, register allocation, code generation