Методы и средства эквивалентного преобразования программ на основе переносимой среды выполнения тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат наук Логинов Иван Павлович

• Логинов Иван Павлович
• кандидат наук
• 2020

Оглавление диссертации кандидат наук Логинов Иван Павлович

РЕФЕРАТ

БУКОРЗУБ

ВВЕДЕНИЕ

ГЛАВА 1 Анализ подходов к обеспечению переносимости программ

1.1 Особенности разработки переносимого программного обеспечения

1.1.1 Понятие переносимого программного обеспечения

1.1.2 Бинарная переносимость приложений

1.1.3 Переносимость на уровне исходного кода

1.1.4 Совместное проектирование встраиваемых вычислительных систем и программного обеспечения

1.2 Средства разработки переносимого программного обеспечения

1.2.1 Принципы построения компиляторов

1.2.2 Настраиваемые и кросс-компиляторы

1.2.3 Языки описания систем команд

1.2.4 Виртуальные среды выполнения программ

ГЛАВА 2 Метод эквивалентного преобразования программ

2.1 Характеристика методов эквивалентного преобразования программ

2.2 Разработка модифицированной двухэтапной модели эквивалентного преобразования программ

2.3 Процедура переноса среды выполнения

2.4 Реализация генератора кода

ГЛАВА 3 Разработка предметно-ориентированного языка описания системы команд

3.1 Требования к языку описания системы команд

3.2 Реализация языка описания системы команды

3.2.1 Структурное представление описания

3.2.2 Детали описания аспектов целевых платформ

3.2.3 Стеки

3.2.4 Набор инструкций

3.2.5 Кодирование полей в составе кода операции

3.2.6 Поведение инструкций (функции)

3.2.7 Мнемоники

3.3 Инструментальное обеспечение языка описания системы команд

ГЛАВА 4 Проектирование и разработка переносимой среды выполнения программ

4.1 Требования к переносимой среде выполнения программ

4.2 Реализация компонентов среды выполнения

4.2.1 Система типов

4.2.2 Подсистема метаданных

4.2.3 Механизм управления памятью

4.2.4 Компоненты отладчика

4.3 Процедура генерации бинарного образа среды выполнения программ

4.4 Организация эксперимента

Заключение

Список сокращений и условных обозначений

Список литературы

Приложение А - грамматика, определяющая ядро языка описания системы команд

Приложение Б - акты о внедрении

Приложение В - тексты публикаций

РЕФЕРАТ

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

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

важное значение имеет наличие обратной совместимости новых версий как процессоров, так и операционных систем.

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

Одним из подходов к решению данной задачи является разработка настраиваемых компиляторов. Такие компиляторы могут быть адаптированы к различным системам команд процессоров за счет использования их описаний на предметно-ориентированных языках. Эти языки в данном контексте называются языками описания архитектур (Architecture Description Languages, ADL) или языками описания систем команд. Однако наличия одного лишь компилятора, поддерживающего новую архитектуру процессора, недостаточно. Требуется реализация программной среды выполнения приложений, используемых библиотек, а также других инструментальных средств, необходимых разработчику.

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

переносимая среда выполнения, адаптируемая описаниями систем команд процессоров на предметно-ориентированном языке. Предложенный подход является дальнейшим развитием идеи обеспечения переносимости, воплощенной в средах выполнения JVM (Java Virtual Machine) и CLR (Common Language Runtime) применительно к целевым платформам - программно-аппаратным платформам встраиваемых вычислительных систем.

Степень разработанности проблемы. Существующие средства обеспечения переносимости решают данную задачу либо для определенного языка программирования, либо для определенных архитектур процессоров. Существующие реализации виртуальных сред выполнения программ, такие как JVM и CLR, позволяют получать приложения, переносимые на уровне исполнимых модулей. При этом сами они не являются переносимыми, так как их реализация специфична для каждой целевой платформы. Другим подходом к обеспечению переносимости программ являются настраиваемые компиляторы, которые исследовались при разработке встраиваемых вычислительных систем. Существует множество компиляторов, а также генераторов компиляторов и кодогенераторов: CodeSyn, SPAM, REDACO (для процессоров обработки сигналов), Marion, LCC, LLVM, GCC (для процессоров общего назначения), Rocket, IMPACT (для процессоров семейства VLIW-архитектур), PEAS, EXPRESS, MSSQ (для проблемно-ориентированных процессоров), комплексные решения (LISA). Данные решения позволяют выполнять компиляцию кода приложений для процессоров с различными системами команд, не предоставляя полноценного набора инструментов и средств для разработки и выполнения приложений. Также данные решения не ориентированы на генерацию кода для процессоров различных архитектур - CISC, RISC, VLIW, ASIP.

Теоретический вклад в данную область в части разработки компиляторов внесли Рэйнер Льюперс, Альфред Ахо, Эндрю Аппель; в части технологий разработки программного обеспечения для встраиваемых вычислительных систем - А.Н. Терехов, специалисты института системного программирования РАН А.А.

Белеванцев, Ш. Ф. Курмангалеев, зарубежные специалисты - Эдвард Ли, Тереза Хигуера-Толедано.

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

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

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

Цель работы. Обеспечение переносимости программ на вновь создаваемые специализированные вычислительные системы на основе адаптируемой среды выполнения.

Для достижения поставленной цели требуется решить следующие задачи:

1. Выполнить анализ состояния работ в области инструментальных программных средств в части обеспечения переносимости программ на вновь создаваемые встраиваемые вычислительные системы.

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

3. Разработать предметно-ориентированный язык описания систем команд процессоров с вариативной степенью детализации.

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

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

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

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

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

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

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

Основные положения, выносимые на защиту.

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

2. Предметно-ориентированный язык описания системы команд процессора с вариативной степенью детализации.

3. Самопереносимая среда выполнения программ, настраиваемая описанием системы команд процессора.

Апробация работы. Основные положения работы прошли апробацию на следующих научных конференциях: XLVIII, XLIX научная и учебно-методическая конференция Университета ИТМО (2019-2020 гг.), VIII, IX Всероссийский конгресс молодых ученых (КМУ) (2019-2020 гг.), 18th, 19th International Multidisciplinary Scientific GeoConference (SGEM) (2018-2019гг.).

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

Внедрение результатов работы. Результаты работы получены в рамках выполнения НИР-ФУНД № 619296 «Разработка методов создания и внедрения киберфизических систем» и внедрены в опытно-конструкторские и производственные процессы компаний ООО «ЛМТ», а также в учебный процесс Университета ИТМО в рамках реализации дисциплин «Основы разработки компиляторов» и «Низкоуровневое программирование» на факультете программной инженерии и компьютерной техники.

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

1. В работе «Метод обеспечения переносимости программного обеспечения на основе перенацеливаемой среды выполнения программ» автором предложен метод обеспечения переносимости программного обеспечения и методика его применения. Павловский Е.А. выполнял исследование исходного кода сред выполнения программ с целью оценки объема работы, необходимого для их адаптации к новым системам команд.

2. В работе «Retargetable compiler design issues» автором предложен подход к применению языка описания систем команд для адаптации компилятора без необходимости перекомпиляции его исходного кода, а также рассмотрены ключевые особенности применения предложенного языка. Кореньков Ю.Д. занимался разработкой языкового инструментария, необходимого для реализации предметно-ориентированного языка описания систем команд. Доронин О.В. выполнял исследование архитектуры семейства компиляторов GCC и платформы для построения компиляторов LLVM. Садырин Д.С. описал возможный сценарий процесса исследования пространства проектных решений при проектировании встраиваемых вычислительных систем.

3. В работе «Реализация метаязыковой абстракции для поддержки ООП средствами языка Си» исследовалась возможность расширения синтаксиса языка Си с целью его дальнейшего применения для разработки описаний программных моделей архитектур процессоров. Необходимость данного исследования обусловлена проблемой аннотирования сложно-функциональных блоков «систем на кристалле», представленных на языках описания аппаратуры (VHDL, Verilog), для получения информации о программной модели архитектуры с целью генерации описаний на разработанном языке. Автором выполнено исследование области разработки предметно-ориентированных языков, сформулированы общие принципы их реализации. Жирков И.О. и Кореньков Ю.Д. осуществляли реализацию механизмов инкапсуляции, наследования и полиморфизма средствами препроцессора языка Си.

4. В работе «Problem research and development of a tool for checking application binary interface compatibility of virtual method tables» автором предложено средство для проверки бинарной совместимости приложений. Дергун К.И. выполняла обзор проблемы совместимости приложений на уровне программных и бинарных интерфейсов приложений. Кореньков Ю.Д.

выполнял исследование структуры таблиц виртуальных методов. Доронин О.В. осуществлял оценку эффективности разработанного средства.

5. В работе «Declarative target architecture definition for data-driven development toolchain» автором предложен язык описания архитектур целевых платформ. Кореньковым Ю.Д. разработан синтаксический и семантический анализатор для предлагаемого языка описания систем команд. Лаздиным А.В. осуществлялось исследование возможностей описания архитектур процессоров средствами компиляторов GCC и LLVM.

