РЕАЛИЗАЦИЯ ГЕНЕРАТОРА ПРОМЕЖУТОЧНОГО ПРЕДСТАВЛЕНИЯ SSA ИЗ ПОЛИЭДРАЛЬНОЙ МОДЕЛИ В КОЛЛЕКЦИИ КОМПИЛЯТОРОВ GNU

Глава 1. Полиэдральная модель 8
Области итерирования 11
Аффинные планы 13
Функции доступа к памяти 15
Объедиение трансформаций 17
Зависимости данных 21
Зависимости данных и полиэдральная модель 23
Дальнейшее развитие полиэдральной модели 24
Заключение 24
Глава 2. Коллекция компиляторов GNU и фреймворк Graphite 25
Выделение SCoPs 32
Построение полиэдрального представления 36
Применение анализа зависимостей и трансформаций 37
Анализ псевдонимов 39
Восстановление кода gimple 40
Дальнейшее развитие фреймворка Graphite 40
Заключение 41
Глава 3. Реализация генератора промежуточного представления SSA из полиэдральной модели в коллекции компиляторов GNU 42
CLooG 42
Определяемые структуры данных 43
Генерация абстрактного синтаксического дерева 43
Представление абстрактного синтаксического дерева 44
Т8Ь 50
Представление целочисленных множеств и отношений между ними ..51
Генерация абстрактного синтаксического дерева 52
Генератор на основе библиотеки СЬооС 56
Генератор на основе библиотеки 18Г 62
Анализ зависимостей по данным 69
Сравнение генераторов промежуточного представления ЗЗЛ на основе
библиотек 18Г и СЬооС 73
Заключение 74
Заключение 75
Список использованных источников 76
Купить

Реферат
Гареев Р.А. РЕАЛИЗАЦИЯ ГЕНЕРАТОРА ПРОМЕЖУТОЧНОГО ПРЕДСТАВЛЕНИЯ SSA ИЗ ПОЛИЭДРАЛЬНОЙ МОДЕЛИ В КОЛЛЕКЦИИ КОМПИЛЯТОРОВ GNU,
дипломная работа: стр.78, рис. 10, табл. 2, ,библ. 29 назв.
Ключевые слова: ПОЛИЭДРАЛЬНАЯ МОДЕЛЬ, КОЛЛЕКЦИЯ КОМПИЛЯТОРОВ GNU, GRAPHITE, ISL, CLOOG.
Объект исследования - генерация промежуточного представления из полиэдарльной модели в коллекции компиляторов GNU .
Цель работы - создание генератора промежуточного представления SSA из полиэдральной модели полностью независимого от библиотеки CLooG.
В процессе работы анализировалась возможность генерации абстрактных синтаксических деревьев в библиотеках CLooG и ISL; производилось сравнение генераторов на основе библиотек CLooG и ISL.
Все улучшения, связанные с фреймворком Graphite, нашли широкое применение на практике, в силу того, что коллекция компиляторов GNU является лидером по количеству процессоров и операционных систем, которые она поддерживает.
В силу своих преимуществ, соответствия всем стандартам принятым в коллекции и отсутствия регрессии при тестировании с использованием наборов тестов, предоставляемых коллекцией компиляторов GNU и инфраструктурой для компиляции llvm, генератор, реализованный в рамках данной работы, был принят сообществом коллекции компиляторов GNU в качестве основного. Возможность использования версии, работа которой основана на библиотеке CLooG, была полностью исключена.
Языки программирования представляют собой средство описания вычислений для людей и машин. Современное общество зависит от языков программирования, поскольку все программное обеспечение на всех компьютерах мира написано на том или ином языке программирования. Однако прежде чем запустить программу, её необходимо преобразовать в форму, которая может выполняться на компьютере. Иногда эта трансляция происходит перед запуском программы и в этом случае называется компиляцией.
Существует множество компиляторов для одного и того же языка программирования. Иногда компиляторы объединяются в коллекции, распространяемые как платно, так и бесплатно. Примером коллекции компиляторов, распространяемых по лицензии свободного программного обеспечения, служит коллекция компиляторов от GNU [1], разрабатываемая около 28 лет, содержащая более 7 миллионов строк программного кода и используемая как стандартный компилятор для свободных UNIX-подобных операционных систем.
Несмотря на то, что по определению компилятор — это программа, которая считывает текст программы, написанной на одном языке — исходном, и транслирует его в эквивалентный текст на другом языке — целевом [2, с. 29], одна из важных ролей компилятора состоит в оптимизации кода, т.е. попытке компилятора получить код, более эффективный, чем обычно [2, с. 39]. Можно выделить различные виды оптимизаций: машинно-независимые и машинно-зависимые, оптимизации циклов, локальные, внутрипроцедурные, межпроцедурные, внутримодульные, глобальные и т.д. Для некоторых из них используются точные математические основы, с помощью которых можно убедиться в корректности оптимизации и получить желаемый эффект для всех возможных входных данных.
Полиэдральная модель — математический фреймворк, специализированный на оптимизации процесса выполнения циклов и взаимодействия с массивами.
Первые её применения можно встретить в работах [3, 4]. Предложенные в них идеи, такие как, например, представление множества значений индуктивных переменных цикла через полиэдр, послужили основой для создания моделей, предоставляющих новые возможности для практического использования. Таким примером служит полиэдральная модель, описанная в [5]. Кроме области итерирования, представляющей, в частности, множество значений индуктивных переменных цикла, в ней определяются функции доступа, описывающие взаимодействие с памятью, а также аффинные планы, применяющиеся для опис ания порядка выполнения итераций и инструкций. Классические оптимизации, такие как, слияние циклов (англ. loop fusion) и разбиение цикла на блоки (англ. loop tiling), могут образовывать произвольную по следовательно сть трансформаций, которую можно произвести с этой моделью без необходимости генерации программного кода для отдельной трансформации. В рамках этой модели можно проверить присутствие зависимостей данных в циклах и опр еделить, подходят ли они для распараллеливания в случае отсутствия таких зависимостей.
С целью практического использования полиэдральной модели разрабатывались различные фреймоворки и библиотеки, поддерживающие работу с ней. Например, Graphite [6] — фреймворк, применяющийся для полиэдрального анализа и трансформаций, выполняющийся среди прочих проходов оптимизации над формой SSA в коллекции компиляторов GNU.
До 2014 года библиотека CLooG [7], специализированная на генерации кода из поэлидарльной модели, была основным компонентом фреймворка Graphite и использовала библиотеку ISL [8] в качестве бэкенда. В отличие от библиотеки CLooG библиотека ISL позволяет выполнять различные операции с целочисленными множествами и отношениями между ними. Со временем в библиотеке ISL появилась поддержка собственной генерации абстрактного синтаксического дерева.
В данной работе рассматривается устройство и принципы работы генератора промежуточного представления фреймворка Graphite с целью возможной оптимизации скорости работы этого фреймворка и устранения избыточной зависимости от библиотеки CLooG. Таким образом, были поставлены следующие задачи:
• Исследование полиэдральной модели, принципов работы и устройства коллекции компиляторов GNU и, в частности, фреймворка Graphite.
• Создание генератора промежуточного представления SSA из полиэдральной модели в коллекции компиляторов GNU на основе библиотеки ISL.
• Сравнение генераторов промежуточного представления SSA из полиэдральной модели в коллекции компиляторов GNU на основе библиотек ISL и CLooG.
Цель исследования: опровергнуть или подтвердить оптимальность по времени выполнения и времени компиляции программного кода используемых сейчас средств генерации абстрактного синтаксического дерева из полиэдральной модели в коллекции компиляторов GNU.

Купить