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

Code optimization
 If you look at the original gene─
pi code translated by our compiler, then we
we will see that it is extremely suboptimal - neither
memory, nor performance. It's very
a lot of calls to the stack, using that─
only one register, a lot of repeated calculations─
mergers, etc. Immediately when parsing operators
we could not generate optimal code,
because looked through every token of the sequence─
strictly, recursively descending defiantly─
to the designs of nuclear power plants. Now it is necessary
make several types of optimizations to
bring the code into a more or less neat form and
acceptable performance. Of course, bring it
to almost perfection, which can be created pro─
manually programming in assembler, we
It won't work, but you can get close to it.
When programming in assembler manually
a person already sees in advance many possible
"bottlenecks" in performance or memory
and adjusts the code structure to suit them. B
it is impossible to do this with a compiler,
we are entirely dependent on the designs of nuclear power plants.
   ZX Like Pascal implements the following:
types of optimizations:

 -convolution of constants;
 -simplification of expressions by flipping
operands from the stack to registers (removing 
extra push/pop); 
 -removing duplicatesassignments and what─
tion of variables; 
 -fast multiplication and division by numbers
powers of 2, as well as fast multiplication by 
some commonly used numbers; 
 -removing repeated index calculations
arrays. 

   The well-known ones are also left out
optimization methods, such as analysis of common bases─
reactions, merging/splitting cycles and
inductance of variables (mathematical
dependence on other variables, e.g.
dependence in the cyclea[i] on i).They require─
for a deeper analysis of the source code
in Java, you need to view the structures of the operating system
rators, their nesting and interaction.
Although I partially did this for oud─
for repeated calculations of mass indices─
WWII Also not really necessary for Spectrum
splitting (opening) of cycles, because for
RAM designs require a lot of memory,
and performance-critical procedures
(output in a loop the familiarity of sprites, maps and
etc.) are already hardcoded in the assembly library
ZX Like Pascal, they can’t be written in Java 
sense.

   The first three types of optimizations are performed
at the local level. Several are viewed─
only adjacent pi code commands as if through
"peephole" (scientifically, peephole optimization─
tions) to see if it is possible to produce with them─
conduct anytransformation for optimal─
tions. In particular, they can be replaced
one command or a shorter sequence─
teamwork.
   Such frequently occurring patterns-for─
men commands in my compiler it turned out
about 20. And after each pass op─
optimization it is necessary to make a new pass
according to the code, because previous optimization could
generate new sequences of commands,
which can be optimized again.Simple
abstract example - the nearest co─ were removed
mandapush hl and pop hl, saw on the next─
more passage that you can remove the framing
thempush hl/pop hl.
 Command replacement patterns are as follows:
     
Design of a nuclear power plant 
 Sequence
 pi code commands,
 generated Replacement
 when parsing con- command
 structures of a Java computer or pi code
 after the previous one
optimization
 Equivalent Equivalent
            код на          код на
            ассемблере      ассемблере

...+number 
     Push (0,'')        LoadConstAdd
     LoadConst           (number,'')
      (number,'')
     PopAdd (0,'')
            push hl         ld de,number
            ld hl,number    add hl,de
            pop de
            add hl,de
...+name_var 
     Push (0,'')        LoadVarAdd
     LoadLabel           (0,name_var)
      (0,name_var)
     LoadNumber (0,'')
     PopAdd (0,'')
            push hl
   ld hl,name_var
            ld e,(hl)       ld de,
            inc hl             (name_var)
            ld d,(hl)       add hl,de
            ex de,hl
            pop de
            add hl,de
...-number 
     Push (0,'')        LoadConstSub
     LoadConst           (number,'')
      (number,'')
     PopSub (0,'')
            push hl         ld de,number
            ld hl,number    and a
            pop de          sbc hl,de
            ex de,hl
            and a
            sbc hl,de
...-name_var 
     Push (0,'')        LoadVarSub
     LoadLabel           (0,name_var)
      (0,name_var)
     LoadNumber (0,'')
     PopSub (0,'')
            push hl
            ld hl,name_var
            ld e,(hl)       ld de,
            inc hl             (name_var)
            ld d,(hl)       and a
            ex de,hl        sbc hl,de
            pop de
            ex de,hl
            and a
            sbc hl,de
...*number 
     Push (0,'')        LoadConstMul
     LoadConst           (number,'')
      (number,'')
     PopMul (0,'')
            push hl         ld de,number
            ld hl,number    call mul
            pop de
            call mul
...*name_var 
     Push (0,'')        LoadVarMul
     LoadLabel           (0,name_var)
      (0,name_var)
     LoadNumber (0,'')
     PopMul (0,'')
            push hl
            ld hl,name_var
            ld e,(hl)       ld de,
            inc hl             (name_var)
            ld d,(hl)       call mul
            ex de,hl
            pop de
            call mul
