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

Усунення спільних підвиразів (англ. 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.