Когда пишешь на ассемблере, всегда возникают проблемы с использованием регистров. Регистров всего восемь, а переменных, которые надо в них разместить, значительно больше. Сравни - регистров 8, а инструкции трех-местные. У меня распределение регистров всегда было постоянным источником ошибок и путаницы. Да и код может оказаться неоптимальным. Решил проблему, написав скрипт (ruby), который, найдя выделенные фрагменты кода с абстрактными регистрами, анализирует текст и заменяет переменные на физические регистры. Например, имея текст, в котором используются 22 абстрактных регистра (пишешь, не заботясь, какой физический регистр использовать)
получаешь фрагмент с назначенными реальными регистрами. Все 22 переменные разместились в шести регистрах.
Чтобы уменьшить зависимости, добавил в скрипт опцию “перемешивания” регистров, которая означает простую рекомендацию - не вынимать из стека свободных регистров последний возвращенный в стек регистр. Однако ускорение оказалось не большим: видно, механизм “переименовывания регистров” неплохо работает.
В качестве алгоритма “распределения регистров” (register allocation) использовал простой анализ живучести переменных (liveness analysis), описанный во многих книжках по компиляторам. А.Аппель представил его в своей книге “Modern Compiler Implementation in C” так (никогда не называй сделанное "современным")
В качестве алгоритма “распределения регистров” (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".
