[Перевод] Как я написал компилятор C за 40 дней
Предлагаю вам перевод дневника Руи Уэяма (Rui Ueyama), программиста из Google, который он вел во время работы над реализацией компилятора языка C около трех с половиной лет назад.
Этот дневник не несет какой-то практической пользы и не является туториалом, но мне было очень интересно его прочитать, надеюсь и вам эта история тоже понравится :)
Я написал C компилятор за 40 дней, который назвал 8cc. Это дневник написанный мной в то время. Код и его историю можно посмотреть на GitHub.
День 8
Я пишу компилятор. Он начал работать после написания примерно 1000 строк кода. Вот несколько примеров, которые уже работают:
int a = 1;
a + 2; // => 3
int a = 61;
int *b = &a;
*b; // => 61
Массивы корректно преобразовываются в указатели, так что код ниже тоже работает. Также поддерживается вызов функций.
char *c = "ab" + 1;
printf("%c", *c); // => b
Реализовать это было не сложно, т.к. я делаю это уже второй раз. Я научился лучше управляться с массивами и указателями.
День 15
Я далеко продвинулся в реализации компилятора и он работает на удивление хорошо. Нетривиальные программы, например эта — решающая задачу о восьми ферзях, компилируются и запускаются.
Конечно ему не хватает многих функций. Эти примеры программ подобраны так, чтобы не использовать их.
Реализация довольно проста; нет даже распределения регистров (register allocation).
Он компилирует программы на стеке, используя стек машины как стек. Каждая операция требует обращения к памяти. Но пока меня это устраивает.
В начале компилятор умещался примерно в 20 строк и единственное на что он был способен это прочитать целое значение со стандартного входа и запустить программу которая тут же завершается возвращая это целое.
Теперь он содержит около 2000 строк. Если посмотреть git, то кажется он развивался таким образом:
- добавлены »+» и »-»
- разделены фазы синтаксического анализа и генерации кода
- добавлены »*» и »/»
- добавлены переменные (неявно подразумевающие тип int)
- добавлен вызов функций
- добавлены строки
- разделены генератор меток (tokenizer) и анализ синтаксиса
- поддержка объявления базовых типов
- добавлены указатели и массивы
- поддержка выражений инициализации массивов
- добавлен «if»
- поддерживается объявление функций
- добавлены «for» и «return»
- поддерживается присвоение указателей
- добавлено »==»
- добавлены индексация массивов и арифметика указателей
- добавлены »++»,»--» и »!»
День 17
Я успешно реализовал структуры. Структура — это такой объект, который может занимать больше одного машинного слова. Их сложнее реализовать, чем примитивные типы, но это было легче чем я ожидал.
Кажется, это работает как надо; я могу определить структуру, содержащую структуру. Я могу определить указатель на структуру и разыменовать его. Структуры, содержащие массивы и массивы структур также работают. Хотя я уже знал, что код теоретически должен работать, я все равно обрадовался, когда он действительно заработал, даже в таком сложном случае.
Однако, я не чувствую, что я полностью понимаю, почему этот код работает правильно. Он ощущается немного магическим из-за его рекурсивной природы.
Я не могу передавать структуры в функции. В соглашении о вызовах для x86 структура копируется на стек и указатель на нее передается функции. Но в x86–64 вы должны разделить структуру на несколько частей данных и передать их через регистры. Это сложно, так что это я пока отложу. Передача структур по значению нужна реже, чем передача указателей на них.
День 18
Реализовать объединения было легче, т.к. это просто вариант структуры, в котором все поля имеют одинаковое смещение. Также реализован оператор »→». Проще простого.
Организовать поддержку чисел с плавающей точкой было тяжело. Похоже неявное преобразование типов между int и float работает, но числа с плавающей точкой не могут быть переданы в функции. В моем компиляторе все параметры функций сначала помещаются на стек, а затем записываются в регистры в порядке определенном в соглашении о вызовах x86–64. Но в этом процессе видимо есть баг. Он возвращает ошибку доступа к памяти (SIGSEGV). Его сложно отлаживать, рассматривая ассемблерный вывод, потому что мой компилятор не оптимизирует ассемблер для чтения. Я думал, что смогу закончить с этим за день, но я ошибался.
День 19
Я потратил время впустую, потому что забыл что в соответствии с соглашением о вызовах x86–64 кадр стека должен быть выровнен на 16 байт. Я обнаружил, что printf () падает с SEGV, если передать ей несколько чисел с плавающей точкой. Я попытался найти условия при которых это можно воспроизвести. Оказалось что имеет значение положение стекового кадра, что заставило меня вспомнить про требования ABI x86–64.
Я совсем не позаботился об этом, так что кадр стека был выровнен только по 8 байт, но print () не жаловалась пока принимала только целые числа. Эта проблема может быть легко исправлена корректировкой стекового кадра до вызова инструкции CALL. Но таких проблем не избежать если, тщательно не читать спецификацию перед написанием кода.
День 20
Я поменял отступы в коде компилятора с 2 на 4. Я больше привык к использованию 2-ух пробельных отступов, потому что такие используются на моей работе в Google. Но по некоторым причинам мне кажется отступы в 4 пробела больше подходят для «красивой программы с открытым исходным кодом».
Есть еще одно, более значимое, изменение. Я переписал тесты из shell скриптов на C. До этого изменения каждая тестовая функция компилируемая моим компилятором, связываллась с main () которая компилировалась GCC и затем запускалась shell скриптом. Это было медленно, т.к. порождало много процессов для каждого теста. У меня не было выбора когда я начинал проект, т.к. у моего компилятора не было многих функций. Например, он не мог сравнить результат с ожидаемым значением из-за отсутствия операторов сравнения. Теперь он достаточно мощный, чтобы компилировать код тестов. Так что я переписал их, чтобы сделать их быстрее.
Еще я реализовал большие типы, такие как long и double. Написание кода было веселым потому что я очень быстро преуспел в реализации этих функций.
День 21
Я почти закончил реализацию препроцессора C за один день. На самом деле это порт из моей предыдущей попытки написать компилятор.
Реализация препроцессора C не простая задача.
Это часть стандарта C, так это определено в спецификации. Но спецификация говорит слишком мало, чтобы это могло быть полезным для самостоятельной реализации. Спецификация включает несколько макросов с их развернутая формой, но она очень мало говорит о самом алгоритме. Я думаю она даже не объясняет детали его ожидаемого поведения. В общем, он недоспецифицирован.
Насколько я знаю, PDF в этом блоге единственный и лучший ресурс о том как реализовать препроцессор языка C. Алгоритм описанный в документе (алгоритм Дейва Проссера) пытается развернуть столько токенов сколько возможно, избегая бесконечного разворачивания макроса. Каждый токен имеет свою историю разворачивания, так что токены не разворачиваются одним и тем же макросом более одного раза.
Препроцессор C сам по себе является независимым языком. У него много особенностей, и только матерые программисты C хорошо его понимают.
День 22
Пытался заставить компилятор читать системные заголовки, так что теперь он понимает #include. Пока я пытался, я получал много ошибок. Это выявило, что моему препроцессру до сих пор не хватает многих функций, например операторы которые можно использовать только в #if. Существует и много багов кроме этого. Я исправлял их, как только находил.
Системные заголовочные файлы большие и запутанные. Они требуют много функций от компилятора, таких как enum и typedef. Я реализовал их одну за другой, но иногда я срезал углы. Я пытаюсь прочитать stdio.h. Понятия не имею как много времени это может занять.
Компилятор сейчас состоит из 4000 строк. Небольшой компилятор LCC содержит 12000 строк. Используя его как гайд, я думаю, мой компилятор скоро сможет работать как настоящий компилятор C.
Я удивлен, что написал 500 строк кода сегодня. Я могу работать в потоке на протяжении 12 часов, но это может быть неэффективно, т.к. я устаю не замечая этого. В любом случае я должен признать, что я человек с большим количеством свободного времени.
День 24
Я не помню что я исправил, но теперь stdio.h может подключаться. Это очень круто, потому что типы функций определенных в заголовочном файле теперь корректно обрабатываются.
Схема, которую я использую для реализации своего компилятора, подразумевает создание компилятора для небольшого подмножества языка и затем развитие его в настоящий язык C. До недавнего момента, я не сильно пытался реализовывать функции, которые не до конца понимаю. Я мог писать столько кода сколько хочу и оставлять остальное. Это было весело.
Внешние штуки, такие как система заголовков, стали причиной многих проблем. Теперь я должен реализовать все функции которые ожидаются от «настоящего» компилятора C. Я сделал много грязных хаков, чтобы прочитать stdio.h. Например, я реализовал хак для игнорирования всех вхождений токена «const». Это расстраивает меня.
Вы можете спросить, почему бы не сделать это правильным способом с самого начала. Я бы сказал, что это не весело. Слишком. Например синтаксис объявления типов в C слишком запутанный без какой либо вменяемой причины и реализовывать его совсем не интересно.
Не смотря на это есть некоторые вещи которых я не могу избежать. Вероятно, мне следует изменить мой взгляд, чтобы реализовать все функции, от начала и до конца. Я могу найти это интересным по мере приближения к цели. Иногда, мне приходится писать больше кода, чем я хочу для того, чтобы достичь цели.
День 25
Я застрял на два дня с реализацией синтаксиса определений и объявлений без какого-либо успеха. Почему я не могу закончить это? Я сделал указатели и структуры за один день работы. Я чувствую что недооценил это. Может быть мне нужен план?
День 26
В сложной ситуации как эта, я, вероятно, должен вспомнить тот факт что компилятор был всего в одном файле, чтобы увидеть как я продвинулся за месяц. Он просто считывал целое через scanf () и печатал его через printf (). Действительно, я очень серьезно продвинулся за один месяц. Да, я думаю могу сделать это.
День 28
Закончил писать парсер для объявлений и определений. Думаю причина по которой я терпел неудачи была в том, что я пытался написать слишком много деталей с самого начала, так что я написал псевдокод чтобы убедиться что правильно все понимаю и затем конвертировал его в реальный код.
Я пишу на C уже почти 15 лет, но только сегодня я почувствовал, что, наконец, понимаю синтаксис типов в С. Не удивительно, что я не мог писать работающий код. Это потому, что я просто не понимал его правильно.
Код, который я только что написал слишком сложен и хрупок, что даже я с трудом его понимаю. Я не верю, что Деннис Ритчи, создатель языка C, понимал последствия того, что он делал. Я подозреваю, что он придумав синтаксис, написал код, который оказался сложнее, чем он ожидал, и, в итоге, был стандартизирован комитетом ANSI. Трудно реализовать стандартизированный язык, потому что вы должны сделать все правильно. Скорее легче написать свой собственный игрушечный язык.
День 29
Реализовал еще много операторов и почистил код.
Сегодня моему компилятору впервые удалось скомпилировать один из своих файлов. Когда я связал его с другими файлами, скомпилированными с помощью GCC, он оказался рабочим. И получившийся компилятор тоже кажется работает. Похоже цель становится ближе.
День 30
Я реализовал switch-case, continue, break и goto сегодня. Когда я писал тест кейсы для goto, код тестов быстро превратился спагетти код, который я не мог прочитать. Это меня рассмешило. Я убедился, почему goto считается вредным.
День 31
Реализовал функции для varargs, а именно va_start, va_arg и va_end. Они используются не часто, но я нуждался в них для компиляции функций, например printf.
Спецификация vararg для C не очень хорошо продумана. Если вы передаете все аргументы функции через стек, va_start может быть реализован довольно легко, но на современных процессорах и в современных соглашениях о вызовах аргументы передаются через регистры, чтобы уменьшить накладные расходы на вызов функций. Поэтому спецификация не соответствует реальности.
Грубо говоря, ABI для x86–64, стандартизированное AMD, требует чтобы функции с переменным числом аргументов копировали все регистры в стек, чтобы подготовиться к последующему вызову va_start. Я понимаю, что у них не было другого выбора, но это все равно выглядит неуклюже.
Мне стало интересно как другие компиляторы обрабатывают функции с переменным числом аргументов. Я посмотрел на заголовки TCC и, похоже, они не совместимы с ABI x86–64. Если структура данных для varargs отличается, то функции передающие va_list (такие как vprintf) становятся несовместимыми. Или я ошибаюсь? [И я действительно ошибаюсь — они совместимы.] Я также посмотрел на Clang, но он выглядит запутанным. Я не стал читать его. Если я буду читать слишком много кода других компиляторов, это может испортить веселье от собственной реализации.
День 32
После исправления незначительных проблем и добавления управляющих последовательностей для строковых литералов (до сих пор не было '\0' и подобных вещей), получилось скомпилировать еще один файл. Я чувствую уверенный прогресс.
Я пытался реализовать поддержку функций, имеющих более шести параметров, но не смог закончить это за один день. В x86–64 первые 6 целочисленных параметров передаются через регистры, а оставшиеся через стек. Сейчас поддерживается передача только через регистры. Передачу через стек не сложно реализовать, но она требует слишком много времени для отладки. Я думаю в моем компиляторе нет функций, имеющих более шести параметров, так что я пока отложу их реализацию.
День 33
Еще три файла скомпилированы сегодня. Итого 6 из 11. Но если считать строки кода, то это около 10% от общего числа. Оставшиеся файлы намного больше, так как содержат код ядра компилятора.
Еще хуже то, что в файлах ядра я использую относительно новые особенности C, такие как составные литералы и назначенные инициализаторы. Они сильно усложняют самокомпиляцию. Я не должен был использовать их, но переписывать код на простом старом C будет не продуктивно, поэтому я хочу поддерживать их в своем компиляторе. Хотя на это потребуется время.
День 34
Несколько замечаний о средствах отладки. Так как компилятор — это сложный кусок кода, который состоит из многих этапов, необходим способ как-то исследовать его для отладки. Мой компилятор не исключение; я реализовал несколько функций, которые посчитал полезными.
Во-первых, лексический анализатор запоминает свою позицию чтения и когда он прерывается по непредвиденным причинам, он возвращает эту позицию. Это позволяет легко найти баг, когда компилятор не принимает корректные входные данные.
Есть опция командной строки для печати внутреннего абстрактного синтаксического дерева. Если есть ошибка в синтаксическом анализаторе, я хочу посмотреть на синтаксическое дерево.
Генератор кода позволяет широко использовать рекурсию, потому что он генерирует фрагменты ассемблерного кода, когда обходит абстрактное синтаксическое дерево. Так я смог реализовать печать мини трассировки стека для каждой строки ассемблерного вывода. Я если я замечаю что-то неправильное, я могу проследить за генератором кода, посмотрев на его вывод.
Большинство внутренних структур данных имеют функции для преобразования в строку. Это полезно при использовании printf для отладки.
Я всегда пишу юнит-тесты, когда пишу новую функцию. Даже реализовав ее, я стараюсь сохранять код компилирующимся, чтобы запускать тесты. Тесты пишутся так, чтобы выполняться за короткий промежуток времени, так что вы можете запускать их так часто, как вам хочется.
День 36
Реализовал составные литералы и переписал инициализатор структур и массивов. Мне не нравилась предыдущая реализация. Теперь инициализатор стал лучше. Я должен был написать красивый код с самого начала, но поскольку я понял это, только написав рабочий код, переписывание было неизбежным.
Думаю, единственная особенность, которой не хватает для самокомпиляции, это присваивание структур. Надеюсь все будет работать как задумано без особой отладки, когда она будет реализована.
День 37
Файл, содержащий токенайзер скомпилирован, но получившийся компилятор второго поколения по некоторым причинам не генерирует корректный ассемблерный код. Хотя код, генерируемый компилятором первого поколения проходит все тесты. Такой вот коварный баг.
Думаю, что у меня нет другого выбора, кроме использования printf для отладки, потому что второе поколение компилируется через мой компилятор, который не поддерживает отладочную информацию. Я добавил printf в подозрительных местах. Отладочные сообщения printf отображались при компиляции второго поколения, что меня несколько удивило. Я хотел чтобы отладочные сообщения выводились только когда я использую второе поколение, так что я не ожидал что вывод будет работать, когда второе поколение только создается.
Мне это напоминает фильм «Начало». Мы должны идти глубже, чтобы воспроизвести этот баг. Это забавная часть отладки самокомпилирующегося компилятора.
День 38
Я исправил проблему, возникавшую во втором поколении, если лексический анализатор был самоскомпилирован. Она вызывала баг при котором -1 > 0 иногда возвращало true (я забыл про знаковое расширение). Есть еще один баг в размещении структур (struct layout). Осталось только три файла.
День 39
Генератор кода теперь тоже может скомпилировать себя. Осталось два файла. Работа почти закончена, хотя мне, возможно, не стоит быть чересчур оптимистичным. Могут оставаться еще неожиданные подводные камни.
Я исправил много проблем, вызванных плохим качеством кода, который я писал на ранней стадии этого проекта. Это утомило меня.
Я верил, что имел все возможности для самокомпиляции, но это не правда. Нет даже префиксных операторов инкремента/декремента. Для некоторых особенностей C99 я переписал часть компилятора, чтобы сделать его более удобным для компиляции. Так как я не ожидал добраться до возможности самокомпиляции так быстро, я использовал столько новых особенностей C, сколько хотел.
День 40
Ура! Мой компилятор теперь может полностью себя скомпилировать!
Это заняло около 40 дней. Это очень короткий промежуток времени, для написания самокомпилируемого компилятора C. Вы так не думаете? Я считаю, что мой подход — вначале сделать небольшой компилятор для очень ограниченного подмножества C, и затем преобразовать его в настоящий компилятор C очень хорошо сработал. В любом случае сегодня я очень счастлив.
Смотря на свой код, даже зная что я сам написал его, я ощущаю его немного волшебным, потому что он может принять сам себя на входе и преобразовать в ассемблер.
Осталось много багов и нереализованных особенностей. Я, наверное, закончу с ними, а потом начну работу по улучшению выходного кода.
Исходный код находится здесь. Я не знаю, стоит ли это читать, но может быть интересно посмотреть его как образец кода на языке C, который может обработать простой компилятор в 5000 строк.
День 41
Вернулся к систематической разработке, так как была достигнута большая веха. Я изменил код, пытаясь читать его, как если бы я был третьим лицом, и, в итоге, удовлетворился качеством кода. Это напоминает подрезку дерева бонсай.
Я добавил тест для повторного запуска самокомпиляции, чтобы убедиться, что результаты оказываются одинаковыми для второго и третьего поколения файлов. Если я правильно помню, у GCC есть подобный тест.
День 42
Есть часть информации, которую можно передать следующему поколению только через исполняемые файлы в двоичном формате, несмотря на то что она не записывается в исходный код компилятора.
Например, мой компилятор интерпретирует »\n» (последовательность обратного слеша и символа «n») в строковый литерал »\n» (в данном случае символ новой строки). Если вы подумаете об этом, вы можете счесть это немного странным, потому что он не располагает информацией о реальном ASCII коде для »\n». Информация о коде символа не присутствует в исходном коде, но передается из компилятора, компилирующего компилятор. Символы новой строки моего компилятора могут быть прослежены до GCC.
Компиляторы могут передать гораздо больше информации, чем код символа.
Эта удивительная история была представлена Кеном Томпсоном в его лекции при получении премии Тьюринга. Информация, которую Кен добавил в раннюю версию Unix компилятора давала возможность программе для входа пользователей принимать некоторые особенные пароли, так что Кен мог войти в любую учетную запись Unix. Он также сделал так чтобы компилятор распознавал собственную компиляцию и передавал хак программы для входа дочернему компилятору, так что этот бэкдор (которого не было в исходном коде) передавался из поколения в поколение. Вы не могли удалить его, даже если бы тщательно осмотрели каждую строчку исходного кода компилятора и перекомпилировали его, поскольку компилятор, который обрабатывает исходный код был заражен. Это удивительная история, не правда ли?
День 43
Переписал реализацию парсера для операторов на метод рекурсивного спуска вместо использования первенства операторов (operator-precedence parser). Я думаю, что причина для того, чтобы выбрать парсер использующий приоритет операторов это простота и скорость, но грамматика используемая в для операторов в C слишком запутанная для обработки таким способом (например, индексы массивов или различные виды унарных операторов). Код теперь легче читать, чем раньше, потому что большие функции разбиваются на множество мелких. Также теперь должно быть легче добавить проверку ошибок в парсер.
Техники написания парсеров — это один из моих самых полезных навыков как программиста. Он помогал мне бесчисленное количество раз.
Однако, когда я читал спецификацию языка Си, чтобы написать парсер для грамматики использующий рекурсивный спуск, я обнаружил, что некоторые производные являются леворекурсивными. Мне пришлось некоторое время подумать и открыть учебник еще раз, чтобы вспомнить, как переписать грамматику, чтобы сделать ее праворекурсивной. Устранение левой рекурсии является базовой темой в синтаксическом анализе, которая описывается в любом вводном учебнике. Но я не мог вспомнить такие элементарные вещи, так как не использовал технику на протяжении длительного периода времени.
День 44
Входные данные сейчас преобразуются таким образом: строка символов → последовательность токенов → последовательность токенов после подстановки макросов → абстрактное синтаксическое дерево → x86–64 ассемблер. Последний переход, возможно делает слишком много и слишком запутан. Он выполняет различные виды операций, такие как неявные преобразования типов и разворачивание имен меток, пока производит ассемблерный код. Теоретически, я, вероятно, должен определить промежуточный язык между АСД и ассемблером.
Я снова читал Dragon Book по этой теме, не чувствуя, что я полностью ее понял. Книга слишком абстрактна, так что я не могу немедленно применить ее моем случае.
Мой компилятор в два раза медленнее чем GCC когда компилирует сам себя. Это не так плохо, как я думал. Мой компилятор генерирует жутко бесхитростный ассемблер, но такой код не медленнее на порядок.
День 45
Мне было интересно, как gcov будет работать на моем коде. Он нашел множество ветвей кода, которые не прошли юнит тесты. Я нашел несколько багов, добавив тесты для этих ветвей кода. Инструменты покрытия кода действительно полезны.
День 46
Я чувствую, что у меня кончились идеи о том, что делать с компилятором. Для меня было не сложно добраться до текущего состояния разработки, потому что мне не пришлось изучать новые штуки, но вещи за пределами этой точки кажется трудновыполнимым.
Я вынес неявное преобразование типов из генератора кода. Они сейчас явно представлены в АСД. Это позволяет легко понять, что происходит под капотом. Я также сделал бессистемные улучшения в различных местах. Я думал, что работа была почти завершена, но в действительности существовало множество нереализованных особенностей и ошибок.
Я стал лучше понимать оптимизацию компилятора, после того как прочитал еще несколько страниц из Dragon Book. Я мог бы начать писать код, если разберусь в этом еще чуть-чуть лучше.
День 52
Я искал таинственный баг в течение трех дней: если вы округлите вверх или вниз указатель стека для выравнивания к 16-байтовой границе, компилятор второго поколения выводит сообщение об ошибке для корректных входных данных. Такого рода ошибки отлаживать труднее, чем обычные фатальные ошибки.
Моим первым предположением было: неправильное выравнивание указателя стека. Но это не так, потому что указатель стека был уже правильно выровнен по 16-байтовой границе. Я не мог найти баги в ассемблерном выводе. Я решил разделить пополам.
Я пытался компилировать каждый файл через мой компилятор, а остальное через GCC чтобы определить функцию, с которой я могу воспроизвести проблему. Но казалось, что функция не содержит ошибок. Это не функция, которая выводит сообщение об ошибке — они даже не в одном файле. Теория заключается в том, что одна функция создает неверные данные которые вызывают ошибки в других функциях.
После продолжительной бессистемной отладки, я наконец нашел причину: компилятор не инициализирует поля структуры нулями. Спецификация C требует, чтобы при инициализации структуры, поля, не инициализирующиеся значениями, компилятор должен автоматически заполнять нулями. Я знал спецификацию когда писал код (поэтому мой код зависит от этого поведения), но я забыл его реализовать. В результате некоторые поля структур инициализировались мусором вместо нулей. Мусорные данные меняются в зависимости от текущей позиции стека, поэтому изменение указателя стека случайным образом изменяло поведение программы.
В итоге, после трехдневной отладки была исправлена всего одна строка. Хотелось бы иметь какие-то средства чтобы упростить подобную отладку.
День 53
Исправлена еще одна загадочная ошибка. Если компилировать некоторые файлы с помощью GCC, а остальные — моим компилятором, то полученный компилятор сообщает о синтаксических ошибках при корректных входных данных. Такие проблемы должны быть связаны с совместимостью ABI. Моим первым предположением было, что проблема может быть связана с разметкой структур или тем как аргументы передаются в функции, но ассемблерный выход для них кажется правильными.
Я снова сузил поиск до конкретного файла, разделяемого пополам. Я переносил функции по очереди из одного файла в другой, чтобы найти функцию, которая была причиной проблемы. Эта функция была не маленькой, поэтому я разделял ее и переносил код в другой файл. Наконец я получил несколько строк кода. Я скомпилировал их, с помощью GCC и моего компилятора и сравнил.
Единственная разница заключалась в этом: мой компилятор проверяет все биты в регистре, чтобы определить содержит ли он булево значение true, тогда как GCC проверяет только младшие 8 бит. Таким образом, например, если значение в регистре 512 (= 29 или 0×100), то мой компилятор воспринимает его как true, тогда как GCC считает по-другому. GCC на самом деле возвращает некоторое очень большое число с нулями в наименее значимых 8 битах, что воспринимается как false.
Из-за этой несовместимости, цикл, который использует для проверки условия выхода функцию, скомпилированную с помощью GCC (при этом сам цикл компилируется моим компилятором) прекращается сразу же на первой итерации. В результате, макросы препроцессора не определяются. И какие-то из токенов оставались неопределенными и поэтому парсер сообщал о синтаксических ошибках при некоторых входных данных. Причина была далеко от того места, где сообщалось об ошибке, но я, наконец, отловил ее.
Спецификация x86–64 ABI имеет небольшую заметку о том, что только младшие 8 бит являются значимыми для логических возвращаемых значений. Я читал это, но в первый раз не понял что это значит, так что я даже не помнил, что такое указание существовало. Но теперь для меня это предельно ясно. У меня смешанные чувства — я узнал новые вещи, но я мог бы их узнать, не тратя на это столько времени.
День 55
Реализованы битовые поля.
Вы можете упаковать несколько переменных в небольшой области с использованием битовых полей, но компилятор все равно должен создавать пространство между ними в зависимости от их типов. Мое быстрое исследование вывода GCC выявило такие правила (конечно, без гарантии, что они правильны):
- Выравнивание первого битового поля подчиняется выравниванию типа. Например, для «int x:5», x выравнивается по 4-байтовой границе (предполагается, что int — это 32 бита).
- Любая переменная не должна пересекать свои естественные границы. Например, для «int x:10», x не должен пересекать 4-байтовую границу. Если оставшееся число битов слишком мало, чтобы удовлетворить этому условию, они остаются неиспользованными и следующее битовое поле начинается в следующих границах.
Обращение к битовому полю требует больше одной машинной инструкции, потому что CPU не имеет инструкций для доступа к отдельным битам в памяти. Вы должны прочитать в регистр память, содержащую битовое поле, а затем использовать & маску для чтения битового поля. Когда вы записываете его в память, вы должны сначала прочитать память, содержащую битовое поле, применить побитовую маску &, побитовое «или», чтобы получить новое значение, и затем записать значение обратно в память.
День 56
Реализованы вычисляемые goto (computed goto). Обычный goto может ссылаться только на одну метку, но вычисляемый goto может принимать указатель и передавать управление на этот адрес. Этого нет в стандарте C и существует как расширение для GCC. Если вы когда-либо писали виртуальную машину с очень большим switch-case, вы, скорее всего, знаете об этой возможности. Эта функция часто используется, чтобы заменить большой переключатель switch-case на таблицу преобразований и вычисляемый goto.
Вычисляемый goto компилируется в единую инструкцию непрямого перехода. Наверное, это легче понять в терминах ассемблера. Мой компилятор генерирует ассемблер, так что это было очень легко реализовать.
День 57
Реализовал C11 _Generic, потому что я хотел использовать его в своем компиляторе. Но после реализации, я заметил, что GCC 4.6.1 не поддерживает _Generic. Я не могу использовать эту функцию так как если я использую ее, то GCC не сможет компилировать мой компилятор.
Я также реализовал функцию typeof (), которая также является расширением GCC. Обе эти функции не используются в данный момент, но это нормально, так как для их реализации потребовалось очень мало кода.
День 58
Добавил диграфы из C99. Диграф — это необычная функция для специфичных окружений, в которых невозможно использовать некоторые символы. Например,»
В С89 есть триграфы, которые очевидно вредны. Триграфы — трехбуквенные последовательности символов, которые преобразуются в один символов везде, где они появляются в исходном коде. Например, printf («huh?!») выведет не «huh?!», а «huh|» потому что »?!» это триграф для »|». Это сильно сбивает с толку. У меня нет планов, поддерживать триграфы.
День 62
Я пытаюсь скомпилировать TCC. Но пока я далек от успеха из-за нереализованных функций и ошибок.
TCC — это маленький компилятор C, размер которого составляет от 20К до 30к строк кода. Если вы удалите поддержку архитектур кроме x86–64, количество строк, вероятно, будет около 10К-20К. Удивительно видеть, что такой маленький компилятор поддерживает такое множество функций. Фабрис Беллар, создатель ТСС, — гений.
Я несколько раз попытался прочитать исходный код TCC, но все еще не понимаю всю картину. Компиляторы это сложные программы, поэтому вы обычно хотите разбить их на небольшие управляемые части, но исходный код ТСС ощущается, как монолитный компилятор. Я не могу писать такой великолепный код. Я не знаю, хочу ли я подражать, но то что в мире есть кто-то, кто может писать такой код, действительно производит на меня впечатление.
День 73
Безуспешно продолжал работать над компиляцией TCC. Конечно это тяжело, потому что если она пройдет, это значит мой компилятор имеет те же функции что и TCC. Компиляция других компиляторов полезна для отладки, но по своей природе она придираеся к каждой детали спецификации языка.
