Ця стаття містить , але походження тверджень у ній через практично повну відсутність . |
Усунення спільних підвиразів (англ. 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.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Cya stattya mistit perelik posilan ale pohodzhennya tverdzhen u nij zalishayetsya nezrozumilim cherez praktichno povnu vidsutnist vnutrishnotekstovih dzherel vinosok Bud laska dopomozhit polipshiti cyu stattyu peretvorivshi dzherela z pereliku posilan na dzherela vinoski u samomu teksti statti Usunennya spilnih pidviraziv angl common subexpression elimination CSE ce optimizaciya kompilyatora za yakoyi shukayutsya primirniki totozhnih viraziv tobto takih sho mayut odnakove znachennya i prijmayetsya rishennya chi varto zaminiti yih odniyeyu zminnoyu sho mistit obchislene znachennya PrikladTakij kod a b c g d b c d mozhe buti docilno pererobiti tak tmp b c a tmp g d tmp d Docilno oznachaye sho otrimanij novij kod bude vikonuvatis shvidshe OsnoviMozhlivist USP bazuyetsya na doslidzhenni dostupnih viraziv tobto takih sho ne potrebuyut pereobchislennya Viraz b c dostupnij u tochci p v programi yaksho kozhnij shlyah z pochatkovogo vuzla do p obchislyuye b c do dosyagnennya p i nemaye prisvoyen b abo c pislya obchislennya j do p Doslidzhennya vartist vigoda vikonuvane optimizatorom obchislit chi vartist zberigannya tmp mensha za vartist mnozhennya na praktici inshi chinniki taki yak vmist registriv takozh vazhlivi Rozrobniki kompilyatoriv rozriznyayut dva vidi USP usunennya lokalnih spilnih pidviraziv obroblyaye odin bazovij blok i tomu legko realizuyetsya usunennya globalnih spilnih pidviraziv opracovuye proceduru cilkom pokladayetsya na yaki virazi dostupni v cij tochci proceduri VigodiOptimizaciya USP shiroko vikoristovuyetsya bo vigodi vid neyi dosit znachni V prostih virazah na zrazok prikladu vishe programist mozhe pid chas napisannya kodu vruchnu usunuti podvijni virazi Najkrashe dzherelo USP ce promizhni kodovi poslidovnosti stvoreni kompilyatorom taki yak rozrahunki indeksaciyi masiviv de rozrobnik ne mozhe vtrutitis vruchnu V deyakih vipadkah cherez osoblivosti movi mozhe utvoryuvatisya bagato povtoryuvanih viraziv Napriklad makrosi C de rozgortannya makrosiv mozhe mati naslidkom bagato spilnih pidviraziv ne vidimih v pochatkovomu kodi Kompilyatori mayut buti rozvazhlivimi shodo kilkosti timchasovih ob yektiv dlya utrimannya znachen Nadmirna kilkist timchasovih znachen sprichinyaye tisk na registri z mozhlivim nastupnim prolivannyam registriv u pam yat sho prizvede do zatrimki bilshoyi nizh potribna dlya prostogo pereobchislennya arifmetichnogo rezultatu DzherelaSteven 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