Размещение регистров - Register allocation

В оптимизация компилятора, распределение регистров это процесс назначения большого количества целевой программы переменные на небольшое количество ЦПУ регистры.

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

Контекст

Смотрите также: Компилятор и Устный переводчик

Принцип

Смотрите также: Хранение компьютерных данных и Иерархия памяти
Различное количество скалярных регистров в наиболее распространенных архитектурах
Архитектура32 бит64 бит
РУКА1531
Intel x86816
MIPS3232
RISC-V16/3232
SPARC3131


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

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

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

Компоненты размещения регистров

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

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

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

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

Регистры Intel 386

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

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

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

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

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

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

Смотрите также: Раскраска графика

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

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

Принцип

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

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

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

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

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

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

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

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

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

Псевдокод

Это описывает алгоритм, впервые предложенный Poletto et al.[30]

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

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

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

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

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

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

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

Смотрите также: Рематериализация

Проблема оптимального размещения регистров является NP-полной. Как следствие, компиляторы используют эвристические методы для приближенного решения.

Чайтин и др. обсудить несколько идей по повышению качества кода утечки. Они указывают на то, что определенные значения могут быть пересчитаны в одной инструкции и что требуемый операнд всегда будет доступен для вычисления. Они называют эти исключительные значения «никогда не уничтожаемыми» и отмечают, что такие значения следует пересчитывать, а не проливать и перезагружать. Они также отмечают, что несвязанная копия никогда не уничтоженного значения может быть удалена путем пересчета ее непосредственно в желаемый регистр.[40]

Эти методы называются рематериализацией. На практике возможности рематериализации включают:

  • немедленная загрузка целочисленных констант и, на некоторых машинах, констант с плавающей запятой,
  • вычисление постоянного смещения от указателя кадра или области статических данных, и
  • загрузка нелокальных указателей кадров с дисплея.[40]

Бриггс и Эл расширяют работу Chaitin, чтобы воспользоваться возможностями рематериализации для сложных, многозначных живых диапазонов. Они обнаружили, что каждое значение должно быть помечено достаточным количеством информации, чтобы распределитель мог его правильно обработать. Подход Бриггса заключается в следующем: сначала разделите каждый активный диапазон на его значения компонентов, затем распространите теги рематериализации на каждое значение и сформируйте новые живые диапазоны из связанных значений с идентичными тегами.[40]

Коалесцирующий

Смотрите также: Объединение (информатика)

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

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

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

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

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

Гибридное размещение

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

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

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

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

В 2007 году Бушез и др. Также предложили разделить регистр на разные этапы, при этом один этап посвящен разливу, а другой - окраске и объединению.[55]

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

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

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

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

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

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

