Jump to content

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

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

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

Контекст

[ редактировать ]
Различное количество скалярных регистров в наиболее распространенных архитектурах.
Архитектура 32 бит 64 бит
РУКА 15 31
Интел х86 8 16
МИПС 32 32
ПИТАНИЕ/PowerPC 32 32
РИСК-V 16/32 32
СПАРК 31 31


Во многих языках программирования программист может использовать любое количество переменных . Компьютер может быстро читать и записывать регистры ЦП работает быстрее , , поэтому компьютерная программа когда в регистрах ЦП может находиться больше переменных. [1] Кроме того, иногда код доступа к регистрам более компактен, поэтому код меньше и его можно получить быстрее, если он использует регистры, а не память. Однако количество регистров ограничено. Следовательно, когда компилятор переводит код на машинный язык, он должен решить, как распределить переменные по ограниченному числу регистров ЦП. [2] [3]

Не все переменные используются (или «действуют») одновременно, поэтому на протяжении всего времени существования программы данный регистр может использоваться для хранения разных переменных. Однако две переменные, используемые одновременно, не могут быть присвоены одному и тому же регистру без повреждения одной из переменных. Если регистров недостаточно для хранения всех переменных, некоторые переменные можно перемещать в ОЗУ и из ОЗУ . Этот процесс называется «разливом» регистров. [4] За время существования программы переменная может быть как распределена, так и сохранена в регистрах: тогда эта переменная считается «разделенной». [5] Доступ к оперативной памяти происходит значительно медленнее, чем доступ к регистрам. [6] и поэтому скомпилированная программа работает медленнее. Поэтому оптимизирующий компилятор стремится назначить регистрам как можно больше переменных. Высокое « давление регистра » — это технический термин, который означает, что необходимо больше разливов и перезагрузок; это определено Braun et al. как «количество одновременно действующих переменных в инструкции». [7]

Кроме того, некоторые компьютерные конструкции кэшируют часто используемые регистры. Таким образом, программы можно дополнительно оптимизировать, назначив один и тот же регистр источнику и назначению move инструктаж по возможности. Это особенно важно, если компилятор использует промежуточное представление , например статическую форму с одним присваиванием (SSA). В частности, когда SSA не полностью оптимизирована, она может искусственно генерировать дополнительные move инструкции.

Компоненты распределения регистров

[ редактировать ]

Таким образом, распределение регистров заключается в выборе места хранения переменных во время выполнения, т. е. внутри или снаружи регистров. Если переменная должна храниться в регистрах, распределитель должен определить, в каком регистре(ах) будет храниться эта переменная. В конце концов, еще одна задача состоит в том, чтобы определить продолжительность, в течение которой переменная должна оставаться в одном и том же месте.

Распределитель регистров, независимо от выбранной стратегии распределения, может полагаться на ряд основных действий для решения этих проблем. Эти действия можно объединить в несколько категорий: [8]

Переместить вставку
Это действие состоит в увеличении количества инструкций перемещения между регистрами, т. е. заставляет переменную жить в разных регистрах в течение ее жизни вместо одного. Это происходит при использовании метода разделения живого диапазона.
Разлив
Это действие заключается в сохранении переменной в памяти вместо регистров. [9]
Назначение
Это действие заключается в присвоении регистра переменной. [10]
Объединение
Это действие заключается в ограничении количества перемещений между регистрами, тем самым ограничивая общее количество инструкций. Например, идентифицируя переменную, живущую в разных методах, и сохраняя ее в одном регистре в течение всего ее существования. [9]

Многие подходы к распределению регистров оптимизируются для одной или нескольких конкретных категорий действий.

Регистры Intel 386

Общие проблемы, возникающие при распределении регистров

[ редактировать ]

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

