stringtranslate.com

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

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

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

Контекст

Принцип


Во многих языках программирования программист может использовать любое количество переменных . Компьютер может быстро читать и записывать регистры ЦП , поэтому компьютерная программа работает быстрее , когда в регистрах ЦП может находиться больше переменных. [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 Runtime (ART). [30] Компилятор сервера Hotspot использует раскраску графов для повышения качества кода. [31]

Псевдокод

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

LinearScanRegisterAllocation активный ← {} для каждого живого интервала i в порядке возрастания начальной точки выполните ExpireOldIntervals(i) если длина (активная) = R , то РазливАтИнтервал(i) еще Register[i] ← регистр, удаленный из пула свободных регистров добавить i в активный, отсортировать по возрастанию конечной точкиExpireOldIntervals(i)  для каждого интервала j  в активном режиме, в порядке возрастания конечной точки выполните,  если конечная точка[j] ≥ начальная точка[i], затем  вернитесь и удалите j из активного добавить регистр[j] в пул свободных регистровРазливАтИнтервал(i) пролив ← последний интервал активности если конечная точка[разлив] > конечная точка[i], то зарегистрироваться[i] ← зарегистрироваться[пролить] location[разлив] ← новое место стека удалить разлив из активного добавить i в активный, отсортировать по возрастанию конечной точки else location[i] ← новое местоположение стека

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

Однако линейное сканирование имеет два основных недостатка. Во-первых, из-за своего жадного аспекта он не учитывает дыры времени жизни, то есть «диапазоны, в которых значение переменной не требуется». [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]

Смотрите также

Рекомендации

  1. ^ Дитцель и Маклеллан 1982, с. 48.
  2. ^ Рунесон и Нистрем 2003, стр. 242.
  3. ^ аб Эйсл и др. 2016, с. 14:1.
  4. ^ аб Чайтин и др. 1981, с. 47.
  5. ^ abc Eisl et al. 2016, с. 1.
  6. ^ «Цифры сравнения задержек в компьютере/сети» . blog.morizyun.com. 6 января 2018 года . Проверено 8 января 2019 г.
  7. ^ Браун и Хак 2009, с. 174.
  8. ^ Коес и Гольдштейн 2009, с. 21.
  9. ^ abcd Bouchez, Darte & Rastello 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. ^ abc Бриггс, Купер и Торчон 1992, стр. 316.
  19. ^ Полетто и Саркар 1999, с. 896.
  20. ^ Рунесон и Нистрем 2003, стр. 241.
  21. ^ Книга 1975, с. 618–619.
  22. ^ Коломбет, Бранднер и Дарте 2011, с. 1.
  23. ^ Смит, Рэмси и Холлоуэй 2004, с. 277.
  24. ^ abc Кавазос, Мосс и О'Бойл 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. ^ аб Ан и Пэк 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.

Источники

Внешние ссылки