Я ищу способ размещения локальных переменных в регистрах. Я знаю пару серьезных способов сделать это (а именно, упомянутыев Википедии), но я застрял на том, как "разлив" осуществляется. Кроме того, соответствующая литература довольно пугающая. Я надеюсь, что есть что-то более простое, что удовлетворит мои приоритеты:

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

Перевести операцию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 требует вертикальной прокрутки.

График интерференции для функции на 14 переменныхГрафик потока управления для функции, с информацией о живучести

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

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

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

...
a = a + b
...

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

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

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

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

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

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

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

Аспекты, которые меня не беспокоят (прямо сейчас):

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

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

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

http://www.cs.princeton.edu/courses/archive/spr05/cos320/notes/Register%20Allocation.ppt

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

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