Псевдонимы
В некоторых архитектурах присвоение значения одному регистру может повлиять на значение другого: это называется псевдонимами. Например, архитектура x86 имеет четыре 32-битных регистра общего назначения, которые также можно использовать как 16-битные или 8-битные регистры. [11] В этом случае присвоение 32-битного значения регистру eax повлияет на значение регистра al.
Предварительное окрашивание
Эта проблема представляет собой попытку принудительного присвоения некоторых переменных определенным регистрам. Например, в PowerPC соглашениях о вызовах параметры обычно передаются в R3–R10, а возвращаемое значение передается в R3. [12]
NP-Проблема
Чайтин и др. показал, что распределение регистров является NP-полной задачей. Они сводят проблему раскраски графа к проблеме распределения регистров, показывая, что для произвольного графа можно построить программу, в которой распределение регистров для программы (где регистры представляют узлы, а машинные регистры представляют доступные цвета) будет раскраской для оригинальный график. Поскольку раскраска графа является NP-сложной задачей, а распределение регистров находится в NP, это доказывает NP-полноту задачи. [13]

Методы распределения регистров

[ редактировать ]

Распределение регистров может происходить в рамках базового блока кода: оно называется «локальным» и впервые упоминается Хорвитцем и др. [14] Поскольку базовые блоки не содержат ветвей, процесс выделения считается быстрым, поскольку управление точками слияния графа потока управления при распределении регистров проявляется [ нужны разъяснения ] трудоемкая операция. [15] Однако считается, что этот подход не обеспечивает столь оптимизированный код, как «глобальный» подход, который работает со всей единицей компиляции (например, методом или процедурой). [16]

Распределение раскраски графа

[ редактировать ]

Раскраска графов является преобладающим подходом к решению проблемы распределения регистров. [17] [18] Впервые это было предложено Chaitin et al. [4] В этом подходе узлы графа представляют собой действующие диапазоны ( переменные , временные значения , виртуальные/символические регистры), которые являются кандидатами на распределение регистров. Края соединяют действующие диапазоны, которые мешают, т. е. активные диапазоны, которые одновременно активны хотя бы в одной точке программы. Распределение регистров тогда сводится к задаче раскраски графа , в которой цвета (регистры) назначаются узлам так, что два узла, соединенные ребром, не получают одинаковый цвет. [19]

С помощью анализа живучести можно построить интерференционный график. Граф интерференции, который представляет собой неориентированный граф , узлами которого являются переменные программы, используется для моделирования того, какие переменные не могут быть помещены в один и тот же регистр. [20]

Основные этапы работы распределителя регистров с раскраской графов в стиле Чайтина: [18]

Распределитель регистров на основе итеративной раскраски графов Чайтина и др.
  1. Перенумеровать : найти информацию о реальном диапазоне в исходной программе.
  2. Построить : построить график интерференции.
  3. Объединение : объединение текущих диапазонов невлияющих переменных, связанных инструкциями копирования.
  4. Стоимость разлива : вычислите стоимость разлива каждой переменной. Это оценивает влияние отображения переменной в память на скорость конечной программы.
  5. Упростить : построить порядок узлов в графе выводов.
  6. Код разгрузки : вставляет инструкции разгрузки, т.е. загружает и сохраняет значения для переключения между регистрами и памятью.
  7. Выберите : назначить регистр каждой переменной.

Недостатки и дальнейшие улучшения

[ редактировать ]

Распределение раскраски графов имеет три основных недостатка. Во-первых, он полагается на раскраску графа, которая является NP-полной задачей , чтобы решить, какие переменные будут выброшены. Нахождение минимального графа раскраски действительно является NP-полной задачей. [21] Во-вторых, если не используется разделение живого диапазона, вытесненные переменные распределяются повсюду: инструкции сохранения вставляются как можно раньше, т. е. сразу после определения переменных; Инструкции загрузки соответственно вставляются поздно, непосредственно перед использованием переменной. В-третьих, переменная, которая не теряется, хранится в одном и том же регистре на протяжении всего своего существования. [22]

