Оптимизация выражений (констант) в ПОЛИЗ (RPN)

Пишет digitalinvitro,

Не могли бы вы меня навести на алгоритм оптимизации выражений в ПОЛИЗ, существует ли таковой, особенно это касается свертки констант?

Дело в том что если константы разбросаны по исходному выражению то при симуляционном выполнении арифметического стека (самая простейшая оптимизация какую мне удалось найти), когда переменные откидываются, удается свернуть только следующие впереди переменных константы, завершающие выражение константы остаются не свернутыми. К сожалению не смог найти больше информации по ПОЛИЗу как по методу разбора и трансляции/компиляции выражений, а оптимизированный код для выражений хотелось бы иметь в арсенале. Шутка ли объемы простеньких программ для разработанной архитектуры процессора в силу отсутствия оптимизации легко выпрыгивают за 8 и 16 Кб кода, и немалый вклад в оверхед вносят в первую очередь выражения. Буду очень благодарен за развернутый ответ.

Forums: 

Изображение пользователя Serguei_Tarassov.

Уточнения

Пишет Serguei_Tarassov,

Вопрос интересный, но требует разных уточнений и примеров. Какая грамматика, какой метод разбора, каковы используемые стадии и что на выходе?

Например, рекурсивный спуск формирует синтаксическое дерево, соответствующее вызовам команд для RPN-ПОЛИЗ. Все константы попадают в соответствующую таблицу, исключающую дублирование, вызовы используют адреса констант. Должно получаться крайне компактно, как в Форте.

Думаю, будет проще, если описать какой-нибудь простой конкретный пример, вызывающий проблемы.

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

Выражение

v1 := (123 + 456) * 789

Синтаксическое дерево и таблицы (без оптимизации, текстовый формат)

Prog (Name: )
 
External libraries:
 
External routines:
 
Constants:
synSubTypeInt: $SYNSUBTYPEINT_123
synSubTypeInt: $SYNSUBTYPEINT_456
synSubTypeInt: $SYNSUBTYPEINT_789
 
Global vars:
 
== main ==
Local vars:
  V1
Labels:
 
synMainProc[1,1]: "v1" (synSubTypeNone)
    synStatement[1,1]: "v1" (synSubTypeNone)
        synStatementAssign[1,1]: "v1" (synSubTypeNone)
            synVarLocal[1,1]: "v1" (synSubTypeNone)
            synExpression[1,7]: "(" (synSubTypeNone)
                synAdditiveExpression[1,7]: "(" (synSubTypeNone)
                    synMultiplicativeExpression[1,7]: "(" (synSubTypeNone)
                        synUnaryExpression[1,7]: "(" (synSubTypeNone)
                            synPrimaryExpression[1,7]: "(" (synSubTypeNone)
                                synExpression[1,8]: "123" (synSubTypeInt)
                                    synAdditiveExpression[1,8]: "123" (synSubTypeInt)
                                        synMultiplicativeExpression[1,8]: "123" (synSubTypeInt)
                                            synUnaryExpression[1,8]: "123" (synSubTypeInt)
                                                synPrimaryExpression[1,8]: "123" (synSubTypeInt)
                                                    synConst[1,8]: "123" (synSubTypeInt)
                                        synAdditiveOpPlus[1,12]: "+" (synSubTypeNone)
                                        synAdditiveExpression[1,14]: "456" (synSubTypeInt)
                                            synMultiplicativeExpression[1,14]: "456" (synSubTypeInt)
                                                synUnaryExpression[1,14]: "456" (synSubTypeInt)
                                                    synPrimaryExpression[1,14]: "456" (synSubTypeInt)
                                                        synConst[1,14]: "456" (synSubTypeInt)
                        synMultiplicativeOpMult[1,19]: "*" (synSubTypeNone)
                        synMultiplicativeExpression[1,21]: "789" (synSubTypeInt)
                            synUnaryExpression[1,21]: "789" (synSubTypeInt)
                                synPrimaryExpression[1,21]: "789" (synSubTypeInt)
                                    synConst[1,21]: "789" (synSubTypeInt)

Исполняемый модуль (текстовый формат), умещается в несколько десятков байт

Code: 14
Addr     Mnemo Word      InstrT
00000000   VAL 00000000   5(0x05)
00000001 SETBP 00000000  31(0x1F)
00000002   VAL 00000000   5(0x05)
00000003  CALL 00000005   6(0x06)
00000004   END 00000000  32(0x20)
00000005 ENTER 00000010   8(0x08)
00000006  LOAD 00000001   1(0x01)
00000007  LOAD 00000002   1(0x01)
00000008   ADD 00000000  26(0x1A)
00000009  LOAD 00000003   1(0x01)
00000010  MULT 00000000  24(0x18)
00000011 LSTOR 00000009   4(0x04)
00000012 LEAVE 00000000   9(0x09)
00000013   RET 00000000  10(0x0A)
 
