"Statik" döngülerinin optimizasyonu

Question

Eğlence için derlenmiş bir dil yazıyorum ve son zamanlarda derleyicimi çok güçlü yapmak için bir tekme atışı yaptım. Bazı şeyleri optimize etmenin çeşitli yollarını buldum, örneğin, 2 + 2 her zaman 4, yani bu matematiği derleme zamanında yapabiliriz, eğer (yanlış) {...} tamamen kaldırılabilirse, vs. Döngüleri aldım. Bazı araştırmalardan sonra, yapmaya çalıştığım şeyin tam olarak döngüsel değil, ama yine de bir optimizasyon tekniği olduğunu düşünüyorum. Açıklamama izin ver.

Aşağıdaki kodu kullanın.

String s = ""; 
for(int i = 0; i < 5; i++){ 
    s += "x"; 
} 
output(s); 

bir insan gibi, ben burada oturup bu zamanın% 100 Yani

output("xxxxx"); 

eşdeğer olacak olduğunu söyleyebilirim, başka bir deyişle, bu döngü "derlenebilir "tamamen". Döngüsel bir döngü değil, "tam statik" dediğim şey, yani, segmentin davranışını değiştirecek hiçbir girdi yok. Benim fikrim, tamamen statik olan herhangi bir şeyin tek bir değere çözülebilmesi, girdiye dayanan veya koşullu çıkışı sağlayan herhangi bir şey daha fazla optimize edilememesidir. Dolayısıyla, makinenin bakış açısından, neye dikkat etmem gerekiyor? Bir döngüyü "tam statik" yapan nedir?

Nasıl kategorize edileceğini anlatabilmem için üç tür döngüden söz ediyorum. Her çalışmadan sonra, her girişten sonra, girişler ne olursa olsun, ASLA OLMAYACAĞIZ döngüler ve bir şekilde ya da diğerini anlayamadığım döngülerle sonuçlanacak döngüler. Bunu çözemediğim durumda (koşullu olarak dinamik girişlere göre kaç kez çalışacağını değiştirir), optimizasyon konusunda endişelenmiyorum. Sonsuz olan döngüler, programlayıcı tarafından özel olarak bastırılmadıkça bir derleme hatası/uyarısı olacaktır ve her defasında aynı olan döngüler, doğrudan doğruya makineyi uygun duruma getirerek döngü yapmadan atlamalıdır.

En iyi duruma getirilmesi gereken ana durum, içerdeki tüm işlevler de statik olduğunda statik döngü yinelemeleridir. Döngünün dinamik bileşenlere sahip olup olmadığını belirleme yeteri kadar kolaydır ve dinamik değilse statik olması gerekir. Anlayamadığım şey, sonsuzluk olup olmayacağını tespit etmektir. Bunun hakkında herhangi bir fikri var mı? Bunun durma probleminin bir alt kümesi olduğunu biliyorum, ama çözülebilir olduğunu düşünüyorum; Durma problemi, bazı program alt kümeleri için, sonsuza kadar koşabileceğini söyleyememeniz nedeniyle bir problemdir, olmayabilir, ancak bu vakaları düşünmek istemiyorum, sadece vakaları düşünmek istiyorum nerede duracak, ya da durmayacak, ama önce üç devlet arasında ayrım yapmak zorundayım.

Answer 1

Bu, genel olarak değil, çeşitli sınıflar için tanımlanabilen bir tür sembolik çözücüye benziyor.

Gereksinimleri biraz kısıtlayalım: hiçbir döngü taşması yok, sadece döngüler için (bazen devam etmenin kullanılması hariç, döngü için tam olarak dönüştürülebiliyorken), herhangi bir mola, for döngüsündeki kontrol değişkeninde herhangi bir değişiklik yok .

for (var i = S; E(i); i = U(i)) ... E (i) ve U (i) sembolik olarak manipüle edilebilir ifadelerdir

.

U(i) = i + CONSTANT: çok sayıda nispeten kolaydır sınıfı vardır n inci döngüsü i değeri S + n * CONSTANT

U(i) = i * CONSTANT olup: n inci döngü i değeri S * CONSTANT^n

U(i) = i/CONSTANT olup: n inci döngüsü i'un değeri S * CONSTANT^-n

U(i) = (i + CONSTANT) % M: n inci döngü i değeri (S + n * CONSTANT) % M

ve bazı diğer oldukça kolaydır kombinasyonları (ve bazı çok zor olanlar)

döngü E(i(n)) yanlış olduğu n için arama sona olup olmadığının belirlenmesi. Bu, bir çok durum için sembolik bir manipülasyonla yapılabilir, ancak çözücünün yapılmasında çok fazla iş vardır.

E.g.

• for(int i = 0; i < 5; i++),
• i(n) = 0 + n * 1 = n
, E(i(n)) => not(n < 5) =>
• n >= 5 =>, n = 5

---

• for(int i = 0; i < 5; i--) durur
• i(n) = 0 + n * -1 = -n, E(i(n)) =>not(-n < 5) =>-n >= 5 =>
• n < -5 - n negatif olmayan tam sayı olduğu için bu asla doğrudur - hiç durur

  ---

  • for(int i = 0; i < 5; i = (i + 1) % 3)
  ,
• E(i(n)) = >not(n % 3 < 5) =>n % 3 >= 5 => bu asla doğru değil => asla durmaz

---

• for(int i = 10; i + 10 < 500; i = i + 2 * i) = n bütün
• for(int i = 10; i < 480; i = 3 * i),
• i(n) = 10 * 3^n,
• E(i(n)) =>not(10 * 3^n < 480) =>10 * 3^n >= 480 =>3^n >= 48 =>n >= log3(48) =>n >= 3.5... =>
• olup> yana =>n = 4
için duracaktır Sembolik manipülasyon içindiğer durumlar için

onlar zaten çözebilir olanları dönüştürülmüş olsun eğer iyi olurdu ...

Birçok hileler Lisp döneminden gelen ve çok zor değildir. Tanımlananlar (veya varyantlar) en yaygın uygulama türleri olmasına rağmen, senaryoları çözmek için çok daha zor ve/veya imkansızlıklar vardır.