Optymalizacja pętli "statycznych"

Question

Piszę skompilowany język dla zabawy, a ostatnio zrobiłem kopa, aby mój kompilator optymalizacyjny był bardzo solidny. Wymyśliłem kilka sposobów na optymalizację niektórych rzeczy, na przykład 2 + 2 to zawsze 4, więc możemy to zrobić w czasie kompilacji, jeśli (false) {...} można całkowicie usunąć, itp., Ale teraz Dostałem się do pętli. Po pewnych badaniach myślę, że to, co próbuję zrobić, nie polega na rozwijaniu pętli, ale nadal jest to technika optymalizacji. Pozwól mi wyjaśnić.

Wprowadź następujący kod.

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

Jako człowiek, mogę siedzieć tutaj i powiedzieć, że to 100% czasu będzie równoznaczne

output("xxxxx"); 

Więc innymi słowy, ta pętla może być „skompilowany "całkowicie. To nie jest rozwijanie w pętli, ale to, co nazywam "w pełni statyczną", czyli nie ma danych wejściowych, które mogłyby zmienić zachowanie segmentu. Moim pomysłem jest to, że wszystko, co jest w pełni statyczne, może być rozdzielone na jedną wartość, wszystko, co opiera się na danych wejściowych lub oczywiście sprawia, że ​​wynik warunkowy nie może być dalej optymalizowany. Tak więc, z punktu widzenia maszyny, co muszę wziąć pod uwagę? Co powoduje, że pętla jest w pełni statyczna?

Wymyśliłem trzy rodzaje pętli, które muszę wymyślić, jak kategoryzować. Pętle, które zawsze będą kończyły się tym samym stanem maszyny po każdym uruchomieniu, niezależnie od wejść, pętli, KTÓRYCH NIGDY się nie zakończy i pętli, których nie potrafię wymyślić w ten czy inny sposób. W przypadku, gdy nie mogę tego rozgryźć (warunkowo zmienia to ile razy będzie on działał w oparciu o dynamiczne wejścia), nie martwię się o optymalizację. Pętle, które są nieskończone, będą błędem/ostrzeżeniem kompilacji, o ile nie zostaną przez programistę specjalnie zlikwidowane, a pętle, które są takie same za każdym razem, powinny po prostu przejść bezpośrednio do ustawienia maszyny w prawidłowym stanie, bez pętli.

Głównym celem optymalizacji jest wykonywanie pętli statycznych, gdy wszystkie wywołania funkcji są również statyczne. Ustalenie, czy pętla ma komponenty dynamiczne, jest dość łatwe, a jeśli nie jest dynamiczne, to chyba musi być statyczne. Nie potrafię zrozumieć, jak wykryć, czy będzie nieskończona, czy nie. Czy ktoś ma jakieś przemyślenia na ten temat? Wiem, że jest to podzespół problemu zatrzymania, ale czuję, że to rozwiązalne; problem z zatrzymaniem jest problemem z uwagi na fakt, że dla niektórych podzbiorów programów po prostu nie można powiedzieć, że może działać wiecznie, może nie, ale nie chcę brać pod uwagę tych przypadków, po prostu chcę rozważyć przypadki gdzie to zatrzyma się, albo nie zatrzyma się, ale najpierw muszę rozróżnić trzy stany.

Answer 1

Wygląda to na rodzaj symbolicznego rozwiązania, które można zdefiniować dla kilku klas, ale nie na ogół.

Zmodyfikujmy nieco wymagania: brak przepełnienia liczby, tylko dla pętli (czasami można przekształcić w pełną dla pętli, z wyjątkiem użycia kontynuacji itp.), Bez przerw, bez modyfikacji zmiennej sterującej wewnątrz pętli for .

for (var i = S; E(i); i = U(i)) ...

gdzie E (I) i U (I) są wyrażeniami, które można symbolicznie manipulowane.Istnieje kilka klas, które są stosunkowo proste:

U(i) = i + CONSTANT: n -ty cykl wartość i jest S + n * CONSTANT

U(i) = i * CONSTANT: n -ty cykl wartość i jest S * CONSTANT^n

U(i) = i/CONSTANT: n -ty cykl wartość i jest S * CONSTANT^-n

U(i) = (i + CONSTANT) % M: n -ty cykl wartość i jest (S + n * CONSTANT) % M

i kilka innych dość proste kombinacje (i niektóre z nich bardzo trudne)

Ustalenie, czy pętla kończy szuka n gdzie E(i(n)) jest fałszywe. Można to zrobić za pomocą symbolicznej manipulacji dla wielu przypadków, ale jest wiele pracy związanej z tworzeniem solwera.

E.g.

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

---

• for(int i = 0; i < 5; i--),
• i(n) = 0 + n * -1 = -n, E(i(n)) =>not(-n < 5) =>-n >= 5 =>
• n < -5 - od n jest nieujemną liczbą całkowitą to nigdy nie jest prawda - nigdy nie przestaje

---

• for(int i = 0; i < 5; i = (i + 1) % 3),
• E(i(n)) = >not(n % 3 < 5) =>n % 3 >= 5 => to nigdy nie jest prawdziwe => nigdy się nie zatrzymuje

---

• for(int i = 10; i + 10 < 500; i = i + 2 * i) =>
• 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... =>
• od n cały => zatrzyma się na n = 4

dla innych wypadkach byłoby dobrze, gdyby można je dostać przekształcona do tych można już rozwiązać ...

Wiele sztuczek manipulacji symbolicznej pochodzą z epoki Lisp i nie są zbyt trudne. Chociaż te opisane (lub warianty) są najczęściej stosowanymi typami, istnieje wiele trudniejszych i/lub niemożliwych do rozwiązania scenariuszy.