Регистрировать распределение и разлив, простой способ?

Я ищу способ выделения локальных переменных в регистры. Я знаю несколько серьезных методов для этого (а именно упомянутые

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

Перевести операцию x = y # z на:

movl y, %eax
movl z, %ebx
op %ebx, %eax
movl %eax, x

Поскольку я настроен на Intel 386, некоторые соответствующие ограничения:

Двоичные операции принимают два аргумента, один из которых является источником и пунктом назначения. Унарные операции принимают один аргумент. Операции могут иметь доступ только к одной ячейке памяти; поэтому для двоичных операций требуется хотя бы один аргумент в регистре. Доступно максимум шесть регистров: %eax %ebx %ecx %edx %esi %edi. (%ebp также может быть включено в качестве последнего средства.) Существуют специальные случаи, например, для регистров с целым делением и возвратом, но я могу их игнорировать пока.

В настоящий момент компилятор проходит три этапа:

i386ification: все операции преобразуются в форму a = a # b (или a = #a для унарных операций). Анализ жизнедеятельности: определяются группы живых переменных до и после каждой операции. Распределение регистров: построено и окрашено граф помех.

И затем компилятор бросает свои карандаши в воздух и не знает, что делать дальше.

Пример

public int mf(int cr, int ci) {
    int i = 0;
    int zr = 0;
    int zi = 0;

    while (i < 100 && zr*zr + zi*zi < 4) {
        int t = zr * zr - zi * zi + cr;
        zi = 2 * zr * zi + ci;
        zr = t;

        i = i + 1;
    }
    return i;
}

Здесь довольно симпатичный график помех для функции и CFG с информацией о жизнеспособности. К сожалению, изображение CFG требует некоторой вертикальной прокрутки.

Было использовано семь цветов. Я хотел бы пролить один из них (или набор переменных, назначенных этому цвету). Метод выбора, который не слишком важен. Что становится сложным, так это то, как справляться с пролитыми переменными.

Скажем, я разлил "розовый", который представляет собой набор переменных t, $t4, $t7. Это означает, что те операции, которые относятся к одной из этих переменных, будут обращаться к нему из своей позиции в стеке стека, а не через регистр. Это должно работать для этого примера.

Но что, если программа была:

...
a = a + b
...

и должны были разливаться как a, так и b? Я не могу испустить команду addl b, a с двумя адресами памяти. Мне понадобится еще один запасной регистр, чтобы временно удерживать один из операндов, а это означает, что он проливает другой цвет. Это предполагает общий метод:

Если все переменные могут быть окрашены цветами r, отлично! В противном случае разливайте цвета и связанные с ними переменные. Если существует операция, которая обращается к двум пролитым переменным, проливает другой цвет и использует запасной регистр для временного хранения для всех таких операций.

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

Конкретные проблемы

Основная проблема заключается в следующем: когда разливается переменная, как это влияет на генерируемые команды? Должны ли все инструкции, использующие эту переменную, обращаться к ней непосредственно в памяти (из ее положения стека)? Как это будет работать, если в операции используются две пролитые переменные? (Архитектура не позволяет инструкциям обращаться к двум различным ячейкам памяти.)

Вторичные проблемы:

Как определить, куда вставлять инструкции загрузки/хранения, для правильности (и, что менее важно, эффективности)? Могу ли я разлить переменную только для той части своего жизненного цикла, когда она не находится в непосредственном использовании, а затем нераспределить ее позже? Так что все инструкции действуют на непереполненных регистрах. Переменная может жить в разных регистрах в разное время. Могу ли я быть более эффективным в особых случаях. Например, для возвращаемого значения используется %eax, поэтому было бы неплохо, если бы переменная, которая должна быть возвращена, была назначена этому регистру к моменту возврата. Аналогичным образом, некоторые регистры являются "callee-save", поэтому, если бы меньшее количество переменных оказалось живым во время вызова функции, если они были распределены для регистров с сохранением недействительности, это означало бы, что я могу избежать хранения этих регистров. Помогла ли SSA помощь (если вообще)? Возможность устранения общих подвыражений и оценки констант может уменьшить (?) Давление в регистре, но в противном случае это имело бы какой-либо эффект?

Аспекты, которые меня не волнуют (прямо сейчас):

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

Update

Извините за простоя - я думал о полученных ответах и пытался найти легкий подход, чтобы начать реализацию некоторых идей. Честно говоря, я затягивал...: -\

Я нашел очень приятную презентацию (PPT, к сожалению):

Отвечает на вопрос о том, как справляться с конкретными потребностями в работе (например, использовать один и тот же регистр для источника и получателя или нужен определенный регистр для некоторых операций). Я не уверен в том, заканчивается ли цикл Lively-Coloring-Allocation.

Я постараюсь сделать некоторую фактическую работу в ближайшее время и, надеюсь, закрыть вопрос.

Ответ 1

Я использовал жадный подход в распределителе JVM один раз, который работал очень хорошо. В основном, начало в верхней части базового блока со всеми значениями, хранящимися в стеке. Затем просто отсканируйте инструкции вперед, сохранив список регистров, которые содержат значение, и является ли значение грязным (должно быть записано обратно). Если инструкция использует значение, которое не находится в регистре (или не находится в правильном регистре), выполните загрузку (или перемещение), чтобы поместить ее в свободный регистр перед инструкцией. Если инструкция записывает значение, убедитесь, что она находится в регистре и пометила ее после инструкции.

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

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

Если вы в порядке со всеми данными в стеке на каждой границе базового блока, эта схема работает очень хорошо. Он должен давать результаты, подобные линейному сканированию в базовом блоке, поскольку он в основном делает очень похожие вещи.

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

Я использовал этот распределитель в компиляторе SSA, YMMV.

Ответ 2

Во-первых: нет разумного способа сделать это. Проблема NP-полная; -)

