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

Question

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

Краткий обзор компилятора:

7Basic является компилятор, который ставит своей целью собрать 7Basic кода непосредственно в машинный код для целевой архитектуры/платформы. В настоящее время 7Basic генерирует сборку x86 с исходным файлом.

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

Например, код this (который составляет до this код сборки) занимает почти 80,47 раз дольше, чем the equivalent C code.

Часть проблемы заключается в том, что компилятор генерирует код вроде следующего:

push eax 
push 5000000 
pop ebx 
pop eax 

Вместо того, чтобы более логично:

mov ebx,5000000 

... который выполняет то же самое.

Мой вопрос: какие методы избегают такого рода проблем? Парсер в основном использует рекурсию для анализа выражений, поэтому генерируемый код отражает это.

Answer 1

Один метод называется peephole optimisation. Это требует итеративного подхода к очистке кода сборки. По сути, вы просматриваете код сборки, просматривая только две или три команды за раз, и видите, можете ли вы уменьшить их на что-то более простое. Например,

push eax  ; 1 
push 5000000 ; 2 
pop ebx   ; 3 
pop eax   ; 4 

Первым шагом будет смотреть на линии 2 и 3, и заменить это:

push eax  ; 1 
mov ebx,5000000 ; 2a 
pop eax   ; 4 

Во-вторых, вы могли бы рассмотреть 1 и 4, а если eax не затрагивается в средний инструкция, удалить их обоих, оставив то, что вы хотите:

mov ebx,5000000 ; 2a 

Answer 2

вы можете рассмотреть вопрос о генерации кода C, а не сборка, а затем пусть C компилятор (например, GCC) обрабатывать код г для вас. Нет смысла пытаться изобрести колесо.

Answer 3

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

Этот шаблон испускаемого кода подсказывает мне, что генератор кода не знает, что x86 имеет инструкции «mov немедленного», которые непосредственно вставляют постоянное значение в поток команд. Кодировка x86 для кодов операций с немедленными значениями может немного усложниться (байты R/M переменной длины), но это уже необходимо, если вы хотите использовать многие инструкции x86.

Этот испущенный код также предполагает, что генератор кода не знает, что EAX не изменяется инструкциями EBX. Это похоже на то, что codegen является шаблоном, а не дискретной логикой.

Этот вид codegen возникает, когда внутреннее промежуточное представление операций компилятора недостаточно детально, чтобы представлять все грани целевой архитектуры. Это особенно верно, если архитектура генератора кода была первоначально разработана для набора команд RISC, но была перепрофилирована для извлечения инструкций x86. Архитектура RISC, как правило, имеет очень мало и очень простая загрузка, хранение и управление инструкциями reg/reg, тогда как набор инструкций x86 органично развивается в течение десятилетий, чтобы включать в себя множество кодов операций, которые непосредственно работают с памятью, встроенными константами в инструкции, и весь беспорядок других вещей. Если промежуточное представление компилятора (граф выражений) подключено к RISC, будет сложно сделать его доступным для широкого разнообразия и тонкостей x86.

Answer 4

В настоящее время я беру курс компилятора. Я сделал большой прогресс в выпуске эффективного кода, но вы должны заглянуть в книгу драконов. Это обряд посвящения. Вы должны взглянуть на код из книги Джереми Беннетта, Введение в методы компиляции: первый курс с использованием ANSI C, LEX и YACC. Сама книга очень трудно найти, но вы можете загрузить исходный код для компилятора, свободного от

http://www.jeremybennett.com/publications/download.html

Файл генератор кода (cg.c) имеет некоторые функции для генерации достаточно оптимизированный код. Целевой язык не i386, но вы должны рассмотреть вопрос о том, как он описывает регистры и отслеживает, где хранятся записи таблицы символов. Его выходная сборка может быть дополнительно оптимизирована, но она обеспечивает отличную основу для создания кода, который может конкурировать с выходом gcc -S в некоторых отношениях.

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

Например, если ваш промежуточный код представляет собой список четверки, вы должны просто итератором через него для каждой функции и отслеживать максимальное смещение. Затем выведите строку, чтобы вычесть объем пространства в стеке. Это устраняет необходимость включения и выключения большого количества переменных. Чтобы удалить их, вы можете просто переместить их значение из их смещения в стек в регистр. Это значительно улучшит производительность.

Answer 5

Оптимизация Peephole поможет, но одна очевидная проблема заключается в том, что ваш компилятор не выполняет распределение регистров!

http://en.wikipedia.org/wiki/Register_allocation

Если вы хотите, чтобы получить серьезные уровни производительности, что вы делаете, чтобы смотреть на это. Это можно сделать за один проход, если вы делаете это с жадностью «на лету».