Machine-Level Programming II: Control Flow Sept. 09, 2008Processor State (IA32, Partial)Condition CodesSetting Condition Codes (cont.)Slide 5Reading 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” “While” “Do-While”“For” “While” (Jump-to-Middle)Switch 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. 09, 2008TopicsCondition CodesSettingTestingControl FlowIf-then-elseVarieties of LoopsSwitch Statementsclass05.ppt15-213“The course that gives CMU its Zip!”15-213, F’08x86-64 featuresconditional movedifferent loop implementation– 2 –15-213, F’08Processor State (IA32, Partial)Information about currently executing programTemporary dataLocation of current code control pointLocation of runtime stackStatus of recent tests%eax%edx%ecx%ebx%esi%edi%esp%ebp%eipGeneral purposeregistersCurrent stack topCurrent stack frameInstruction pointerCF ZF SF OFCondition codes– 3 –15-213, F’08Condition 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 bitUsed to detect unsigned overflowZF set if t == 0SF set if t < 0OF 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– 4 –15-213, F’08Setting Condition Codes (cont.)Explicit Setting by Compare Instructioncmpl Src2,Src1 cmpq Src2,Src1 cmpl b,a like computing a-b without setting destinationCF set if carry out from most significant bitUsed for unsigned comparisonsZF set if a == bSF set if (a-b) < 0OF set if two’s complement overflow(a>0 && b<0 && (a-b)<0) || (a<0 && b>0 && (a-b)>0)– 5 –15-213, F’08Setting Condition Codes (cont.)Explicit Setting by Test instructiontestl Src2,Src1testq Src2,Src1Sets condition codes based on value of Src1 & Src2Useful to have one of the operands be a mask testl b,a like computing a&b without setting destination ZF set when a&b == 0SF set when a&b < 0– 6 –15-213, F’08Reading 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 InstructionsSet single byte based on combinations of condition codes– 7 –15-213, F’08Reading Condition Codes (Cont.)SetX InstructionsSet single byte based on combinations of condition codesOne of 8 addressable byte registersEmbedded within first 4 integer registersDoes not alter remaining 3 bytesTypically 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– 8 –15-213, F’08Reading condition codes: x86-64SetX InstructionsSet single byte based on combinations of condition codesDoes not alter remaining 7 bytesx86-64 arguments x in %rdi 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)– 9 –15-213, F’08JumpingjX 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 InstructionsJump to different part of code depending on condition codes– 10 –15-213, F’08Conditional 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– 11 –15-213, F’08Conditional 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 controlCloser to machine-level programming styleGenerally 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:– 12 –15-213, F’08C 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 TranslationTest is expression returning integer= 0 interpreted as false0 interpreted as trueCreate separate code regions for then & else expressionsExecute appropriate oneval = x>y ? x-y : y-x;– 13 –15-213, F’08Conditionals: x86-64Conditional move instructioncmovC src, destMove value from src to dest if condition C holdsMore efficient than conditional branching»Simple & predictable control flowabsdiff: # x in %edi, y in %esimovl %edi, %eax # v = xmovl %esi, %edx # ve = ysubl
View Full Document