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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

Проблемы[править | править вики-текст]

Задача распределения регистров является 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&nbsp;(англ.)
  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. (англ.)