С другой стороны, одно имя регистра может встречаться в нескольких классах регистров, где класс представляет собой набор имен регистров, взаимозаменяемых в определенной роли. Тогда несколько имен регистров могут быть псевдонимами одного аппаратного регистра. [23] Наконец, раскраска графа — это агрессивный метод распределения регистров, но он требует больших вычислительных затрат из-за использования интерференционного графа, размер которого в наихудшем случае может быть квадратичен по числу активных диапазонов. [24] Традиционная формулировка распределения регистров с раскраской графов неявно предполагает наличие одного банка непересекающихся регистров общего назначения и не учитывает нестандартные архитектурные особенности, такие как перекрывающиеся пары регистров, регистры специального назначения и несколько банков регистров. [25]

Еще одно усовершенствование подхода к раскраске графов в стиле Чайтина было обнаружено Бриггсом и др.: оно называется консервативным объединением. Это улучшение добавляет критерий для принятия решения о том, когда можно объединить два живых диапазона. Главным образом, помимо требований невмешательства, две переменные могут быть объединены только в том случае, если их слияние не приведет к дальнейшему разливу. Бриггс и др. представляет второе улучшение работ Чайтина - смещенную окраску. Смещенная раскраска пытается назначить один и тот же цвет в раскраске графика живому диапазону, связанному с копированием. [18]

Линейное сканирование

[ редактировать ]

Линейное сканирование — еще один подход к глобальному распределению регистров. Впервые это было предложено Полетто и др. в 1999 году. [26] При таком подходе код не превращается в граф. Вместо этого все переменные сканируются линейно, чтобы определить их динамический диапазон, представленный в виде интервала. После того как действительные диапазоны всех переменных определены, интервалы просматриваются в хронологическом порядке. Хотя этот обход может помочь идентифицировать переменные, чьи живые диапазоны мешают, граф взаимодействий не строится, и переменные распределяются жадным способом. [24]

Мотивацией такого подхода является скорость; не с точки зрения времени выполнения сгенерированного кода, а с точки зрения времени, затраченного на генерацию кода. Обычно стандартные подходы к раскраске графов создают качественный код, но имеют значительные накладные расходы . [27] [28] используемый алгоритм раскраски графов имеет квадратичную стоимость. [29] Благодаря этой функции линейное сканирование — это подход, используемый в настоящее время в нескольких JIT-компиляторах, таких как клиентский компилятор Hotspot , V8 , Jikes RVM , [5] и среда выполнения Android (ART). [30] Компилятор сервера Hotspot использует раскраску графов для повышения качества кода. [31]

Псевдокод

[ редактировать ]

Это описывает алгоритм, впервые предложенный Полетто и др., [32] где:

  • R — количество доступных регистров.
  • активным является список, отсортированный по возрастанию конечной точки, живых интервалов, перекрывающих текущую точку и помещенных в регистры.
LinearScanRegisterAllocation
    active ← {}
    for each live interval i, in order of increasing start point do
        ExpireOldIntervals(i)
        if length(active) = R then
            SpillAtInterval(i)
        else
            register[i] ← a register removed from pool of free registers
            add i to active, sorted by increasing end point

ExpireOldIntervals(i)
    for each interval j in active, in order of increasing end point do
        if endpoint[j] ≥ startpoint[i] then
            return 
        remove j from active
        add register[j] to pool of free registers

SpillAtInterval(i)
    spill ← last interval in active
    if endpoint[spill] > endpoint[i] then
        register[i] ← register[spill]
        location[spill] ← new stack location
        remove spill from active
        add i to active, sorted by increasing end point
    else
        location[i] ← new stack location

Недостатки и дальнейшие улучшения

[ редактировать ]

Однако линейное сканирование имеет два существенных недостатка. Во-первых, из-за своего жадного аспекта он не учитывает дыры времени жизни, то есть «диапазоны, в которых значение переменной не требуется». [33] [34] Кроме того, удаленная переменная останется удаленной на протяжении всего своего существования.

Меньшая дальность действия с подходом SSA

