Дикий ум - Генерация и оптимизация кода в компилятора (часть 1)

<b>Дикий ум</b> - Генерация и оптимизация кода
в компилятора (часть 1)

Генерация и оптимизация кода
       Генерация и оптимизация кода
              в компиляторах
Andrew771 
     
          Оптимизация - тема для отдельной
       статьи, а генерация  кода - занятие
       для самоубийцы.

          М. Черкашин"Компилятор  пишется
      так..."
     
  Вот  эту  отдельную  статью с описанием
"самоубийства" я и решил написать сегодня.
Описание   будет  основываться  на  опыте,
полученном  мною при создании кросс-компи─
лятора  усечённого  языка программирования
Паскаль для  компьютера  ZX Spectrum - ZX 
Like Pascal.Некоторые описанные вещи,ско─ 
рее  всего, являются "изобретением велоси─
педа". Но с сожалением могу отметить,что в
большом  количестве литературы по компиля─
торостроению  генерации и оптимизации кода
касаются  мало. В  основном  на  последних
главах бегло, часто для какой-нибудь выду─
манной виртуальной машины,из которой чита─
телю  уже  будет необходимо самостоятельно
дописать  конвертер  полученного пи-кода в
ассемблер  для конкретного компьютера. Оп─
тимизацию же описывают только в общих чер─
тах в словесной форме. Я же сделаю на этом
упор.
     
     Кросс-компилятор ZX Like Pascal
     
   Кросс-компилятор ZX Like Pascal написан
на Delphi и предназначен, прежде всего,для
написания  игр на Спектруме, поэтому в нём
реализовано  в основном только необходимое
для игр. Также накладывают отпечаток огра─
ничения по памяти и быстродействию,т.к. ZX
Spectrum - 8-битная ретро-машина. Компиля─ 
ция производится в текст ассемблера Z80.
   На  данный момент поддерживаются только
типы Byte, Word, String[N], одномерные  и
двумерные массивы этих типов,процедуры без
параметров. Выход  за  пределы  допустимых
значений переменных и массивов не отслежи─
вается,за ними должен следить программист.
Это  сделано для увеличения быстродействия
программ.
   Имеются   встроенные  операторы  вывода
окон, познакоместных  спрайтов и двумерных
карт  из  элементов-спрайтов. Карты  могут
представлять  собой  ландшафты, лабиринты,
игровые  поля.  Имеется  также  встроенный
оператор поиска элементов на карте по раз─
личным критериям. Карта задается в двумер─
ном  массиве, байт  на клетку. В программе
может быть несколько карт, соответствующих
нескольким массивам.
   Вывод текста,спрайтов и карт можно осу─
ществлять как с атрибутами, так и без них,
а также можно осуществлять как непосредст─
венно на экран, так и на виртуальный экран
в памяти для последующего вывода на реаль─
ный  экран. Виртуальный экран используется
для построения  в памяти изображения и его
быстрого  вывода на экран целиком, для ис─
ключения мерцания экрана.
   В  процессе  создания  компилятора мною
был  выбран  метод  рекурсивного спуска по
исходному  коду  на Паскале, основанный на
"зашивании" правил  грамматики непосредст─
венно  в управляющие конструкции распозна─
вателя. Общий принцип состоит в следующем.
Мы идем по последовательности токенов, по─
лученных при лексическом анализе,слева на─
право. Токены (или лексемы) - это ключевые
слова,  числа, строки, разделители - одним
словом,допустимые "символы" языка высокого
уровня  (ЯВУ). При этом для каждого токена
проверяем, можем  ли  мы уже сгенерировать
код  для  него, или же токен подразумевает
дополнительные  токены  (как бы параметры)
для  себя. В  первом случае мы генерируем.
кусок кода и переходим на следующий токен.
Во  втором  случае  начинаем рассматривать
следующий  токен, спускаясь  рекурсивно по
токенам. И так идем до тех пор,пока не уч─
тём все токены-параметры для первоначально
вызвавшего их токена.На каждом шаге мы за─
одно проверяем наличие синтаксических оши─
бок.Умными словами - наш процесс называет─
ся парсингом, а если изображать его графи─
чески, то это синтаксическое дерево разбо─
ра.
   Рекурсивным  спуском  мы  распознаем не
