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

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

В компиляторе, который я имею честь курировать, есть место, где выделяются регистры x86-64 для адресов: указателей, параметров функций и т.п. В терминах языка для базированных переменных.

При выделении регистров компилятор сначала пытается найти самый выгодный регистр, например, тот который тут же опять будет использоваться для этой же цели и, значит, его не потребуется снова загружать этим же значением. Если никаких выгодных не найдено – выделяется первый свободный. Ничего особенного и сложного здесь нет. Пожалуй, единственный вопрос: какой из свободных регистров выделять сначала – один из «традиционных» для x86 типа RBX/RSI/RDI, или один из «новых» в x86-64, т.е. R8-R15?

С одной стороны, R8-R15 реже используются, например, в системной библиотеке (она переделана для x86-64 из x86), а, значит, больше шансов, что их значения не будут часто затираться при выполнении программы и требовать повторных загрузок. Но с другой стороны, использование R8-R15 требует добавления REX-префиксов в команды, что увеличивает объем кода.

Например, команда PUSH RAX занимает один байт, а вроде бы такая же PUSH R8 – два. Команда INC B PTR [RBX] не требует REX-префикса, а INC B PTR [R10] – требует и т.д. Когда-то я попробовал в компиляторе выделять регистры сначала из свободных R8-R15 и тут же увидел, что просто код раздувается без каких-либо видимых преимуществ. Ну и не стал дальше экспериментировать.

Немного отвлекаясь в сторону. С появлением x86-64 появился и забавный вопрос. Вот есть в x86 команда MOV EAX,EBX. Можно получить тот же результат, используя пару команд PUSH EBX + POP EAX. Но нет никаких оснований считать, что эта пара будет работать лучше обычной пересылки. В паре и команды зависимы друг от друга через стек и идет запись и чтение из памяти. И для x86-64 все эти соображения, конечно, остаются. Но появляется нюанс. В команде пересылки MOV RAX,RBX теперь нужен REX-префикс и она занимает три байта. А в паре пересылки через стек PUSH RBX + POP RAX не нужен REX-префикс и пара занимает лишь два байта, а не три. Т.е. появился аргумент и в пользу пересылки через стек – уменьшение кода. Насколько это преимущество пересиливает (и пересиливает ли?) недостатки – это, конечно, вопрос.

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

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

Я выделил лишь 16 влияющих на код вариантов установки приоритета при выделении регистров. Вообще-то, поскольку регистров общего назначения 16, а регистр RSP не выделяем, то должно было бы быть 32768 разных комбинаций. Но 99.99% этих вариантов ничего не поменяют. А так каждый бит номера варианта означает, что не следует выделять указанный регистр для адреса, даже если в данный момент он свободен. Первый бит – это регистр RBX, второй - RSI, третий – RDI и четвертый RCX. Например, вариант №3 означает, что не следует выделять для адресации ни регистр RBX, ни регистр RSI, даже, если сейчас они не заняты никакими значениями. Похоже на инструкцию Холмса доктору Ватсону. Помните? «Не садитесь ни в первый, ни во второй кэб, который попадется навстречу». Во что это выльется в программе и как это скажется на размере команд предсказать сложно.

А вот вставить это условие в компилятор проще-простого. Ведь он все равно проверяет, занят сейчас регистр или нет. А так, проверяет занятость и заодно установку соответствующего бита в переменной. Если бит установлен – это все равно, что регистр занят.

Итак, 16 вариантов компиляций. Чтобы не менять автоматически создаваемые скрипты сборок программ, номер варианта компиляции задается не через командную строку вызова компилятора, а через реестр Windows, где вводится одна переменная, которую компилятор и читает при своем запуске. Разумеется, если в реестре такой переменной нет – значит, нулевой вариант по умолчанию.

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

Ниже приведен фрагмент этого скрипта. Лучшие варианты сохраняются в файлах с расширением .OOO.

Все выполняется скриптовой процедурой REG_ADD, которая сначала создает «базовый» набор объектных модулей, а затем еще 15 раз повторяет компиляцию всех модулей и 15 раз отбирает с помощью простой специально написанной для этого программы CODE_OBJ.EXE лучшие образцы от очередного варианта.

А собственно компиляция всех модулей так и продолжает производиться командой CALL ML.BAT, после которой создаются 40 объектных модулей.

Сначала всякие подготовительные операции
…
REM ---- СОЗДАЕМ ПЕРВЫЕ ВАРИАНТЫ *.OBJ ----
DEL *.OOO
CALL :REG_ADD 0
COPY *.OBJ *.OOO
REM ---- СОЗДАЕМ ОСТАЛЬНЫЕ ВАРИАНТЫ *.OBJ, ЛУЧШИЕ СОХРАНЯЕМ В *.OOO ----
FOR /L %%J IN (1,1,15) DO CALL :REG_ADD %%J
REM ---- ЛУЧШИЕ ВАРИАНТЫ *.OBJ ВОЗВРАЩАЕМ ПО МЕСТАМ ----
COPY *.OOO *.OBJ
…
Далее выполняется штатная сборка EXE-файла, но уже из лучших модулей

