Kod Üretimi ve Optimizasyonu
Kod üretimi ve optimizasyonu, ara temsilleri verimli hedef koda dönüştürerek, programların anlamlarını korurken daha hızlı çalışmasını veya daha az kaynak kullanmasını sağlamaktadır.
Tanım
Kod üretimi, ara temsilden hedef (makine veya bayt kodu) komutlarının oluşturulmasıdır ve optimizasyon, bir programın hızını, boyutunu veya kaynak kullanımını iyileştiren, anlamı koruyan dönüşümlerin uygulanmasıdır.
Kapsam
Bu konu, derleyici arka ucu ve orta ucunu kapsamaktadır: statik tek atama (SSA) formu gibi ara temsiller, veri akışı analizi, klasik optimizasyonlar (sabit yayılımı, ortak alt ifade eleme, döngü optimizasyonları), komut seçimi, komut zamanlaması ve yazmaç tahsisi. Dönüşümlerin program semantiğini korurken performansı nasıl iyileştirdiğini ele almaktadır.
Temel sorular
- Program dönüşümleri, davranışı değiştirmeden performansı nasıl iyileştirebilir?
- Hangi ara temsiller optimizasyon analizini verimli hale getirir?
- Sınırlı makine yazmaçları, çok sayıda program değerine nasıl tahsis edilir?
- Agresif optimizasyonda doğruluk ve performans arasında nasıl bir denge kurulur?
Temel kuramlar
- Statik tek atama formu
- Cytron ve arkadaşları, programları SSA formuna dönüştürmek için verimli bir algoritma sunmuştur; bu formda her değişken yalnızca bir kez atanır, bu da birçok veri akışı tabanlı optimizasyonu önemli ölçüde basitleştirmektedir.
- Çizge renklendirme ile yazmaç tahsisi
- Chaitin, yazmaç tahsisini bir girişim çizgesinin renklendirilmesi olarak modellemiş ve program değerlerini sınırlı bir makine yazmaçları kümesine atamak için temel bir yaklaşım sunmuştur.
- Veri akışı tabanlı optimizasyon
- Muchnick ve Dragon Kitabı, veri akışı analizini klasik optimizasyonların altında yatan çerçeve olarak formüle etmekte, güvenli dönüşümleri haklı çıkarmak için gereken program özelliklerini hesaplamaktadır.
Klinik önem
Kod üretimini optimize etmek, programların işlemcileri ve belleği ne kadar verimli kullandığını belirlemekte olup, enerji kullanımı ve büyük ölçekli maliyet üzerinde geniş bir etkiye sahiptir. SSA formu ve çizge renklendirme tabanlı yazmaç tahsisi, üretim derleyicileri ve anında (just-in-time) sistemler için merkezi önemini korumaktadır.
Tarihçe
Optimizasyon, Fortran derleyicisi ile başlamış ve 1970'lerde Allen ve Cocke'un veri akışı analizi ile olgunlaşmıştır. Chaitin'in 1981-82 tarihli çizge renklendirme tabanlı yazmaç tahsisi ve Cytron ve arkadaşlarının 1991 tarihli verimli SSA yapısı, modern derleyicilerin temel taşları haline gelmiş, günümüzdeki araç zincirlerinde kullanılan gelişmiş optimizasyon boru hatlarını mümkün kılmıştır.
Tartışmalar
- Optimizasyon agresifliği ile doğruluk ve öngörülebilirlik
- Derleyici tasarımcıları, tanımsız davranışı istismar etmenin ve yeniden sıralamanın hız sağlayabilmesine rağmen şaşırtıcı veya güvensiz sonuçlar doğurabileceği için ne kadar agresif optimize edileceği konusunda tartışmaktadır; bu durum doğrulanmış ve öngörülebilir optimizasyona olan ilgiyi artırmaktadır.
Öne çıkan isimler
- Frances Allen
- Gregory Chaitin
- Ron Cytron
- Steven Muchnick
- Alfred Aho
İlgili konular
Temel eserler
- cytron1991
- chaitin1982
- muchnick1997
- aho2006
Sıkça sorulan sorular
- SSA formu nedir?
- Statik tek atama formu, her değişkenin tam olarak bir kez atandığı ve kullanımların tek bir tanıma bağlandığı bir ara temsildir; bu durum birçok derleyici optimizasyonunu basitleştirmekte ve güçlendirmektedir.
- Yazmaç tahsisi neden zordur?
- Programlar genellikle makine yazmaçlarından çok daha fazla değer kullanır, bu nedenle derleyici hangi değerlerin yazmaçları paylaşacağına ve hangilerinin belleğe aktarılacağına karar vermelidir; temel sorun, genel olarak hesaplama açısından zor olan çizge renklendirmeye eşdeğerdir.