О реализации метода оптимизации при компиляции
ВведениеСуществует множество методов оптимизации при компиляции с языков высокого уровня [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 «Компиляция», Москва «Мир» 19782. «PL/I language Programmer’s Guide» Digital Research, Сalifornia 1982 Автор: Д.Ю.Караваев. 22.01.2012 Опубликовано: 2018.08.26, последняя правка: 2019.01.28 20:51
Написать автору можно на электронную почту |
Продолжение цикла и выход из него