Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
В информатике выбор инструкций — это этап бэкенда компилятора, который преобразует промежуточное представление среднего уровня (IR) в промежуточное представление низкого уровня. В типичном компиляторе выбор инструкций предшествует планированию инструкций и распределению регистров; следовательно, выходной IR содержит бесконечное множество псевдорегистров (часто называемых временными переменными) и может, и обычно подвергается, оптимизации проходами. В остальном он тесно соответствует машинному коду целевой платформы, байт-коду или языку ассемблера. Например, для следующей последовательности кода IR среднего уровня:
t1 = a
t2 = b
t3 = t1 + t2
a = t3
b = t1
NOTOC
In computer science, instruction selection is the stage of a compiler backend that transforms its middle level intermediate representation (IR) into a low level IR. In a typical compiler, instruction selection precedes both instruction scheduling and register allocation; hence its output IR has an infinite set of pseudo registers (often known as temporaries) and may still be – and typically is – subject to peephole optimization. Otherwise, it closely resembles the target machine code, bytecode, or assembly language. For example, for the following sequence of middle level IR code
t1 = a
t2 = b
t3 = t1 + t2
a = t3
b = t1
хорошей последовательностью инструкций для архитектуры x86 будет:
a good instruction sequence for the x86 architecture is
MOV EAX, a
XCHG EAX, b
ADD a, EAX
MOV EAX, a
XCHG EAX, b
ADD a, EAX
Для всестороннего обзора темы выбора инструкций см.
For a comprehensive survey on instruction selection, see.
Макро-расширение
Самый простой подход к выбору инструкций известен как расширение макросов или генерация интерпретативного кода. Выборщик инструкций, основанный на расширении макросов, работает путем сопоставления шаблонов с промежуточным представлением (IR). При совпадении соответствующий макрос выполняется, используя сопоставленную часть IR в качестве входных данных, что приводит к генерации соответствующих целевых инструкций. Расширение макросов может выполняться либо непосредственно над текстовым представлением IR, либо IR может быть сначала преобразовано в графическое представление, которое затем обходится в глубину. В последнем случае шаблон сопоставляется с одним или несколькими смежными узлами в графе. Если целевая машина не очень проста, расширение макросов само по себе обычно генерирует неэффективный код. Чтобы смягчить это ограничение, компиляторы, использующие этот подход, обычно сочетают его с оптимизацией "peephole", заменяя комбинации простых инструкций более сложными эквивалентами, которые повышают производительность и уменьшают размер кода. Этот подход известен как подход Дэвидсона — Фрейзера и в настоящее время применяется в GCC.
The simplest approach to instruction selection is known as macro expansion or interpretative code generation. A macro expanding instruction selector operates by matching templates over the middle level IR. Upon a match the corresponding macro is executed, using the matched portion of the IR as input, which emits the appropriate target instructions. Macro expansion can be done either directly on the textual representation of the middle level IR, or the IR can first be transformed into a graphical representation which is then traversed depth first. In the latter, a template matches one or more adjacent nodes in the graph. Unless the target machine is very simple, macro expansion in isolation typically generates inefficient code. To mitigate this limitation, compilers that apply this approach typically combine it with peephole optimization to replace combinations of simple instructions with more complex equivalents that increase performance and reduce code size. This is known as the Davidson Fraser approach and is currently applied in GCC.
Покрытие графика
Другой подход заключается в том, чтобы сначала преобразовать промежуточное представление высокого уровня в граф, а затем покрыть этот граф с помощью шаблонов. Шаблон – это образец, соответствующий части графа и реализуемый одной инструкцией целевой машины. Цель состоит в том, чтобы покрыть граф таким образом, чтобы общая стоимость выбранных шаблонов была минимальной, где стоимость обычно отражает количество циклов, необходимых для выполнения инструкции. Для графов, имеющих древовидную структуру, покрытие с наименьшей стоимостью можно найти за линейное время с помощью динамического программирования, но для DAG-графов и полноценных графов задача становится NP-полной и, следовательно, чаще всего решается с использованием жадных алгоритмов или методов комбинаторной оптимизации.
Another approach is to first transform the middle level IR into a graph and then cover the graph using patterns. A pattern is a template that matches a portion of the graph and can be implemented with a single instruction provided by the target machine. The goal is to cover the graph such that the total cost of the selected patterns is minimized, where the cost typically represents the number of cycles it takes to execute the instruction. For tree shaped graphs, the least cost cover can be found in linear time using dynamic programming, but for DAGs and full fledged graphs the problem becomes NP complete and thus is most often solved using either greedy algorithms or methods from combinatorial optimization.