Распределение регистров
В оптимизации компилятора распределение регистров — это процесс назначения локальных автоматических переменных и результатов выражений ограниченному числу регистров процессора .
Распределение регистров может происходить по базовому блоку ( локальное распределение регистров ), по всей функции/ процедуре ( глобальное распределение регистров ) или по границам функции, пересекаемым через граф вызовов ( межпроцедурное распределение регистров ). Когда это делается для каждой функции/процедуры, соглашение о вызовах может потребовать вставки сохранения/восстановления вокруг каждого места вызова .
Контекст [ править ]
Принцип [ править ]
| Архитектура | 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]
Многие подходы к распределению регистров оптимизируются для одной или нескольких конкретных категорий действий.
Общие проблемы, возникающие регистров при распределении
Распределение регистров порождает несколько проблем, которые можно решить (или избежать) с помощью различных подходов к распределению регистров. Три наиболее распространенные проблемы определяются следующим образом:
- Псевдонимы
- В некоторых архитектурах присвоение значения одному регистру может повлиять на значение другого: это называется псевдонимами. Например, архитектура 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]
- Перенумеровать : найти информацию о реальном диапазоне в исходной программе.
- Построить : построить график интерференции.
- Объединение : объединение текущих диапазонов невлияющих переменных, связанных инструкциями копирования.
- Стоимость разлива : вычислите стоимость разлива каждой переменной. Это оценивает влияние отображения переменной в память на скорость конечной программы.
- Упростить : построить порядок узлов в графе выводов.
- Код разгрузки : вставляет инструкции разгрузки, т.е. загружает и сохраняет значения для переключения между регистрами и памятью.
- Выберите : назначить регистр каждой переменной.
Недостатки и дальнейшие улучшения [ править ]
Распределение раскраски графов имеет три основных недостатка. Во-первых, он полагается на раскраску графа, которая является 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
активный ← {}
для каждого живого интервала i в порядке возрастания начальной точки выполните
ExpireOldIntervals(i)
если длина (активная) = R , то
РазливАтИнтервал(i)
еще
Register[i] ← регистр, удаленный из пула свободных регистров
добавить i в активный, отсортировать по возрастанию конечной точки
ExpireOldIntervals(i)
для каждого интервала j активного , в порядке возрастания конечной точки выполните
, если endpoint[j] ≥ startpoint[i] , затем
верните
удалить j из активного
добавить регистр[j] в пул свободных регистров
РазливАтИнтервал(i)
пролив ← последний интервал активности
если конечная точка[разлив] > конечная точка[i] , то
зарегистрироваться[i] ← зарегистрироваться[пролить]
location[разлив] ← новое место стека
удалить разлив из активного
добавить i в активный, отсортировать по возрастанию конечной точки
еще
location[i] ← новое местоположение стека
Недостатки и дальнейшие улучшения [ править ]
Однако линейное сканирование имеет два основных недостатка. Во-первых, из-за своего жадного аспекта он не учитывает дыры во времени жизни, то есть «диапазоны, в которых значение переменной не требуется». [33] [34] Кроме того, удаленная переменная останется удаленной на протяжении всего своего существования.
Многие другие исследовательские работы развивали алгоритм линейного сканирования Полетто. Трауб и др., например, предложили алгоритм, называемый бинпаковкой второго шанса, направленный на генерацию кода более высокого качества. [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++ для размещения переменной в регистре.
- Алгоритм Сетхи-Ульмана — алгоритм, обеспечивающий наиболее эффективное распределение регистров для вычисления одного выражения, когда количество регистров, необходимых для вычисления выражения, превышает количество доступных регистров.
Ссылки [ править ]
- ^ Дитцель и Маклеллан 1982 , с. 48.
- ^ Рунесон и Нюстрем 2003 , стр. 242.
- ^ Перейти обратно: а б Эйсл и др. 2016 , с. 14:1.
- ^ Перейти обратно: а б Чайтин и др. 1981 , с. 47.
- ^ Перейти обратно: а б с Эйсл и др. 2016 , с. 1.
- ^ «Сравнение задержек в компьютере/сети» . blog.morizyun.com. 6 января 2018 года . Проверено 8 января 2019 г.
- ^ Браун и Хак 2009 , с. 174.
- ^ Коес и Гольдштейн 2009 , с. 21.
- ^ Перейти обратно: а б с д Буше, Дарте и Растелло 2007b , с. 103.
- ^ Коломбет, Бранднер и Дарте 2011 , с. 26.
- ^ «Руководство разработчика программного обеспечения для архитектур Intel® 64 и IA-32, раздел 3.4.1» (PDF) . Интел. Май 2019 г. Архивировано из оригинала (PDF) 25 мая 2019 г.
- ^ «Соглашения о вызове 32-битных функций PowerPC» .
- ^ Бушез, Дарте и Растелло 2006 , с. 4.
- ^ Хорвиц и др. 1966 , с. 43.
- ^ Фарах и Либераторе 1998 , с. 566.
- ^ Эйсл и др. 2017 , с. 92.
- ^ Эйсль, Леопольдседер и Мессенбёк 2018 , стр. 1.
- ^ Перейти обратно: а б с Бриггс, Купер и Торчон 1992 , с. 316.
- ^ Полетто и Саркар 1999 , с. 896.
- ^ Рунесон и Нюстрем 2003 , стр. 241.
- ^ Книга 1975 , с. 618–619.
- ^ Коломбет, Бранднер и Дарте 2011 , с. 1.
- ^ Смит, Рэмси и Холлоуэй 2004 , стр. 277.
- ^ Перейти обратно: а б с Кавасос, Мосс и О'Бойл, 2006 , с. 124.
- ^ Рунесон и Нюстрем 2003 , стр. 240.
- ^ Полетто и Саркар 1999 , с. 895.
- ^ Полетто и Саркар 1999 , с. 902.
- ^ Виммер и Мессенбёк 2005 , с. 132.
- ^ Johansson & Sagonas 2002, p. 102.
- ^ Эволюция ART – Google I/O 2016 . Google . 25 мая 2016 г. Событие происходит в 3:47.
- ^ Палечный, Vick & Click 2001 , с. 1.
- ^ Полетто и Саркар 1999 , с. 899.
- ^ Эйсл и др. 2016 , с. 2.
- ^ Трауб, Холлоуэй и Смит 1998 , стр. 143.
- ^ Трауб, Холлоуэй и Смит 1998 , стр. 141.
- ^ Полетто и Саркар 1999 , с. 897.
- ^ Виммер и Франц 2010 , с. 170.
- ^ Мессенбёк и Пфайффер 2002 , с. 234.
- ^ Мессенбёк и Пфайффер 2002 , с. 233.
- ^ Мессенбёк и Пфайффер 2002 , с. 229.
- ^ Роджерс 2020 .
- ^ Чайтин 1982 , с. 90.
- ^ Перейти обратно: а б Ан и Пэк 2009 , с. 7.
- ^ Парк и Луна 2004 , с. 736.
- ^ Чайтин 1982 , с. 99.
- ^ Парк и Луна 2004 , с. 738.
- ^ Бриггс, Купер и Торчон 1994 , стр. 433.
- ^ Джордж и Аппель 1996 , с. 212.
- ^ Парк и Луна 2004 , с. 741.
- ^ Эйсл и др. 2017 , с. 11.
- ^ Кавазос, Мосс и О'Бойл 2006 , с. 124-127.
- ^ Эйсл и др. 2016 , с. 4.
- ^ Диуф и др. 2010 , с. 66.
- ^ Коэн и Роху 2010 , с. 1.
- ^ Диуф и др. 2010 , с. 72.
- ^ Бушез, Дарте и Растелло 2007a , с. 1.
- ^ Полетто и Саркар 1999 , с. 901-910.
- ^ Блэкберн и др. 2006 , с. 169.
- ^ Флажоле, Рауль и Вийемен 1979 .
Источники [ править ]
- Ан, Минук; Пэк, Юнхын (2009). «Методы объединения регистров для гетерогенной архитектуры регистров с фильтрацией копий». Транзакции ACM во встроенных вычислительных системах . 8 (2): 1–37. CiteSeerX 10.1.1.615.5767 . дои : 10.1145/1457255.1457263 . ISSN 1539-9087 . S2CID 14143277 .
- Ахо, Альфред В.; Лам, Моника С.; Сетхи, Рави; Уллман, Джеффри Д. (2006). Составители: принципы, методы и инструменты (второе изд.). 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 .
- Блэкберн, Стивен М.; Гайер, Сэмюэл З.; Хирзель, Мартин; Хоскинг, Энтони; Прыгай, Мария; Ли, Хан; Элиот, Дж.; Мосс, Б.; Фансалкар, Аашиш; Стефанович, Дарко; ВанДрунен, Томас; Гарнер, Робин; фон Динклаге, Даниэль; Видерманн, Бен; Хоффманн, Крис; Ханг, Асджад М.; МакКинли, Кэтрин С.; Бенцур, Ротем; Диван, Америка; Фейнберг, Дэниел; Фрэмптон, Дэниел (2006). «Эталоны DaCapo». Материалы 21-й ежегодной конференции ACM SIGPLAN по системам, языкам и приложениям объектно-ориентированного программирования — OOPSLA '06 . п. 169. дои : 10.1145/1167473.1167488 . hdl : 1885/33723 . ISBN 978-1595933485 . S2CID 9255051 .
- Книга Рональда В. (декабрь 1975 г.). «Карп Ричард М.. Сводимость комбинаторных задач. Сложность компьютерных вычислений, Материалы симпозиума по сложности компьютерных вычислений, состоявшегося 20-22 марта 1972 года в Центре IBM Томаса Дж. Уотсона, Йорктаун-Хайтс, Нью-Йорк, под редакцией Миллера Рэймонда Э. и Тэтчер Джеймса В., Plenum Press, Нью-Йорк и Лондон, 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 .
- Буше, Флоран; Дарте, Ален; Растелло, Фабрис (2007a). «О сложности объединения регистров». Международный симпозиум по генерации и оптимизации кода (CGO'07) . стр. 102–114. CiteSeerX 10.1.1.101.6801 . дои : 10.1109/CGO.2007.26 . ISBN 978-0-7695-2764-2 . S2CID 7683867 .
- Буше, Флоран; Дарте, Ален; Растелло, Фабрис (2007b). «О сложности разлива повсеместно по форме ССА». Уведомления ACM SIGPLAN . 42 (7): 103–114. 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 .
- Кавасос, Джон; Мосс, Дж. Элиот Б.; О'Бойл, Майкл Ф.П. (2006). «Гибридная оптимизация: какой алгоритм оптимизации использовать?». Конструкция компилятора . Конспекты лекций по информатике. Том. 3923. стр. 124–138. дои : 10.1007/11688839_12 . ISBN 978-3-540-33050-9 . ISSN 0302-9743 .
- Чайтин, Грегори Дж.; Ауслендер, Марк А.; Чандра, Ашок К.; Кок, Джон; Хопкинс, Мартин Э.; Маркштейн, Питер В. (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 .
- Дитцель, Дэвид Р.; Маклеллан, HR (1982). «Зарегистрируйте размещение бесплатно». Материалы первого международного симпозиума по архитектурному обеспечению языков программирования и операционных систем — ASPLOS-I . стр. 48–56. дои : 10.1145/800050.801825 . ISBN 978-0897910668 . S2CID 2812379 .
- Эйсль, Йозеф; Гриммер, Матиас; Саймон, Дуг; Вюртингер, Томас; Мессенбёк, Ханспетер (2016). «Распределение регистров на основе трассировки в JIT-компиляторе». Материалы 13-й Международной конференции «Принципы и практика программирования на платформе Java: виртуальные машины, языки и инструменты» — PPPJ '16 . стр. 1–11. дои : 10.1145/2972206.2972211 . ISBN 9781450341356 . S2CID 31845919 .
- Эйсль, Йозеф; Марр, Стефан; Вюртингер, Томас; Мессенбёк, Ханспетер (2017). «Политика распределения регистров трассировки» (PDF) . Материалы 14-й Международной конференции по управляемым языкам и средам выполнения — Ман Ланг 2017 . стр. 92–104. дои : 10.1145/3132190.3132209 . ISBN 9781450353403 . S2CID 1195601 .
- Эйсль, Йозеф; Леопольдседер, Дэвид; Мессенбёк, Ханспетер (2018). «Распределение регистров параллельной трассировки». Материалы 15-й Международной конференции по управляемым языкам и средам выполнения - Man Lang '18 . стр. 1–7. дои : 10.1145/3237009.3237010 . ISBN 9781450364249 . S2CID 52137887 .
- Коес, Дэвид Райан; Гольдштейн, Сет Копен (2009). «Распределение регистров деконструировано» . Написано в Ницце, Франция. Материалы 12-го международного семинара по программному обеспечению и компиляторам для встраиваемых систем . ОБЛАСТИ '09. Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 21–30. ISBN 978-1-60558-696-0 .
- Фарах, Мартин; Либераторе, Винченцо (1998). «О размещении локального регистра» . Написано в Сан-Франциско, Калифорния, США. Материалы девятого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . СОДА '98. Филадельфия, Пенсильвания, США: Общество промышленной и прикладной математики. стр. 564–573 . ISBN 0-89871-410-9 .
- Флажоле, П. ; Рауль, Дж.К.; Вуйемен, Дж. (1979), «Количество регистров, необходимых для оценки арифметических выражений», Theoretical Computer Science , 9 (1): 99–125, doi : 10.1016/0304-3975(79)90009-4
- Джордж, Лал; Аппель, Эндрю В. (1996). «Итерированное объединение регистров» . Транзакции ACM в языках и системах программирования . 18 (3): 300–324. дои : 10.1145/229542.229546 . ISSN 0164-0925 . S2CID 12281734 .
- Хорвиц, LP; Карп, Р.М.; Миллер, Р.Э.; Виноград, С. (1966). «Распределение индексных регистров» . Журнал АКМ . 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 .
- Курдахи, Ф.Дж.; Паркер, AC (1987). «РЕАЛ: программа для РЕГИСТРАЦИИ АЛлокации». Материалы 24-й конференции ACM/IEEE, посвященной конференции по автоматизации проектирования - DAC '87 . стр. 210–215. дои : 10.1145/37888.37920 . ISBN 978-0818607813 . S2CID 17598675 .
- Мессенбёк, Ханспетер; Пфайффер, Майкл (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 .
- Палечный, Майкл; Вик, Кристофер; Клик, Клифф (2001). «Компилятор сервера Java HotSpot». Материалы симпозиума по исследованиям и технологиям виртуальных машин Java (JVM01) . Монтерей, Калифорния, США. стр. 1–12. CiteSeerX 10.1.1.106.1919 .
- Пак, Джинпё; Мун, Су-Мук (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 .
- Виммер, Кристиан; Мессенбёк, Ханспетер (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 .
Внешние ссылки [ править ]
- Учебник по целочисленному программированию
- Конференция «Целочисленное программирование и комбинаторная оптимизация», IPCO
- Семинар по комбинаторной оптимизации Aussois
- Босшер, Стивен; и Новилло, Диего. GCC получает новую платформу оптимизатора . Статья об использовании SSA в GCC и о его преимуществах по сравнению со старыми IR.
- Библиография SSA . Обширный каталог исследовательских работ SSA.
- Задек, Ф. Кеннет. «Разработка статической формы единого задания» , декабрь 2007 г., рассказ о происхождении SSA.
- ВВ.АА. «Проектирование компилятора на основе SSA» (2014 г.)
- Цитаты из CiteSeer
- Руководства по оптимизации от Agner Fog - документация по процессорной архитектуре x86 и низкоуровневой оптимизации кода.
 | |||||||||||||||
| |||||||||||||||