6. В работе «Применение декларативной модели описания целевых архитектур к существующим ISA» автором разработано демонстрационное описание архитектуры с использованием разработанного предметно-ориентированного языка. Кореньковым Ю.Д. рассмотрены особенности некоторых инструкций. Лаздиным А.В. выполнен обзор возможностей LLVM. Кузенкова Е.В. сформулировала общую характеристику проблематики разработки инструментальных средств.

7. В работе «Сравнение сборщиков мусора в различных платформах» автором выполнен анализ производительности некоторых существующих сборщиков мусора. Кузенковой Е.В. выполнена обработка полученных данных. Кореньковым Ю.Д. осуществлялось техническое обеспечение эксперимента. Соответствие диссертации паспорту научной специальности. Диссертационная работа соответствует паспорту научной специальности

05.13.11 «Математическое обеспечение вычислительных машин, комплексов и компьютерных сетей», а проведенное исследование - формуле специальности. Исследование соответствует следующим пунктам паспорта специальности.

1. Модели, методы и алгоритмы проектирования и анализа программ и программных систем, их эквивалентных преобразований, верификации и тестирования.

2. Языки программирования и системы программирования, семантика программ.

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

Введение диссертации (часть автореферата) на тему «Методы и средства эквивалентного преобразования программ на основе переносимой среды выполнения»

Объем и структура работы.

Диссертация состоит из введения, четырех глав, заключения, списка литературы (104 источника). Содержит 111 страниц текста, включая семь таблиц и 22 рисунка.

СОДЕРЖАНИЕ РАБОТЫ

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

В главе 1 исследуется предметная область - методы и средства обеспечения переносимости программ и программных систем.

Переносимостью, согласно стандарту ГОСТ Р ИСО/МЭК 25010-2015, называется характеристика программного продукта, определяющая степень простоты эффективного и рационального переноса системы, продукта или компонента из одной программно-аппаратной среды в другую. Переносимое программное обеспечение может использоваться на множестве вычислительных платформ, представленных операционными системами разных семейств, процессорами различных архитектур. Для обеспечения переноса приложений на различные платформы необходимы средства, позволяющие осуществить трансляцию исходного кода программ в машинный код, поддерживаемый данными платформами.

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

системы, которые разрабатываются в рамках отдельных проектов - встраиваемые системы. Одним из технических решений, применяемых при реализации встраиваемых систем, является использование «систем на кристалле». В виду большой сложности «системы на кристалле» создаются с использованием готовых компонентов - сложно-функциональных блоков, которые применяются в различных сочетаниях и конфигурациях, что приводит к уникальности архитектуры каждой встраиваемой вычислительной системы. Архитектура систем на кристалле описывается при помощи низкоуровневых языков описания аппаратуры (Hardware Description Language, HDL), таких как Verilog, VHDL, которые не предназначены для построения моделей выполнения программ и разработки программного обеспечения. Таким образом, универсальные средства для разработки аппаратной части встраиваемых систем существуют, но три этом отсутствуют средства разработки программного обеспечения, необходимого для функционирования вновь разрабатываемых встраиваемых систем. Для разработки программного обеспечения таких систем необходимы инструментальные средства, ориентированные на вновь создаваемые системы команд, включая компиляторы, отладчики, профилировщики.

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

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

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

код, определенный стандартом ECMA-335, что позволяет использовать существующие компиляторы языков программирования высокого уровня.

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

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

Таблица 1 - процедура адаптации среды выполнения

# Действие Объект Параметр

A01 Load runtime instance as builder

A02 Load executable

A03 Load target description

A04 Validate typesystem hardware properties

A05 Check external dependencies executable imports

A06 Trace memory manager memory model

A07 Retarget instruction selector target description

A08 Retarget instruction scheduler

A09 Retarget register allocator

A10 Extract class library profile executable

A11 Configure image builder binary format spec

A12 Build runtime binary

Ниже описана последовательность действий, необходимых для адаптации среды выполнения.

А01. Загрузка экземпляра среды выполнения на исходной платформе. Загрузка осуществляется в режиме утилиты-построителя бинарных образов.

А02, А03. Загрузка исполнимого модуля приложения, содержащего байт-код и описание системы команд целевой платформы.

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

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

А06. Трассировка менеджера памяти для проверки возможности доступа к объектам программы с учетом выбранной дисциплины планирования ресурсов.

А07-09. Генерация кода адаптированных версий селектора и планировщика команд, распределителя регистров.

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

А11. Определение формата бинарного модуля среды выполнения с учетом требований целевой платформы.

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

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

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

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

1. Выполнить переименование значений таким образом, чтобы минимизировать зависимости инструкций по данным.

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

3. Выполнить приоритезацию операций на основе наибольшей длины пути от данного узла до корня дерева.

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

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

программ. В частности, это касается менеджера памяти, средств отладки и профилирования приложений.

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

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

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

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

Описание системы команд записывается в виде именованного блока architecture, содержащего описание соответствующих конкретной архитектуре процессора аспектов: регистрового, организации адресных пространств, инструкций, мнемоник, ограничений и отображения функциональности байт-кода на инструкции. Каждый аспект именуется соответствующим словом. Структура описания системы команд выглядит следующим образом: architecture archName {

registers: /* регистровый аспект */

memory: /* аспект организации адресных пространств */

instructions: /* аспект инструкций */ mnemonics: /* аспект мнемоник */

}

Аспекты в составе блока описания архитектуры могут встречаться в любом порядке и любое количество раз. В зависимости от специфики системы команд незадействованные аспекты могут быть опущены. Для описания регистровой модели используется синтаксис, представленный ниже. Синтаксис позволяет описывать различные регистровые модели процессоров, создавать «представления» - интерфейсы для доступа к физическим хранилищам, которые могут быть представлены регистрами процессора или отдельными их частями, а также памятью. Ниже приведен пример синтаксического описания регистров процессора. registers:

/* физический регистр и его размер (количество бит). */ storage <name>[<bits count>];

/* интерфейс доступа к физическому регистру (представление)*/ view <name> = <storage name>;

/* отображение одного бита физического регистра на представление*/

view <name> = <storage name>[<bin index>]; /* отображение фрагмента регистра на представление */ view <name> = <storage name>[<from>..<to>]; view <name> = {<storage1 name>[<from>..<to>],

<storage2 name>[<from>..<to>],

};

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

/* диапазон памяти */

range <name> [<min address>..<max address>] {

/* размер адресуемой ячейки памяти в битах*/ cell = <memory cell size in bits>; /* порядок байт (little-endian или big-endian) */ endianness = <bytes order spec>;

/* требование к выравниванию при обращении к диапазону */ granularity = <r/w operations alignment>;

}

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

Поля могут быть представлены:

1) в виде шаблонов, состоящих из символов 0 и 1, опционально разделяемых пробелами (шаблоны могут быть предопределены для повторного использования);

2) аргументами в виде значения, интерпретируемого как адрес или данные;

3) аргументом в виде ссылки на регистр.

Последовательность операций описывается в формате, синтаксически похожем на язык Си, и предписывает выполнение операций над состоянием процессора. Поддерживаются возможности в виде стандартных выражений вида «а = b», содержащих бинарные и унарные операции (арифметические, логические, сравнения, битовые), объявления переменных, блоков, условных конструкций, циклов (с пост- или предусловием). Синтаксическое описание данного аспекта представлено ниже:

instructions:

instruction <name> = { <comma-separated list of fields and fixed bit patterns> } {

/* последовательность операций */

};

/* непрерывная последовательность бит */ instruction nop = { 10010000 }; /* биты могут быть сгруппированы */ instruction invd = { 0000 1111, 0000 1000 };

/* Описание поля может быть дополнено указанием способа интерпретации его значения в составе инструкции (data, offset, displacement). */ encode <name> field = immediate[<bits count>];

encode <name> field = immediate[<bits count>] <interpretation>;

/*

Описание поля, ссылающегося на регистр, содержит список возможных

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

*/

encode <name> field = register { <reg view 1 name> = <bits>, <reg view 2 name> = <bits>

}

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

mnemonics:

/* предопределенная форматная строка */ format <name> is "format string>"; /* группа форматных строк */

format <name> of <comma-separated predefined format spec>; /* определение мнемоники */

mnemonic <name> <comma-separated format per insn specs>;

В качестве примера приводится фрагмент описания инструкции и мнемоники adc3w1. instructions:

encode rmModByte sequence = alternatives {

rm00reg = { 00, rmModByteReg as reg1, rmMod00AsReg as reg2 }, rm00sib = { 00, rmModByteReg as reg1, 100, sequence sibByte }, rm00off = { 00, rmModByteReg as reg1, 101, off32 as off }, rm01reg = { 01, rmModByteReg as reg1, rmModXXAsReg as reg2, off8 as off },

rm01sib = { 01, rmModByteReg as reg1, 100, sequence sibByte, off8 as off},

rm10reg = { 10, rmModByteReg as reg1, rmModXXAsReg as reg2, off32 as off },

rm10sib = { 10, rmModByteReg as reg1, 100, sequence sibByte, off32 as off },

rm11reg = { 11, rmModByteReg as reg1, rmMod11AsReg as reg2 }

};

instruction adc3w1 = { 0001 0011, sequence rmModByte }; mnemonics:

format sib-to-plain of (reg1, reg2) "{1}, [{2}]" when rm00reg,

