Замкнуть круг

Прошлая глава закончилась замером: наш Лисп почти в сотню раз медленнее Python, потому что при каждом вызове заново разбирается в одном и том же дереве. Есть другой путь — разобраться один раз и перевести программу в язык, который понимает машина. Окупается ли перевод, проверим на маленькой программе с двумя вложенными циклами: выполним её двумя способами. Толмач ходит по её дереву, как evaluate из главы 51. Переводчик один раз превращает то же дерево в текст на C, а C компилятор tcc из песочницы переводит в машинный код.

Ответ один и тот же — 56, а разница в скорости — несколько сотен раз. Внутренний цикл выполняется пятьдесят тысяч раз, и толмач пятьдесят тысяч раз выясняет, что перед ним присваивание, что справа — исключающее ИЛИ, где лежит s. Программа на C ничего не выясняет: всё решено при переводе, и процессору остаётся выполнять команды. Функция to_c — полтора десятка строк, и это уже компилятор, правда, перекладывающий самую трудную часть на tcc.

Трудную часть мы сделаем сами и переводить будем прямо в машинный код «Искры-8» — компьютера, который вы собрали в четвёртой части курса: вентили в главе 29, сумматор и АЛУ в главе 30, память в главе 31, процессор и ассемблер в главе 32. Лексер и разборщик у нас есть с главы 50, стековая машина — с главы 15 и главы 33. Не хватает одного звена — программы, которая переведёт текст на понятном человеку языке в байты, понятные «Искре». Когда она появится, круг замкнётся: программа, написанная вами, побежит по проводам, которые вы собрали.

1952. Компилятор, которого никто не трогал

Сегодняшний компилятор делает то, что A-0 и не снилось, но идея та же: программа, которая пишет программу. Прежде чем писать такую для «Искры», надо решить, с какого языка она будет переводить.

Язык Огниво

Огнивом высекают искру. Наш язык будет маленьким подмножеством Python, чтобы его не пришлось учить, — и любую программу на нём прочтёт сам Python. В Огниве есть:

• числа от 0 до 255 — ровно столько помещается в регистр «Искры», и вся арифметика идёт по модулю 256, как в главе 33;
• переменные с латинскими именами и присваивание x = выражение;
• действия + - * & | ^ и скобки;
• циклы while и развилки if … else, в условии — одно сравнение: < > <= >= == !=;
• plot(x, y) — зажечь пиксель на экране 8 × 8, print(e) — напечатать число, read() — прочитать число с ввода.

Вот программа, которую мы будем переводить всю главу:

Она обходит экран строка за строкой и зажигает пиксель, если у номеров столбца и строки нет общих единичных битов. Получается треугольник Серпинского; в главе 9 мы рисовали его рекурсией. Здесь он возникает из одного побитового И: на месте единиц треугольника Паскаля по модулю 2 стоят ровно те клетки, где x & y == 0. Условие записано без скобок: в Python & связывает сильнее, чем ==, поэтому x & y == 0 — это (x & y) == 0. В C всё наоборот, и там эту строку пришлось бы писать со скобками — одна из знаменитых ловушек языка.

Конвейер

Компилятор работает как конвейер: каждый этап берёт результат предыдущего, переделывает и передаёт дальше. Первые два вам знакомы по главе 50. Лексер режет текст на слова. Разборщик строит из слов дерево. Огниво — подмножество Python, поэтому эти два этапа возьмём готовыми у самого Python: в стандартной библиотеке есть и лексер, модуль tokenize, и разборщик, модуль ast.

Отступы, которые человек видит глазами, лексер Python превращает в слова INDENT и DEDENT — открывающую и закрывающую скобки, которых нет в тексте. Следующие этапы для вас новые. Проверка смысла ищет ошибки, которые грамматика пропускает: имя, которое нигде не получает значения, число 300, которое не влезет в байт, вызов неизвестной функции. Промежуточный код переписывает дерево в простые команды воображаемой машины, удобные и для оптимизации, и для перевода. Оптимизатор переписывает эти команды в более короткие и быстрые. Генератор кода превращает их в команды процессора, а ассемблер из главы 32 — в байты. Пройдите конвейер сами: правьте программу и смотрите, что получается на каждом этапе.