Как происходит пролитие:

Вы запускаете свой алгоритм распределения регистров и получаете список переменных, которые вы должны проливать. Теперь вы можете выделить некоторое пространство в стеке в начале вашей функции. Свяжите каждую пролитую переменную и место в стеке. Если вы хотите быть умной объединенной памятью с неперекрывающимися живыми диапазонами. Всякий раз, когда вам нужно проливать регистр, сохраните его в памяти и загрузите его, когда он понадобится снова.

Как обращаться с eax:

Отметьте регистр как заполненный, но не храните в нем какую-либо переменную (предварительное выделение). Это заставит генератор кода очистить этот регистр. Чтобы быть умным, сохраните значение в другом регистре, если оно полезно.

Простые и правильные способы обработки разлива:

Просто разливай все. Предположим, что каждая переменная живого диапазона - это вся программа. Это может быть дополнено использованием таких вещей, как LRU или счет использования, чтобы выбрать, какие регистры должны быть освобождены.

Следующее, что вам нужно сделать, это, вероятно, распределение линейного сканирования. Это должно быть довольно легко реализовать даже при использовании предварительного выделения. Я предлагаю вам заглянуть в связанную бумагу.

Конкретные ответы

Что для вас значит правильность? Даже простые алгоритмы распределения правильны, если вы не делаете ошибку программирования. Корректная (математическая) корректность намного сложнее. Как нагрузки, так и магазины должны быть вставлены до того, как снова потребуется значение/регистр. Оба должны быть вставлены после сохранения/создания значения.
Да. Если вы запрограммируете его таким образом. Если ваш алгоритм может обрабатывать значение в нескольких регистрах во время его жизни, вы можете использовать эти оптимизации.
Это снова для вас, чтобы реализовать определенные улучшения. Одна из возможностей заключалась бы в том, чтобы блокировать eax только тогда, когда это необходимо, а не для всей программы.
При определенных условиях SSA помогает. Графы вывода кода SSA всегда chordal, что означает, что нет цикла с более чем тремя узлами. Это особый случай окраски графа, в котором минимальная окраска может быть найдена в полиномиальное время. Преобразование в SSA не обязательно означает более или менее регистрирующее давление. Хотя форма SSA обычно имеет больше переменных, они, как правило, имеют меньший вес.