9. Code generation

The core problem of code generation ;

• Instruction selection
• Register allocation
• Instruction scheduling

Instruction selection

Select the appropriate target instruction or instruction sequence for each intermediate language statement

The first principle is Ensure semantic consistency

Find instruction sequence templates with consistent semantics for intermediate language statements directly ：

a=b+c

MOV b, R0 //  take b Load R0
ADD R0, c //  take c Add to R0
MOV R0, a //  save R0 Content to a

Second, consider The efficiency of the generated code

A machine rich in the target instruction set can provide several implementation methods for a given operation

Suppose each instruction is ready for the operand The cost of performing its operations by 1

Every time Access memory once Will increase the cost 1

The execution cost of the above code is 6

If we assume R1 and R2 Have been included in b and c Value , So here's the code ：

MOV R1, R0 //  Register R1 Load the contents of the register R0
ADD R0, R2 // R2 Add content to R0
MOV R0, a //  save R0 Content to a

The cost is 4

hypothesis R1 and R2 It already contains b and c Value , also b The value of is no longer required

ADD R1, R2 // R2 Add content to R1
MOV R1, a //  save R1 Content to a

The cost is 3

Register allocation

Reallocation period , Select a set of variables that reside in a register for a point in the program

In the subsequent assignment phase , Pick the variable that will reside Specific register , Register assignment

• The principle of distribution
• • Try to keep the value of the variable or the calculation result in the register
  • Registers occupied by variables that are no longer referenced should be released as soon as possible
• Local / Global register allocation
• • Local ： Register allocation in the range of basic blocks
  • overall situation ： Register allocation in process scope

Instruction scheduling

• Adjust the execution sequence of instructions properly , Thus, the whole program is optimized
• RISC In Architecture , The value fetched from the memory into the register will not be used in some subsequent cycles , In these cycles , It is important to call out instructions that do not depend on the fetched value for execution
• The scheduling algorithm can be limited to the basic block , It can also be a broader global instruction scheduling ;
• It can be the adjustment of the execution sequence of statically completed instructions , It can also realize dynamic instruction scheduling

Code generation process

Register computer ：

• The typical ones are 16、32 Or more registers
• • All operations are performed in registers
• Access and storage are through load / store Conduct
• • Memory cannot be used for direct computation

structure ：

Memory ： Store the overflow variable

register ： The space in which operations are performed , Suppose there are an infinite number of

Execution engine ： Execution of instructions

At the beginning x、y And so on

[ Failed to transfer the external chain picture , The origin station may have anti-theft chain mechanism , It is suggested to save the pictures and upload them directly (img-FpgnaM13-1642042259498)(…/picture/74.png)]

Register machines only support one data type int

In the code generation phase , Suppose there are infinite registers on the register machine

• Therefore, each declared variable and temporary variable will occupy a （ fictitious ） register
• Sometimes the process of allocating virtual registers to physical registers is called register allocation

With Basic block As a unit of a simple code generation algorithm

• Suppose that only the basic block is formed a:=b op c and a:=b Of TAC Statement sequence
• Assume that the target language contains only two types of instructions
• • MOV x, y
  • x and y Is a variable or register , But at least one is a register , The execution of this instruction will x The value of is passed to y
  • OP x, y
  • OP Is the corresponding binary operation op The operator of ,x It's a register ,y It is a variable or a register , The instruction is to make x and y The content of OP Corresponding operation , The result is stored in the register x

Instruction selection can be accomplished by direct correspondence , So the core of this code generation algorithm is how to deal with the basic block Make full use of registers The problem of

principle ：

• When generating the target object value of a variable , Try to keep the value of the variable or the calculation result in the register
• Reference the value of the variable in the register as much as possible
• Within the same basic block , Registers occupied by variables that are no longer referenced should be released as soon as possible
• When reaching the exit of the basic block , You need to store the value of the variable in memory , In this way, the variable values entered from outside the basic block are all in memory

Directly use the post order traversal of the syntax tree , Violence is listed

[ Failed to transfer the external chain picture , The origin station may have anti-theft chain mechanism , It is suggested to save the pictures and upload them directly (img-ENAiPauM-1642042259501)(…/picture/80.png)]

Heuristic algorithm

Register description array RVALUE,RVALUE[R] describe register R Which variables are currently stored

Variable description array AVALUE,AVALUE[a] Express Variable a In which register is the value of （ Or not in any register ）

function getreg Description of

getreg function ： With i: x := y op z or i: x := y Is the parameter , Returns a pseudo register

(1) about i: x := y op z

if y∈RVALUE[R], And in the statement i after y Is no longer referenced in the basic block , It is also not an active variable after the basic block exit , Then return to R; otherwise , Returns a new pseudo register R’

(2) about i: x := y

if y∈RVALUE[R], Then return to R; otherwise , Returns a new pseudo register R’

(1) For each TAC sentence i: x := y op z or i: x := y, Perform the following steps in sequence ：

With i Is the parameter , call getreg(i), Returns a register R, As storage x Register of current value

utilize AVALUE[y] and AVALUE[z], Identify y and z The storage location of the current value

If its current value is in a register , Then take the register as Ry and Rz;

If its current value is not in the register , Then... Is still used in the corresponding instruction y and z Express

[ Failed to transfer the external chain picture , The origin station may have anti-theft chain mechanism , It is suggested to save the pictures and upload them directly (img-iPL1jnRS-1642042259502)(…/picture/75.png)]

[ Failed to transfer the external chain picture , The origin station may have anti-theft chain mechanism , It is suggested to save the pictures and upload them directly (img-uNxsbEpW-1642042259503)(…/picture/76.png)]

[ Failed to transfer the external chain picture , The origin station may have anti-theft chain mechanism , It is suggested to save the pictures and upload them directly (img-8yZ7izzL-1642042259504)(…/picture/77.png)]

[ Failed to transfer the external chain picture , The origin station may have anti-theft chain mechanism , It is suggested to save the pictures and upload them directly (img-3QzFEM3A-1642042259505)(…/picture/78.png)]

[ Failed to transfer the external chain picture , The origin station may have anti-theft chain mechanism , It is suggested to save the pictures and upload them directly (img-hvTzfKBw-1642042259506)(…/picture/79.png)]

With the following TAC A basic block consisting of a sequence of statements , Suppose at the exit ,b and d Is active

sentence	Code	Register description	Variable address description
t := a – b	MOV a R0; sub R0 b	R0 contain t	t stay R0 in (a No longer in R0)
a := b	MOV b R1;	R0 contain t R1 contain a, b	t stay R0 in a, b stay R1 in
u := a – c	MOV R1 b; sub R1 c	R0 contain t R1 contain u	t stay R0 in u stay R1 in
v := t + u	add R0 R1	R0 contain v R1 contain u	u stay R1 in v stay R0 in
d := v + u	add R0 R1; MOV R0 d	R0 contain d	d stay R0 And memory

u := a – c | MOV R1 b; sub R1 c | R0 contain t R1 contain u | t stay R0 in u stay R1 in |
| v := t + u | add R0 R1 | R0 contain v R1 contain u | u stay R1 in v stay R0 in |
| d := v + u | add R0 R1; MOV R0 d | R0 contain d | d stay R0 And memory |

It is assumed that there is no upper limit on the number of registers ( A simple register allocation algorithm )