Супероптимизация

Супероптимизация — это процесс, при котором компилятор автоматически находит оптимальную последовательность инструкций без циклов. Реальные компиляторы, как правило, не могут создавать по-настоящему оптимальный код, и хотя большинство стандартных оптимизаций компилятора улучшают код лишь частично, цель супероптимизатора — найти оптимальную последовательность, каноническую форму . Супероптимизаторы можно использовать для улучшения обычных оптимизаторов, выделяя упущенные возможности, чтобы человек мог написать дополнительные правила.

История

Термин «супероптимизация» был впервые введен Алексией Массалин в статье 1987 года «Супероптимизатор: взгляд на самую маленькую программу» . ^{[ 1 ]} Ярлык «оптимизация программы» был присвоен области, которая не стремится к оптимизации, а только к улучшению. Это неправильное название вынудило Массалин назвать свою систему супероптимизатором, который на самом деле является оптимизатором для поиска оптимальной программы. ^{[ 2 ]}

В 1992 году был разработан GNU Superoptimizer (GSO) для интеграции в коллекцию компиляторов GNU (GCC). ^{[ 3 ]}^{[ 4 ]} Более поздние работы развили и расширили эти идеи.

Техники

Традиционно супероптимизация выполняется путем исчерпывающего перебора в пространстве допустимых последовательностей команд. Это дорогостоящий метод, поэтому он непрактичен для компиляторов общего назначения. Тем не менее, было показано, что он полезен при оптимизации внутренних циклов, критичных к производительности. также можно использовать решатель SMT Для решения проблемы , что значительно повышает эффективность поиска (хотя входные данные, более сложные, чем базовый блок, остаются недоступными). ^{[ 5 ]}

В 2001 году целенаправленная супероптимизация была продемонстрирована в проекте Denali исследовательской компанией Compaq. ^{[ 6 ]} В 2006 году набора ответов декларативное программирование использовалось для супероптимизации в проекте «Полная оптимизация с использованием технологии набора ответов» (TOAST) в Университете Бата . ^{[ 7 ]}^{[ 8 ]}

Супероптимизацию можно использовать для автоматического создания оптимизаторов-глазков общего назначения . ^{[ 9 ]}

Общедоступные супероптимизаторы

Несколько супероптимизаторов доступны для бесплатного скачивания.

Для семейства наборов инструкций x86:
- Супероптимизатор GNU (суперопт) ^{[ 10 ]} (ГСО) (1992) ^{[ 3 ]}^{[ 4 ]} – также поддерживает множество других ISA
- СТОК, ^{[ 11 ]} стохастический оптимизатор ^{[ 12 ]} для x86-64 языка ассемблера x86 .
Для АРМ:
- Неограниченный супероптимизатор, ^{[ 5 ]} преобразование LLVM IR в сборку ARMv7-A
Для встраиваемых систем:
- PIC-микроконтроллер SuperOptimizer (2003 г.) ^{[ 13 ]}^{[ 14 ]}
- Технико-экономическое обоснование AVR , проведенное Embecosm (2014 г.) , на основе GSO. ^{[ 15 ]}^{[ 16 ]}
Для JVM:
- Супероптимизатор Clojure для виртуальной машины Java (2012 г.) ^{[ 17 ]}
Для ЛЛВМ ИР:
- ужин ^{[ 18 ]} супероптимизатор для программ на промежуточном языке LLVM .
Для веб-сборки
- спады ^{[ 19 ]} обеспечивает супероптимизацию программ WASM на основе супера.

См. также

Ссылки

