Code Generation II CS308 Compiler Theory
Code Generation Ⅱ CS308 Compiler Theory 1
A Simple Code Generator One of the primary issues:deciding how to use registers to best advantage ·Four principal uses: In most machine architectures,some or all of the operands of an operation must be in registers in order to perform the operation. Registers make good temporaries to hold the result of a sub expression or a variable that is used only within a single basic block. - Registers are used to hold (global)values that are computed in one basic block and used in other blocks. Registers are often used to help with run-time storage management. CS308 Compiler Theory 2
A Simple Code Generator • One of the primary issues: deciding how to use registers to best a dvantage • Four principal uses: – I hi hi ll f h d f i b i In most machine architectures, some or all o f t he operan ds o f an operation must be in registers in order to perform the operation. – Registers make good temporaries to hold the result of a sub expression or a variable that is used only within a single basic block. – Registers are used to hold (global) values that are computed in one basic block and used in other blocks. – Registers are often used to help with run-time storage management. CS308 Compiler Theory 2
A Simple Code Generator Assumption of the code-generation algorithm in this section: Some set of registers is available to hold the values that are used within the block The basic block has already been transformed into a preferred sequence of three-address instructions For each operator,there is exactly one machine instruction that takes the necessary operands in registers and performs that operation,leaving the result in a register ·LDeg,mem ·ST mem,reg ·OP reg,reg,reg CS308 Compiler Theory 3
A Simple Code Generator • Assumption of the code-generation algorithm in this section: – Some set of registers is available to hold the values that are used within the block. – The basic block has already been transformed into a preferred sequence of three-address instructions – For each operator, there is exactly one machine instruction that takes the necessary operands in registers and performs that operation, leaving the result in a register CS308 Compiler Theory 3
Register and Address Descriptors Descriptors are necessary for variable load and store decision. ·Register descriptor For each available register Keeping track of the variable names whose current value is in that register -Initially,all register descriptors are empty ·Address descriptor For each program variable Keeping track of the location(s)where the current value of that variable can be found Stored in the symbol-table entry for that variable name. CS308 Compiler Theory 4
Register and Address Descriptors • Descriptors are necessary for variable load and store decision. • Register descriptor – For each available register – Keeping track of the ariable names hose c rrent al e is in that register Keeping track of the variable names whose c urrent val u e is in that register – Initially, all register descriptors are empty • Address descri ptor – For each program variable – Keeping track of the location (s) where the current value of that variable can be found – S di h b l Store d in t he sym b ol-tabl f h i bl ble entry for t hat variable name. CS308 Compiler Theory 4
The Code-Generation Algorithm ·Function getReg) Selecting registers for each memory location associated with the three-address instruction I. Machine Instructions for Operations For a three-address instruction such as x=y +z,do the following: 1.Use getReg(x=y+z)to select registers for x,y,and z.Call these Rx,Ry,and Rz. 2.Ify is not in Ry (according to the register descriptor for Ry),then issue an instruction LD Ry,y',where y'is one of the memory locations fory(according to the address descriptor for y). 3.Similarly,ifz is not in Rz,issue an instruction LD Rz,z',where z'is a location for z. 4.Issue the instruction ADD Rx,Ry,Rz. CS308 Compiler Theory 5
The Code-Generation Algorithm • Function getReg(I) – Selecting registers for each memory location associated with the three-address instruction I. • Machine Instructions for Operations – For a three For a three -address instr ction s ch as + do the follo ing: address instruction s uch as x = y + z, do the follo wing: 1. Use getReg(x = y + z) to select registers for x, y, and z. Call these Rx, Ry, and Rz . 2 . If y is not in Ry (according to the register descriptor for Ry) , then issue an instruction LD Ry , y' , where y' is one of the memory locations for y (according to the address descriptor for y) . 3. Similarly, if z is not in R z , issue an instruction LD R z, z’ , where z’ is a location for z. 4. Issue the instruction ADD Rx , Ry , Rz. CS308 Compiler Theory 5
The Code-Generation Algorithm Machine Instructions for Copy Statements -For x=y,getReg will always choose the same register for both xand y. Ify is not in that register Ry,generate instruction LD Ry,y. Ify was in Ry,do nothing. -Need to adjust the register description for Ry so that it includes x as one of the values. Ending the Basic Block - generate the instruction STx,R,where R is a register in which x's value exists at the end of the block ifx is live on exit from the block. CS308 Compiler Theory 6
The Code-Generation Algorithm • Machine Instructions for Copy Statements – For x=y, getReg will always choose the same register for both xand y. – If y is not in that register Ry , generate instruction LD Ry , y. – If y was in Ry , do nothing do nothing. – Need to adjust the register description for Ry so that it includes x as one of the values. • Ending the Basic Block – generate the instruction ST x, R, where R is a register in which x's value exists at the end of the block if the block if x is live on exit from the block is live on exit from the block. CS308 Compiler Theory 6
The Code-Generation Algorithm Managing Register and Address Descriptors 1.For the instruction LD R,x -(a)Change the register descriptor for register R so it holds only x. -(b)Change the address descriptor for x by adding register R as an additional location. 2.For the instruction ST x,R,change the address descriptor for x to include its own location. 3.For an operation such as ADD Rx,Ry,Rz for x=y +z -(a)Change the register descriptor for Rx so that it holds only x. -(b)Change the address descriptor for x so that its only location is Rx. Note that the memory location for x is not now in the address descriptor for x. -(c)Remove Rx from the address descriptor of any variable other than x. 4.When process a copy statement x=y,after generating the load for y into register Ry,if needed,and after managing descriptors as for all load statements(per rule 1 ) -(a)Add x to the register descriptor for Ry. -(b)Change the address descriptor for x so that its only location is Ry. CS308 Compiler Theory 7
The Code-Generation Algorithm • Managing Register and Address Descriptors 1 . For the instruction LD R, x – (a) Change the register descriptor for register R so it holds only x. – () g p y g g b ) Chan ge the address descri ptor for x b y addin g re gister R as an additional location. 2. For the instruction ST x, R, change the address descriptor for x to include its own location. 3. For an operation such as ADD Rx , Ry , Rz for x = y + z – ( ) Ch th i t d i t f R th t it h ld l ( a ) Change the regis ter descrip tor for Rx so th a t it h olds only x. – (b) Change the address descriptor for x so that its only location is Rx . – Note that the memory location for x is not now in the address descriptor for x . – (c) Remove Rx from the address descriptor of any variable other than x. 4. When process a copy statement x = y , after generating the load for y into register Ry, if needed, and after managing a nagin g descriptors ripto r s as for all load statements (per rule 1 ) : – (a) Add x to the register descriptor for Ry . – (b) Change the address descriptor for x so that its only location is Ry . CS308 Compiler Theory 7
R1 R2 R3 a b c d t u v a b c d t a-b LD R1,a LD R2,b SUB R2,R1,R2 a t a,R1b c d R2 u =a-c LD R3,c SUB R1,R1,R3 u a b c,R3 d R2R1 v =t u ADD R3,R2,R1 t b R2 R1 R3 a d LD R2,d u a,d v R2 b cd,R2 R1R3 d v+u ADD R1,R3,R1 d R2 bc R1 R3 exit ST a,R2 ST d,R1 d a a,R2 b c d,R1 R3 CS308 Compiler Theory 8
CS308 Compiler Theory 8
Design of the Function getreg Pick a register Ry for y in x=y+z -1.y is currently in a register,pick the register. -2.y is not in a register,but there is an empty register,pick the register. -3.y is not in a register,and there is no empty register. Let R be a candidate register,and suppose v is one of the variables in the register descriptor need to make sure that v's value either is not needed,or that there is somewhere else we can go to get the value of R. (a)OK if the address descriptor for v says that v is somewhere besides R, (b)OK if v is x,and x is not one of the other operands of the instruction(z in this example) (c)OK if v is not used later (d)Generate the store instruction ST v,R to place a copy of v in its own memory location.This operation is called a spill. CS308 Compiler Theory 9
Design of the Function getReg • Pick a register Ry for y in x=y+z – 1 . y is currently in a register, pick the registe r. – 2. y is not in a register, but there is an empty register, pick the register. – 3. y is not in a re g , py g ister, and there is no emp t y re gister. • Let R be a candidate register, and suppose v is one of the variables in the register descriptor • need to make sure that v's value either is not needed, or that there is somewhere else we can go to get the value of get the value of R. (a) OK if the address descriptor for v says that v is somewhere besides R, (b) OK if v is x, and x is not one of the other operands of the instruction(z in this example) (c) OK if (c) OK if v is not used later is not used later (d) Generate the store instruction ST v, R to place a copy of v in its own memory location. This operation is called a spill. CS308 Compiler Theory 9
Design of the Function getreg Pick a register Rx for x in x=y+z Almost as for y,differences: 1.Since a new value of x is being computed,a register that holds only x is a choice for Rx; 2.Ify is not used after the instruction,and Ry holds only y after being loaded,then Ry can be used as Rx;A similar option holds regarding z and Rz. CS308 Compiler Theory 10
Design of the Function getReg • Pick a register Rx for x in x=y+z – Almost as for y, differences: 1. Since a new value of x is being computed, a register that holds only x is a choice for Rx; 2. If y is not used after the instruction, and Ry holds onl y y after bein g , loaded, then Ry can be used as Rx; A similar option holds regarding z and Rz · CS308 Compiler Theory 10