Войти
В оптимизации компилятора, выделение регистров - это процесс назначения большого количества целевая программа переменные на небольшое количество регистров CPU .
Распределение регистров может происходить в базовом блоке (распределение локальных регистров) в целая функция / процедура (глобальное распределение регистров) или пересечение границ функций через граф вызовов (межпроцедурное распределение регистров). При выполнении для каждой функции / процедуры соглашение о вызовах может потребовать вставки сохранения / восстановления вокруг каждого сайта вызова.
| Архитектура | 32 бита | 64 бита |
|---|---|---|
| ARM | 15 | 31 |
| Intel x86 | 8 | 16 |
| MIPS | 32 | 32 |
| RISC-V | 16/32 | 32 |
| SPARC | 31 | 31 |
. Во многих языках программирования программист может использовать любое количество переменных. Компьютер может быстро читать и записывать регистры в ЦП, поэтому компьютерная программа работает быстрее, когда в регистрах ЦП может быть больше переменных. Кроме того, иногда код доступа к регистрам более компактен, поэтому код меньше и может быть извлечен быстрее, если он использует регистры, а не память. Однако количество регистров ограничено. Следовательно, когда компилятор переводит код на машинный язык, он должен решить, как распределить переменные в ограниченном количестве регистров в ЦП.
Не все переменные в использовать (или «жить») одновременно, поэтому в течение всего времени существования программы данный регистр может использоваться для хранения различных переменных. Однако две переменные, которые используются одновременно, не могут быть назначены одному и тому же регистру без повреждения одной из переменных. Если регистров недостаточно для хранения всех переменных, некоторые переменные могут быть перемещены в и из RAM. Этот процесс называется «проливанием» регистров. В течение срока службы программы переменная может быть как разнесена, так и сохранена в регистрах: тогда эта переменная считается «разделенной». Доступ к ОЗУ происходит значительно медленнее, чем доступ к регистрам, поэтому скомпилированная программа работает медленнее. Поэтому оптимизирующий компилятор стремится присвоить регистрам как можно больше переменных. Высокое «давление в регистре » - это технический термин, который означает, что необходимо больше разливов и повторных загрузок; это определено Braun et al. как «количество одновременно действующих переменных в команде».
Кроме того, некоторые компьютеры проектируют кэш часто используемые регистры. Таким образом, программы могут быть дополнительно оптимизированы путем назначения одного и того же регистра источнику и назначению инструкции move, когда это возможно. Это особенно важно, если компилятор использует промежуточное представление, такое как статическая форма с одним назначением (SSA). В частности, когда SSA не полностью оптимизирован, он может искусственно генерировать дополнительные инструкции перемещения.
Таким образом, распределение регистров состоит в выборе места для хранения переменных во время выполнения, т.е. внутри или вне регистров. Если переменная должна храниться в регистрах, то распределителю необходимо определить, в каком регистре (ах) эта переменная будет храниться. В конце концов, другая задача - определить продолжительность, в течение которой переменная должна оставаться в одном месте.
Распределитель регистров, игнорируя выбранную стратегию распределения, может полагаться на набор основных действий для решения этих проблем. Эти действия могут быть объединены в несколько различных категорий:
Многие подходы к распределению регистров оптимизируют для одной или нескольких конкретных категорий действий.
Регистры Intel 386 Выделение регистров порождает несколько проблем, которые можно решить (или избежать) с помощью различных подходов к распределению регистров. Ниже перечислены три наиболее распространенных проблемы:
Распределение регистров может происходить по базовому блоку кода: он считается «локальным» и впервые был упомянут Хорвицем и др. Поскольку базовые блоки не содержат ветвей, процесс распределения считается быстрым, потому что управление точками слияния графа потока управления в распределении регистров оказывается трудоемкой операцией. Однако считается, что этот подход не дает такого оптимизированного кода, как «глобальный» подход, который работает над всем блоком компиляции (например, методом или процедурой).
Распределение раскраски графа - преобладающий подход к решению распределения регистров. Впервые он был предложен Chaitin et al. В этом подходе узлы в графе представляют живые диапазоны (переменные, временные, виртуальные / символьные регистры), которые являются кандидатами для распределения регистров. Края соединяют живые диапазоны, которые мешают, т. Е. Активные диапазоны, которые одновременно являются активными как минимум в одной точке программы. Затем распределение регистров сводится к проблеме раскраски графа, в которой цвета (регистры) назначаются узлам таким образом, что два узла, соединенные ребром, не получают одинаковый цвет.
Использование анализ живучести, можно построить интерференционный граф. Граф интерференции, который представляет собой неориентированный граф, где узлы являются переменными программы, используется для моделирования того, какие переменные не могут быть размещены в одном регистре.
Основными этапами в распределителе регистров раскраски графов в стиле Чейтина являются:
Распределитель регистров на основе итеративной раскраски графов Чейтина и др. Распределение раскраски графов имеет три основных недостатка. Во-первых, он полагается на раскраску графа, которая является NP-полной проблемой, чтобы решить, какие переменные будут разбиты. Поиск минимального графа раскраски действительно является NP-полной проблемой. Во-вторых, если не используется разделение живого диапазона, вытесненные переменные распространяются повсюду: инструкции сохранения (соответственно загрузки) вставляются как можно раньше (соответственно поздно), то есть сразу после (соответственно до) определений переменных (соответственно использования). В-третьих, переменная, которая не разливается, хранится в одном и том же регистре на протяжении всего срока службы.
С другой стороны, одно имя регистра может появляться в нескольких классах регистров, где класс представляет собой набор имен регистров. которые взаимозаменяемы в определенной роли. Тогда несколько имен регистров могут быть псевдонимами для одного аппаратного регистра. Наконец, раскраска графа - это агрессивный метод распределения регистров, но он требует больших вычислительных ресурсов из-за использования графа интерференции, который может иметь наихудший размер квадратичный по числу активных диапазонов. Традиционная формулировка выделения регистров раскраски графа неявно предполагает наличие одного банка неперекрывающихся регистров общего назначения и не обрабатывает нестандартные архитектурные особенности, такие как перекрывающиеся пары регистров, регистры специального назначения и несколько банков регистров.
Один позже. Бриггс и др. обнаружили усовершенствование метода раскраски графов в стиле Чайтина: это называется консервативным объединением. Это улучшение добавляет критерий для принятия решения о том, когда два живых диапазона могут быть объединены. В основном, помимо требований невмешательства, две переменные могут быть объединены только в том случае, если их объединение не вызовет дальнейшего разлива. Briggs et al. вводит второе улучшение работ Чайтина - предвзятую окраску. Смещенная раскраска пытается назначить тот же цвет в раскраске графа живому диапазону, связанному с копированием.
Линейное сканирование - это еще один подход к глобальному распределению регистров. Впервые он был предложен Poletto et al. в 1999 году. При таком подходе код не превращается в граф. Вместо этого все переменные линейно сканируются, чтобы определить их текущий диапазон, представленный как интервал. После определения диапазонов значений всех переменных, интервалы просматриваются в хронологическом порядке. Хотя этот обход может помочь идентифицировать переменные, живые диапазоны которых мешают, граф интерференции не строится, а переменные распределяются жадным образом.
Мотивом для этого подхода является скорость; не с точки зрения времени выполнения сгенерированного кода, а с точки зрения времени, затраченного на генерацию кода. Как правило, стандартные подходы к раскраске графа производят качественный код, но имеют значительные накладные расходы, так как используемый алгоритм раскраски графа имеет квадратичную стоимость. Благодаря этой функции, линейное сканирование - это подход, который в настоящее время используется в нескольких JIT-компиляторах, таких как компилятор Hotspot, V8 и Jikes RVM.
. Здесь описывается алгоритм, как впервые предложенный. Полетто и др.
LinearScanRegisterAllocation active ← {} для каждого живого интервала i в порядке увеличения начальной точки do ExpireOldIntervals (i) if length (active) = R, затем SpillAtInterval (i) else register [i] ← регистр, удаленный из пула свободных регистров, добавить i в активный, отсортированный по возрастанию конечной точки ExpireOldIntervals (i) для каждого интервала j в активном, в порядке увеличения конечной точки doifконечной точки [j] ≥ начальной точки [i] затем return удалить j из активного регистра добавления [j] в пул свободных регистров SpillAtInterval (i) spill ← последний интервал в активном if endpoint [spill ]>конечная точка [i] затем регистр [i] ← регистр [разлив] место [разлив] ← новое место стека удалить разлив из ctive добавить i в активный, отсортированный по возрастанию конечной точки else location [i] ← новое расположение стекаОднако линейное сканирование имеет два основных недостатки. Во-первых, из-за своего жадного аспекта он не принимает во внимание пробелы в сроке службы, то есть «диапазоны, в которых значение переменной не требуется». Кроме того, разлитая переменная будет оставаться разлитой на протяжении всего срока службы.
Более короткие живые диапазоны с подходом SSA Многие другие исследовательские работы продолжили работу над алгоритмом линейного сканирования Poletto. Трауб и др., Например, предложили алгоритм, называемый бункерной упаковкой второго шанса, направленный на создание кода более высокого качества. В этом подходе разлитые переменные получают возможность позже сохраняться в регистре с использованием эвристики , отличной от той, которая используется в стандартном алгоритме линейного сканирования. Вместо того, чтобы использовать живые интервалы, алгоритм полагается на живые диапазоны, а это означает, что если диапазон должен быть расширен, нет необходимости разливать все другие диапазоны, соответствующие этой переменной.
Распределение линейного сканирования было также адаптировано для использования преимуществ формы SSA : свойства этого промежуточного представления используются для упрощения алгоритма распределения. Во-первых, время, затрачиваемое на анализ графа потока данных, направленное на построение интервалов времени жизни, сокращается, а именно потому, что переменные уникальны. Следовательно, это дает более короткие живые интервалы, потому что каждое новое назначение соответствует новому живому интервалу.
Проблема оптимального распределения регистров является NP-полной. Как следствие, компиляторы используют эвристические методы для приближения своего решения.
Chaitin et al. обсудить несколько идей по повышению качества кода утечки. Они указывают на то, что определенные значения могут быть повторно вычислены в одной инструкции и что требуемый операнд всегда будет доступен для вычисления. Они называют эти исключительные значения «никогда не уничтожаемыми» и отмечают, что такие значения следует пересчитывать, а не проливать и перезагружать. Они также отмечают, что несвязанная копия никогда не уничтоженного значения может быть удалена путем пересчета ее непосредственно в желаемый регистр.
Эти методы называются рематериализацией. На практике возможности для рематериализации включают:
Бриггс и Эл расширяют работу Чейтина, чтобы воспользоваться возможностями рематериализации для сложных многозначных диапазонов реального времени. Они обнаружили, что каждое значение должно быть помечено достаточным количеством информации, чтобы распределитель мог его правильно обработать. Подход Бриггса заключается в следующем: сначала разделите каждый активный диапазон на его значения компонентов, затем распространите теги рематериализации на каждое значение и сформируйте новые живые диапазоны из связанных значений с идентичными тегами.
В контексте распределения регистров объединение - это акт объединения операций перемещения переменной в переменную путем размещения этих двух переменных в одном месте. Операция объединения происходит после построения интерференционного графа. После объединения двух узлов они должны получить один и тот же цвет и быть размещены в одном регистре, как только операция копирования станет ненужной.
Выполнение объединения может иметь как положительное, так и отрицательное влияние на раскрашиваемость интерференционного графа. Например, одно негативное влияние, которое объединение может оказать на раскрашиваемость вывода графа, - это объединение двух узлов, так как конечный узел будет иметь объединение ребер объединяемых. Положительное влияние объединения на раскрашиваемость графа вывода состоит, например, в том, что когда узел мешает объединению обоих узлов, степень узла уменьшается на единицу, что приводит к улучшению общей раскрашиваемости интерференционного графа.
Доступно несколько эвристик объединения:
Некоторые другие Подходы к распределению регистров не ограничиваются одним методом оптимизации использования регистров. Cavazos et.al, например, предложили решение, в котором можно использовать как алгоритмы линейного сканирования, так и алгоритмы раскраски графов. В этом подходе выбор между тем или иным решением определяется динамически: во-первых, алгоритм машинного обучения используется в автономном режиме, то есть не во время выполнения, для создания эвристической функции, которая определяет, какой необходимо использовать алгоритм распределения. Затем во время выполнения используется эвристическая функция; в свете поведения кода распределитель может затем выбрать один из двух доступных алгоритмов.
Выделение регистров трассировки - это недавний подход, разработанный Eisl et al. Этот метод обрабатывает распределение локально: он полагается на данные динамического профилирования, чтобы определить, какие ветви будут наиболее часто использоваться в данном графе потока управления. Затем он выводит набор «следов» (то есть сегментов кода), в которых точка слияния игнорируется в пользу наиболее часто используемой ветви. Затем каждая трасса независимо обрабатывается распределителем. Этот подход можно рассматривать как гибридный, поскольку можно использовать разные алгоритмы распределения регистров между разными трассировками.
Разделенное распределение - это еще один метод распределения регистров, который объединяет различные подходы, обычно рассматриваемые как наоборот. Например, метод гибридного распределения можно рассматривать как разделение, поскольку первый этап построения эвристики выполняется в автономном режиме, а эвристическое использование выполняется в режиме онлайн. Таким же образом B. Diouf et al. предложил метод распределения, основанный как на автономном, так и на онлайн-поведении, а именно на статической и динамической компиляции. На этапе автономной работы сначала собирается оптимальный набор разливов с помощью Целочисленное линейное программирование. Затем живые диапазоны аннотируются с использованием алгоритма compressAnnotation, который основан на ранее идентифицированном оптимальном наборе разлива. Распределение регистров выполняется впоследствии во время онлайн-этапа на основе данных, собранных на автономном этапе.
В 2007 году Бушез и др. Также предложили разделить распределение регистров на разные этапы, имея один этап, посвященный разливу и один посвящен раскрашиванию и объединению.
Для оценки эффективности одного метода распределения регистров по сравнению с другим использовалось несколько показателей. При распределении регистров обычно приходится иметь дело с компромиссом между качеством кода, то есть кодом, который выполняется быстро, и накладными расходами на анализ, то есть временем, затраченным на определение анализа исходного кода для генерации кода с оптимизированным распределением регистров. С этой точки зрения время выполнения сгенерированного кода и время, потраченное на анализ жизнеспособности, являются релевантными метриками для сравнения различных методов.
После выбора соответствующих метрик должен быть доступен код, к которому будут применяться метрики. и имеет отношение к проблеме, либо отражая поведение реального приложения, либо будучи уместным для конкретной проблемы, которую алгоритм хочет решить. В более поздних статьях о распределении регистров используется, в частности, набор тестов Dacapo.
