Boppan's blog

Register allocation

Есть такой алгоритм: сначала мы создаём граф из переменных. Переменные, используемые единовременно в контрол-флоу соединены. Затем мы по очереди забираем из графа переменные, имеющие менее k соседей, где k - это количество регистров. Кидаем их в стэк. Так со всеми. В конце мы попаем все элементы в стэке, пихаем их обратно и прифигачиваем каждому из них регистр минимального номера исключая всех, что присоединены к этой переменной.

Если вдруг нам не хватает регистров (в какой то момент нет переменных, имеющих менее k связей), мы при помощи эвристик вырезаем одну из переменных, обрабатываем все остальные ноды. После этого возвращаем вырезанную ноду и смотрим: а вдруг некоторые из соседей используют одинаковые регстры? Если да - профит, можно юзать оставшиеся регистры. Нет - придётся пихать ее в память и загружать и выгружать её при каждом использовании. Тогда вместо использования одной переменной для неё, мы используем несколько. Типа, f1 = load f, use f1, f2 = load f2, write to f2, store f2 to f. Это облегчает граф, там теперь меньше связей. Spilling называется это.

Чаще всего, шпилить придётся больше одной переменной, и тут вопрос - какие из них и в какм порядке? Некоторый порядок может выдать лучший результирующий код чем другой.

Page preparing taken 0.0027 seconds.