Каким должен быть язык программирования? Анализ и критика Описание языка Компилятор
Отечественные разработки Cтатьи на компьютерные темы Компьютерный юмор Прочее

О реализации метода оптимизации при компиляции

Введение

Введение

            Существует множество методов оптимизации при компиляции с языков высокого уровня [1]. Иногда сама форма записи операторов в языке, например X+=2; вместо X=X+2; (где X целая переменная) прямо показывает компилятору способ, которым он может улучшить реализацию, т.к. явно указывается, что результат сложения помещается на место операнда. Вполне вероятно, что тогда компилятор в первом случае приведенного примера сгенерирует команду IA-32 вида:
ADD X,2
а во втором, более общем случае, команды вида:
MOV EAX,X
ADD EAX,2
MOV X,EAX
поскольку для того, чтобы свести второй случай к первому необходимо провести дополнительный анализ программы. Далее рассматривается метод, позволяющий провести такой дополнительный анализ с целью поиска особых случаев и генерации для них более эффективных команд. Этот метод реализован в компиляторе с языка PL/1 для персонального компьютера [2], разработанном американским специалистом Гарри Килдэллом (Gary Kildall).

Представление программы на промежуточном языке

            Анализ оператора присваивания X=X+2; указанным компилятором PL/1 и перевод его во внутреннее представление (в обратную польскую запись) даст результат вида:
 1  2 3 4  5 6
IID 0 N 1 00 X
IID 0 N 1 00 X
ILD 1 N 0 31
C4  0 N 0 00 #2
ILD 1 N 0 02
IAD 2 B 0 31
IAS 2 S 0 31
            Здесь приведены операции и операнды внутреннего представления. В данном случае операции и операнды — понятия, переходящие друг в друга: результат операции сам может быть операндом операции, стоящей выше в иерархии.

            В первой колонке приведены аббревиатуры внутренних операций (первая буква I означает работу с объектами целого типа), во второй колонке — число операндов у каждой операции, в третьей колонке — тип каждой операции: N-обычная, B-коммутативная, S-запоминание, в четвертой колонке указан признак наличия объекта в таблице компилятора (т.е. имеет ли объект адрес памяти). В пятой колонке указан размер объекта в битах. Наконец в шестой, последней колонке, приводится ссылка на объект в таблице компилятора или непосредственное значение для констант: т.е. ссылка на переменную X и значение константы 2.

            Это внутреннее представление отражает то, что оператор присваивания (операция IAS) должен записать по адресу X (самая верхняя операция именования IID) свой второй операнд, в данном случае результат сложения (операция IAD). В свою очередь, результат сложения получается из двух операций загрузки ILD, каждая из которых имеет один свой операнд — ссылку на объект IID и на 2-х битную константу C4. Операция сложения имеет признак коммутативности, т.е. ее операнды могут идти в любом порядке, не влияя на результат.

Перестановка операндов для упрощения анализа

            С целью упрощения анализа для коммутативных операций проводится перестановка операндов таким образом, чтобы операнд, имеющий ссылку на объект (а не на константу), шел первым. В операциях присваивания адрес и выражение также меняются местами. Такие перестановки не влияют на результат выполнения программы, однако уменьшают число возможных вариантов при анализе. Во-первых, исчезает необходимость иметь при анализе отдельно операции запоминания и присваивания (при разборе они отличались друг от друга только порядком операндов). Остается одна операция присваивания. Во-вторых, например, оператор X=2+X; из-за коммутативности сложения будет приведен к точно такому же внутреннему представлению, что и X=X+2;

            После всех перестановок и перед поиском особых случаев фрагмент во внутреннем представлении выглядит уже так:
 1  2 3 4  5 6
IID 0 N 1 00 X
ILD 1 N 0 31
C4  0 N 0 00 #2
ILD 1 N 0 02
IAD 2 B 0 31
IID 0 N 1 00 X
IAS 2 S 0 31
Теперь верхняя операция именования IID относится к сложению, а нижняя — к присваиванию.

