Распределение регистров и их утечка - простой способ?

Question

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

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 также может быть включен в качестве крайней меры.)
• Существуют особые случаи, такие как для регистров целочисленного деления и возврата, но пока я могу их игнорировать.

На данный момент компилятор выполняет три шага:

• i386 классификация:все операции преобразуются в форму 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

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

Скоро я постараюсь проделать какую-нибудь реальную работу и, надеюсь, закрою этот вопрос.

Answer 1

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

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

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

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

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

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

Answer 2

Первый:Нет никакого разумного способа сделать это.Проблема NP-завершена ;-)

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

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

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

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

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

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

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

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

1. Что для вас означает корректность?Даже простые алгоритмы распределения являются правильными, если вы не допускаете ошибки программирования.Проверка (математической) корректности намного сложнее.Как загрузка, так и сохранение должны быть вставлены до того, как значение / регистр снова понадобятся.Оба должны быть вставлены после сохранения / создания значения.

2. ДА.Если вы запрограммируете это таким образом.Если ваш алгоритм может обрабатывать значение в нескольких регистрах в течение своего жизненного цикла, вы можете использовать эти оптимизации.

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

4. При определенных условиях SSA действительно помогает.Графики вывода кода SSA всегда хордовый, что означает, что не существует цикла с более чем 3 узлами.Это частный случай раскраски графа, в котором минимальная раскраска может быть найдена за полиномиальное время.Преобразование в SSA не обязательно означает большее или меньшее давление в регистре.Хотя форма SSA обычно содержит больше переменных, они, как правило, имеют меньшее время жизни.