Вот текст скриптовой процедуры:

REM ---- ИЗ РАЗНЫХ ВАРИАНТОВ *.OBJ СОХРАНЯЕМ В *.OOO ЛУЧШИЕ ----
:REG_ADD
@ECHO .
@ECHO %1
@REG ADD HKCC\Software\PL/1 /v RBX /t REG_DWORD /d 0000000%1 /f >NUL
@DEL *.OBJ 
@CALL ML.BAT
@IF "%1" == "0" GOTO :EOF
@REM ---- СОХРАНЯЕМ В *.OOO ЛУЧШИЕ ВАРИАНТЫ *.OBJ ----
@ECHO OFF
@FOR %%I IN (*.OOO) DO CODE_OBJ.EXE %%I %%~NI.OBJ
@GOTO :EOF

Таким образом, доработки и компилятора и скрипта сборки EXE-файла самые примитивные. Добавляется еще простенькая программа выбора самого короткого варианта объектного модуля. Вот текст этой программы, которая сравнивает размеры команд двух файлов в формате OMF и сохраняет более короткий в файле с расширением .OOO.

Я не предлагаю разбираться в этом тексте, а, просто показываю, какой он небольшой:

CODE_OBJ:PROC(S) MAIN; 
DCL 
 S                CHAR(*) VAR,
 F1               FILE,
 P1               PTR,
 X(0:100_000_000) BIT(8) BASED(P1),
(I,J,K)           FIXED(31),
 B32              BIT(32) DEF(J),
 B8               BIT(8)  DEF(J),
 B8_1             BIT(8)  DEF(J+1),
 B8_2             BIT(8)  DEF(J+2),
 B8_3             BIT(8)  DEF(J+3),
 ЗАГОЛОВОК        BIT(8),
(ИМЯ_1,ИМЯ_2)     CHAR(*) VAR, 
(COPYFILEA        ENTRY(CHAR(*) VAR,CHAR(*)VAR,BIT(32)),
 GETLASTERROR)    RETURNS(FIXED(31)) IMPORT;

//---- ЧИТАЕМ ДВА ИМЕНИ ФАЙЛОВ ЧЕРЕЗ ПРОБЕЛ ----
GET STRING(S) LIST(ИМЯ_1,ИМЯ_2);
//---- ОТКРЫВАЕМ ПЕРВЫЙ OBJ - ФАЙЛ (ЛУЧШИЙ) ----
ON UNDEFINEDFILE(F1) PUT SKIP LIST('НЕТ',ИМЯ_1,STOP(0));
OPEN(F1) INPUT RECORD TITLE(ИМЯ_1) ENV(B(-1));// ОТОБРАЖЕНИЕМ НА ПАМЯТЬ
READ(F1) SET(P1);
REVERT UNDEFINEDFILE(F1);
//---- ЕСЛИ НЕТ OMF-ЗАГОЛОВКА ----
IF X(0) ^= '80'B4 THEN STOP(0);
//---- ПРОПУСКАЕМ ВСЕ ЗАПИСИ ДО ПЕРВОГО SEGDEF-32 ----
DO WHILE(ЗАГОЛОВОК^='99'B4);
   J=0; B8=X(I+1); B8_1=X(I+2);     // ДОСТАЛИ ДЛИНУ
   I+=J+3;                          // ПРОПУСТИЛИ ЗАПИСЬ
   ЗАГОЛОВОК=X(I);                  // ЗАГОЛОВОК СЛЕДУЮЩЕЙ ЗАПИСИ
   IF ЗАГОЛОВОК='98'B4 THEN STOP(0);// ЭТО БЫЛ OMF ОТ АССЕМБЛЕРА	
