stringtranslate.com

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

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

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

Контекст

Принцип


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

Не все переменные используются (или «живут») одновременно, поэтому в течение жизненного цикла программы данный регистр может использоваться для хранения разных переменных. Однако две переменные, используемые одновременно, не могут быть назначены одному регистру без повреждения одной из переменных. Если регистров недостаточно для хранения всех переменных, некоторые переменные могут быть перемещены в ОЗУ и из него . Этот процесс называется «выгрузкой» регистров. [4] В течение жизненного цикла программы переменная может быть как выгружена, так и сохранена в регистрах: эта переменная затем считается «разделенной». [5] Доступ к ОЗУ значительно медленнее, чем доступ к регистрам [6], и поэтому скомпилированная программа работает медленнее. Поэтому оптимизирующий компилятор стремится назначить как можно больше переменных регистрам. Высокое « давление регистра » — это технический термин, который означает, что требуется больше выгрузок и перезагрузок; Браун и др. определяют его как «количество одновременно живых переменных в инструкции». [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] Впервые он был предложен Чайтином и др. [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 , в порядке возрастания начальной точки, выполните ИстекаютСтарыеИнтервалы(i) если длина(активная) = R тогда SpillAtInterval(i) еще register[i] ← регистр удален из пула свободных регистров добавить i к активному, отсортировать по возрастанию конечной точкиExpireOldIntervals(i)  для каждого интервала j  в active, в порядке возрастания конечной точки, выполнить  if endpoint[j] ≥ startpoint[i], затем  вернуть remove j из active добавить регистр[j] в пул свободных регистровSpillAtInterval(i) разлив ← последний интервал в активном если конечная точка[spill] > конечная точка[i] , то регистр[i] ← регистр[пролив] местоположение[spill] ← новое местоположение стека удалить разлив из активного добавить i к активному, отсортировать по возрастанию конечной точки иначе location[i] ← новое местоположение стека

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

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

Более короткие диапазоны действия с подходом SSA

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

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

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

Слияние

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

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

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

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

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

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

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

Распределение регистров трассировки — это недавний подход, разработанный Эйслом и др. [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 г. Получено 08.01.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) . Intel. Май 2019 г. Архивировано из оригинала (PDF) 25.05.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. ^ Эволюция ИСКУССТВА - Google I/O 2016. Google . 25 мая 2016 г. Событие происходит в 3:47.
  31. ^ Палечны, Вик и Клик 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. ^ ab Ahn & Paek 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.

Источники

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