^ Массалин, Генри (1987). «Супероптимизатор: взгляд на самую маленькую программу» (PDF) . Новости компьютерной архитектуры ACM SIGARCH . 15 (5): 122–126. дои : 10.1145/36177.36194 . Проверено 1 мая 2023 г. Учитывая набор команд, супероптимизатор находит кратчайшую программу для вычисления функции. Были созданы поразительные программы, многие из которых занимаются запутанной битовой манипуляцией, мало похожей на исходные программы, определяющие функции. Ключевая идея супероптимизатора — вероятностный тест, который делает практичным исчерпывающий поиск программ полезного размера.
^ Джоши, Раджив; Нельсон, Грег; Рэндалл, Кейт (2002). «Денали: целенаправленный супероптимизатор» . Уведомления ACM SIGPLAN . 37 (5): 304–314. дои : 10.1145/543552.512566 .
^ Перейти обратно: ^а ^б Гранлунд, Торбьёрн; Кеннер, Ричард (июль 1992 г.). «Устранение ветвей с помощью супероптимизатора и компилятора GNU C». Уведомления ACM SIGPLAN . 27 (7): 341–352. CiteSeerX 10.1.1.58.3509 . дои : 10.1145/143095.143146 . ISBN 978-0-89791475-8 . S2CID 8825539 .
^ Перейти обратно: ^а ^б «Индекс /gnu/superopt» . Операционная система GNU . Фонд свободного программного обеспечения, Inc., 14 июня 1995 г .. Проверено 1 мая 2023 г.
^ Перейти обратно: ^а ^б Джангда, Абхинав; Йорш, Грета (25 октября 2017 г.). Неограниченная супероптимизация . Вперед!»'17, 25–27 октября 2017, Ванкувер, Канада. стр. 78–88. дои : 10.1145/3133850.3133856 .
^ Джоши, Раджив; Нельсон, Грег; Рэндалл, Кейт (30 июля 2001 г.). «Денали: целенаправленный супероптимизатор» . Исследовательский центр систем Compaq. Лаборатории HP . Hewlett-Packard Co. Проверено 1 мая 2023 г.
^ Брэйн, Мартин; Крик, Том; Де Вос, Марина; Фитч, Джон (17 августа 2006 г.). «TOAST: применение программирования набора ответов для супероптимизации». В Эталье, Сандро; Трушинский, Мирослав (ред.). Логическое программирование . Шпрингер-Верлаг , Берлин/Гейдельберг. стр. 270–284. ISBN 978-3-540-36636-2 .
^ «ТОСТ – KRRwiki» . Департамент компьютерных наук, группа математических фондов. Группа «Представление знаний и рассуждение» (KRR) . Университет Бата . 07.08.2007. Архивировано из оригинала 28 ноября 2012 г. Проверено 03 сентября 2016 г.
^ Бансал, Сорав; Эйкен, Алекс (2006). «Автоматическое создание супероптимизаторов-глазков» (PDF) . Проверено 1 мая 2023 г.
^ «Супероптимизатор GNU» .
^ СтэнфордPL. «СТОК» . Гитхаб .
^ Бансал, Сорав; Эйкен, Алекс (2008). «Двоичный перевод с использованием супероптимизаторов-глазков» (PDF) . Проверено 1 мая 2023 г.
^ Серпелл, Дэниел (2003). «Супероптимизатор для PIC-микроконтроллеров Microchip» . Сайты Google . Архивировано из оригинала 11 октября 2016 г. Проверено 6 сентября 2016 г.
^ Серпелл, Дэниел (21 июня 2003 г.). «Супероптимизатор микроконтроллера PIC» . Бесплатный код . Слэшдот Медиа. Архивировано из оригинала 17 сентября 2016 г. Проверено 6 сентября 2016 г.
^ «Технико-экономическое обоснование Embecosm» .
^ Embecosm Супероптимизация - Исходный код
^ Хьюм, Том (21 августа 2012 г.). «Программа Clojure для исчерпывающего поиска оптимальных Java-программ» . Гитхаб . Архивировано из оригинала 10 июня 2018 г. Проверено 6 сентября 2016 г.
^ Саснаускас, Раймондас; Чен, Ян; Коллингборн, Питер; Кетема, Йерун; Луп, Грациан; Танеха, Джуби; Регер, Джон (2017). «Супер: синтезирующий супероптимизатор». arXiv : 1711.04422 . Исходный код GitHub
^ Кабрера Артеага, Хавьер; Донде, Шриниш; Гу, Цзянь; Флорос, Орестис; Сатабин, Лукас; Бодри, Бенуа; Монперрус, Мартин (23 марта 2020 г.). Супероптимизация байт-кода WebAssembly . MoreVMs: семинар по современным языковым средам выполнения, экосистемам и виртуальным машинам. стр. 36–40. arXiv : 2002.10213 . дои : 10.1145/3397537.3397567 . Исходный код GitHub

[Massalin_1987_Superoptimizer-1] Массалин, Генри (1987). «Супероптимизатор: взгляд на самую маленькую программу» (PDF) . Новости компьютерной архитектуры ACM SIGARCH . 15 (5): 122–126. дои : 10.1145/36177.36194 . Проверено 1 мая 2023 г. Учитывая набор команд, супероптимизатор находит кратчайшую программу для вычисления функции. Были созданы поразительные программы, многие из которых занимаются запутанной битовой манипуляцией, мало похожей на исходные программы, определяющие функции. Ключевая идея супероптимизатора — вероятностный тест, который делает практичным исчерпывающий поиск программ полезного размера.

[Denali-2] Джоши, Раджив; Нельсон, Грег; Рэндалл, Кейт (2002). «Денали: целенаправленный супероптимизатор» . Уведомления ACM SIGPLAN . 37 (5): 304–314. дои : 10.1145/543552.512566 .

[GCCsuperACM-3] Перейти обратно: ^а ^б Гранлунд, Торбьёрн; Кеннер, Ричард (июль 1992 г.). «Устранение ветвей с помощью супероптимизатора и компилятора GNU C». Уведомления ACM SIGPLAN . 27 (7): 341–352. CiteSeerX 10.1.1.58.3509 . дои : 10.1145/143095.143146 . ISBN 978-0-89791475-8 . S2CID 8825539 .

[GCCsuperopt-4] Перейти обратно: ^а ^б «Индекс /gnu/superopt» . Операционная система GNU . Фонд свободного программного обеспечения, Inc., 14 июня 1995 г .. Проверено 1 мая 2023 г.

