Оптимизация в языках программирования

от
Java    оптимизация, video, ownlang, парсер
Продолжая тему создания своего языка программирования, я решил рассказать об оптимизации.

С последнего 14-го урока в предыдущей серии, язык OwnLang заметно улучшился, поэтому для начала я предлагаю ознакомиться с изменениями.


Все оптимизации делаются после парсинга, в момент, когда у нас уже сформировано дерево AST. Дальше нам поможет Visitor, с его помощью удобно обходить дерево и заменять узлы.
OptimizationVisitor - базовый класс, который может заменить один узел (Statement или Expression) на другой, либо удалить его. Классы всех остальных оптимизаций будут унаследованы от этого OptimizationVisitor, что позволит больше не задумываться о том, как заменить узел. Достаточно лишь возвратить новый объект и базовый класс заменит узел.


Свёртка констант (Constant Folding)
Эта оптимизация заменяет выражения, которые можно посчитать на этапе компиляции. Наприимер, x = 2 + -3 - y можно заменить на x = -1 - y



В момент обхода выражения, мы должны проверить, что оно содержит константу. В нашем случае это ValueExpression. Если, к примеру, в BinaryExpression будут две константы и, допустим, операция сложения, мы сможем посчитать выражение ещё до запуска программы. Реализуется это так:
  1. @Override
  2. public Node visit(BinaryExpression s) {
  3.     if ( (s.expr1 instanceof ValueExpression) && (s.expr2 instanceof ValueExpression) ) {
  4.         return new ValueExpression(s.eval());
  5.     }
  6.     return super.visit(s);
  7. }
  8.  
  9. @Override
  10. public Node visit(UnaryExpression s) {
  11.     if (s.expr1 instanceof ValueExpression) {
  12.         return new ValueExpression(s.eval());
  13.     }
  14.     return super.visit(s);
  15. }

Таким образом, выражение x = 2 + -3 - y на первом проходе заменит унарную операцию "минус" от числа 3 на константное значение -3, а на втором проходе посчитает сумму 2 + -3.
constant_folding.gif

ConstantFolding.java


Распространение констант (Constant Propagation)
Эта оптимизация подставляет вместо констант их значения.
  1. x = 5
  2. y = 2 * x - 8
Поскольку x имеет константное значение 5, мы можем подставить его во второе выражение:
  1. x = 5
  2. y = 2 * 5 - 8
Дальше Constant Folding посчитает выражение и мы получим
  1. x = 5
  2. y = 2



  Здесь нужно сначала собрать статистику о переменных, чтобы определить, какие из них имеют значения и больше нигде не изменяются. Этим занимается отдельный Visitor VariablesGrabber. После его прохода мы получаем Map<String, VariableInfo>, где String - имя переменной, а в VariableInfo хранится значение, если его удалось посчитать до запуска программы, и количество модификаций.

Теперь, отобрав константы из статистики о переменных:
  1. final Map<String, Value> candidates = new HashMap<>();
  2. for (Map.Entry<String, VariableInfo> e : variables.entrySet()) {
  3.     final VariableInfo info = e.getValue();
  4.     if (info.modifications != 1) continue;
  5.     if (info.value == null) continue;
  6.     switch (info.value.type()) {
  7.         case Types.NUMBER:
  8.         case Types.STRING:
  9.             candidates.put(e.getKey(), info.value);
  10.             break;
  11.     }
  12. }
мы можем заменить VariableExpression на ValueExpression:
  1. @Override
  2. public Node visit(VariableExpression s, Map<String, Value> t) {
  3.     if (t.containsKey(s.name)) {
  4.         return new ValueExpression(t.get(s.name));
  5.     }
  6.     return super.visit(s, t);
  7. }

ConstantPropagation.java


Удаление мёртвого кода (Dead Code Elimination)
После внедрения констант, может случиться так, что у нас остались неиспользуемые присваивания, либо какие-то другие ненужные выражения, убрав которые, мы не затронем результат программы. Dead code elimination как раз это и делает. Например:
  1. x = 2 + 1
  2. if (x > 0) {
  3.     run()
  4. } else {
  5.     exit()
  6. }
После свёрки и внедрения констант мы получим такую программу:
  1. x = 3
  2. if (true) {
  3.     run()
  4. } else {
  5.     exit()
  6. }
Здесь можно с уверенностью сказать, что функция run() выполнится, а exit() нет. И присваивание нам тоже больше не понадобится. В результате мы получим лишь:
  1. run()



В случае с IfStatement мы должны посмотреть, является ли его условие константным. Если да и это true, то можно заменить if содержимое его ветки, если false, тогда либо заменяем на содержимое ветки else, либо, если else нет, полностью удаляем if.

  1. @Override
  2. public Node visit(IfStatement s, Map<String, VariableInfo> t) {
  3.     if (isValue(s.expression)) {
  4.         ifStatementEliminatedCount++;
  5.         // true statement
  6.         if (s.expression.eval().asInt() != 0) {
  7.             return s.ifStatement;
  8.         }
  9.         // false statement
  10.         if (s.elseStatement != null) {
  11.             return s.elseStatement;
  12.         }
  13.         return new ExprStatement(s.expression);
  14.     }
  15.     return super.visit(s, t);
  16. }

