Slide 1Last TimeLast TimeLast TimeToday“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)x86-64 Switch ImplementationIA32 Object CodeIA32 Object Code (cont.)Disassembled TargetsMatching Disassembled Targetsx86-64 Object Codex86-64 Object Code (cont.)SummarizingTodayIA32 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/18-243, spring 20097th Lecture, Feb. 3rd Instructors: Gregory Kesden and Markus PüschelCarnegie 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, …Better support for passing function arguments in registersControlCondition 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 MellonLast TimeDo-While loopWhile-Do loopC Codedo Body while (Test);Goto Versionloop: Body if (Test) goto loopWhile versionwhile (Test) BodyDo-While Version if (!Test) goto done; do Body while(Test);done:Goto Version if (!Test) goto done;loop: Body if (Test) goto loop;done:goto middle;loop: Bodymiddle: if (Test) goto loop;orCarnegie MellonTodayFor loopsSwitch statementsProceduresCarnegie Mellon“For” Loop Example: Square-and-MultiplyAlgorithmExploit bit representation: p = p0 + 2p1 + 22p2 + … 2n–1pn–1Gives: xp = z0 · z1 2 · (z2 2) 2 · … · (…((zn –12) 2 )…) 2zi = 1 when pi = 0zi = x when pi = 1Complexity O(log p)/* Compute x raised to nonnegative power p */int ipwr_for(int x, unsigned p){int result;for (result = 1; p != 0; p = p>>1) {if (p & 0x1) result *= x; x = x*x; } return result;}n–1 timesExample310= 32 * 38= 32 * ((32)2)2Carnegie Mellonipwr Computation/* Compute x raised to nonnegative power p */int ipwr_for(int x, unsigned p){int result;for (result = 1; p != 0; p = p>>1) {if (p & 0x1) result *= x; x = x*x; } return result;}before iterationresult x=3 p=1011 3 10=1010221 9 5= 101239 81 2= 10249 6561 1= 12559049 43046721 0Carnegie Mellon“For” Loop Examplefor (Init; Test; Update) Body int result; for (result = 1; p != 0; p = p>>1) { if (p & 0x1) result *= x; x = x*x; }General FormInitresult = 1Testp != 0Updatep = p >> 1Body { if (p & 0x1) result *= x; x = x*x; }Carnegie Mellon“For” “While” “Do-While”for (Init; Test; Update ) BodyInit;while (Test ) { Body Update ;}Goto Version Init; if (!Test) goto done;loop: Body Update ; if (Test) goto loop;done:While VersionFor VersionDo-While Version Init; if (!Test) goto done; do { Body Update ; } while (Test)done:Carnegie MellonFor-Loop: Compilation #1for (Init; Test; Update ) BodyGoto Version Init; if (!Test) goto done;loop: Body Update ; if (Test) goto loop;done:For Versionfor (result = 1; p != 0; p = p>>1){ if (p & 0x1) result *= x; x = x*x;} result = 1; if (p == 0) goto done;loop: if (p & 0x1) result *= x; x = x*x; p = p >> 1; if (p != 0) goto loop;done:Carnegie Mellon“For” “While” (Jump-to-Middle)for (Init; Test; Update ) BodyInit;while (Test ) { Body Update ;} Init; goto middle;loop: Body Update ;middle: if (Test) goto loop;done:While VersionFor VersionGoto VersionCarnegie MellonFor-Loop: Compilation #2for (Init; Test; Update ) Body Init; goto middle;loop: Body Update ;middle: if (Test) goto loop;done:For VersionGoto Versionfor (result = 1; p != 0; p = p>>1){ if (p & 0x1) result *= x; x = x*x;} result = 1;goto middle;loop: if (p & 0x1) result *= x; x = x*x; p = p >> 1;middle: if (p != 0) goto loop;done:Carnegie MellonTodayFor loopsSwitch statementsProceduresCarnegie MellonSwitch Statement ExampleMultiple case labelsHere: 5, 6Fall through casesHere: 2Missing casesHere: 4long switch_eg (long x, long y, long z){ long w = 1; switch(x) { case 1: w = y*z; break; case 2: w = y/z; /* Fall Through */ case 3: w += z; break; case 5: case 6: w -= z; break; default: w = 2; } return w;}Carnegie MellonJump Table StructureCode Block0Targ0:Code Block1Targ1:Code Block2Targ2:Code Blockn–1Targn-1:•••Targ0Targ1Targ2Targn-1•••jtab:target = JTab[x];goto *target;switch(x) { case val_0: Block 0 case val_1: Block 1 • • • case val_n-1: Block n–1}Switch FormApproximate TranslationJump TableJump TargetsCarnegie MellonSwitch Statement Example (IA32)Setup:switch_eg:pushl %ebp # Setupmovl %esp, %ebp # Setuppushl %ebx # Setupmovl $1, %ebx # w = 1movl 8(%ebp), %edx # edx = xmovl 16(%ebp), %ecx # ecx = zcmpl $6, %edx # x:6ja .L61 # if > goto defaultjmp *.L62(,%edx,4) # goto JTab[x]long switch_eg(long x, long y, long z){ long w = 1; switch(x) { . . . } return w;}Will disappearBlackboard?Carnegie MellonSwitch Statement Example (IA32)Setup:switch_eg:pushl %ebp # Setupmovl %esp, %ebp # Setuppushl %ebx # Setupmovl $1,
View Full Document
Unlocking...