Data: 4
Addr     Type          Value
00000000   0(   Empty) 
00000001   3( Integer) 123
00000002   3( Integer) 456
00000003   3( Integer) 789
 
Symbols
 
System vars:
Addr     Name
00000000 RESULT
 
Global vars:
Addr     Name
 
Constants:
Addr     Name
00000001 123
00000002 456
00000003 789
 
Local vars:
main (00000005 - 00000013)
Addr     Name
00000000 I1
00000001 I2
00000002 I3
00000003 I4
00000004 I5
00000005 I6
00000006 I7
00000007 I8
00000008 I9
00000009 v1

ПОН и методы оптимизации

Пишет digitalinvitro,

Да, Сергей, думаю что Вы правы, начну с примера:

вот пример для идеального сворачивания констант

30*4  + 0xFF + 10 + t + (2*j - 3*90)/2 - (b - 100)*2

как видно все константы предшествуют членам выражения с переменным значением (переменным грубо говоря)

методом Дейкстры получаем это выражение в ПОН (Польская обратная нотация или ПОЛИЗ)

24: Constant value 30
23: Constant value 4
22: ( 8) Operate *
21: Constant value 255
20: ( 7) Operate +
19: Constant value 10
18: ( 7) Operate +
17: Local var t
16: ( 7) Operate +
15: Constant value 2
14: Global var j
13: (20) Operate *
12: Constant value 3
11: Constant value 90
10: (20) Operate *
9: (19) Operate -
8: Constant value 2
7: ( 8) Operate /
6: ( 7) Operate +
5: Global var b
4: Constant value 100
3: (19) Operate -
2: Constant value 2
1: ( 8) Operate *
0: ( 7) Operate -

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

после оптимизации записи ПОН(симулятицией вычисления)

   ;-------------------- aripmetic expression assembled -------------------	
   ; POLIZ stack, after optimize:	
   ;  385 lvar:t + 2 gvar:j * 270 - 2 / + gvar:b 100 - 2 * -	
   ;-----------------------------------------------------------------------

Хорошо видно что все константы свернулись в одну суммарную.

Берем не подготовленный к оптимизации таким способом пример:

 30*4  + 10 + t + (2*j - 3*90)/2 - (b - 100)*2 + 0xFF

Хорошо видно что за членами выражения с переменным значением располагается константа, а именно шестнадцатеричное 0xFF (255).

Разбор выражения в ПОН:

24: Constant value 30
23: Constant value 4
22: ( 8) Operate *
21: Constant value 10
20: ( 7) Operate +
19: Local var t
18: ( 7) Operate +
17: Constant value 2
16: Global var j
15: (20) Operate *
14: Constant value 3
13: Constant value 90
12: (20) Operate *
11: (19) Operate -
10: Constant value 2
9: ( 8) Operate /
8: ( 7) Operate +
7: Global var b
6: Constant value 100
5: (19) Operate -
4: Constant value 2
3: ( 8) Operate *
2: ( 7) Operate -
1: Constant value 255
0: ( 7) Operate +

после оптимизации записи ПОН(симуляцией вычисления)

   ;-------------------- aripmetic expression assembled -------------------	
   ; POLIZ stack, after optimize:	
   ;  130 lvar:t + 2 gvar:j * 270 - 2 / + gvar:b 100 - 2 * - 255 +	
   ;-----------------------------------------------------------------------

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

Изображение пользователя Serguei_Tarassov.

Теперь понятно

Пишет Serguei_Tarassov,

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

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

Вернемся к твоему примеру.

30*4 + 10 + t + (2*j - 3*90)/2 - (b - 100)*2 + 0xFF

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

"+"
 |--"-"
 |   |--"-"
 |   |   |--"+"
 |   |   |   |--"+"
 |   |   |   |   |--"*"
 |   |   |   |   |   |--"30"
 |   |   |   |   |   |--"4"   
 |   |   |   |   |  
 |   |   |   |   |--"10"
 |   |   |   |
 |   |   |   |--"t"
 |   |   |
 |   |   |--"/"
 |   |       |--"-"
 |   |       |   |--"*"
 |   |       |   |   |--"2"
 |   |       |   |   |--"j"
 |   |       |   |   
 |   |       |   |--"*"
 |   |       |       |--"3"
 |   |       |       |--"90"
 |   |       |
 |   |       |--"2"
 |   |        
 |   |--"*"
 |       |--"2"
 |       |--"-"
 |           |--"b"
 |           |--"100"
 |--"0xFF"

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

