Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

В теорії компіляторів ви даленням ме ртвого ко ду англ dead code elimination DCE називають оптимізацію за якої видаляєть

Видалення мертвого коду

Видалення мертвого коду

В теорії компіляторів ви́даленням ме́ртвого ко́ду (англ. dead code elimination, DCE) називають оптимізацію, за якої видаляється мертвий код. Ме́ртвим ко́дом (або ма́рним ко́дом) називають код, виконання якого не впливає на (вивід) програми, всі результати обчислення такого коду є [en], тобто змінними, значення яких надалі в програмі не використовуються.

Через існування різночитань терміна мертвий код, важливо відзначити, що оптимізація видалення мертвого коду не займається видаленням недосяжного коду. Локалізацією і видаленням недосяжного коду можуть займатися прибиральник або інші оптимізації, наприклад, видалення недосяжного коду.

Видалення непотрібного коду здатне прискорити роботу програми завдяки зменшенню кількості виконуваних у ній операцій і зменшити обсяг програми або [en].

Приклади

Розглянемо такий код мовою Сі:

 int foo(void)  {  int a = 24;  int b;  b = a + 3; /* Марний код */  return a << 2;  }

У цьому прикладі операція додавання b = a + 3 є мертвим кодом, оскільки змінна b не використовується в подальших обчисленнях, а отже є мертвою, починаючи з цієї точки і закінчуючи кінцем процедури. Після видалення цієї інструкції отримаємо:

 int foo(void)  {  int a = 24;  int b; /* Мертва змінна */  return a << 2;  }

Після видалення операції додавання, змінна b стає мертвою у всій процедурі. Оскільки її оголошено локально, то її можна повністю видалити з програми:

 int foo(void)  {  int a = 24;  return a << 2;  }

Попри те що обчислення відбувається всередині функції, його результат записується в змінну, яка перебуває в області видимості тільки цієї функції; якщо врахувати що функція безумовно повертає число 96, її можна спростити оптимізацією так, щоб її тіло складалося тільки з операції return 96. А потім компілятор зможе замінити всі виклики цієї функції значенням, яке вона повертає.

Алгоритми

Класичний алгоритм DCE («Dead») працює на і складається з двох обходів: перший обхід («Mark») позначає (маркує) всі напевне живі операції (операції виходу з процедури, введення-виведення, що змінюють глобальні змінні); другий обхід («Sweep») починається з живих операцій і йде вгору по визначеннях аргументів, позначаючи всі операції на своєму шляху живими, закінчуючи тими операціями, які не мають попередників у SSA-поданні. Максимальна обчислювальна складність такого алгоритму залежить від розміру програми як O(n2).

DCE може не проводити ніякого самостійного аналізу, а просто скористатися результатами [en], але обчислювальна складність такого аналізу становить у гіршому випадку O(n3). Існують специфічні алгоритми, які видаляють порожні вузли в графі потоку керування, об'єднують декілька базових блоків в один тощо, але для такого аналізу потрібен побудований граф потоку керування.

Алгоритм «Dead» вперше опубліковано в статті «Static Single Assignment Form and the Program Dependence Graph» в журналі [en] 1991 року. Алгоритм «Clean», що працює з графом потоку керування розробив і реалізував Роб Шиллер 1992 року.

Застосування

Видалення мертвого коду може в процесі компіляції застосовуватися кілька разів, оскільки мертвий код може не тільки існувати в програмі від початку, але й з'являтися після деяких перетворень коду програми. Наприклад, оптимізації [en] і часто перетворюють інструкції в марний код. Також доводиться видаляти мертвий код, створений іншими перетвореннями в компіляторі. Наприклад, класичний алгоритм оптимізації заміщає трудомісткі операції менш трудомісткими, після чого видалення мертвого коду усуває старі операції і завершує перетворення (без ускладнення алгоритму зниження вартості).

Цікаві факти

  • У листопаді 2010 року Microsoft випустила нову версію Internet Explorer 9 Platform Preview 7, яка за швидкістю інтерпретації JavaScript на бенчмарку SunSpider [ 20 січня 2022 у Wayback Machine.] перевершила всі інші браузери. В офіційному блозі Internet Explorer лідер проєкту, [en], заявив, що одним із нововведень релізу є використання оптимізації видалення мертвого коду, завдяки чому й досягнуто такого результату. Однак незабаром з'ясувалося, що незначні зміни у сирцевому коді бенчмарка викликали істотне падіння продуктивності Internet Explorer 9, чого не відбувалося при тестуванні Google Chrome або Opera. Через це на адресу розробників Internet Explorer посипалися звинувачення в «підгонці» продукту під конкретний бенчмарк.

Див. також

