Усунення загальних підвиразів

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Усунення загальних підвиразів (англ. common subexpression elimination, CSE) це оптимізація компілятора, що шукає примірники тотожних виразів (тобто таких, що обчислюються в однакове значення), і розмірковує чи варто замінити їх на одну зміну, що містить обчислене значення.

Приклад[ред.ред. код]

В такому коді:

a = b * c + g;
d = b * c * d;

може бути варто переробити його так:

tmp = b * c;
a = tmp + g;
d = tmp * d;

«варто» означає, що отриманий новий код буде виконуватись швидше.

Основи[ред.ред. код]

Можливість УЗП базується на дослідженні доступних виразів, тобто таких, що не потребують переобчислення (аналіз потоку даних). Вираз b*c доступний у точці p в програмі, якщо:

  • кожний шлях з початкового вузла до p обчислює b*c до досягнення p,
  • і немає присвоєнь b або c після обчислення й до p.

Дослідження вартість-вигода виконуване оптимізатором обчислить чи вартість зберігання tmp менша за вартість множення; на практиці інші чинники такі як яке значення міститься в якому регістрі також важливі.

Розробники компіляторів розрізняють два види УЗП:

  • усунення локальних загальних підвиразів обробляє один базовий блок і тому легка до здійснення.
  • усунення глобальних загальних підвиразів опрацьовує процедуру цілком, покладається на аналіз потоку даних, які вирази доступні в цій точці процедури.

Вигоди[ред.ред. код]

Оптимізація УЗП загально використовна, бо вигоди від неї досить значні.

В простих виразах на кшталт прикладу вгорі, програміст може під час написання коду вручну усунути подвійні вирази. Найкраще джерело УЗП це проміжний послідовності коду створені компілятором, такі як розрахунки індексації масивів, де розробник не може втрутитись вручну. В деяких випадках мова може утворювати багато повторюваних виразів. Наприклад, C макроси, де розгортання макросів може мати наслідком багато загальних підвиразів не видимих в початковому коді.

Компілятори мають бути розважливими щодо кількості тимчасових об'єктів для утримання значень. Надмірна кількість тимчасових значень спричиняє тиск на реєстри з можливим наступним проливанням реєстрів у пам'ять, що призведе до затримки більшої ніж потрібна для переобчислення арифметичного результату за потреби.


Джерела[ред.ред. код]

  • Steven S. Muchnick, Advanced Compiler Design and Implementation (Morgan Kaufmann, 1997) pp. 378-396
  • John Cocke. "Global Common Subexpression Elimination." Proceedings of a Symposium on Compiler Construction, ACM SIGPLAN Notices 5(7), July 1970, pages 850-856.
  • Briggs, Preston, Cooper, Keith D., and Simpson, L. Taylor. "Value Numbering." Software-Practice and Experience, 27(6), June 1997, pages 701-724.