В настоящее время я пишу компилятор ECMAScipt5, который выполняет различные данные оптимизации/преобразования в дереве синтаксического анализа и компилируется обратно в ECMAScipt5.
Одна функциональность - переименовать привязку в EnvironmentRecord.
Это преобразование может быть выполнено автоматически, например. как часть оптимизации, целью которой является уменьшение размера кода, когда каждой переменной (не в глобальной области) будет присвоено следующее кратчайшее доступное имя или вручную путем аннотации после инструкции, которая вводит новую область.
Однако я должен ограничивать (автоматический) процесс только объявлениями переменных.
Рассмотрим эти два примера. Первый, скомпилированный, определяющий трансформации [Minify], второй с использованием [Directives, PrettyPrint]
Синтаксис: Compiler.fromSource (src).compile ([/*Array of transformations*/]);
var bar,foo;
(function exampleMin () {
var bar="foo",
foo="bar";
function fooBar () {
return foo + bar;
}
})
компилируется в
var bar,foo;function exampleMin(){var A="foo",B="bar";function fooBar(){return B+A}}
и
var bar,foo;
(function exampleMin () {
@Rename bar:A
@Rename foo:B
@Rename fooBar:C
var bar="foo",
foo="bar";
function fooBar () {
return foo + bar;
}
})
компилируется в
var bar,foo;
function exampleMin(){
var A="foo",B="bar";
function C(){
return B+A;
}
};
Что приводит к проблематичной части, функции... рассмотрим следующее
if (fooBar.name === 'fooBar') {
//...
}
Теперь, если это утверждение будет содержаться в exampleMin. Определенное пользователем переименование преобразует код в семантически другой код. Что никогда не должно происходить при автоматическом преобразовании.
В то время как я вслепую предполагаю, что пользовательское переименование функций не изменяет семантику каким-либо образом, я хотел бы создать предупреждение, если это может быть так. Но я не знаю , как определить, безопасно ли переименовать функцию программно или нет.
Это сводит меня к вопросам:
- Что, помимо доступа к имени функции, необходимо учитывать при переименовании функции?
- Какой анализ необходимо выполнить, чтобы отметить функцию как безопасную оптимизацию или нет. Возможно ли это вообще.
- Я бы предпочел исключить переименование функций или попытаться изменить другую сторону, например. сравнение с именем функции. (Если можно доказать отсутствие побочных эффектов)
- Может ли изменение в семантике быть допустимым в таком конкретном случае (GCC, кажется, так думает), если я, взамен, предложить аннотацию
@do-not-optimize?
Обновление 1.
Я пришел к выводу, что этот анализ может быть возможен не только посредством статического анализа
Рассмотрим следующий код.
function foo () {}
function bar () {}
var fns = [bar,foo];
if (fns [0].name === 'bar') fns [0] ();
fns.unshift (foo);
if (fns [1].name === 'bar') fns [1] ();
Я не могу себе представить, как отслеживать ссылки назад к нему, как только функция была добавлена в массив, без выполнения кода. Может быть, мне понадобится какая-то форма абстракции Интерпретация 1?
Обновление2
В среднем и после чтения @Genes ответ, я понял, что есть и другие вещи, которые, возможно, не помешают добавить. Во-первых, некоторые примечания:
- По-видимому, я не пишу компилятор, а скорее препроцессор, так как он выводит исходный код, а не машинный код.
- Учитывая, что будут только статические обращения связанных идентификаторов, у меня есть хорошая идея о том, как подойти к проблеме.
- Каждое связывание в каждой записи среды в настоящее время содержит список всех его статических ссылок (я, очевидно, не мог добавить динамические)
В настоящее время я работаю над преобразованием SSA [2]. Таким образом, я еще не реализовал анализ DataFlow. Но это по плану.
Таким образом, для простоты предположим, что будут выполнены следующие предпосылки.
- AST и CFG находятся в форме статического одиночного присваивания.
- Множества GEN и KILL были рассчитаны для каждого node в CFG 4
- Достигнуты определения 4/IN и OUT наборы.
- Вычислены пары DEF/USE.
-
границы потока реакции были добавлены в CFG
Итак, график потока управления для первого примера может выглядеть примерно так.
- Черные, не пунктирные линии представляют собой границы потока управления.
- Черные пунктирные соединения представляют зависимости потока данных
- Синие линии двойной стрелки представляют собой сайты вызовов.
- Синие пунктирные линии представляют межпроцедурные зависимости. Я, однако, не уверен, что я должен сделать прямое соединение между соответствующими узлами каждого из предшествующих CFG
Учитывая это, я мог бы просто выполнить следующее.
Для каждой функции, которая должна быть переименована:
- Посетите его объявления CFG node
- Для каждого края зависимости потока обратитесь к целевому объекту node
- Если это node является условным оператором goto, а ссылкой на функции является LHS атрибута доступа к ресурсам, а RHS - "имя".
- Отметить функцию как испорченную
Единственная проблема - Я не могу понять, как вычислить (даже приблизительную) эту информацию для нестатических ссылок функции.
Су, если этот анализ не поможет найти ссылки ALL на функцию, я мог бы также использовать предыдущий список ссылок, чтобы каждая привязка была записана в среде. Так как функция имеет декларативную запись среды , а также запись окружения объекта. Я мог бы просто взглянуть на счет ссылок на его объектные среды "name" Binding.
В качестве справочного материала приведен фактический код, который в настоящее время выполняет переименование
var boundIdentifiers = this.environment.record.bindings, //`this` refers to an AST node representing a FunctionDeclaration or a FunctionExpression
nextName,
identifier,
binding;
for (identifier in boundIdentifiers) {
binding = boundIdentifiers [identifier];
if (binding.uses < 2 && !binding.FunctionExpression) {
compiler.pushWarning (binding.references [0].line, binding.references [0].column,'Declared function ' + identifier + ' is never called.') //False positive if the functions reference is obtained dynamically
}
if (boundIdentifiers [identifier].FunctionDeclaration || boundIdentifiers [identifier].FunctionExpression) {
continue; //Skip function declarations and expressions, since their name property could be accessed
}
do {
nextName = nextVar ();
} while (
Object.hasOwnProperty.call (boundIdentifiers,nextVar) //There could exist a `hasOwnProperty` binding.
); //ther could a with the name that already exists in the scope. So make sure we have assign a free name.
this.environment.record.setBindingName (identifier, nextName);
}
Таким образом, общая проблема сводится к поиску нестатических ссылок
Какие методы анализа и предварительная оптимизация должны быть задействованы, чтобы поймать хотя бы некоторые (поскольку их невозможно поймать все), нестатические ссылки.
Я изменил вопросы, чтобы они соответствовали обновлению. Таким образом, вышеупомянутые вопросы по-прежнему применяются
[1] Обзор методов статистического анализа программ (CH: 2) [2] Статическая одиночная книга назначения [4] Представление и анализ программного обеспечения
Как упоминалось в комментариях @didierc, эта же проблема возникает для доступа к свойствам с использованием нотации скобок. Таким образом, привязка записи объектной среды может быть переименована только вручную.