(reg1, r32) "{1}, [{2} * 1]" when rm00sib and x1, (reg1, r32) "{1}, [{2} * 2]" when rm00sib.and x2, (reg1, r32) "{1}, [{2} * 4]" when rm00sib and x4, (reg1, r32) "{1}, [{2} * 8]" when rm00sib and x8, (reg1, off) "{1}, [{2}]" when rm00off,

(reg1, reg2, off) "{1}, [{2} + {3}]"when rmModXXAsReg,

(reg1, r32 , off) "{1}, [{2} * 1 + {3}]" when x1, (reg1, r32 , off) "{1}, [{2} * 2 + {3}]" when x2, (regí, r32 , off) "{1}, [{2} * 4 + {3}]" when x4, (regí, r32 , off) "{1}, [{2} * 8 + {3}]" when x8, (reg1, reg2) "{1}, {2}" when rm11reg;

mnemonic adc for adc3w1(...) sib-to-plain;

Каждый из описанных форматов аргументов мнемоники, содержащий заданные фрагменты, будет сопоставлен варианту кода операции. Например, вариант с двумя аргументами reg1 и off будет соответствовать коду операции с вариантом rm00off в последовательности rmModByte, которая выглядит так: 00, rmModByteReg as reg1, 101, off32 as off.

Результирующий код операции будет следующим:

0001 0011, 00, <encoded register>, 101, <32-bit number>.

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

Процесс проектирования

специализированной (встраиваемой) системы

v

Рисунок 2 - Место языка описания архитектур целевых платформ в процессе проектирования встраиваемых систем

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

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

В главе 4 решается задача проектирования и реализации переносимой среды выполнения программ. Решение основано на опыте разработки сред выполнения программ JVM и CLR, в основу которых заложена модель двухэтапной трансляции. Использование данной модели трансляции необходимо, так как позволяет решить

проблему бинарной переносимости приложений, оставляя открытым вопрос переносимости самой среды выполнения.

На текущий момент переносимость сред выполнения обеспечивается на уровне исходного кода, для чего выполняется адаптация отдельных компонентов или повторная разработка сред выполнения. Предлагаемый подход к реализации адаптируемой среды выполнения основан на применении языка описания систем команд. Существующие инструментальные средства, которые могут быть адаптированы к новым системам команд процессоров с использованием таких языков, требуют доработки их кода и последующей перекомпиляции. Предлагаемая архитектура переносимой среды выполнения предполагает наличие байт-кода самой среды выполнения, который позволяет выполнять генерацию ее адаптированного машинно-ориентированного представления для заданной системы команд. Это позволяет осуществлять генерацию машинно-ориентированного кода без изменения исходного кода среды выполнения и его перекомпиляции. Компоненты среды выполнения представлены на рисунке 3. Исполнимый модуль приложения и описание системы команд целевой платформы являются входными данными для среды выполнения и используются для настройки ее компонентов: менеджера памяти, генератора кода (компилятора или интерпретатора), службы отладки и профилирования.

Рисунок 3 - Компоненты среды выполнения программ

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

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

Реализация данного метода в виде самопереносимой среды выполнения и описаний систем команд процессоров Intel x86-64 и ARM демонстрирует показатели производительности, сопоставимые с применяющимися в индустрии реализациями сред выполнения, однако нуждается в доработке. На рисунке 4 показано время, необходимое на осуществление сборки мусора в различных средах выполнения программ, а на рисунке 5 показано время выполнения сортировки массива методом вставок. Показатели для реализации среды выполнения в рамках данной работы на рисунках показаны под названием «Portable Runtime».

re

¡= а 5 8

t I

О й

и

1400 1200 1000 800 600 400 200 0

/

I

Ч®

.1

cJ>

I . .1 . .

I

&

✓

Средняя продолжительность сборки мусора ■ Максимальная продолжительность сборки простоя

Рисунок 4 - Продолжительность сборки мусора, мс

а

Сй

900 800 700 600 500 400 300 200 100 0

I

I

Ханои20

Sort1000 Sort5000

