Wild Mind - Code generation and optimization in the compiler (part 1)

Code generation and optimization
 Code generation and optimization
              in compilers
Andrew771 
     
          Optimization is a topic for a separate
       articles, and code generation is an activity
       for a suicide.

          M. Cherkashin"The compiler is written
so..."
     
 Here is this separate article with a description
"suicide" I decided to write today.
The description will be based on experience
obtained by me when creating a cross-computer─
lator of a truncated programming language
Pascal for the ZX Spectrum computer - ZX 
Like Pascal.Some of the things described─ 
most likely, they are "the invention of the bicycle"
peda". But with regret I can note that in
a large amount of literature on the compile─
hull buildingcode generation and optimization
touch a little. Mainly on the latter
chapters fluently, often for some purpose─
manna virtual machine from which to read─
the body will need to independently
add the converter of the resulting pi code to
assembler for a specific computer. Op─
timization is described only in general terms─
tah in verbal form. I'll do it on this
stop.
     
     Cross compiler ZX Like Pascal
     
   ZX Like Pascal cross compiler written
in Delphi and is intended primarily for
writing games on the Spectrum, so in it
Mostly only what is necessary has been implemented
for games. Also leaves an ogre imprint─
differences in memory and performance, because ZX
Spectrum is an 8-bit retro machine. Compilation─ 
tion is produced into the Z80 assembler text.
   Currently only supported
types Byte, Word,String[N], one-dimensional and
two-dimensional arrays of these types, procedures without
parameters. Exceeding the limits
do not track the values of variables and arrays─
It turns out that the programmer must monitor them.
This is done to increase performance
programs.
   There are built-in output operators
windows, familiar sprites and two-dimensional
maps from sprite elements. Cards can
represent landscapes, labyrinths,
playing fields.  There is also a built-in
operator for searching elements on the map by time─
personal criteria. The map is specified in two dimensions─
nom array, bytes per cell. In the program
there may be several cards corresponding
several arrays.
   You can output text, sprites and maps─
act both with and without attributes,
and can also be carried out directly
both on the screen and on the virtual screen
in memory for subsequent output to real life─
ny screen. Virtual screen in use
to build an image in memory and its
quick display of the entire screen, for use─
turn on screen flickering.
   In the process of creating a compiler by me
the recursive descent method was chosen
source code in Pascal, based on
"tweaking" the rules of grammar directly─
recognized in control structures─
vatela. The general principle is as follows.
We follow the sequence of tokens, by─
obtained during lexical analysis, on the left on─right. Tokens (or lexemes) are key
words, numbers, lines, separators - one
in a word, acceptable "symbols" of a high language
level (YAVU). Moreover, for each token
check if we can already generate
code for it, or does the token mean
additional tokens (like parameters)
for yourself. In the first case we generate.
piece of code and move on to the next token.
In the second case, we begin to consider
next token, descending recursively along
tokens. And so we go until we learn─
then all token parameters for initially
the token that called them. At every step we are for─
one thing we check for syntax errors─
side. In clever words - our process calls─
using parsing, but if you depict it graphically─
chesically, then this syntax tree is broken down─
ra.
   By recursive descent we recognize not
only program code, but also arithmetic
and logical expressions, declarations of changes─
nal, constant and types. When recognizing
variables and constants are entered into the table
variables, which contains for each
of which name, type, valid range (for
indexed variables - arrays and
strings), value (for constants).
     
Parsing operators and generating code for them 
     
   As practice has shown, code generation
when disassembling it is better to do it not directly─
primarily in assembler, and in intermediatepi-
code.Pi-code will allow, firstly, abstraction─
depending on the real processor and its system─
command topics, which is important when developing a company─
peeler for different types of processors, vpo─
consequently, writing for each of them a con─
verter (post-processor) into a specific assembly─
Blair. Secondly, and most importantly, the pi code is
allows for effective optimization
code much better than assembler.
   Pi-code is not just a replacement for the name ka─
every assembler command, and these are lo─
logically completed but small actions.
Each pi code command can be equivalent─
tape to one or more access commands─
bller, but for some it is even necessary
call assembly procedures from bib─
library (for example, for multiplication, division
numbers, screen output, keyboard reading and
etc.). Selecting a list of required commands for─
hangs entirely from the compiler creator,
here you need to maintain some balance according to their
quantity, because then according to their combinations
After generation, optimization will be performed─
tion. If you take too many commands, then boo─
there are a lot of combinations, which will complicate them
taken into account during optimization. If it’s not enough, then either
they will not be enough to disassemble the design─
tions of a nuclear power plant, or there will be few optimizations.
   I have selected the following ZX pi code commands
