Я очень люблю придумывать для компилятора, который сопровождаю, всякие приемы мелкой, или, как я ее называю, «тактической» оптимизации.
В компиляторе при генерации кода имеется такой момент, когда большинство команд будущей программы (точнее, компилируемого модуля) уже сгенерировано, но их еще можно менять или выбрасывать, поскольку адреса команд переходов и вызовов еще не вычислены, а окончательный размер кода программы (точнее, этого модуля) еще не получен.
Вот этот момент и является самым удобным для проведения «тактической» оптимизации в пределах 2-3 соседних команд. Как правило, и анализ при такой оптимизации очень прост, поскольку можно сравнивать прямо двоичные коды с шаблонами, а не проводить детальное изучение множества операций и их операндов во внутреннем представлении будущей программы.
Рассмотрим некоторые приемы оптимизации «сверткой» на простейшем примере.
Вот есть такой код примитивной, но, тем не менее, законченной программы, которая просто выводит значение битовой строки на экран:
test:proc main;
dcl x bit(1);
put list(x);
end test;Компилятор превращает это в такие коды:
Поскольку кодов мало, их все здесь легко перечислить. По сути, вся программа перевелась в несколько системных вызовов или, как я их называю, «экстракодов».
Вызов «экстракода» ?START, как нетрудно догадаться, это пролог программы (выделение памяти, открытие стандартного ввода-вывода и т.п.) Перед его вызовом компилятор помещает в регистр EAX состояние всех флагов компиляции, из которых и получается такая «кривая» десятичная константа.
Потом идет открытие операции стандартного вывода в виде вызова ?SYSPS. Перед его вызовом в регистр ECX помещается адрес внутренней метки, на которую надо перейти, если операция вывода потерпела неудачу.
Затем идет собственно вывод переменной X типа «битовая строка в один бит» (т.е. это переменная булева типа). Значение переменной пишется в регистр AL, число значащих бит в переменной – в регистр CH.
Сначала вызовом ?QB08C заданная битовая строка переводится в текст и вызовом ?PNBOP этот текст выдается на экран.
Затем вызовом ?QIOOP вся операция вывода закрывается, и, наконец, вызовом «экстракода» ?STOPX вся программа завершается.
Если запустить эту программу, она выдаст на экран текст ’0’b , что в данном примере и означает содержимое битовой переменной X.
Если X описать не как bit(1), а, например, как bit(64), то в кодах немного чего поменяется:
Но, разумеется, изменения есть, и в регистр CH теперь засылается длина 64 бита, а не 1.
Казалось бы, ну что здесь оптимизировать и сокращать? Внутри системных вызовов выполняется довольно много действий и, например, вставлять эти действия прямо в программу (т.е. «in line») совершенно непродуктивно, код сильно раздуется.
Но в реальных, больших программах гораздо чаще выводятся булевы переменные, чем, например, строки типа bit(64). Поэтому имеет смысл добавления в компилятор нового специализированного «экстракода», переводящего в текст именно переменные типа bit(1) и имеющего новое имя, например, ?QB081. Поскольку тело ранее используемого «экстракода» ?QB08C расположено в системной библиотеке и начинается с метки ?QB08C:, то новый экстракод располагается чуть выше и состоит всего лишь из одной команды mov ch,1:
PUBLIC ?QB081:
mov ch,1
PUBLIC ?QB08C:
...Выполнение команд при таком добавлении, по сути, не меняется, просто раньше выполнялась команда mov ch,1 и затем происходил системный вызов, а с новым экстракодом сначала происходит его вызов, первой командой которого выполняется все та же загрузка mov ch,1.
Собственно оптимизация заключается в том, что компилятор ищет среди уже сгенерированных команд пару mov ch,1 + call ?QB08C.
Если он ее находит, пара заменяется на один вызов добавленного «экстракода» call ?QB081:
Код системной библиотеки увеличился на 2 байта команды mov ch,1, а код программы – сократился на те же 2 байта. Но если таких фрагментов в компилируемом модуле найдется несколько – общий код программы сократится и иногда существенно.
Можно заметить, что чаще всего, битовая строка преобразуется в текст, когда это требуется для ее последующей выдачи. Т.е. после «экстракода» ?QB08C или нового ?QB081 часто будет вызов ?PNBOP. Хорошо бы и эту пару вызовов «свернуть» в один новый вызов, который тоже добавить в системную библиотеку. К сожалению, создать новый вызов с именем, например, ?PNBO1, просто разместив внутри системной библиотеки вызов ?QB081 перед началом имеющегося экстракода ?PNBOP :
PUBLIC ?PNBO1:
call ?QB081
PUBLIC ?PNBOP:
…как в предыдущем случае не получится, поскольку вызов ?QB081 возвращает результат в виде текстовой строки через стек.
Для правильной работы экстракода ?PNBOP в стеке сначала должен находиться адрес возврата, а не сразу текстовая строка. Но с помощью небольших исправлений можно привести стек в правильное состояние:
PUBLIC ?PNBO1:
pop R8 ; достаем адрес возврата
call ?QB081
push R8 ; помещаем адрес возврата в вершину стека
PUBLIC ?PNBOP:
…Здесь используются знания о том, что экстракод ?QB081 не использует регистр R8 и поэтому в этом регистре можно сохранить адрес возврата.
Оптимизация «сверткой», как и в предыдущем случае, заключается в том, что компилятор ищет пару вызовов call ?QB081 + call ?PNBOP и заменяет эту пару единственным вызовом call ?PNBO1:
Таким образом, добавлением в таблицу компилятора и системную библиотеку двух новых «экстракодов» ?QB081 и ?PNBO1 удается сократить код программы, за счет незначительного увеличения кода системной библиотеки.
Поскольку в реальных программах таких мест встречаются десятки, а то и сотни, код программы начинает сокращаться, что важно для работы современных процессоров, так как быстрее читаются команды выполняемой программы из памяти в процессор.
При этом никаких серьезных доработок компилятора не требуется. Добавляются имена новых экстракодов в его общую внутреннюю таблицу. Их сейчас там уже 266 штук. И добавляется очередной типовой поиск сочетаний заданных команд в уже сгенерированном компилятором коде. Ну и, разумеется, добавляются крошечные исправления в системную библиотеку.
Не буду дальше развивать эту тему, но замечу, что и «экстракод» ?SYSPS, и «свернутый» в примере ?PNBOP сами тоже являются результатами предыдущих «сверток» универсальных представлений «экстракодов». Поэтому коды типовых фрагментов программы от такой оптимизации «сверткой» становятся все компактнее и компактнее, а все разрастающееся при этом число специализированных «экстракодов» в системной библиотеке никаких сложностей не вызывает и для программиста прозрачно.