C □ Python ■PortaЫe Runtime (C#)

Sort10000

Рисунок 5 - Сравнение времени выполнения алгоритмов сортировки и решения

задачи "Ханойская башня"

Ключевым аспектом данного метода является обеспечение эквивалентности преобразования программ. Для подтверждения эквивалентности преобразования валидация результатов преобразований выполняется с использованием двух платформ - исходной и целевой. Для каждой из них генерируется образ среды выполнения, при этом эквивалентность преобразования программ средой выполнения на исходной платформе подтверждается использованием апробированных трансляторов. Контрольные испытания позволяют проверить функционирование среды выполнения в части выполнения арифметико-логических операций, циклов, условных переходов, корректной инициализации объектов, отсутствия бесконечных рекурсивных вызовов подпрограмм. Схема организации эксперимента показана на рисунке 6.

Рисунок 6 - Организация экспериментальной проверки эквивалентности

преобразований

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

Рисунок 7 - Процедура обратного переноса среды выполнения

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

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

Заключение

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

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

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

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

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

Список литературы диссертационного исследования кандидат наук Логинов Иван Павлович, 2020 год

Литература

1. Deniau L. The С object system: using С as a high-level object-oriented language. arXiv.org. 2010. URL: https://arxiv.Org/abs/l003.2547 (дата обращения: 20.03.2018).

2. Mernik M., Heering I, Sloane A.M. When and how to develop domain-specific languages. ACM Computing Surveys (CSUR), 2005, vol. 37, no. 4, pp. 316-344. DOI: http://doi.acm.org/10.1145/ 1118890.1118892.

3. Фаулер M., Парсонс P. Предметно-ориентированные языки программирования. М.: Вильяме, 2011. 576 с.

4. Jacobs М., Lewis Е.С. SMART С: a semantic macro replacement translator for С. Proc. 6th IEEE Intern. Workshop Source Code Analysis and Manipulation (SCAM'06), 2006, pp. 95-106.

5. Smith B. Object-oriented programming: In Advanced ActionScript 3.0: Design Patterns, USA, NY, Apress, 2011, pp. 1-25.

6. Pecinovsky R., Pavlickova J., Pavlicek L. Let's modify the objects-first approach into design-patterns-first. ACM SIGCHI Bui., 2006, vol. 38, no. 3, pp. 188-192.

7. Ernst M.D., Badros G.J., Notkin D. An empirical analysis of С preprocessor use. Software Engineering, IEEE Transactions, 2002, vol. 28, no. 12, pp. 1146-1170. DOI: 10.1109/TSE.2002.1158288.

8. MeyersR. The new С: X macros. 2001. URL:

http://www.drdobbs.com/the-new-c-x-macros/1844 01387 (дата обращения: 20.03.2018).

9. Подбельский В.В. Динамическая идентификация типов (ДТП): В кн.: Язык Си++. М.: Финансы и статистика, 2003. 560 с.

lO.Fokin A., Troshina К., Chernov A. Reconstruction of class hierarchies for decompilation of С++programs. Proc. 14thEurop. Conf. Soft. Maintenance and Reengmeering. ГЕЕЕ, 2010, pp. 240-243. DOI: 10.1109/csmr. 2010.43.

Software & Systems Received 29.05.18

DOI: 10.15827/0236-235X. 126.190-196 2019, vol. 32, no. 2, pp. 190-196

Implementing metalinguistic abstraction to support OOP using C

A.M. Dergachev 1, Ph.D. (Engineering), Associate Professor, dam60CXa),gmail.com

I.O. Zhirkm>l, tutor, igorjirkov@gmaiLcom

LP. Loginov l. Postgraduate Student [e-mail]

Yu.D. Korenkov \ Postgraduate Student, ged.yuko(a)gmait.com

1 The National Research University of Information Technologies, Mechanics and Optics, St. Petersburg, 197101, Russian Federation

Abstract. The paper shows the use of higher order macro definitions to support the object-oriented programming paradigm in C89 without extensions. Choosing the right programming style is important prior to writing a code. A large class of problems is described using object-oriented programming style. Many mainstream programming languages such as C++, C# or Java provide support for this programming style. However, it is not always possible to utilize these languages as the required development software such as compilers for some platforms might not be available. A typical example of this situation is Application-Specific Instruction-set Processor (ASIP), which is provided with a C compiler. The smaller set of C- language features and its low-level nature allow quick and cheap compiler implementation. At the same time, the C preprocessor can be used for a sophisticated logic generation that goes far beyond simple parameterized substitutions.

This paper presents an internal support of the object-oriented programming style implemented in C-89 without language extensions via an extensive usage of higher-order macro definitions. The example code shows the implementation of encapsulation, inheritance and polymorphism principles. Encapsulation syntactically prohibits accessing private fields and methods in compile time. We pay special attention to type-safety of generated code: the inheritance implementation does not weaken the already weak static typing used in C.

The results of this work can be used to construct object-oriented programs using only C-89 compiler in case the usage of object-oriented languages is impossible.

Keywords: C-, preprocessor, object-oriented programming, metaprogramming, macro definition.

References

1. DeniauL. The C Object System: Using C as a High-Level Object-Oriented Language. 2010. Available at: https://arxiv.org/abs/1003.2547 (accessed March 20, 201S).

2. MernikM., Heering J., Sloane A.M. When andhow to develop domain-specific languages. ACM Computing Surveys (CSUR). 2005, vol. 37, no. 4, pp. 316-344. DOI: http://doi.acm.Org/10.l 145/1118890.1118892.

3. Fowler M., Parsons R Domain-Specific Languages. Addison Wesley Publ., 2010, 640 p. (Russ. ed.: Moscow, Volyams Publ., 2011, 576 p.).

4. Jacobs M., Lewis E.C. SMART C: A semantic macro replacement translator for C. SCAM'06. 6th IEEE Intern. Workshop on. Source Code Analysis and Manipulation. 2006, pp. 95-106.

5. Smith B. Object-oriented programming. Ad\>ancED ActionScript 3.0: Design Patterns. Apress, 2011, pp. 1-25.

6. Pecinovsky R., Pavlickova J., Pavlicek L. Let's modify the objects-first approach into design-patterns-first. ACMSigcse Bui 2006, vol. 38, no. 3, pp. 188-192.

7. Ernst M.D., Badros G. J., Notkin D. An empirical analysis of C preprocessor use. IEEE Trans, on Software Engineering. 2002, vol. 28, no. 12, pp. 1146-1170. DOI: 10.1109/TSE.2002.1158288.

8. Meyers R. The New C:XMacros. Dr.Dobb's 2001. Available at: http://www.drdobbs.com/the-new-c-x-macros/i 84401387 (accessed March 20, 2018).

9. Podbelsky V.V. 12.6 Dynamic Type Identification (RTTI). C++. 4th ed. Moscow, Finansy i Statistika Publ., 2003, 560p.

10.Fokin A., Troshina K., Chernov A. Reconstruction of class hierarchies for decompilation of C++ programs. IEEE Nth European Conf on Software Maintenance andReengineering. 2010, pp. 240-243. DOI: 10.1109/csmr. 2010.43.

DECLARATIVE TARGET ARCHITECTURE DEFINITION FOR DATA DRIVEN DEVELOPMENT TOOLCHAIN

Iurii Korenkov1, Ivan Loginov1

Assoc. Prof. Andrey Dergachev1, Arthur Lazdin1

1ITMO University, Russia

ABSTRACT

Today retargetable and cross-platform compilers are mainstream, because variety of hardware platforms is very large, and it is required to support general-purpose programming languages for these platforms. But retargetable compiler development process has very high cost. The main criterion is development time (develop, debug and maintain time, high entrance level). Some of the most popular solutions on the market of these compilers are GCC, LLVM. Each of them contains (in implementation) platform-specific code like platform-specific functions' implementations [1].

In general, each platform (in this context - processor architecture or hardware platform in general case) requires development its own compiler, specific for this instruction set or/and memory model, etc. One of the most complicated aspect of compiler development is to make it modular. For example, it means, that it is possible to create a custom module for GCC to support some particular architecture. Development of such module among other tasks commonly incorporates hardcoding description of the instruction set, optimizations implementation, debugger support. The concept of our solution is introduced in this paper.

Keywords: compiler, DSL, language workbench, data-driven development INTRODUCTION

The GCC compiler uses the Register Transfer Language (RTL) [2]. RTL is the form of a program intermediate representation (IR), that looks like abstract assembly for the abstract machine with registers and memory. Besides GCC, RTL is used by other compilers, for example, CompCert [3]. In addition to IR by means of RTL it is possible to define descriptions of the software architectures of the target CPUs. Consider a small example of code in the GCC RTL definition in the Listing 1. This example shows definition of procedure of translation to code for the target platform.

Example code parts meanings: (1) Define instruction pattern, (2) Pattern name, (3) RTX (RTL expression) - target instruction semantics, (4) C boolean expression, if required; (5) Target instruction in target assembly syntax.

(define_msn /* (1) */ "movsi" /* (2) */ (set /* (3) */ (match operand 0 "register operand" "r") (match operand 1 "const int operand" "k") ) "" /* (4) */ "1 i%0, %1" /»(5)*/) Source: D.XXXX = YYYYY; Transormation: (set (reg:SI 58 [D.XXXX]) (const int YY: [YYYYYh]) ) Result: li $t0, YYYYY

Listing 1 Example of target arch instruction for GCC and results of translation of this code:

https://doi.Org/10.5593/sgem2018/2.l/S07.035

to introduce the declarative target architecture definition syntax and API to reduce support time and domain entrance threshold.

PROPOSED NOTATION BASICS

Notation for target architecture definition should describe various aspects of the architecture, meaningful for an application developer. Minimum core subset of such aspects includes following: memory model structure (addressable regions and registers), opcode encodings for instructions and optionally corresponding mnemonic formats. As soon as main purpose is possibility to describe architectures intended to be a hardware computation models, this core features subset is sufficient for the first approach. Based on this, we are proposing extensible but not redundant format, consisting of architecture aspects enumeration, where each aspect defined in a form, which could be easily read, written and supported by a maintaining person without deep knowledge of the particular tool infrastructure, such as compiler-specific stages pipeline.

Top level of the proposed notation includes target architecture aspects enumeration. All aspects should be described inside an architecture block as shown at Listing 3.

architecture TestArch { memoiy: /* addressable spaces information */ registers: /* registers model information */ instructions: /* part of instruction definitions */ mnemonics: /* part of mnemonic definitions */}

Listing 3 Top level of an architecture definition

Aspects definition can be split into multiple entries so that logically connected parts of various aspects could be described together but not interfering with each other.

Architecture definitions do not have to be complete in terms of functionality and computational completeness. They could be split into few fragments, where each block of functionality can be described as subset. Those subsets could be reused through import semantics in the particular complete architecture definition.

While proposed format and current implementation of the related instrumentation are designed in an extensible way, below is the brief overview of the core aspects.

I. Registers configuration

A part of a memory model, representing registers configuration, described in terms of physical data location cells (storages) and their addressable fragments (views).

Figure 3. Red, blue and green line

registers:

storage X[32];

storage Y[32];

view A = X[24..31];

view B = { X[0..15], Y[16..24] };

view C = Y;

Listing 4 Registers storages and views relations example

Where X and Y are 32-bit register storages. Register view A provides access to the higher 8 bit for X, register view B provides access to combination of lower 16 bits of X and lower half of the higher word of Y (bits 16-23), register view C provides access to the whole content of storage Y.

B. Addressable spaces

Ranges of addressable memory or any other randomly addressable data holding entities are described with range bocks, see Listing 5.

memory:

range ram [0x0000..Qxffff] { cell = 8;

endianness = little-endian; granularity = 1;

}

Listing 5 Top level of an architecture definition

Here ram is name of the range, with which this range can be referred to. Numbers in the square brackets denotes valid address values for this range, cell element denotes size of range's cell in bits, endianness element denotes the order of the cells representing contiguous value of size more than one cell, when such value should be placed or taken from the range. It is also referred to as a byte order and can take one of the two values: little-endian or big-endian. The last part of the range description - granularity element denotes value, residue of division of effective address on which should be equal to zero for valid addressing operation.

C. Instruction set

Instruction is a minimum algorithmically meaningful encoding of the sequence of operations to be performed by an abstract interpreter. It is an atomic entity which is encoded by a bit pattern consisting of fields. Fields can denote either instruction parameters or fixed values, the purpose of the last ones is to distinguish various instructions from each other. Every possible instruction in a particular architecture should composed of such fields, that no other instruction can intersect with by a possible bit patterns of the whole opcode.

Description of every concrete instruction can be reflected by the following syntax representing an opcode encoding:

instruction <name> = { < list of fields > };

Besides, instruction definition can be followed by a function description:

instruction <name> = { < list of fields > } { <operations> };

Here <name> is a unique name for this instruction. List of fields is a comma-separated set of bit patterns and references to encodings for variable field entries. <operations> defines functional meaning of the instruction and describes operations with machine states in form similar to mix of RTL (register-transfer logic) and high-level programming language (see below). Table 7 represents possible entries of the opcode bit pattern encoding.

Table 7. Possible elements of the opcode fragment definition.

Representation Meaning

<bit pattern with spaces> Fixed parts of an opcode, represented by explicit bits

<field encoding name> as <value name> Variable part of an opcode, represented by referred value encoding

<field encoding name>.<value name> Fixed part of an opcode, represented by one element of the explicitly enumerated bit patterns

sequence <sequence encoding name> Variable part of an opcode, represented by predefined subset of the opcode fields

<sequence encoding name>(<subfields>) Same as previous with nested values renaming

Besides an instruction opcode pattern, there are simple and complex encodings for various parts of the opcode.

Simple encodings intended for description of immediate values, register references and predefined bit patterns:

encode <name> field = immediate[<bits count>]; encode <name> field = register {

<reg view 1 name> = <bits>, <reg view 2 name> = <bits>, ...

h

encode <name> field = cases {

<case 1 name> = <bits>, <case 2 name> = <bits>, ...

};

Complex encodings are sequence encodings and encodings of sequence alternatives:

encode <name> sequence = { <list of fields> }; encode <name> sequence = alternatives j

<case 1 name> = { <list of fields> }, <case 2 name> = { <list of fields> }. ...

};

Listing 6 demonstrates complex example of sequence alternatives encoding definition.

instructions:

encode rmModByte sequence = alternatives {

rmOOreg = {00, rmReg as regl, rmOOAsReg as reg2 j,

rmOOsib = {00, rmReg as regl, 100, sequence sibByte},

rmOOoff = {00, rmReg as regl, 101, off32 as off}, "

rmOlreg = {01, rmReg as regl, rmXXAsReg as reg2, off8 as off},

rmOlsib = {01, rmReg as regl, 100, sequence sibByte, offS as off},

rmlOreg = {10, rmReg as regl, rmXXAsReg as reg2, off32 as off},

rmlOsib = {10, rmReg as regl, 100, sequence sibByte, off32 as off},

rml lreg —{11, rmReg as regl, rml lAsReg as reg2} };

instruction adc3wl = { 0001 0011, sequence rmModByte }; Listing 6 Top level of an architecture definition

Each instruction encoding can be followed by an instruction function definition. Such instruction function may be used in a number of ways: as compiler translation stage guidance, as interpreting machine state transition descriptions, as basis for complexity estimation of an instruction sequences and encoded algorithms, etc.

Each instruction function can be considered as C function without explicit resulting value and with variable opcode fields as arguments. While immediate and cases kind

values are treated as read-only by value arguments, register references are treated as writable by-reference arguments.

Body of an instruction function, as well as in C, is treated as block, that consists of sequence of nested statements. Basic statements are: expression statement, variable declaration statement, block statement, condition statements, loop statements.

Expressions inside these statements can be represented by the combination of various operator expressions (arithmetic operations, bit operations, comparisons, logical operations, assignment, memory indexing) and literals such as following: binary (ObOOOllOlO), decimal (12345), hexadecimal (0x78ab25FD).

For the various alternative encodings of one instruction, appearing when the sequence alternatives are used, there is a special condition syntax similar to if statement with keyword when instead of it. This when statement denotes logic branch selection depending on presence of the fields or their combination in the particular opcode instance. Examples of <condition> element see below in the description of the mnemonics format matching.

D. Mnemonics

Mnemonics' purpose is to allow user to interact with native code representation. They stand for human-readable form of native code in a linear form, directly inherited from underlying nature of native instruction sequences.

Mnemonic definitions describe matching between every instruction opcode alternative and combination of mnemonic name and arguments format string. Mnemonic variants are described in various ways depending on instruction arguments and structure of part of the particular opcode fields. It is decomposable into multiple entries with additional conditions eliminating intersections between concrete opcodes.

It is possible to describe format string of the arguments once and then use it for many mnemonics with simultaneous formats. If the accompanied by the same opcode structure conditions group of argument format strings occurs in many mnemonics for different instructions, this group together with conditions can also be described separately from the particular mnemonics. Here are how basic elements of the mnemonics aspect look like:

format <name> is "<format strmg>"; /* predefined format string */

format <name> of <list of format specs>; /* predefined group of format strings */

mnemonic <name> <list of format per instruction specs>; /* mnemonic definition */

Each format in <list of format per instruction specs> begins with list of arguments and ends with optional conditions on opcode fields presence for mnemonics-to-opcodes matching ambiguities resolution. Instead of format string there each format entry can refer to the predefined format string or to the predefined group of format strings. In the latter case there should be an '...' designation on the place of the arguments denoting that actual argument lists resided in the referenced group definition:

format <name> of (<arg list 1>) "<format string 1>", (...) <format strings group name>, (<arg list 2>) "<format string 2>" when <condition>, (<arg list 3>) <format string name> when <condition>, ...

Note the difference between group of format strings and mnemonic with explicit multiple format strings:

mnemonic <name> for <insnname> (<arg names list 1>) "<format string 1>",

(...) <format strings group name>, for <insn name> (<arg list 2>) "<format string 2>" when <cond>,

(<arg list 3>) <format string name> when <condition>, ...

Each of the format spec entries in the mnemonic definition optionally preceded with instruction name so the following format strings would be matched to the variants of the referred instruction's opcode. So, the simples form of mnemonic definition is:

mnemonic nop ():

Such definition tells that there is instruction with name nop somewhere and its opcode has no arguments, thus no format string required. Here is complex example of the format definition for the adc3wl instruction mentioned above demonstrating all the elements together:

format sib-to-plain of (regl,reg2) "{l},[j2}]" whenrmOOreg,

(regl, r32) "{1}, [{2} * 1]" whenrmUOsib andxl, (regl, r32) "{1}, [}2j * 2]" when rm OOsib. and x2, (regl, off) "{1}, [{2}]" whenrmOOoff,

(regl. reg2, off) "{1}, [{2} + {3}]" whenrmXXAsReg. (regl, r32 , off) "{1}, [{2} * 1 + {3}]" whenxl, (regl, r32 , off) "{1}, [{2} * 2 + {3}]" whenx2, (regl,reg2) "(1}, {2}" whenrmllreg;

mnemonic adc for adc3wl(...) sib-to-plain;

MANIPULATION API

A set of libraries was created for the proposed notation. These libraries expose few levels of API for manipulations with target architecture definition: definitions source text model, architecture definitions model, architecture information semantic model, native code and mnemonic operations.

When some tool uses target architecture definitions as its input for manipulations with native code, these APIs are used during this tool initialization.

At first, particular architecture definition should be read from one or multiple text files. As a result of their parsing, source text models are produced. Then during translation process these text models are gathered into one rich target definition model. Here is where aggregation of the information from multiple input definition files occurs. When all required aspects and subsets are introduced into definition model, next step is collection. Collection means selection from the introduced definitions of all information required for the concrete target architecture model to be functionally and computationally complete. During this step, a number of actions take place: merging of subsets, resolving of dependencies between definition parts and validation of the instruction encodings.

As a result of collection step, an object implementing IArchitecturelnfo interface is produced. Besides information about current architecture, this object has two methods named CreateNativeCodeParser and CreateMnemonicsParser. They provide a way to perform conversions between mnemonic representation of instructions and native code

bytes. As every native instruction instance description associated with corresponding parts of the complete architecture info, robust opportunities for various code analysis, validation, generation and other tools creation exist.

In addition to basic scenario, this APIs can be used to generate architecture definitions programmatically: on source model level and on complete definition level. It makes architecture definitions itself a subject of manipulation. This is where metamodeling begins with all of its might in models' manipulation, transformations and such.

CONCLUSION

Developed declarative target platform architecture definitions format and supporting libraries demonstrate that model-based approach can be easily expanded to the low-level tools development bringing almost the same level of customizability, as in pure high-level modelling software such as Eclipse Modelling Framework.

For the evaluation of the proposed solution, few experimental tools were created: compact assembler with NASM-like syntax, disassembling tool as analogue to objdump utility, simple command-line debugger, syntax highlighting profile for our language workbench [7].

When the core functionality of the library was implemented, it was not a troublesome task to use its API to create an example tools and achieve consistency in their behaviour.

Further work would be concentrated primarily on the high-level code processing features: (1) ensure, that proposed notation allows describing the majority of actual hardware architectures on the market; (2) common intermediate models framework creation, intended to be used as target-architecture-independent basis for manipulations with algorithm intermediate representations of the programs; (3) generalized IR translation algorithms between various particular computational models; (4) complete modular compiler pipeline based on described principles and introduced libraries; (5) retargetable without toolchain recompilation compiler driven by proposed target architecture definitions.

REFERENCES

[1] GCC, the GNU Compiler Collection website, Web: https://gcc.gnu.0rg/0nlined0cs/gcc/Target-Builtins.html#Target-Builtins

[2] GCC, the GNU Compiler Collection website, Web: https ://gcc. gnu.org/ onlinedocs/gccint/RTL.html

[3] Kastner, Daniel, et al. "CompCert: Practical Experience on Integrating and Qualifying a Formally Verified Optimizing Compiler." ERTS2 2018-Embedded Real Time Software and Systems. 2018.

[4] The Conceptual Structure of GCC, Web: https://www.cse.iitb.ac.in/grc/intdocs/gcc-conceptual-structure.html

[5] The Architecture of Open Source Applications, LLVM, Web: http://aosabook.org/en/llvm.html

[6] Korenkov, Yuriy, Ivan Loginov, and Arthur Lazdin. "PEG-based language workbench." Open Innovations Association (FRUCT), 2015 17th Conference of. IEEE, 2015.

PROBLEM RESEARCH AND DEVELOPMENT OF A TOOL FOR CHECKING APPLICATION BINARY INTERFACE COMPATIBILITY OF VIRTUAL

METHOD TABLES

Oleg Doronin1, Karina Dergun1, Ivan Loginov1, Iurii Korenkov1 Assoc. Prof. Andrey Dergachev1

1ITMO University, Russia

ABSTRACT

Backward-compatible software allows to change its libraries without rebuilding and adapting the interface used for interaction between its components or other applications (application programming interface, API). Application binary interface (ABI) compatibility is important for application portability. There are ready-made solutions to verify binary compatibility, such as libabigail and ABI-compliance tools. Such tools have several disadvantages. For example, libabigail works only with libraries containing DWARF information. The ABI-compliance library can work without DWARF information, but it does not provide full information about the virtual method tables.

The aim of this work is to solve the problem of compatibility verification for virtual method tables. Changes covered include when addition, removal and modification of records in such tables. The paper analyzes advantages and disadvantages of libabigail and ABI-compliance libraries related to binary compatibility issues and virtual method tables. Based on the analysis, we developed a new application free from the problems found in the libabigail and ABI-compliance libraries. We solved the dependency on DWARF information; realised ability to get full information about virtual methods tables and increased performance compared to competitors. The paper presents a comparative analysis of the algorithms when applied to libraries such as boost, libcds and others. Results show that the developed tool is effective when used in software applications to determine binary compatibility of virtual method tables.

Keywords: backward compatibility, virtual methods table, application binary interface, application program interface, binary compatibility analysis

INTRODUCTION

Nowadays software development process brings a lot of changes in applications on different levels: from GUI to internal applications design. This generates the compatibility issues. Each application based on some third-party components (e.g., class libraries, operating system services, web services, etc.) that provides base functionality. Changes in these components can make impossible to use them from software in the same way, without changes, or can lead software, based on these components, to unexpected behaviour. There are two abstractions that can help software developers to avoid this issue.

The first, application programming interface (API) is a contract, that declares the way of interacting between computer programs or platforms, in other words, the interface for

interaction. This is a source code-level abstraction which provides functionality (functions, data structures, classes) and specifications to use it correctly. These specifications could be presented in different formats: header files for C-based APIs (like libc, Windows API), metadata for .NET/JVM-based APIs, etc. When software developer changes some aspects of the application's implementation, it does not break the compatibility between the components. In other case, changes in a used third-party component don't affect the software.

The second, application binary interface (ABI) is a set of conventions for application access to the operating system functionality and other low-level services designed for portability of executable code between machines. Unlike the API that regulates source-level compatibility, ABI can be thought of as a set of rules that allow the linker to combine compiled component modules without recompiling all of the code while at the same time defining the binary interface. The general notion of backward compatibility is the presence in the new version of the computer program or the computer hardware interface present in the old version, resulting in other programs (or users) can continue to work with the new version without significant alteration. Full backward compatibility means that replacement of the old version of a component, the whole system will not be compromised. In terms of binary compatibility, only the ABI compatibility check is performed. Binary compatibility is a necessary requirement to maintain backward compatibility that allows us to safely and quickly provide user updates with a replacement for the implementation rather than the interface. Failure of backward compatibility at the ABI level can lead to errors in the software. For example, when some function was called, a completely unexpected result may be obtained. Such errors are difficult to catch and can cause catastrophic effects, bring vulnerabilities in applications.

Application binary interface includes low-level implementation aspects like processor architecture (instruction set architecture, memory model), runtime-used information (conventions to call functions, make system calls), the format of the object file. Maintaining compatibility on the ABI level leads us to check this all information before the providing of a new version of software to the end-user. In some cases (related to application or platform design issues) this is impossible and creates a lot of work for developers to test or verification software which depends on this component and to make updates to fix negative effects.

One of the popular programming languages which is related to ABI-compatibility issues is C++ [1]. In other cases, like with Java, C# or Python, it is not a problem, because programs executes in a virtual machine or by the particular interpreter. C++ code compiles to the platform-specific code and both compiler developer and software developer need to think about some specifics, like alignments, sizes of data types. One of these specifics is the virtual method table (also named VMT, vtable) - data structure which is needed to dispatch virtual functions and provide runtime type information (RTTI).

The structure of virtual method tables

Any vtable contains addresses of dynamically linked object methods. During the dispatch, the method address is fetched from the table and then the method is called. The VMT will be the same for all objects belonging to the same class, so it can be shared. Objects of type-compatible classes (for example, those of types located one step down the

inheritance tree) will have similar coordinating tables: the position of each shared method address in the table is fixed with the same offset for all classes that are compatible by type. Tims, by selecting the address of the method from vtable with an offset, we get the method associated with the current object class [2].

C++ standards do not clearly define how dynamic coordination should be implemented, but compilers often use variations of the same underlying model. Typically, the compiler creates a separate vtable for each class. The pointer to this vtable is known as a virtual table pointer or vpointer (also sometimes called vptr or vfptr). After the object is created, a vpointer is added as a hidden member of the object (often as the first member). The compiler also generates "hidden" code in the constructor of each class to initialize the vpointer of its objects with the addresses of the corresponding vtable. For example, the following is a class and its virtual method table:

struct Task

{

virtual void execute(); virtual const char* get name(); virtual Type get type();

virtual void set_context (const Contexts; context);

1;

vtable for Task (_ZTV4Task)

0 0

8 typeinfo for Task

16 void Task::execute() 2 4 char const * Task : : get_narne ( 32 Type Task::get type()

40 void Task: : set context (Context constSi)

It is very easy to break the application's backward compatibility. Certain type of source code changes can affect it:

• removal of an exported class or class export label;

• changes to the class hierarchy;

• changes to template arguments;

• removal of a function, labelling a function, addition of inline keyword to the signature of a function, changing the qualifiers, and more;

• removal, reordering or addition of virtual methods;

• removal, a change of object's field type, or a change of object's field order.

The full list of changes that may affect binary compatibility is much longer than shown above, but this work is focused on virtual methods only.

VTABLE BACKWARD COMPATIBILITY CHECKING

To create a good and careful compatibility checking solution, binary file analysis should be made. Analyzing binaries without any metadata creates a lot of headache for developers, but some data could be used to do that. First of all, binaries are implemented by some specification. It could be ELF, portable executable (PE) and others. The best

case if source code and debugging information are available, but it is not always realistic. Anyway, it is possible and this case will be considered.

One of the widespread formats of debugging information is the DWARF (debugging with attributed record formats) [3]. It used to describe programs in C and other similar programming languages. It was originally developed by Bell Labs for use with the UNIX System V debugger named sdb. Special in-memory data structures were used for DWARF data representation algorithm implementation. It has resulted in a significant increase in performance compared to libabigail [4] and ABI-compliance tools [5]. Special inmemory data stmctures were used for DWARF data representation algorithm implementation. It has resulted in a significant increase in performance compared to libabigail and ABI-compliance.

A special cache was used for storing data such as function names, types, variables, and others. The cache maps unique strings to natural numbers. The cache uses a tree data structure, which allows for 0(Jen(yv)) complexity of lookup/insert operations. Here ir is the word, len(w) is the number of characters in this word. The reverse build process uses dynamic array data structure, where the insert and delete operations take O(l) time

A hashtable can be used to lookup a function by its address. Hashtable lookup/remove and insert operations takes O(l) time on average. However, this constant can be sufficiently large to adversely affect the performance of the algorithm. Given high locality of function addresses, these addresses only differ in the last three bytes. Hence the improved hash table is used for the build, with the hash key being the last 3 bytes as opposed to the entire address. To store such a hash table, a regular array of size 224 is used. It provides for the guaranteed constant complexity of lookup/remove/insert operations, with the minimum possible value of this constant. Figure 1 shows a diagram to display the addresses in the data.

ffaddress, value) -> address := address % 2*24

get/insert/removefvalue)

Figure 1. Improved hash-table architecture.

Some libraries have no DWARF information. It is done to keep the size of binary files smaller. For example, size considerations can be important for embedded systems. To add debugging information into the binary file the source code should be compiled with -g option.

The ABI-compliance tool uses a dlopen-based algorithm to obtain information about virtual method tables. The algorithm of this approach is as follows:

1. The first step retrieves information about all the virtual method tables. To do this, the binary file [6] [7] is opened using the open system call and the file descriptor is passed to the library to work with the ELF fonnat. We can use the library to get a list of all the symbols in a binary file as well as their addresses. Symbols that contain information about virtual method tables begin with ' ZTV'; An example

of such symbol from a virtual table of the boost library is _ZTVN5boost6detail 17sp_counted_impl_pIP 12ompi_group_tEE

2. For each symbol of a table-related virtual method, the address and size information of the table is retrieved;

3. After the size is obtained, the number of rows in the table is calculated. The number of rows in the table is the size of the table divided by the pointer size;

4. The next step is to iterate through the rows of the table. The dlopen mechanism is used to iterate through the table;

5. The address is checked for each line. If the address is 0, it is a pure virtual method, and if the address is not zero, the information is searched using dladdr,

6. As a result, dladdr retrieves the row information in the virtual method table.

The algorithm described has an important advantage. It allows to retrieve the tables of virtual methods without using debugging data, which sometimes may not be in existing libraries. But the same approach has a number of significant disadvantages:

1. The binary representation of method names does not store the return type, so vtable that are ineompatible with the return type will not be defined;

2. It is not always possible to get the names of inline methods with dladdr;

3. There is no way to get information about pure virtual methods;

4. dlopen requires dependent libraries to be specified with LD PRELOAD variable.

DWARF information-based algorithm for virtual table information retrieval (libabigail)

The libabigail library relies solely on DWARF to extract virtual tables. The algorithm is:

1. Read the executable file into RAM;

2. Extract DWARF functions and types information;

3. Convert encrypted function names into a human-readable format;

4. Collate information about virtual method tables.

This algorithm breaks down completely if DWARF information is not found. The inability to display partial vtable information is another disadvantage.

DWARF and ELF - based algorithm for virtual table information retrieval (new approach)

The problem with the ABI-compliance library is its dependency on dlopen. It requires presence of all dependent libraries, which is not always practical. It also makes it harder to load two (or more) libraries into a single binary file, as the dependencies between libraries can be very different and/or conflicting. It is also impossible to compare binary files, but only shared libraries. To correct this problem, the following algorithm was developed:

1. Read ELF information about a binary file (with libelf library).

2. Extract virtual method table addresses and their sizes. The search of virtual method tables is made within the set of all symbols by the filter _ZTV;

3. Open an executable file as a regular binary file. Use the location from the previous step to read the virtual table contents.

4. Retrieve data of virtual method tables from the file.

5. Map the addresses to method names and convert function names into human-readable fonn.

6. If DWARF information is available, it is used for the return types, pure virtual functions, and inline functions.

The use of DWARF information on the last step allows to add fully qualified function names into the virtual table. Without type information the getnameQ method of the Task class would look like this:

2 4 Task::get_name(

In that case, we would not be able to verify backward compatibility with regards to return type. If we do not extract backward compatibility information about pure virtual methods through DWARF, the rows with pure virtual methods in virtual methods table will be displayed as follows:

2 4 0

That will not allow to detect replacement of one pure virtual method by another. This algorithm is free from the disadvantages of libabigail and ABI-compliance libraries, and also demonstrates better performance compared to its counterparts.

RESULTS

In the course of the work, a new tool was developed to extract information about the virtual method tables using ELF data. If there is DWARF information in the binary file, it is used to supplement the data obtained from the ELF. The newly developed tool eliminates the disadvantages of libabigail and ABI-compliance by combining ELF and DWARF information. A comparative analysis of the tools' performance is given in the Table 1. Time-consuming criteria for these algorithms are important because it has direct influence to whole development cycle duration.

Table 1. Comparative analysis of libraries performance

new approach, s libabigail, s ABI-compliance, s

boost 0.361 0.588 0.948

libcds 0.071 0.006 0.005

LLVM 0.592 0.845 10.892

libstdc++ 0.080 0.140 0.116

As shown in the table above the new implementation is almost twice as fast for popular libraries as boost, LLVM, libctdc++, but it is considerably slower when applied to libcds

library. This is explained by higher overhead caused by preparation of data structures for DWARF information. Given the low number of virtual method tables in the libcds library the speed up does not justify the preparation overhead. The performance improvement for large libraries is significant.

CONCLUSION

During the work, a library was developed to verify the compatibility of the virtual method tables, which is faster than the considered analogues. The speed up in analysis was achieved by processing executable files in RAM, the use of caching methods and improvements to the hash table. The developed tool allows to extract full information about tables of virtual methods using both ELF and DWARF information or ELF data in DWARF is not available. This functionality is unique to the tool developed and sets it apart from its analogues.

REFERENCES

[1] KDE TechBase. Policies/Binary Compatibility Issues With C++. http://techbase.kde.org/Policies/Binary-Compatibility-Issues-With-C++. Link checked on 14.05.2019.

[2] Margaret A. Ellis and Bjarne Stroustrup: The Annotated C++ Reference Manual. Addison-Wesley. Reading, Mass. 1990

[3] Exploring the DWARF debug format information, https://developer.ibm.com/articles/au-dwarf-debue-format/. link checked on 14.05.2019

[4] The ABI Generic Analysis and Instrumentation Library. https://sourceware.org/libabigail/. Link checked on 14.05.2019

[5] A. Ponomarenko and V. Rubanov Backward Compatibility of Software Interfaces: Steps towards Automatic Verification, 2011

[6] System V Application Binary Interface, Third Edition, Intel386 Architecture Processor Supplement ISBN 0-13-104670-5 UNIX Press, PTR Prentice Hall, 113 Sylvan Avenue, Englewood Cliffs, NJ 07632.

[7] Drepper, LI., How to Write Shared Libraries. December 2010. http://www.akkadia.org/drepper/dsohowto.pdf. Link checked on 14.05.2019.

RETARGETABLE COMPILER DESIGN ISSUES

Iurii Korenkov1, Ivan Loginov1, Oleg Doronin1, Daniil Sadyrin1 Assoc. Prof. Andrey Dergachev1

1ITMO University, Russia

ABSTRACT

Today, much attention is paid to the research and development of application-specific instruction set processors (ASIPs). The architecture of such processors is focused on their application and the command systems differ from each other, therefore each architecture requires its own set of developer tools like a compiler, debugger, linker, etc. The program code optimization for each ASIP also has its own specifics. At the same time, compiler development should be as fast and technologically advanced as possible in order to minimize the application delivery time (time-to-market), and make the compiled program code as reliable as possible.

In this work, a comparative analysis of approaches to the retargetable compiler design is performed. The analysis of languages for the description of target platforms, which are used for automatic developer tools generation, is performed. A data-driven approach to the development of compilers, which minimizes the costs of providing support for a set of target architectures, is proposed. The possibility of using this approach for a co-design compiler and an ASIP processor or an embedded system has been substantiated.

Keywords: retargetable compiler, compiler design, application-specific instruction set processor, embedded systems, machine description language

INTRODUCTION

Nowadays software developers are faced with an increasing variety of processors' architectures used in computing systems. This is especially true for embedded systems: in this area, an increasing amount of software is used [1]. Also, increases the usage of application-specific instruction set processors (ASIPs). Initially (at the development stage, after its completion) there are no high-level programming languages' compilers for such processors. In the best case, the assembler is available to the developer, but it doesn't allow rapid software development. At the same time, it is necessary to ensure a minimum time-to-market window.

There are many compilers for a wide range of programming languages, but it is not always possible to adapt them to a target platform that isn't initially supported. This is connected with the design of compilers. Retargeting often isn't a key requirement to a compiler, like in the case with GCC [2], but after some time this feature becomes necessary (development could be initiated, e.g., by the community). In the case of embedded systems, usage of a general-purpose compiler is usually impossible (by the inefficiency reason) and development of a platform-specific compiler is expensive. A possible way to reach the trade-off between the high cost of the compiler development process and highlevel language support for new hardware architectures is to design of an easily-

customizable compiler or retargetable compiler. Customization of compilers is an ability to create multiple backends [3] (one backend - one target platform). This design model leads developers to deep understanding of both the compiler internals and the target architecture. Retargetable compiler model consists of only one backend, but it must be configurable (retargetable). To ensure the possibility of retargeting, special architecture description languages (ADL) are usually used. Architecture descriptions are used by the compiler as a «configuration» for the code generator. The efficiency of the code that the compiler will generate depends on the capabilities of ADL.

Creating a retargetable compiler and implementing support of multiple target platforms may take less time than the total time to development of particular target-specific compilers. Reducing compiler development time, in turn, reduces software delivery time to the end-user.

Retargetable compiler development is a good opportunity to improve the design space exploration (DSE) process. Hardware and software co-design approach now are a widely used in ASIP development area. It means that compiler take one of the key places in this process [4]: after each change of hardware compiler will be configured by new architecture-description which makes it possible to compile software again, on each design space exploration cycle, like it is shown on Figure 1.

Figure 1. Possible design space exploration cycle.

In another case, retargeting compiler by-hands (e.g., implementing compiler's back-end) requires more time and makes the DSE process slower. Also, a retargetable compiler could be used as a base for further work to create well-optimizing platform-specific compiler if it will provide possibilities to tune its internals.

COMPILER DESIGN MODELS

The field of compiler engineering is well established - there are accepted approaches to the development of both compilers as a whole and their individual components. The

choice of a certain approach (or their combinations) to the design of the compiler is an important aspect from the point of view of its further development and use. Depending on the approach chosen, you can get a compiler that is absolutely unsuitable for retargeting, and a very flexible tool that both developers and users can customize.

The classical approach (Figure 2) to the design of compilers assumes the presence of components for analyzing the text of a program in the source language (front-end), manipulating the intermediate representation (middle-end), and also for performing code generation (back-end) [5].

Figure 2. Classical compiler design model.

This approach isn't good for development of cross-compilers and, particularly, retargetable compilers, but successfully applied in proprietary compilers. Such compilers usually support one source language and some similar target architectures (e.g., Intel Fortran Compiler supports x86, x86-64, IA-32). These compilers make possible to generate well-optimized code, but don't give any possibility to extend the range of target platforms for code generation. Some compilers, e.g., GCC demonstrate the evolution of this approach (Figure 3). GCC developer can create a machine-description file in RTL (register transfer languages, some kind of ADL), write a big amount of platform-specific code (e.g., with optimizations implemented), and rebuild the entire compiler. It requires a lot of time to understanding specifics of GCC's implementation, rebuilding and debugging. In the rapid software development world, it isn't a good applicable approach.

Figure 3. GCC design model.

The other design model looks like "many-to-many" relationship: there are many frontends (M), backends (N) and the middle-end which handles intermediate representation (IR) of a program in generic form. As a result, it gives support of M * N combination of source languages and target platforms. One of the first examples of implementation of this model is the UNCOL project [6]. Nowadays this approach is used in the LLVM project: it provides agile features to implement custom back-ends, including, to support processors for embedded systems [7]. LLVM provides more clear design and it has lower entrance level for the developer than in the case with GCC. This approach has some limitations: developer requires to rebuild toolchain, use an only default programming language (as a rule, C++), the restricted scope of supported architectures.

Difference between architecture families - one of the key issues in retargetable compiler development. Implementation of back-end components (register allocator, code selector, instruction scheduler) for one architecture family (e.g., RISC, CISC, VLIW) makes it impossible to generate efficient code that targets platform from the other family. This experience and negative results were shown by DSPProject [8].

There are a lot of retargetable compilers projects exists: MSSQ, COACH, CHESS, Aviv, Marion, IMPACT, PROPAN, RECORD, etc., which are listed in work [3]. These compilers based on architecture description languages. Features and restrictions of this compilers are driven by features and restrictions of used ADLs.

ARCHITECTURE DESCRIPTION LANGUAGES

Quality of the retargetable compiler depends on expressive possibilities, supported by architecture description language. In general case, there are three categories of ADLs: instruction-set centric, architecture-centric and mixed [9]. Languages in each category focused on specific aspects connected with architecture. For example, RASSP, MIMOLA [3] are architecture-centric languages and provides the functionality to describe microarchitecture aspects. These languages are well to use in electronic design automation, e.g., for generating of simulators (functional, register-transfer-level), hardware synthesis.

The other class of languages is an instruction-set centric. These languages (e.g., ISDL [3], CSDL) focused only on instruction set architecture and don't touch microarchitecture level, particularly does not provide enough functionality to describe low-level details, which are important for simulator generation and platform-specific code generation, like a pipeline. On the other hand, they are high-level enough to quickly describe the instruction set and get a working compiler for this platform that can be improved manually.

A hybrid approach seems to be promising - the use of languages, that allow describing both the instruction set architecture and aspects related to the micro-architecture. An example of a hybrid language is Maril [3]. Description in this language consists of sections: resource declaration, instruction set description, runtime model. So, this language allows us to describe pipeline stages, cost, latency delays. It is focused strictly on RISC-processors [9]. Other hybrid solutions are LISA, EXPRESSION, IDL, MADL [10] (it supports scalar, superscalar, and VLIW processors. MADL is one of the most well-balanced solutions in this category of languages.

A lot of architecture descriptions languages were created. Some of them are good for compiler generation, some - for electronic design automation. Most of them are used to create retargeted compilers for embedded systems, many developments are used only as part of specific compilers that are not currently supported. There are popular solutions in the community of developers, such as RTL, which are used in many compilers. Many ADLs are characterized by the restriction to certain families of processor architectures, which makes it impossible to widely use compilers based on them. Lack of support in the community of developers negatively affects the quality of such compilers. Also, many ADLs do not allow to take into account specific aspects of the microarchitecture, which makes it impossible to implement effective code optimizers. On the other hand, conventional solutions, such as GCC, LLVM, are not adapted (or are difficult to adapt) for application in the field of embedded systems. This state of affairs in this area is the motivation to improve the ADL presented in [11] and create an approach that would allow

to use existing developments in this area, as well as make this solution popular in the developer community.

PROPOSED RETARGETING APPROACH

Retargetable compilers, according to Leupers [1], can be defined as parameterized compiler, user-retargetable, developer-retargetable. Each of them has its own advantages and disadvantages. For example, parameterized retargeting can work quite simply - it is enough to pass the number of registers used as an argument to the command line. Of course, in the implementation of this approach is also simple, and in terms of supporting multiple target platforms, it is useless. On the other hand, developer-retargetable compilers offer maximum retargeting capabilities, but they are difficult to use and require highly skilled developers. Schematically, the complexity and aspects of retargeting are shown in Figure 4.

bit depth Pipeline

(other constant ISA structure Memory model

parameters) Register model

Easy to implement Hard to implement

Poor retargetability Rich retargetability

Figure 4. Compiler retargetability levels.

It can be seen that increasing the flexibility (functional, as well as in terms of the set of supported architectures) leads to the complication of both the implementation of the means for providing retargeting (in this case, ADL) and the compiler, which will work with it.

It is a good approach to retain advantages of user-retargetability (low entrance level, high development speed) and add support of different architecture families. At this moment, developed ADL supports such resource aspects of target architectures as: memory and register models, instruction set architecture descriptions (including mnemonics). Each aspect description is located in a particular section. Each section is optional, it is possible to handle register overlap scenarios by creating views for memory and registers (mapping to physical storages). It is possible to describe operations in more complex way, than single expression (like in Maril), use C-like syntax. It is Also possible to define variables, set cycles with post- and preconditions, branching, blocks. The classical operators are allowed: binary arithmetic, logical, bitwise, comparisons, as well as unary (increment, decrement, inversion) operators. Literals could be written in an intuitive way - binary ones: ObOOOlOlOlOl, decimal ones: just numbers, hexadecimal numbers: 0x0123456789ABCDefd. There is a special construction «when» for when it is necessary to give different interpretations to instructions with matching, mutually alternative opcodes (a shorter version than using the if statement). In an intuitive style, mnemonics are also described.

But ADL alone is not enough to create a flexible retargetable compiler. The infrastructure that defines the different usage scenarios is important. Below are the key features of using the language and working with descriptions on it (list 1).

• Flexible use of architecture description aspects:

o use of default implementations of particular architecture description aspects;

o the ability to override existing aspects, as well as access to their source code, if necessary;

o optional use of aspects of the description of the target platform;

o extensibility of language by metaprogramming features*.

• Integration with development environments:

o support of Visual Studio; o syntax highlighting for Sublime editor.

• Translation from/to other ADLs*:

o creating a semantic model for manipulations from various programming languages.

• Presence of pre-defined templates, aspect implementation for architecture families (CISC, RISC, VLIW)*.

• Storing information about intermediate representations (or the representation themselves) at all stages of code transformation by the compiler*.

* - planned or work-in-progress features.

The important point is the optional use of aspects, as well as the presence of default implementations, or implementation templates. Creating a model for these templates allows developers to use them from a single back-end component. Thus, the creation of a template description of the use of the computing pipeline for the x86-64 architecture will allow it to be used in the descriptions of similar architectures. If necessary, this description can be partially redefined or replaced entirely.

The definition of a language based on the parsing-expression grammar (PEG) makes it relatively simple to translate it, which makes it possible to get the support of the missing features with a minimum of effort.

A great perspective of using this language as part of compilers is the idea of translation between other ADLs. Thus, the creation of a translator from the RTL language (together with the analysis of C code) will provide support for all the architectures that already exist in GCC and other compilers using RTL.

The difficulty is the creation of a model of optimization descriptions, but this will allow developers to create a library of ready-to-use optimization methods, which will significantly reduce the time to implement support for target architectures. In the future, this approach will eliminate the need to develop specific code selectors, instruction schedulers.

Further work will also be concentrated on research of different atomic aspects of architecture specifics. For example, in some cases it is required to specify pipeline stages that can be used for a particular operation, data paths between pipeline stages in general case. Big work is related to creating of constraints description agile model.

CONCLUSION

This article presents various aspects related to the design of retargetable compilers. In many ways, they boil down to the task of developing an ADL with an adequate level of abstraction, as well as the corresponding components that make up the back-end. An infrastructure is proposed for description manipulation (API, for example, for use in already existing compilers), as well as approaches to its use. In the future, this work will create a family of descriptions of architectures that are partially derived automatically, and simplify the process of creating retargetable compilers.

REFERENCES

[1] Leupers, Rainer, and Peter Marwedel. Retargetable compiler technology for embedded systems: tools and applications. Springer Science & Business Media, 2001.

[2] GCC, the GNU Compiler Collection website, Web: https://gcc.gnu.Org/onlinedocs/gcc-3.0.3/gcc_15.html, Link checked on 14.05.2019.

[3] Qin, Wei, and Sharad Malik. "Architecture Description Languages for Retargetable Compilation." (2002): 535-564.

[4] Leupers, Rainer. "Compiler design issues for embedded processors." IEEE Design & Test of Computers 19.4(2002): 51-58.

[5] Cooper, Keith, and Linda Torczon. Engineering a compiler. Elsevier, 2011.

[6] Conway, Melvin E. "Proposal for an UNCOL." Communications of the ACM 1.10 (1958): 5-8.

[7] Husar, Adam, et al. "Automatic C compiler generation from architecture description language ISAC." Sixth Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'10)—Selected Papers. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2011.

[8] V. Zivojnovic etal. 1994. DSPstone: A DSP-oriented benchmarking methodology. In Proc. of ICSPAT, Vol. 94.

[9] Hohenauer, Manuel, and Rainer Leupers. C Compilers for ASIPs. Springer, 2010.

[10] Qin, Wei, Subramanian Rajagopalan, and Sharad Malik. "A formal concurrency model based architecture description language for synthesis of software development tools." ACM SIGPLAN Notices. Vol. 39. No. 7. ACM, 2004.

[11] Korenkov, I., Loginov, I., Dergachev, A., & Lazdin, A. (2018). DECLARATIVE TARGET ARCHITECTURE DEFINITION FOR DATA-DRIVEN DEVELOPMENT TOOLCHAIN. International Multidisciplinary Scientific GeoConference: SGEM: Surveying Geology & mining Ecology Management, 18, 271-278.