CSc 453Compilers and Systems Software21 : Code Generation IIDepartment of Computer ScienceUniversity of [email protected]° 2009 Christian CollbergNext-Use InformationOverviewWe need to know, for each use of a variable in a basic block,whether the value contained in the variable will be used againlater in the block.If a variable has no next-use we can reuse the registerallocated to the variable.We also need to know whether a variable used in a basic blockis live-on-exit, i.e. if the value contained in the variable has ause outside the block. The global data-flow analysis we talkedabout in the optimization unit can be used to this end.If no live-variable analysis has been done we assume allvariable are live on exit from the block. This will mean thatwhen the end of a basic block has been reached, all valueskept only in registers will have to be stored back into theircorresponding variables’ memory locations.Basic Block Code GenerationX := Z + YX := Y + ZZ := Z * 5T7 := Z + 1Y := Z − T7Generate code one basic block at a time.We don’t know which path through the flow-graph has takenus to this basic block. ⇒ We can’t assume that any variablesare in registers.Basic Block Code Generation. . .X := Z + YX := Y + ZZ := Z * 5T7 := Z + 1Y := Z − T7We don’t know where we will go from this block. ⇒ Valueskept in registers must be stored back into their memorylocations before the block is exited.into their memory locations.Load variables into registers.Compute....Store register values backNext-Use InformationX := Z + YX := Y + ZZ := Z * 5T7 := Z + 1Y := Z − T7We want to keep variables in registers for as long as possible,to avoid having to reload them whenever they are needed.When a variable isn’t needed any more we free the register toreuse it for other variables. ⇒ We must know if a particularvalue will be used later in the basic block.Next-Use Information. . .X := Z + YX := Y + ZZ := Z * 5T7 := Z + 1Y := Z − T7If, after computing a value X, we will soon be using the valueagain, we should keep it in a register. If the value has nofurther use in the block we can reuse the register.Next-Use Information. . .X is live at (5)(5) X := · · ·... (no ref to X) ...(14) · · · := · · · X · · ·X is live at (5) because the value computed at (5) is used laterin the basic block.X’s next use at (5) is (14).It is a good idea to keep X in a register between (5) and (14).Next-Use Information. . .X is dead at (12)(12) · · · := · · · X · · ·... (no ref to X) ...(25) X := · · ·X is dead at (12) because its value has no further use in theblock.Don’t keep X in a register after (12).Next-Use Information – ExampleIntermediate Live/Dead Next UseCode x y z t7x y z t7(1) x := y+z L D D (2)(2) z := x∗5 D L (3)(3) t7:= z+1 L L (4) (4)(4) y := z-t7L L D (5) (5)(5) x := z+y D D Dx, y, z are live on exit, t7(a temporary) isn’t.AlgorithmNext-Use AlgorithmA two-pass algorithm computes next-use & livenessinformation for a basic block.In the first pass we scan over the basic block to find the end.Also:1For each variable X used in the block we create fields X.liveand X.nextuse in the symbol table. Set X.live:=FALSE;X.next use:=NONE.2Each tuple (i) X:=Y+Z stores next-use & live information.We set(i).X.live:=(i).Y.live:=(i).Z.live:=FALSE and(i).X.next use:=(i).Y.next use:= (i).Z.next use:= NONE.Next-Use Algorithm. . .Basic BlockKind=VAR Type=IntLive=TRUE NextUse=(5)Symbol Table Entry for X(5) X.Live=FALSE X.NextUse=_(4) X.Live=TRUE X.NextUse=(5)Y.Live=FALSE Y.NextUse=_Tuple Info.(4) X := Y + 3(5) Z := X + 9ID=X1Scan forwards over the basic block:Initialize the symbol table entry for each used variable, and thetuple data for each tuple.2Scan backwards over the basic block. For every tuple(i): x := yop z do:1Copy the live/next use-info from x, y, z’s symbol tableentries into the tuple data for tuple (i).2Update x, y, z’s symbol table entries:x.live := FALSE;x.nextuse := NONE;y.live := TRUE;z.live := TRUE;y.next use := i;z.nextuse := i;ExampleNext-Use Example – Forward PassSyTab-Info Instr.-Infolive next use live next usei x y z x y z x y z x y z(1) x:=y+z F F F F F F(2) z:=x*5 F F F F F F(3) y:=z-7 F F F F F F(4) x:=z+y F F F F F FNext-Use Example – Backwards PassSyTab-Info Instr.-Infolive next use live next usei x y z x y z x y z x y z(4) x := z+y F T T 4 4 F F F(3) y := z-7 F F T 3 F T T 4 4(2) z := x*5 T F F 2 F F T 3(1) x := y+z F T T 1 1 T F F 2The data in each row reflects the state in the symbol table andin the data section of instruction i after i has been processed.Register & Address DescriptorsRegister & Address DescriptorsDuring code generation we need to keep track of what’s ineach register (aRegister Descriptor).One register may hold the values of several variables (e.g.after x:=y).We also need to know where the values of variables arecurrently stored (an Address Descriptor).A variable may be in one (or more) register, on the stack, inglobal memory; all at the same time.Register & Address Descriptors. . .Address DescriptorId Memory Regs.x fp(16) {r0}y fp(20) {}z 0x2020 {r1, r3}t1 {r0}Register DescriptorReg Contentsr0 {x, t1}r1 {z}r2 {}r3 {z}A Simple Code GeneratorA Simple Code GeneratorA flowgraph: We generate code for each individual basic block.An Address Descriptor (AD): We store the location of eachvariable: in register, on the stack, in global memory.A Register Descriptor (RD): We store the contents of eachregister.Next-Use Information: We know for each point in the codewhether a particular variable will be referenced lateron.We need:GenCode(i: x := y op z): Generate code for the i:th intermediatecode instruction.GetReg(i: x := y op z): Select a register to hold the result of theoperation.Machine ModelWe will generate code for the address-register machinedescribed in the book. It is a CISC, not a RISC; it is similar tothe x86 and MC68k.The machine has n general purpose registers R0, R1, ...,Rn.MOV M, R Load variable M into register R.MOV R, M Store register R into variable M.OP M, R Compute R := R OP M, where OP is one of ADD,SUB, MUL, DIV.OP R2, R1 Compute R1 := R1 OP R2, where OP is one ofADD, SUB, MUL, DIV.GenCode((i): X := Y OP Z)L is the location in which the result will be stored. Often aregister.Y’ is the most favorable location for Y. I.e. a register if Y is ina register, Y’s memory location otherwise.GenCode((i): X := Y)Often we won’t have to generate any code at all for the tupleX := Y; instead we just update the