Пилю генератор кода для компилятора
Здравствуйте, теребятки! С вами наша непостоянная рубрика ненормальное программирование.
В качестве пет-проекта я потихоньку пилю собственный Ada-подобный ЯП. Планов на фичи языка очень много, но пока он по фичам не далеко ушел от ранних вариантов сишечки. Однако сегодня не об этом. Сегодня я вам хочу рассказать о генерации кода.
Генерация кода в настоящее время реализована из синтаксического дерева, без трансляции в отдельное представление для оптимизации. Обычно так не делают, так делать неправильно. Но реализовывать полноценную систему анализа графа управления в мои задачи не входило, поэтому я постарался выжать эффективность насколько возможно из трансляции, управляемой синтаксическим деревом.
Сегодня мы посмотрим, что получается, если решать задачу заведомо неподходящим способом.
Некоторые используемые приёмы оптимизации:
- Отслеживание, какие константы или значения выражений загружены в регистры и устранение избыточных загрузок.
- Переупорядочивание вычисления операндов выражения.
- Устранение выдачи неиспользованных меток. (Помогает лучше отслеживать состояние регистров в п.1.)
- Устранение избыточных цепочек jmp-ов. (Когда jmp делается на следующий jmp.)
Далее я покажу примеры, как генератор кода устраняет избыточные загрузки значений. Про остальные пункты расскажу как-нибудь в другой раз. (Примерно через никогда.)
Пример 1.
Генератор кода устранил 4 инструкции mov EAX, dword [EBP+8], так как увидел, что значение переменной Index уже загружено в регистр.
Функция:
char @DictGetFullyQualifiedName(word D)
when D >= nDict:
StopInternal(__FILE__, __LINE__);
word Index = Dict[D].FullyQualifiedName;
when Index != 0:
return @Char[Index];
char Buff[nBUFF];
strbuf buf;
strbuf_init(@buf, @Buff, nBUFF);
Dict_MakeFullyQualifiedName(@buf, D);
Index = SaveString0(@Buff);
Dict[D].FullyQualifiedName = Index;
return @Char[Index];
end
Сгенерированный код:
@10342: ; ## DictGetFullyQualifiedName ##
push EBP
mov EBP, ESP
sub ESP, 144
; #line compiler_dict.ctxi:84
mov EAX, dword [EBP+8]
cmp EAX, dword [@@DATA+8476676]
jb @10343
; #line compiler_dict.ctxi:85
push dword 85
push dword @@ROLITERALS+7329
call @10235 ; StopInternal
@10343:
; #line compiler_dict.ctxi:87
mov EAX, dword [EBP+8]
imul EAX, 77
mov EAX, dword [@@DATA+EAX+776684]
mov dword [EBP-4], EAX
; #line compiler_dict.ctxi:88
; Node link reuse in CodePrimaryWrapped
; Переиспользуется значение Index в регистре EAX
test EAX, EAX
je @10346
; #line compiler_dict.ctxi:89
; Node link reuse in CodePrimaryWrapped
; Переиспользуется значение Index в регистре EAX
add EAX, @@DATA+49288
leave
ret 4
@10346:
; #line compiler_dict.ctxi:91
; #line compiler_dict.ctxi:92
; #line compiler_dict.ctxi:93
push dword 128
lea EAX, [EBP-132]
push EAX
lea EAX, [EBP-144]
push EAX
call @10126 ; strbuf_init
; #line compiler_dict.ctxi:94
push dword [EBP+8]
lea EAX, [EBP-144]
push EAX
call @10335 ; Dict_MakeFullyQualifiedName
; #line compiler_dict.ctxi:96
lea EAX, [EBP-132]
push EAX
call @10272 ; SaveString0
mov dword [EBP-4], EAX
; #line compiler_dict.ctxi:97
; Node link reuse in Code_ASSIGN (1)
; Переиспользуется значение Index в регистре EAX
mov EBX, dword [EBP+8]
imul EBX, 77
mov dword [@@DATA+EBX+776684], EAX
; #line compiler_dict.ctxi:98
; Node link reuse in CodePrimaryWrapped
; Переиспользуется значение Index в регистре EAX
add EAX, @@DATA+49288
leave
ret 4
В этом примере есть интересный фрагмент:
mov EAX, dword [EBP+8]
cmp EAX, dword [@@DATA+8476676]
jb @10343
; #line compiler_dict.ctxi:85
push dword 85
push dword @@ROLITERALS+7329
call @10235 ; StopInternal
@10343:
; #line compiler_dict.ctxi:87
mov EAX, dword [EBP+8]
Здесь также можно было бы устранить повторную загрузку mov EAX, dword [EBP+8], но это пока не реализовано.
- Компилятор знает, что StopInternal не возвращает управление.
- Единственный переход по метке @10343 выполняется из места, в котором EAX уже содержит нужное значение.
- Таким образом вторая загрузка регистра избыточна.
- Но чтобы отследить это, необходим продвинутый анализ перехода по меткам, делать который в мои планы пока не входит.
Пример 2.
Вот еще пример устранения загрузок локальной переменной. Генератор кода дважды переиспользует значение переменой L в регистре EAX:
word L = strlen(@Dst);
if L > 1 then
if str_has_char(@fpath_p_dir_separators, Dst[L - 1]) == 0 then
strn_cat(@Dst, @fpath_p_dir_separator, Size);
end:if
end:if
; #line include/fpath.ctxi:131
push dword [EBP+8]
call @10013 ; strlen
mov dword [EBP-4], EAX
; #line include/fpath.ctxi:132
; Node link reuse in CodePrimaryWrapped
cmp EAX, 1
jbe @10179
; #line include/fpath.ctxi:133
; Node link reuse in CodePrimaryWrapped
dec EAX
add EAX, dword [EBP+8]
mov AL, byte [EAX]
push EAX
push dword [@@DATA+44]
call @10106 ; str_has_char
Пример 3.
В этом примере генератор кода понимает, что можно повторно использовать константу в EAX, но не понимает, что можно повторно использовать указатель в EBX.
Для оптимизации использования указателя необходим анализ, какие переменные могут измениться при сохранении значения регистра, а какие - не могут. Так как сейчас такой анализ не реализован, то любая запись в память сбрасывает привязку вычисленных выражений.
mov EAX, 100000
mov EBX, dword [EBP-8]
mov dword [EBX+44], EAX
; #line compiler_dict.ctxi:117
; Node link reuse in Code_ASSIGN (1)
mov EBX, dword [EBP-8]
mov dword [EBX+32], EAX
; #line compiler_dict.ctxi:118
; Node link reuse in Code_ASSIGN (1)
mov EBX, dword [EBP-8]
mov dword [EBX+36], EAX
; #line compiler_dict.ctxi:119
; Node link reuse in Code_ASSIGN (1)
mov EBX, dword [EBP-8]
mov dword [EBX+40], EAX
; #line compiler_dict.ctxi:120
; Node link reuse in Code_ASSIGN (1)
mov EBX, dword [EBP-8]
mov dword [EBX+12], EAX
; #line compiler_dict.ctxi:121
; Node link reuse in Code_ASSIGN (1)
mov EBX, dword [EBP-8]
mov dword [EBX+16], EAX
; #line compiler_dict.ctxi:122
; Node link reuse in Code_ASSIGN (1)
mov EBX, dword [EBP-8]
mov dword [EBX+20], EAX
; #line compiler_dict.ctxi:123
; Node link reuse in Code_ASSIGN (1)
mov EBX, dword [EBP-8]
mov dword [EBX+24], EAX
Примеры 4, 5, 6.
Устранение загрузок в условных выражениях:
if rs >= BRACKET_LEX_SIZE | rs < 1 then
StopInternal(__FILE__, __LINE__);
end
mov EAX, dword [EBP-8]
cmp EAX, 3
jae @11156
; Node link reuse in CodePrimaryWrapped
cmp EAX, 1
jae @11155
@11156:
; #line frontend_syn_brackets.ctxi:40
push dword 40
push dword @@ROLITERALS+7664
call @10235 ; StopInternal
@11155:
В теле цикла после проверки условия цикла:
while i < nOperator do
word j = i + 1;
...
mov EAX, dword [EBP-4]
cmp EAX, dword [@@DATA+12180364]
jae @11180
; #line frontend_syn_operators.ctxi:66
; Node link reuse in CodePrimaryWrapped
inc EAX
mov dword [EBP-8], EAX
while i < nOperator do
if Operator[i].Prio > Prio then
...
mov EAX, dword [EBP-8]
cmp EAX, dword [@@DATA+12180364]
jae @11197
; #line frontend_syn_operators.ctxi:120
; Node link reuse in CodePrimaryWrapped
imul EAX, 36
mov EAX, dword [@@DATA+EAX+12178080]
cmp EAX, dword [EBP+12]
jbe @11198
