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