13/01/2021, Vladimir Kazanov¶

BLISS - один из самых ранних портативных языков для системного программирования, первая версия которого (BLISS-10) была выпущена для PDP-10 еще в 1970-ом году. Наиболее широкое применение язык нашел во внутренних разработках компании DEC, где на BLISS вплоть до 90-х создавались компиляторы, операционные системы и низкоуровневые утилиты.

Но прославился этот язык благодаря версии для PDP-11, вышедшей в 1975 году. Компилятор BLISS-11 был на голову выше конкурентов вроде ранних компиляторов C и поражал воображение разработчиков (“we’d sit and chuckle at what it had done”). Реализацию описывали несколько диссертаций (одна из них - за авторством будущего основателя Adobe) и книга. Пример инновационности BLISS-11 - анализ жизни переменных в применении к глобальному распределению регистров.

Книга описывает собственный подход к анализу областей жизни переменных (потому что “no truly satisfactory solution exists in the literature”). Найденные области обозначались каждая двумя координатами в двухмерном пространстве. Координаты задавали вершины прямоугольников. Если области-прямоугольники времени жизни переменных пересекались, то такие области не должны были оказываться в одном регистре.

Каждая переменная получала рейтинг на основе расположения в коде (напр. глубины вложения циклов) и размера области жизни (меньше - лучше). Переменные сортировались по рейтингу, и за один проход одна за другой сопоставлялись с регистрами, если только при этом не случалось пересечения с уже сопоставленными с регистром переменными.

Позже эта проблема была сведена к NP-сложной задаче об упаковке в контейнеры; и в следующих версиях BLISS разработчики развили подход в семейство алгоритмов binpacking, к которым относится и популярный алгоритм линейного сканирования.

С закатом DEC зашла и звезда BLISS. Но в истории компиляторов реализация языка оставила значимый след: книга The Design of an Optimizing Compiler (1975) стала классикой, и без BLISS любое обсуждение истории компиляторов будет неполным.

Wulf, W.A., 1975. The design of an optimizing compiler.

Brender, Ronald F. 2002. The BLISS programming language: a history

#bliss #history #registerallocation

08/01/2021, Vladimir Kazanov¶

Некоторые разработки получают известность не в силу новаторских решений, а благодаря качественной инженерной работе и удобной сопроводительной документации. Пример - портативный компилятор lcc, ставший прообразом 8cc, chibicc, tcc и других свободно доступных небольших компиляторов.

Разработчики lcc задались целью сделать не просто полноценный компилятор языка Си, но еще и подробно документированный: проект написан в стиле “литературного программирования” Д.Кнута, когда код интегрирован в документацию (а не наоборот).

Более того, из такого “художественного” исходного кода можно собрать полноценную книгу, изданную под названием A Retargetable C Compiler: Design and Implementation. Вместе с книгой для разъяснения ключевых технических решений авторы опубликовали статьи, посвященные, например, распределению регистров и порождению кода.

lcc можно отнести к промежуточному варианту между простыми компиляторами, описываемыми в популярных книгах для программистов, и серьезными оптимизирующими компиляторами. Здесь есть внутреннее представление (лес ациклических графов внутри базовых блоков графа потока исполнения), используются отдельные популярные оптимизации.

Характерное для компилятора решение - распределение регистров. Оно локальное и восходящее, то есть проводится внутри базового блока проходом по списку инструкций. Регистры один за другим выделяются под значения до тех пор, пока не приходится искать значение для вытеснения в память. Вытесняются те значения, следующее использование которых в списке инструкций находится дальше всего.

В результате компилятор был портирован на множество платформ, стал основой для бесчисленных форков и даже использовался для скриптования популярного игрового движка id Tech 3 (см. Quake 3 Arena) компании idSoftware.

https://en.wikipedia.org/wiki/LCC_(compiler)

https://github.com/drh/lcc

https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.57.2519&rep=rep1&type=pdf

https://en.wikipedia.org/wiki/Id_Tech_3

#history #lcc #registerallocation

07/01/2021, Vladimir Kazanov¶

Самый ранний и задавший главные направления исследований в области компиляторов проект это, безусловно, оптимизирующий компилятор языка 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-го года.

#fortran #history #registerallocation

26/11/2020, Vladimir Kazanov¶

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

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

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

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

#linearscan #history #registerallocation

22/05/2020¶

Возможно, вы уже слышали новость о древнем GW-BASIC. Компания Microsoft выложила исходники интерпретатора на github: https://devblogs.microsoft.com/commandline/microsoft-open-sources-gw-basic/

В заметке по ссылке есть одна интригующая фраза: “Microsoft was able to generate a substantial amount of the code for a port from the sources of a master implementation. (Alas, sorry, we’re unable to open-source the ISA translator.)”. И действительно, текст на языке ассемблера для 8088 был получен автоматически с помощью специального транслятора. При этом даже комментарии в коде остались нетронутыми, там речь идет, судя по всему, о 8080.

В статье из журнала Byte за 1982 год сравниваются возможности трех трансляторов, которые автоматически преобразуют код 8-битных процессоров 8080/Z80 для CP/M в 16-битный код 8088/8086 для MS-DOS: https://tech-insider.org/personal-computers/research/acrobat/8206-b.pdf

Особенно выделяется среди этих трансляторов XLT86 (8080 -> 8086) от компании Digital Research. Этот транслятор — детище Гэри Килдалла, о котором специально говорить, наверное, нет необходимости. В области построения компиляторов Килдалл известен своей работой A unified approach to global program optimization (1973): https://dl.acm.org/doi/pdf/10.1145/512927.512945

Статья Килдалла до сих пор находится в числе самых цитируемых по компиляторной тематике и речь идет об алгоритме анализа потока данных, который позже был описан во множестве учебников и применяется в самых современных компиляторах: http://compcert.inria.fr/doc-1.6/html/Kildall.html

Вернемся, однако, к XLT86. К счастью, сохранилась документация к транслятору: http://www.s100computers.com/Software%20Folder/Assembler%20Collection/Digital%20Research%20XLT86%20Manual.pdf

Из нее можно узнать, в частности, что:

Трансляция состоит из 5 фаз.
В начале определяются линейные участки и строится граф потока управления. Затем проводится глобальный анализ потока данных для определения “живых” регистров и флагов процессора.
Сам процесс “выбора команд” элегантно описан табличным образом. Некоторые правила преобразований являются условными и зависят от ранее полученных результатов анализа потока данных.
Транслятор написан на ЯП PL/I-80 и имеет ограничение на размер входной программы — не более 6 Kбайт.

#analysis #history