Самый ранний и задавший главные направления исследований в области компиляторов проект это, безусловно, оптимизирующий компилятор языка Fortran I. Работы над ним велись в середине 1950-х и примененные в компиляторе техники устарели, но, например, остроумный механизм распределения регистров продержался в Fortran еще много лет.

Распределение регистров в Фортране 1 проводится в два этапа. На вход первого этапа поступает список инструкций, использующих неограниченное число символьных регистров. Список разбивается на базовые блоки, то есть строится граф потока исполнения. При этом во всех ветвлениях (IF, вычисляемых GOTO) программисты на языке должны были сами (!) расставить вероятность перехода по каждой из ветвей. Вероятности впоследствии используются для моделирования частоты базовых блоков метдом Монте-Карло.

Во втором этапе, начиная от самого "горячего" из оставшихся необработанных блоков, строится регион, внутри которого будет проводится распределение регистров. Регион расширяется самым горячим из соседних базовых блоков до тех пор, пока не упирается в другие регионы или начало/конец графа. Специальным образом обрабатывается закольцованные регионы, то есть циклы.

Само выделение регистров происходит внутри каждого такого региона; при необходимости вытесняются регистры, наименее востребованные в оставшейся части региона (например, мертвые).

Материалы для интересующихся историей компиляторов:

https://www.cs.fsu.edu/~lacher/courses/COT4401/notes/cise_v2_i1/fortran.pdf - краткий современный обзор компилятора

http://archive.computerhistory.org/resources/text/Fortran/102663113.05.01.acc.pdf - оригинальная публикация 1957-го года.

#history #fortran #registerallocation