Общий поиск особых случаев

            Признаком записи результата на место первого операнда в данном простом примере является наличие в операндах операции IAS двух IID с одинаковой ссылкой на X.

            Но поскольку в общем случае операнды сами могут быть сложными выражениями, необходим универсальный механизм выделения операций и операндов, в том числе одинаковых, т.е. приведения внутреннего представления фрагмента к виду:
<1>
ILD 1 N 0 31
<2>
IAD 2 B 0 31
<1>
IAS 2 S 0 31
Здесь <1> и <2> — абстрактные «первый» и «второй» операнды, которые сами могут быть сложными конструкциями. Тогда не только простые операторы типа X=X+2; или X=2+X; но и более сложные записи, например: P->Y(I+J)=2+P->Y(J+I); сведутся к искомому случаю записи результата на место первого операнда.

Подход к анализу и поиску операций/операндов

            Для анализа операций и поиска одинаковых «абстрактных» операндов применен подход воссоздания при компиляции реальной операционной обстановки (которая будет в каждой точке программы при ее выполнении) с помощью модели вычислений операций/операндов. Для единственной задачи нахождения одинаковых объектов такая модель получается сравнительно простой и быстрой, однако необходимой, поскольку в общем случае «одинаковость» операндов может меняться во время исполнения программы. При этом анализируется не сразу вся генерируемая программа целиком, а только ее текущий фрагмент, находящийся в подвижном «окне», границы которого сдвигаются по мере обработки операций к концу программы. Операции/операнды, оказывающиеся вне границы «окна», исключаются из дальнейшего рассмотрения.

Модель вычислений операций и операндов

            Для выделения одинаковых операндов модель вычислений в части входных операндов операции и ее результата постоянно работает в компиляторе. Моделируется «рождение» операндов в операциях загрузки, их «жизнь» во время вычислений и, наконец, использование в операциях присваивания. Для удобства манипулирования при «рождении» операнду назначается уникальный номер, который закрепляется за ним на все время его нахождения в «окне».

            Модель определяет результат выполнения каждой операции просто в виде некоторого уникального числа-номера, поскольку, что именно делает реальная операция при выполнении программы не рассматривается. Кроме результата операции модель манипулирует и со ссылками на имена/константы. Модель отслеживает появление ссылок на имена/константы (в операциях, у которых нет операндов) и «исполняет» операции загрузки путем превращения ссылок во входные операнды для последующих операций. Модель пытается как можно дольше отслеживать связь между ссылками на имена/константы и результатами операций, хотя почти для всех операций эта связь сразу становится неопределенной. Только для операций загрузки и запоминания связь между ссылками и результатами определена и еще только операции индексирования массивов не нарушают эту связь.

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

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

             В модели действуют следующие правила:
1. Каждая операция может иметь 0, 1 или 2 входных операнда. Если у операции более 2 операндов, она обрабатывается как подпрограмма (поскольку три и более операндов обычно имеют встроенные функции языка, см. п. 9).
2. Если операция не имеет входных операндов, она имеет ссылку на имя или константу.
3. Каждая операция имеет единственный результат.
4. При обработке операции ее один/два входных операнда, а также текущая ссылка на имя/константу извлекаются из стека операндов, а ее результат и текущая ссылка на имя/константу запоминаются в стеке. Первоначально стек пуст.
5. После обработки операции присваивания в стек операндов ничего не заносится, так как операнды использованы и заканчивают существование.
6. При обработке операции без операндов текущая ссылка берется не из стека операндов, а из результата самой операции, т.е. «рождается».
7. Если операция имеет входные операнды (и, следовательно, не имеет ссылки на имя/константу) на месте поля ссылки в операции записываются номера одного/двух входных операндов для единого шага поиска одинаковых операций.
8. Если операция имеет входные операнды и не является операцией загрузки /присваивания /индексирования массивов, после ее обработки текущая ссылка становится неопределенной.
9. Если при анализе попадается вызов подпрограммы, далее все предыдущие операнды считаются неопределенными из-за возможного побочного эффекта, поскольку после обращения к подпрограмме операнды могут изменить свое значение и тогда использование их без повторного вычисления может стать неправомерным.

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

