Выбор инструкции

В информатике выбор инструкций — это этап бэкэнда компилятора , который преобразует свое промежуточное представление (IR) среднего уровня в IR низкого уровня. В типичном компиляторе выбор инструкций предшествует как планированию инструкций , так и распределению регистров ; следовательно, его выходной IR имеет бесконечный набор псевдорегистров (часто называемых временными ) и все еще может — и обычно является — объектом оптимизации peephole . В противном случае он очень похож на целевой машинный код , байт-код или язык ассемблера .

Например, для следующей последовательности ИК-кода среднего уровня

т1 = ат2 = бт3 = т1 + т2а = т3б = т1

хорошая последовательность инструкций для архитектуры x86 —

MOV EAX , a XCHG EAX , b ДОБАВИТЬ a , EAX

Для всестороннего обзора выбора инструкций см. [1] [2]

Макрорасширение

Самый простой подход к выбору инструкций известен как макрорасширение [3] или генерация интерпретативного кода . [4] [5] [6] Селектор макрорасширяющихся инструкций работает путем сопоставления шаблонов по IR среднего уровня. При сопоставлении выполняется соответствующий макрос , используя сопоставленную часть IR в качестве входных данных, которые выдают соответствующие целевые инструкции. Макрорасширение может быть выполнено либо непосредственно на текстовом представлении IR среднего уровня, [7] [8] либо IR может быть сначала преобразовано в графическое представление, которое затем просматривается в глубину. [9] В последнем случае шаблон сопоставляет один или несколько смежных узлов в графе.

Если целевая машина не очень проста, макрорасширение в изоляции обычно генерирует неэффективный код. Чтобы смягчить это ограничение, компиляторы, которые применяют этот подход, обычно объединяют его с оптимизацией peephole , чтобы заменить комбинации простых инструкций более сложными эквивалентами, которые повышают производительность и уменьшают размер кода. Это известно как подход Дэвидсона-Фрейзера и в настоящее время применяется в GCC . [10]

Покрытие графа

Другой подход заключается в том, чтобы сначала преобразовать IR среднего уровня в граф , а затем покрыть граф с помощью шаблонов . Шаблон — это шаблон, который соответствует части графа и может быть реализован с помощью одной инструкции, предоставленной целевой машиной. Цель состоит в том, чтобы покрыть граф таким образом, чтобы общая стоимость выбранных шаблонов была минимизирована, где стоимость обычно представляет собой количество циклов, необходимых для выполнения инструкции. Для древовидных графов покрытие с наименьшей стоимостью может быть найдено за линейное время с помощью динамического программирования , [11] но для DAG и полноценных графов задача становится NP-полной и, таким образом, чаще всего решается с помощью либо жадных алгоритмов , либо методов комбинаторной оптимизации. [12] [13] [14]

Ссылки

  1. ^ Блинделл, Габриэль С. Хьорт (2013). Обзор выбора инструкций: обширный и современный обзор литературы (отчет). arXiv : 1306.4898 . ISBN 978-91-7501-898-0.
  2. ^ Блинделл, Габриэль С. Хьорт (2016). Выбор инструкций: принципы, методы и приложения. Springer. doi :10.1007/978-3-319-34019-7. ISBN 978-3-319-34017-3. S2CID  13390131.
  3. ^ Браун, П. (1969). «Обзор макропроцессоров». Annual Review in Automatic Programming . 6 (2): 37–88. doi :10.1016/0066-4138(69)90001-9. ISSN  0066-4138.
  4. ^ Cattell, RGG (1979). "Обзор и критика некоторых моделей генерации кода" (PDF) . Школа компьютерных наук, Университет Карнеги-Меллона (технический отчет). Архивировано (PDF) из оригинала 23 мая 2019 г.
  5. ^ Ганапати, М.; Фишер, КН; Хеннесси, Дж. Л. (1982). «Генерация кода перенацеливаемого компилятора». Computing Surveys . 14 (4): 573–592. doi :10.1145/356893.356897. ISSN  0360-0300. S2CID  2361347.
  6. ^ Лунелл, Х. (1983). Системы написания генераторов кодов (докторская диссертация). Линчёпинг, Швеция: Университет Линчёпинга.
  7. ^ Амманн, Ю.; Нори, КВ; Дженсен, К.; Нэгели, Х. (1974). «Замечания по реализации компилятора PASCAL (P)». Instituts für Informatik (Технический отчет).
  8. ^ Оргасс, Р. Дж.; Уэйт, В. М. (1969). «База для мобильной системы программирования». Сообщения ACM . 12 (9): 507–510. doi : 10.1145/363219.363226 . S2CID  8164996.
  9. ^ Уилкокс, ТР (1971). Генерация машинного кода для языков программирования высокого уровня (докторская диссертация). Итака, Нью-Йорк, США: Корнельский университет.
  10. ^ Дэвидсон, Дж. В.; Фрейзер, К. В. (1984). «Выбор кода посредством оптимизации объектного кода». Труды ACM по языкам и системам программирования . 6 (4): 505–526. CiteSeerX 10.1.1.76.3796 . doi :10.1145/1780.1783. ISSN  0164-0925. S2CID  10315537. 
  11. ^ Ахо, А. В.; Ганапати, М.; Тьян, СВК (1989). «Генерация кода с использованием сопоставления деревьев и динамического программирования». Труды ACM по языкам и системам программирования . 11 (4): 491–516. CiteSeerX 10.1.1.456.9102 . doi :10.1145/69558.75700. S2CID  1165995. 
  12. ^ Wilson, T.; Grewal, G.; Halley, B.; Banerji, D. (1994). «Комплексный подход к генерации перенацеливаемого кода». Труды 7-го Международного симпозиума по высокоуровневому синтезу . С. 70–75. CiteSeerX 10.1.1.521.8288 . doi :10.1109/ISHLS.1994.302339. ISBN  978-0-8186-5785-6. S2CID  14384424.
  13. ^ Башфорд, Стивен; Лейперс, Райнер (1999). "Выбор кода, управляемого ограничениями, для ЦСП с фиксированной точкой". Труды 36-й конференции ACM/IEEE по автоматизации проектирования - DAC '99 . стр. 817–822. CiteSeerX 10.1.1.331.390 . doi :10.1145/309847.310076. ISBN  978-1581331097. S2CID  5513238.
  14. ^ Флох, А.; Волински, К.; Кучински, К. (2010). «Комбинированное планирование и выбор инструкций для процессоров с реконфигурируемой фабрикой ячеек». Труды 21-й Международной конференции по прикладным архитектурам и процессорам (ASAP'10) : 167–174.
Получено с "https://en.wikipedia.org/w/index.php?title=Выбор_инструкции&oldid=1188176304#Стратегия_самого_общего_деноминатора"