только программный код,но и арифметические
и логические выражения,объявления перемен─
ных, констант  и  типов. При распознавании
переменные  и константы вносятся в таблицу
переменных,в которой содержится для каждой
из  них имя, тип, допустимый диапазон (для
индексированных переменных  -  массивов  и
строк), значение (для констант).
     
Разбор операторов и генерация кода для них 
     
   Как  показала  практика, генерацию кода
при разборе лучше производить не непосред─
ственно в ассемблер, а в промежуточныйпи-
код. Пи-код позволит,во-первых,абстрагиро─
ваться  от реального процессора и его сис─
темы команд, что важно при разработке ком─
пилятора для процессоров разного типа,впо─
следствии  написав для каждого из них кон─
вертер (постпроцессор) в конкретный ассем─
блер. Во-вторых, самое главное, пи-код по─
зволит  произвести эффективную оптимизацию
кода, намного лучшую, чем ассемблер.
   Пи-код - это не просто замена имени ка─
ждой команды ассемблера, а это команды ло─
гически завершённых,но небольших действий.
Каждая  команда пи-кода может быть эквива─
лентна одной или нескольким командам ассе─
мблера, но  для  некоторых необходимо даже
вызывать  ассемблерные процедуры  из  биб─
лиотеки (например, для  умножения, деления
чисел, вывода на экран,чтения клавиатуры и
т.д.). Выбор списка необходимых команд за─
висит  целиком  от  создателя компилятора,
здесь нужно  соблюсти  некий  баланс по их
количеству,т.к. затем по их сочетаниям по─
сле генерации будет производится оптимиза─
ция.Если взять слишком много команд,то бу─
дет очень много сочетаний, что усложнит их
учёт при оптимизации. Если же мало,то либо
их будет недостаточно для разбора констру─
кций ЯВУ, либо оптимизаций будет мало.
   Я выбрал  следующие  команды пи-кода ZX
Like Pascal (для  каждой  команды  имеется 
два параметра - число и строка):

Команда пи-кода
          Эквивалентный код
          на ассемблере (для двух-
          байтового представления)
                                 Описание
Call (0,label)
            call label
                    вызов процедуры по ме─
                    тке label
Return (0,'')
            ret
                    возврат из процедуры
Push (0,'')
            push hl
                    помещение  регистра  в
                    стек
LoadConst (number,'')
            ld hl,number
                    чтение  значения конс─
                    танты number в регистр
LoadNumber (0,'')
            ld e,(hl)
            inc hl
            ld d,(hl)
            ex de,hl
                    чтение значения ячейки
                    памяти (числовой пере─
                    менной)  с адреса, за─
                    данным  в  регистре, в
                    регистр
LoadLabel (0,label)
            ld hl,label
                    поместить  адрес метки
                    label в регистр
PopStoreNumber (0,'')
            pop de
            ld (hl),e
            inc hl
            ld (hl),d
                    запись   значения   со
                    стека  в ячейку памяти
                    (числовую  переменную)
                    по адресу, заданному в
                    регистре
StoreString (0,'')
            ex de,hl
            ld hl,string_buffer
            ld c,(hl)
            ld b,0
            ldir
                    запись  строки в стро─
                    ковую  переменную (об─
                    ласть  памяти) с адре─
                    сом, заданным в регис─
                    тре, из буфера строки
ResetString (0,'')
            ld (hl),0
                    очистка  строковой пе─
                    ременной  (области па─
                    мяти) с адресом,задан─
                    ным  в  регистре  (ус─
                    тановка  нулевой длины
                    строки)
PopAdd (0,'')
            pop de
            add hl,de
                    сложение  значения  со
                    стека  с  регистром  и
                    помещение в регистр
PopSub (0,'')
            pop de
            ex de,hl
            and a
            sbc hl,de
                    вычитание  регистра из
                    значения  со стека ре─
                    гистра  и  помещение в
                    регистр;эта же команда
                    используется для срав─
                    нения значений стека и
                    регистра
PopMul (0,'')
            pop de
            call mul(библ.)
                    умножение  значения со
                    стека на регистр и по─
                    мещение в регистр
