Generating Code and RunningProgramsCOMS W4115Prof. Stephen A. EdwardsFall 2007Columbia UniversityDepartment of Computer ScienceA Long K’s Journey into Byte†Compiler front end(Source code↓ Parser/Semantic AnalysisASTCompiler back end↓ Intermediate code generationIR↓ OptimizationAssembly CodeAssemblern↓ AssembleRelocatable Object CodeLinkern↓ LinkExecutableLoadern↓ RelocateIn-memory image†Apologies to O’NeillCompiler Frontends and BackendsThe front end focuses on analysis:lexical analysisparsingstatic semantic checkingAST generationThe back end focuses on synthesis:Translation of the AST into intermediate codeoptimizationassembly code generationPortable CompilersBuilding a compiler a large undertaking; most try toleverage it by making it portable.Instead ofC MIPSC++ SPARCFORTRAN x86Objective C AlphaAda-95 68kPascal PPCPortable CompilersUse a common intermediate representation.C MIPSC++ SPARCFORTRAN IR x86Objective C AlphaAda-95 68kPascal PPC| {z }Language-specificFrontends| {z }Processor-specificBackendsIntermediate Representations/FormatsStack-Based IR: Java Bytecodeint gcd(int a, int b) {while (a != b) {if (a > b)a -= b;elseb -= a;}return a;}# javap -c GcdMethod int gcd(int, int)0 goto 193 iload_1// Push a4 iload_2 // Push b5 if_icmple 15 // if a <= b goto 158 iload_1 // Push a9 iload_2 // Push b10 isub // a - b11 istore_1 // Store new a12 goto 1915 iload_2 // Push b16 iload_1 // Push a17 isub // b - a18 istore_2 // Store new b19 iload_1 // Push a20 iload_2 // Push b21 if_icmpne 3 // if a != b goto 324 iload_1 // Push a25 ireturn // Return aStack-Based IRsAdvantages:Trivial translation of expressionsTrivial interpretersNo problems with exhausting registersOften compactDisadvantages:Semantic gap between stack operations and modernregister machinesHard to see what communicates with whatDifficult representation for optimizationRegister-Based IR: Mach SUIFint gcd(int a, int b) {while (a != b) {if (a > b)a -= b;elseb -= a;}return a;}gcd:gcd._gcdTmp0:sne $vr1.s32 <- gcd.a,gcd.bseq $vr0.s32 <- $vr1.s32,0btrue $vr0.s32,gcd._gcdTmp1// if !(a != b) goto Tmp1sl $vr3.s32 <- gcd.b,gcd.aseq $vr2.s32 <- $vr3.s32,0btrue $vr2.s32,gcd._gcdTmp4 // if !(a < b) goto Tmp4mrk 2, 4 // Line number 4sub $vr4.s32 <- gcd.a,gcd.bmov gcd._gcdTmp2 <- $vr4.s32mov gcd.a <- gcd._gcdTmp2 // a = a - bjmp gcd._gcdTmp5gcd._gcdTmp4:mrk 2, 6sub $vr5.s32 <- gcd.b,gcd.amov gcd._gcdTmp3 <- $vr5.s32mov gcd.b <- gcd._gcdTmp3// b = b - agcd._gcdTmp5:jmp gcd._gcdTmp0gcd._gcdTmp1:mrk 2, 8ret gcd.a // Return aRegister-Based IRsMost common type of IRAdvantages:Better representation for register machinesDataflow is usually clearDisadvantages:Slightly harder to synthesize from codeLess compactMore complicated to interpretIntroduction to OptimizationOptimizationint gcd(int a, int b) {while (a != b) {if (a < b) b -= a;else a -= b;}return a;}First version: GCC on SPARCSecond version: GCC -O7gcd: save %sp, -112, %spst %i0, [%fp+68]st %i1, [%fp+72].LL2: ld [%fp+68], %i1ld [%fp+72], %i0cmp %i1, %i0bne .LL4nopb .LL3nop.LL4: ld [%fp+68], %i1ld [%fp+72], %i0cmp %i1, %i0bge .LL5nopld [%fp+72], %i0ld [%fp+68], %i1sub %i0, %i1, %i0st %i0, [%fp+72]b .LL2nop.LL5: ld [%fp+68], %i0ld [%fp+72], %i1sub %i0, %i1, %i0st %i0, [%fp+68]b .LL2nop.LL3: ld [%fp+68], %i0retrestoregcd: cmp %o0, %o1be .LL8nop.LL9: bge,a .LL2sub %o0, %o1, %o0sub %o1, %o0, %o1.LL2: cmp %o0, %o1bne .LL9nop.LL8: retlnopTypical OptimizationsFolding constant expressions1+3 → 4Removing dead codeif (0) { ...} → nothingMoving variables from memory to registersld [%fp+68], %i1sub %i0, %i1, %i0st %i0, [%fp+72]→sub %o1, %o0, %o1Removing unnecessary data movementFilling branch delay slots (Pipelined RISC processors)Common subexpression elimination;Machine-Dependent vs.-Independent OptimizationNo matter what the machine is, folding constants andeliminating dead code is always a good idea.a = c + 5 + 3;if (0 + 3) {b = c + 8;}→b = a = c + 8;However, many optimizations are processor-specific:Register allocation depends on how many registersthe machine hasNot all processors have branch delay slots to fillEach processor’s pipeline is a little differentBasic Blocksint gcd(int a, int b) {while (a != b) {if (a < b) b -= a;else a -= b;}return a;}lower→A: sne t, a, bbz E, tslt t, a, bbnz B, tsub b, b, ajmp CB: sub a, a, bC: jmp AE: ret asplit→A: sne t, a, bbz E, tslt t, a, bbnz B, tsub b, b, ajmp CB: sub a, a, bC: jmp AE: ret aThe statements in a basic block all run if the first one does.Starts with a statement following a conditional branch or isa branch target.Usually ends with a control-transfer statement.Control-Flow GraphsA CFG illustrates the flow of control among basic blocks.A: sne t, a, bbz E, tslt t, a, bbnz B, tsub b, b, ajmp CB: sub a, a, bC: jmp AE: ret aA: sne t, a, bbz E, tslt t, a, bbnz B, tsub b, b, ajmp CB: sub a, a, bE: ret a C: jmp AAssembly Code and AssemblersAssembly CodeMost compilers produce assembly code: easier to debugthan binary files.! gcd on the SPARCCommentgcd:cmpOpcode%o0, %o1Operand (a register)be .LL8nop.LL9:Labelble,a .LL2Conditional branch to a labelsub %o1, %o0, %o1sub %o0, %o1, %o0.LL2:cmp %o0, %o1bne .LL9nop.LL8:retlnopNo operationRole of an AssemblerTranslate opcodes + operand into byte codesgcd:0000Address80A20009Instruction codecmp %o0, %o10004 02800008 be .LL80008 01000000 nop.LL9:000c 24800003 ble,a .LL20010 92224008 sub %o1, %o0, %o10014 90220009 sub %o0, %o1, %o0.LL2:0018 80A20009 cmp %o0, %o1001c 12BFFFFC bne .LL90020 01000000 nop.LL8:0024 81C3E008 retl0028 01000000 nopEncoding Examplesub %o1, %o0, %o1Encoding of “SUB” on the SPARC:10 rd 000100 rs1 0 reserved rs231 29 24 18 13 12 4rd = %o1 = 01001rs1 = %o1 = 01001rs2 = %o0 = 0010010 01001 000100 01001 0 00000000 010001001 0010 0010 0010 0100 0000 0000 1000= 0x92228004Role of an AssemblerTransforming symbolic addresses to concrete ones.Example: Calculating PC-relative branch offsets.000c 24800003LL2 is 3 words awayble,a .LL20010 92224008 sub %o1, %o0, %o10014 90220009 sub %o0, %o1, %o0.LL2:0018 80A20009 cmp %o0, %o1Role of an AssemblerMost assemblers are “two-pass” because they can’tcalculate everything in a single pass through the code..LL9:000c 24800003 ble,a .LL2Don’t know offset of LL20010 92224008 sub %o1, %o0, %o10014 90220009 sub %o0, %o1, %o0.LL2:0018 80A20009 cmp %o0, %o1001c 12BFFFFC bne .LL9Know offset of LL9Role of an AssemblerConstant data needs to be aligned.char a[] = "Hello";int b[3] = { 5, 6, 7 };.sectionAssembler directives".data"
View Full Document
Unlocking...