Источники

  • Ан, Минвук; Пэк, Юнхын (2009). «Методы объединения регистров для архитектуры гетерогенных регистров с отсеиванием копий». Транзакции ACM во встроенных вычислительных системах. 8 (2): 1–37. CiteSeerX  10.1.1.615.5767. Дои:10.1145/1457255.1457263. ISSN  1539-9087. S2CID  14143277.
  • Ахо, Альфред V .; Lam, Monica S .; Сетхи, Рави; Ульман, Джеффри Д. (2006). Компиляторы: принципы, методы и инструменты (2-е изд.). Addison-Wesley Longman Publishing Co., Inc. ISBN  978-0321486813.
  • Аппель, Эндрю В .; Джордж, Лал (2001). «Оптимальное разливание для машин CISC с несколькими регистрами». Материалы конференции ACM SIGPLAN 2001 по проектированию и реализации языков программирования - PLDI '01. С. 243–253. CiteSeerX  10.1.1.37.8978. Дои:10.1145/378795.378854. ISBN  978-1581134148. S2CID  1380545.
  • Барик, Раджкишор; Гротхофф, Кристиан; Гупта, Рахул; Пандит, Винаяка; Удупа, Рагхавендра (2007). «Оптимальное побитовое размещение регистров с использованием целочисленного линейного программирования». Языки и компиляторы для параллельных вычислений. Конспект лекций по информатике. 4382. С. 267–282. CiteSeerX  10.1.1.75.6911. Дои:10.1007/978-3-540-72521-3_20. ISBN  978-3-540-72520-6.
  • Бергнер, Питер; Даль, Питер; Энгебретсен, Дэвид; О'Киф, Мэтью (1997). «Минимизация сброса кода за счет разлива интерференционной области». Материалы конференции ACM SIGPLAN 1997 по разработке и реализации языков программирования - PLDI '97. С. 287–295. Дои:10.1145/258915.258941. ISBN  978-0897919074. S2CID  16952747.
  • Блэкберн, Стивен М .; Guyer, Samuel Z .; Хирзель, Мартин; Хоскинг, Антоний; Прыгай, Мария; Ли, Хан; Элиот, Дж .; Moss, B .; Пхансалкар, Аашиш; Стефанович, Дарко; ВанДрунен, Томас; Гарнер, Робин; фон Динклаге, Даниэль; Видерманн, Бен; Хоффманн, Крис; Khang, Asjad M .; МакКинли, Кэтрин С .; Бенцур, Ротем; Диван, Амер; Файнберг, Даниэль; Фрэмптон, Дэниел (2006). «Тесты DaCapo». Материалы 21-й ежегодной конференции ACM SIGPLAN по системам, языкам и приложениям объектно-ориентированного программирования - OOPSLA '06. п. 169. Дои:10.1145/1167473.1167488. ISBN  978-1595933485. S2CID  9255051.
  • Книга, Рональд В. (декабрь 1975 г.). Карп Ричард М. Сводимость среди комбинаторных задач. Сложность компьютерных вычислений, Труды симпозиума по сложности компьютерных вычислений, состоявшегося 20-22 марта 1972 года в Центре Томаса Дж. Уотсона IBM, Йорктаун-Хайтс, Нью-Йорк, под редакцией Миллера Рэймонда Э. и Тэтчер Джеймс У., Пленум Пресс, Нью-Йорк и Лондон, 1972, стр. 85–103 ". Журнал символической логики. 40 (4): 618–619. Дои:10.2307/2271828. ISSN  0022-4812. JSTOR  2271828.
  • Буше, Флоран; Дарте, Ален; Растелло, Фабрис (2006). «Распределение регистров: что действительно доказывает NP-полнота Чейтина и др.? Или пересмотр распределения регистров: почему и как». Распределение регистров: что доказывает NP-полнота Chaitin et al. действительно доказать?. Конспект лекций по информатике. 4382. С. 2–14. Дои:10.1007/978-3-540-72521-3_21. ISBN  978-3-540-72520-6.
  • Буше, Флоран; Дарте, Ален; Растелло, Фабрис (2007). «О сложности объединения регистров». Международный симпозиум по генерации кода и оптимизации (CGO'07). С. 102–114. CiteSeerX  10.1.1.101.6801. Дои:10.1109 / CGO.2007.26. ISBN  978-0-7695-2764-2. S2CID  7683867.
  • Буше, Флоран; Дарте, Ален; Растелло, Фабрис (2007). «О сложности разлива повсюду по форме SSA». Уведомления ACM SIGPLAN. 42 (7): 103. arXiv:0710.3642. Дои:10.1145/1273444.1254782. ISSN  0362-1340.
  • Браун, Матиас; Хак, Себастьян (2009). «Разлив регистров и разделение живого диапазона для программ SSA-формы». Конструкция компилятора. Конспект лекций по информатике. 5501. С. 174–189. CiteSeerX  10.1.1.219.5318. Дои:10.1007/978-3-642-00722-4_13. ISBN  978-3-642-00721-7. ISSN  0302-9743.
  • Бриггс, Престон; Купер, Кейт Д.; Торчон, Линда (1992). «Рематериализация». Уведомления ACM SIGPLAN. 27 (7): 311–321. Дои:10.1145/143103.143143. ISSN  0362-1340.
  • Бриггс, Престон; Купер, Кейт Д.; Торцон, Линда (1994). «Улучшения в размещении регистров раскраски графов». Транзакции ACM по языкам и системам программирования. 16 (3): 428–455. CiteSeerX  10.1.1.23.253. Дои:10.1145/177492.177575. ISSN  0164-0925. S2CID  6571479.
  • Кавасос, Джон; Moss, J. Eliot B .; О’Бойл, Майкл Ф. П. (2006). «Гибридные оптимизации: какой алгоритм оптимизации использовать?». Конструкция компилятора. Конспект лекций по информатике. 3923. С. 124–138. Дои:10.1007/11688839_12. ISBN  978-3-540-33050-9. ISSN  0302-9743.
  • Чайтин, Грегори Дж .; Auslander, Marc A .; Chandra, Ashok K .; Кок, Джон; Хопкинс, Мартин Э .; Маркштейн, Питер В. (1981). «Выделение регистров раскраской». Компьютерные языки. 6 (1): 47–57. Дои:10.1016/0096-0551(81)90048-5. ISSN  0096-0551.
  • Чайтин, Г. Дж. (1982). «Размещение и разлив регистров с помощью раскраски графиков». Материалы симпозиума SIGPLAN 1982 г. по созданию компиляторов - SIGPLAN '82. С. 98–101. Дои:10.1145/800230.806984. ISBN  978-0897910743. S2CID  16872867.
  • Чен, Вэй-Ю; Луэ, Гуэй-Юань; Ашар, Пратик; Чен, Кайю; Ченг, Буки (2018). «Распределение регистров для процессорной графики Intel». Материалы Международного симпозиума по генерации и оптимизации кода 2018 года - CGO 2018. С. 352–364. Дои:10.1145/3168806. ISBN  9781450356176. S2CID  3367270.
  • Коэн, Альберт; Роху, Эрвен (2010). «Виртуализация процессора и раздельная компиляция для гетерогенных многоядерных встроенных систем». Материалы 47-й конференции по автоматизации проектирования - DAC '10. п. 102. CiteSeerX  10.1.1.470.9701. Дои:10.1145/1837274.1837303. ISBN  9781450300025. S2CID  14314078.
  • Коломбе, Квентин; Бранднер, Флориан; Дарте, Ален (2011). «Изучение оптимального розлива в свете SSA». Материалы 14-й международной конференции по компиляторам, архитектурам и синтезу для встраиваемых систем - CASES '11. п. 25. Дои:10.1145/2038698.2038706. ISBN  9781450307130. S2CID  8296742.
  • Диуф, Бубакар; Коэн, Альберт; Растелло, Фабрис; Кавасос, Джон (2010). «Разделение регистров: линейная сложность без штрафа за производительность». Высокопроизводительные встроенные архитектуры и компиляторы. Конспект лекций по информатике. 5952. С. 66–80. CiteSeerX  10.1.1.229.3988. Дои:10.1007/978-3-642-11515-8_7. ISBN  978-3-642-11514-1. ISSN  0302-9743.
  • Ditzel, David R .; Маклеллан, Х. Р. (1982). «Выдача реестра бесплатно». Материалы первого международного симпозиума по архитектурной поддержке языков программирования и операционных систем - ASPLOS-I. С. 48–56. Дои:10.1145/800050.801825. ISBN  978-0897910668. S2CID  2812379.
  • Эйсл, Йозеф; Гриммер, Матиас; Саймон, Дуг; Вюртингер, Томас; Mössenböck, Hanspeter (2016). «Распределение регистров на основе трассировки в JIT-компиляторе». Труды 13-й Международной конференции по принципам и практике программирования на платформе Java: виртуальные машины, языки и инструменты - PPPJ '16. С. 1–11. Дои:10.1145/2972206.2972211. ISBN  9781450341356. S2CID  31845919.
  • Эйсл, Йозеф; Марр, Стефан; Вюртингер, Томас; Mössenböck, Hanspeter (2017). «Политики распределения регистров трассировки» (PDF). Материалы 14-й Международной конференции по управляемым языкам и средам выполнения - Man Lang 2017 (PDF). С. 92–104. Дои:10.1145/3132190.3132209. ISBN  9781450353403. S2CID  1195601.
  • Эйсл, Йозеф; Леопольдседер, Дэвид; Mössenböck, Hanspeter (2018). «Распределение регистров параллельной трассировки». Труды 15-й Международной конференции по управляемым языкам и средам выполнения - Man Lang '18. С. 1–7. Дои:10.1145/3237009.3237010. ISBN  9781450364249. S2CID  52137887.
  • Коэс, Дэвид Райан; Гольдштейн, Сет Копен (2009). "Распределение регистров деконструировано". Написано в Ницце, Франция. Материалы 12-го международного семинара по программному обеспечению и компиляторам для встраиваемых систем. SCOPES '09. Нью-Йорк, Нью-Йорк, США: ACM. С. 21–30. ISBN  978-1-60558-696-0.
  • Фарах, Мартин; Либераторе, Винченцо (1998). «О размещении в местном регистре». Написано в Сан-Франциско, Калифорния, США. Материалы девятого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам. SODA '98. Филадельфия, Пенсильвания, США: Общество промышленной и прикладной математики. стр.564–573. ISBN  0-89871-410-9.
  • Флажолет, П.; Raoult, J.C .; Вюйлемен, Дж. (1979), «Количество регистров, необходимых для вычисления арифметических выражений», Теоретическая информатика, 9 (1): 99–125, Дои:10.1016/0304-3975(79)90009-4
  • Джордж, Лал; Аппель, Эндрю В. (1996). «Итерированное слияние регистров». Транзакции ACM по языкам и системам программирования. 18 (3): 300–324. Дои:10.1145/229542.229546. ISSN  0164-0925. S2CID  12281734.
  • Horwitz, L.P .; Karp, R.M .; Miller, R.E .; Виноград, С. (1966). «Размещение индексного регистра». Журнал ACM. 13 (1): 43–61. Дои:10.1145/321312.321317. ISSN  0004-5411. S2CID  14560597.
  • Йоханссон, Эрик; Сагонас, Константинос (2002). «Размещение регистров линейного сканирования в высокопроизводительном компиляторе Erlang». Практические аспекты декларативных языков. Конспект лекций по информатике. 2257. С. 101–119. Дои:10.1007/3-540-45587-6_8. ISBN  978-3-540-43092-6. ISSN  0302-9743.
  • Курдахи, Ф. Дж .; Паркер, А. С. (1987). "REAL: программа для размещения регистраторов". Материалы 24-й конференции ACM / IEEE о конференции по автоматизации проектирования - DAC '87. С. 210–215. Дои:10.1145/37888.37920. ISBN  978-0818607813. S2CID  17598675.
  • Mössenböck, Hanspeter; Пфайффер, Майкл (2002). «Распределение регистров линейного сканирования в контексте ограничений формы SSA и регистров». Конструкция компилятора. Конспект лекций по информатике. 2304. С. 229–246. Дои:10.1007/3-540-45937-5_17. ISBN  978-3-540-43369-9. ISSN  0302-9743.
  • Никерсон, Брайан Р. (1990). «Распределение регистров раскраски графиков для процессоров с многорегистровыми операндами». Уведомления ACM SIGPLAN. 25 (6): 40–52. Дои:10.1145/93548.93552. ISSN  0362-1340.
  • Пак, Джинпио; Луна, Су-Мук (2004). «Оптимистическое слияние регистров». Транзакции ACM по языкам и системам программирования. 26 (4): 735–765. CiteSeerX  10.1.1.33.9438. Дои:10.1145/1011508.1011512. ISSN  0164-0925. S2CID  15969885.
  • Полетто, Массимилиано; Саркар, Вивек (1999). «Размещение регистров линейной развертки». Транзакции ACM по языкам и системам программирования. 21 (5): 895–913. CiteSeerX  10.1.1.27.2462. Дои:10.1145/330249.330250. ISSN  0164-0925. S2CID  18180752.
  • Роджерс, Ян (2020). «Эффективное размещение глобального реестра». arXiv:2011.05608 [cs.PL ].
  • Рунсон, Йохан; Нистрем, Свен-Олоф (2003). «Перенастраиваемое распределение регистров раскраски графиков для нестандартных архитектур». Программное обеспечение и компиляторы для встраиваемых систем. Конспект лекций по информатике. 2826. С. 240–254. CiteSeerX  10.1.1.6.6186. Дои:10.1007/978-3-540-39920-9_17. ISBN  978-3-540-20145-8. ISSN  0302-9743.
  • Смит, Майкл Д .; Рэмси, Норман; Холлоуэй, Гленн (2004). «Обобщенный алгоритм выделения регистров раскраски графов». Уведомления ACM SIGPLAN. 39 (6): 277. CiteSeerX  10.1.1.71.9532. Дои:10.1145/996893.996875. ISSN  0362-1340.
  • Трауб, Омри; Холлоуэй, Гленн; Смит, Майкл Д. (1998). «Качество и скорость в размещении регистров линейного сканирования». Уведомления ACM SIGPLAN. 33 (5): 142–151. CiteSeerX  10.1.1.52.8730. Дои:10.1145/277652.277714. ISSN  0362-1340.
  • Виммер, Кристиан; Mössenböck, Hanspeter (2005). «Оптимизированное разделение интервалов в распределителе регистров линейного сканирования». Материалы 1-й международной конференции ACM / USENIX по виртуальным средам выполнения - VEE '05. п. 132. CiteSeerX  10.1.1.394.4054. Дои:10.1145/1064979.1064998. ISBN  978-1595930477. S2CID  494490.
  • Виммер, Кристиан; Франц, Майкл (2010). «Размещение регистров линейной развертки на бланке SSA». Материалы 8-го ежегодного международного симпозиума IEEE / ACM по генерации и оптимизации кода - CGO '10. п. 170. CiteSeerX  10.1.1.162.2590. Дои:10.1145/1772954.1772979. ISBN  9781605586359. S2CID  1820765.

внешняя ссылка