PopDiv (0,'')
            pop de
            ex de,hl
            call div(библ.)
                    деление   значения  со
                    стека на регистр и по─
                    мещение в регистр
PopMod (0,'')
            pop de
            ex de,hl
            call div(библ.)
            ex de,hl
                    остаток   от   деления
                    значения  со  стека на
                    регистр  и помещение в
                    регистр
PutLabel (0,label)
            label
                    запись  метки  label в
                    код
JumpTo (0,label)
            jp label
                    безусловный переход на
                    метку label
IfLessTo (0,label)
            jp c,label
                    переход  по  условию C
                    на метку label
IfEqualMoreTo (0,label)
            jp nc,label
                    переход  по условию NC
                    на метку label
IfEqualTo (0,label)
            jp z,label
                    переход  по  условию Z
                    на метку label
IfNotEqualTo (0,label)
            jp nz,label
                    переход  по условию NZ
                    на метку label

   Также  понадобятся следующие библиотеч─
ные процедуры,вызываемые командойCall (0,
name_procedure):

 -конкатенация (сложение) в буфер строки
строковой  переменной  (области  памяти) с 
адресом, заданным в регистре; 
 -вывод значения регистра (числа) на эк─
ран; 
 -вывод  строки  из буфера строки на эк─
ран; 
 -чтение символа с клавиатуры и запись в
буфер строки; 
 -конвертирование строки из буфера стро─
ки в число и помещение в регистр; 
 -конвертирование значения регистра (чи─
сла) в строку и помещение в буфер строки; 
 -очистка экрана;
 -установка  цвета бордюра значением ре─
гистра; 
 -установка  атрибутов  экрана значением
регистра; 

   и т.д. (можно добавлять любые,в зависи─
мости от операторов ЯВУ).

   Все конструкции ЯВУ составляются из ко─
мбинаций  только  этих команд пи-кода. Для
некоторых  операторов  Паскаля могут также
вызываться  ассемблерные процедуры из биб─
лиотеки  процедур  по команде пи-кодаCall
(0,name_procedure).
   Под регистром на настоящий момент пони─
мается  регистровая  пара hl для числовых
переменных. Хотя если будет введен, напри─
мер, тип LongInt, то  уже потребуется две
регистровых пары для него.Или наоборот,для
однобайтовых  значений можно подразумевать
регистр a (аккумулятор). В ZX Like Pascal
сейчас  все вычисления выражений  произво─
дятся только в двухбайтовом представлении,
даже для однобайтовых величин.
   Строки  в ZX Like Pascal имеют длину не
более 255  символов, в  том числе и буфер
строки. Первый байт содержит длину строки,
далее подряд идут коды символов. Для очис─
тки строки достаточно обнулить ее длину.
   Используем только одну регистровую пару
hl, т.к.только она позволяет в полном объ─
ёме  производить  арифметические операции,
операции с памятью  и т.д. К сожалению, на
Спектруме  она только одна такая. В совре─
менных  компьютерах  большинство регистров
равноценно по операциям,что широко исполь─
зуется  в  современных компиляторах. Мы же
будем оперировать одним, забрасывая другие
используемые в данный момент числовые зна─
чения в стек.Поэтому у нас будет образовы─
ваться много ассемблерных командpush/pop.
Тем не менее,на стадии оптимизации я пока─
жу, как эффективно избавиться от них. Сей─
час наша задача - сгенерировать работающий
код, не обращая внимания на оптимальность.
   Рассмотрим на примере,как разбирается и
генерируется код для оператораfor:
for index:=<expression1> to <expr.2> do
       <statement>
     
   Сначала  задумываем шаблон на ассембле─
ре, в который преобразуется наш оператор.
  (расчёт выражения <expression 1>, резу─
льтат в hl)
       ld (Index),hl
  (расчёт выражения <expression 2>, резу─
льтат в hl)
       ld (Limit),hl
L001    ld hl,(Index)
       push hl
       ld hl,(Limit)
        ; сравнение hl и (sp)
       pop de
       ex de,hl
       and a
       sbc hl,de
        ; конец сравнения
       jp c,L002
  (выполнение <statement>)
       ld hl,(Index)
       inc hl
       ld (Index),hl
       jp L001
