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

Question

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

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

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

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

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

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

push eax
push 5000000
pop ebx
pop eax

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

mov ebx,5000000

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

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

Answer 1

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

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

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

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

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

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

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

Answer 4

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

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

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

Answer 5

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

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

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

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