Инкрементная компиляция программных трасс

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

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

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

А что, если памяти мало и компилять нужно быстро? Можно оторвать компилятору конечности и со всех сторон его урезать. Но можно поступить лучше. Очевидно, обычно самые узкие места - не очень большие внутренние циклы. Некто проф. М.Франц такие циклы инкрементно обнаруживает и по мере обнаружения компиляет. Компилируемые конструкции ограничены деревяхами, начинающимися с заголовка цикла, листья которых заканчиваются либо циклическим переходом к корню деревяхи, либо выходом в интерпретатор. В интерпретатор, впрочем, можно вываливаться где угодно.

Другие циклические переходы запрещены. Склейки запрещены, но дублирование кода разрешено.

Границы программных единиц (функций, процедур и проч) игнорируются. После этого рекурсия  становится родом цикла, возможно, с нетривиальным стековым эффектом.

Поскольку класс компилируемых конструкций сильно ограничен, для их качественной трансляции не нужно умного компилятора.

Подлежащие компиляции циклы обнаруживаются путем трассировки программ. Заголовки циклов инструментируются для начала генерации трассы. Длина трассы ограничена. Существующие трассы хранятся в словарике обычным префиксным способом, там же лежит ссылка на скомпилированный код.

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