L002


   Или  после  конвертации на пи-код (если
вы  способны  мыслить на пи-коде, то лучше
сразу делать шаблон на нем, чтобы избежать
лишней конвертации):
  (расчёт выражения <expression 1>, резу─
льтат в hl)
       Push (0,'')
       LoadLabel (0,Index)
       PopStoreNumber (0,'')
  (расчёт выражения <expression 2>, резу─
льтат в hl)
       Push (0,'')
       LoadLabel (0,Limit)
       PopStoreNumber (0,'')
       PutLabel (0,'L001')
       LoadLabel (0,Index)
       LoadNumber (0,'')
       Push (0,'')
       LoadLabel (0,Limit)
       LoadNumber (0,'')
       PopSub (0,'')
       IfLessTo (0,'L002')
  (выполнение <statement>)
       LoadLabel (0,Index)
       LoadNumber (0,'')
       Push (0,'')
       LoadConst (1,'')
       PopAdd (0,'')
       Push (0,'')
       LoadLabel (0,Index)
       PopStoreNumber (0,'')
       JumpTo (0,'L001')
       PutLabel (0,'L002')

   Словесные  команды в скобках подразуме─
вают  рекурсивный вызов процедур обработки
других операторов или выражений. Рекурсив─
ный, потому что мы сейчас сами находимся в
процедуре  обработки оператора в коде ком─
пилятора. Назовем еёStatement.
   Теперь "зашьём" этот  шаблон в код ком─
пилятора.Процедура синтаксического анализа
оператораfor будет выглядеть так:
     
 -считываем токен'for';
 -генерируем новое имя метки в строковую
переменнуюLoopLabel(но пока не записыва─ 
ем её в генерируемый код); 
 -генерируем новое имя метки в строковую
переменнуюDoneLabel(но пока не записыва─ 
ем её в генерируемый код); 
 -считываем  следующий токен - имя пере─
менной-счётчика цикла в строковую перемен─ 
нуюIndex;
 -строковая переменнаяLimitравна'Lim'
+Index;
 -считываем токен присваивания':=';
 -вызываем процедуру разбора арифметиче─
ских выраженийExpression,которая запишет 
в пи-код необходимые команды; 
 -записываем в пи-код команду
Push (0,'');
 -записываем в пи-код команду
LoadLabel (0,Index), вместо имени перемен─
нойIndexподставится её значение; 
 -записываем в пи-код команду
PopStoreNumber (0,'');
 -считываем  токен'to'(если у нас реа─
лизовано  и'downto',то тут начнётся аль─ 
тернатива для него в коде компилятора); 
 -вызываем процедуру разбора арифметиче─
ских выраженийExpression,которая запишет 
в пи-код необходимые команды; 
 -записываем в пи-код команду
Push (0,'');
 -записываем в пи-код команду
LoadLabel (0,Limit);
 -записываем в пи-код команду
PopStoreNumber (0,'');
 -записываем в пи-код команду
PutLabel (0,LoopLabel);
 -записываем в пи-код команду
LoadLabel (0,Index);
 -записываем в пи-код команду
LoadNumber (0,'');
 -записываем в пи-код команду
Push (0,'');
 -записываем в пи-код команду
LoadLabel (0,Limit);
 -записываем в пи-код команду
LoadNumber (0,'');
 -записываем в пи-код команду
PopSub (0,'');
 -записываем в пи-код команду
IfLessTo (0,DoneLabel);
 -считываем токен'do';
 -вызываем  рекурсивно процедуру разбора
операторов Statement,которая  запишет  в 
пи-код необходимые команды (в ней, кстати, 
могут  попасться и другие вложенные опера─ 
торыfor); 
 -записываем в пи-код команду
LoadLabel (0,Index);
 -записываем в пи-код команду
LoadNumber (0,'');
 -записываем в пи-код команду
Push (0,'');
 -записываем в пи-код команду
LoadConst (1,'');
 -записываем в пи-код команду
PopAdd (0,'');
 -записываем в пи-код команду
Push (0,'');
 -записываем в пи-код команду
LoadLabel (0,Index);
 -записываем в пи-код команду
