Eliminacja wspólnych podwyrażeń

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Eliminacja wspólnych podwyrażeń (ang. common subexpression elimination) - technika optymalizacji stosowana w kompilatorach, polegająca na takim przekształceniu kodu, aby część tych samych obliczeń występujących w kilku wyrażeniach była wykonywana tylko raz, co wymaga wprowadzenia dodatkowej, pomocniczej zmiennej. Takie przekształcenie wykonuje się tylko wtedy, gdy rzeczywiście jest to opłacalne, tzn. gdy koszt wprowadzenia nowej zmiennej nie będzie przewyższał kosztu obliczania podwyrażenia.

Np. w poniższym fragmencie programu:

a = x * y + z;
b = x * g * y;
c = x * y / z;

powtarza się mnożenie x * y. Kompilator może wygenerować kod równoważny:

M = x * y;          { wspólne podwyrażenie, wynik zapisywany do nowej zmiennej }
a = M + z;
b = g * M;
c = M / z;

W oryginalnym kodzie wykonywano:

  • 4 mnożenia,
  • 3 przypisania,
  • dodawanie i dzielenie,

natomiast po przekształceniu:

  • 2 mnożenia,
  • 4 przypisania.
  • dodawanie i dzielenie.

Zobacz też[edytuj | edytuj kod]