Распределение регистров

Распределением регистров в процессе компиляции^[1] называется отображение множества большого числа переменных фрагмента компьютерной программы (виртуальных регистров промежуточного представления) на, как правило, небольшое множество физических регистров микропроцессора. Распределение регистров может выполняться в отдельно взятом базовом блоке (локальное распределение регистров) или во всей процедуре (глобальное распределение регистров).

Как правило компьютерным программам приходится работать с большим количеством данных, однако большинство микропроцессоров поддерживает операции только на фиксированном числе небольших «ячеек», называемых регистрами. Некоторые процессоры позволяют использовать операнды, хранящиеся в памяти, однако обращение к регистрам происходит намного быстрее, чем обращение в память (даже с учетом того, что указанная область памяти может быть помещена в кэш).

Проблемы

Задача распределения регистров является NP-полной^[2]^[3]. Обычно количество переменных в программе значительно превосходит количество доступных физических регистров, поэтому некоторые переменные приходится хранить в локальном стеке. Обращения к памяти можно минимизировать, если хранить там наименее часто используемые переменные, однако определить, какие переменные используются наименее часто, не всегда легко.

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

Глобальное распределение регистров

Как и большинство других оптимизаций, распределение регистров основано на использовании некоторого анализа. В данном случае это наиболее часто анализ времени жизни переменных и анализ потока данных.

Традиционным алгоритмом распределения регистров считается раскраска графа несовместимости, предложенная математиком Грегори Хайтином.

Каждой переменной (символическому регистру) соответствует узел $N$ графа $G$ . Если времена жизни переменных пересекаются, соответствующие им узлы соединяются дугой. Граф нужно раскрасить $R$ цветами (где $R$ соответствует количеству доступных физических регистров) таким образом, чтобы ни одна пара соседних узлов не имела одинаковый цвет.

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

Пока граф G нельзя раскрасить R цветами
  Итеративно удалять все узлы графа степенью < R, помещая их в стек
  Если все узлы графа были удалены, граф можно раскрасить R цветами
      Вытолкнуть узел N из стека и добавить его в граф, назначив ему цвет
  В противном случае граф G нельзя раскрасить R цветами
    Упростить G, выбрав узел для сохранения в памяти и разбив его на несколько узлов
    (узел для сохранения в памяти выбирается эвристически)

Престон Бриггс предложил модифицировать алгоритм Хайтина^[4], откладывая сохранение переменной в памяти до назначения цветов узлам графа. Для некоторых нераскрашиваемых $R$ цветами графов это позволяет обойтись без сохранения переменных в памяти. Например, квадрат с узлами в вершинах может быть раскрашен $R=2$ цветами, в то время как степень всех его узлов равна двум и алгоритм Хайтина будет вынужден сохранить одну из переменных в памяти.

Примечания

↑ НОУ ИНТУИТ | Лекция | Выбор инструкций при генерации кода (неопр.). Дата обращения: 28 ноября 2017. Архивировано 28 июля 2021 года.
↑ Gregory J. Chaitin, Mark A. Auslander, Ashok K. Chandra, John Cocke, Martin E. Hopkins, and Peter W. Markstein. «Register allocation via coloring.» Computer Languages, 6:47-57, 1981. (англ.)
↑ Fernando Magno Quintão Pereira, Jens Palsberg, «Register Allocation after Classical SSA Elimination is NP-complete» (англ.), http://pike.cs.ucla.edu/~palsberg/paper/fossacs06.pdf Архивная копия от 4 марта 2016 на Wayback Machine
↑ Preston Briggs, Keith D. Cooper, Ken Kennedy, Linda Torczon. «Coloring Heuristics for Register Allocation.» ACM SIGPLAN Notices, Volume 24, Issue 7, 275—284, 1989. (англ.)