Kodgenerering. Maskinberoende optimering.

Kursen Kompilatorer och interpretatorer | Föreläsningar: 1 2 3 4 5 6 7 8 9 10 11 12

Det här är ungefär vad jag tänker säga på föreläsningen. Använd det för förberedelser, repetition och ledning. Det är inte en definition av kursinnehållet, och det ersätter inte kursboken.

Idag: Kodgenerering. Maskinberoende optimering.

ALSU-07 avsnitt 8.1-8.3 (översiktligt)
(ASU-86 9.1-9.4, 9.12)
(KP kapitel 7)

Kodgenerering

Många av de tekniker som behandlas i kursen, t ex för syntaxspecifikation och parsning, är användbara även utanför rena kompilatorer. Just kodgenerering är dock något som man förmodligen inte kommer i kontakt med, annat än som kompilatorutvecklare.

Kodgenerering är kanske inte heller en del av kompilatorn som man har så stor nytta av att förstå i sitt arbete som programmerare.

Därför tar vi bara med så mycket om kodgenerering som vi hinner.

Input: intermediate code, often three-address code, but can also be e. g. syntax trees.

Several types of target code:

Not common: Absolute machine code (no linking, no libraries, no separate compilation)
Relocatable machine code
Assembly language

What the code generator does:

Memory management = where to put the variables = mapping source-program names to memory addresses (Oh, and labels too!)
Instruction choice
Register allocation

From KP page 146, about code generation:

About code generation

8.1 Issues in the Design of a Code Generator

Instruction selection

Example 1, a three-address instruction:

x = y + z;

Use a template:

MOV y,R0 -- Load y into register R0
ADD z,R0 -- Add z to register R0
MOV R0,x -- Store R0 into x

Example 2, more three-address instructions:

a = b + c;
d = a + e;

Using the same template:

MOV b,R0
ADD c,R0
MOV R0,a
MOV a,R0
ADD e,R0
MOV R0,d

Unneccessary instruction(s).

Example 3, a three-address instruction:

a = a + 1;

Use a template:

MOV a,R0
ADD #1,R0 -- Add "immediate" constant 1 to R0
MOV R0,a

Better:

INC a

8.2 The Target Language

Several types of target machines:

Stack machines. Often a virtual machine, no registers.
Register machines. Real hardware. Two types:
- RISC (ex: Sparc)
- CISC (ex: Pentium)

From KP page 143, about register machines:

About register machines

8.3 Addresses in the Target Code

(ASU-86 9.3 Run-time storage management)

Activation records, as in föreläsning 8.
Here they show the actual target-machine instructions to:

allocate activation records on the stack by incrementing the stack pointer register
store the return address in the activation record
jump to the procedure, using a direct goto (ex: GOTO 300)
return, using an indirect goto to the address saved in the activation record (ex: GOTO *0(SP))

8.4-8.5 Basic blocks, flow graphs, optimization

Tas upp i optimeringsföreläsningen

8.6-8.13

Skip the rest of chapter 8.

Kursen Kompilatorer och interpretatorer | Föreläsningar: 1 2 3 4 5 6 7 8 9 10 11 12

Thomas Padron-McCarthy (Thomas.Padron-McCarthy@oru.se) 13 oktober 2007