В своей диссертации Йозеф Эйсель (Josef Eisl) предлагает новый субглобальный подход к распределению регистров в динамических компиляторах, имеющий в основе следующие наблюдения:
1. Глобальные методы тратят много времени на редко исполняемый (холодный) код.
2. В современных динамически компилируемых языках после агрессивного встраивания функций (inline) появляются большие функции, где много холодного кода.
3. Крупные функции при глобальном охвате занимают много времени.
Выходит, что если сконцентрировать внимание алгоритма на горячих участках в ущерб холодным, то можно за то же время найти эффективное (или даже оптимальное!) распределение на отдельных важных участках кода.
В качестве важных участков Эйсель выбрал непересекающиеся последовательности базовых блоков - трассы (traces). Каждая трасса в зависимости от популярности получает свою политику распределения - быструю и неэффективную, долгую и эффективную, компромиссную или даже специализированную.
Интересно, что схожий подход уже применялся в трассирующих jit-компиляторах, но там трассы компилировались целиком, тогда как у Эйселя трассы выделяются только для распределения регистров.
Эйсель в сотрудничестве с Oracle реализовал подход в GraalVM, нового jit-компилятора для JVM, где тот показал сравнимую с актуальными версиями линейного сканирования производительность порожденного кода при меньшем времени РР. При этом распределение на трассах позволяет искать баланс между временем компиляции и производительностью распределения, а также открывает возможности для параллельной работы над трассами.
В настоящий момент код по умолчанию выключен, но доступен в Java версий от 10 и новее через опции
java -XX:+UnlockExperimentalVMOptions -XX:+UseJVMCICompiler -Dgraal.TraceRA=true.
https://ssw.jku.at/General/Staff/Eisl/papers/phdthesis.pdf
#registerallocation #trace #graalvm #jvm