Slide 1Last 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 20096th Lecture, Sep. 9th Instructors: Majd Sakr and Khaled HarrasCarnegie MellonLast TimeComplete memory addressing mode(%eax), 17(%eax), 2(%ebx, %ecx, 8), …Arithmetic operationssubl %eax, %ecx # ecx = ecx + eaxsall $4,%edx # edx = edx << 4addl 16(%ebp),%ecx # ecx = ecx + Mem[16+ebp]leal 4(%edx,%eax),%eax # eax = 4 + edx + eaximull %ecx,%eax # eax = eax * ecxCarnegie MellonLast Timex86-64 vs. IA32Integer registers: 16 x 64-bit vs. 8 x 32-bitmovq, addq, … vs. movl, addl, …ControlCondition code registersSet as side effect or by cmp, testUsed: 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 MellonTodayWhile loopsFor loopsSwitch statementsProceduresCarnegie 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 ExampleUse backward branch to continue loopingOnly 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 Body while (Test);Goto Versionloop: Body if (Test) goto loopGeneral “Do-While” TranslationBody:Test returns integer= 0 interpreted as false0 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 ExampleIs 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 TranslationHistorically used by GCCUses same inner loop as do-while versionGuards loop entry with extra testCarnegie MellonWhile versionwhile (Test) BodyDo-While Version if (!Test) goto done; do Body while(Test);done:General “While” TranslationGoto Version if (!Test) goto done;loop: Body if (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 TranslationRecent technique for GCCBoth IA32 & x86-64First iteration jumps over body computation within loopCarnegie MellonC Codewhile (Test) BodyJump-to-Middle While TranslationAvoids duplicating test codeUnconditional goto incurs no performance penalty for loops compiled in similar fashionGoto Versiongoto middle;loop: Bodymiddle: if (Test) goto loop;Goto (Previous) Version if (!Test) goto done;loop: Body if (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 %eax jmp .L34 # goto Middle.L35: # Loop: imull %edx, %eax # result *= x decl %edx # x--.L34: # Middle: cmpl $1, %edx # x:1 jg .L35 # if >, goto Loop Jump-to-Middle ExampleCarnegie MellonSummaryDo-While loopWhile-Do loopC Codedo Body while (Test);Goto Versionloop: Body if (Test) goto loopWhile versionwhile (Test) BodyDo-While Version if (!Test) goto done;
View Full Document
Unlocking...