Introduction to Computer Systems 15-213, fall 2009 6th Lecture, Sep. 9th Last TimeLast TimeToday“Do-While” Loop Example“Do-While” Loop Compilation“Do-While” Loop CompilationGeneral “Do-While” Translation“While” Loop ExampleAlternative “While” Loop TranslationGeneral “While” TranslationNew Style “While” Loop TranslationJump-to-Middle While TranslationJump-to-Middle ExampleSummaryToday“For” Loop Example: Square-and-Multiplyipwr Computation“For” Loop Example“For” “While” “Do-While”For-Loop: Compilation #1“For” “While” (Jump-to-Middle)For-Loop: Compilation #2TodaySwitch Statement ExampleJump Table StructureSwitch Statement Example (IA32)Switch Statement Example (IA32)Assembly Setup ExplanationJump TableCode Blocks (Partial)IA32 Object CodeIA32 Object Code (cont.)Disassembled TargetsMatching Disassembled TargetsSummarizingTodayIA32 StackIA32 Stack: PushIA32 Stack: PopProcedure Control FlowProcedure Call ExampleProcedure Return ExampleStack-Based LanguagesCall Chain ExampleStack FramesExampleExampleExampleExampleExampleExampleExampleExampleExampleExampleExampleIA32/Linux Stack FrameRevisiting swapRevisiting swapswap Setup #1swap Setup #1swap Setup #1swap Setup #1swap Setup #1swap Finish #1swap Finish #2swap Finish #2swap Finish #2swap Finish #3swap Finish #4swap Finish #4Disassembled swapRegister Saving ConventionsRegister Saving ConventionsIA32/Linux Register UsageRecursive FactorialPointer CodeCreating & Initializing PointerCreating & Initializing PointerPassing PointerPassing PointerIA 32 Procedure SummaryCarnegie MellonIntroduction to Computer Systems15‐213, fall 20096thLecture, Sep. 9thInstructors:Majd Sakr and Khaled HarrasCarnegie MellonLast Time Complete memory addressing mode (%eax), 17(%eax), 2(%ebx, %ecx, 8), … Arithmetic operations subl %eax, %ecx # ecx = ecx + eax sall $4,%edx # edx = edx << 4 addl 16(%ebp),%ecx # ecx = ecx + Mem[16+ebp] leal 4(%edx,%eax),%eax # eax = 4 + edx + eax imull %ecx,%eax # eax = eax * ecxCarnegie MellonLast Time x86‐64 vs. IA32 Integer registers: 16 x 64‐bit vs. 8 x 32‐bit movq, addq, …vs. movl, addl, … Control Condition code registers Set as side effect or by cmp, test Used: Read out by setx instructions (setg, setle, …) Or by conditional jumps (jle .L4, je .L10, …)%rax%rbx%rcx%rdx%rsi%rdi%rsp%rbp%eax%edx%ecx%ebx%esi%edi%esp%ebp%r8%r9%r10%r11%r12%r13%r14%r15%r8d%r9d%r10d%r11d%r12d%r13d%r14d%r15dCF ZF SF OFCarnegie MellonToday While loops For loops Switch statements ProceduresCarnegie MellonC Codeint fact_do(int x){int result = 1;do {result *= x;x = x-1;} while (x > 1);return result;}Goto Versionint fact_goto(int x){int result = 1;loop:result *= x;x = x-1;if (x > 1)goto loop;return result;}“Do‐While” Loop Example Use backward branch to continue looping Only take branch when “while” condition holdsCarnegie MellonGoto Versionintfact_goto(int x){int result = 1;loop:result *= x;x = x-1;if (x > 1)goto loop;return result;}“Do‐While” Loop CompilationRegisters:%edx x%eax resultfact_goto:pushl %ebp # Setupmovl %esp,%ebp # Setupmovl $1,%eax # eax = 1movl 8(%ebp),%edx # edx = x.L11:imull %edx,%eax # result *= xdecl %edx # x--cmpl $1,%edx # Compare x : 1jg .L11 # if > goto loopmovl %ebp,%esp # Finishpopl %ebp # Finishret # FinishAssemblyWill disappearBlackboard?Carnegie MellonGoto Versionintfact_goto(int x){int result = 1;loop:result *= x;x = x-1;if (x > 1)goto loop;return result;}“Do‐While” Loop CompilationRegisters:%edx x%eax resultfact_goto:pushl %ebp # Setupmovl %esp,%ebp # Setupmovl $1,%eax # eax = 1movl 8(%ebp),%edx # edx = x.L11:imull %edx,%eax # result *= xdecl %edx # x--cmpl $1,%edx # Compare x : 1jg .L11 # if > goto loopmovl %ebp,%esp # Finishpopl %ebp # Finishret # FinishAssemblyCarnegie MellonC Codedo Bodywhile (Test);Goto Versionloop:Bodyif (Test)goto loopGeneral “Do‐While” Translation Body: Test returns integer= 0 interpreted as false≠0 interpreted as true{Statement1;Statement2;…Statementn;}Carnegie MellonC Codeint fact_while(int x){int result = 1;while (x > 1) {result *= x;x = x-1;};return result;}Goto Version #1int fact_while_goto(int x){int result = 1;loop:if (!(x > 1))goto done; result *= x;x = x-1;goto loop;done:return result;}“While” Loop Example Is this code equivalent to the do‐while version? Must jump out of loop if test failsCarnegie MellonC Codeint fact_while(int x){int result = 1;while (x > 1) {result *= x;x = x-1;};return result;}Goto Version #2int fact_while_goto2(int x){int result = 1;if (!(x > 1))goto done; loop:result *= x;x = x-1;if (x > 1)goto loop;done:return result;}Alternative “While” Loop Translation Historically used by GCC Uses same inner loop as do‐while version Guards loop entry with extra testCarnegie MellonWhile versionwhile (Test)BodyDo‐While Versionif (!Test) goto done;doBodywhile(Test);done:General “While” TranslationGoto Versionif (!Test)goto done;loop:Bodyif (Test)goto loop;done:Carnegie MellonC Codeint fact_while(int x){int result = 1;while (x > 1) {result *= x;x = x-1;};return result;}Goto Versionint fact_while_goto3(int x){int result = 1;goto middle; loop:result *= x;x = x-1;middle:if (x > 1)goto loop;return result;}New Style “While” Loop Translation Recent technique for GCC Both IA32 & x86‐64 First iteration jumps over body computation within loopCarnegie MellonC Codewhile (Test)BodyJump‐to‐Middle While Translation Avoids duplicating test code Unconditional goto incurs no performance penalty for loops compiled in similar fashionGoto Versiongoto middle;loop:Bodymiddle:if (Test)goto loop;Goto (Previous) Versionif (!Test)goto done;loop:Bodyif (Test)goto loop;done:Carnegie Mellonint fact_while(int x){int result = 1;while (x > 1) {result *= x;x--;};return result;}# x in %edx, result in %eaxjmp .L34 # goto Middle.L35: # Loop:imull %edx, %eax # result *= xdecl %edx # x--.L34: # Middle:cmpl $1, %edx # x:1jg .L35 # if >, goto Loop Jump‐to‐Middle ExampleCarnegie MellonSummary Do‐While loop While‐Do loopC Codedo Bodywhile (Test);Goto Versionloop:Bodyif (Test)goto loopWhile versionwhile (Test)BodyDo‐While Versionif (!Test) goto done;doBodywhile(Test);done:Goto Versionif (!Test)goto done;loop:Bodyif (Test)goto loop;done:goto middle;loop:Bodymiddle:if (Test)goto loop;orCarnegie MellonToday
View Full Document