Данная статья, первая часть статей перевода данного документа – The Design of a Custom 32-bit RISC CPU and LLVM Compiler Backend. Автор этого документа Connor Jan Goldberg. Следить за статьями и добавлять свои тезисы можно по этой ссылке (академическое сообщество). Данный документ описан частично, документ отвечает требованиям для защиты магистерской диссертации в области электротехнических наук (США). Выбор пал случайно в поисках информации по конструированию собственных архитектор процессоров и написанию для них компиляторов.
Автор посвящает эту работу его семье и друзьям, для всех бесконечно любящих, поддерживающих и одобряющих на всем протяжении его работу в Технологическом институте Рочестер.
Краткий обзор.
Инфраструктуры компиляторов часто представляют собой область, представляющую большой интерес для исследований. По мере необходимости для цифровой информации и технологий, увеличивается потребность в увеличении производительность цифрового оборудования. Основным компонентом в большинстве сложных цифровых систем является центральный процессор (ЦП или ЦПУ – центральное процессорное устройство). Компиляторы несут ответственность за трансляцию кода, написанного на языке программирования высокого уровня до последовательности инструкций, которые затем выполняются процессором. Большинство исследований в области технологий компилятора сосредоточено на разработке и оптимизации кода, написанного программистом; однако в какой-то момент этого процесса код должен быть преобразован в инструкции (машинный код), относящиеся к CPU. В настоящем документе описывается дизайн упрощенной архитектуры процессора, а также менее понятная сторона компиляторов: бэкэнд, который отвечает за генерацию команд процессора. Конструкция ЦПУ представлена 32-разрядным процессором с сокращенным набором команд (RISC) и ЦПУ написан на Verilog. В отличие от большинства встроенных (распространенных) архитектур RISC, которые имеют порт компилятора для GCC (сборник компиляторов GNU), этот компилятор был создан для инфраструктуры компилятора LLVM проекта. Код, сгенерированный из бэкэнда LLVM, успешно моделируется на пользовательском ЦПУ с Cadence Incisive, и процессор синтезируется с использованием Synopsys Design Compiler.
Декларация
Настоящим автор заявляет, что, кроме случаев, когда конкретная ссылка дается на другие работы, полное содержание этой статьи является оригинальным и не представлено полностью или частично на рассмотрение любой другой степени или квалификации в этом или любом другом Университете (текст является исключительно уникальным). Эта диссертация – результат собственной работы автора и не содержит ничего, что является результатом работы сделанной в сотрудничестве, за исключением случаев, специально указанных в тексте (очень интересный момент описания работы, т.к. я лично не встречал на постсоветском пространстве таких слов в магистерских работах).
Connor Jan Goldberg
Август 2017
Благодарность
Автор хотел бы поблагодарить своего консультанта, профессора и наставника Mark A. Indovina за все его руководство и обратную связь на протяжении всего этого проекта. Он является причиной любви автора к цифровому дизайну оборудования и заставлял автора настроится на карьерный путь. Он оказал огромную помощь и являлся истинным друг во время моей карьеры в RIT.
Еще одним профессором, которого я (автор) хотел бы поблагодарить, является доктор Dorin Patru. Он привел мне наслаждение в изучении компьютерной архитектурой и всегда предоставлял полезные знания и отзывы для моих случайных вопросов.
Кроме того, я (автор) хочу поблагодарить Tight Squad за настоящую дружбу, бесконечную смех и отличную компанию на протяжении многих, долгих ночей, проведенных в лабораториях. Я также хотел бы поблагодарить моих лучших друзей, Линкольна и Мэтта. Этот проект не был бы возможным без их любви, совета и общения на протяжении всей моей карьеры в RIT.
Наконец, мне нужно поблагодарить моих удивительных родителей и брата. Моя семья давала вдохновение для всего, к чему я стремился, и мой успех был бы ничем, если бы не их мотивация, поддержка и любовь.
Вперед
В документе описывается пользовательский RISC-процессор и связанный с ним LLVM-компилятор. Исследовательский проект, разработанный Коннором Голдбергом. Близкий цикл между новой архитектурой процессора и компаньон-компилятором – не маленький подвиг; Г-н Гольдберг принял задачу с образцовым результатам. Без сомнения, я чрезвычайно горжусь исследовательской работой, подготовленную этим прекрасным учеником.
Mark A. Indovina
Rochester, Нью-Йорк США
Август 2017
Содержание
Краткий обзор ii
Декларация iii
Благодарность iv
Вперед v
Содержание vi
Список рисунков ix
Список объявлений x
Список таблиц xi
1 Введение 1
1.1 Организация. , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , 2
2 Проектирование процессоров и компиляторов 3
2.1. Проектирование ЦП. , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , 3
2.2. Конструкция компилятора. , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , 5
2.2.1 Бинарный интерфейс приложения. , , , , , , , , , , , , , , , , , , , , , 5
2.2.2 Модели компилятора. , , , , , , , , , , , , , , , , , , , , , , , , , , , 6
2.2.3 GCC. , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , 7
2.2.4 LLVM. , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , 8
2.2.4.1 Фронтэнд. , , , , , , , , , , , , , , , , , , , , , , , , , , 8
2.2.4.2 Оптимизация. , , , , , , , , , , , , , , , , , , , , , , , , 9
2.2.4.3 Бэкэнд. , , , , , , , , , , , , , , , , , , , , , , , , , , , 9
3 Пользовательский дизайн CPU RISC 11
3.1. Архитектура набора инструкций. , , , , , , , , , , , , , , , , , , , , , , , , , 11
3.1.1 Файл регистра. , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , 12
3.1.2 Конструкция стека. , , , , , , , , , , , , , , , , , , , , , , , , , , , , , 13
3.1.3 Архитектура памяти. , , , , , , , , , , , , , , , , , , , , , , , , , 14
3.2. Реализация аппаратного обеспечения. , , , , , , , , , , , , , , , , , , , , , , , , , , 15
3.2.1 Проектирование конвейера. , , , , , , , , , , , , , , , , , , , , , , , , , , , , 16
3.2.1.1 Выбор команды. , , , , , , , , , , , , , , , , , , , , , , 16
3.2.1.2 Выбор операндов. , , , , , , , , , , , , , , , , , , , , , , , 17
3.2.1.3 Выполнение. , , , , , , , , , , , , , , , , , , , , , , , , , , , 17
3.2.1.4 Отложенная запись. , , , , , , , , , , , , , , , , , , , , , , , , , 18
3.2.2 Срыв потока. , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , 18
3.2.3 Клоковые фазы. , , , , , , , , , , , , , , , , , , , , , , , , , , , , , 18
3.3 Информация о инструкциях. , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , 18
3.3.1 Загрузка и сохранение. , , , , , , , , , , , , , , , , , , , , , , , , , , , , 19
3.3.2 Передача данных. , , , , , , , , , , , , , , , , , , , , , , , , , , , , , 20
3.3.3 Контроль потока. , , , , , , , , , , , , , , , , , , , , , , , , , , , , , 21
3.3.4 Инструкции по манипулированию. , , , , , , , , , , , , , , , , , , , , , , 22
3.3.4.1 Сдвиг и поворот. , , , , , , , , , , , , , , , , , , , , , , 24
4 Пользовательский дизайн LLVM бэкэнд 26
4.1. Структура и инструменты. , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , 26
4.1.1 Обзор дизайна генератора кода. , , , , , , , , , , , , , , , , , , 27
4.1.2 TableGen. , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , 28
4.1.3. Clang и llc. , , , , , , , , , , , , , , , , , , , , , , , , , , , , , 31
4.2 Внедрение пользовательских целей. , , , , , , , , , , , , , , , , , , , , , , , 31
4.2.1 Описание цели. , , , , , , , , , , , , , , , , , , , , , 33
4.2.1.1 Регистрация информации. , , , , , , , , , , , , , , , , , , , , 33
4.2.1.2. Соглашения о вызовах. , , , , , , , , , , , , , , , , , , , , 34
4.2.1.3 Специальные операнды. , , , , , , , , , , , , , , , , , , , , , , 34
4.2.1.4 Форматы инструкций. , , , , , , , , , , , , , , , , , , , , 35
4.2.1.5 Полные определения инструкций. , , , , , , , , , , , , , 36
4.2.1.6 Дополнительные описания. , , , , , , , , , , , , , , , , , , 40
4.2.2 Выбор команды. , , , , , , , , , , , , , , , , , , , , , , , , , 40
4.2.2.1 Конструкция SelectionDAG. , , , , , , , , , , , , , , , , 41
4.2.2.2 Легализация. , , , , , , , , , , , , , , , , , , , , , , , , , 46
4.2.2.3 Выбор. , , , , , , , , , , , , , , , , , , , , , , , , , , 51
4.2.2.4 Планирование. , , , , , , , , , , , , , , , , , , , , , , , , , 55
4.2.3 Регистрация распределения. , , , , , , , , , , , , , , , , , , , , , , , , , , 55
4.2.4 Кодовая эмиссия. , , , , , , , , , , , , , , , , , , , , , , , , , , , , 57
4.2.4.1 Сборочный принтер. , , , , , , , , , , , , , , , , , , , , , , 57
4.2.4.2. Запись объекта ELF. , , , , , , , , , , , , , , , , , , , , , 58
5 Тесты и результаты 62
5.1 Проверка подлинности LLVM. , , , , , , , , , , , , , , , , , , , , , , , , , , 62
5.2 Реализация ЦП. , , , , , , , , , , , , , , , , , , , , , , , , , , , , , 65
5.2.1 Синтез RTL для предварительного сканирования. , , , , , , , , , , , , , , , , , , , , , , , 66
5.2.2 Синтез DFT после сканирования. , , , , , , , , , , , , , , , , , , , , , , , 66
5.3 Дополнительные инструменты. , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , 67
5.3.1. Clang. , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , 67
5.3.2 ELF в память. , , , , , , , , , , , , , , , , , , , , , , , , , , , , 68
5.3.3 Ассемблер. , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , 68
5.3.4 Дисассемблер. , , , , , , , , , , , , , , , , , , , , , , , , , , , , , 68
6 Выводы 69
6.1. Будущая работа. , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , 69
6.2 Выводы проекта. , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , 70
Ссылки 71
I Руководства I-1
I.1 Построение LLVM-CJG. , , , , , , , , , , , , , , , , , , , , , , , , , , , , , I-1
I.1.1 Загрузка LLVM. , , , , , , , , , , , , , , , , , , , , , , , , , I-1
I.1.2 Импорт исходных файлов CJG. , , , , , , , , , , , , , , , , , , , I-2
I.1.3 Изменение существующих файлов LLVM. , , , , , , , , , , , , , , , , , , , I-2
I.1.4 Импорт Clang. , , , , , , , , , , , , , , , , , , , , , , , , , , , I-5
I.1.5 Построение проекта. , , , , , , , , , , , , , , , , , , , , , , , , , I-8
I.1.6 Использование. , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , I-9
I.1.6.1 Использование llc. , , , , , , , , , , , , , , , , , , , , , , , , , , , I-9
I.1.6.2 Использование Clang. , , , , , , , , , , , , , , , , , , , , , , , , , I-10
I.1.6.3 Использование ELF для памяти. , , , , , , , , , , , , , , , , , , , I-10
I.2. Дерево каталогов LLVM. , , , , , , , , , , , , , , , , , , , , , , , , I-11
II Исходный код II-1
II.1 CJG RISC CPU RTL. , , , , , , , , , , , , , , , , , , , , , , , , , , , , , II-1
II.1.1 Заголовки опкодов. , , , , , , , , , , , , , , , , , , , , , , , , , , , , II-1
II.1.2 Определение заголовков. , , , , , , , , , , , , , , , , , , , , , , , , , , II-2
II.1.3 Конвейер. , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , II-3
II.1.4 Генератор клоков. , , , , , , , , , , , , , , , , , , , , , , , , , , , II-32
II.1.5 АЛУ. , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , II-33
II.1.6 Сдвиговое устройство. , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , II-35
II.1.7 Стек данных. , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , II-38
II.1.8 Вызов стека. , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , II-39
II.1.9 Тестовые файлы. , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , II-40
II.2 ELF в память. , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , II-45
Cписок рисунков
2.1. Модель Ахо Ульмана. , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , 6
2.2. Модель Дэвидсона Фрейзера. , , , , , , , , , , , , , , , , , , , , , , , , , , , , 6
3.1 Биты регистра состояния. , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , 12
3.2 Биты программы. , , , , , , , , , , , , , , , , , , , , , , , , , , , , 13
3.3 Регистр указателя стека. , , , , , , , , , , , , , , , , , , , , , , , , , , , , 13
3.4 Функциональная блок-схема ЦП RISC. , , , , , , , , , , , , , , , , , 15
3.5 Четырехступенчатый конвейер. , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , 16
3.6 Четырехступенчатая блок-схема конвейера. , , , , , , , , , , , , , , , , , , , , , 16
3.7 Фазы синхронизации. , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , 19
3.8. Загрузите и сохраните инструкцию. , , , , , , , , , , , , , , , , , , , , , , 19
3.9. Слово для передачи данных. , , , , , , , , , , , , , , , , , , , , , , , 20
3.10. Инструкция по управлению потоком. , , , , , , , , , , , , , , , , , , , , , , , 21
3.11. Инструкция по регистрации манипулятора регистрации. , , , , , , , , , , , , , 23
3.12. Инструкция о немедленной манипуляции с регистрацией. , , , , , , , , , , , , 23
3.13. Регистровый регистр сдвиг и поворот инструкции. , , , , , , , , , , , , 24
3.14. Слово «Инструкция о немедленном манипулировании». , , , , , , , , , , , , 24
4.1. CJGMCTargetDesc.h График включения. , , , , , , , , , , , , , , , , , , , , 32
4.2. Первоначальный myDouble: запись SelectionDAG. , , , , , , , , , , , , , , , , , , , , 43
4.3. Первоначальный myDouble: if.then SelectionDAG. , , , , , , , , , , , , , , , , , , , 44
4.4 Первоначальный myDouble: if.end SelectionDAG. , , , , , , , , , , , , , , , , , , , , 45
4.5 Оптимизированный myDouble: запись SelectionDAG. , , , , , , , , , , , , , , , , , , 47
4.6. Легализованный myDouble: запись SelectionDAG. , , , , , , , , , , , , , , , , , , 48
4.7. Выбранный myDouble: запись SelectionDAG. , , , , , , , , , , , , , , , , , , , 52
4.8. Выбранный myDouble: if.then SelectionDAG. , , , , , , , , , , , , , , , , , , 53
4.9 Выбранный myDouble: if.end SelectionDAG. , , , , , , , , , , , , , , , , , , , 54
5.1 myDouble Simulation Waveform. , , , , , , , , , , , , , , , , , , , , , , , 64
Список объявлений
4.1 Определения набора регистров таблицы. , , , , , , , , , , , , , , , , , , , , , , 30
4.2. Вывод таблицы AsgWriter. , , , , , , , , , , , , , , , , , , , , , , , , 30
4.3. Вывод отчета RegisterGen. , , , , , , , , , , , , , , , , , , , , , , , , 30
4.4 Определение класса основных регистров. , , , , , , , , , , , , , , , , , 33
4.5. Определение условного вызова. , , , , , , , , , , , , , , , , , , , , 34
4.6. Специальные определения операндов. , , , , , , , , , , , , , , , , , , , , , , , , , 35
4.7 Определение базовой инструкции CJG. , , , , , , , , , , , , , , , , , , , , , , , 36
4.8 Определения формата базы данных АЛУ. , , , , , , , , , , , , , , , , , , 37
4.9 Завершенные определения инструкций АЛУ. , , , , , , , , , , , , , , , , , , , 38
4.10. Завершенное определение условной инструкции перехода. , , , , , , , , , , , , 40
4.11 Зарезервированные регистры Описание Реализация. , , , , , , , , , , , , , , 41
4.12. Реализация myDouble C. , , , , , , , , , , , , , , , , , , , , , , , , , 41
4.13 myDouble LLVM IR Code. , , , , , , , , , , , , , , , , , , , , , , , , , , 42
4.14. Определения пользовательских SDNode TableGen. , , , , , , , , , , , , , , , , , , , , 49
4.15 Определения для конкретных SDNode-операций. , , , , , , , , , , , , , , , , 49
4.16 Кодирование кода условия перехода. , , , , , , , , , , , , , , , , , , , , , , , 49
4.17. Реализация операции SDNode для конкретных целей. , , , , , , , , , , , , , 50
4.18. Начальный список инструкций MyDouble Machine. , , , , , , , , , , , , , , , , , 55
4.19. Окончательный список инструкций MyDouble Machine. , , , , , , , , , , , , , , , , , , 56
4.20 Custom printMemSrcOperand Реализация. , , , , , , , , , , , , , , , 58
4.21 Заключительный код myDouble Assembly. , , , , , , , , , , , , , , , , , , , , , , , 58
4.22. Внедрение пользовательских getMemSrcValue. , , , , , , , , , , , , , , , , , 59
4.23 Определения формата базовой загрузки и хранения. , , , , , , , , , , , , 60
4.24. Кодирование выходного файла TableEenter для загрузки. , , , , , , , , , , , , , 60
4.25 Демонтированный код MyDouble Machine. , , , , , , , , , , , , , , , , , , , 61
4.26 myDouble Machine Code. , , , , , , , , , , , , , , , , , , , , , , , , , , , 61
5.1 Измененный код myDouble Assembly. , , , , , , , , , , , , , , , , , , , , , 65
Список таблиц
3.1 Описание битов регистра состояния. , , , , , , , , , , , , , , , , , , , , , 12
3.2 Описание режима адресации. , , , , , , , , , , , , , , , , , , , , , , , , 19
3.3. Инструкции по загрузке и хранению. , , , , , , , , , , , , , , , , , , , , , 20
3.4. Инструкции по передаче данных. , , , , , , , , , , , , , , , , , , , , , , 20
3.5 Описание кода условия перехода. , , , , , , , , , , , , , , , , , , , , , , 22
3.6. Инструкции по управлению потоком. , , , , , , , , , , , , , , , , , , , , , , , 22
3.7 Подробные инструкции по манипуляции. , , , , , , , , , , , , , , , , , , , , , , 23
3.8. Сдвиг и поворот Инструкции. , , , , , , , , , , , , , , , , , , , , , 25
4.1 Регистрация карты для myDouble. , , , , , , , , , , , , , , , , , , , , , , , , , , 57
5.1. Предварительный просмотр области списка каналов. , , , , , , , , , , , , , , , , , , , , , , , , 66
5.2. Результаты сканирования Netlist для предварительного сканирования. , , , , , , , , , , , , , , , , , , , , , , , , 66
5.3. Результаты сканирования в списке Netlist. , , , , , , , , , , , , , , , , , , , , , , , , 67
5.4 Результаты синтаксического анализа Netlist после сканирования. , , , , , , , , , , , , , , , , , , , , , , , 67
Глава 1
Введение
Инфраструктура компилятора – популярная область исследований в области информатики. Почти каждая возникающая современная проблема дает решение использующее программное обеспечение в какой-то момент его реализации. Это особенно важно для компиляторов в качестве инструментов для перевода программного обеспечения из его письменного состояния в состояние, которое может использоваться центральным процессор (CPU). Большинство исследований компилятора сосредоточено на функциональности эффективно читать и оптимизировать программное обеспечение ввода. Однако половина функциональности компилятора состоит в том, чтобы генерировать машинные инструкции для конкретной архитектуры ЦП. Эта область компиляторов, бэкэнд, во многом игнорируется и не документируется.
С целью изучения бэкэнд конструкции компиляторов, пользовательский, встроенный стиль, 32-разрядный процессор компьютера с уменьшенным набором инструкций (RISC) был разработан для использования компилятором кода C. Поскольку разработка такого компилятора с нуля не была возможным вариантом для этого проекта, два существующих и устоявшихся компилятора рассматривались в качестве отправных точек: коллекция компиляторов GNU (GCC) и LLVM. Несмотря на то, что GCC имеет возможность генерации кода для широкого спектра архитектур процессора, то же самое не относится к LLVM. Инфраструктура llvm-это относительно новый проект; тем не менее, он имеет очень современный дизайн и, кажется, хорошо документирован. LLVM был выбран по этим причинам, и, кроме того, чтобы изучить причину кажущегося отсутствия популярности в сообществе встроенного процессора.
Этот проект призван обеспечить представление о процессе принятия функции C из исходных кодов для машинного кода, который может быть выполнен на аппаратном обеспечении процессора через LLVM инфраструктуру компилятора. Во всех главах 4 и 5 простая функция C используется, как пример для детализации потока от кода C до запуска машинного кода. Машинный код моделируется на пользовательском процессоре с использованием Cadence Incisive и синтезируется с помощью Synopsys Design Compiler.
1.1 Организация
В главе 2 обсуждается базовый дизайн процессоров и компиляторов для обеспечения некоторой фоновой информации. В главе 3 представлен дизайн и реализация пользовательского RISC-процессора и архитектуры. В главе 4 представлен дизайн и реализация пользовательского LLVM компилятор. В главе 5 показаны тесты и результаты реализации LLVM компилятор для настраиваемого ЦП RISC, чтобы показать, где этот проект преуспевает и терпит неудачу. В главе 6 обсуждается возможная будущая работа и завершается работа над документом.