научная статья по теме КОМПОНЕНТНЫЙ ПОДХОД К ПОСТРОЕНИЮ ОПТИМИЗИРУЮЩИХ КОМПИЛЯТОРОВ Математика

Текст научной статьи на тему «КОМПОНЕНТНЫЙ ПОДХОД К ПОСТРОЕНИЮ ОПТИМИЗИРУЮЩИХ КОМПИЛЯТОРОВ»

ПРОГРАММИРОВАНИЕ, 2009, No 5, с. 70-80

- КОМПИЛЯТОРЫ И СИСТЕМЫ ПРОГРАММИРОВАНИЯ =

УДК 004.92+004.94

КОМПОНЕНТНЫЙ ПОДХОД К ПОСТРОЕНИЮ ОПТИМИЗИРУЮЩИХ КОМПИЛЯТОРОВ

© 2009 г. А. Ю. Дроздов

ИТМиВТ им. С.А. Лебедева РАН 119991 Москва, Ленинский просп., 51 E-mail: ajudrozdov@ipmce.ru Поступила в редакцию 10.11.2008 г.

ВВЕДЕНИЕ

Современное состояние индустрии ИТ характеризуется огромным разнообразием вычислительных систем. Основным инструментом, позволяющим эффективно использовать аппаратные возможности вычислительных систем, является оптимизирующий компилятор. Основная задача оптимизирующего компилятора - получение кода, максимально эффективного для данного вычислительного комплекса. Современный оптимизирующий компилятор представляет собой программный инструмент, с помощью которого можно откомпилировать программу, написанную на некотором входном языке программирования (С, С++, Fortran и. т. д.) или представленную в машинных кодах (x86, SPARC и т.д.) в требуемый выходной язык или машинный код. В процессе компиляции программа последовательно трансформируется в промежуточные представления, используемые для сохранения семантики программы. На интерфейсах промежуточных представлений реализуются алгоритмы анализа и оптимизаций.

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

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

Другим критическим параметром создания оптимизирующих систем является время их разработки для вновь создаваемых платформ. Разработка каждого отдельного решения требует временных затрат в пределах десятков лет и значительных затрат по сопровождению этих решений (примеры: оптимизирующие компиляторы компаний Intel, Sun Microsystems, Transmeta, Microsoft, IBM, HP, Elbrus, ...). Все эти компании имеют свои собственные коммерческие продукты - компиляторы, которые создавались на протяжении десятилетий, содержат миллионы строк исходного кода, и в которые разработчики, сопровождающие эти программы, не способны оперативно встраивать поддержку новых аппаратных решений и требований пользователей. И это не вопрос компетентности разработчиков, осуществляющих поддержку продукта: за десятилетия истории развития конкретного продукта исходный код разрастается неимоверно, а команда разработчиков, как правило, обновляется не один раз. И тех, кто способен свободно ориентироваться в проекте в несколько миллионов строк, просто не остается.

Рис. 1. Общая идея использования УБТ в готовой системе трансляции.

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

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

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

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

1. КОМПОНЕНТНАЯ ТЕХНОЛОГИЯ ОПТИМИЗИРУЮЩЕЙ КОМПИЛЯЦИИ

1.1. Понятие Универсальной библиотеки трансляции (УБТ)

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

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

Рис. 2. Представление операции.

УБТ структурно разделяется на две части - аналитическую и базу данных программы (БДП). Аналитическая часть является основой библиотеки, в ней абстрагированы от конкретных платформ и языков и реализованы алгоритмы анализа и оптимизации на основе собственного языка промежуточного представления. База данных программы содержит описание ресурсов целевой архитектуры, свой язык описания семантики программы, а также высокоуровневую информацию - символьные таблицы, типы, размерности и т.д. - словом, все, что существует в языках высокого уровня. Эти две части взаимодействуют через четко определенные интерфейсы, которые обозначены нами как интерфейсы доступа к семантике программы. Объявляются эти интерфейсы в аналитической части, а определяются - в базе данных программы.

Язык описания семантики программы, составляющий часть БДП, может быть настроен на разные целевые платформы, включая "виртуальные" (как, например, С1МРЬЕ в gcc). Кроме собственно языка, БДП содержит способы его сохранения и восстановления.

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

1.2. Семантическое представление

Любое промежуточное представление, используемое в компиляторах, в первую очередь сохраняет семантику исходной программы. Под семантикой программы понимается ее алгоритмическая сущность. С точки зрения фрагментации, программы, написанные на наиболее распространенных языках программирования (С, С++, Fortran и т.д.), организованы в модули и процедуры. Модуль соответствует файловой организации программы. В виде процедур оформляются фрагменты программы внутри модулей. Структуры данных программы представляются объектами с фиксированными или динамически задаваемыми размерами и описанием их внутренней структуры с помощью типов. Наиболее общим способом сохранения алгоритмической составляющей программы в компиляторах является операционное представление (рис. 2).

Операционное представление является списком операций. У операции могут существовать входной контекст и выходной контекст. Входной и выходной контексты задаются списками аргументов и результатов. Аргументы могут быть литералами, объектами или ссылками на другие операции. В последнем случае, когда аргументом операции является ссылка на другую операцию, вернее на результат, ею вырабатываемый, можно поступить следующим образом: ввести новый вспомогательный объект, в который помещать указанный результат, а ссылку на операцию заменить на использование веденного объекта. Таким образом, можно сказать, что отображение связи между результатом одной операции и аргументом другой через объекты является более общим, чем представление этой связи в виде ссылки на операцию. Сама операция представляет собой набор атрибутов, определяющих семантическое действие над входным контекстом для получения выходного контекста. К такому операционному представлению может быть сведено практически любое известное промежуточное представление, начиная с синтаксических деревьев фронтендов (gcc, edg), заканчивая представлениями, наиболее приближенными к ассемблерам целевых архитектур.

Рис. 3. Аналитическая операция.

1.3. Аналитическое представление

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

Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.

Показать целиком