Я ищу способ выделения локальных переменных для регистров. Я знаю пару серьезных способов сделать это (а именно, упомянутые в Википедии ), но я застрял на том, как "пролить". Кроме того, соответствующая литература довольно пугающая. Я надеюсь, что есть что-то более простое, что удовлетворит мои приоритеты:
- Корректность - алгоритм, который будет генерировать правильный код независимо от количества локальных переменных.
- Простота - что-то, что я могу понять без необходимости читать слишком много литературы.
- Эффективность - она должна быть лучше, чем текущий метод, а именно:
Перевести операцию 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 цветами, отлично!
- В противном случае пролить некоторые цвета и связанные с ними переменные.
- Если существует операция, которая обращается к двум разлитым переменным, выведите другой цвет и используйте резервный регистр для временного хранения всех таких операций.
В этот момент я бы заподозрил, что разлито гораздо больше материала, чем необходимо, и удивился бы, есть ли какой-нибудь более умный способ разлива вещей, такой как разлив части времени жизни переменной, а не всей переменной. Есть ли какие-то простые (ish) методы, которые я мог бы использовать здесь? Опять же, я не нацеливаюсь особенно высоко - конечно, недостаточно высоко, чтобы требовать прочтения чего-либо слишком глубокого. ; -)
Конкретные проблемы
Основная конкретная проблема: когда разлитая переменная, как это влияет на сгенерированные инструкции? Все ли инструкции, использующие эту переменную, должны обращаться к ней напрямую в памяти (из позиции стека)? Как это будет работать, если в операции используются две разлитые переменные? (Архитектура не позволяет инструкциям обращаться к двум разным ячейкам памяти.)
Вторичные проблемы:
- Как определить, куда вставлять инструкции по загрузке / хранению, для корректности (и, что менее важно, эффективности)?
- Могу ли я пролить переменную только на ту часть ее времени жизни, когда она не используется немедленно, и удалить ее позже? Так что все инструкции действуют на незаполненные регистры. Переменная может жить в разных регистрах в разное время.
- Могу ли я быть немного более эффективным в особых случаях. Например,
%eax используется для возвращаемого значения, поэтому было бы хорошо, если бы возвращаемая переменная была назначена этому регистру к моменту возврата. Точно так же некоторые регистры являются «сохраняемыми», поэтому, если во время вызова функции оказалось меньше переменных, то их назначение в регистры, не сохраняемые при вызове, означало бы, что я могу избежать сохранения этих регистров.
- Может ли форма SSA помочь (если вообще)? Возможность устранения общих подвыражений и оценки констант может уменьшить (?) Давление в регистре, но в противном случае это будет иметь какой-либо эффект?
Аспекты, которые меня не беспокоят (прямо сейчас):
- Распределение и оптимизация стека: он уже реализован наивно и может быть оптимизирован с использованием графа помех, если это необходимо.
- Эффективность во время компиляции, до тех пор, пока она заканчивается. (NP-полнота не подразумевает, что данный алгоритм следует избегать.)
Обновление
Извините за время простоя - я размышлял над ответами и пытался найти простой подход, чтобы начать реализацию некоторых идей. Если честно, я откладывал ...: - \
Я нашел очень хорошую презентацию (PPT, к сожалению):
http://www.cs.princeton.edu/courses/archive/spr05/cos320/notes/Register%20Allocation.ppt
Что отвечает на вопрос о том, как справляться с конкретными операционными потребностями (например, использовать один и тот же регистр для источника и получателя или нужен определенный регистр для некоторых операций). В чем я не уверен, так ли заканчивается цикл «Живость-раскраска-распределение».
Я постараюсь сделать какую-то реальную работу в ближайшее время и, надеюсь, закрою вопрос.