.../number 
     Push (0,'')        LoadConstDiv
     LoadConst           (number,'')
      (number,'')
     PopDiv (0,'')
            push hl         ld de,number
            ld hl,number    call div
            pop de
            ex de,hl
            call div
.../name_var 
     Push (0,'')        LoadVarDiv
     LoadLabel           (0,name_var)
      (0,name_var)
     LoadNumber (0,'')
     PopDiv (0,'')
            push hl
            ld hl,name_var
            ld e,(hl)       ld de,
            inc hl             (name_var)
            ld d,(hl)       call div
            ex de,hl
            pop de
            ex de,hl
            call div
...%number 
     Push (0,'')        LoadConstMod
     LoadConst           (number,'')
      (number,'')
     PopDiv (0,'')
            push hl         ld de,number
            ld hl,number    call div
            pop de          ex de,hl
            ex de,hl
            call div
            ex de,hl
...%name_var 
     Push (0,'')        LoadVarMod
     LoadLabel          (0,name_var)
      (0,name_var)
     LoadNumber (0,'')
     PopDiv (0,'')
            push hl
            ld hl,name_var
            ld e,(hl)       ld de,
            inc hl             (name_var)
            ld d,(hl)       call div
            ex de,hl        ex de,hl
            pop de
            ex de,hl
            call div
            ex de,hl
number1+number2 
     LoadConst          LoadConst
      (number1,'')       (number1+
     LoadConstAdd         number2,'')
      (number2,'')
            ld hl,number1   ld hl,
            ld de,number2      number1+
            add hl,de          number2
number1-number2 
     LoadConst          LoadConst
      (number1,'')       (number1-
     LoadConstSub         number2,'')
      (number2,'')
            ld hl,number1   ld hl,
            ld de,number2      number1-
            and a              number2
            sbc hl,de
number1*number2 
     LoadConst          LoadConst
      (number1,'')       (number1*
     LoadConstMul         number2,'')
      (number2,'')
            ld hl,number1   ld hl,
            ld de,number2      number1*
            call mul           number2
number1/number2 
     LoadConst          LoadConst
      (number1,'')       (number1/
     LoadConstDiv         number2,'')
      (number2,'')
            ld hl,number1   ld hl,
            ld de,number2      number1/
            call div           number2
number1%number2 
     LoadConst          LoadConst
      (number1,'')       (number1%
LoadConstMod         number2,'')
      (number2,'')
            ld hl,number1   ld hl,
            ld de,number2      number1%
            call div           number2
            ex de,hl
name_var:=... 
     LoadLabel          PopStoreVar
      (0,name_var)       (0,name_var)
     PopStoreNumber
      (0,'')
            ld hl,name_var
            pop de          pop hl
            ld (hl),e       ld
            inc hl          (name_var),hl
            ld (hl),d
чтение значения переменной 
     LoadLabel          LoadVar
(0,name_var)       (0,name_var)
     LoadNumber (0,'')
            ld hl,name_var
            ld e,(hl)       ld hl,
            inc hl             (name_var)
            ld d,(hl)
            ex de,hl
чтение только что записанной переменной 
     PopStoreVar        PopStoreVar
      (0,name_var)       (0,name_var)
     LoadVar
      (0,name_var)
           pop hl           pop hl
           ld (name_var),hl ld
           ld hl,(name_var) (name_var),hl
name_var:=number 
     Push (0,'')        StoreVar
     PopStoreVar         (0,name_var)
 (0,name_var)
 push hl ld
 pop hl (name_var),hl
 ld (name_var),hl
     
   Replacement templates are used to produce the first
three types of optimization: constant convolution,
simplifying expressions by tossing operans─ 
moving from the stack to registers and removing repeats─ 
ary assignments and readings of variables. 
   For example, the construction a:=4+(2+3) after
parsing and generating code will look like
like this:
     
 LoadConst (4,'')
 Push (0,'')
 LoadConst (2,'')
 Push (0,'')
 LoadConst (3,'')
 PopAdd (0,'')
 PopAdd (0,'')
 Push (0,'')
 LoadLabel (0,'_a')
 PopStoreNumber(0,'')
     
   Now we apply replacement templates, then
successive transformations of our code
will be like this:
     
 LoadConst (4,'')
 Push (0,'')
 LoadConst (2,'')
 LoadConstAdd (3,'')
 PopAdd (0,'')
 Push (0,'')
 LoadLabel (0,'_a')
 PopStoreNumber (0,'')
 ---
 LoadConst (4,'')
 Push (0,'')
 LoadConst (5,'')
 PopAdd (0,'')
 Push (0,'')
 LoadLabel (0,'_a')
 PopStoreNumber (0,'')
 ---
 LoadConst (4,'')
 LoadConstAdd(5,'')
    Push (0,'')
    LoadLabel (0,'_a')
    PopStoreNumber (0,'')
     ---
    LoadConst (9,'')
    Push (0,'')
    LoadLabel (0,'_a')
    PopStoreNumber (0,'')
     ---
    LoadConst (9,'')
    Push (0,'')
    PopStoreVar (0,'_a')
     ---
    LoadConst (9,'')
    StoreVar (0,'_a')
     
   Или на ассемблере:
     
    ld hl,9
    ld (_a),hl
     
   Четвертый вид оптимизации - быстрое ум─