[jangda-5] Перейти обратно: ^а ^б Джангда, Абхинав; Йорш, Грета (25 октября 2017 г.). Неограниченная супероптимизация . Вперед!»'17, 25–27 октября 2017, Ванкувер, Канада. стр. 78–88. дои : 10.1145/3133850.3133856 .

[Joshi_2001-6] Джоши, Раджив; Нельсон, Грег; Рэндалл, Кейт (30 июля 2001 г.). «Денали: целенаправленный супероптимизатор» . Исследовательский центр систем Compaq. Лаборатории HP . Hewlett-Packard Co. Проверено 1 мая 2023 г.

[TOAST-book-7] Брэйн, Мартин; Крик, Том; Де Вос, Марина; Фитч, Джон (17 августа 2006 г.). «TOAST: применение программирования набора ответов для супероптимизации». В Эталье, Сандро; Трушинский, Мирослав (ред.). Логическое программирование . Шпрингер-Верлаг , Берлин/Гейдельберг. стр. 270–284. ISBN 978-3-540-36636-2 .

[TOAST-KRR-8] «ТОСТ – KRRwiki» . Департамент компьютерных наук, группа математических фондов. Группа «Представление знаний и рассуждение» (KRR) . Университет Бата . 07.08.2007. Архивировано из оригинала 28 ноября 2012 г. Проверено 03 сентября 2016 г.

[Bansal_2006-9] Бансал, Сорав; Эйкен, Алекс (2006). «Автоматическое создание супероптимизаторов-глазков» (PDF) . Проверено 1 мая 2023 г.

[GSO_1992-10] «Супероптимизатор GNU» .

[STOKE-11] СтэнфордPL. «СТОК» . Гитхаб .

[Bansal_2008-12] Бансал, Сорав; Эйкен, Алекс (2008). «Двоичный перевод с использованием супероптимизаторов-глазков» (PDF) . Проверено 1 мая 2023 г.

[Serpell_2003_1-13] Серпелл, Дэниел (2003). «Супероптимизатор для PIC-микроконтроллеров Microchip» . Сайты Google . Архивировано из оригинала 11 октября 2016 г. Проверено 6 сентября 2016 г.

[Serpell_2003_2-14] Серпелл, Дэниел (21 июня 2003 г.). «Супероптимизатор микроконтроллера PIC» . Бесплатный код . Слэшдот Медиа. Архивировано из оригинала 17 сентября 2016 г. Проверено 6 сентября 2016 г.

[Embecosm_2014-15] «Технико-экономическое обоснование Embecosm» .

[16] Embecosm Супероптимизация - Исходный код

[Hume_2012-17] Хьюм, Том (21 августа 2012 г.). «Программа Clojure для исчерпывающего поиска оптимальных Java-программ» . Гитхаб . Архивировано из оригинала 10 июня 2018 г. Проверено 6 сентября 2016 г.

[souper-18] Саснаускас, Раймондас; Чен, Ян; Коллингборн, Питер; Кетема, Йерун; Луп, Грациан; Танеха, Джуби; Регер, Джон (2017). «Супер: синтезирующий супероптимизатор». arXiv : 1711.04422 . Исходный код GitHub

[slumps-19] Кабрера Артеага, Хавьер; Донде, Шриниш; Гу, Цзянь; Флорос, Орестис; Сатабин, Лукас; Бодри, Бенуа; Монперрус, Мартин (23 марта 2020 г.). Супероптимизация байт-кода WebAssembly . MoreVMs: семинар по современным языковым средам выполнения, экосистемам и виртуальным машинам. стр. 36–40. arXiv : 2002.10213 . дои : 10.1145/3397537.3397567 . Исходный код GitHub

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

v т и Оптимизация компилятора
Базовый блок	Оптимизация глазка Нумерация локальных значений
Петля	Автоматическое распараллеливание Автоматическая векторизация Индукционная переменная Петля слияния Движение кода, инвариантное к циклу Инверсия цикла Перестановка петель Оптимизация гнезда циклов Разделение цикла Развертывание цикла Выключение петли Конвейерная обработка программного обеспечения Снижение прочности
Поток данных анализ	Доступное выражение Удаление общего подвыражения Постоянное складывание мертвого магазина Устранение Распознавание и устранение индукционных переменных Анализ переменных в реальном времени Использовать-определить цепочку
SSA на основе	Глобальная нумерация значений Разреженное условное постоянное распространение
Генерация кода	Планирование инструкций Выбор инструкции Распределение регистров Рематериализация
Функциональный	Вырубка лесов Устранение хвостового вызова
Глобальный	Межпроцедурная оптимизация
Другой	Устранение проверки границ Выполнение функции во время компиляции Устранение мертвого кода Шаблоны выражений Встроенное расширение Перейти к потоку Частичная оценка Оптимизация на основе профиля
Статический анализ	Анализ псевдонимов Анализ доступа к массиву Анализ потока управления Анализ потока данных Анализ зависимостей Анализ побега Анализ указателя Анализ формы Анализ диапазона значений