автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Методика разработки кодогенерирующей части трансляторов на примере семейства трансляторов с Алгола 68

Санкт-Петербургский государственный университет

РГб оь

2 2 МАЙ ^335 пРавах рукописи

Лаврова Юлия Кимовна

Методика разработки кодогенерирукмцей части трансляторов на примере семейства трансляторов с Алгола 68

05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Санкт-Петербург - 1995

Работа выполнена в Санкт-Петербургском государственном университете.

Научный руководитель: доктор физико-математических наук, профессор Терехов Андрей Николаевич ~ "

Официальные оппоненты:

• доктор технических наук, профессор Осовецкий Леонид Георгиевич

• кандидат физико-математических наук Вдовкин Сергей Валентинович

Ведущая организация - Институт систем информатики СО РАН (г. Новосибирск)

Защита состоится "У" 199 £[_ в час.

мин. на заседании диссертационного совета К 063.57.54 по защите диссертации на соискание ученой степени кандидата физико-математических наук в Санкт-Петербургском государственном университете по адресу: 198904 Санкт-Петербург, Старый Петергоф, Библиотечная пл. 2.

С диссертацией можно ознакомиться в библиотеке Санкт-Петербургского государственного университета по адресу:

199034, Санкт-Петербург, Университетская набережная, 7/9.

Автореферат разослан " !Ь " ^еШ^е 199/г.

Ученый секретарь диссертационного совета

кандидат физ.-мат. наук, доцент Б.К. Мартыненко

Общая характеристика работы

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

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

Целью работы является разработка методов быстрой и эффективной реализации настраиваемого кодогенерирующего просмотра транслятора на основе опыта работы в составе коллектива разработчиков системы программирования \УВС и апробация этих методов на примере создания кодогенерирующих просмотров трансляторов с Алгола 68, входящих в состав \УВС.

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

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

• метод "повторной" трансляции, обеспечивающий эффективное распределение регистров под промежуточные вычисления в пределах ряда конструкций

• метод "условной" трансляции, обеспечивающий распределение регистров в пределах произвольного фрагмента программы

• метод интерпретации таблиц, позволяющий компактно описать проекции конструкций исходного языка в терминах системы команд объектной ЭВМ с учетом различных вариантов реализации конструкции, а затем осуществить выбор оптимального варианта.

Практическая ценность. Практическая ценность данной работы определяется использованием ее результатов в разработке семейства трансляторов с Алгола 68: трансляторы для IBM PC (в операционных системах MS DOS и UNIX), ПС1001, ПСЗООО.

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

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

Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались на семинарах в лаборатории системного программирования НИИ ММ Санкт-Петербургского государственного университета.

Разработанные с применением предложенных методов трансляторы используются в различных промышленных в таких организациях, как НПО "Красная Заря", НПО "Ленинец", НПО "Импульс" и МГП "Терком".

По теме диссертации опубликованы 4 научные работы, не считая программной документации по разработанным средствам.

Методы разработки, предложенные в данной работе, использовались при создании транслятора с Паскаля и Оберона для ЭВМ Самсон.

Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения, библиографии и списка литературы (30 наименований). Объем основной части работы - 95 страниц.

Содержание работы

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

Одной из основных особенностей системы программирования на базе Алгола 68 является ее ориентация сразу на несколько инструментальных ЭВМ. Транслятор разбивается на две фазы: переносимую машино-независимую (общую для всех ЭВМ) и кодогенерирующую, разрабатываемую для каждой целевой ЭВМ в отдельности. При таком подходе существенно сокращаются затраты на разработку транслятора, а основные проблемы реализации сосредотачиваются на фазе генерации кода. Особенно остро встает задача создания кодогенерирующего просмотра, настраивающегося на специфику архитектуры и операционной системы конкретной ЭВМ.

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

Основные проблемы генерации кода связаны с необходимостью порождения оптимального кода программ. Под термином оптимизация объектного кода имеется ввиду построение объектного кода с экономным использованием таких ресурсов ЭВМ, как оперативная память и время центрального процессора. Для оптимизации объектного кода применяются специальные методы и приемы, которые составляют основную часть кодогенерирующих просмотров.

Рассматриваются различные методы оптимизации объектного кода, используемые на фазе кодогенерации, и делаются выводы о целесообразности применения этих методов в трансляторах с Алгола 68.

Во второй главе рассматриваются общие принципы проектирования переносимой системы программирования \УВС и структура семейства трансляторов с Алгола 68 .

Распространение встроенных спецЭВМ из-за нестандартной архитектуры, малой тиражности и жестких ограничений на объем программ приводит к отсутствию развитых инструментальных программных средств (операционных систем, трансляторов, средств отладки и т.п.) для этих ЭВМ. Как правило, разработка и отладка самой спецЭВМ протекает практически одновременно с созданием программного обеспечения для нее, что особенно затрудняет положение разработчиков программного обеспечения. Для таких спецЭВМ оказалось удобным разрабатывать кросс-трансляторы, работающие на инструментальной ЭВМ и генерирующие объектную программу в коды целевой спецЭВМ. Развитая среда инструментальной ЭВМ, особенно при наличии интерпретатора спецЭВМ, создает широкие возможности для отладки прикладного программного обеспечения.

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

В системе программирования \УВС резидентные трансляторы разрабатываются методом "раскрутки" кросс-трансляторов: тексты самого кросс-транслятора, написанные на исходном языке, подаются на вход кросс-транслятору. В результате получается программа -транслятор с исходного языка, работающая на целевой ЭВМ.

Одной из основных особенностей системы программирования \УВС является ее ориентация сразу на несколько целевых ЭВМ. Транслятор разбивается на две фазы: переносимую машино-независимую

(общую для всех ЭВМ) и кодогенерирующую, разрабатываемую для каждой целевой ЭВМ в отдельности.

Далее дается обзор трансляторов системы программирования WBC для разных типов ЭВМ: ЕС ЭВМ, СМ/4, ЭВМ САМСОН, ПС 1001, IBM PC.

В третьей главе дается подробное описание реализаций Алгола 68 для IBM PC, выполненных автором диссертации с применением предлагаемых методов:

• реализация неполного Алгола 68 (1987 - 1990)

• реализация полного Алгола 68 для ОС MS DOS (1991 - 1992)

• реализация полного Алгола 68 для ОС UNIX (1993)

Рассматриваются основные проблемы разработки кодогенери-рующего просмотра:

• выбор структуры объектной программы

• выбор способа распределения памяти в объектной программе

• разработка механизма вызовов процедур

• разработка проекций конструкций исходного языка

• представление значений исходного языка в терминах целевой ЭВМ

• дисциплина работы с регистрами.

Первая версия транслятора с Алгола 68 для IBM PC разрабатывалась в то время, когда основным требованиям к транслятору было требование эффективности порождаемого кода, основным "конкурентом" - транслятор с Паскаля TURBO Pascal версии 3, а основной ЭВМ, на которой велись работы - IBM PC/XT со сравнительно небольшим объемом оперативной памяти. Эти условия и определили основную цель работ: достижение максимальной эффективности порождаемых программ даже за счет ограничений на входной язык и объем программ.

Со временем условия изменились, и возникла необходимость в разработке второй версии транслятора с Алгола 68: 1. Попытка усечения такого сбалансированного языка, как Алгол 68, ни к чему хорошему не привела. Реализация некоторых конструкций

не в полном объеме вызвала появление ошибок в трансляторе при некорректном использовании этих конструкций.

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

3.К тому моменту стали доступны ПЭВМ 80286 и 80386, и стало ясно, что малой модели памяти недостаточно для работы.

4.В Алгол 68 были включены новые конструкции, требующие реализации (модули, исключительные ситуации).

5.Была разработана система динамической поддержки транслятора, позволяющая реализовать в полном объеме работу с динамическими значениями Алгола 68.

6.Был разработан оптимизирующий просмотр, упрощающий работу по реализации кодогенерирующего просмотра.

7. К этому моменту разработчики больших систем на Алголе 68 вплотную подошли к ограничениям на длину кода и объем данных объектной программы.

В рамках работ с итальянской государственной компанией ITALTEL была разработана версия транслятора с Алгола 68 для ОС UNIX. Она отличается использованием непрерывного адресного пространства без разбивки его на сегменты. Это привело к изменению модели объектной программы и к необходимости проводить настройку транслятора заново. Вся работа по созданию кросс-транслятора с применением предложенных в диссертации методов и переносе его способом "раскрутки" в ОС UNIX заняла 4 чел/мес.

В четвертой главе рассматриваются предлагаемые автором методы разработки кодогенерирующего просмотра трансляторов.

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

корректный код объектной программы, и только во-вторых, чтобы генерировать этот код достаточно эффективно.

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

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

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

Следует отметить, что предлагаемые методы не предназначены для решения проблемы оптимизации объектного кода, хотя определенную оптимальность гарантируют. Для оптимизации объектного кода следует применять специальные методы, для этого предназначенные (использование остаточных значений на регистрах, глобальные оптимизации размещения переменных на регистрах и др.).

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

Каждый операнд таких конструкций просматривается дважды: один раз с целью сбора информации об используемых регистрах, а

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

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

В работе приводятся примеры применения метода и дается описание его реализации.

Методу соответствует простая модель данных на Алголе 68. В случае настройки на другую систему команд в этой модели нужно изменить некоторые параметры (число и типы регистров) и соответствующие им примитивы.

К недостаткам метода можно отнести:

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

В зависимости от включения - выключения динамического контроля (контроля вырезки, контроля на NIL) порядок исполнения может меняться, и в том случае, если в программе использовался определенный порядок исполнения совместно исполняемых конструкций, может измениться результат выполнения программы.

На больших формулах метод дает существенную потерю времени трансляции (до 40% от времени работы просмотра генерации кода).

Метод "условной" трансляции применяется для реализации работы с регистрами в пределах любого участка текста программы, где может потребоваться сохранение значений регистров.

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

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

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

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

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

В работе приводятся примеры применения метода и дается описание его реализации.

К недостаткам метода можно отнести: 1. Метод не обеспечивает перестановку операндов конструкций (в отличие от метода "повторной" трансляции).

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

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

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

В данной работе предлагается проекции конструкций (с вариантами) выразить на языке проекций (ЯП), простом и близком к системе команд объектной машины. Для выбора оптимального варианта используется оценочная функция.Генерация кода конструкции при этом состоит в интерпретации записи проекции этой конструкции на ЯП.

Тем не менее, принципиальных ограничений для применения этого метода нет. Успешное применение этого метода для ЭВМ совершенно разной архитектуры (IBM PC и ПС 1001) свидетельствует о его независимости от архитектуры ЭВМ.

В работе приводится описание реализации этого метода и примеры его применения.

Далее в четвертой главе дается описание других локальных и глобальных оптимизаций, применяемых автором при разработке трансляторов семейства WBC:

• оптимизация размещения переменных в памяти (с переиспользованием свободной памяти)

• оптимизация условных и безусловных переходов с целью минимизации их числа и удаления недостижимых участков кода

• оптимизация объектного кода с учетом специфики системы команд

• использование остаточных значений вычислений на регистрах

• оптимизация константных вычислений

В пятой главе диссертации дается описание реализации новых черт Алгола 68. С 1974 года язык Алгол 68 был дополнен новыми конструкциями. К ним относятся модули, исключительные ситуации и динамически сменяемые переменные. Все эти конструкции имеют много общего:

• необходимость выполнения определенных действий в начале блока, содержащего такие конструкции

• необходимость выполнения завершающих действий в конце блока

• трудности, возникающие при выходе из блока переходом на метку (в общем случае статически неизвестно, из скольких блоков на самом деле происходит выход)

Все эти общие проблемы в данной реализации решаются одинаково: создается дерево блоков программы, открытых в текущий момент исполнения.

Дерево блоков одной процедуры представляет из себя статическую (известную во время трансляции) информацию о блочной структуре, увязанную в однонаправленный список с направлением к корню дерева. В этот список попадают только те блоки, которые содержат интересующие нас конструкции (модули, исключительные ситуации и сменяемые переменные).

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

1. Статическая модель реализации модулей предполагает, что действия по подключение модуля производятся во время трансляции. Теоретически это сделать можно, поскольку такое подключение - статическое действие по существу. Этот метод обеспечивает эффективность реализации, но труден в реализации и создает сложности для пользователя: требует перетрансляции всех программ, использующих

модуль в случае несущественных изменений в этом модуле (несущественными называются изменения в описаниях, не доступных пользователю).

Динамическая модель подключения модулей предполагает, что трудности периода трансляции переносятся на этап исполнения объектной программы. Подключение модуля происходит статически только в случае:

когда оно не содержит исполняемой части;

известно, что модуль уже подключен (находится в статической видимости).

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

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

Основные результаты

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

• анализ существующих способов и схем реализации кодогенерирующего просмотра транслятора

• разработка методов реализации кодогенерирующего просмотра транслятора

• разбиение кодогенерирующей части транслятора на два просмотра (кодогенерирующий просмотр и просмотр оформления кода) и распределение функций между ними

• разработка синтаксиса промежуточного языка и временных таблиц для передачи информации между просмотрами кодогенерирующей части

• реализация кодогенерирующих частей семейства переносимых трансляторов

• отработка методов переноса транслятора на другие ЭВМ методом "раскрутки"

В ходе работы над диссертацией автором получены следующие результаты:

1. Разработаны и сформулированы методы работы с регистрами, позволяющие быстро, надежно и эффективно реализовать кодогенерирующий просмотр транслятора

2. Произведен подробный анализ предлагаемых методов, их достоинств, недостатков и границ их использования в разработках.

3. На основе предложенных методов разработан и реализован комплекс инструментальных средств, охватывающий весь цикл работ по генерации кода объектной программы.

4. Разработанные инструментальные средства успешно применены при создании нескольких трансляторов: транслятор с Алгола 68 для IBM PC (три версии), кросс-транслятор с Алгола 68 для ПС1001. На базе предложенных в диссертации методов в Молдавии был разработан транслятор с Паскаля и Оберона для ЭВМ Самсон.

5. Выполнен перенос кросс-транслятора с Алгола 68 на IBM PC в среду MS DOS и кросс-транслятора с Алгола 68 для MS DOS в среду ОС UNIX.

Разработанные с применением предложенных методов трансляторы используются в различных промышленных организациях: НПО "Красная Заря", НПО "Ленинец", НПО "Импульс" и МГП "Терком".

Список работ автора по теме диссертации

[1] Лаврова Ю.К. Сравнение реализации Алгола 68 и ПАСКАЛЯ на ПЭВМ типа IBM PC. "Адаптируемые средства программирования. Методы оценки трансляторов." - материалы школы-семинара. Кишинев, 1989, с. 81-84.

[2] Лаврова Ю.К. Алгол 68 для IBM PC. "Информатика и программирование" - сборник научных трудов. Новосибирск, ВЦ СО АН СССР, 1989,с. 121-124.

[3] Лаврова Ю.К. Способы упрощения синтезирующей части компиляторов. "Дискретные системы и их программное обеспечение", Ленинград: Л.: ЛГУ, 1990, с. 92-96.

[4] Лаврова Ю.К. Реализация Алгола 68 для персональных компьютеров, совместимых с IBM PC. "Программное оснащение персональных компьютеров", М.: МГУ, 1990, с. 74-77.