PopStoreNumber (0,'');
 -записываем в пи-код команду
JumpTo (0,LoopLabel);
 -записываем в пи-код команду
PutLabel (0,DoneLabel).
     
   Процедура  синтаксического анализа опе─
ратора  for  (наименование   процедуры  -
for_loop ) вызывается процедурой обработки
операторов Statement  при  встрече токена
for.
   Процедура Statement  является "центро─
вой", её  задача - определить токен опера─
тора и передать управление на его процеду─
ру синтаксического анализа:
     
procedure Statement;
begin
case Current_Token of
   _while: while_loop;
   _repeat: repeat_loop;
   _for: for_loop;
   _if: if_then_else;
   _case: case_op;
   _begin: BlockStatement;
   _write: write_work;
   ...
else
   assignment;//если не токен оператора,
                //то вероятно присваивание
end;
     
   А вот  как выглядит процедура обработки
нашего  оператораfor_loop, в соответствии
с вышеописанным алгоритмом:
     
procedure for_loop;
var
 DoneLabel,LoopLabel,Index,Limit: string;
begin
 Match(_for);
 LoopLabel:=NewLabel;
 DoneLabel:=NewLabel;

 Index:=GetName;
 Limit:='Lim'+Index;
 if LookIdName(Limit)=-1 //добавляем в
                      //таблицу переменных
  then AddSymbol(Limit,_Word,True,0,0,0);

 Match(_assign);
 Expression;
 case TypeVariable(Index) of
    _Byte,_Word:
      begin
      GenCode('Push',0,'');
      GenCode('LoadLabel',0,Index);
      GenCode('PopStoreNumber',0,'');
               end;
 else Abort('Uncompatible type');
 end;

 case Current_Token of
 _to:
  begin
      Match(_to);
      Expression;
      GenCode('Push',0,'');
      GenCode('LoadLabel',0,Limit);
      GenCode('PopStoreNumber',0,'');
      GenCode('PutLabel',0,LoopLabel);
      GenCode('LoadLabel',0,Index);
      GenCode('LoadNumber',0,'');
      GenCode('Push',0,'');
      GenCode('LoadLabel',0,Limit);
      GenCode('LoadNumber',0,'');
      GenCode('PopSub',0,'');
      GenCode('IfLessTo',0,DoneLabel);
      Match(_do);
      Statement;
      GenCode('LoadLabel',0,Index);
      GenCode('LoadNumber',0,'');
      GenCode('Push',0,'');
      GenCode('LoadConst',1,'');
      GenCode('PopAdd',0,'');
      GenCode('Push',0,'');
      GenCode('LoadLabel',0,Index);
      GenCode('PopStoreNumber',0,'');
      GenCode('JumpTo',0,LoopLabel);
  end;
 _downto:
  begin
      Match(_downto);
      Expression;
       ...
  end;
  else Abort('DO or DOWNTO expected');
 end;

 GenCode('PutLabel',0,DoneLabel);

end;
     
   Аналогично  строятся процедуры для дру─
гих операторов - сначала создаём шаблон на
ассемблере/пи-коде, затем встраиваем его в
код компилятора, формируя необходимые кон─
струкции операторов и вызовов процедур,ге─
нерируя новые метки и переменные.
     
 Разбор выражений и генерация кода для них
     
   Разбор выражений (арифметических, логи─
ческих) происходит также рекурсивным спус─
ком,который вызывается в нашем компиляторе
процедурой Expression. Рекурсивные вызовы
здесь определяют приоритеты операций в вы─
ражении; чем  приоритет операции выше, тем
глубже  находится  вызов  процедуры для её
обработки.Например,мы встретили выражение:
2+3*5. Сложение у нас в начале, но умноже─
ние выше по приоритету, чем сложение. Поэ─
тому  при  анализе  сложения сначала будут
вызваны  процедуры проверки всех вышестоя─
щих приоритетных операций, в том числе ум─
ножение,а потом уже будет возврат к сложе─
нию.
   Каждый встреченный в выражении аргумент
заносится в стек, т.к. заранее неизвестно,
что  с ним делать - мы последовательно чи─
таем токены. А каждая операция над аргуме─
нтами сначала читает значение со стека.
   Если отбросить нюансы, то общий принцип
