| Ця стаття містить перелік посилань, але походження тверджень у ній залишається незрозумілим через практично повну відсутність внутрішньотекстових джерел-виносок. |
Усунення спільних підвиразів (англ. 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.