Автоматическое распределение регистров

Когда пишешь на ассемблере, всегда возникают проблемы с использованием регистров. Регистров всего восемь, а переменных, которые надо в них разместить, значительно больше. Сравни - регистров 8, а инструкции трех-местные. У меня распределение регистров всегда было постоянным источником ошибок и путаницы. Да и код может оказаться неоптимальным. Решил проблему, написав скрипт (ruby), который, найдя выделенные фрагменты кода с абстрактными регистрами, анализирует текст и заменяет переменные на физические регистры. Например, имея текст, в котором используются 22 абстрактных регистра (пишешь, не заботясь, какой физический регистр использовать)

получаешь фрагмент с назначенными реальными регистрами. Все 22 переменные разместились в шести регистрах.

Чтобы уменьшить зависимости, добавил в скрипт опцию “перемешивания” регистров, которая означает простую рекомендацию - не вынимать из стека свободных регистров последний возвращенный в стек регистр. Однако ускорение оказалось не большим: видно, механизм “переименовывания регистров” неплохо работает.
В качестве алгоритма “распределения регистров” (register allocation) использовал простой анализ живучести переменных (liveness analysis), описанный во многих книжках по компиляторам. А.Аппель представил его в своей книге “Modern Compiler Implementation in C” так (никогда не называй сделанное "современным")

def и use являются массивами множеств с переменными, которые определяются в строке n (им присваивается значение) или используются, соответственно. Код алгоритма 10.4 буквально может быть таким

begin txt.each_with_index { |line, n| livein_[n] = Set.new(livein[n]) liveout_[n] = Set.new(liveout[n]) livein[n] = Set.new(ause[n]) tmp = Set.new(liveout[n]-adef[n]) livein[n].merge(tmp) unless tmp.empty? liveout[n] = Set.new asucc[n].each { |s| liveout[n].merge(livein[s]) unless livein[s].empty? } } end until livein==livein_ and liveout==liveout_

Интервалы живучести переменных и присвоение имен физических регистров (номеров) можно представить таким образом.

Слева - исходный код (усеченный текст) с абстрактными регистрами, в середине - интервалы жизни этих регистров по телу функции, справа - присвоенные физические регистры, точнее их номера. Горизонтальный заголовок из цифр по модулю 10 - это номера абстрактных переменных. В имени абстрактной переменной для 128-разрядных регистров используется префикс "x", для 256-разрядных - префикс "y".