В ZJIT — новом JIT-компиляторе для Ruby — завезли свежий регистровый аллокатор. Зачем он нужен? Когда компилятор генерирует машинный код, ему надо решить, где хранить значения. CPU работает с регистрами — это быстро, но их мало. Если переменных больше, чем регистров, часть значений приходится «выливать» в память (spill). Этим и занимается аллокатор: распределяет регистры и решает, что отправить на стек.
В ZJIT выбрали линейный сканирующий аллокатор на основе статьи Christian Wimmer «Linear Scan Register Allocation on SSA Form». Почему не графовую раскраску? Графы дают качественнее, но строить их долго. Для JIT скорость компиляции критична, так что линейный проход — оптимальный компромисс.
ZJIT использует SSA-форму (Static Single Assignment) — каждая переменная определяется ровно один раз. Например, Ruby-код a = 123; a = a + 1 превращается в v1 = Const(123); v2 = Const(1); v3 = Add v1, v2; CRet v3. v1, v2, v3 — разные SSA-переменные. Это упрощает анализ.
Аллокатор сначала вычисляет lifetimes (время жизни) каждой переменной: от определения до последнего использования. Если две переменные живут одновременно — им нужны разные регистры. Перекрывающиеся lifetimes заставляют spill'ить. В статье приведён пример с методом add_twice и таблицей, где видно, как переменные рождаются и умирают.
Раньше в ZJIT был локальный аллокатор, унаследованный от YJIT. Он видел только один базовый блок за раз. На границах блоков все живые значения приходилось сохранять в стек или фиксированные регистры — дорого и неудобно. Теперь аллокатор глобальный: анализирует весь граф потока управления функции целиком. Это позволяет держать переменную в одном регистре через несколько блоков, избегая лишних загрузок/сохранений. Ещё это открыло путь к оптимизациям вроде method inlining.
Сейчас новый аллокатор уже влит в основную ветку и работает стабильно. Method inlining активно разрабатывается и опирается на глобальное распределение. Остались улучшения: например, lifetime holes — когда значение «живёт» непрерывно от определения до последнего использования, хотя внутри может быть мёртвым на некоторых ветках (как в примере с if). Учёт таких дыр позволит агрессивнее переиспользовать регистры и уменьшить spill'ы. Команда довольна фундаментом и строит дальше.