Многие другие исследовательские работы развивали алгоритм линейного сканирования Полетто. Трауб и др., например, предложили алгоритм, называемый бинпаковкой второго шанса, направленный на генерацию кода более высокого качества. [35] [36] В этом подходе распределенные переменные получают возможность быть сохраненными позже в регистре с использованием эвристики, отличной от той, которая используется в стандартном алгоритме линейного сканирования. Вместо использования живых интервалов алгоритм опирается на действующие диапазоны, а это означает, что если необходимо расширить диапазон, нет необходимости распространять все остальные диапазоны, соответствующие этой переменной.

Распределение линейного сканирования также было адаптировано для использования преимуществ формы SSA : свойства этого промежуточного представления упрощают алгоритм распределения и позволяют напрямую вычислять дыры за время жизни. [37] Во-первых, сокращается время, затрачиваемое на анализ графов потоков данных, направленный на построение интервалов времени жизни, именно потому, что переменные уникальны. [38] Следовательно, это приводит к более коротким живым интервалам, поскольку каждое новое назначение соответствует новому живому интервалу. [39] [40] Чтобы избежать моделирования интервалов и дыр в жизнеспособности, Роджерс продемонстрировал упрощение, называемое наборами будущих активных действий, которое успешно удалило интервалы для 80% инструкций. [41]

Рематериализация

[ редактировать ]

Объединение

[ редактировать ]

В контексте распределения регистров объединение — это процесс слияния операций перемещения переменных между переменными путем размещения этих двух переменных в одном и том же месте. Операция объединения происходит после построения интерференционного графа. После объединения двух узлов они должны получить одинаковый цвет и быть помещены в один и тот же регистр, поскольку операция копирования становится ненужной. [42]

Выполнение объединения может иметь как положительное, так и отрицательное влияние на раскраску интерференционного графа. [9] Например, одно негативное влияние, которое объединение может оказать на раскрашиваемость вывода графа, заключается в том, что два узла объединяются, поскольку результирующий узел будет иметь объединение ребер объединяемых узлов. [9] Положительное влияние объединения на раскрашиваемость графа вывода заключается, например, в том, что когда узел мешает слиянию обоих узлов, степень узла уменьшается на единицу, что приводит к улучшению общей раскрашиваемости интерференционного графа. [43]

Доступно несколько эвристик объединения: [44]

Агрессивное объединение
Впервые он был представлен оригинальным распределителем регистров Chaitin. Эта эвристика направлена ​​на объединение любых немешающих узлов, связанных с копированием. [45] С точки зрения исключения копирования эта эвристика дает наилучшие результаты. [46] С другой стороны, агрессивное объединение может повлиять на раскрашиваемость графика вывода. [43]
Консервативное объединение
в основном он использует ту же эвристику, что и агрессивное объединение, но объединяет ходы тогда и только тогда, когда это не ставит под угрозу раскрашиваемость интерференционного графа. [47]
Итерированное объединение
он удаляет один конкретный ход за раз, сохраняя при этом раскраску графа. [48]
Оптимистическое объединение
он основан на агрессивном слиянии, но если раскрашиваемость графа вывода нарушена, то он отказывается от как можно меньшего количества ходов. [49]

Смешанные подходы

[ редактировать ]

Гибридное распределение

[ редактировать ]

Некоторые другие подходы к распределению регистров не ограничиваются одним методом оптимизации использования регистров. Кавазос и др., например, предложили решение, в котором можно использовать как алгоритмы линейного сканирования, так и алгоритмы раскраски графов. [50] В этом подходе выбор между тем или иным решением определяется динамически: сначала алгоритм машинного обучения используется «оффлайн», то есть не во время выполнения, для построения эвристической функции, которая определяет, какой алгоритм распределения необходимо использовать. . Эвристическая функция затем используется во время выполнения; в зависимости от поведения кода распределитель может затем выбрать один из двух доступных алгоритмов. [51]