Поиск одинаковых операций

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

            Если найдена предшествующая такая же операция с такими же входными операндами, в качестве результата текущей операции записывается тот же номер, что у совпавшей, иначе результату текущей операции назначается новый уникальный номер. Такой подход позволяет единственным сравнением для каждой операции сравнивать на тождество сколь угодно сложные структуры (в пределах «окна»), так как появление уникального номера результата автоматически даст различие при последующих сравнениях на верхних уровнях иерархии. И наоборот, присвоение уже имеющегося номера результата позволяет продолжать прослеживать дальнейшие совпадения на более высоких уровнях иерархии.

Поиск ближайшего одинакового операнда

            Если найдена одинаковая с текущей операция и, значит, определен уже существующий номер ее результата, далее ищется ближайшая к текущей операция с точно таким же результатом, поскольку таких операций может быть несколько. В текущей операции окончательно фиксируются результаты поиска в виде занесения в специальное поле числа позиций от текущей до ближайшей предыдущей операции с точно таким же результатом и занесение «длины» операции, т.е. количества входящих в текущую операцию «вложенных» операций. В случае простой ссылки длина операции равна 1.

Пример поиска одинаковых операций

            Работа модели выполнения операций и алгоритма поиска в рассматриваемом примере:
 1  2 3 4  5 6    7 8    9      10      11      12    13
                  1 2  СРАВН  ССЫЛКА РЕЗУЛЬТАТ АДРЕС ДЛИНА
IID 0 N 1 00 X    - -    X      4       4        -     -
ILD 1 N 0 31      4 -   - 4     4       5        -     -
C4  0 N 0 00 #2   - -    #2     6       6        -     -
ILD 1 N 0 02      6 -   - 6     6       7        -     -
IAD 2 B 0 31      7 5   5 7     0       8        -     -
IID 0 N 1 00 X    - -    X      4       4        5     1
IAS 2 S 0 31      4 4   - 4     4       -        -     -
В дополнительных колонках приведены:
- 7 и 8 колонки - входные операнды, извлекаемые из стека.
- 9 колонка — поле операции, содержащее ссылку на имя/константу или входные операнды, используется при сравнении операций на равенство.
- 10 колонка - связь между ссылкой на имя/константу и номером результата, для большинства операций не определена (например, для IAD), прослеживается для операций ILD и IAS.
- 11 колонка — результат операции, которому присваивается уникальный номер, если не найдены такие же операции.
- 12 колонка — конечный результат поиска, в примере найдено, что совпала операция IID с операцией, расположенной пятью позициями ранее.
- 13 — длина совпавшей операции, в данном случае длина 1, т.е. состоит только из одной операции ссылки IID.             Как следует из таблицы, моделируя выполнение операций, алгоритм поиска обнаружил две одинаковые операции и отметил у них одинаковый результат (с номером 4). Результаты поиска одинаковых операций отмечены у операции IID в виде относительного адреса 5 и длины 1. В процессе поиска отслеживались ссылки на имя X и константу 2, хотя связь между результатами операций и этими ссылками уже через одну операцию становилась неопределенной.

Проверка на особые случаи

            Механизм использования результатов поиска операций/операндов (в том числе одинаковых) действует в компиляторе в универсальной процедуре обработки операций. Для каждой внутренней операции в таблице компилятора может быть указан список ее особых случаев. В списке для операции IAS есть и комбинация ее операндов вида:
