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

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

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

Перевести операцию 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 с двумя адресами памяти. Мне понадобится еще один запасной регистр для временного хранения одного из операндов, а это означает выделение другого цвета. Это предлагает общий метод:

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

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

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

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

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

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

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

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

Обновлять

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

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

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

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

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