Пособие по практике программирования

         

Компиляция "на лету"

В предыдущем разделе мы говорили о программах, которые пишут программы. В каждом примере программы генерировались в виде исходного ада и, стало быть, для запуска должны были быть скомпилированы или нтерпретированы. Однако возможно сгенерировать код, который можно шускать сразу, создавая машинные инструкции, а не исходный текст, акой процесс известен как компиляция "налету" (on the fly) или "как раз :вовремя" (just in time); первый термин появился раньше, однако последний — включая его акроним JIT — более популярен.

Очевидно, что скомпилированный код по определению получается епереносимым — его можно запустить только на конкретном типе процессора, зато он может получиться весьма скоростным. Рассмотрим такое выражение:

max (b, c/2)

Здесь нужно вычислить с, поделить его на 2, сравнить результат с b и вы-рать большее из значений. Если мы будем вычислять это выражение, используя виртуальную машину, которую мы в общих чертах описали в начале этой главы, то хотелось бы избежать проверки деления на ноль в divop: поскольку 2 никогда не. будет нулем, такая проверка попросту бессмысленна. Однако




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

Вот здесь-то нам и может помочь динамическая генерация кода. Если мы будем создавать непосредственно код для выражения, а не использовать предопределенные операции, мы сможем исключить проверку деления на ноль для делителей, которые заведомо отличны от нуля. На самом деле мы можем пойти еще дальше: если все выражение является константой, как, например, тах(3*3, 2/2), мы можем вычислить его единожды, при генерации кода, и заменять константой-значением, в данном случае числом 9. Если такое выражение используется в цикле, то мы экономим время на его вычисление при каждом проходе цикла. При достаточно большом числе повторений цикла мы с лихвой окупим время, потраченное на дополнительный разбор выражения при генерации кода.

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



Однако, когда мы генерируем код для конкретного шаблона, значение этого literal фиксировано, например ' х ' , так что мы можем вместо показанного выше сравнения использовать оператор вроде следующего:



И затем, вместо того чтобы предварительно определять специальный оператор для значения каждого символа-литеры, мы можем поступить проще: генерировать код для операторов, которые нам будут действительно нужны для данного выражения. Применив эту идею для полного набора операторов, мы можем написать JlT-компилятор, который будет анслировать заданное регулярное выражение в специальный код, оп-мизированный именно под это выражение.

Кен Томпсон (Ken Thompson) именно это и сделал в 1967 году для реализации регулярных выражений на машине IBM 7094. Его версия генерировала в двоичном коде небольшие блоки команд этой машины для разных операторов выражения, сшивала их вместе и затем запускала шучившуюся программу, просто вызвав ее, совсем как обычную функцию. Схожие технологии можно применить для создания специфических юледовательностей команд для обновлений экрана в графических системах, где может быть так много различных случаев, что гораздо более эффективно создавать динамический код для каждого из них, чем расписать с все заранее или включить сложные проверки в более общем коде.

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

Итак, вспомним, в каком виде мы оставили нашу виртуальную маши-у, — структура ее выглядела примерно так:



Для того чтобы адаптировать этот код для JIT-компиляции, в него [адо внести некоторые изменения. Во-первых, массив code будет теперь» re массивом указателей на функции, а массивом исполняемых команд.

Будут ли эти команды иметь тип char, int или long — зависит только от того процессора, под который мы компилируем; предположим, что это будет int. После того как код будет сгенерирован, мы вызываем его как функцию. Никакого виртуального счетчика команд программы в новом коде не будет, поскольку обход кода за нас теперь будет выполнять собственно исполнительный цикл процессора; по окончании вычисления результат будет возвращаться — совсем как в обычной функции. Далее, мы можем выбрать — поддерживать ли нам отдельный стек операндов для нашей машины или воспользоваться стеком самого процессора. У каждого из этих вариантов есть свои преимущества; мы решили остаться верными отдельному стеку и сконцентрироваться на деталях самого кода. Теперь реализация выглядит таким образом:



После того как generate завершит работу, gen return вставит команды, которые обусловят передачу управления от сгенерированного кода к eval.

Функция f lushcaches отвечает за шаги, необходимые для подготовки процессора к запуску свежесозданного кода. Современные машины работают быстро, в частности благодаря наличию кэшей для команд и данных, а также конвейеров (pipeline), которые отвечают за выполнение сразу нескольких подряд идущих команд. Эти кэши и конвейеры исходят из предположения, что код не изменяется; если же мы генерируем этот код непосредственно перед запкуском, топроцессор может оказаться в затруднении: ему нужно обязательно очистить свой конвейер и кэши для исполнения новых команд. Эти операции очень сильно зависят от энкретного компьютера, и, соответственно, реализация f lushcaches будет в каждом случае совершенно уникальной.

Замечательное выражение (void (*)(void)) code преобразует адрес :ассива, содержащего сгенерированные команды, в указатель на функцию, который можно было бы использовать для вызова нашего кода.

Технически не так трудно сгенерировать сам код, однако, конечно, для ого чтобы сделать это эффективно, придется позаниматься инженерной .еятельностью. Начнем с некоторых строительных блоков. Как и раньше, [ассив code и индекс внутри него заполняются во время компиляции. Для [ростоты мы повторим свой старый прием — сделаем их оба глобальными. Затем мы можем написать функцию для записи команд:



Сами команды могут определяться макросами, зависящими от процессора, или небольшими функциями, которые собирали бы код, заполняя поля в командном слове инструкции. Гипотетически мы могли бы завести функцию pop reg, которая бы генерировала код для выталкивания значения из стека и сохраняла его в регистре процессора, и функцию push reg, которая бы генерировала код для получения значения, хранящегося в регистре процессора, и заталкивания его в стек. Наша обновленная функция addop будет использовать некие их аналоги, применяя некоторые предопределенные константы, описывающие команды (вроде ADDINST) и их расположение (различные позиции сдвигов SHIFT, которые определяют формат командного слова):




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

Теперешняя реализация функции generate выглядит весьма похоже на реализацию виртуальной машины, но на этот раз она задает реальные машинные команды вместо указателей на предопределенные функции. Чтобы генерировать более эффективный код, следовало бы потратить усилия на избавление от лишних констант и другие виды оптимизации.

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

Между регулярным выражением и программой на C++ есть, конечно, немалая разница, но суть у них одна — это всего лишь нотации для решения проблем. При правильной нотации многие проблемы становятся гораздо более простыми. А проектирование и реализация выбранной нотации может дать массу удовольствия.

Упражнение 9-18

JIT-компилятор сгенерирует более быстрый код, если сможет заменить выражения, содержащие только константы, такие как тах(3*3, 4/2), их значением. Опознав такое выражение, как он должен вычислять его значение?

Упражнение 9-19

Как бы вы тестировали JIT-компилятор?


Содержание раздела