ножение  и деление  на  числа степени 2, а 
также быстрое умножение на некоторые часто 
используемые числа - реализуется непосред─ 
ственно в ассемблерных процедурах в библи─
отеке.В коде процедуры на ассемблереbefore
"fair" multiplication (or division) by
an arbitrary number is checked
operands, whether one of them is equal to a number
power of 2 or a frequently used number (in
ZX Like Pascal is0,1,2,3,4,5,8,10,15,16, 
20,32,50,64,100,128,256).If the condition is you─
is filled, then the corresponding call is made
of the short multiplication subprocedure
(divisions). Thus, library pro─
The procedure allows you to produce a short mind─
cutting or dividing all encountered signs─
values in registers (variables), and not only
predefined constants in the Java code. For
multiplying or dividing by constants in Java
it would be possible to additionally introduce optimi─
pi code configuring commands (in ZX Like Pascal
not implemented).
   For the fifth type of optimization - removal
repeated calculations of array indices, - like
has already been written above, analysis is needed
neighboring nuclear power plant structures. Index calculation
array is produced by pi code commands for
calculation of expressions, because indexes can dis─
be read using any values─
nium constants, variables and even other cells─
ek arrays (when parsing
called recursively).  Every time
there is a calculation of the array index, in our
originally generated pi code for─
a new expression is calculated to calculate it─
ta. For example, indesignsif a[i+1]>b then
a[i+1]:=a[i+1]+b; index calculationi+1 will be 
is performed three times. It is necessary to have such
eliminate secondary calculations, calculate
index value only once, remember─
in memory, and then when repeating, take
ready value from memory.
   To analyze neighboring structures you need─
We need to mark them with ─ in pi code commands
beginnings and ends, as well as their headings. For
for this I used pi code pseudo commands
(markers) that are inserted during parsing
operators in the same way as other commands, and
then before carrying out other types of opti─
misizations are removed or not taken into account. On
linear sections of codeStatement calculations
indices will go in a row, and here we are─
We can definitely reduce the calculations.
But at the beginning of the code branches we will be os─
show full index calculations if they are
found - in operator headersIf,
Case, For, While, Repeat or at the beginning about─
procedures. Also in intermediate statements
There may be changes in variables, which
who participate in the calculation of indices, in this
In this case, the reduction in calculations is also not carried out─
common.
   Here is the search algorithm andreductions re─
ary calculations of array indices in the following─
pi code command values:
     
 1.Fill in the start and end markers for
sequences of Statement, If, commands 
Case, For, While, Repeat, procedure calls, 
calculations of indexes of Selector arrays; 
 2.Find the new end of index calculation
array (we go from the beginning of the sequence 
pi code); 
 3.Compare with the previous calculation in─
dex command by command. If they do not match, then 
item 2; 
 4.Find all the variables in the expressions
participating in the calculation of indices (Selector); 
 5.Statement transition flag := 0
(i.e. a flag indicating that the line is out of line 
operator block); 
 6.We go back command by command from the beginning of the race─
index number; 
 7.If you encounter a change in a variable,
participating in the calculation of indices, in subsequent─ 
command intensityPush (0,''), LoadLabel
(0,name_var) and PopStoreNumber (0,''),to
on item 2; 
 8.If the For start marker is encountered,
While, Repeat, call the procedure, then to step 2; 
 9.If we encounter the end marker If, Case,
For, While, Repeat, procedure call, then on 
item 2; 
 10.If you encounter an end-of-heading marker─
ka If, Case, then flag:=0; 
 11.If we encounter the start marker State─
ment, then flag:=1; 
 12. If you meet the end of the previous
calculation of indices and flag = 0, then replacing those─ 
final calculation of indices on a sequence─ 
Command LinearityLoadLabel (0,temp_index),
LoadNumber (0,'') and go to step 2;
 13.Go to step 6.
     
                Conclusion
     
   We looked at the methods of generation and opti─
mization of code using specific examples, using
used in the Truncated Pascal compiler
- ZX Like Pascal.  By recursive method
descent, viewing tokens one after another
in the source code of the program in Java, we finish─
We are looking forward to all nested structures and you─
expressions, inserting at the same time suitable
pi code commands into their linearfollow─
flatness. When optimizing a pi code, mainly
templates are viewed sequentially─
sty commands and are replaced with more optimal ones─
new I hope this article will help you create
your compiler!
   In conclusion, I would like to recommend the book
Niklaus Wirth"Building compilers", 
M., 2010. It describes in detail all stages
parsing of nuclear power structures and code generation,
Optimization has been slightly affected.  Given
complete source code for the language compiler
Oberon, written in Oberon itself (!), 
which is an “advanced” continuation─
I use the Pascal language.