Выделение регистра и проливание, простой способ?

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

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 используется для возвращаемого значения, таким образом, было бы хорошо, если бы переменная, которая будет возвращена, оказалось, была выделена тому регистру к тому времени, когда с возвратом встретились. Точно так же некоторые регистры являются "сохранением вызываемый", поэтому если бы меньше переменных, оказалось, было живо во время вызова функции, то выделение их к регистрам non-callee-save означало бы, что я могу постараться не хранить те регистры.
• SSA сформировался бы, помогают многому (если вообще)? Способность устранить общие подвыражения и оценить константы могла бы уменьшить (?) давление регистра, но иначе это будет иметь какой-либо эффект?

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

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

Обновление

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

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

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

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

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