Разработка компилятора. Оптимизатор

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

Оптимизатор — объект компилятора, выполняющий оптимизацию кода на уровне AST (абстрактного синтаксического дерева), сокращая либо преобразуя ноды AST, приводя тем самым к более быстрому исполнению кода.

Оптимизатор работает в многопроходном режиме, то есть запуск повторяется до тех пор, пока очередной запуск не внесет никаких изменений в AST.

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

1. Предрасчет статических выражений.

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

print(1*3+17);

Значение выражения 1*3+17 статично, это каждый раз 20. И каждый раз, машине требуется 5 операций, на то, чтобы это понять. Поможем ей?
Заменим выражение 1*3+17 на константу 20, теперь вместо 5 команд нужно выполнить всего одну!

2. Оптимизация блоков

Блок — набор инструкций, заключенных в фигурные скобки: {}. Используется в функциях, циклах, условиях.
На самом деле, здесь несколько разных оптимизаций, рассмотрим их:

2.1. Проверка используемости переменных

В каждом блоке могут объявляться локальные переменные, но при этом некоторые из них могут не использоваться. Было ли это ошибкой разработчика? Возможно. Поэтому неплохо бы ему об этом сообщить. Рассмотрим код:

var a = 5+9 * 3;
for(var i = 0; i < 1000000; i++)
{
	var a = b+c;
}
print(a);

В цикле происходит объявление переменной a, но ее значение нигде не используется. Сгенерируем предупреждение, и удалим эту переменную. В результате останется только это:

var a = 5+9 * 3;
for(var i = 0; i < 1000000; i++)
{
	b+c;
}
print(a);

Кто-то заметит, что выражение b+c; тоже ничего полезного не делает, и будет прав. На самом деле, его мы тоже удалим, только в другом проходе.

2.2. Проверка наличия новых переменных

Каждый блок — новый контекст. А контексты — это дорого. Подробнее о контекстах. Программисту блоки нужны, но не всегда нужны контексты. Чаще даже не нужны. В каких случаях можно не создавать контекст для блока? Если в нем не объявляется новых переменных, очевидно. Проверим все инструкции блока — если среди них нет ни одной для объявления новой переменной — значит опускаем контекст.

2.3. Удаление пустых блоков

Довольно очевидная оптимизация, просто уберем блок, если в нем ничего нет.

3. Удаление бесполезных выражений.

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

5+9 * 3;
for(var i = 0; i < 1000000; i++)
{
	b+c;
	b+runSomethind();
}
print(a);

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

for(var i = 0; i < 1000000; i++)
{
	b+runSomethind();
}
print(a);

Почему мы оставили b+runSomethind();? Потому, что здесь имеется вызов функции. Сейчас мы не можем быть уверены, что он не несет побочных эффектов, поэтому и удалить вызов нельзя.

4. Проверка константности условий.

Маловероятно, но все же, в условных выражениях могут встречаться константы.

if(1+3-4)
{
	doAlotOfWork();
}
else
{
	done() + asd();
}

В таком случае, исключаем само условие, и ложную ветвь:

done() + asd();

И конечно же генерируем предупреждение о недоступности ветви с doAlotOfWork();

Заключение:

Здесь рассмотрены далеко не все возможные оптимизации, это самые простые и/или очевидные. И именно они применяются в s4g версии 0.9.2. Другие я сделать не успелsmile В одной из следующих статей мы рассмотрим более сложные оптимизации, которые могут быть применимы в большем числе случаев.

Оптимизатор это не так уж и сложно))

Поделиться:

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

*