Компилятор целиком

Вот весь компилятор Огнива на Python. Прочтите его сверху вниз: каждая функция — один этап конвейера. Под чертой — проверка: компилируем треугольник Серпинского, собираем ассемблером из главы 32 и запускаем на эмуляторе «Искры» из песочницы.

Треугольник на экране «Искры» — и ни одной строки ассемблера, написанной руками. Пройдём по этапам.

Передняя часть: только то, что есть в Огниве

front разбирает текст Python-ом, а потом обходит его дерево и переписывает в наше, маленькое: кортежи вида ("=", "x", ("+", "x", 1)), как деревья формул из главы 50. Заодно она отказывается от всего, чего в Огниве нет. Python поймёт x = [1, 2] или def f():, а front ответит CompileError с номером строки. Компиляторы часто устроены так: передняя часть понимает язык, задняя знает машину, а между ними — промежуточное представление. Так у одного языка бывает много целей, а у одной машины — много языков: у компилятора Clang передняя часть понимает C и C++, а задняя часть, LLVM, общая с Rust, Swift и другими языками.

Смысл: все ли имена на месте

Разборщик проверяет только форму. Программа x = y + 1 безупречна грамматически, но y нигде не получает значения, и выполнять её бессмысленно. Функция check собирает имена, которым что-то присваивается, и имена, которые читаются, и сравнивает. Заодно она составляет список переменных: каждой понадобится байт памяти. В больших компиляторах этот этап называют семантическим анализом, и основное в нём — проверка типов. У Огнива тип один, байт, и проверять нечего. В Python типов много, и об этом будет следующая глава.

Промежуточный код: стековая машина

Из дерева сразу в ассемблер переводить можно, но неудобно: дерево — вложенная структура, а программа для процессора — плоский список команд с прыжками. Поэтому почти все компиляторы сначала переводят дерево в промежуточное представление — простые команды воображаемой машины. Наша воображаемая машина — стековая, как виртуальная машина CPython из главы 33. Выражение x + 1 превращается в LOAD x, PUSH 1, +: сначала операнды, потом действие. Это обратная польская запись из главы 15, и получается она обходом дерева в обратном порядке: сначала левое поддерево, потом правое, потом корень.

Циклы и развилки превращаются в метки и прыжки. while — это метка в начале, проверка условия с прыжком за конец цикла, тело и прыжок обратно к метке:

В точности так же вы строили циклы из прыжков руками в главе 32. Теперь это делает gen_ir, а чтобы метки вложенных циклов не путались, она нумерует их счётчиком: L1, L2, L3…

Генерация: каждой команде — несколько команд «Искры»

Последний этап, генерация кода, переводит каждую команду стековой машины в команды «Искры». У «Искры» есть и свой, аппаратный стек: PUSH, POP и указатель SP из главы 32. Поэтому перевод почти дословный: PUSH 1 — положить число в R0 и R0 на стек; + — снять правый операнд в R1, левый в R0, сложить, положить результат обратно. Переменная — байт памяти с меткой v_x после программы.

Сравнения интереснее. CMP R0, R1 вычитает, не сохраняя разность, и ставит флаги: Z, если числа равны, C, если пришлось занимать, то есть R0 < R1. Прыжков у «Искры» четыре: всегда, если Z, если не Z, если C. Прыжка «если не C» нет, и while y < 8, которому нужно прыгнуть за цикл, когда y < 8 неверно, обходится двумя прыжками: если перенос есть — перепрыгнуть через выход, иначе — выйти. Сравнение беззнаковое: 200 больше 100, хотя в дополнительном коде 200 — отрицательное число. Флаг знака N наш компилятор не трогает.

