CSc 453Compilers and Systems Software19 : Code Generation IDepartment of Computer ScienceUniversity of [email protected]° 2009 Christian CollbergIntroductionCompiler PhasesWe are here!ASTasmSemanticAnalyserInterm.Code GenIRMachineCode GenIRASTLexertokenssourceerrorsParsererrorsOptimizeerrorsIntermediate CodeGenerationSemantic Analysis,Intermediate CodeSeparation intoBasic Blocks; Flow analysis;Next−use infocomputation;X is definedhere:X is usedhere:Control−Flow GraphAssemblyCodeAssemblerMachineCodePeepholeOptimizationRegisterAssignmentRegisterAllocationRegisterSpillingInstructionSelectionInstructionSchedulingLexing, ParsingCode Generation IssuesThe purpose of the code generation phase of the compiler isto transform the intermediate code produced by the front endinto some other code that can be executed.Often the the code generator will produce assembly code orobject code which (after assembly and linking) can be directlyexecuted by the hardware.Alternatively, the code generator can generate C-code and usethe native C-compiler as the “real” back-end.Or, the code generator can generate code for a “virtualmachine”, and use an interpreter to execute the code.We expect the code generator to produce code that is asefficient as possible.Code Generation Issues. . .CodeTreeDAGt1 := a + bt2 := c + t1d := t2TuplesInstructionSelectionRegisterAllocationCode GenerationC−CodeGenerationC−CodeC−CompilerGet NextInstructionExecuteInstructionInterpretationIntermediate CodeAbsoluteMachine CodeAssembly CodeRelocatableCode Generation Issues. . .The input to the code generator can be any one of theintermediate representations we’ve discussed: Trees, Tuples,Graphs,. . . The work of the code generator consists of several(interdependent) tasks:Instructionselection: Which instructions should begenerated?scheduling: In which order should they begenerated?Registerallocation: Which variables should be kept inregisters?assignment: In which registers should they bestored?spilling: Which registers should be spilledwhen?ArchitecturesMachine Architectures—Instruction Sets3-Register: add R1, R2, R3[R1 := R2 + R3] (MIPS,VAX,· · · ).Register-Address: add R, Addr[R := R + Addr] (VAX,x86,MC68k)2-Register: add R1, R2[R1 := R1 + R2] (VAX,x86,MC68k)2-Address: add Addr1, Addr2[Addr1 := Addr1 + Addr2] (VAX)3-Address: add Addr1, Addr2, Addr3[Addr1 := Addr2 + Addr3] (VAX)Machine Architectures—Register ClassesGeneral One set of register that can hold any type of data(VAX, Alpha).Integer+Float Separate integer and floating point register sets(Sparc, MIPS).Integer+Float+Address Separate integer, floating point, andaddress register sets (MC68k).Machine Architectures—Addressing ModesImmediate: #X The value of the constant X. (All architectures.)Register Direct: R The contents of register R. (All.)Register Indirect: (R) The contents of the memory address inregister R. (All.)Register Indirect with increment: (R+) The contents of thememory address in register R. R is incremented by thesize of the instruction (i.e. if MOVE.W (R+),Addrmoves two bytes, then R would be incremented by2). (VAX, MC68k.)Register Ind. with Displacement: d(R) The contents of thememory address R+d, where R is a register and d a(small) constant. (All architectures.)Machine Architectures—Instruction CostThe Cost of an instruction is the number of machine cycles ittakes to execute it.On RISCs, most instructions take 1 cycle to execute. Loads,stores, branches, multiplies, and divides may take longer.On CISCs, the number of cycles required to execute aninstruction Instr Op1, Op2iscost(Instr)+cost(Op1)+cost(Op2). cost(Opi) is thenumber of cycles required to compute the addressing modeOpi.A Simple ExampleExample — SourceA straight-forward code generator considers one tuple at atime, without looking at other tuples. The code generator issimple, but the generated code is sub-optimal.The Source Program:int A[5], i, x;main(){for(i=1;i<=5;i++)x=x*A[i]+A[i];}Example — Intermediate Codeint A[5], i, x;main(){for(i=1;i<=5;i++) x=x*A[i]+A[i];}The Tuple Code(1) i := 1(2) T0 := i(3) IF T0<6 GOTO (5)(4) GOTO (17)(5) T1 := i(6) T2 := A[T1](7) T3 := x(8) T4 := T2*T3(9) T5 := i(10) T6 := A[T5](11) T7 := T4+T6(12) x := T7(13) T8 := i(14) T9 := T8+1(15) i := T9(16) GOTO (2)Example – Unoptimized MIPS Code(1) i := 1li $2,0x1 # $2 := 1sw $2,i # i := $2L2: (2) T0 := ilw $2,i # $2 := i(3) IF i < 6 GOTO (5)slt $3,$2,6 # $3 := i < 6bne $3,$0,L5 # IF $36=0 GOTO L5(4) GOTO (17)j L3 # GOTO L3L5: (5) T1 := ilw $2,i # $2 := CONT(i)(6) T2 := A[T1]move $3,$2 # $3 := $2sll $2,$3,2 # $2 := $3 * 4la $3,A # $3 := ADDR(A)addu $2,$2,$3 # $2 := $2 + $3lw $2,0($2) # $2 := CONT(A[i])(7) T3 := xlw $3,x # $3 := CONT(x);(8) T4 := T2 * T3mult $3,$2 # $lo := $3 * $2mflo $4 # $4 := $lo(9) T5 := ilw $2,i # $2 := CONT(i)(10) T6 := A[T5]move $3,$2 # $3 := $2sll $2,$3,2 # $2 := $3 * 4la $3,A # $3 := ADDR(A)addu $2,$2,$3 # $2 := $2 + $3lw $3,0($2) # $2 := CONT(A[i])(11) T7 := T4 + T6addu $2,$4,$3 # $2 := $4 + $3(12) x := T7sw $2,x # x := $2(13) T8 := ilw $3,i # $3 := CONT(i)(14) T9 := T8 + 1addu $2,$3,1 # $2 := $3 + 1move $3,$2 # $3 := $2(15) i := T9sw $3,i # i := $3(16) GOTO (2)j L2 # GOTO L2L3:Common Sub-expressionEliminationExample — After CSEThe generated code becomes a lot faster if we performCommon Sub-Expression Elimination (CSE) and keep theindex variable i in a register ($6) over the entire loop:(1) i := 1li $6,0x1 # $6 := 1L2: (2) T0 := i(3) IF i < 6 GOTO (5)slt $3,$6,6 # $3 := i < 6bne $3,$0,L5 # IF $36=0 GOTO L5(4) GOTO (17)j L3 # GOTO L3A[T1] is computed once, and the result is kept in register $5until it’s needed the next time.L5:(5) T1 := i(6) T2 := A[T1]move $3,$6 # $3 := $6sll $2,$3,2 # $2 := $3 * 4la $3,A # $3 := ADDR(A)addu $2,$2,$3 # $2 := $2 + $3lw $5,0($2) # $5 := CONT(A[i])(7) T3 := xlw $3,x # $3 := CONT(x);(8) T4 := T2 * T3mult $3,$5 # $lo := $3 * $5mflo $4 # $4 := $loAfter the loop we need to store $6 back into i.(9) T5 := i(10) T6 := A[T5](11) T7 := T4 + T6addu $2,$4,$5 # $2 := $4 + $5(12) x := T7sw $2,x # x := $2(13) T8 := i(14) T9 := T8 + 1(15) i := T9addu $6,$6,1 # $6 := $6 + 1(16) GOTO (2)j L2 # GOTO L2L3:sw $6,i # i := $6More OptimizationExample — More Register AllocationSince x and ADDR(A) seem to be used a lot in the loop, wekeep them in registers ($7 and $8, respectively) as well.We also reverse the comparison, which allows us to removeone jump.The move instruction is unnecessary, so we remove it also.(1) i := 1li $6,0x1 #