Супероптимизация — это процесс, при котором компилятор автоматически находит оптимальную последовательность для последовательности инструкций без циклов. Реальные компиляторы, как правило, не могут производить действительно оптимальный код, и хотя большинство стандартных оптимизаций компиляторов улучшают код только частично, цель супероптимизатора — найти оптимальную последовательность, каноническую форму . Супероптимизаторы можно использовать для улучшения обычных оптимизаторов, выделяя упущенные возможности, чтобы человек мог написать дополнительные правила.
История
Термин «супероптимизация» впервые был введен Алексией Массалин в статье 1987 года «Супероптимизатор: взгляд на самую маленькую программу» . [1]
Ярлык «оптимизация программы» был дан области, которая не стремится к оптимизации, а только к улучшению. Это неправильное название заставило Массалин назвать свою систему супероптимизатором, которая на самом деле является оптимизатором для поиска оптимальной программы. [2]
В 1992 году был разработан GNU Superoptimizer (GSO) для интеграции в GNU Compiler Collection (GCC). [3] [4] Более поздние работы продолжили развивать и расширять эти идеи.
Методы
Традиционно супероптимизация выполняется с помощью полного перебора в пространстве допустимых последовательностей инструкций. Это дорогостоящий метод, и поэтому непрактичный для компиляторов общего назначения. Тем не менее, было показано, что он полезен для оптимизации внутренних циклов, критически важных для производительности. Также возможно использовать решатель SMT для решения проблемы, значительно повышая эффективность поиска (хотя входные данные, более сложные, чем базовый блок , остаются вне досягаемости). [5]
В 2001 году целевая супероптимизация была продемонстрирована в проекте Denali исследовательской группой Compaq. [6] В 2006 году декларативное программирование с использованием набора ответов использовалось для супероптимизации в проекте Total Optimisation using Answer Set Technology (TOAST) в Университете Бата . [7] [8]
Супероптимизация может использоваться для автоматического создания универсальных оптимизаторов-глазков . [9]
Общедоступные супероптимизаторы
Несколько супероптимизаторов доступны для бесплатной загрузки.
Для семейства наборов инструкций x86:
GNU superoptimizer (superopt) [10] (GSO) (1992) [3] [4] – также поддерживает многие другие ISA
^ Massalin, Henry (1987). "Superoptimizer: A look at the smallly program" (PDF) . ACM SIGARCH Computer Architecture News . 15 (5): 122–126. doi :10.1145/36177.36194 . Получено 2023-05-01 . Учитывая набор инструкций, супероптимизатор находит самую короткую программу для вычисления функции. Были созданы поразительные программы, многие из которых занимались замысловатыми битовыми манипуляциями, имеющими мало общего с исходными программами, которые определяли функции. Ключевая идея в супероптимизаторе — вероятностный тест, который делает исчерпывающий поиск практичным для программ полезного размера.
^ ab Granlund, Torbjörn; Kenner, Richard (июль 1992 г.). "Устранение ветвей с помощью супероптимизатора и компилятора GNU C". Труды конференции ACM SIGPLAN 1992 года по проектированию и реализации языков программирования - PLDI '92 . Том 27. С. 341–352. CiteSeerX 10.1.1.58.3509 . doi :10.1145/143095.143146. ISBN978-0-89791475-8. S2CID 8825539. {{cite book}}: |journal=проигнорировано ( помощь )
^ ab "Индекс /gnu/superopt". Операционная система GNU . Free Software Foundation, Inc. 1995-06-14 . Получено 2023-05-01 .
^ ab Jangda, Abhinav; Yorsh, Greta (2017-10-25). Неограниченная супероптимизация . Вперед!'17, 25–27 октября 2017 г., Ванкувер, Канада. С. 78–88. doi :10.1145/3133850.3133856.
^ Brain, Martin; Crick, Tom; De Vos, Marina; Fitch, John (2006-08-17). "TOAST: применение программирования с набором ответов к супероптимизации". В Etalle, Sandro; Truszczyński, Mirosław (ред.). Logic Programming . Springer-Verlag , Berlin / Heidelberg. стр. 270–284. ISBN978-3-540-36636-2.
^ "TOAST – KRRwiki". Департамент компьютерных наук, Группа математических основ. Группа представления и обоснования знаний (KRR) . Университет Бата . 2007-08-07. Архивировано из оригинала 2012-11-28 . Получено 2016-09-03 .
^ Бансал, Сорав; Айкен, Алекс (2008). «Двоичная трансляция с использованием супероптимизаторов Peephole» (PDF) . Получено 01.05.2023 .
^ Serpell, Daniel (2003). "SuperOptimizer for Microchip's PIC microcontrollers". Google Sites . Архивировано из оригинала 2016-10-11 . Получено 2016-09-06 .
^ Serpell, Daniel (2003-06-21). "PIC Microcontroller SuperOptimizer". Freecode . Slashdot Media. Архивировано из оригинала 2016-09-17 . Получено 2016-09-06 .
^ "Технико-экономическое обоснование Embecosm".
^ Супероптимизация – Исходный код Embecosm
^ Хьюм, Том (2012-08-21). "Программа Clojure для исчерпывающего поиска оптимальных программ Java". GitHub . Архивировано из оригинала 2018-06-10 . Получено 2016-09-06 .