Умножения и рисования у «Искры» нет совсем. Их делают подпрограммы, которые компилятор дописывает в конец программы, если они понадобились: __mul умножает сдвигами и сложениями, как в задаче «Умножить быстро» из главы 32, __plot вычисляет адрес строки экрана и сдвигает единичку в нужный столбец. Такой набор подпрограмм, который компилятор добавляет к каждой программе, называют библиотекой времени выполнения. У C это libc, у Python — сам CPython: каждый BINARY_OP вызывает его функцию.

«Искра» исполняет

Ячейка показала только итог, а ниже машинный код можно пройти такт за тактом. Это «Искра-8» из главы 32: экран, регистры, флаги и вся её память, 256 байт. Она исполняет то, что последним скомпилировал конвейер выше, а рядом с текущей командой видна строка исходника на Огниве, из которой та выросла.

Пустите Серпинского на медленной скорости и последите за стеком. Он то дорастает до двух байтов, то пустеет: каждое выражение кладёт на него операнды и тут же снимает. Посчитайте заодно, сколько работы уходит на одну строчку x = x + 1: LD, PUSH, LDI, PUSH, POP, POP, ADD, PUSH, POP, ST — десять команд, тринадцать байтов. Человек написал бы LD R0, [v_x], INC R0, ST R0, [v_x]: три команды, пять байтов. Компилятор переводит верно, но слово в слово.

Оптимизатор

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

Свёртка констант и мёртвый код

Начнём с промежуточного кода. Если на стек кладутся два числа, а за ними идёт действие, результат можно посчитать сразу, при компиляции: PUSH 2, PUSH 4, * заменяются одной PUSH 8. Это свёртка констант. То же с условием: если оба операнда сравнения известны, известен и исход. Условие, которое всегда ложно, превращает if в безусловный прыжок, а всё, что стоит после безусловного прыжка до ближайшей метки, не выполнится никогда. Такой код называют мёртвым, и его можно выбросить. Вот оптимизатор промежуточного кода — на программе, где есть и то и другое.

Двадцать семь команд стали восемнадцатью. 2 * 4 свернулось в 8, 8 - 1 - y — в 7 - y: выражение читается слева направо, (8 - 1) - y, и левую скобку можно посчитать заранее. А отладочная печать под if 1 == 0 исчезла вместе с условием. Так поступают и промышленные компиляторы: строчку if DEBUG: с ложной константой они вырезают из программы, и отладка в готовой программе не стоит ни такта. Свернуть x + 2 + 3 этот оптимизатор не сможет: там сначала x + 2, и двух чисел подряд на стеке не окажется. Компилятору пришлось бы переставить сложения, а это законно для сложения по модулю 256, но не для каждого действия.

Оптимизация глазком

Вторая оптимизация смотрит уже на готовый ассемблер — через узкое окошко в две-три соседние команды — и заменяет расточительные пары на экономные. В нашем коде сплошь и рядом идёт PUSH R0 и сразу POP R0: положить на стек и тут же снять. Пара ничего не делает, её можно выбросить. PUSH R0 и POP R1 заменяются одной MOV R1, R0. JMP L2 прямо перед меткой L2: — прыжок на следующую строку. Такую оптимизацию называют оптимизацией глазком (peephole). О программе в целом она ничего не знает, зато дешёвая и полезнее, чем кажется: генератор кода, переводя каждую команду отдельно, оставляет на стыках одни и те же следы.

Регистры вместо стека

Самое крупное расточительство глазок не исправит: все промежуточные значения у нас ходят через память. Стек в памяти — это PUSH и POP, по такту и байту на каждый. А у «Искры» четыре регистра, и почти всё время три из них простаивают. Генератор кода может держать вершину стека в регистрах: левый операнд — в R0, правый — в R1, а на стек откладывать значение, только когда правая часть выражения сама сложная и ей нужны оба регистра. Заодно он может выбирать команды поудачнее: x + 1 — это INC, а не LDI и ADD.