Распределение регистров трассировки — это недавний подход, разработанный Eisl et al. [3] [5] Этот метод обрабатывает распределение локально: он опирается на данные динамического профилирования , чтобы определить, какие ветви будут наиболее часто использоваться в данном графе потока управления. Затем он выводит набор «трасс» (т.е. сегментов кода), в которых точка слияния игнорируется в пользу наиболее используемой ветки. Затем каждая трасса независимо обрабатывается распределителем. Этот подход можно считать гибридным, поскольку между разными трассами можно использовать разные алгоритмы распределения регистров. [52]

Разделенное распределение

[ редактировать ]

Разделенное распределение — это еще один метод распределения регистров, который сочетает в себе различные подходы, обычно считающиеся противоположными. Например, метод гибридного распределения можно рассматривать как метод разделения, поскольку первый этап построения эвристики выполняется в автономном режиме, а использование эвристики выполняется в режиме онлайн. [24] Таким же образом Б. Диуф и др. предложил метод распределения, основанный как на автономном, так и на онлайновом поведении, а именно статическую и динамическую компиляцию. [53] [54] На автономном этапе сначала собирается оптимальный набор разливов с помощью целочисленного линейного программирования . Затем текущие диапазоны аннотируются с помощью compressAnnotation алгоритм, который опирается на ранее определенный оптимальный набор разливов. Распределение регистров выполняется впоследствии на онлайн-этапе на основе данных, собранных на автономном этапе. [55]

В 2007 году Буше и др. предложил также разделить распределение регистров на разные этапы: один этап предназначен для распределения, а другой — для раскрашивания и объединения. [56]

Сравнение различных техник

[ редактировать ]

Для оценки эффективности одного метода распределения регистров по сравнению с другим использовалось несколько показателей. При распределении регистров обычно приходится иметь дело с компромиссом между качеством кода, т. е. кодом, который выполняется быстро, и накладными расходами на анализ, т. е. временем, затрачиваемым на анализ исходного кода для генерации кода с оптимизированным распределением регистров. С этой точки зрения время выполнения сгенерированного кода и время, затраченное на анализ жизнеспособности, являются важными показателями для сравнения различных методов. [57]

После того как соответствующие метрики выбраны, код, к которому будут применяться метрики, должен быть доступен и соответствовать проблеме, либо отражая поведение реального приложения, либо будучи релевантным конкретной проблеме, которую хочет решить алгоритм. В более поздних статьях о распределении регистров особенно используется набор тестов Dacapo. [58]

См. также

