Carnegie MellonIntroduction to Computer Systems15-213/18-243, spring 20097thLecture, Feb. 3rdInstructors:Gregory Kesden and Markus PüschelCarnegie 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, … Better support for passing function arguments in registers 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 MellonLast Time 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 For loops Switch statements ProceduresCarnegie Mellon“For” Loop Example: Square-and-Multiply Algorithm Exploit bit representation: p = p0+ 2p1+ 22p2+ … 2n–1pn–1 Gives: xp= z0· z12· (z22)2· … · (…((zn –12)2 )…)2zi= 1 when pi= 0zi= x when pi= 1 Complexity 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 iterationresultx=3p=1011310=101022195= 101239812= 1024965611= 12559049430467210Carnegie Mellon“For” Loop Examplefor (Init; Test; Update)Bodyint 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 ) {BodyUpdate ;}Goto VersionInit;if (!Test)goto done;loop:BodyUpdate ;if (Test)goto loop;done:While VersionFor VersionDo-While VersionInit;if (!Test)goto done;do {BodyUpdate ;} while (Test)done:Carnegie MellonFor-Loop: Compilation #1for (Init; Test; Update )BodyGoto VersionInit;if (!Test)goto done;loop:BodyUpdate ;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 ) {BodyUpdate ;}Init;goto middle;loop:BodyUpdate ;middle:if (Test)goto loop;done:While VersionFor VersionGoto VersionCarnegie MellonFor-Loop: Compilation #2for (Init; Test; Update )BodyInit;goto middle;loop:BodyUpdate ;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 MellonToday For loops Switch statements ProceduresCarnegie MellonSwitch Statement Example Multiple case labels Here: 5, 6 Fall through cases Here: 2 Missing cases Here: 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 0case 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, %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;}Indirect jumpJump table.section .rodata.align 4.L62:.long .L61 # x = 0.long .L56 # x = 1.long .L57 # x = 2.long .L58 # x = 3.long .L61 # x = 4.long .L60 # x = 5.long .L60 # x = 6Carnegie MellonAssembly Setup Explanation Table Structure Each target requires 4 bytes Base address at .L62 JumpingDirect: jmp .L61 Jump target is denoted by label .L61Indirect: jmp *.L62(,%edx,4) Start of jump table: .L62 Must scale by factor of 4 (labels have 32-bit = 4 Bytes on IA32) Fetch target from effective Address .L61 + edx*4 Only for 0 x 6.section .rodata.align 4.L62:.long .L61 # x = 0.long .L56 # x = 1.long .L57 # x = 2.long .L58 # x = 3.long .L61 # x = 4.long .L60 # x = 5.long .L60 # x = 6Jump tableCarnegie MellonJump Table.section .rodata.align 4.L62:.long .L61 # x = 0.long .L56 # x = 1.long .L57 # x = 2.long .L58 # x = 3.long .L61 # x = 4.long .L60 # x = 5.long .L60 # x = 6Jump tableswitch(x) {case 1: // .L56w = y*z;break;case 2: // .L57w = y/z;/* Fall Through */case 3: // .L58w += z;break;case 5:case 6: // .L60w -= z;break;default: // .L61w = 2;}Carnegie MellonCode Blocks (Partial).L61: // Default casemovl $2, %ebx # w = 2movl %ebx, %eax # Return wpopl %ebxleaveret.L57: // Case 2:movl 12(%ebp), %eax # ycltd # Div prepidivl %ecx # y/z movl %eax, %ebx # w = y/z# Fall through.L58: // Case 3: addl %ecx,
View Full Document