Примітки

  1. Компиляторы — принципы, технологии, инструменты — С. 713, 714.
  2. Engineering a Compiler — С. 544.
  3. Dead code detection and removal. Aivosto. Архів оригіналу за 5 серпня 2012. Процитовано 14 липня 2012. (смешивание понятий мёртвого и недостижимого кодов)
  4. Компиляторы — принципы, технологии, инструменты — С. 669 (недостижимый код), 713 (мёртвый код).
  5. А. Ю. Дроздов, А. М. Степаненков. Управляемые пакеты оптимизаций. В Информационные технологии и вычислительные системы, 2004, № 3 (текст [ 2016-03-04 у Wayback Machine.])
  6. Engineering a Compiler — С. 544—546.
  7. Jan Olaf Blech, Lars Gesellensetter, Sabine Glesner. Formal Verification of Dead Code Elimination in Isabelle/HOL. , сентябрь 2005 (текст).
  8. Advanced Compiler Design and Implementation — С. 443.
  9. Engineering a Compiler — С. 547—550.
  10. Ron Cytron, Jeanne Ferrante, Barry Rosen, and Ken Zadeck. Efficiently Computing Static Single Assignment Form and the Program Dependence Graph. [en] 13(4), 1991 (текст).
  11. Engineering a Compiler — С. 593.
  12. Advanced compiler design and implementation — С. 13, 327, 603.
  13. Frances Allen, John Cocke, and Ken Kennedy. Reduction of Operator Strength. В Program Flow Analysis: Theory & Application, Muchnick and Jones, Prentice-Hall, 1981.
  14. Browser debate: Did Microsoft cheat?. The H. Архів оригіналу за 25 червня 2012. Процитовано 12 червня 2012.
  15. Lies, damned lies, and benchmarks: is IE9 cheating at SunSpider?. Ars Technica. Архів оригіналу за 25 червня 2012. Процитовано 3 грудня 2017.

Література

  • [en] and Torczon. Engineering a Compiler. — Morgan Kaufmann, 2011. — С. 544—550, 593. — .
  • Ахо, Альфред В.; Сети, Рави; Ульман, Джеффри Д. Компиляторы — принципы, технологии, инструменты. — Вильямс, 2003. — С. 713, 714, 733, 734. — .
  • [en]. Advanced Compiler Design and Implementation. — , 1997. — С. 592-597. — .

Посилання

  • How to trick C/C++ compilers into generating terrible code?

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