"+"
 |--"-"
 |   |--"-"
 |   |   |--"+"
 |   |   |   |--"130"
 |   |   |   |--"t"
 |   |   |
 |   |   |--"/"
 |   |       |--"-"
 |   |       |   |--"*"
 |   |       |   |   |--"2"
 |   |       |   |   |--"j"
 |   |       |   |   
 |   |       |   |--"270"
 |   |       |
 |   |       |--"2"
 |   |        
 |   |--"*"
 |       |--"2"
 |       |--"-"
 |           |--"b"
 |           |--"100"
 |--"0xFF"

Но это не предел. Теперь можно использовать дополнительную оптимизацию.
Обходим дерево "снизу", от листев к корню (на моей картинке это с самого правого верхнего узла).

Г1
  В1
    Б1
      А1
      А2
    Б2
  В2

1. если узел А1 - константа, то запоминаем узел, его операцию Б1 и поднимемся вверх
иначе переходим к следующему листу А2
2. если операция выше В1 имеет более низкий приоритет чем Б1, то выход
иначе смотрим второй узел Б2 операции В1 (первый - Б1)
3. если Б2 - константа, то проводим операцию Б1 с константой А1 и Б2, заменяем его значением Б2, удаляем узел А1, а Б1 заменяем на А2 (удалив Б1)
4. если Б2 - операция, имеет более высокий приоритет, то поднимаемся еще выше к Г1 и повторяем по п.1
иначе опускаемся по Б2 и смотрим его подузлы А4 и А5 по п.3

Прошу прощения за нестрогую формулировку алгоритма, над этим надо серёзно поработать, но, думаю, что идея понятна.

В итоге получится дерево вида

"+"
 |--"-"
 |   |--"-"
 |   |   |--"t"
 |   |   |--"/"
 |   |       |--"-"
 |   |       |   |--"*"
 |   |       |   |   |--"2"
 |   |       |   |   |--"j"
 |   |       |   |   
 |   |       |   |--"270"
 |   |       |
 |   |       |--"2"
 |   |        
 |   |--"*"
 |       |--"2"
 |       |--"-"
 |           |--"b"
 |           |--"100"
 |--"0xFF+130"

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

Понятно

Пишет digitalinvitro,

Да Сергей я кажется понял, то есть ПОЛИЗ как инструмент оптимизации ограничен и алгоритмы его полной оптимизации не разработаны. Необходим переход к синтаксическому дереву, а точнее рассмотрение выражения триплетами, что еще полнее сворачивать константы. В принципе я вижу путь преобразования ПОН в дерево триплетов, опять таки через использования стека, а именно имея готовый стек S0 и новый S1

Подымаем текущий элемент pop и проверяем его тип, если это ОПЕРАНД, опускаем push его в стек S1, если это ОПЕРАТОР, со стека S1 подымаем pop два элемента ОПЕРАНДА (а это будут именно ОПЕРАНДЫ при условии правильности ПОН) и подключаем в триплет, вместе с ОПЕРАТОРОМ. Получившийся триплет опускаем push в стек S1 (триплет тоже ОПЕРАНД). Прогоны вдоль стека повторяем пока не останется один единственный триплет.

Сергей что мне очень интересно, Дейкстра столп алгоритмики использовал ПОН, он должен был видеть его недостатки или тогда вопросы оптимизации мало кого заботили (хотя например и Вирт и Кнут озабачивались)? Хотя зная мощности тех вычислительных ресурсов наоборот должны были мобилизовывать на поиск преобразований ПОН. Мне кажется алгоритм поиска по синтаксическому дереву - должен транспонироваться на ПОН. Даже свой довесок к ПОН (такой как уровень операций) я считаю избыточным для него, с уровнем операций (когда в зависимости от прохождения скобок равные операции поднимаются на максимальный уровень приоритета) я вижу (пока еще не могу формализовать) алгоритм свертки ПОН триплетами до минимально возможного уровня операций, при котором возможно перемещение членов выражения со своим оператором вдоль стека до ближайшей константы с последующей сверткой. Но как я уже и говорил уровень операций - избыток для ПОН, ну мне так какжется вполне вероятно я и не прав. Так есть потенциал у ПОН или ПОН полностью исследована и заброшена алгоритмиками?

Обойти синтаксическое дерево

Пишет digitalinvitro,

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

