Kayıtların tahsisi
Bir derleyicide , kayıtların tahsis edilmesi , kod üretiminde önemli bir adımdır . Bu neyi akıllıca seçim hedefliyor kayıt ait CPU lar kaydedilecektir' değişkenleri derlemek programın yürütülmesi sırasında.
Kayıtlar, genellikle bir makine kelimesi içerebilen, işlemcinin dahili hafızalarıdır. Kayıtlarda saklanan değerler üzerindeki işlemler, mümkün olan tek şey bunlar olmadığında, RAM'deki değerlerden daha hızlıdır . Ancak bir işlemcinin nadiren birkaç düzineden fazla kaydı vardır, bir programdaki tüm değişkenler için çok azdır. Bu nedenle, uygulamanın her aşamasında kayıtlarda bulunması gereken değişkenleri uygun şekilde seçmek çok önemlidir. Bu, derlemenin ilk aşamalarında zor olduğundan, sınırsız sayıda yazmacımız varmış gibi davranarak başlıyoruz, sonra bu sanal yazmaçlara gerçek yazmaçlar veya bellek konumları atıyoruz.
Tahsisatı grafik renklendirmeyle kaydedin
Klasik yazmacı ayırma yöntemlerinden biri için sorun azaltmaktır boyama arasında girişim grafik değişkenlerinin. Bu grafiğin köşeleri programın değişkenleridir ve karşılık gelen değişkenler karışırsa iki köşe bir kenarla bağlanır.
Biri tanımlanırken diğeri aktifken (yani yürütmenin geri kalanında kullanılabilecek) iki değişkenin karıştığını söylüyoruz. Müdahale eden iki değişken aynı kayda yerleştirilemez - tek bir teknik nitelikle: bazı işlemcilerde kayıtlar eşdeğer değildir. Bu nedenle , hepsinin birbirine karıştığını ve bir değişkenin kendisine yasak olan kayıtlara müdahale ettiğini kabul ederek , müdahale ilişkisini kaydettirmek için genişletiyoruz . Böylece, bir can not renk girişim grafiğinde komşu olan iki değişken aynı kayıt ile. Kayıtları değişkenlere atamak , girişim grafiğini renklerle renklendirmekle eşdeğerdir .
-Coloration sorunu olan NP-tam (için ) ve bir grafik için. Herhangi bir grafiğe gelince, girişim grafiği olan bir program oluşturmak mümkündür , kayıt tahsis problemi de NP-tamdır. Ayrıca genellikle iyi pratik sonuçlar sağlayan bir buluşsal yöntem kullanırız . Renklendirmesi kolay olan köşeleri grafikten çıkarmaktan ibarettir: grafiğe, kesinlikle daha küçük olan bir derece köşesi için bakarız . Komşuları daha çok renk kullanacağı için bu zirveyi renklendirebileceğimizden eminiz . Bu yüzden onu grafikten çıkarıyoruz ve bir kenara bırakıyoruz. Basitleştirilmiş grafiği yinelemeli olarak renklendirmeyi başarırsak, onu yeniden yerleştirebilir ve renklendirebiliriz.
Tüm köşelerin en azından derecesi varsa , birkaç strateji mümkündür:
- Renklendirmeye devam edebilir ve her aşamada minimum derecedeki bir tepe noktasını kaldırabiliriz, komşularından ikisinin aynı renge sahip olmasını umarak yükselişte renklendirmeyi başarabiliriz. Kurtarma sırasında, karşılaşılan her bir tepe noktasına, onu aşması anlamına gelse bile ilk mevcut renk atanır , ardından her bir rengin değişkenlerini bellekte saklamanın maliyeti, her birine gerçek bir kayıt veya bir bellek yuvası atamak için değerlendirilir. Her köşe için komşularının komşularınınkinden bir renk seçmeye çalışarak biraz daha iyisini yapmak mümkündür;
- diğer bir yöntem ise, aksine, maksimum derecede bir tepe noktası seçmekten ibarettir, ümidiyle, kaldırılması grafiği önemli ölçüde basitleştirecektir. Depolama maliyeti hakkında bilgi mevcutsa, istifleme maliyetinin dereceye oranı daha iyi bir göstergedir. Gerçek kayıt defteri ayırma sistemleri, bu iki yöntemi birleştirebilen biraz daha karmaşık buluşsal yöntemler kullanır. Son olarak, bir değeri yeniden hesaplamanın (örneğin, işlenenler yazmaçlarda bulunuyorsa) onu tekrar okumak için kaydetmekten daha ucuz olduğuna dikkat edin.