Михаэль Франц
"Динамическая кодогенерация: ключ к разработке переносимого программного обеспечения"
(c) 1998, ИнфоАртMichael Franz
Перевод на русский язык и публикация с разрешения автора
"Code-Generation On-the-Fly: A Key for Portable Software"
Zurich, Dissertation No.10497.
(c) 1994, M.Franz
СОДЕРЖАНИЕСведения об авторе
Михаэль Франц (Michael Franz) — ныне профессор компьютерных наук в университете Калифорнии в Ирвине (University of California at Irvine). Ранее работал ведущим исследователем (Senior Research Associate) в группе Никлауса Вирта в ETH (Цюрих). Будучи одним из первых коллег Н.Вирта по проекту Oberon, он внес значительный вклад в развитие этой технологии. М.Франц является автором ETH-реализации системы Oberon для Apple Macintosh. Профессиональный интерес профессора Франца сосредоточен на двух областях. Первая — это языки программирования и их реализация, а вторая — расширяемые системы, включая программную архитектуру таких систем, компонентное программное обеспечение (componentware) и переносимое программное обеспечение, способное мигрировать по компьютерным сетям.Аннотация
В настоящей диссертации предлагается метод представления программ в виде абстрактном и независящим от возможной целевой архитектуры, который позволяет получить представление файлов в два раза более компактное, нежели машинный код для CISC-процессора. Этот метод лег в основу реализованной автором системы, в которой процесс кодогенерации откладывается до этапа загрузки. В этот момент загрузчик с динамической кодогенерацией и порождает машинный (native) код.При динамической кодогенерации процесс загрузки протекает настолько быстро, что на него уходит лишь чуть больше времени, нежели на ввод эквивалентного машинного кода из дискового запоминающего устройства. Это объясняется главным образом компактностью абстрактного представления программы: дополнительное время, потраченное на кодогенерацию, компенсируется за счет сокращения времени ввода. Поскольку мощность процессоров растет в настоящее время быстрее, нежели сокращаются время доступа к диску и скорость передачи данных, есть основания полагать, что по мере дальнейшего развития технологии производства аппаратных средств предлагаемый метод станет еще более конкурентоспособным.
Пользователи реализованной системы могут теперь работать с модулями в абстрактном представлении с той же легкостью, что и с обычными объектными файлами. В этой системе представления файлов обоих типов сосуществуют; они полностью взаимозаменяемы, и модули в любом представлении могут импортировать данные из модуля другого типа. Реализована полная поддержка раздельной компиляции (separate compilation) программных модулей с интерфейсами, обеспечивающими контроль типов, а также помодульная динамическая загрузка (dynamic loading).
Задержка кодогенерации до этапа загрузки открывает ряд новых возможностей, особенно в тех случаях, когда промежуточное представление программы не зависит от используемой машины и является таким образом переносимым. В диссертации показано, что сочетание переносимости и практичности представляет собой важный шаг на пути к индустрии программных компонент (software-component industry). Среди других преимуществ нового метода — возможность сокращения числа повторных компиляций при внесении изменений в исходный текст, а также механизм, позволяющий определять, следует ли динамически проверять на целостность библиотечный модуль (это избавляет от необходимости различать конфигурации библиотек, предназначенных для разработки программных продуктов). Есть все основания полагать, что эти новые возможности приведут к сокращению издержек по проектированию и эксплуатации программного обеспечения.
Не исключено, что в перспективе переносимость программного обеспечения на различные процессоры, реализующие одну и ту же архитектуру, будет достигаться уже не за счет бинарной совместимости, а с помощью быстрой динамической кодогенерации. Ведь уже сегодня различные модели семейства процессоров все сильнее отличаются друг от друга, так что одинаково успешно работать с ними, применяя лишь одну версию машинного кода, становится все труднее. Если же код генерируется лишь во время загрузки, его всегда можно "подогнать" под конкретный процессор, на котором он в конечном счете и будет работать.
Ключевые слова
Динамическая кодогенерация, SDE-технология, семантический словарь, абстрактные машины, абстрактное синтаксическое дерево.БЛАГОДАРНОСТИ
Я глубоко признателен профессору Никлаусу Вирту (Niklaus K. Wirth) за выпавшее на мою долю счастье работать рядом с ним. На протяжении многих лет он одаривает меня сокровищами мудрости, которые помогают и будут помогать мне в течение всей моей профессиональной жизни, да и после ее окончания. Я искренне преклоняюсь перед его редким даром мгновенно выделять существенную сторону явлений и перед тем мужеством, с которым он отказывается от всего лишнего и наносного, даже когда другие считают отброшенные им вещи просто незаменимыми. Довольно часто я пытаюсь следовать в своей работе его принципам суждений — и результаты таковы, что ими нельзя не восхищаться. Я сердечно признателен ему за внимательную опеку моей диссертации и за те компетентные замечания к проводимому проекту, что мне довелось от него слышать.Я благодарен профессору Юргу Гуткнехту (Juerg Gutknecht) за его согласие быть еще одним научным консультантом (co-examiner) моей диссертации и за помощь в ее подготовке. Он поистине великий педагог, и если содержание моей работы покажется вам четким и понятным, то это целиком и полностью его заслуга, это результат его критических замечаний на ранней стадии проекта, после которых диссертация унаследовала его непревзойденный стиль изложения.
Я выражаю признательность моим коллегам из Института компьютерных систем (Institute for Computer Systems) в Цюрихе за их готовность к восприятию новых идей и за тот энтузиазм, с которым они участвовали в их обсуждении, даже хотя наши дискуссии нередко заканчивались далеко за полночь. Благодаря всем им создалась настоящая рабочая атмосфера дружбы и интеллектуального творчества.
В заключение мне хочется выразить свою благодарность Пфистеру (C.Pfister) и Людвигу (S.Ludwig) за их внимательное прочтение моей диссертации.
1. Введение
1. ВВЕДЕНИЕ
2. Представление программ
3. Кодер и декодер для SDE-представления
4. Модульный проект реализации
5. Результаты тестирования
6. Переносимость и программные компоненты
7. Последующие приложения
8. Смежные работы
9. Резюме и заключение
Быстрое развитие аппаратной технологии оказывает постоянное влияние на разработку программного обеспечения, и это ведет как к положительным, так и к отрицательным последствиям. Случается, что быстродействие аппаратных средств маскирует изъяны и стоимость неудачно спроектированных программ. Рейзер [Rei89] не так уж далек от истины, когда замечает, что иногда "программы замедляют свою работу быстрее, чем ускоряется быстродействие аппаратуры". С другой стороны, усовершенствования в аппаратных средствах, такие, как увеличение объема памяти и повышение быстродействия процессоров, обеспечивают возможность создания более совершенных программ.
Достаточно часто появление аппаратуры более высокого качества имеет своим косвенным следстием принципиально новые методические решения. Взять хотя бы такие приемы программной инженерии, как инкапсуляция информации (information hiding) и абстрактные типы данных (abstract data types). Их просто нельзя было разработать до того, как компьютеры стали настолько мощными, что смогли поддерживать компиляторы для модульных языков программирования. Механизмы, подобные раздельной компиляции, также предъявляют определенные требования к используемому оборудованию, и они тоже смогли получить распространение лишь после того, как повсюду стали применяться достаточно мощные компьютеры.
В диссертации представлен пример еще одного новаторского решения в области систематической технологии (systematic technological advance), реализация которого стала возможной благодаря усовершенствованию аппаратных средств. В ней описывается метод представления программ в абстрактном виде — в формате, в два раза более компактном, нежели объектный код для CISC-процессора. Применение промежуточного представления программ с помощью нового метода в сочетании с быстродействием современных процессоров и большим объемом основной памяти позволяет столь существенно ускорить процесс кодогенерации, что он может совершаться "на лету" в ходе загрузки программы в память обычного настольного компьютера, причем с получением высококачественного кода.
Автором реализована система, позволяющая оперировать программными модулями в промежуточном машинно-независимом представлении "со всеми удобствами" — как если бы они были транслированы в машинный код. В диссертации утверждается, что такая система открывает несколько абсолютно новых возможностей, в числе которых — перспектива создания целой индустрии, производящей компоненты программного обеспечения непосредственно для пользователей, причем компоненты эти можно применять непосредственно на нескольких типах целевой архитектуры.
Среди тем, к которым диссертант многократно обращается в данной работе, — методы представления программ, кодогенерация, модульное программирование (modular programming) и переносимость программного обеспечения. Этот достаточно широкий для докторской диссертации круг проблем нашел свое отражение в объемном списке литературы, включающем самые разнообразные источники.
2. ПРЕДСТАВЛЕНИЕ ПРОГРАММДля каждой вычислимой функции (calculable function) существует алгоритм ее вычисления [Chu36]. А программа — это закодированное описание такого алгоритма, дающее универсальной вычислительной машине указание на вычисление соответствующей функции. Машина именуется универсальной в том случае, если она позволяет вычислить любую функцию, которую можно представить с помощью алгоритма; возможность существования таких универсальных машин показана еще Тьюрингом [Tur37]. Языки программирования соответствуют абстрактным и относительно сложным универсальным машинам, тогда как цифровые компьютеры (digital computers) представляют собой физическую реализацию универсальных машин, которые можно программировать с помощью характерных для этих компьютеров машинных языков.
Алгоритмы могут транслироваться из одного представления программы в другое; само существование некоторого алгоритма свидетельствует о возможности создания соответствующей программы для любой универсальной машины. В этой главе обсуждается применение промежуточных языков в качестве переходных шагов в таких трансформациях между представлениями программ, в особенности — решений, основанных на абстрактных машинах. Затем в ней вводится новый метод представления программ, именуемый кодированием на основе семантического словаря (semantic-dictionary encoding). Этот метод позволяет добиться высокой информационной плотности и одновременно облегчает дальнейший эффективный перевод на различные машинные языки.
Декомпозиция компиляторовЧасто (и по самым разным причинам) компиляторы разделяют на более мелкие элементы. Это может быть статическое разделение на модули, либо динамическое разделение на две и более фазы компиляции (или прохода), выполняющиеся друг за другом. На такое разделение часто приходится идти из-за физических ограничений инструментального компьютера, не позволяющих создать монолитный компилятор. Однако декомпозиция компилятора на более мелкие элементы дает и другие преимущества, которые делают этот подход привлекательным, даже если он и не диктуется внешними ограничениями. Привлекательность его сохраняется даже тогда, когда упомянутые органичения в конце концов устраняются с развитием аппаратной технологии.
Наиболее важное обстоятельство состоит в том, что разделение компилятора обычно приводит к его упрощению. Ведь отдельные элементы меньше и, следовательно, проще, нежели целое, а все части, взятые вместе, по сложности зачастую уступают соответствующему монолитному компилятору. Объясняется это тем, что различные части, как правило, довольно легко отделяются друг от друга, и в результате между ними образуются узкие интерфейсы. С другой стороны, сложность концентрируется, главным образом, в нелокальных зависимостях.
Еще один довод в пользу структурирования компилятора — это та легкость, с которой его можно перенацеливать на другую архитектуру. Отделив кодогенерирующие функции от остальной части компилятора, мы можем существенно упростить создание семейства компиляторов для различных целевых архитектур. И тогда для адаптации компилятора к новой целевой машине достаточно будет создать новый кодогенератор, а в остальных частях компилятора ничего менять не придется. К слову, этот метод стал настолько распространенным, что мы сегодня часто говорим о "кодогенераторах", как если бы они сами по себе были полноценными программами, совершенно забывая о том, что в первых компиляторах синтаксический анализ и кодогенерация не были отделены друг от друга.
Промежуточные языкиКомпилятор преобразует программу из одного представления в другое. Когда такой компилятор состоит из нескольких фаз, то это подразумевает наличие еще нескольких промежуточных представлений (intermediate representations), переносящих состояние компиляции из предыдущей фазы в последующую. Как правило, эти промежуточные представления — всего лишь переходные структуры данных в памяти, но в отдельных компиляторах они имеют линейную форму, которая может быть отражена в файле данных. В последующем изложении такие особые линейные представления именуются промежуточными языками (intermediate languages).
Промежуточные языки представляют интерес с точки зрения переносимости программного обеспечения на различные компьютеры. Если промежуточный язык достаточно прост, можно без труда создать несколько интерпретаторов, способных непосредственно работать с этим языком на ряде различных целевых машин. Этот подход представляет интерес, ибо вообще говоря, интерпретаторы проектировать легче, нежели кодогенераторы. Правда, за простоту реализации здесь приходится платить ухудшением рабочих характеристик. В числе систем, реализованных на основе интерпретируемых таким образом промежуточных языков, можно назвать BCPL [Ric71, RiW79], SNOBOL4 [Gri72] и Pascal [NAJ81].
Кроме того, промежуточные языки часто используются в процессе первоначальной загрузки компиляторов на новые машины [Hal65]. Допустим, унас есть переносимый компилятор, который транслирует входной язык SL (Source Language) на промежуточный язык IL (Intermediate Language) и что этот компилятор сам написан на SL, а закодирован как на SL, так и на IL. Допустим далее, что мы располагаем интерпретатором для языка IL, который выполняется на компьютере с машинным языком TL (Target Language). Тогда мы сможем, модифицировав переносимый компилятор (написанный на SL), получить чистый компилятор, транслирующий прямо с SL на TL. Скомпилировав его с интерпретируемой версией первоначального компилятора, мы получим чистый компилятор, написанный на языке IL и, таким образом, выполнимый для данного интерпретатора. Теперь с помощью этого компилятора можно создавать чистый компилятор, способный выполняться непосредственно на целевой машине (см.рис.2.1).
Каждый контур в форме буквы T представляет компилятор, написанный на этом языке и транслирующий с этого языка на этот ввод вывод Исходная язык компиляции компиляции ситуация SL IL SL IL SL IL производный вариант SL TL SL Первая SL SL IL IL Компиляция IL интерпретируемое выполнение SL TL SL TL Вторая SL SL TL TL Компиляция IL интерпретируемое выполнениеРис. 2.1: Начальная загрузка компилятора
Универсальный язык UNCOLВ 50-х годах стало очевидно, что тенденция к росту числа языков программирования и типов аппаратных архитектур еще какое-то время сохранится. А это, соответственно, вызовет большой спрос на различные компиляторы, поскольку для каждой комбинации входного языка и целевой архитектуры потребуется отдельный компилятор.
Иными словами, можно было ожидать настоящего комбинаторного взрыва, и в этой обстановке родилась идея "языкового коммутатора" (linguistic switchbox), которая и была материализована в 1958 г. [SWT58, Con58, Ste60, Ste61a]. Замысел состоял в том, чтобы разработать некий универсальный промежуточный язык, на который с помощью соответствующего генератора (front-end, если пользоваться нынешней терминологией) можно было бы транслировать программы, написанные на любом проблемно-ориентированном языке и с которого при помощи подходящего транслятора (back-end) можно было бы генерировать код для любой акрхитектуры процессора. В этом случае (если принять число языков за "m", а число машин, на которых компиляторы должны работать, — за "n"), для компиляторов уже не пришлось бы писать m*n программ. Можно было бы обойтись гораздо меньшим их числом - всего m+n, то есть m-программ для front-end частей системы, и n-программ — для back-end частей (см.рис.2.2). Для этого промежуточного языка было выбрано имя UNCOL, что означает "универсальный машинно-ориентированный язык" (universal computer-oriented language).
SL1 SL2 SLm Входные языки FE1 FE2 ... FEm Front-Ends UNCOL Универсальный язык BE1 \ BE2 ... BEn Back-Ends TL1 TL2 ... TLn Целевые языки Рис. 2.2 Язык UNCOL в качестве языкового коммутатора
Разумеется, может возникнуть вопрос, почему подобный промежуточный язык надо обязательно проектировать специально для этой цели. Ведь если алгоритмы могут транслироваться из одного представления программы в другое, тогда в принципе в качестве языка UNCOL может выступать машинный язык любого достаточно мощного компьютера. К сожалению, однако, трансляции с языка на язык в большинстве случаев настолько трудны, что на практике этим методом пользоваться невозможно. То есть, кандидаты на звание языка UNCOL должны быть легко и эффективно реализуемыми. Они должны также допускать дальнейшее развитие как входных, так и целевых языков. Стил (Steel) [Ste61b] приводит пример гипотетического языка UNCOL, созданного до изобретения индексных регистров. Он оказался очень неудобным при работе с теми программами, которые оперировали массивами.
По сей день ни один из кандидатов на звание универсального машинно-ориентированного языка так и не получил всеобщего признания. Однако дух языка UNCOL по-прежнему живет во многих семействах компиляторов, где посредством общих промежуточных представлений реализованы различные комбинации front-end частей и back-end частей. Более того, определенные языки программирования реализованы на столь многочисленных различных архитектурах, что они практически достигли статуса универсального языка. Так, почти повсеместное распространение получил язык программирования C [KeR78]. Аткинсон (Atkinson) и его коллеги [ADH89] описывают компилятор языка Cedar, переносимость которого достигается за счет высокоуровневой трансляции "источник-источник" (source-to-source), дающей на выходе код на языке C. Получающиеся таким образом программы затем непосредственно передаются на компилятор языка C без какого-либо дальнейшего редактирования. В данном контексте эти программы выступают лишь как промежуточные представления.
Абстрактные машиныОдин из наиболее простых способов представления программы на промежуточном языке состоит в том, чтобы представить ее как последовательность команд для некоторого воображаемого компьютера, иначе именуемого абстрактной машиной (abstract machine) [PoW69, NPW72, KKM80]. Именно такая схема реализована в большинстве промежуточных языков, включая самый первый из предложенных универсальных машинно-ориентированных языков [Con58].
Помимо абстрактных машин, в качестве основы для промежуточных языков выступают также линеаризованные деревья синтаксического разбора [GaF84,DRA93a]. К тому же, существуют еще и компиляторы, которые работают через обычные языки программирования высокого уровня уже упоминавшимся методом трансляции "источник-источник" [ADH89].
Пик популярности абстрактных машин пришелся на начало 70-х годов. Десять лет они широко использовались повсюду, обеспечивая переносимость программ на ряд целевых архитектур и потребляя при этом весьма скромные ресурсы. Некоторые типы архитектуры появлялись на свет в виде абстрактных машин и лишь позднее благодаря своей популярности были реализованы физически или в микрокоде. Среди наиболее известных абстрактных машин этого периода можно назвать следующие.
BCPL. BCPL [Ric69] представляет собой компактный, состоящий из блоков язык программирования, предназначенный, главным образом, для системного программирования. В нем предусмотрен лишь один тип данных, Rvalue, которому язык придает различные интерпретации в зависимости от совершаемой операции. Каждый экземпляр типа Rvalue занимает единицу памяти идеального объектного компьютера (idealized object computer), видимую на уровне входного языка. Данная реализация BCPL [Ric71, RiW79] основана на абстрактной стековой машине. Семантическая модель BCPL без типов на идеальном компьютере допускает переносимую адресную арифметику в исходных программах и не зависимое от целевой машины управление стеками в компиляторе.
SNOBOL4. SNOBOL4 входит в семейство обрабатывающих знаковые строки языков SNOBOL [Gri81]. Первоначально был реализован [Gri72] на безрегистровой абстрактной машине, предусматривающей только команды "память-память". Основная единица данных, обрабатываемых такой машиной, называется дескриптор (descriptor). Внутри дескрипторов кодируются все типы данных языка SNOBOL4. Однако внутренний формат дескрипторов зависит от типа целевой архитектуры, что позволяет эффективно реализовывать данный интерпретатор на различных типах аппаратных средств, но требует внесения изменений в компилятор SNOBOL4 всякий раз, когда система переносится на другую аппаратуру.
Pascal-P. Универсальный язык программирования Pascal [Wir71] широко используется и по сей день. Pascal-P, одна из его ранних реализаций, основан на гипотетическом стековом компьютере, подобном абстрактной машине, которая использовалась при реализации BCPL. Но в отличие от BCPL Pascal различает несколько типов данных. В реализации Pascal-P представления этих типов на абстрактной машине (в плане их требований к памяти и выравниванию на границу блока памяти (alignment) адаптируются применительно к целевой архитектуре. Как и в случае с реализацией языка SNOBOL4, эта зависимость от целевой архитектуры препятствует прямой переносимости промежуточного языка, но зато обеспечивает эффективное распределение памяти и работу интерпретатора.
Janus. В отличие от трех приведенных выше примеров, где для реализации одного входного языка на ряде целевых архитектур используется абстрактная машина, Janus определяет главные параметры промежуточного языка независимо от входного языка или целевой архитектуры, и тем самым он ближе подходит к первоначальной идее универсального машинно-ориентированного языка UNCOL. Janus не опирается на одну абстрактную машину, а описывает основные черты общей структуры (стековая машина с индексным регистром) целого семейства абстрактных машин, отличающихся друг от друга наборами команд, которые применяются для обработки конкретных конструкций входных языков. Janus успешно использовался при проектировании компиляторов для языков программирования Pascal [Wir71] и Algol-68 [WMP69]. Появление персональных компьютеров привело в конце концов к закату эры абстрактных машин, поскольку оно означало фактическую стандартизацию машинного языка на компьютерах с низкой производительностью, которые стали доступны широким слоям пользователей. В свете квазистандартного машинного языка, больше не было нужды применять промежуточные языки для достижения переносимости программного обеспечения, тем более что интерпретированное выполнение абстрактных машин ассоциировалось с неэффективностью.
И только сейчас ситуация вновь начинает меняться. Хотя процесс стандартизации аппаратного обеспечения продолжается вот уже два последних десятилетия (так что теперь остается лишь десяток важных типов архитектур, на которые нужно переносить программное обеспечение), популярность традиционной бинарной совместимости идет на спад. Объясняется это тем, что различные реализации одной и той же архитектуры становятся настолько непохожими друг на друга, что генерировать машинный код, хорошо выполняемый на всех процессорах внутри одного семейства, становится все труднее и труднее. В диссертации предлагается альтернатива: динамическая кодогенерация в период загрузки (речь об этом пойдет в одной из следующих глав). Таким образом, каждый процессор получает оптимизированные последовательности команд, а работать при этом так же удобно, как и при использовании метода бинарной совместимости.
Недостатки абстрактных машинАбстрактные машины часто задают на основе формирования концептуальных пересечений архитектур потенциальных целевых машин. Следовательно, промежуточные языки, основанные на абстрактных машинах, по самой своей природе ближе к машинным языкам, чем к языкам программирования высокого уровня. К сожалению, из этого вытекает нежелательное следствие, состоящее в том, что представление алгоритма, полученное на основе абстрактной машины, менее структурировано, нежели соответствующая исходная программа. Большинство абстрактных машин в состоянии описывать лишь алгоритмические аспекты вычисления. Они не могут корректно сохранять всю информацию более высокого порядка, которая выражена в программах, написанных на языках высокого уровня, в частности, блочную структуру и контроль типов данных.
Рассмотрим для примера следующий исходный фрагмент на языке программирования Oberon [Wir88]:
VAR ch : CHAR; lint: LONGINT; BEGIN lint := LONG(ORD(ch)); А вот как можно представить этот фрагмент в виде последовательности команд для абстрактного стекового компьютера: LOAD1 ch поместить 1-байтовое CHAR-значение в стек ORD zero-extend, результат типа INTEGER LONG sign-extend, результат типа LONGINT STORE4 lint поместить 4-байтовое LONGINT-значение обратно в памятьОднако на некоторых процессорах (в частности, принадлежащих семейству NS32000 фирмы National Semiconductor [Nat84]), эта последовательность операций может выполняться с помощью одной команды:
MOVZBD ch, lint загрузить расширенный до нуля байт в двойное слово
Следовательно, при генерировании кода из промежуточного представления, полученного с помощью абстрактной машины, может оказаться необходимым (кроме разве что самых примитивных случаев) объединять несколько команд абстрактной машины в одну команду целевой машины. В этих случаях кодогенератору в сущности приходится со значительными издержками восстанавливать информацию, которая была бы легче доступна во front-end части, но она уже потеряна при переходе к промежуточному представлению.
Единственный путь разрешения этой конкретной проблемы состоит в ликвидации семантического разрыва посредством введения на уровне абстрактной машины отдельных инструкций MOVE для каждой комбинации входного и выходного типа данных. И все же так можно действовать только в тех случаях, когда происходит прямое преобразование формата данных. А поскольку целевые архитектуры потенциально могут предложить операции произвольного уровня сложности, например, объединенные операции move-shift, объединение нескольких команд абстрактной машины в одну команду целевой машины никогда нельзя исключать полностью, независимо от того, насколько четко проработан проект абстрактной машины.
Дефекты в структуре основанных на абстрактных машинах промежуточных языков не оставляют возможности использовать их в качестве базы для генерирования высококачественного машинного кода. Далее в этой главе предлагается промежуточное представление, которое может послужить такой основой. Будучи весьма компактным, это представление, которое я называю кодированием на основе семантического словаря (SDE, semantic dictionary encoding), полностью сохраняет семантический контекст исходной программы.
Обзор метода кодирования на основе семантического словаряSDE — это представление компактное. При использовании данного метода синтаксически корректная исходная программа кодируется с помощью идующих друг за другом индексов в семантический словарь, который, в свою очередь, содержит всю необходимую информацию для генерирования машинного кода. Сам словарь не является частью SDE-представления. Он создается динамически в ходе трансляции исходной программы в SDE-форму и реконструируется до начала (или в ходе) процесса декодирования. Этот метод чем-то напоминает повсеместно используемые схемы сжатия данных [Wel84].
Если исключить полностью константные выражения, которые вычисляются в ходе преобразования исходной программы в SDE-форму, SDE-кодирование сохраняет всю информацию, содержащуюся на уровне входного языка. Следовательно, в отличие от представлений, основанных на использовании абстрактных машин, преобразование в SDE-форму сохраняет блочную структуру программ, а также тип каждого выражения. Более того, в определенных случаях при подаче полученных с помощью SDE-кодирования данных на вход кодогенератора генерация кода упрощается, что приводит к повышению эффективности трансляции.
Программа в SDE-форме состоит из таблицы символов (symbol table), представленной в компактном формате (как это изложено в [Fra93b]), и серии словарных индексов (dictionary indices). Таблица символов описывает имена и внутреннюю структуру различных объектов, на которые ссылается программа, таких как переменные, процедуры и типы данных. Она используется в фазе инициализации, в ходе которой в семантический словарь помещается несколько начальных записей (initial entries). Кодирование действий программы состоит в выставлении ссылок на эти записи словаря, а также на другие записи, добавляемые позднее в процессе кодирования.
Записи словаря представляют собой узлы ориентированного ациклического графа (DAG, direct acyclic graph), который описывает семантические действия программы в абстрактной форме. В самом элементарном виде семантический словарь представляет собой абстрактное синтаксическое дерево (abstract syntax-tree) в форме таблицы, в которой ссылки между узлами заменены индексами таблицы. Каждая запись словаря состоит из атрибута класса, указывающего на семантическое действие, которое представляет данная запись (например, присваивание, сложение и т.д.), и, возможно, некоторые ссылки на объекты в таблице символов (связанные через атрибут Info на диаграмме ниже) и на другие записи словаря (описанные атрибутом Links). На рис.2.3 мы видим пример простого арифметического выражения, представленного в виде абстрактного семантического дерева и семантического словаря.
a + b * c Арифметическое выражение + a * Абстрактное синтаксическое дерево b c индекс класс Info Link n-1 ... n переменная a n+1 переменная b n+2 переменная c n+3 умножение n+1, n+2 n+4 сложение n, n+3 n+5 ... Рис.2.3 Арифметическое выражение в разных представлениях
Отличие представленного в виде таблицы абстрактного синтаксического дерева от семантического словаря состоит в том, что последний может описывать также и родовые характеристики (generic characteristic) потенциальных узлов, которые могут появиться на таком дереве. В дополнение к полным записям (complete entries), которые прямо соответствуют узлам абстрактного синтаксического дерева, семантические словари содержат также родовые, или шаблонные записи (template entries). Эти шаблоны имеют ту же структуру, что и полные записи, но здесь недостает по крайней мере одного из атрибутов полной записи, что отражается в соответствующем флаге состояния. В ходе SDE-кодирования сложные выражения могут быть представлены не только с помощью полных записей, но также и с помощью шаблонов в сочетании с другими записями. Так, выражение "a+b" может быть представлено с помощью индекса шаблона "сложение", за которым следуют индексы двух записей со ссылками на переменные (variable-references entries).
Представим теперь, что в семантическом словаре для каждой конструкции входного языка (присваивание, сложение и т.д.) существует свой шаблон, и семантический словарь инициализирован таким образом, что для всякого возможного варианта использования любого объекта таблицы символов он содержит, по крайней мере, одну запись (возможно, шаблон). Например, для объекта, описывающего процедуру языка программирования Oberon [Wir88], требуется по меньшей мере четыре записи в словаре, которые, в свою очередь, связаны с вызовом процедуры, с входом в процедуру, с возвратом из процедуры и с адресацией процедуры. Упомянутые записи используются при присваивании процедуры процедурным переменным. Других операций с процедурами в языке Oberon не предусмотрено.
Для выполнения этих предусловий словарь должен быть соответствующим образом проинициализирован. Предусловия позволяют нам представлять любую программу, пользуясь при этом только таблицей символов и последовательностью словарных индексов. Рассмотрим для примера следующий модуль M, написанный на языке программирования Oberon:
MODULE M; VAR i,j,k: INTEGER; PROCEDURE P(x: INTEGER): INTEGER; BEGIN ... END P; BEGIN i := P(i); i := i + j; j := i + k; k := i + j; i := i + j END M.Для того чтобы закодировать эту программу с помощью метода SDE, нам нужно прежде всего проинициализировать семантический словарь с использованием операций, предусмотренных языком программирования (в данном случае, языком Oberon), и объектов из таблицы символов. Таблица символов для данной программы состоит из трех целочисленных переменных (i, j и k) и процедуры-функции (P). После инициализации соответствующий семантический словарь мог бы выглядеть следующим образом (индексы отдельных записей представлены символьными именами так, чтобы на них можно было ссылаться в ходе дальнейшего изложения материала в данной главе, а недостающие атрибуты шаблонов обозначены точкой):
индекс класс значение не хватает asgn присваивание . := . левый, правый plus сложение . + . левый, правый ... ... ... ... vi переменная i — vj переменная j — vk переменная k — refp адрес P — callp вызов P(.) правый entp точка входа P-BEGIN — retp возврат P-RETURN. правыйТогда последовательность команд, составляющая тело модуля M, может быть представлена с помощью следующей последовательности 24 словарных индексов:
asgn vi callp vi i := P(i) asgn vi plus vi vj i := i + j asgn vj plus vi vk j := i + k asgn vk plus vi vj k := i + j asgn vi plus vi vj i := i + jИ вот здесь может оказаться полезной вторая важная идея SDE-кодирования. Что если в процессе кодирования мы будем продолжать вводить в словарь новые записи, основанные на кодируемых выражениях, в надежде вновь встретить подобные выражения в ходе дальнейшей работы?
Например, закодировав присваивание i := P(i), мы могли бы ввести в словарь следующие три записи:
класс значение не хватает вызов P(i) — присваивание i := . правый присваивание i := P(i) —В дальнейшем, если в исходном тексте вновь появится это же присваивание i := P(i), мы сможем представить его с помощью одного словарного индекса. Если же нам встретится еще одно присваивание другого выражения переменной i, его можно будет представить с помощью шаблона "присвоить i", и код в результате получится компактней.
Итак, в случае кодирования модуля M вышеописанным образом в словарь помещаются следующие дополнительные записи (при этом предполагается, что после инициализации словарь содержит n-1 записей):
индекс класс значение не хватает ... ... ... ... n вызов P(i) — n+1 присваивание i := . правый n+2 присваивание i := P(i) — n+3 сложение i + . правый n+4 сложение . + i левый n+5 сложение i + j — n+6 присваивание i := i + j — n+7 сложение . + k левый n+8 сложение i + k — n+9 присваивание j := . правый n+10 присваивание j := i + k — n+11 присваивание k := . правый n+12 присваивание k := i + j — ... ... ... ... Тогда тело модуля M может быть закодировано следующим образом: asgn vi callp vi i := P(i) n+1 plus vi vj i := i + j asgn vj n+3 vk j := i + k asgn vk n+5 k := i + j n+6 i := i + jВ этом случае для кодирования требуется всего 16 словарных индексов, а не 24, как в предыдущем примере, хотя сами отдельные индексы здесь могут быть объемнее, поскольку словарь состоит из большего числа записей. И все же, второй вариант кодирования обычно гораздо более компактен и обеспечивает другие преимущества, что будет показано в следующем параграфе.
Повышение скорости кодогенерацииПроцесс декодирования программы, представленной в SDE-форме, подобен процессу кодирования. Сначала инициализируется словарь; он должен быть приведен в то же состояние, в каком он находился в начале кодирования. Поскольку таблица символов является частью SDE-представления файлов, декодер в этом случае располагает всей необходимой информацией для решения данной задачи.
После этого декодер неоднократно считывает словарные индексы из файла, отыскивая в семантическом словаре каждую соответствующую запись. Когда таким образом находится полная запись, ее значение кодируется непосредственно в словарь, и декодер может продолжать обрабатывать следующий индекс входного потока. Если же вместо этого обнаруживается шаблон, он копируется, затем по очереди вводятся новые записи статьи, соответствующие неописанным атрибутам шаблона, и модифицированная копия вводится в словарь в качестве новой полной записи. Более того, в соответствии с некоторым фиксированным эвристическим приемом в семантический словарь иногда вводятся дополнительные шаблоны на случай, если в дальнейшем будет обнаружена соответствующая ветвь синтаксического дерева программы. Подробнее такой эвристический прием мы рассмотрим в следующей главе.
Метод SDE не только дает компактное представление программы, с его помощью можно получать некоторые сведения, не содержащиеся явно в исходном тексте, а именно, сведения о многократно встречающихся в тексте идентичных подвыражениях (включая, помимо прочего, общих адресатов — common designators). Иногда такие сведения используются в ходе кодогенерации, что позволяет повысить скорость вывода закодированных данных.
Вернемся еще раз к рассмотрению описанного выше второго, более компактного SDE-представления модуля M. Представим теперь, что мы хотим генерировать объектный код для простой стековой машины непосредственно из этой SDE-формы. Предположим, что мы уже обработали первые два оператора тела модуля M и получили такую последовательность команд, начинающуюся с адреса "a":
а LOAD i load i onto stack а+1 BRANCH P call procedure P with argument i а+2 STORE i assign result to i а+3 LOAD i load i а+4 LOAD j load i а+5 ADD add i to j а+6 STORE i assign their sum to iПредставим, далее, что мы исправно отмечаем в семантическом словаре соответствие каждой сгенерированной команды тем или иным записям в словаре. Это можно сделать, к примеру, следующим образом: для каждой записи дважды (до и после генерации кода для данной записи) записывать в семантический словарь значение счетчика команд:
Такая установка позволяет нам при некоторых обстоятельствах обойти обычный процесс кодогенерации, заменив его простой командой copy, воспроизводящей уже сгенерированные команды. Например, когда мы доходим до второй ссылки на запись n+6 в SDE-представлении модуля M, мы знаем, что ранее мы уже оттранслировали соответствующий оператор "i := i + j ". И в этом случае мы можем просто вновь выдать эту уже сгенерированную последовательность команд, которая находится в объектном коде между адресами a+3 и a+6, как это и записано в словаре.
Разумеется, этот метод не подходит для всех случаев жизни и для всех типов машин. Прежде всего, копирование кода возможно лишь для позиционно независимых последовательностей команд. Так, подвыражение, включающее вызов локальной функции с помощью относительного перехода, не является позиционно независимым, поскольку при каждом вызове функции расстояние перехода (branch distance) меняется. Но получается так, что информация о позиционной инвариантности тоже может быть с легкостью записана в словарь, как это явствует из приведенного выше примера.
Во-вторых, последовательности команд, полученные с помощью копирования кода, совсем не обязательно являются оптимальными для более сложных процессоров с большим числом регистров и многоступенчатыми конвейерами обработки команд. При работе с такими машинами может возникнуть необходимость прибегнуть к особым приемам оптимизации. Однако, поскольку метод SDE сохраняет всю информацию, присутствующую в исходном тексте, в ходе кодогенерации возможны произвольные уровни оптимизации, хотя упрощенные решения, возможные при копирования кода, в данном случае недоступны. Так что с семантическим словарем в подобных случаях приходится работать просто как с абстрактным синтаксическим деревом в форме таблицы.
Любопытная деталь: копирование кода дает особенно хорошие результаты как раз на тех машинах, которые при других обстоятельствах работают медленно, т.е. на компьютерах, оснащенных CISC-процессорами с небольшим количеством регистров. Давайте еще раз вернемся к модулю M, в котором выражение "i := i + j" встречается три раза. На простой машине, оснащенной всего одним сумматором или стеком выражений, всякий раз, когда встречается это подвыражение, нам просто придется использовать идентичную последовательность команд. И в этом случае копирование кода может ускорить процесс кодогенерации. С другой стороны, оптимальным решением для современного RISC-процессора, где используются регистровые переменные и конвейерная обработка команд, оптимальное решение вполне может состоять в том, что для трех экземпляров данного подвыражения будут использованы три различных последовательности команд. Впрочем, быстродействие, характерное для большинства таких процессоров, компенсирует дополнительное время на кодогенерацию. Поэтому приемлемая скорость генерации кода достигается даже в тех случаях, когда приходится прибегать к оптимизации.
3. КОДЕР И ДЕКОДЕР ДЛЯ SDE-ПРЕДСТАВЛЕНИЯВ предыдущей главе объяснялся метод, названный кодированием на основе семантического словаря (SDE). Опираясь на данный метод кодирования, была реализована система, в которой кодогенератор уже больше не является составной частью компилятора, а встраивается непосредственно в загрузчик модулей. Реализованная система предоставляет компилятор Oberon-SDE, который преобразует программы, написанные на языке программирования Oberon [Wir88] в файлы с SDE-представлением, а также кодогенерирующий загрузчик (code-generating loader), который считывает SDE-файлы и использует содержащуюся в них информацию для динамической кодогенерации под процессор Motorola 68020 [Mot87].
В данной главе обсуждаются механизмы кодирования и декодирования. В ней также представлена аргументация ключевых проектных решений. Но более важно то, что в ней поясняются некоторые эвристические приемы, используемые в управлении семантическими словарями.
Использование механизма областей видимостиМногие языки программирования ограничивают область видимости определенных объектов, встречающихся внутри программы, например, как в случае ограничения видимости локальных переменных процедуры в объемлющей ее процедуре. Эти правила видимости (scoping rules) могут быть использованы для уменьшения размера семантического словаря. Малые размеры семантического словаря — это замечательное достоинство, поскольку программа в SDE-форме состоит из словарных индексов. При увеличении словаря в среднем требуется большее количество бит для представления этих индексов.
Мы также отмечаем, что существуют объекты, которые видны на протяжении всего модуля. Это константы и глобальные переменные. Далее словарь содержит также шаблоны операций, которые используются для кодирования семантических действий программы. Они никогда не должны удаляться из словаря.
Если принять во внимание эти различия между временными и постоянными записями, простое и эффективное решение в плане управления словарем состоит в том, что словарь расширяется одновременно в двух направлениях, как это показано на рис.3.1. Записи с неограниченной областью видимости добавляются в конец словаря, который может расширяться до бесконечности. Все другие узлы добавляются по другую сторону словаря, который работает по принципу стека. Каждый раз, когда открывается новая область видимости, помечается текущая ширина словаря, и после закрытия области видимости она сбрасывается к этой отметке. Декодер SDE-формата хранить историю этих меток и восстанавливать операции за счет анализа их входного потока на предмет обнаружения словарных индексов, обозначающих точку входа в процедуру и возврат из процедуры.
Представление индексов внутри файлаВ реализованной нами системе словарные индексы представляются в SDE-файлах в виде данных переменной длины, опирающихся на стоповый бит (stop-bit). Этот прием описан в работе [Fra93b]. Формат данных переменной длины требует меньше пространства для кодирования небольших неотрицательных величин, чем это требуется для больших чисел. Такой компактный формат идеально подходит для представления словарных индексов. Однако, плотность информации результирующего кодирования в значительной степени зависит от величины отдельных индексов, а потому и от расстояния записей от начала словаря. Для достижения компактного кодирования важно отображать вектор индексов в словарь таким образом, чтобы наиболее часто встречающиеся в словаре записи лежали внутри диапазона, который может адресоваться минимальным числом битов.
Эксперименты показали, что ссылки в словаре, носящие наиболее общий характер, относятся в SDE-закодированных программах к шаблонам, описывающим примитивные операции входного языка, а также к выражениям, где фигурируют локальные переменные. Таким образом, была принята схема адресации словаря, представленная на рис.3.2. Так как большинство процедур берут начало на лексическом уровне 0 и остаются относительно короткими (т.е. для них генерируется всего несколько новых записей), большой процент словарных индексов, встречающихся в типичном SDE-представлении, будет попадать внутрь диапазона таких индексов, которые в смысле занимаемого пространства могут быть представлены весьма эффективно.
Кодирование исходных Oberon-программ в SDE-представлениеOberon-SDE компилятор имеет в своей структуре достаточно традиционную для компиляторов front-end часть [Cre91]. Он осуществляет разбор каждого исходного текста на языке Oberon по рекурсивно-нисходящей стратегии и строит таблицу символов, а также абстрактное синтаксическое дерево, т.е. ориентированный ациклический граф, который описывает семантические действия программы. Если во время разбора не было обнаружено ни одной ошибки, то управление передается кодеру, который создает SDE-файл, представляющий содержимое исходной программы в компактном и машинно-независимом виде.
По ходу работы кодер осуществляет обход абстрактного синтаксического дерева. Для каждого узла, затронутого эти обходом, он ищет текущий семантический словарь с записью, максимально соответствующей данному узлу. Соответствие определяет, насколько хорошо запись в словаре подходит для узла дерева. Запись является полностью соответствующей (fully conforming), или изоморфной (isomorhic), узлу абстрактного дерева, если запись и узел описывают одно и то же семантическое действие и если они вообще не имеют потомков или если все их аналогичные потомки изоморфны друг другу. Например, на рис.3.3 запись в словаре с индексом n+2 является изоморфной узлу, помеченному как "t", а запись с индексом "n" — узлу "u".
Быть полностью соответствующими узлам синтаксического дерева могут только полные записи (т.е. записи без неопределенных потомков). Для шаблонов соответствие определяется более скромным образом. Шаблон соответствует узлу абстрактного синтаксического дерева, если он описывает то же самое семантическое действие и все его определенные потомки являются изоморфными по отношению к аналогичным потомкам узла. Например, на рис.3.4 все шаблоны с индексами "x", "x+1" и "x+2" соответствуют узлу, помеченному как "t".
Поиск подходящей записи всегда завершается успешно, поскольку за счет инициализации словаря мы гарантируем, что для любого произвольного узла в абстрактном синтаксическом дереве существует по крайней мере один минимально соответствующий шаблон. После нахождения подходящей записи кодер заносит ее индекс в SDE-файл и затем рекурсивно обходит все поддеревья абстрактного синтаксического дерева, которые связаны с неопределенными потомками подходящей записи. В случае, когда существует несколько альтернативных записей, каждая из которых соответствует конкретному узлу абстрактного синтаксического дерева, как это показано на рис.3.4, кодер может добиться максимальной плотности информации в SDE-файле за счет того, что всегда будет выбирать запись с наибольшим количеством определенных потомков.
Представление, используемое в SDE-файлах, в значительной мере ориентировано на простоту декодирования. Процесс кодирования требует большого числа просмотров словаря и потому значительно менее эффективно. В принципе вполне возможно осуществить все требуемые просмотры путем линейного обхода всего словаря до тех пор, пока не будет найдена подходящая запись. Однако, для больших программ это может сделать кодирование на основе семантического словаря просто непрактичным.
Вместо поиска по всему словарю снова и снова, в нашей реализации для уменьшения числа записей в словаре, которые нужно обойти, используется специальная структура с сортировкой по оверлеям. Записи из словаря группируются в этой отсортированной структуре по своим семантическим действиям, а все записи, связанные с областью видимости конкретной ппроцедуры, удаляются сразу же, как только эта область будет закрыта.
Заметим, что для корректности алгоритма достаточно сбрасывать счетчик словаря в конце каждой области видимости, в то время как сами записи не должны удаляться из словаря. Благодаря природе правил видимости для любой произвольной записи в словаре невозможна ситуация, когда она возвращается в качестве результата поиска после того, как соттветствующая область видимости уже закрыта.
Эвристические приемы по управлению словаремСуществует несколько различных компромиссов (в смысле пространства и времени), которые необходимо учитывать в алгоритме, отвечающем за управление семантическим словарем. Это становится особенно важным, когда рассматривается стратегия, с помощью которой добавляются новые шаблоны. Обычно добавление большого количества шаблонов приводит к более плотному представлению программы в SDE-файлах, но при этом также возрастает размер словаря, а, следовательно, и требования к памяти для процессов кодирования и декодирования. Это может к тому же увеличивать время декодирования из-за накладных расходов на размещение в памяти большего по размерам словаря и на проведение более продолжительной инициализации. В последующих параграфах будет представлен ряд вопросов, на которые нужно найти ответ в ходе проработки эвристических приемов по управлению словарем. Как и прежде, используется такой синтаксис выражений, где точка обозначает отсутствующую компоненту шаблона.
Рассмотрим выражение "a + b". Поскольку сложение — одна из основных операций в языке Oberon, гарантируется, что для каждого Oberon-ориентированного семантического словаря после его инициализации уже существует шаблон для родового выражения ". + ." . Аналогичным образом, если две переменные "a" и "b" встречаются в таблице символов конкретной программы, то соответствующий семантический словарь после инициализации будет содержать нужные ссылки. Выражение "a + b" при появлении в начале программы, следовательно, будет оттранслировано в последовательность из трех индексов: ". + ." , "a" и "b".
В этом месте разработчик эвристики управления словарем должен сделать выбор, какие из записей ". + b", "a + ." или "a + b" должна быть добавлена в словарь. Очевидно, что при стратегии, предусматривающей порождение наиболее компактных SDE-файлов, при наличии в словаре достаточного пространства будут добавлены все три записи. Итак, давайте предположим, что в словарь добавлены все три варианта. А теперь посмотрим, что произойдет, если чуть позже в той же самой программе мы встретим выражение "a + x". Оно может быть закодировано на основе записи "a + .", которая уже имеется в семантическом словаре. Но что же за ней? Здесь опять-таки существует выбор из новых записей, которые могут быть добавлены в словарь. Ясно, что "a + x" нам подойдет? Ну а как насчет ". + x" ?
Проблема здесь состоит в том, что запись ". + x" может уже быть в семантическом словаре, например, в результате предшествующего кодирования "y + x". Однако, чтобы обнаружить, имеется ли данная запись в словаре, надо провести поиск, который весьма накладен и потому неприемлем во время декодирования. Следовательно, существует выбор между тем, чтобы оставить наличие этой записи в словаре под вопросом, и тем, что не глядя занести ее в словарь, даже несмотря на то, что там такая уже имеется и что будет расточительно использоваться свободное пространство таблицы.
Вопрос о том, какая стратегия лучше, остается открытым. Были проведены эксперименты с различными эвристическими приемами генерации шаблонов, которые привели к выводу о том, что эффект их использования различается в зависимости от стиля, в котором была написана исходная программа, и наряду с другими факторами в прямой зависимости от количества общих подвыражений явно используемых программистом. Возможным решением было бы, конечно, перебрать в процессе кодирования несколько вариантов, чтобы найти ту стратегию, которая наилучшим образом подходит для данной конкретной программы. Соответствующий эвристический прием может быть применен во время фазы декодирования, и его можно зафиксировать в SDE-файле с помощью какого-нибудь тега. Для простоты наша реализация для генерации новых шаблонов использует прямую стратегию.
Упорядочивание процедурных вызововПри анализе существующих Oberon-программ мы обнаружили, что список параметров процедуры обычно упорядочен таким образом, что параметры становятся более "изменчивыми" при переходе к правой стороне списка. Например, процедура
WriteBytes (VAR r: Files.Rider; VAR x: ARRAY OF CHAR; n: LONGINT) вызывается неоднократно с фиксацией некой закладки (rider) "r", тогда как остальные параметры могут варьироваться. Более того, фактический параметр для "n" меняется сильнее, чем параметр, соответствующий формальному параметру "x".
Такое упорядочение во многом связано с интенсивным использованием абстрактных типов данных, которые естественным образом выступают как первые параметры процедур, обеспечивающих работу с этими типами данных. Однако, среди программистов существует и более глубокое, неписанное, но постоянно применяемое правило структуризации списка параметров именно таким способом. Эвристические приемы по управлению словарем, которые используются при кодировании процедурных вызовов, должны опираться на гипотезу о том, что естественнее размещать менее "изменчивые" параметры перед более "изменчивыми".
Поэтому реализованная нами система поддерживает упорядочивание общих список параметров, совпадение которых смещено в левую сторону списка. Например, после кодирования процедурного вызова "P(x, y, z)", в семантический словарь добавляется соответствующая полная запись в виде двух шаблонов: "P(x, ., .)" и "P(x, y, .)". Последующий процедурный вызов "P(x, y, a)" может быть эффективно представлен в виде двух словарных индексов, которые отвечают за "P(x, y, .)" и за "a".
Данная стратегия представляет собой компромисс между плотностью информации и размером словаря, оставаясь при этом вполне подходящей для эффективной реализации. Адекватное отображение в представление на основе семантического словаря может быть найдено достаточно просто, если рассматривать каждый процедурный вызов как двоичное дерево частичных вычислений (binary tree of partial evaluations). Взгляните на рис.3.5.
Альтернативная стратегия могла бы приводить к генерации новых записей, описывающих все возможные комбинации "заменителей" (обозначаемых точкой) в списке параметров. Например, после кодирования процедурного вызова "P(x, y, z)" в дополнение к ранее уже упомянутым можно включить следующие записи: "P(., y, .)", "P(., ., z)", "P(., y, z)" и "P(x, ., z)".
Подготовка словаря для декодированияВ реализованной нами системе SDE-файлы декодируются во время загрузки. Это достигается с помощью кодогенерирующего загрузчика, который осуществляет SDE-декодирование и опирается на генератор кода системы MacOberon [Fra90a, Fra90b, Fra91, BCF92, Fra93a, Fra93b]. Он делает возможным использование идеи копирования кода, о которой говорилось в предыдущей главе. В этом подходе идеальным фундаментом является предварительно обработанное синтаксическое дерево, так как оно возникает из кодирования на основе семантического словаря. Здесь на уровне исходного текста производится упорядочивание общих подвыражений и общих адресатов (designators). Стратегия инициализации семантического словаря с записями, которые опираются на объекты, встречающиеся в таблице символов, способна привести к дальнейшему улучшению эффективности кодогенерации.
Рассмотрим произвольный объект категории "переменная" из таблицы символов. В front-end части компилятора не проводится никакой дискриминации по отношению к различным видам переменных, будь то глобальные переменные модуля или локальные переменные процедуры. Это различие остается для кодогенератора, для которого каждая ссылка на переменную должна определять, какой конкретный вид переменной обрабатывается, другими словами, какой используется режим адресации.
В то же время внутри SDE-файла все ссылки на переменные опираются на записи, которые размещаются в словаре на этапе инициализации. Важный момент состоит в том, что значения (meanings) отдельных записей в словаре декодера не должны прямо соответствовать значениям соответствующих записей, используемых на этапе кодирования (см.рис.3.6). Следовательно, можно упростить задачу кодогенерации за счет проведения определенной предварительной обработки на этапе инициализации словаря, проводя более тонкое разграничение между различными вариантами объектов из таблицы символов с ориентацией на декодер, чем та, что нужна собственно кодеру.
Реализованный кодогенерирующий загрузчик для процессора MC 68020 [Mot87] осуществляет некоторые действия по подобной предварительной обработке. Например, он проводит разграничение между глобальными переменными (с абсолютной адресацией), прямыми локальными переменными (с адресацией относительно стекового фрейма) и косвенными локальными переменными (с косвенной адресацией к ячейкам памяти, когда используются параметры, передаваемые по ссылке). Следовательно, для представления всех этих видов переменных используются разные категории записей в словаре, и вся информация, требуемая для генерации адресов, собирается в семантическом словаре, уже когда он проинициализирован. Поскольку в типичных программах большинство переменных встречается более одного раза, эта стратегия ускоряет процесс кодогенерации.
Декодирование SDE-файловТеперь, после всех изложенных выше нюансов проектирование кодогенерирующего загрузчика становится достаточно понятным. Сначала из SDE-файла считывается глобальная таблица символов. Затем по обсужденной ранее схеме инициализируется семантический словарь. Далее по порядку считываются и обрабатываются словарные индексы. Это осуществляется по следующему алгоритму:
<считывается индекс idx и извлекается соответствующая запись E := dict[idx]> IF E.copy-safe THEN <считывается код между E.beg и E.end в текущем положении PC> ELSE IF <E — это шаблон> THEN <рекурсивно вводятся неопределенные потомки E> <возможно на основе эвристик создаются новые шаблоны> <из шаблона и потомков создается новая полная запись E> END; E.beg := PC; <генерируется код для E, при этом соответственно модифицируется флаг E.copy-safe> E.end := PC END;Признак copy-safe необходим для остлеживания всех полных записей в словаре. Он говорит о том, что код для соответствующего выражения может быть порожден просто путем дублирования последовательности инструкций, которые были сгенерированы ранее. Шаблоны никогда не могут удовлетворять этому признаку.
Запись в словаре является готовой для копирования (copy-safe), если внутри результирующего кода не ожидается никаких правок (fix-up) и если код является позиционно-независимым. В реализованном кодогенерирующем загрузчике для процессора Motorola 68020 эти критерии удовлетворяются для всех полных записей, за исключением тех, где описываются выражения, содержащие вызовы локальных функций. Эти вызовы транслируются в относительные переходы, которые для каждого вызова имеют разные длины (branch distance).
Копирование кода послужило основной причиной, почему было принято решение не транслировать обращения к внешним процедурам в относительные переходы, что можно было сделать довольно просто, поскольку во время динамической кодогенерации известны все адреса во внешних модулях. Это было единственной ситуацией, когда скорости генерации кода было отдано предпочтение по сравнению со скоростью его выполнения. Однако, производительность при использовании двух инструкций вызова падает не намного, в то время как внешние вызовы обычно в модулях встречаются довольно часто, а это позволяет извлечь выгоду из техники копирования кода.
Детали реализацииВ любом проекте вроде того, что мы обсуждаем, всегда существует множество крошечных проектных решений. Многие из них могут быть скорее подогнанными под конкретную задачу, тогда как причины использования других могут быть потеряны еще до того, как приступят к их документированию. Представленный ниже список минирешений далеко не полон, но он иллюстрирует некоторые тонкие моменты, которые не затрагивались в этой диссертации.
Таблица символов. Из того, о чем уже было сказано ранее, читатель может сделать вывод, что полная таблица символов хранится как единое целое в начале SDE-файла. Это не совсем верно. В действительности, в начале SDE-файла хранится только глобальная область видимости, в то время как остальные области идут за словарными индексами, которые представляют соответствующие записи о процедуре. Это обеспечивает более эффективное распределение памяти в декодере и позволяет применять механизм стека не только для словаря, но и для таблицы символов. Константы. В реализованной нами системе безымянные символьные константы (literal constants) фактически не входят в таблицу символов, а непосредственно вставляются в поток словарных индексов, следуя за индексом шаблона "константа", который косвенно говорит о типе константы. Для каждой представленной таким образом константы, создается полная запись, которая добавляется в глобальный конец словаря, поэтому последующие появления этой константы могут быть закодированы напрямую по индексу. Константа NIL соответствует зарезервированному слову языка Oberon и размещается в словаре во время его инициализации, точно также дело обстоит и с константами TRUE и FALSE. Примитивы распределения памяти. В языке Oberon обращения к стандартным процедурам NEW и SYSTEM.NEW обычно транслируются в специальные обращения к супервизору, так что компилятору статически нужно знать только номер соответствующего вектора прерывания, а отнюдь не программы, которая его обрабатывает. При отсутствии на целевой машине системы защиты памяти не имеет смысла отказываться от дорогостоящего механизма обращений к супервизору, поскольку фактический адрес процедуры из модуля Kernel, который реализует инструкцию супервизора, известен во время кодогенерации.Вот почему в нашей реализации эти два примитива распределения памяти транслируются в обычные процедурные вызовы, которые не только сокращают последовательность инструкций, но и ускоряют сам вызов.
Окончание следует
ЛИТЕРАТУРА [ADH89] Atkinson R., Demers A., Hauser C., Jacobi Ch., Kessler P., Weiser M. (1989) "Experiences Creating a Portable Cedar" // Proceedings of the SIGPLAN’89 Conference on Programming Language Design and Implementation // SIGPLAN Notices, Vol.24, No.7, p.322-329.
[BCF92] Brandis M., Crelier R., Franz M., Templ J. (1992) "The Oberon System Family" // ETH Zurich, Department of Informatics, Report No.174.
[Chu36] Church A. (1936) "An Unsolvable Problem of Elementary Number Theory" // American Journal of Mathematics, Vol.58, p.345-363.
[Con58] Conway M.E. (1958) "Proposal for an UNCOL" // Communications of the ACM, Vol.1, No.10, p.5-8.
[Cre91] Crelier R. (1991) "OP2: A Portable Oberon-2 Compiler" // Proceedings of the 2nd International Modula-2 Conference // Loughborough, England, p.58-67.
[DRA93a] (1993) "United Kingdom Defence Research Agency: A Guide to the TDF Specification" // Issue 2.1, June 1993.
[Fra90a] Franz M. (1990) "The Implementation of MacOberon" // ETH Zurich, Department of Informatics, Report No.141.
[Fra90b] Franz M. (1990) "MacOberon Reference Manual" // ETH Zurich, Department of Informatics, Report No.142.
[Fra91] Franz M. (1991) "The Rewards of Generating True 32-bit Code" // SIGPLAN Notices, Vol.26, No.1, p.121-123.
[Fra93a] Franz M. (1993) "Emulating an Operating System on Top of Another" // Software — Practice and Experience, Vol.23, No.6, p.677-692.
[Fra93b] Franz M. (1993) "The Case for Universal Symbol Files" // Structured Programming, Vol.14, No.3, p.136-147.
[GaF84] Ganapathi M., Fischer C.N. (1984) "Attributed Linear Intermediate Representations for Retargetable Code Generators" // Software — Practice and Experience, Vol.14, No.4, p.347-364.
[Gri72] Griswold R.E. (1972) "The Macro Implementation of SNOBOL4: A Case Study in Machine-Dependent Software Development" // Freeman.
[Gri81] Griswold R.E. (1981) "A History of the SNOBOL Programming Languages" // In "History of Programming Languages" ed. by R.L.Wexelblat // Proceedings of the History of Programming Languages Conference // Academic Press, p.601-645.
[Hal65] Halpern M.I. (1965) "Machine Independence: Its Technology and Economics" // Communications of the ACM, Vol.8, No.12, p.782-785.
[KeR78] Kernighan B.W., Ritchie D.M. (1978) "The C Programming Language" // Prentice-Hall.
[KKM80] Kornerup P., Kristensen B.B., Madsen O.L. (1980) "Interpretation and Code Generation Based on Intermediate Languages" // Software — Practice and Experience, Vol.10, No.8, p.635-658.
[Mot87] (1987) "MC68030 Enhanced 32-bit Microprocessor User’s Manual" // Motorola Inc., 1987.
[NAJ81] Nori K.V., Amman U., Jensen K., Nageli H.H., Jacobi Ch. (1981) "Pascal-P Implementation Notes" // In "Pascal: The Language and Its Implementation" ed. by D.W.Barron // John Wiley & Sons.
[NPW72] Newey M.C., Poole P.C., Waite W.M. (1972) "Abstract Machine Modelling to Produce Portable Software: A Review and Evaluation" // Software — Practice and Experience, Vol.2, No.2, p.107-136.
[Nat84] (1984) "Series 32000: Instruction Set Reference Manual" // National Semiconductor Corp.
[PoW69] Poole P.C., Waite W.M. (1969) "Machine Independent Software" // Proceedings of the ACM 2nd Symposium on Operating System Principles // Princeton.
[Rei89] Reiser M. (1989) <личная переписка>.
[Ric69] Richards M. (1969) "BCPL: A Tool for Compiler Writing and System Programming" // Proceedings of the 1969 Spring Joint Computer Conference // Published as "Proceedings of the AFIPS Conference Proceedings", No.34 // AFIPS Press.
[Ric71] Richards M. (1971) "The Portability of the BCPL Compiler" // Software — Practice and Experience, Vol.1, No.2, p.135-146.
[RiW79] Richards M., Whitby-Strevens C. (1979) "BCPL: The Language and its Compiler" // Cambridge University Press.
[Ste60] Steel T.B. (1960) "UNCOL: Universal Computer Oriented Language Revisited" // datamation, Vol.6, No.1, p.18-20.
[Ste61a] Steel T.B., Jr. (1961) "A First Version of UNCOL" // Proceedings of the Western Joint IRE-AIEE-ACM Computer Conference, Los Angeles, p.371-378.
[Ste61b] Steel T.B., Jr. (1961) "UNCOL: The Myth and the Fact" // Annual Review in Automatic Programming, Vol.2, p.325-344.
[SWT58] Strong J., Wegstein J., Tritter A., Olsztyn J., Mock O., Steel T.B. (1958) "The Problem of Programming Communication with Changing Machines: A Proposed Solution" // Communications of the ACM, Vol.1, No.8, p.12-18; Vol.1, No.9, p.9-15.
[Tur37] Turing A.M. (1937) "On Computable Numbers, with an Application to the Entscheidungsproblem" // Proceedings of the London Mathematical Society, 2nd Series, Vol.42, p.230-265.
[Wel84] Welch T.A. (1984) "A Technique for High-Performance Data Compression" // IEEE Computer, Vol17, No.6, p.8-19.
[Wir71] Wirth N. (1971) "The Programming Language Pascal" // Acta Informatica, Vol.1, No.1, p.35-63.
[Wir88] Wirth N. (1988) "The Programming Language Oberon" // Software — Practice and Experience, Vol.18, No.7, p.671-690.
[WMP69] Van Wijngaarden A., Mailloux B.J., Peck J.E.L., Koster C.H.A (1969) "Report on the Algorithmic Language Algol-68" // Numerische Mathematik, Vol.14, p.79-218.