Machine-Level Programming II:Control FlowSept. 11, 2003Machine-Level Programming II:Control FlowSept. 11, 2003TopicsTopics Condition Codes Setting Testing Control Flow If-then-else Varieties of Loops Switch Statementsclass06.ppt15-213“The course that gives CMU its Zip!”– 2 –15-213, F’03Condition CodesCondition CodesSingle Bit RegistersSingle Bit RegistersCF Carry Flag SF Sign FlagZF Zero Flag OF Overflow FlagImplicitly Set By Arithmetic OperationsImplicitly Set By Arithmetic Operationsaddl Src,DestC analog: t = a + b CF set if carry out from most significant bitUsed 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)NotNotSet by Set by leallealinstructioninstruction– 3 –15-213, F’03Setting Condition Codes (cont.)Setting Condition Codes (cont.)Explicit Setting by Compare InstructionExplicit Setting by Compare Instructioncmpl Src2,Src1 cmpl b,a like computing a-b without setting destination CF set if carry out from most significant bit Used for unsigned comparisons ZF set if a == b SF set if (a-b) < 0 OF set if two’s complement overflow(a>0 && b<0 && (a-b)<0) || (a<0 && b>0 && (a-b)>0)– 4 –15-213, F’03Setting Condition Codes (cont.)Setting Condition Codes (cont.)Explicit Setting by Test instructionExplicit Setting by Test instructiontestl Src2,Src1 Sets condition codes based on value of Src1 & Src2 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’03Reading Condition CodesReading 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)SetXSetXInstructionsInstructions Set single byte based on combinations of condition codes– 6 –15-213, F’03Reading Condition Codes (Cont.)Reading Condition Codes (Cont.)SetXSetXInstructionsInstructions Set single byte based on combinations of condition codes One of 8 addressable byte registers Embedded within first 4 integer registers Does not alter remaining 3 bytes 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’03JumpingJumpingjX 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)jXjXInstructionsInstructions Jump to different part of code depending on condition codes– 8 –15-213, F’03Conditional Branch ExampleConditional Branch Exampleint max(int x, int y){if (x > y)return x;elsereturn y;}_max:pushl %ebpmovl %esp,%ebpmovl 8(%ebp),%edxmovl 12(%ebp),%eaxcmpl %eax,%edxjle L9movl %edx,%eaxL9:movl %ebp,%esppopl %ebpretBodySetUpFinish– 9 –15-213, F’03Conditional Branch Example (Cont.)Conditional Branch Example (Cont.)movl 8(%ebp),%edx # edx = xmovl 12(%ebp),%eax # eax = ycmpl %eax,%edx # x : yjle L9 # if x <= y goto L9movl %edx,%eax # eax = xL9: # Done:int goto_max(int x, int y){int rval = y;int ok = (x <= y);if (ok)goto done;rval = x;done:return rval;}Skipped when x ≤≤≤≤ y C allows “goto” as means of transferring control Closer to machine-level programming style Generally considered bad coding style– 10 –15-213, F’03C Codeint fact_do(int x){int result = 1;do {result *= x;x = x-1;} while (x > 1);return result;}Goto Versionint fact_goto(int x){int result = 1;loop:result *= x;x = x-1;if (x > 1)goto loop;return result;}“Do-While” Loop Example“Do-While” Loop Example Use backward branch to continue looping Only take branch when “while” condition holds– 11 –15-213, F’03Goto Versionint fact_goto(int x){int result = 1;loop:result *= x;x = x-1;if (x > 1)goto loop;return result;}“Do-While” Loop Compilation“Do-While” Loop CompilationRegistersRegisters%edx x%eax result_fact_goto:pushl %ebp # Setupmovl %esp,%ebp # Setupmovl $1,%eax # eax = 1movl 8(%ebp),%edx # edx = xL11:imull %edx,%eax # result *= xdecl %edx # x--cmpl $1,%edx # Compare x : 1jg L11 # if > goto loopmovl %ebp,%esp # Finishpopl %ebp # Finishret # FinishAssembly– 12 –15-213, F’03C Codedo Bodywhile (Test);Goto Versionloop:Bodyif (Test)goto loopGeneral “Do-While” TranslationGeneral “Do-While” Translation Body can be any C statementTypically compound statement: Test is expression returning integer= 0 interpreted as false ≠≠≠≠0 interpreted as true{Statement1;Statement2;…Statementn;}– 13 –15-213, F’03C Codeint fact_while(int x){int result = 1;while (x > 1) {result *= x;x = x-1;};return result;}First Goto Versionint fact_while_goto(int x){int result = 1;loop:if (!(x > 1))goto done; result *= x;x = x-1;goto loop;done:return result;}“While” Loop Example #1“While” Loop Example #1 Is this code equivalent to the do-while version? Must jump out of loop if test fails– 14 –15-213, F’03C Codeint fact_while(int x){int result = 1;while (x > 1) {result *= x;x = x-1;};return result;}Second Goto Versionint 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;}Actual “While” Loop TranslationActual “While” Loop Translation Uses same inner loop as do-while version Guards loop entry with extra test– 15 –15-213, F’03C Codewhile (Test)BodyDo-While Versionif (!Test) goto done;doBodywhile(Test);done:General “While” TranslationGeneral “While” TranslationGoto Versionif (!Test)goto done;loop:Bodyif (Test)goto loop;done:– 16 –15-213, F’03“For” Loop Example“For” Loop ExampleAlgorithmAlgorithm Exploit property that p = p0+ 2p1+ 4p2+ … 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
View Full Document
Unlocking...