Machine-Level Programming II: Control Flow Sept. 12, 2007Condition CodesSetting Condition Codes (cont.)Setting Condition Codes (cont.)Reading Condition CodesReading Condition Codes (Cont.)Reading condition codes: x86-64JumpingConditional Branch ExampleConditional Branch Example (Cont.)General Conditional Expression TranslationConditionals: x86-64General Form with Conditional MoveLimitations of Conditional MoveImplementing Loops“Do-While” Loop Example“Do-While” Loop CompilationGeneral “Do-While” Translation“While” Loop Example #1Alternative “While” Loop TranslationGeneral “While” TranslationNew Style “While” Loop TranslationJump-to-Middle While TranslationJump-to-Middle Example“For” Loop Exampleipwr Computation“For” Loop Example“For” “While” “Do-While”“For” Loop Compilation #1“For” “While” (Jump-to-Middle)“For” Loop Compilation #2Switch StatementsSwitch Statement ExampleJump Table StructureSwitch Statement Example (IA32)Assembly Setup ExplanationJump TableCode Blocks (Partial)Code Blocks (Rest)x86-64 Switch ImplementationIA32 Object CodeIA32 Object Code (cont.)Disassembled TargetsMatching Disassembled Targetsx86-64 Object Codex86-64 Object Code (cont.)Sparse Switch ExampleSparse Switch Code (IA32)Sparse Switch Code StructureSummarizingMachine-Level Programming II:Control FlowSept. 12, 2007Topics Condition Codesz Settingz Testing Control Flowz If-then-elsez Varieties of Loopsz Switch Statementsclass05.ppt15-213“The course that gives CMU its Zip!”15-213, F’07 x86-64 featuresz conditional movez different loop implementation–2–15-213, F’07Condition CodesSingle Bit RegistersCF Carry Flag SF Sign FlagZF Zero Flag OF Overflow FlagImplicitly Set By Arithmetic Operationsaddl Src,Dest addq Src,DestC analog: t = a + b (a = Src, b = Dest) CF set if carry out from most significant bitzUsed to detect unsigned overflow ZF set if t == 0 SF set if t < 0 OF set if two’s complement overflow(a>0 && b>0 && t<0) || (a<0 && b<0 && t>=0)Not set by lea, inc, or dec instructions–3–15-213, F’07Setting Condition Codes (cont.)Explicit Setting by Compare Instructioncmpl Src2,Src1 cmpq Src2,Src1 cmpl b,a like computing a-b without setting destination CF set if carry out from most significant bitz Used for unsigned comparisons ZF set if a == b SF set if (a-b) < 0 OF set if two’s complement overflowz (a>0 && b<0 && (a-b)<0) || (a<0 && b>0 && (a-b)>0)–4–15-213, F’07Setting Condition Codes (cont.)Explicit Setting by Test instructiontestl Src2,Src1testq Src2,Src1 Sets condition codes based on value of Src1 & Src2z Useful to have one of the operands be a mask testl b,a like computing a&b without setting destination ZF set when a&b == 0 SF set when a&b < 0–5–15-213, F’07Reading Condition CodesSetX Condition Descriptionsete ZFEqual / Zerosetne ~ZFNot Equal / Not Zerosets SFNegativesetns ~SFNonnegativesetg ~(SF^OF)&~ZFGreater (Signed)setge ~(SF^OF)Greater or Equal (Signed)setl (SF^OF)Less (Signed)setle (SF^OF)|ZFLess or Equal (Signed)seta ~CF&~ZFAbove (unsigned)setb CFBelow (unsigned)SetX Instructions Set single byte based on combinations of condition codes–6–15-213, F’07Reading Condition Codes (Cont.)SetX Instructions Set single byte based on combinations of condition codes One of 8 addressable byte registersz Embedded within first 4 integer registersz Does not alter remaining 3 bytesz Typically use movzbl to finish job%eax%edx%ecx%ebx%esi%edi%esp%ebp%al%ah%dl%dh%cl%ch%bl%bhint gt (int x, int y){return x > y;}movl 12(%ebp),%eax # eax = ycmpl %eax,8(%ebp) # Compare x : ysetg %al # al = x > ymovzbl %al,%eax # Zero rest of %eaxNote inverted ordering!Body–7–15-213, F’07Reading condition codes: x86-64SetX Instructions Set single byte based on combinations of condition codesz Does not alter remaining 7 bytes x86-64 argumentsz x in %rdiz y in %rsiint gt (long x, long y){return x > y;}xorl %eax, %eax # eax = 0cmpq %rsi, %rdi # Compare x : ysetg %al # al = x > yBody (same for both)long lgt (long x, long y){return x > y;}(32-bit instructions set high order 32 bits to 0)–8–15-213, F’07JumpingjX Condition Descriptionjmp 1Unconditionalje ZFEqual / Zerojne ~ZFNot Equal / Not Zerojs SFNegativejns ~SFNonnegativejg ~(SF^OF)&~ZFGreater (Signed)jge ~(SF^OF)Greater or Equal (Signed)jl (SF^OF)Less (Signed)jle (SF^OF)|ZFLess or Equal (Signed)ja ~CF&~ZFAbove (unsigned)jb CFBelow (unsigned)jX Instructions Jump to different part of code depending on condition codes–9–15-213, F’07Conditional Branch Exampleint absdiff(int x, int y){int result;if (x > y) {result = x-y;} else {result = y-x;}return result;}absdiff:pushl %ebpmovl %esp, %ebpmovl 8(%ebp), %edxmovl 12(%ebp), %eaxcmpl %eax, %edxjle .L7subl %eax, %edxmovl %edx, %eax.L8:leaveret.L7:subl %edx, %eaxjmp .L8Body1SetUpFinishBody2–10–15-213, F’07Conditional Branch Example (Cont.)int goto_ad(int x, int y){int result;if (x<=y) goto Else;result = x-y;Exit:return result;Else:result = y-x;goto Exit;} C allows “goto” as means of transferring controlz Closer to machine-level programming style Generally considered bad coding style.L7: # Else:subl %edx, %eax # result = y-xjmp .L8 # Goto ExitBody1Body2# x in %edx, y in %eaxcmpl %eax, %edx # Compare x:yjle .L7 # <= Goto Elsesubl %eax, %edx # x-= ymovl %edx, %eax # result = x.L8: # Exit:–11–15-213, F’07C Codeval = Test ? Then-Expr ? Else-Expr;Goto Versionnt = !Test;if (nt) goto Else;val = Then-Expr;Done:. . .Else:val = Else-Expr;goto Done;General Conditional Expression Translation Test is expression returning integer= 0 interpreted as false≠0 interpreted as true Create separate code regions for then & else expressions Execute appropriate oneval = x>y ? x-y : y-x;–12–15-213, F’07Conditionals: x86-64 Conditional move instructionz cmovC src, destz Move value from src to dest if condition C holdsz More efficient than conditional branching» Simple & predictable control flowabsdiff: # x in %edi, y in %esimovl %edi, %eax # v = xmovl %esi, %edx # ve = ysubl %esi, %eax # v -= ysubl %edi, %edx # ve -= xcmpl %esi, %edi # x:ycmovle %edx, %eax # v=ve if <=retint absdiff(int x, int y){int result;if (x > y) {result = x-y;} else {result = y-x;}return result;}–13–15-213, F’07C Codeval = Test ? Then-Expr ? Else-Expr;Conditional Move Versionval = Then-Expr;vale = Else-Expr;val = vale if !Test; Both values get computed
View Full Document