построения  процедур распознавания выраже─
ний таков:
     
   ПроцедураExpression:
 -читаем токен;
 -вызываем процедуруSimpleExpression;
 -вызываем  процедуру  сравнения со сте─
ком,если токен соответствует одной из этих 
операций (в ней будет  генерация пи-кода с 
командойPopSub). 
     
   ПроцедураSimpleExpression:
 -вызываем процедуруTerm;
 -вызываем  процедуру сложения или вычи─
тания  со стеком, если токен соответствует 
одной из этих  операций (генерация пи-кода 
с командамиPopAdd, PopSub). 
     
   ПроцедураTerm:
 -вызываем процедуруFactor;
 -вызываем  процедуру умножения, деления
или остатка от деления со стеком, если то─ 
кен  соответствует  одной из этих операций 
(генерация  пи-кода  с  командами PopMul,
PopDiv, PopMod ).
     
   ПроцедураFactor:
 -если  токен - левая круглая скобка, то
рекурсивно  вызываем процедуруExpression,
а затем ожидаем правую круглую скобку; 
 -если  токен - имя переменной или конс─
танты (определяем  по таблице переменных), 
то  генерируем  пи-код  чтения её значения 
(генерация  пи-кода с командамиLoadLabel,
LoadConst, LoadNumber, LoadString );
 -если  токен - имя  массива  или записи
(определяем по таблице переменных), то вы─ 
зываем процедуруSelector.

   ПроцедураSelector:
 -читаем токен;
 -если  токен - левая квадратная скобка,
то в цикле для каждого индекса массива ре─ 
курсивно  вызываем  процедуру Expression,
ожидаем правую квадратную скобку,генериру─ 
ем пи-код расчёта адреса для элемента мас─ 
сива и чтения его значения; 
 -если токен - точка,то читаем следующий
токен, если он - имя поля записи, то гене─ 
рируем  пи-код расчёта адреса для поля за─ 
писи и чтения его значения. 
     
   В итоге  работы  процедурыExpression и
всех вложенных процедур будет сгенерирован
пи-код, в конце  которого в регистре будет
рассчитанное значение выражения.
   В ZX Like Pascal разрешены только одно─
мерные и двумерные массивы.
   Адрес для ячейки для одномерного масси─
ва рассчитывается так:
addr(i) = addr(1)+(i-1)*size
   Для двумерного массива:
addr(i,j) = addr(1)+(max(i)-1)*(j-1)*size
   где:
 - addr(1)- адрес начала массива (перво─
го элемента); 
 - size- размер элемента в байтах, соот─
ветствует типу массива; 
 - max(i)- максимальное значение индекса
i в массиве.
     
   Для записей будет аналогично,только ну─
жно учесть, что у каждого поля записи свой
размерsize.
   Реализация в компиляторе чтения элемен─
та для одномерного или двумерного массива,
в соответствии с вышеприведёнными формула─
ми:
     
proc_i:=LookIdName(current_name);
 //находим ID массива в таблице переменных
Match(_lsqbkt); //ожидаем левую квадратную
                //скобку
if SymbolTable[proc_i].CountIndex=2 then
                //если двумерный массив
   begin
     Expression;
     GenCode('Push',0,'');
     GenCode('LoadConst',1,'');
     GenCode('PopSub',0,'');
     GenCode('Push',0,'');
     GenCode('LoadConst',
     SymbolTable[proc_i].Index2Size,'');
     GenCode('PopMul',0,'');
     Match(_comma);//ожидаем запятую
   end
else GenCode('LoadConst',0,'');
GenCode('Push',0,'');
Expression;
GenCode('Push',0,'');
GenCode('LoadConst',1,'');
GenCode('PopSub',0,'');
GenCode('PopAdd',0,'');
GenCode('Push',0,'');
GenCode('LoadLabel',0,current_name);
GenCode('PopAdd',0,'');
Match(_rsqbkt); //ожидаем правую
                //квадратную скобку
if LookTypeName(current_name)='String'
             //если переменная типа String
     then GenCode('Call',0,'load_string')
     else GenCode('LoadNumber',0,'');

 (про оптимизацию см. в следующей статье)