27/01/2021, Vladimir Kazanov¶
Распределение регистров - одна из старейших проблем построения компиляторов, первые работы по которой появились еще в 50-ые годы прошлого века. Как и в других NP-полных задачах недостатка в эвристических решениях нет. Тем не менее, в последние десятилетия разработчики все чаще используют один из двух глобальных подходов: линейное сканирование в динамических (JIT) компиляторах и раскраску графа в статических (AOT) компиляторах.
В своей диссертации Йозеф Эйсель (Josef Eisl) предлагает новый субглобальный подход к распределению регистров в динамических компиляторах, имеющий в основе следующие наблюдения:
-
Глобальные методы тратят много времени на редко исполняемый (холодный) код.
-
В современных динамически компилируемых языках после агрессивного встраивания функций (inline) появляются большие функции, где много холодного кода.
-
Крупные функции при глобальном охвате занимают много времени.
Выходит, что если сконцентрировать внимание алгоритма на горячих участках в ущерб холодным, то можно за то же время найти эффективное (или даже оптимальное!) распределение на отдельных важных участках кода.
В качестве важных участков Эйсель выбрал непересекающиеся последовательности базовых блоков - трассы (traces). Каждая трасса в зависимости от популярности получает свою политику распределения - быструю и неэффективную, долгую и эффективную, компромиссную или даже специализированную.
Интересно, что схожий подход уже применялся в трассирующих jit-компиляторах, но там трассы компилировались целиком, тогда как у Эйселя трассы выделяются только для распределения регистров.
Эйсель в сотрудничестве с Oracle реализовал подход в GraalVM, нового jit-компилятора для JVM, где тот показал сравнимую с актуальными версиями линейного сканирования производительность порожденного кода при меньшем времени РР. При этом распределение на трассах позволяет искать баланс между временем компиляции и производительностью распределения, а также открывает возможности для параллельной работы над трассами.
В настоящий момент код по умолчанию выключен, но доступен в Java версий от 10 и новее через опции
java -XX:+UnlockExperimentalVMOptions -XX:+UseJVMCICompiler -Dgraal.TraceRA=true
.