Аналогично с тернарными операторами и циклами.

Чтобы удалить присваивание, нужно заменить его на то значение, которое было уже посчитано. Потому что может быть такой случай:
  1. x = y = z = 10
Здесь нужно заменить "z = 10" на "10", тогда x и y правильно проинициализируются:
  1. x = y = 10
Для этого снова понадобится VariablesGrabber, чтобы узнать, какие переменные используются один раз — при присваивании.
  1. @Override
  2. public Node visit(AssignmentExpression s, Map<String, VariableInfo> t) {
  3.     if (!isVariable((Node)s.target)) return super.visit(s, t);
  4.  
  5.     final String variableName = ((VariableExpression) s.target).name;
  6.     if (!t.containsKey(variableName)) return super.visit(s, t);
  7.  
  8.     final VariableInfo info = t.get(((VariableExpression) s.target).name);
  9.     if (info.modifications != 1 || info.value == null) {
  10.         return super.visit(s, t);
  11.     }
  12.  
  13.     switch (info.value.type()) {
  14.         case Types.NUMBER:
  15.         case Types.STRING:
  16.             assignmentExpressionEliminatedCount++;
  17.             return new ValueExpression(info.value);
  18.         default:
  19.             return super.visit(s, t);
  20.     }
  21. }

DeadCodeElimination.java


Упрощение выражений (Expression Simplification)
Эта оптимизация заменяет выражения на аналогичные, но более эффективные.
Например: x = y / -1 можно заменить на x = -y



Теперь не обязательно, чтобы все выражения в рассматриваемом блоке были посчитаны. К примеру, имея выражение "x = sin(x) * 0", нам не важно ни значение x, ни результат вызова функции sin, мы видим, что один из аргументов - ноль, а операция - умножение. Это значит, что результат безусловно будет нулём.

  1. @Override
  2. public Node visit(BinaryExpression s, Void t) {
  3.     // operations with 0
  4.     final boolean expr1IsZero = isIntegerValue(s.expr1, 0);
  5.     if (expr1IsZero || isIntegerValue(s.expr2, 0)) {
  6.         switch (s.operation) {
  7.             case SUBTRACT:
  8.                 if (expr1IsZero) {
  9.                     // 0 - x2 to -x2
  10.                     return new UnaryExpression(UnaryExpression.Operator.NEGATE, s.expr2);
  11.                 }
  12.                 // x1 - 0 to x1
  13.                 return s.expr1;
  14.  
  15.             case MULTIPLY:
  16.                 // 0 * x2 to 0, x1 * 0 to 0
  17.                 return new ValueExpression(0);
  18.         }
  19.     }
  20.  
  21.     // x1 / 1 to x1
  22.     if (isIntegerValue(s.expr2, 1) && s.operation == BinaryExpression.Operator.DIVIDE) {
  23.         return s.expr1;
  24.     }
  25.  
  26.     // x - x to 0
  27.     if (isSameVariables(s.expr1, s.expr2) && s.operation == BinaryExpression.Operator.SUBTRACT) {
  28.         simplificationsCount++;
  29.         return new ValueExpression(0);
  30.     }
  31.  
  32.     return super.visit(s, t);
  33. }
В этом примере я показал лишь замену в таких случаях:
  - вычитание выражения от нуля (равносильно отрицанию выражения),
  - вычитание нуля от выражения (равносильно самому выражению, ноль не играет роли),
  - деление выражения на единицу (равносильно самому выражению),
  - вычитание выражения из выражение (равносильно нулю).
В классе ExpressionSimplification.java замен гораздо больше.


Объединение инструкций (Instruction Combining)
Если в программе подряд идут несколько операторов, к примеру print:
  1. print 3
  2. println "test"
  3. print "1212"
Тогда можно их объединить в один:
  1. print "3test\n1212"



Здесь нужно просматривать сразу по два Statement, чтобы узнать можно ли их объединить.
Если первый и второй операторы это print:
  1. if ((n1 instanceof PrintStatement) && (n2 instanceof PrintStatement)) {
  2. }
И их значения уже известны до запуска программы:
  1. final Expression e1 = ((PrintStatement) n1).expression;
  2. final Expression e2 = ((PrintStatement) n2).expression;
  3. if (isConstantValue(e1) && isConstantValue(e2)) {
  4. }
Тогда мы можем эти значения объединить (так как это строки, то операцией будет конкатенация) и создать новый PrintStatement, куда положим результат:
  1. return new PrintStatement(new ValueExpression(s1 + s2));

Здесь я привёл лишь случай с print, но в исходнике InstructionCombining.java есть полный пример обработки print и println.


Попробовать, как справляется оптимизация можно в ПК версии OwnLang, запустив программу с ключом "-o 9", либо в OwnLang Android Pro
:strela: Плейлист с уроками про оптимизацию
:strela: Классы, отвечающие за оптимизацию (GitHub)
  • +6
  • views 4419
    • Java
    Категории