Распределение регистров - краеугольная задача любого порождающего машинный код компилятора. В работе Linear Scan Register Allocation (1999) был представлен один из двух популярнейших алгоритмов распределения регистров.

По сравнению с алгоритмами на основе раскраски графов алгоритм линейного сканирования отличается простотой в реализации, высокой скоростью работы самого алгоритма и эффективностью выходного кода. Авторы пишут, что даже простейший вариант алгоритма, представленный в публикации, порождает код, лишь немного уступающий в производительности алгоритмам на основе раскраски графов.

Благодаря своим свойствам алгоритм стал стандартным решением в динамических (just-in-time) и легковесных компиляторах.

Из известных компиляторов линейное сканирование используется, например, в luajit или Hotspot.

#history #registerallocation #linearscan