V teoriyi kompilyatoriv vi dalennyam me rtvogo ko du angl dead code elimination DCE nazivayut optimizaciyu za yakoyi vidalyayetsya mertvij kod Me rtvim ko dom abo ma rnim ko dom nazivayut kod vikonannya yakogo ne vplivaye na vivid programi vsi rezultati obchislennya takogo kodu ye en tobto zminnimi znachennya yakih nadali v programi ne vikoristovuyutsya Cherez isnuvannya riznochitan termina mertvij kod vazhlivo vidznachiti sho optimizaciya vidalennya mertvogo kodu ne zajmayetsya vidalennyam nedosyazhnogo kodu Lokalizaciyeyu i vidalennyam nedosyazhnogo kodu mozhut zajmatisya pribiralnik abo inshi optimizaciyi napriklad vidalennya nedosyazhnogo kodu Vidalennya nepotribnogo kodu zdatne priskoriti robotu programi zavdyaki zmenshennyu kilkosti vikonuvanih u nij operacij i zmenshiti obsyag programi abo en PrikladiRozglyanemo takij kod movoyu Si int foo void int a 24 int b b a 3 Marnij kod return a lt lt 2 U comu prikladi operaciya dodavannya b a 3 ye mertvim kodom oskilki zminna b ne vikoristovuyetsya v podalshih obchislennyah a otzhe ye mertvoyu pochinayuchi z ciyeyi tochki i zakinchuyuchi kincem proceduri Pislya vidalennya ciyeyi instrukciyi otrimayemo int foo void int a 24 int b Mertva zminna return a lt lt 2 Pislya vidalennya operaciyi dodavannya zminna b staye mertvoyu u vsij proceduri Oskilki yiyi ogolosheno lokalno to yiyi mozhna povnistyu vidaliti z programi int foo void int a 24 return a lt lt 2 Popri te sho obchislennya vidbuvayetsya vseredini funkciyi jogo rezultat zapisuyetsya v zminnu yaka perebuvaye v oblasti vidimosti tilki ciyeyi funkciyi yaksho vrahuvati sho funkciya bezumovno povertaye chislo 96 yiyi mozhna sprostiti optimizaciyeyu tak shob yiyi tilo skladalosya tilki z operaciyi return 96 A potim kompilyator zmozhe zaminiti vsi vikliki ciyeyi funkciyi znachennyam yake vona povertaye AlgoritmiKlasichnij algoritm DCE Dead pracyuye na i skladayetsya z dvoh obhodiv pershij obhid Mark poznachaye markuye vsi napevne zhivi operaciyi operaciyi vihodu z proceduri vvedennya vivedennya sho zminyuyut globalni zminni drugij obhid Sweep pochinayetsya z zhivih operacij i jde vgoru po viznachennyah argumentiv poznachayuchi vsi operaciyi na svoyemu shlyahu zhivimi zakinchuyuchi timi operaciyami yaki ne mayut poperednikiv u SSA podanni Maksimalna obchislyuvalna skladnist takogo algoritmu zalezhit vid rozmiru programi yak O n2 DCE mozhe ne provoditi niyakogo samostijnogo analizu a prosto skoristatisya rezultatami en ale obchislyuvalna skladnist takogo analizu stanovit u girshomu vipadku O n3 Isnuyut specifichni algoritmi yaki vidalyayut porozhni vuzli v grafi potoku keruvannya ob yednuyut dekilka bazovih blokiv v odin tosho ale dlya takogo analizu potriben pobudovanij graf potoku keruvannya Algoritm Dead vpershe opublikovano v statti Static Single Assignment Form and the Program Dependence Graph v zhurnali en 1991 roku Algoritm Clean sho pracyuye z grafom potoku keruvannya rozrobiv i realizuvav Rob Shiller 1992 roku ZastosuvannyaVidalennya mertvogo kodu mozhe v procesi kompilyaciyi zastosovuvatisya kilka raziv oskilki mertvij kod mozhe ne tilki isnuvati v programi vid pochatku ale j z yavlyatisya pislya deyakih peretvoren kodu programi Napriklad optimizaciyi en i chasto peretvoryuyut instrukciyi v marnij kod Takozh dovoditsya vidalyati mertvij kod stvorenij inshimi peretvorennyami v kompilyatori Napriklad klasichnij algoritm optimizaciyi zamishaye trudomistki operaciyi mensh trudomistkimi pislya chogo vidalennya mertvogo kodu usuvaye stari operaciyi i zavershuye peretvorennya bez uskladnennya algoritmu znizhennya vartosti Cikavi faktiU listopadi 2010 roku Microsoft vipustila novu versiyu Internet Explorer 9 Platform Preview 7 yaka za shvidkistyu interpretaciyi JavaScript na benchmarku SunSpider 20 sichnya 2022 u Wayback Machine perevershila vsi inshi brauzeri V oficijnomu blozi Internet Explorer lider proyektu en zayaviv sho odnim iz novovveden relizu ye vikoristannya optimizaciyi vidalennya mertvogo kodu zavdyaki chomu j dosyagnuto takogo rezultatu Odnak nezabarom z yasuvalosya sho neznachni zmini u sircevomu kodi benchmarka viklikali istotne padinnya produktivnosti Internet Explorer 9 chogo ne vidbuvalosya pri testuvanni Google Chrome abo Opera Cherez ce na adresu rozrobnikiv Internet Explorer posipalisya zvinuvachennya v pidgonci produktu pid konkretnij benchmark Div takozhMertvij kod Nedosyazhnij kod Vidalennya nedosyazhnogo koduPrimitkiKompilyatory principy tehnologii instrumenty S 713 714 Engineering a Compiler S 544 Dead code detection and removal Aivosto Arhiv originalu za 5 serpnya 2012 Procitovano 14 lipnya 2012 smeshivanie ponyatij myortvogo i nedostizhimogo kodov Kompilyatory principy tehnologii instrumenty S 669 nedostizhimyj kod 713 myortvyj kod A Yu Drozdov A M Stepanenkov Upravlyaemye pakety optimizacij V Informacionnye tehnologii i vychislitelnye sistemy 2004 3 tekst 2016 03 04 u Wayback Machine Engineering a Compiler S 544 546 Jan Olaf Blech Lars Gesellensetter Sabine Glesner Formal Verification of Dead Code Elimination in Isabelle HOL sentyabr 2005 tekst Advanced Compiler Design and Implementation S 443 Engineering a Compiler S 547 550 Ron Cytron Jeanne Ferrante Barry Rosen and Ken Zadeck Efficiently Computing Static Single Assignment Form and the Program Dependence Graph en 13 4 1991 tekst Engineering a Compiler S 593 Advanced compiler design and implementation S 13 327 603 Frances Allen John Cocke and Ken Kennedy Reduction of Operator Strength V Program Flow Analysis Theory amp Application Muchnick and Jones Prentice Hall 1981 Browser debate Did Microsoft cheat The H Arhiv originalu za 25 chervnya 2012 Procitovano 12 chervnya 2012 Lies damned lies and benchmarks is IE9 cheating at SunSpider Ars Technica Arhiv originalu za 25 chervnya 2012 Procitovano 3 grudnya 2017 Literatura en and Torczon Engineering a Compiler Morgan Kaufmann 2011 S 544 550 593 ISBN 978 0 12 088478 0 Aho Alfred V Seti Ravi Ulman Dzheffri D Kompilyatory principy tehnologii instrumenty Vilyams 2003 S 713 714 733 734 ISBN 5 8459 0189 8 en Advanced Compiler Design and Implementation 1997 S 592 597 ISBN 1 55860 320 4 PosilannyaHow to trick C C compilers into generating terrible code

Дата публікації:
Топ