27/11/2020, Vladimir Kazanov¶
Популярный алгоритм распределения регистров линейным сканированием (Linear Scan Register Allocation, 1999) определен на живых интервалах (live intervals) и линейном списке инструкций. Построение и хранение списка интервалов в виде пар индексов инструкций занимает время и память, поэтому исследователи продолжали искать возможность не строить явно список интервалов.
Авторы Efficient Global Register Allocation (2020) предложили алгоритм из того же семейства, но определенный на графе потока исполнения (control flow graph). Ключевые идеи здесь две:
-
Список живых интервалов здесь отслеживаются неявно, на каждом из базовых блоков и инструкций внутри блоков.
-
Проход по отдельным инструкциям позволяет не только не строить в явном виде интервалы, но и высвобождать временно регистры внутри блоков, что решает проблему “пустот в живости” (liveness holes).
Алгоритм сравним по производительности порожденного кода с актуальными реализациями линейного сканирования, немного выигрывая в ресурсах на этапе компиляции. Из работы следует, что основное преимущество подхода заключается в возможностях специальных оптимизаций.
В настоящий момент этот вариант линейного сканирования используется при порождении регистрового байткода dex для виртуальной машины ART, используемый в Android.
https://arxiv.org/pdf/2011.05608.pdf
#art #registerallocation #android #dex #linearscan
26/11/2020, Vladimir Kazanov¶
Распределение регистров - краеугольная задача любого порождающего машинный код компилятора. В работе Linear Scan Register Allocation (1999) был представлен один из двух популярнейших алгоритмов распределения регистров.
По сравнению с алгоритмами на основе раскраски графов алгоритм линейного сканирования отличается простотой в реализации, высокой скоростью работы самого алгоритма и эффективностью выходного кода. Авторы пишут, что даже простейший вариант алгоритма, представленный в публикации, порождает код, лишь немного уступающий в производительности алгоритмам на основе раскраски графов.
Благодаря своим свойствам алгоритм стал стандартным решением в динамических (just-in-time) и легковесных компиляторах.
Из известных компиляторов линейное сканирование используется, например, в luajit или Hotspot.