Выбор инструкции
В информатике , выбор инструкций — это этап бэкэнда компилятора (IR) среднего уровня который преобразует свое промежуточное представление в IR низкого уровня. В типичном компиляторе выбор инструкций предшествует как планированию команд, так и выделению регистров ; следовательно, его выходной сигнал IR имеет бесконечный набор псевдорегистров (часто называемых временными ) и может по-прежнему подвергаться – и обычно является – объектом оптимизации «глазок» . В остальном он очень похож на целевой машинный код , байт-код или язык ассемблера .
Например, для следующей последовательности IR-кода среднего уровня
t1 = a t2 = b t3 = t1 + t2 a = t3 b = t1
хорошая последовательность команд для архитектуры x86 :
MOV EAX, a
XCHG EAX, b
ADD a, EAX
Подробный обзор выбора инструкций см. [1] [2]
Расширение макросов
[ редактировать ]Самый простой подход к выбору инструкций известен как расширение макроса. [3] или генерация интерпретирующего кода . [4] [5] [6] Селектор команд расширения макроса работает путем сопоставления шаблонов через IR среднего уровня. При совпадении соответствующий макрос выполняется с использованием совпавшей части IR в качестве входных данных, который генерирует соответствующие целевые инструкции. Расширение макроса может быть выполнено либо непосредственно на текстовом представлении ИР среднего уровня, [7] [8] или IR может быть сначала преобразован в графическое представление, которое затем просматривается в глубину. [9] В последнем случае шаблон соответствует одному или нескольким соседним узлам графа.
Если целевая машина не очень проста, изолированное расширение макросов обычно создает неэффективный код. Чтобы смягчить это ограничение, компиляторы, применяющие этот подход, обычно сочетают его с оптимизацией «глазок», чтобы заменить комбинации простых инструкций более сложными эквивалентами, которые повышают производительность и уменьшают размер кода. Это известно как подход Дэвидсона-Фрейзера и в настоящее время применяется в GCC . [10]
Покрытие графа
[ редактировать ]Другой подход — сначала преобразовать IR среднего уровня в граф , а затем покрыть граф с помощью шаблонов . Шаблон — это шаблон, который соответствует части графа и может быть реализован с помощью одной инструкции, предоставленной целевой машиной. Цель состоит в том, чтобы покрыть граф так, чтобы общая стоимость выбранных шаблонов была минимизирована, причем стоимость обычно представляет собой количество циклов, необходимых для выполнения инструкции. Для древовидных графов покрытие с наименьшей стоимостью можно найти за линейное время с помощью динамического программирования . [11] но для DAG и полноценных графов проблема становится NP-полной и поэтому чаще всего решается с использованием либо жадных алгоритмов , либо методов комбинаторной оптимизации. [12] [13] [14]
Ссылки
[ редактировать ]- ^ Блинделл, Габриэль С. Хьорт (2013). Обзор выбора инструкций: обширный и современный обзор литературы (отчет). arXiv : 1306.4898 . ISBN 978-91-7501-898-0 .
- ^ Блинделл, Габриэль С. Хьорт (2016). Выбор инструкций: принципы, методы и приложения . Спрингер. дои : 10.1007/978-3-319-34019-7 . ISBN 978-3-319-34017-3 . S2CID 13390131 .
- ^ Браун, П. (1969). «Обзор макропроцессоров». Ежегодный обзор автоматического программирования . 6 (2): 37–88. дои : 10.1016/0066-4138(69)90001-9 . ISSN 0066-4138 .
- ^ Кеттелл, RGG (1979). «Обзор и критика некоторых моделей генерации кода» (PDF) . Школа компьютерных наук Университета Карнеги-Меллон (технический отчет). Архивировано (PDF) из оригинала 23 мая 2019 г.
- ^ Ганапати, М.; Фишер, Китай; Хеннесси, Дж. Л. (1982). «Генерация кода перенацеливаемого компилятора». Вычислительные опросы . 14 (4): 573–592. дои : 10.1145/356893.356897 . ISSN 0360-0300 . S2CID 2361347 .
- ^ Лунелл, Х. (1983). Генераторные системы письма (Докторская диссертация). Линчёпинг, Швеция: Университет Линчёпинга.
- ^ Амманн, У.; Нори, КВ; Дженсен, К.; Нэгели, Х. (1974). «Замечания по реализации компилятора PASCAL (P)». Институт компьютерных наук (Технический отчет).
- ^ Оргасс, Р.Дж.; Уэйт, WM (1969). «База для системы мобильного программирования» . Коммуникации АКМ . 12 (9): 507–510. дои : 10.1145/363219.363226 . S2CID 8164996 .
- ^ Уилкокс, Т.Р. (1971). Генерация машинного кода для языков программирования высокого уровня (Докторская диссертация). Итака, Нью-Йорк, США: Корнельский университет.
- ^ Дэвидсон, Дж.В.; Фрейзер, CW (1984). «Выбор кода посредством оптимизации объектного кода». Транзакции ACM в языках и системах программирования . 6 (4): 505–526. CiteSeerX 10.1.1.76.3796 . дои : 10.1145/1780.1783 . ISSN 0164-0925 . S2CID 10315537 .
- ^ Ахо, А.В.; Ганапати, М.; Цзян, SWK (1989). «Генерация кода с использованием сопоставления деревьев и динамического программирования». Транзакции ACM в языках и системах программирования . 11 (4): 491–516. CiteSeerX 10.1.1.456.9102 . дои : 10.1145/69558.75700 . S2CID 1165995 .
- ^ Уилсон, Т.; Гревал, Г.; Галли, Б.; Банерджи, Д. (1994). «Комплексный подход к генерации ретаргетингового кода». Материалы 7-го международного симпозиума по синтезу высокого уровня . стр. 70–75. CiteSeerX 10.1.1.521.8288 . дои : 10.1109/ISHLS.1994.302339 . ISBN 978-0-8186-5785-6 . S2CID 14384424 .
- ^ Башфорд, Стивен; Лойперс, Райнер (1999). «Выбор кода на основе ограничений для DSPS с фиксированной точкой». Материалы 36-й конференции ACM/IEEE по автоматизации проектирования - DAC '99 . стр. 817–822. CiteSeerX 10.1.1.331.390 . дои : 10.1145/309847.310076 . ISBN 978-1581331097 . S2CID 5513238 .
- ^ Флох, А.; Волински, К.; Куччинский, К. (2010). «Комбинированное планирование и выбор инструкций для процессоров с реконфигурируемой матрицей ячеек». Материалы 21-й Международной конференции по архитектурам и процессорам для конкретных приложений (ASAP'10) : 167–174.