Like Pascal (for each command there is 
two parameters - a number and a string):

Pi code command
 Equivalent code
 in assembler (for two-
 byte representation)
 Description
Call (0,label)
 call label
 procedure call by me─
                    tke label
Return (0,'')
 ret
 return from procedure
Push (0,'')
 push hl
 placing the register in
                    stack
LoadConst (number,'')
 ld hl,number
 reading the value of cons─
                    tant number to register
LoadNumber (0,'')
 ld e,(hl)
 inc hl
ld d,(hl)
 ex de,hl
reading the cell value
                    memory (numerical re─
                    mine) from the address for─
                    data in the register, in
                    register
LoadLabel (0,label)
 ld hl,label
 place the label address
                    label to register
PopStoreNumber (0,'')
 pop de
 ld (hl),e
 inc hl
 ld (hl),d
 record value with
                    stack to memory location
                    (numeric variable)
                    at the address specified in
                    register
StoreString (0,'')
 ex de,hl
 ld hl,string_buffer
ld c,(hl)
 ld b,0
 ldir
 writing a string to a string─
                    kovy variable (about─
                    memory space) from address─
                    som specified in registry─
                    tre, from line buffer
ResetString (0,'')
 ld (hl),0
 clearing string ne─
                    belt (area pa─
                    mint) with address given─
                    nom in the register (us─
                    zero length tanning
                    lines)
PopAdd (0,'')
 pop de
 add hl,de
 adding a value with
                    stack with register and
                    placement in the register
PopSub (0,'')
 pop de
 ex de,hl
 and a
 sbc hl,de
 subtract case from
                    values from stack re─
                    hysteria and placement in
                    register;same command
                    used for comparison
                    different stack values and
                    register
PopMul (0,'')
 pop de
 call mul(bibl.)
 multiplying the value with
                    stack per register and by─
                    placement in the register
PopDiv (0,'')
 pop de
 ex de,hl
 call div(bibl.)
 dividing the value with
                    stack per register and by─
                    placement in the register
PopMod (0,'')
 pop de
 ex de,hl
 call div(bibl.)
 ex de,hl
 division remainder
                    values from stack to
                    register and room in
                    register
PutLabel (0,label)
 label
 writing label to
                    code
JumpTo (0,label)
jp label
 unconditional transition to
                    label
IfLessTo (0,label)
 jp c,label
 transition by condition C
                    to the label
IfEqualMoreTo (0,label)
 jp nc,label
 transition based on NC condition
                    to the label
IfEqualTo (0,label)
jp z,label
 transition based on Z condition
                    to the label
IfNotEqualTo (0,label)
 jp nz,label
 transition by condition NZ
                    to the label

   You will also need the following libraries─
special procedures called by the commandCall (0,
name_procedure):

 -concatenation (addition) into a string buffer
string variable (memory area) with 
the address specified in the register; 
 -output the register value (number) to eq─
wounds; 
 -outputting a line from the line buffer to eq─
wounds; 
 -reading a character from the keyboard and writing to
linebuffer; 
 -converting a string from the string buffer─
ki in number and placement in register; 
 -converting register value (chi─
sl) to a string and placing it in the string buffer; 
 -screen cleaning;
 -setting the border color with the re value─
hystra; 
 -setting screen attributes by value
register; 

   etc. (you can add any, depending─
from nuclear power operators).

   All designs of nuclear power plants are made up of co─
combinations of only these pi code commands. For
some Pascal operators can also
assembler procedures are called from bib─
libraries of procedures by pi-code commandCall
(0,name_procedure).
Under register at the moment pony─
register pair hl for numeric
variables. Although if it is introduced, for example─
measures, type LongInt, then you will need two
register pairs for it. Or vice versa, for
single-byte values can be implied
registera (accumulator). In ZX Like Pascal
now all calculations of expressions are arbitrary─
are only in two-byte representation,
even for single-byte values.
   Lines in ZX Like Pascal are not long
more than 255 characters, including buffer
lines. The first byte contains the length of the string,Then there are character codes in a row. For cleaning─
For a string it is enough to reset its length to zero.
   We use only one register pair
