Code Generation

Global ma'lumotlardan foydalanish: rang berishni ro'yxatdan o'tkazish

• Kichik dasturda registrlardan optimal foydalanish: barcha o'zgaruvchilarni registrlarda saqlash
• ishlash muddatini bilish kerak (dasturdagi ko'rsatmalar to'plami)
• Ikki o'zgaruvchiga bir xil registr tayinlanishi mumkin emas, agar ularning ishlash muddati bir-biriga to'g'ri kelsa
• interferentsiya grafigiga tarjima qilinadi :
• Har bir o'zgaruvchi grafikdagi tugundir
• Tegishli o'zgaruvchilarning ishlash muddati bir-biriga to'g'ri kelsa, ikkita tugun o'rtasida chekka mavjud
• grafikni bo'yashga teng

Grafik rang berish

• Grafik va N rang to‘plamini hisobga olgan holda, har bir cho‘qqiga rang belgilang, shunda chekka bilan bog‘langan ikkita cho‘qqi turli ranglarga ega bo‘lsin.
• Muammo NP-to'liq
• Tez evristik algoritm (Chaitin) odatda chiziqli bo'ladi:
• Qo'shnilari N -1 dan kam bo'lgan har qanday tugun rangli bo'lib, grafikdan o'chirilishi mumkin. Eng kam sonli qo'shnilar bilan tugun bilan boshlang.
• Grafik bo'sh bo'lguncha takrorlang, keyin ranglarni teskari tartibda belgilang
• Agar biron bir nuqtada N -1 qo'shnidan ko'p tugun bo'lsa, registrni (to'kilmasin) bo'shatish kerak. Keyin tugunni olib tashlash va davom ettirish mumkin.

Misol

• FABFA
• DECDEC
• Olib tashlash tartibi: B, C, A, E, F, D
• 3 ta rang mavjudligini taxmin qiling : ranglarni allaqachon rangli tugunlar bilan chegaralangan teskari tartibda tayinlang.
• D (cheklovsiz) F (D) E (D) A (F, E) C (D, A ) B (A, C)

To'kish uchun yaxshiroq yondashuv

• Ikkinchi o'tishda kerakli ranglar sonini hisoblang: R
• R - N o'zgaruvchilarni xotiraga joylashtirish kerak
• Eng kam foydalanish soniga ega to'kilmasin o'zgaruvchilari.
• Foydalanishni taxmin qilish uchun halqa tuzilishidan foydalaning.