W jaki sposób kompilator może zastosować funkcję eliminacji funkcji nieczytelnych?

Question

Często podczas pisania kodu, wielokrotnie używam wartości z konkretnego wywołania funkcji. Zdałem sobie sprawę, że oczywistą optymalizacją byłoby uchwycenie tych wielokrotnie używanych wartości w zmiennych. to (pseudo kod):

function add1(foo){ foo + 1; } 
... 
do_something(foo(1)); 
do_something_else(foo(1)); 

Staje:

function add1(foo){ foo + 1; } 
... 
bar = foo(1); 
do_something(bar); 
do_something_else(bar); 

Jednak robi to wyraźnie czyni kod mniej czytelny w moim doświadczeniu. Zakładam, że kompilatory nie mogą przeprowadzić tego rodzaju optymalizacji, jeśli nasz wybrany język pozwala funkcjom mieć efekty uboczne.

Ostatnio zajrzałem w to i jeśli dobrze rozumiem, ta optymalizacja jest/może być zrobiona dla języków, w których funkcje muszą być czyste. Nie zaskakuje mnie to, ale podobno można to zrobić także w przypadku nieczystych funkcji. Za pomocą kilku szybkich wyszukiwań Google Znalazłem te fragmenty: GCC 4.7 Fortran improvement

Podczas wykonywania Czołowy optymalizacji opcja -faggressive-funkcja-eliminacja umożliwia usunięcie duplikatu wywołań funkcji nawet dla funkcji nieczystych.

Compiler Optimization (Wikipedia)

Na przykład, w niektórych funkcjach języków nie mogą mieć skutki uboczne. Dlatego jeśli program wykonuje kilka wywołań tej samej funkcji z tymi samymi argumentami, kompilator może od razu wywnioskować, że wynik tej funkcji musi zostać obliczony tylko raz. W językach, w których funkcje mogą mieć efekty uboczne, możliwa jest inna strategia. Optymalizator może określić, która funkcja nie ma skutków ubocznych i ograniczyć takie optymalizacje do funkcji wolnych od skutków ubocznych. Ta optymalizacja jest możliwa tylko wtedy, gdy optymalizator ma dostęp do wywoływanej funkcji.

Z mojego rozumowania oznacza to, że optymalizator może określić, kiedy dana funkcja jest lub nie jest czysta, i wykonać tę optymalizację, gdy funkcja jest. Mówię to, ponieważ jeśli funkcja zawsze wytwarza to samo wyjście, gdy otrzyma to samo wejście i jest wolna od skutków ubocznych, spełni oba warunki, aby zostać uznanym za czysty.

Te dwa fragmenty podnoszą dwa pytania do mnie.

1. W jaki sposób kompilator może bezpiecznie wykonać tę optymalizację, jeśli funkcja nie jest czysta? (jak w funkcji eliminacji fagresywnej)
2. W jaki sposób kompilator może ustalić, czy dana funkcja jest czysta czy nie? (Jak w strategii sugerowane w artykule Wikipedia)

i wreszcie:

• Czy ten rodzaj optymalizacji być stosowany w dowolnym języku, lub tylko wtedy, gdy spełnione są określone warunki?
• Czy ta optymalizacja jest warta zachodu, nawet w przypadku bardzo prostych funkcji?
• Ile kosztu wiąże się ze składowaniem i pobieraniem wartości ze stosu?

Przepraszam, jeśli są to głupie lub nielogiczne pytania. To tylko niektóre rzeczy, które mnie ostatnio interesowały. :)

Answer 1

Nota prawna: Nie jestem facetem kompilatora/optymalizatora, mam tylko tendencję do podglądania wygenerowanego kodu i lubię czytać o tych rzeczach - więc to nie jest autorytatywne. Szybkie wyszukiwanie nie przyniosło zbyt wielu efektów w postaci eliminacji funkcji fagresywnych, więc może zrobić dodatkową magię, której tu nie wyjaśniono.

---

optymalizator może

• próba inline wywołanie funkcji (z generacji kodu czasu związek ten działa nawet w poprzek jednostek kompilacji)
• wykonać eliminacja wspólnych podwyrażeń, oraz, ewentualnie, efektem ubocznym zmiana kolejności.

Modyfikacja przykład nieco, i robi to w C++:

extern volatile int RW_A = 0; // see note below 

int foo(int a) { return a * a; } 
void bar(int x) { RW_A = x; } 

int _tmain(int argc, _TCHAR* argv[]) 
{ 
    bar(foo(2)); 
    bar(foo(2)); 
} 

postanawia (Pseudokod)

<register> = 4; 
RW_A = register; 
RW_A = register; 

(Uwaga: odczyt i zapis do zmiennej lotny jest "obserwowalny efekt uboczny", że optymalizator musi zachować w tej samej kolejności, co kod.)

---

Modyfikowanie przykład dla foo mieć efekt uboczny:

extern volatile int RW_A = 0; 
extern volatile int RW_B = 0; 
int accu = 1; 

int foo(int a) { accu *= 2; return a * a; } 
void bar(int x) { RW_A = x; } 

int _tmain(int argc, _TCHAR* argv[]) 
{ 
    bar(foo(2)); 
    bar(foo(2)); 

    RW_B = accu; 
    return 0; 
} 

generuje następujące Pseudokod:

registerA = accu; 
registerA += registerA; 
accu = registerA; 

registerA += registerA; 
registerC = 4; 
accu = registerA; 

RW_A = registerC; 
RW_A = registerC; 

RW_B = registerA; 

Obserwujemy, że likwidacja wspólnego podwyrażenie jest jeszcze zrobione, i oddzielone od skutków ubocznych. Inlineing i zmiana kolejności pozwala oddzielić efekty uboczne od "czystej" części.

Należy zauważyć, że kompilator czyta i chętnie zapisuje z powrotem do accu, które nie byłoby konieczne. Nie jestem pewien na tej racji.

---

Podsumowując:

Kompilator nie trzeba przetestować pod kątem czystości. Może identyfikować działania niepożądane, które należy zachować, a następnie przekształcać resztę w jej upodobania.

Takie optymalizacje są opłacalne, nawet dla funkcji trywialne, ponieważ m.in.

• procesora i pamięci są udostępnionych zasobów, czego użyć można odebrać od kogoś innego
• życia baterii
• Drobne optymalizacje mogą być bramkami dla większych.

Narzut związany z dostępem do pamięci stosu wynosi zwykle ~ 1 cykl, ponieważ górna część stosu zwykle znajduje się w pamięci podręcznej poziomu 1 już.Zauważ, że zwykle powinno być pogrubione: może być "nawet lepsze", ponieważ odczyt/zapis może być zoptymalizowany z dala, lub może być gorszy, ponieważ zwiększone ciśnienie na pamięci podręcznej L1 opróżnia inne ważne dane z powrotem do L2.

Gdzie jest limit?

Teoretycznie, czas kompilacji. W praktyce przewidywalność i poprawność optymalizatora są dodatkowymi kompromisami.

---

Wszystkie testy z VC2008, domyślne ustawienia optymalizacji dla wersji "Release".