Ця стаття містить перелік посилань але походження тверджень у ній залишається незрозумілим через практично повну відсутн

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