Высокоуровневая /семантическая оптимизация

Question

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

То, что я искал в последнее время, - это меньше оптимизации кода и больше семантической / высокоуровневой оптимизации.Например:

free(malloc(400)); // should be completely optimized away

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

Другой пример:

string Parenthesize(string str) {
    StringBuilder b; // similar to C#'s class of the same name
    foreach(str : ["(", str, ")"])
        b.Append(str);
    return b.Render();
}

В этой ситуации я бы хотел иметь возможность инициализировать bспособность к str.Length + 2 (достаточно, чтобы точно сохранить результат, не тратя впустую память).

Если быть до конца честным, я понятия не имею, с чего начать в решении этой проблемы, поэтому я надеялся с чего-нибудь начать.Была ли проделана какая-либо работа в аналогичных областях?Существуют ли какие-либо компиляторы, которые реализовали что-либо подобное в общем смысле?

Answer 1

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

Ваш бесплатный (malloc(400)) возможен, потому что free и malloc являются обратными значениями в домене распределения хранилища.Множество операций имеют обратные значения и обучают компилятор тому, что они являются обратными, и демонстрируют, что результаты одного потока данных безоговорочно переходят в другой, это то, что необходимо.Вы должны убедиться, что ваши инверсии действительно являются инверсиями и где-то нет сюрприза;a / x * x выглядит как просто значение a, но если x равно нулю, вы получаете ловушку.Если вас не волнует ловушка, это обратная;если вы действительно заботитесь о ловушке, то оптимизация является более сложной:(if (x==0) then trap() else a) что по-прежнему является хорошей оптимизацией, если вы считаете, что divide стоит дорого.

Возможны и другие "алгебраические" соотношения.Например, существуют могут быть идемпотентные операции:обнуление переменной (многократная установка чего-либо в одно и то же значение) и т.д.Существуют операции, в которых один операнд действует как элемент идентификатора;X+0 ==> X для любого 0.Если X и 0 являются матрицами, это все еще верно и дает большую экономию времени.

Другие оптимизации могут произойти, когда вы можете абстрактно рассуждать о том, что делает код ."Абстрактная интерпретация" - это набор методов для рассуждения о значениях путем классификации результатов по различным интересным ячейкам (например, это целое число неизвестно, равно нулю, отрицательно или положительно).Чтобы сделать это, вам нужно решить, какие ячейки полезны, а затем вычислить абстрактное значение в каждой точке.Это полезно когда есть тесты для категорий (например, "если (x<0) { ..." и вы знаете абстрактно, что x меньше нуля;вы можете их оптимизировать, избавившись от условности.

Другой способ - символически определить, что делает вычисление, и смоделировать вычисление, чтобы увидеть результат.Именно так вы вычислили эффективный размер требуемого буфера;вы символически вычислили размер буфера перед запуском цикла, и смоделировали эффект выполнения цикла для всех итераций.Для этого вам нужно уметь создавать символьные формулы представляющие свойства программы, составлять такие формулы и часто упрощать такие формулы, когда они становятся непригодно сложными (своего рода переход к абстракции схема интерпретации).Вы также хотите, чтобы такое символьное вычисление учитывало алгебраические свойства, которые я описал выше.Инструменты, которые хорошо справляются с этим, хороши в построении формул, и системы преобразования программ часто являются хорошей основой для этого.Одна система преобразования программы от источника к источнику, которая может быть использована для этого является Инструментарий для Реинжиниринга программного обеспечения DMS.

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

Answer 2

В Бродвей фреймворк может быть в духе того, что вы ищете.Статьи на тему "преобразование от источника к источнику", вероятно, также будут поучительными.