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

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

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

t1 = at2 = bt3 = t1 + t2a = t3b = t1

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

MOV EAX, аXCHG EAX, бДОБАВИТЬ а, EAX

Подробный обзор выбора инструкций см.[1]

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

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

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

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

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

Стратегия наименьшего общего знаменателя

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

Использование стратегии наименьшего общего знаменателя означает, что дополнительные инструкции процессора и возможности по умолчанию не используются.

Рекомендации

  1. ^ Хьорт Блинделл, Габриэль (2016). Выбор инструкций: принципы, методы и применение. Springer. Дои:10.1007/978-3-319-34019-7. ISBN  978-3-319-34017-3.
  2. ^ Браун, П. (1969). «Обзор макропроцессоров». Ежегодный обзор в области автоматического программирования. 6 (2): 37–88. Дои:10.1016/0066-4138(69)90001-9. ISSN  0066-4138.
  3. ^ Кеттелл, Р. Дж. Г. (1979). «Обзор и критика некоторых моделей генерации кода» (PDF). Школа компьютерных наук Университета Карнеги-Меллона (Технический отчет).
  4. ^ Ganapathi, M .; Fischer, C.N .; Хеннесси, Дж. Л. (1982). «Генерация кода ретаргетируемого компилятора». Вычислительные опросы. 14 (4): 573–592. Дои:10.1145/356893.356897. ISSN  0360-0300.
  5. ^ Лунелл, Х. (1983). Системы написания генераторов кода (Докторская диссертация). Линчёпинг, Швеция: Университет Линчёпинга.
  6. ^ Ammann, U .; Nori, K. V .; Jensen, K .; Нэгели, Х. (1974). «Замечания по реализации компилятора PASCAL (P)». Instituts für Informatik (Технический отчет).
  7. ^ Orgass, R.J .; Уэйт, У. М. (1969). «База мобильной системы программирования». Коммуникации ACM. 12 (9): 507–510. Дои:10.1145/363219.363226.
  8. ^ Уилкокс, Т. Р. (1971). Генерация машинного кода для языков программирования высокого уровня (Докторская диссертация). Итака, Нью-Йорк, США: Корнельский университет.
  9. ^ Дэвидсон, Дж. У .; Фрейзер, К. В. (1984). «Выбор кода посредством оптимизации объектного кода». Транзакции ACM по языкам и системам программирования. 6 (4): 505–526. CiteSeerX  10.1.1.76.3796. Дои:10.1145/1780.1783. ISSN  0164-0925.
  10. ^ Ахо, А. В .; Ganapathi, M .; Цзян, С. В. К. (1989). «Генерация кода с использованием сопоставления деревьев и динамического программирования». Транзакции ACM по языкам и системам программирования. 11 (4): 491–516. CiteSeerX  10.1.1.456.9102. Дои:10.1145/69558.75700.
  11. ^ Wilson, T .; Grewal, G .; Halley, B .; Банерджи, Д. (1994). Комплексный подход к перенацеливанию генерации кода. Материалы 7-го Международного симпозиума по синтезу высокого уровня (ISSS'94). С. 70–75. CiteSeerX  10.1.1.521.8288. Дои:10.1109 / ISHLS.1994.302339. ISBN  978-0-8186-5785-6.
  12. ^ Башфорд, Стивен; Leupers, Райнер (1999). «Выбор кода на основе ограничений для DSPS с фиксированной точкой». Материалы 36-й конференции ACM / IEEE по автоматизации проектирования - DAC '99. С. 817–822. CiteSeerX  10.1.1.331.390. Дои:10.1145/309847.310076. ISBN  978-1581331097.
  13. ^ Floch, A .; Wolinski, C .; Куччинский, К. (2010). «Комбинированное планирование и выбор инструкций для процессоров с реконфигурируемой структурой ячеек». Материалы 21-й Международной конференции по прикладным архитектурам и процессорам (ASAP'10): 167–174.

внешняя ссылка