<1> IAD <2> ILD <1>
означающая, что необходимо проверить, не идет ли сразу за загрузкой первого операнда IAS операция сложения IAD, после которой может быть любой операнд (условно «второй»), после чего идет операция ILD и точно такой же операнд, как и первый в IAS.

            При поиске особых случаев универсальная процедура обработки разбирает (без выполнения) операции, относящиеся к операции IAS. После разбора и пропуска «первого» операнда, следует проверка на строгое совпадение с операцией IAD, затем пропуск «второго» операнда, затем проверка на строгое совпадение с операцией ILD и, наконец, разбор опять «первого» операнда.

            Главная в данном случае проверка, что это именно такой же операнд, как и «первый», заключается в вычислении по ранее найденному моделью относительному адресу (в примере 5) от текущей операции IID места этого, предполагаемого совпадающего операнда. Компилятор запомнил адрес «первого» разобранного операнда IAS и при текущей проверке он действительно находится уже 5 позициями ранее текущей разбираемой операции. Кроме этого, запомненная компилятором длина «первого» операнда и длина текущего разбираемого операнда одинаковы и равны 1. Компилятор делает вывод, что найден этот особый случай комбинации операндов у операции IAS.

            Если компилятор не нашел ни одного из заданных особых случаев, он ищет универсальную комбинацию типа <1> <2> <3> <4>… по числу входных операндов данной операции. Поскольку конкретных операций здесь нет, такая комбинация всегда будет найдена и тем самым будут определены адреса всех входных операндов текущей операции.

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

Генерация команд с учетом особых случаев

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

            Процедуры генерации процессорных команд имеют свой уровень оптимизации, действующий уже в рамках одной команды. В данном случае будет сгенерирована команда сложения переменной X в памяти с константой 2. Если бы и «первый» операнд был константой — сложение выполнилось бы сразу при компиляции. Если бы константа была равна 1, использовалась бы более короткая команда инкремента. Если бы и «второй» операнд был объектом в памяти — был бы создан промежуточный операнд (по возможности регистр), однако если бы «второй» операнд был равен «первому», то сложение заменилось бы сдвигом и т.д.

Общее использование особых случаев при компиляции

            В результате такого подхода в процессе обработки операций внутреннего представления программы и генерации команд постоянно производится поиск особых случаев комбинаций операндов, причем не обязательно состоящих в использовании одних и тех же операндов. Это может быть любая комбинация операндов и операций, распознавание которой упрощает генерацию команд. В текущей версии компилятора PL/1 распознается 85 особых случаев для разных операций. Дополнительным удобством постоянного поиска особых случаев является то, что адреса опознанных операндов уже найдены в процессе этого поиска и могут сразу использоваться при генерации команд, без нового поиска.

            Например, список особых случаев при разборе условия в операторе IF включает 7 комбинаций:
BLD <1>
IGT <1>,<2>
ILT <1>,<2>
IEQ <1>,<2>
IGE <1>,<2>
ILE <1>,<2>
INE <1>,<2>
            Первый особый случай означает, что в программе в условном операторе стоит загрузка битовой строки, а не выражение, и можно сразу генерировать команду ее сравнения с нулем.

            Остальные особые случаи позволяют сразу генерировать команды загрузки найденных «первого» и «второго» операндов, а затем команду их сравнения и перехода по заданному условию (больше, меньше, равно и т.д.), т.е. генерировать команды для условий типа IF X=Y… или IF (A+B)>(C+D)…, «первыми» операндами здесь будут X и A+B, а «вторыми» соответственно Y и C+D. В этих случаях при генерации команд результат поиска одинаковых операндов не используется, однако используются адреса найденных «первого» и «второго» операндов.

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