END WHILE;
//---- ДОСТАЕМ ДЛИНУ СЕГМЕНТА SEGDEF-32 ----
B8  =X(I+4);
B8_1=X(I+5);
B8_2=X(I+6);
B8_3=X(I+7);
K=J; // ЗАПОМНИЛИ ДЛИНУ ДЛЯ БУДУЩЕГО СРАВНЕНИЯ
CLOSE(F1);
//---- ОТКРЫВАЕМ ВТОРОЙ OBJ - ФАЙЛ (ТЕКУЩИЙ) ----
ON UNDEFINEDFILE(F1) PUT SKIP LIST('НЕТ',ИМЯ_2,STOP(0));
OPEN(F1) INPUT RECORD TITLE(ИМЯ_2) ENV(B(-1));// ОТОБРАЖЕНИЕМ НА ПАМЯТЬ
READ(F1) SET(P1);
I=0;
ЗАГОЛОВОК='00'B4;    // ПОКА ОПЯТЬ НЕТ OMF-ЗАГОЛОВКОВ
//---- ЕСЛИ НЕТ ЗАГОЛОВКА OMF-ФАЙЛА ----
IF X(0) ^='80'B4 THEN STOP(0);
//---- ПРОПУСКАЕМ ВСЕ ЗАПИСИ ДО ПЕРВОГО SEGDEF-32 ----
DO WHILE(ЗАГОЛОВОК^='99'B4);
   J=0; B8=X(I+1); B8_1=X(I+2);     // ДОСТАЛИ ДЛИНУ
   I+=J+3;                          // ПРОПУСТИЛИ ЗАПИСЬ
   ЗАГОЛОВОК=X(I);                  // ЗАГОЛОВОК СЛЕДУЮЩЕЙ ЗАПИСИ
   IF ЗАГОЛОВОК='98'B4 THEN STOP(0);// ЕСЛИ ЭТО БЫЛ OMF ОТ АССЕМБЛЕРА	
END WHILE;
//---- ДОСТАЕМ ДЛИНУ СЕГМЕНТА ----
B8  =X(I+4);
B8_1=X(I+5);
B8_2=X(I+6);
B8_3=X(I+7);
CLOSE(F1);
//---- ТЕКУЩИЙ OBJ-ФАЙЛ БОЛЬШЕ ПО КОДАМ, ЧЕМ ЛУЧШИЙ ----
IF K<=J THEN STOP(1);  // НИЧЕГО НЕ НАДО ДЕЛАТЬ
//---- ТЕКУЩИЙ OBJ-ФАЙЛ КОРОЧЕ ЛУЧШЕГО, КОПИРУЕМ ЕГО КАК ЛУЧШИЙ ----
IF COPYFILEA(ИМЯ_2,ИМЯ_1,'00000000'B4)^=0 THEN 
  PUT SKIP EDIT('СКОПИРОВАН ЛУЧШИЙ ',ИМЯ_2,J,' БАЙТ В ')(A,A,COL(35),F(8),A)
                                    (ИМЯ_1,K,' БАЙТ')   (  A,COL(65),F(8),A);
  ELSE PUT SKIP LIST('ОШИБКА',GETLASTERROR,STOP(0));
STOP(1);
END CODE_OBJ;

Сначала я просто 16 раз попробовал собрать прикладную программу для разных вариантов выделения регистров и записал 16 размеров кода EXE-файла. Видно, что любая попытка помешать выделять свободные регистры RBX/RCX/RSI/RDI чаще приводит к увеличению размера кода. А для двух вариантов вообще не удалось скомпилировать один из 40 модулей, поскольку получались недопустимые команды типа MOV AH,[R10] из-за «нехватки» традиционных регистров.

А вот результат запуска скрипта с 16-ю компиляциями 40 модулей и с выбором самого короткого.

Фрагмент листинга работы CODE_OBJ.EXE. Видно, как находятся все более короткие варианты объектных модулей:

В результате был собран EXE-файл c размером команд 15B76B, что короче, чем у самого лучшего из приведенных выше вариантов. Так сказать, получилась «сборная» модулей из всех «клубных» модулей. Аналогия со спортивными командами проявилась еще и в том, что почти все «команды» (т.е. почти все варианты) делегировали в «сборную» своих «лучших игроков», несмотря на общий весьма средний уровень каждой «команды» (большинство модулей в размерах не уменьшались, а увеличивались).

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

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

Могут сказать, что результаты этой мета-оптимизации получились слабыми. В программе, состоящей из 1.4 Мб команд, удалось таким путем сократить менее 2 Кб. Однако ну и пусть себе и эта копейка начинает беречь рубль. Ведь выигрыш достался практически даром. Всего лишь за полчаса написания программы выбора более короткого объектного модуля. Даже время компиляции, несмотря на 16 вариантов, замедлилась не критично: было 3 секунды, стало 48 секунд. Не страшно, новая сборка не выполняется каждую минуту, это редкое событие.

Более интересный вопрос: а за счет чего вдруг вообще получилось уменьшение кода? Если в большинстве случаев отказ использовать для адресации регистр RSI или RDI увеличивает код, а не уменьшает?

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

Обычно в роли обратной связи выступает программист, который анализирует результаты работы программы и ключами компилятора пытается найти наилучший вариант.

Здесь же, хотя и в самом простом виде и только по одному параметру (размер команд) эта обратная связь автоматизирована.

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