Изображение пользователя Serguei_Tarassov.

Дерево и стек

Пишет Serguei_Tarassov,

Алексей, восстановить дерево выражения из стека без потери семантки в частном случае можно, если, например, зафисировать правила:
- только левое или только правое заполнение
- узлы - операции, листья - операнды (константы, переменные)

Значит привиденный алгоритм для дерева может быть реализован и на стеке. Просто мне было нагляднее в виде дерева представить логику работы. Без дерева это будет выглядеть, как перебор операндов, нахождение соответствующей ему операции и попытки переместить операнд выше или ниже по стеку без потери семантики (т.е. с учетом приоритетов). Мне кажется, что алгоритм будет сложный, сложнее "деревянного".

Алгоритм Дейкстры имеет вполне конкретную область применения - вычисление алгебраических выражений без синтаксического разбора. Это позволяет обойтись лексическим анализатором (токенайзером), который есть в стандартной библиотеке Си. Видимо, для простых задач вроде вычислений в командной строке этого было достаточно, а для более сложных создавался полноценный транслятор с внутренним представлением семантики, пригодным для глубокой оптимизации.

Т.о., если ты хочешь работать с деревом, то тебе нет смысла реализовывать алгоритм Дейкстры, нужно написать простенький синтаксический анализатор для грамматики выражений (или сгенерировать flex/bison по имеющимся в открытом доступе описаниям). Он будет сразу давать на выходе дерево или упомянутые тобой "тройки" (два операнда и операция).

Обход дерева, как правило, рекурсивный. Он проще в написании, но сложнее в отладке. Вот пример псевдокода для простой оптимизации свертки констант (стартовать надо с корня):

procedure OptimizeTree(CurrNode: TSynNode);
begin
  if CurrNode.Right = nil then Exit;
  if CurrNode.Right.NodeType <> synConst then
    OptimizeTree(CurrNode.Right);
  if CurrNode.Left = nil then Exit;
  if CurrNode.Left.NodeType <> synConst then
    OptimizeTree(CurrNode.Left);
  if (CurrNode.Right.NodeType = synConst) and
     (CurrNode.Left.NodeType = synConst) then
  begin
    CurrNode.Value := Calc(CurrNode, CurrNode.Right, CurrNode.Left);
    CurrNode.NodeType = synConst;
    CurrNode.DeleteRight;
    CurrNode.DeleteLeft;
  end
end;

Спасибо за науку

Пишет digitalinvitro,

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

Про flex/bison не то что бы я не знал про эти инструменты, знал конечно. Но если честно не умею пользоваться, это серьезные вещи и мне кажется я еще не дорос до такого уровня специализации.

Сергей а вот серьезные компиляторы, предположим icc или скажем тот же Watcom они умеют втаскивать константы под скобки, сокращать их, т.е. упрощать выражения на более высоком уровне?

Изображение пользователя Serguei_Tarassov.

Оптимизация

Пишет Serguei_Tarassov,

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

Конечно, flex/bison - это отдельный мир, непростой, поэтому для создания простых трансляторов его использование под вопросом. Да и не все языки укладываются в поддерживаемые ими грамматики.

По поводу продвинутых компиляторов, можно провести эксперимент с GCC.

Тестовый пример

#include <stdio.h>
int main()
{
  int t = 333;
  int b = 444;
  int j = 555;
  double a = 30 * 4 + 10 + t + (2 * j - 3 * 90) / 2 - (b - 100) * 2 + 255;
  printf("%f", a);
}

Генерируем ассемблерный код без оптимизации
 gcc -c -O0 -g -Wa,-a,-ad test01.c > test01.s

Смотрим сгенерированный ассемблер (файл test.s). В тексте можно увидеть константы "130" и "255". То есть даже без оптимизации, семантический анализатор сворачивает константы в дереве.

Первый уровень оптимизации:
 gcc -c -O1 -g -Wa,-a,-ad test01.c > test01.s

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

Чтобы избежать такой предусмотрительности, изменим исходник.

#include <stdio.h>
int main(int argc, char *argv[])
{
  int t = atoi(argv[1]);
  int b = atoi(argv[2]);
  int j = atoi(argv[3]);
  double a = 30 * 4 + 10 + t + (2 * j - 3 * 90) / 2 - (b - 100) * 2 + 255;
  printf("%f", a);
}

При генерации с уровнем оптимизации -O1 видны все те же константы "130", "255", что и без оптимизации, но появляется "-270".

При генерации с уровнем оптимизации -O3 видна "255", остальные, видимо, преобразованы другим способом.