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

Распределением регистров в процессе компиляции^[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. (англ.)

Ссылки править

http://www.intuit.ru/studies/courses/1157/173/lecture/4707?page=5 7
Компиляция. 7: назначение регистров, 2010
Караваев Д.Ю. О реализации метода распределения регистров при компиляции, RSDN 2012
Hadi Brais, Оптимизации компилятором - Что каждый программист должен знать об оптимизациях кода компилятором. Часть 2, Май 2015
Keith Schwarz, Register Allocation, Stanford's cs143 Compilers, 2012

[1] НОУ ИНТУИТ | Лекция | Выбор инструкций при генерации кода (неопр.). Дата обращения: 28 ноября 2017. Архивировано 28 июля 2021 года.

[2] 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. (англ.)

[3] 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

[4] Preston Briggs, Keith D. Cooper, Ken Kennedy, Linda Torczon. «Coloring Heuristics for Register Allocation.» ACM SIGPLAN Notices, Volume 24, Issue 7, 275—284, 1989. (англ.)

[1]

[2]

[3]

[4]