Во взрослых компиляторах это отдельная большая задача — распределение регистров. Переменных и промежуточных значений много, регистров мало — у x86-64 их шестнадцать общего назначения, у «Искры» четыре. Два значения, которые нужны в одно и то же время, не могут жить в одном регистре. Нарисуйте граф: вершины — значения, ребро — если они нужны одновременно. Раздать регистры — значит раскрасить вершины так, чтобы соседи получили разные цвета, а цветов не больше, чем регистров. Не хватило цветов — какое-то значение отправляется в память. Задача раскраски в общем случае трудная, как задачи из главы 58, поэтому компиляторы решают её приближённо, жадными способами.

Для Серпинского оптимизации сокращают код со 119 байт до 79, а работу — с 3210 тактов до 1744, почти вдвое. Свёртке здесь нечего делать — в программе нет выражений из одних чисел, — зато на программе «константы» она одна выбрасывает две пятых кода. И ни одна не изменила смысла: на экране тот же треугольник. Это первое правило оптимизатора. Но по исходнику не проверишь, соблюдает ли его компилятор: что сделает программа, в итоге решает он, — и через раздел мы увидим, чем это опасно.

Компилятор компилирует себя

Наш компилятор написан на Python. Скомпилировать сам себя он не может: в Огниве нет ни строк, ни списков, ни функций, а компилятору нужно всё это. Но у больших языков так бывает постоянно. Компилятор tcc из песочницы написан на C, компилятор Go с 2015 года — на Go, компилятор Rust — на Rust. Компилятор, написанный на том языке, который он переводит, называют самокомпилирующимся. Это родственник метациклического интерпретатора из прошлой главы, и он сразу задаёт загадку о курице и яйце: чем скомпилировать первую версию?

Выход называется раскруткой, по-английски bootstrapping: «подтянуть себя за ремешки ботинок». Первую версию пишут на другом языке или запускают в интерпретаторе. С Паскалем, например, было так: первую попытку написать его компилятор на Фортране в 1969 году бросили — Фортран плохо описывал сложные структуры данных. Вторую версию, по воспоминаниям Вирта, написали сразу на Паскале, для которого ещё не было компилятора, и один из авторов, Р. Шильд, две недели вручную переводил её на низкоуровневый язык машины CDC. Переведённая программа скомпилировала паскалевский текст, и дальше компилятор собирал себя сам. А в MIT в 1962 году Тим Харт и Майк Левин написали компилятор Лиспа на самом Лиспе и прогнали его в интерпретаторе, выросшем из eval Рассела. Интерпретатор выполнял компилятор, компилятор переводил в машинный код сам себя, и дальше интерпретатор был уже не нужен. Скомпилированная функция, по их оценке, работала примерно в сорок раз быстрее той же функции в интерпретаторе. Так ответ на вопрос, которым кончилась прошлая глава, нашёлся через три-четыре года после первого интерпретатора.

Компилятор GCC до сих пор собирается в три ступени. Сначала его исходники компилирует какой-нибудь уже установленный компилятор — получается первая ступень. Первая ступень компилирует те же исходники — получается вторая. Вторая компилирует их ещё раз — третья. Первая и вторая ступени — один и тот же компилятор, только собранный разными компиляторами, поэтому из одних и тех же исходников они должны получить одно и то же: вторая и третья ступени обязаны совпасть байт в байт; если не совпали, в компиляторе ошибка, и инструкция по сборке просит о ней сообщить. Проверка хорошая, но она лишь показывает, что компилятор согласен сам с собой. А честен ли он?

Доверие к доверию

Ту же атаку можно устроить на нашем компиляторе. Программа ниже — замок: читает код и открывает, если код верный. Компилятор с закладкой узнаёт сравнение с кодом и подмешивает в него второй, свой. Исходники компилятора и замка видны в карточках: следите, на каком шаге закладка в них есть, а на каком её уже нет.

Похожие атаки случались и на деле. В 2009 году антивирусная лаборатория Sophos нашла вирус Induc, который заражал не программы, а среду разработки Delphi: он подменял часть её стандартной библиотеки, и каждая программа, собранная заражённым Delphi, несла вирус дальше, хотя её исходники были чисты. В 2015 году поддельная копия среды разработки Apple Xcode, XcodeGhost, распространялась в Китае и встроила вредоносный код в приложения для iPhone, попавшие в App Store: сначала нашли несколько десятков таких приложений, а фирма FireEye насчитала больше четырёх тысяч. Ни один из этих случаев не повторял Томпсона в точности: заражённый компилятор не воспроизводил себя из чистых исходников. Но оба показали, что подменённый инструмент сборки заражает всё, что им собрано.