[ редактировать ]
  • Число Стралера — минимальное количество регистров, необходимое для вычисления дерева выражений. [59]
  • Регистр (ключевое слово) — подсказка в C и C++ для размещения переменной в регистре.
  • Алгоритм Сетхи-Ульмана — алгоритм, обеспечивающий наиболее эффективное распределение регистров для вычисления одного выражения, когда количество регистров, необходимых для вычисления выражения, превышает количество доступных регистров.
  1. ^ Дитцель и Маклеллан 1982 , стр. 48.
  2. ^ Рунесон и Нюстрем 2003 , стр. 242.
  3. ^ Jump up to: а б Эйсл и др. 2016 , с. 14:1.
  4. ^ Jump up to: а б Чайтин и др. 1981 , с. 47.
  5. ^ Jump up to: а б с Эйсл и др. 2016 , с. 1.
  6. ^ «Сравнение задержек в компьютере/сети» . blog.morizyun.com. 6 января 2018 года . Проверено 8 января 2019 г.
  7. ^ Браун и Хак 2009 , с. 174.
  8. ^ Коес и Гольдштейн 2009 , с. 21.
  9. ^ Jump up to: а б с д Буше, Дарте и Растелло 2007b , с. 103.
  10. ^ Коломбет, Бранднер и Дарте 2011 , с. 26.
  11. ^ «Руководство разработчика программного обеспечения для архитектур Intel® 64 и IA-32, раздел 3.4.1» (PDF) . Интел. Май 2019 г. Архивировано из оригинала (PDF) 25 мая 2019 г.
  12. ^ «Соглашения о вызове 32-битных функций PowerPC» .
  13. ^ Бушез, Дарте и Растелло 2006 , с. 4.
  14. ^ Хорвиц и др. 1966 , с. 43.
  15. ^ Фарах и Либераторе 1998 , с. 566.
  16. ^ Эйсл и др. 2017 , с. 92.
  17. ^ Эйсль, Леопольдседер и Мессенбёк 2018 , стр. 1.
  18. ^ Jump up to: а б с Бриггс, Купер и Торчон 1992 , с. 316.
  19. ^ Полетто и Саркар 1999 , с. 896.
  20. ^ Рунесон и Нюстрем 2003 , стр. 241.
  21. ^ Книга 1975 , с. 618–619.
  22. ^ Коломбет, Бранднер и Дарте 2011 , с. 1.
  23. ^ Смит, Рэмси и Холлоуэй 2004 , стр. 277.
  24. ^ Jump up to: а б с Кавасос, Мосс и О'Бойл, 2006 , с. 124.
  25. ^ Рунесон и Нюстрем 2003 , стр. 240.
  26. ^ Полетто и Саркар 1999 , с. 895.
  27. ^ Полетто и Саркар 1999 , с. 902.
  28. ^ Виммер и Мессенбёк 2005 , с. 132.
  29. ^ Йоханссон и Сагонас 2002 , стр. 102.
  30. ^ Эволюция ART – Google I/O 2016 . Google . 25 мая 2016 г. Событие происходит в 3:47.
  31. ^ Палечный, Vick & Click 2001 , с. 1.
  32. ^ Полетто и Саркар 1999 , с. 899.
  33. ^ Эйсл и др. 2016 , с. 2.
  34. ^ Трауб, Холлоуэй и Смит 1998 , стр. 143.
  35. ^ Трауб, Холлоуэй и Смит 1998 , стр. 141.
  36. ^ Полетто и Саркар 1999 , с. 897.
  37. ^ Виммер и Франц 2010 , с. 170.
  38. ^ Мессенбёк и Пфайффер 2002 , с. 234.
  39. ^ Мессенбёк и Пфайффер 2002 , с. 233.
  40. ^ Мессенбёк и Пфайффер 2002 , с. 229.
  41. ^ Роджерс 2020 .
  42. ^ Чайтин 1982 , с. 90.
  43. ^ Jump up to: а б Ан и Пэк 2009 , с. 7.
  44. ^ Парк и Луна 2004 , с. 736.
  45. ^ Чайтин 1982 , с. 99.
  46. ^ Парк и Луна 2004 , с. 738.
  47. ^ Бриггс, Купер и Торчон 1994 , стр. 433.
  48. ^ Джордж и Аппель 1996 , с. 212.
  49. ^ Парк и Луна 2004 , с. 741.
  50. ^ Эйсл и др. 2017 , с. 11.
  51. ^ Кавазос, Мосс и О'Бойл 2006 , с. 124-127.
  52. ^ Эйсл и др. 2016 , с. 4.
  53. ^ Диуф и др. 2010 , с. 66.
  54. ^ Коэн и Роху 2010 , с. 1.
  55. ^ Диуф и др. 2010 , с. 72.
  56. ^ Бушез, Дарте и Растелло 2007a , с. 1.
  57. ^ Полетто и Саркар 1999 , с. 901-910.
  58. ^ Блэкберн и др. 2006 , с. 169.
  59. ^ Флажоле, Рауль и Вийемен 1979 .

Источники

[ редактировать ]
[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 812f74ac017de48ee246824cac4e05f3__1721623080
URL1:https://arc.ask3.ru/arc/aa/81/f3/812f74ac017de48ee246824cac4e05f3.html
Заголовок, (Title) документа по адресу, URL1:
Register allocation - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)