Заключение

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

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

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

            Поиск одинаковых операндов не запрещает возможности сокращенного вида операторов в языке, просто запись результата на место операнда будет обнаружена в любом случае:
   1 000000 TEST:PROC;
   2 000000 DCL
   3 000000 (X,I,J)     FIXED(31),
   4 000000 Y(100)      FIXED(31) BASED,
   5 000000 P           PTR;
   6 000000
   7 000000 X=X+2;
     000000 83050800000002              add    X,2
   8 000007 X=2+X;
     000007 83050800000002              add    X,2
   9 00000E X+=2;
     00000E 83050800000002              add    X,2
  10 000015 P->Y(I+J)=1+1+P->Y(J+I);
     000015 8B3D14000000                mov    edi,P
     00001B A110000000                  mov    eax,J
     000020 03050C000000                add    eax,I
     000026 834487FC02                  add    0FFFFFFFCh[edi+eax*4],2
     00002B C3                          ret
  11 00002C END TEST;

Литература

1. А. Ахо, Дж. Ульман «Теория синтаксического анализа, перевода и компиляции. Том 2 «Компиляция», Москва «Мир» 1978
2. «PL/I language Programmer’s Guide» Digital Research, Сalifornia 1982

Автор: Д.Ю.Караваев. 22.01.2012

Последняя правка: 2018-10-29    16:00

Оцените

Написать отзыв

Написать автору можно на электронную почту mail(аt)compiler.su

Авторизация

Регистрация

Выслать пароль

Карта сайта


Каким должен быть язык программирования?

Анализ и критика

Описание языка

Компилятор

Отечественные разработки

Cтатьи на компьютерные темы

Двадцать тысяч строк кода, которые потрясут мир?

Почему владение/заимствование в Rust такое сложное?

Масштабируемые архитектуры программ

Почему Хаскелл так мало используется в отрасли?

Бесплатный софт в мышеловке

Исповедь правового нигилиста

Русской операционной системой должна стать ReactOS

Почему обречён язык Форт

Программирование без программистов — это медицина без врачей

Электроника без электронщиков

Статьи Дмитрия Караваева

●  Идеальный транслятор

●  К вопросу о совершенствовании языка программирования

●  О реализации метода оптимизации при компиляции

●  О реализации метода распределения регистров при компиляции

●  О распределении памяти при выполнении теста Кнута

●  Опыты со стеком или «чемпионат по выполнению теста Кнута»

●  Сколько проходов должно быть у транслятора?

●  Чтение лексем

●  Экстракоды при синтезе программ

●  Об исключенных командах или за что «списали» инструкцию INTO?

●  Типы в инженерных задачах

●  Непрерывное компилирование

●  Об одной реализации специализированных операторов ввода-вывода

●  О русском языке в программировании

●  Формула расчета точности для умножения

●  Права доступа к переменным

●  Скорость в попугаях

●  Крах операции «Инкогнито»

●  Предопределенный результат

Компьютерный юмор

Прочее

Последние комментарии

2018/11/12 14:18 ••• Попов Михаил
✎ Программирование без программистов — это медицина без врачей

2018/11/11 23:39 ••• Автор сайта
✎ Изменение длины объекта в стеке во время исполнения

2018/11/11 14:29 ••• Александр Коновалов aka Маздайщик
✎ Помеченные комментарии

2018/11/11 14:01 ••• Александр Коновалов aka Маздайщик
✎ Нерабочий код

2018/11/11 13:39 ••• Александр Коновалов aka Маздайщик
✎ О русском языке в программировании

2018/11/11 12:57 ••• Александр Коновалов aka Маздайщик
✎ Об одной реализации специализированных операторов ввода-вывода

2018/11/03 22:43 ••• rst256
✎ Непрерывное компилирование

2018/11/02 23:23 ••• Неслучайный читатель
✎ Сколько проходов должно быть у транслятора?

2018/11/01 19:10 ••• Автор сайта
✎ Об исключенных командах или за что «списали» инструкцию INTO?

2018/10/31 06:01 ••• kt
✎ Чтение лексем

2018/10/30 18:30 ••• Александр Коновалов aka Маздайщик
✎ Экстракоды при синтезе программ

2018/10/29 13:17 ••• Автор сайта
✎ Каким должен быть язык программирования?