Carnegie Mellon Introduction to Computer Systems 15 213 fall 2009 6th Lecture Sep 9th Instructors Majd Sakr and Khaled Harras Carnegie Mellon Last Time Complete memory addressing mode eax 17 eax 2 ebx ecx 8 Arithmetic operations subl eax ecx sall 4 edx edx addl 16 ebp ecx leal 4 edx eax eax imull ecx eax ecx edx ecx eax eax ecx 4 ecx 4 eax eax Mem 16 ebp edx eax ecx Carnegie Mellon Last 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 rax eax r8 r8d rbx edx r9 r9d rcx ecx r10 r10d rdx ebx r11 r11d rsi esi r12 r12d rdi edi r13 r13d rsp esp r14 r14d rbp ebp r15 r15d CF ZF Read out by setx instructions setg setle Or by conditional jumps jle L4 je L10 SF OF Carnegie Mellon Today While loops For loops Switch statements Procedures Carnegie Mellon Do While Loop Example C Code int fact do int x int result 1 do result x x x 1 while x 1 return result Goto Version int fact goto int x int result 1 loop result x x x 1 if x 1 goto loop return result Use backward branch to continue looping Only take branch when while condition holds Carnegie Mellon Do While Loop Compilation Goto Version Assembly Registers edx eax x result int fact goto int x int result 1 fact goto pushl ebp movl esp ebp movl 1 eax movl 8 ebp edx loop result x x x 1 if x 1 goto loop L11 imull edx eax decl edx cmpl 1 edx jg L11 Will result x disappear x Blackboard Compare x 1 if goto loop return result movl ebp esp popl ebp ret Setup Setup eax 1 edx x Finish Finish Finish Carnegie Mellon Do While Loop Compilation Goto Version Assembly Registers edx eax x result int fact goto int x int result 1 fact goto pushl ebp movl esp ebp movl 1 eax movl 8 ebp edx Setup Setup eax 1 edx x loop result x x x 1 if x 1 goto loop L11 imull edx eax decl edx cmpl 1 edx jg L11 result x x Compare x 1 if goto loop return result movl ebp esp popl ebp ret Finish Finish Finish Carnegie Mellon General Do While Translation Goto Version C Code do Body while Test Body Statement1 Statement2 Statementn Test returns integer 0 interpreted as false 0 interpreted as true loop Body if Test goto loop Carnegie Mellon While Loop Example C Code int fact while int x int result 1 while x 1 result x x x 1 return result Goto Version 1 int fact while goto int x int result 1 loop if x 1 goto done result x x x 1 goto loop done return result Is this code equivalent to the do while version Must jump out of loop if test fails Carnegie Mellon Alternative While Loop Translation C Code int fact while int x int result 1 while x 1 result x x x 1 return result Historically used by GCC Uses same inner loop as do while version Guards loop entry with extra test Goto Version 2 int 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 Carnegie Mellon General While Translation While version while Test Body Do While Version if Test goto done do Body while Test done Goto Version if Test goto done loop Body if Test goto loop done Carnegie Mellon New Style While Loop Translation C Code int fact while int x int result 1 while x 1 result x x x 1 return result Recent technique for GCC Both IA32 x86 64 First iteration jumps over body computation within loop Goto Version int fact while goto3 int x int result 1 goto middle loop result x x x 1 middle if x 1 goto loop return result Carnegie Mellon Jump to Middle While Translation C Code while Test Body Goto Version goto middle loop Body middle if Test goto loop Avoids duplicating test code Unconditional goto incurs no performance penalty for loops compiled in similar fashion Goto Previous Version if Test goto done loop Body if Test goto loop done Carnegie Mellon Jump to Middle Example int 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 Carnegie Mellon Summary Do While loop Goto Version C Code do Body while Test loop Body if Test goto loop While Do loop Do While Version While version while Test Body if Test goto done do Body while Test done or Goto Version if Test goto done loop Body if Test goto loop done goto middle loop Body middle if Test goto loop Carnegie Mellon Today While loops For loops Switch statements Procedures Carnegie Mellon For Loop Example Square and Multiply 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 Algorithm Exploit bit representation p p0 2p1 22p2 2n 1pn 1 Gives xp z0 z1 2 z2 2 2 zn 12 2 2 zi 1 when pi 0 zi x when pi 1 Complexity O log p Example n 1 times 310 32 38 32 32 2 2 Carnegie Mellon ipwr 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 iteration result x 3 p 10 1 2 3 4 5 1 1 9 9 59049 3 9 81 6561 43046721 10 10102 5 1012 2 102 1 12 0 Carnegie Mellon For Loop Example int result for result 1 p 0 p p 1 if p 0x1 result x x x x General Form for Init Test Update Body Test p 0 Init result 1 Update p p 1 Body if p 0x1 result x x x x Carnegie Mellon For While Do While For Version for Init Test Update Body Goto Version Init if Test goto done loop Body Update if Test goto loop done While Version Init while Test Body Update Do While Version Init if Test goto done do Body Update while Test done Carnegie Mellon For Loop Compilation 1 For Version for Init Test Update Body Goto Version Init if Test goto done loop Body Update if Test goto loop done for 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 …
View Full Document
Unlocking...