Раз проверить исходники недостаточно, защищаться приходится иначе. Американский исследователь безопасности Дэвид А. Уилер — однофамилец автора «прыжка Уилера» из главы 5 — в 2005 году описал и проверил на деле, развив идею Генри Спенсера, двойную компиляцию разными компиляторами. Исходники подозрительного компилятора собирают независимым компилятором, а получившейся программой — снова те же исходники. Если подозрительный компилятор действительно собран из этих исходников, результат обязан совпасть с ним байт в байт: обе сборки делают одно и то же, только разными руками. Закладка, которая есть в одном компиляторе и не может быть в другом, совпадение испортит. Другой ответ — воспроизводимые сборки: если любой человек, собрав программу из опубликованных исходников, получает те же байты, что разработчик, подменить их незаметно гораздо труднее. О закладках и о том, как их ищут, подробнее — в главе 61.

И здесь круг замыкается ещё раз. В главе 7 мы спросили, может ли программа напечатать саму себя, и ответили: да, если хранит шаблон своего текста и подставляет в него собственную запись. Томпсон показал тёмную сторону этого упражнения: программа, способная воспроизвести себя, способна воспроизвести себя вместе с чем угодно.

Переводить на ходу

Интерпретатор понимает программу каждый раз заново, компилятор — один раз заранее. Есть и третий путь, про который мы говорили в главе 33: JIT-компиляция, перевод во время работы. Исполнитель начинает как интерпретатор, считает, какие куски программы выполняются чаще всего, и только их переводит в машинный код — причём подстраивая под то, что увидел: если в этом цикле x всегда целое, можно выпустить машинную команду сложения целых и проверять тип один раз на входе. Так работают JavaScript в браузере, Java, PyPy. В Python 3.13 появился экспериментальный JIT, по умолчанию выключенный, — по технике «скопировать и залатать»: готовые заготовки машинного кода для каждой команды байт-кода склеиваются, а в дыры подставляются адреса и числа. Чем-то это похоже на наш генератор кода, который тоже склеивает готовые куски ассемблера, — только на ходу и прямо в память.

Как программа понимает программу

Три главы назад мы стояли в музее языков перед строчкой 2 + 3 * (4 - 1) и спрашивали, как машина в ней разбирается. Теперь у нас есть все части ответа.

Задачи

Три задачи — три куска своего компилятора: оптимизатор на дереве и генератор кода для выражений и для целых программ. Деревья в них те же, что строит front: число, имя-строка или кортеж (знак, левое, правое). Тесты собирают ваш ассемблер ассемблером «Искры» и запускают на её эмуляторе — так же, как ячейка «огниво.py».

Куда дальше

Круг замкнулся: программа на Огниве дошла до машины, которую вы собрали из вентилей. Всё, что лежит между вашей строчкой и проводами, теперь можно прочитать, а значит, и изменить.

Но вспомните, что делает check: проверяет, что у каждого имени есть значение, и больше ничего. В Огниве этого хватает, потому что значения там одного вида — байт. В Python видов много: числа, строки, списки, словари, и не всякое действие с ними имеет смысл. Компилятор Python об этом не заботится.

Строку умножить на словарь нельзя, но компилятор Python перевёл её в байт-код без единого вопроса: LOAD_CONST, BUILD_MAP, BINARY_OP *. Ошибка всплыла только при запуске, и случись эта строчка в редко выполняемой ветке программы — она всплыла бы у пользователя через месяц, ночью. Мы научились переводить программу до запуска. Можно ли до запуска и проверить её — найти, что строку собираются умножить на словарь, ещё не выполнив ни одной команды? Об этом — следующая глава, где на скамье подсудимых окажется самое опасное значение в программировании.