Stałe składanie - Constant folding

Ciągłe zwijanie i ciągła propagacja to powiązane optymalizacje kompilatora używane przez wiele współczesnych kompilatorów . Zaawansowana forma ciągłej propagacji, znana jako rzadka warunkowa propagacja stała, może dokładniej propagować stałe i jednocześnie usuwać martwy kod .

Stałe składanie

Stałe zwijanie to proces rozpoznawania i oceniania wyrażeń stałych w czasie kompilacji, a nie obliczania ich w czasie wykonywania. Terminy w wyrażeniach stałych są zwykle prostymi literałami, takimi jak literał liczb całkowitych 2 , ale mogą to być również zmienne, których wartości są znane w czasie kompilacji. Rozważ stwierdzenie: 

  i = 320 * 200 * 32;

Większość kompilatorów w rzeczywistości nie wygenerowałaby dwóch instrukcji mnożenia i magazynu dla tej instrukcji. Zamiast tego identyfikują konstrukcje takie jak te i zastępują obliczone wartości w czasie kompilacji (w tym przypadku 2,048,000 ).

Stałe składanie może wykorzystywać tożsamości arytmetyczne. Jeśli x jest numeryczny, wartość 0 * x jest równa zero, nawet jeśli kompilator nie zna wartości x (zwróć uwagę, że nie jest to poprawne dla elementów zmiennoprzecinkowych IEEE, ponieważ x może to być Infinity lub NotANumber . Jednak niektóre języki, które sprzyjają wydajności, takie jak GLSL, pozwalają na to dla stałych , które czasami mogą powodować błędy).

Ciągłe pasowanie może dotyczyć nie tylko liczb. Konkatenacja literałów ciągów i ciągów stałych może być składana na stałe. Kod taki, jaki "abc" + "def" można zastąpić "abcdef" .

Ciągłe składanie i kompilacja krzyżowa

Przy implementacji kompilatora krzyżowego należy zadbać o to, aby zachowanie operacji arytmetycznych na architekturze hosta było zgodne z zachowaniem na architekturze docelowej, ponieważ w przeciwnym razie włączenie ciągłego zwijania zmieni zachowanie programu. Ma to szczególne znaczenie w przypadku operacji zmiennoprzecinkowych , których dokładna realizacja może się znacznie różnić.

Ciągłe rozmnażanie

Ciągłe propagowanie jest procesem zastępowania wartości znanych stałych w wyrażeniach w czasie kompilacji. Takie stałe obejmują te zdefiniowane powyżej, a także funkcje wewnętrzne stosowane do wartości stałych. Rozważmy następujący pseudokod: 

  int x = 14;
  int y = 7 - x / 2;
  return y * (28 / x + 2);

Propagowanie x plonów: 

  int x = 14;
  int y = 7 - 14 / 2;
  return y * (28 / 14 + 2);

Kontynuacja propagacji daje następujące wyniki (które prawdopodobnie byłyby dalej optymalizowane przez eliminację martwego kodu zarówno x, jak i y). 

  int x = 14;
  int y = 0;
  return 0;

Ciągłe propagowanie jest realizowane w kompilatorach z wykorzystaniem wyników analizy definicji . Jeśli definicje wszystkich osiągających zmiennych są tym samym przypisaniem, które przypisuje tę samą stałą do zmiennej, to zmienna ma stałą wartość i może zostać zastąpiona stałą.

Stałe propagowanie może również powodować uproszczenie gałęzi warunkowych do jednej lub więcej instrukcji bezwarunkowych, gdy wyrażenie warunkowe może zostać ocenione jako prawda lub fałsz w czasie kompilacji, aby określić jedyny możliwy wynik.

Optymalizacje w akcji

Stałe zwijanie i propagacja są zwykle używane razem, aby osiągnąć wiele uproszczeń i redukcji, poprzez ich iteracyjne przeplatanie, aż nie będzie już żadnych zmian. Rozważmy ten niezoptymalizowany pseudokod, który zwraca liczbę losową : 

  int a = 30;
  int b = 9 - (a / 5);
  int c;

  c = b * 4;
  if (c > 10) {
     c = c - 10;
  }
  return c * (60 / a);

Jednokrotne zastosowanie stałego rozmnażania, a następnie ciągłe zwijanie, daje: 

  int a = 30;
  int b = 3;
  int c;

  c = b * 4;
  if (c > 10) {
     c = c - 10;
  }
  return c * 2;

Dwukrotne powtórzenie obu kroków daje: 

  int a = 30;
  int b = 3;
  int c;

  c = 12;
  if (true) {
     c = 2;
  }
  return c * 2;

Ponieważ a i b zostały uproszczone do stałych, a ich wartości są zastępowane wszędzie tam, gdzie wystąpiły, kompilator stosuje teraz eliminację martwego kodu, aby je odrzucić, jeszcze bardziej redukując kod: 

  int c;
  c = 12;

  if (true) {
     c = 2;
  }
  return c * 2;

W powyższym kodzie zamiast true tego może być 1 lub dowolna inna konstrukcja logiczna w zależności od frameworka kompilatora. Przy tradycyjnej stałej propagacji uzyskamy tylko tyle optymalizacji. Nie może zmienić struktury programu.

Istnieje inna podobna optymalizacja, zwana rzadką warunkową stałą propagacją , która wybiera odpowiednią gałąź na podstawie if-condition . Kompilator może teraz wykryć, że if instrukcja zawsze zostanie oceniona jako prawda , c można ją wyeliminować, co jeszcze bardziej zmniejszy kod: 

  return 4;

Gdyby ten pseudokod stanowił treść funkcji, kompilator mógłby dodatkowo skorzystać z wiedzy, którą ocenia do stałej liczby całkowitej, 4 aby wyeliminować niepotrzebne wywołania funkcji, co przyniosłoby dalszy wzrost wydajności.

Zobacz też

Bibliografia

Dalsza lektura