hl, because only it allows full volume ─
we can perform arithmetic operations,
memory operations, etc. Unfortunately, on
There is only one of these on the Spectrum. In modern times─
on portable computers most registers
equivalent in operations that are widely used─
is used in modern compilers. We are
we will operate with one, neglecting the others
currently used numerical values─
stacked. Therefore, we will have educational─
There are a lot of assembler commandspush/pop.
However, I’m still at the optimization stage─
I'm wondering how to effectively get rid of them. This─
hour our task is to generate a working
code without paying attention to optimality.
   Let's look at an example of how to understand and
code is generated for the operatorfor:
for index:= to  do
 
     
   First we conceive the template in assembly─
re, into which our operator is converted.
 (calculation of expression , res─
льтат в hl)
       ld (Index),hl
  (расчёт выражения , резу─
льтат в 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
  (выполнение )
       ld hl,(Index)
       inc hl
       ld (Index),hl
       jp L001
L002


 Or after converting to pi code (if
you are able to think in pi code, then it's better
immediately make a template on it to avoid
unnecessary conversion):
 (calculation of expression , res─
ltat in hl)
 Push (0,'')
 LoadLabel (0,Index)
 PopStoreNumber (0,'')
 (calculation of expression , res─
ltat in 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')
  (выполнение )
       LoadLabel (0,Index)
       LoadNumber (0,'')
       Push (0,'')
       LoadConst (1,'')
       PopAdd (0,'')
       Push (0,'')
       LoadLabel (0,Index)
       PopStoreNumber (0,'')
       JumpTo (0,'L001')
       PutLabel (0,'L002')

   Словесные  команды в скобках подразуме─
вают  рекурсивный вызов процедур обработки
других операторов или выражений. Рекурсив─
ный, потому что мы сейчас сами находимся в
процедуре  обработки оператора в коде ком─peeler Let's call itStatement.
 Now let's "sew" this template into code com─
Pilator.Parsing procedure
operatorfor will look like this:
     
 -read token'for';
 -generate a new label name in a string
variableLoopLabel(but not yet written─ 
I add it to the generated code); 
 -generate a new label name into a string
variableDoneLabel(but not yet written─ 
I add it to the generated code); 
 -read the next token - rename
variable-counter loop into string variable─ 
newIndex;
 -string variableLimitequal'Lim'
+Index;
 -read the assignment token':=';
 -call the arithmetic parsing procedure─
Chinese expressionsExpressionwhich will write 
in pi code the necessary commands; 
 -write the command to the pi code
Push (0,'');
 -write the command to the pi code
LoadLabel (0,Index), instead of the variable name─
noyIndexits value will be substituted; 
 -write the command to the pi code
PopStoreNumber (0,'');
 -read the token'to'(if we have rea─
lyzed and'downto',then the al will begin─ 
an alternative for it in the compiler code); 
 -call the arithmetic parsing procedure─
Chinese expressionsExpressionwhich will write 
in pi code the necessary commands; 
 -write the command to the pi code
Push (0,'');
 -write the command to the pi code
LoadLabel (0,Limit);
 -write the command to the pi code
PopStoreNumber (0,'');
 -write the command to the pi code
PutLabel (0,LoopLabel);
 -write the command to the pi code
LoadLabel (0,Index);
 -write the command to the pi code
LoadNumber (0,'');
 -write the command to the pi code
Push (0,'');
 -write the command to the pi code
LoadLabel (0,Limit);
 -write the command to the pi code
LoadNumber (0,'');
 -write the command to the pi code
PopSub (0,'');
 -write the command to the pi code
IfLessTo (0,DoneLabel);
 -read the token'do';
 -call the parsing procedure recursively
operators Statement,which will write to 
pi code of the necessary commands (in it, by the way, 
there may be other nested operas─ 
torifor); 
 -write the command to the pi code
LoadLabel (0,Index);
 -write the command to the pi code
LoadNumber (0,'');
 -write the command to the pi code
Push (0,'');
 -write the command to the pi code
LoadConst (1,'');
 -write the command to the pi code
PopAdd (0,'');
 -write the command to the pi code
Push (0,'');
 -write the command to the pi code
LoadLabel (0,Index);
 -write the command to the pi code
PopStoreNumber (0,'');
 -write the command to the pi code
JumpTo (0,LoopLabel);
 -write the command to the pi code
PutLabel (0,DoneLabel).
     
   OP parsing procedure
rator for (procedure name -
for_loop ) is called by the processing procedure
operators Statement when meeting a token
for.
   Procedure Statement is the "center─
howl", herзадача - определить токен опера─
тора и передать управление на его процеду─
ру синтаксического анализа:
     
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;
     
   Procedures are constructed similarly for other
some operators - first we create a template on
assembler/pi code, then embed it in
compiler code, forming the necessary con─
structures of operators and procedure calls, ge─
without adding new labels and variables.
     
 Parsing expressions and generating code for them
     
   Parsing expressions (arithmetic, logs─
chesical) also occurs by recursive descent─
com, which is called in our compiler
procedure Expression. Recursive calls
here determine the priorities of operations in you─
injury; the higher the priority of the operation, the
deeper is the procedure call for it
processing. For example, we came across the expression:
2+3*5. We have addition at the beginning, but multiply─
addition is higher in priority than addition. Poe─
Therefore, when analyzing addition, first there will be
caused byprocedures for checking all superiors─
general priority operations, including the mind─
knife, and then there will be a return to complexity─
nu.
   Each argument encountered in the expression
is pushed onto the stack because unknown in advance
what to do with it - we consistently chi─
melting tokens. And every operation on argume─
ntami first reads the value from the stack.
   If we ignore the nuances, then the general principle
constructing recognition procedures in expressions─
it is as follows:
     
   ProcedureExpression:
 -read token;
 -call the procedureSimpleExpression;
 -call the comparison procedure with ste─
com, if the token matches one of these 
operations (it will generate pi code with 
commandPopSub). 
     
   ProcedureSimpleExpression:
 -call the procedureTerm;
 -call the addition or subtraction procedure─
dealing with the stack if the token matches 
one of these operations (pi-code generation 
withcommandsPopAdd, PopSub). 
     
   ProcedureTerm:
 -call the procedureFactor;
 -call the multiplication and division procedure
or the remainder from division with the stack, if that─ 
ken matches one of these operations 
(pi-code generation with commandsPopMul,
PopDiv, PopMod).
     
   ProcedureFactor:
 -if the token is a left parenthesis, then
recursively call the procedureExpression,
and then expect a right parenthesis; 
 -if the token is the name of a variable or cons─
tants (determined from the table of variables), 
then we generate a pi code for reading its value 
(generation of pi code with commandsLoadLabel,
LoadConst, LoadNumber, LoadString );
 -if token -array or record name
(we determine from the table of variables), then you─ 
call the procedureSelector.

   ProcedureSelector:
 -read token;
 -if the token is a left square bracket,
then in a loop for each index of the array re─ 
in italics we call the procedure Expression,
expect right square bracket, generate─ 
I eat the pi code for calculating the address for the mas element─ 
siwa and reading its meaning; 
 -if the token is a dot, then read the following
token, if it is the name of the record field, then gene─ 
We rewrite the pi-code for calculating the address for the field for─ 
writing and reading its meaning. 
     
   As a result of the procedureExpression and
all nested procedures will be generated
pi code, at the end of which the register will be
the calculated value of the expression.
   In ZX Like Pascal only one thing is allowed─
dimensional and two-dimensional arrays.
   Cell address for one-dimensional mass─
va is calculated as follows:
addr(i) = addr(1)+(i-1)*size
 For a two-dimensional array:
addr(i,j) = addr(1)+(max(i)-1)*(j-1)*size where:
 - addr(1)- address of the beginning of the array (first
th element); 
 - size- element size in bytes, relative─
corresponds to an array type; 
 - max(i)- maximum index value
i in the array.
     
   For records it will be the same, only well─
It is important to note that each field in the record has its own
sizesize.
 Implementation of element reading in the compiler─
that for a one-dimensional or two-dimensional array,
in accordance with the above formula─
mi:
     
proc_i:=LookIdName(current_name);
 //find the array ID in the variable table
Match(_lsqbkt); //waiting for the left square
 //bracket
if SymbolTable[proc_i].CountIndex=2 then
 //if a two-dimensional array
 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); //ожидаемright
 //square bracket
if LookTypeName(current_name)='String'
 //if the variable is a String
 then GenCode('Call',0,'load_string')
 else GenCode('LoadNumber',0,'');

 (about optimization, see the next article)