Phoenix

Введение в компиляцию

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

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

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

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

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

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

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

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

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

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

Основы Phoenix

Phoenix - это инфраструктура для разработки компиляторов, средств анализа кода, его оптимизации и тестирования.

Phoenix предоставляет множество строительных блоков, реализованных на основе промежуточного представления - Common Intermediate Representation (CIR), для создания перечисленных инструментальных средств. Phoenix может быть использован в задачах генерации кода для различных архитектур процессоров.

Промежуточное представление (Intermediate Representation - IR)

IR представляет собой строго типизированное линейное представление потока инструкций. IR представляет функции на нескольких уровнях абстракции: от высокого машинно-независимого (HIR) до низкого машинно-зависимого (LIR).

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

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

IR строго типизировано. Тип результата определяется операндом и типами входных операндов. Инфраструктура Phoenix предоставляет средства для проверки соответствия типов.

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

Код на языках высокого уровня (таких как C++, C# или J#) преобразуется в промежуточное представление при помощи компонент Phoenix. Инструментальные средства на основе Phoenix используют промежуточное представление. Таким образом, они могут обрабатывать код, изначально написанный на разных языках. Например, компоненты анализа, оптимизации или верификации, работающие с IR, могут быть повторно использованы в компиляторах различных языков высокого уровня.

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

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

Фазы компиляции

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

Средство, разрабатываемое на основе Phoenix, создает список фаз. Инфраструктура Phoenix и различные расширения (plug-in) могут изменять этот список.

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

Сборки и модули

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

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

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

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

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

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

Система типов Phoenix служит основой для генерации кода, отслеживания указателей (pointer tracking), высокоуровневой оптимизации и отладки объектного кода. Компиляторы и другие средства, основанные на Phoenix, используют систему типов для проверки соответствия типов в промежуточном представлении кода.

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

Управляемый и неуправляемый режимы компиляции

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

В управляемом режиме исходный код компилируется в сборки .NET Framework, содержащие код на промежуточном языке (Microsoft intermediate language - MSIL). При запуске такой код преобразуется по запросу (on demand) в машинный код и исполняется в рамках общеязыковой исполняющей среды (common language runtime).Преобразование по запросу, как правило, означает, что при первом вызове определенного участка кода (например, метода) этот код преобразуется из MSIL в машинный код, исполняется и кэшируется на случай повторного вызова.

В неуправляемом режиме исходный код компилируется напрямую в машинный код.

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

Компоненты Phoenix

Компоненты преобразования кода

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

Благодаря компонентам преобразования кода происходит отделение машинно-зависимых задач компилятора, типа работы с регистрами. Компоненты преобразования кода используются для преобразования кода в LIR (low-level intermediate representation) и генерации кода. То есть компоненты делают машинно-зависимую функциональность компиляторов повторно используемой.

Для преобразований между различными архитектурами аппаратного обеспечения или различными промежуточными представлениями кода используется специальный язык. Язык носит название Grand Unified Retargeting Language (GURL) и предназначен для решения следующих задач:

Компоненты обработки входных и выходных данных

Эти компоненты обрабатывают промежуточный язык компилятора (Compiler Intermediate Language - CIL), PE-файлы (Microsoft Portable Executable), COFF-файлы (Microsoft Common Object File Format), файлы с кодом на промежуточном языке MSIL (Microsoft Intermediate Language), сборки и т. д.

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

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

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

Инфраструктура потоков данных

Phoenix предоставляет инфраструктуру для анализа потоков данных и выполнения преобразований. Инфраструктура поддерживает прямой и обратный проходы для итеративного и неитеративного анализа.

Сборщик мусора (Garbage Collector - GC)

Инфраструктура Phoenix предоставляет общую среду для поддержки сбора мусора во время исполнения. Инфраструктура поддерживает:

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

Графы

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

Коллекции

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

Все структуры данных из пространства Collections поддерживают операции New(), Delete(), Insert(), Remove(), Iterate(), Count(), Push\Pop. Операция New создает коллекцию. Операция Delete удаляет коллекцию. Операция Insert добавляет элемент в коллекцию. Операция Remove удаляет элемент из коллекции. Операция Iterate позволяет переходить от одного элемента коллекции к следующему. Операция Count подсчитывает число элементов в коллекции. Операция Push добавляет элемент в начало или конец коллекции, а операция Pop выбирает элемент. При этом операция Push запрашивает новую память под коллекцию большего размера, копирует все элементы старой коллекции в новую область памяти и дописывает к ним новый элемент. Аналогично Pop удаляет элемент.

Использование псевдонимов (Aliasing)

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

Lifetime (время жизни)

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

Обработка исключений

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

Расширения (plug-in)

Под plug-in в Phoenix понимается программный модуль, написанный пользователем инструментального средства. К примеру, на основе Phoenix было разработано инструментальное средство для компиляции, после чего пользователь этого средства решил расширить его функциональность и создал plug-in. Plug-in исполняется компилятором на основе Phoenix.

При этом расширяющий модуль имеет полный доступ к внутренним структурам данных компилятора.

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

Итоги

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

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