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

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