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

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

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

Проблемы

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

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

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

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

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

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

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

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

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

См. также

• Хайтин, Грегори

Примечания

1. ↑ 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. (англ.)
2. ↑ Fernando Magno Quintão Pereira, Jens Palsberg, "Register Allocation after Classical SSA Elimination is NP-complete", http://www.cs.ucla.edu/~palsberg/paper/fossacs06.pdf (англ.)
3. ↑ Preston Briggs, Keith D. Cooper, Ken Kennedy, Linda Torczon. "Coloring Heuristics for Register Allocation." ACM SIGPLAN Notices, Volume 24, Issue 7, 275-284, 1989. (англ.)