第3章程序的機器級表示:

——控制

計算機組成與結構

2016年4月主講教師HunanUniversityTodayControl:ConditioncodesConditionalbranchesLoopsSwitchstatementsHunanUniversityProcessorState(IA32,Partial)InformationaboutcurrentlyexecutingprogramTemporarydata

(%eax,…)Locationofruntimestack

(%ebp,%esp)Locationofcurrentcodecontrolpoint

(%eip,…)Statusofrecenttests

(CF,ZF,SF,OF)%eipGeneralpurposeregistersCurrentstacktopCurrentstackframeInstructionpointerCFZFSFOFConditioncodes%eax%ecx%edx%ebx%esi%edi%esp%ebpHunanUniversityConditionCodes(ImplicitSetting)SinglebitregistersCFCarryFlag(forunsigned)SFSignFlag(forsigned)ZFZeroFlag OFOverflowFlag(forsigned)Implicitlyset(thinkofitassideeffect)byarithmeticoperationsExample:addl/addqSrc,Dest?t=a+bCFsetifcarryoutfrommostsignificantbit(unsignedoverflow)ZFsetift==0SFsetift<0(assigned)OFsetiftwo’s-complement(signed)overflow

(a>0&&b>0&&t<0)||(a<0&&b<0&&t>=0)Notsetbylea/movinstructionHunanUniversityConditionCodes(ExplicitSetting:Compare)ExplicitSettingbyCompareInstructioncmpl/cmpqSrc2,Src1 ;Src1–Src2,影響標志位cmplb,alikecomputinga-bwithoutsettingdestinationCFsetifcarryoutfrommostsignificantbit(usedforunsignedcomparisons)ZFsetifa==bSFsetif(a-b)<0(assigned)OFsetiftwo’s-complement(signed)overflow

(a>0&&b<0&&(a-b)<0)||(a<0&&b>0&&(a-b)>0)HunanUniversityConditionCodes(ExplicitSetting:Test)ExplicitSettingbyTestinstructiontestl/testqSrc2,Src1 ；Src1&Src2，影響標志位testlb,alikecomputinga&bwithoutsettingdestinationSetsconditioncodesbasedonvalueofSrc1&Src2UsefultohaveoneoftheoperandsbeamaskZFsetwhena&b==0SFsetwhena&b<0OF/CFclearHunanUniversityReadingConditionCodesSetXInstructionsSetsinglebytebasedoncombinationsofconditioncodesSetXConditionDescriptionseteZFEqual/Zerosetne~ZFNotEqual/NotZerosetsSFNegativesetns~SFNonnegativesetg~(SF^OF)&~ZFGreater(Signed)setge~(SF^OF)GreaterorEqual(Signed)setl(SF^OF)Less(Signed)setle(SF^OF)|ZFLessorEqual(Signed)seta~CF&~ZFAbove(unsigned)setbCFBelow(unsigned)HunanUniversitymovl12(%ebp),%eax #eax=ycmpl%eax,8(%ebp) #Comparex:ysetg%al #al=x>ymovzbl%al,%eax #Zerorestof%eaxReadingConditionCodes(Cont.)SetXInstructions:SetsinglebytebasedoncombinationofconditioncodesOneof8addressablebyteregistersDoesnotalterremaining3bytesTypicallyusemovzbltofinishjobintgt(intx,inty){returnx>y;}Body%eax%ah%alHunanUniversityReadingConditionCodes:x86-64intgt(intx,inty){returnx>y;}movl12(%ebp),%eaxcmpl%eax,8(%ebp)setg%almovzbl%al,%eaxBodieslonglgt(longx,longy){returnx>y;}SetXInstructions:SetsinglebytebasedoncombinationofconditioncodesDoesnotalterremaining3bytescmpq%rsi,%rdisetg%almovzbq%al,%raxTodayControl:ConditioncodesConditionalbranches&MovesLoopsSwitchstatementsHunanUniversityJumpingjXInstructionsJumptodifferentpartofcodedependingonconditioncodesjXConditionDescriptionjmp1UnconditionaljeZFEqual/Zerojne~ZFNotEqual/NotZerojsSFNegativejns~SFNonnegativejg~(SF^OF)&~ZFGreater(Signed)jge~(SF^OF)GreaterorEqual(Signed)jl(SF^OF)Less(Signed)jle(SF^OF)|ZFLessorEqual(Signed)ja~CF&~ZFAbove(unsigned)jbCFBelow(unsigned)HunanUniversityConditionalBranchExample（OldStyle）intabsdiff(intx,inty){intresult;if(x>y){result=x-y;}else{result=y-x;}returnresult;}absdiff:pushl%ebpmovl%esp,%ebpmovl8(%ebp),%edxmovl12(%ebp),%eaxcmpl%eax,%edxjle.L6subl%eax,%edxmovl%edx,%eaxjmp.L7.L6:subl%edx,%eax.L7:popl%ebpretBody1SetupFinishBody2bBody2aabsdiff:pushl%ebpmovl%esp,%ebpmovl8(%ebp),%edxmovl12(%ebp),%eaxcmpl%eax,%edxjle.L6subl%eax,%edxmovl%edx,%eaxjmp.L7.L6:subl%edx,%eax.L7:popl%ebpretBody1SetupFinishBody2bBody2aConditionalBranchExample(Cont.)intgoto_ad(intx,inty){intresult;if(x<=y)gotoElse;result=x-y;gotoExit;Else:result=y-x;Exit:returnresult;}Callows“goto”asmeansoftransferringcontrolClosertomachine-levelprogrammingstyleGenerallyconsideredbadcodingstyleCCodeval=Test?Then_Expr:Else_Expr;GotoVersionnt=!Test; if(nt)gotoElse;val=Then_Expr;gotoDone;Else:val=Else_Expr;Done: ...GeneralConditionalExpressionTranslation

（UsingBranches）Testisexpressionreturninginteger=0interpretedasfalse≠0interpretedastrueCreateseparatecoderegionsforthen&elseexpressionsExecuteappropriateoneval=x>y?x-y:y-x;CCodetval=Then_Expr;result=Else_Expr;t=Test;if(t)result=tval;returnresult;UsingConditionalMovesConditionalMoveInstructionsInstructionsupports:if(Test)DestSrcSupportedinpost-1995x86processorsGCCdoesnotalwaysusethemWantstopreservecompatibilitywithancientprocessorsEnabledforx86-64Useswitch–march=686forIA32Why?BranchesareverydisruptivetoinstructionflowthroughpipelinesConditionalmovedonotrequirecontroltransferintcomvdiff(intx,inty){inttval=y-x;

intrval=x-y;inttest=x<y;if(test)rval=tval;resultrval;}absdiff:movl8(%ebp),%ecxmovl12(%ebp),%edxmovl%edx,%ebxsubl%ecx,%ebxmovl%ecx,%eaxsubl%edx,%eaxcmpl%edx,%ecxcmovl%ebx,%eaxConditionalMovesExampleabsdiff:pushl%ebpmovl%esp,%ebpmovl8(%ebp),%edxmovl12(%ebp),%eaxcmpl%eax,%edxjle.L6subl%eax,%edxmovl%edx,%eaxjmp.L7.L6:subl%edx,%eax.L7:popl%ebpretExpensiveComputationsBadCasesforConditionalMoveBothvaluesgetcomputedOnlymakessensewhencomputationsareverysimpleval=Test(x)?Hard1(x):Hard2(x);RiskyComputationsBothvaluesgetcomputedMayhaveundesirableeffectsval=p?*p:0;ComputationswithsideeffectsBothvaluesgetcomputedMustbeside-effectfreeval=x>0?x*=7:x+=3;TodayControl:ConditioncodesConditionalbranchesandmovesLoopsSwitchstatementsHunanUniversityCCodeintpcount_do(unsignedx){intresult=0;

do{result+=x&0x1;x>>=1;}while(x);returnresult;}GotoVersionintpcount_do(unsignedx){intresult=0;loop:result+=x&0x1;x>>=1;

if(x)gotoloop;returnresult;}“Do-While”LoopExampleCountnumberof1’sinargumentx(“popcount”)UseconditionalbranchtoeithercontinueloopingortoexitloopHunanUniversityRegisters:%edxx%ecxresultCCode“Do-While”LoopCompilation

movl $0,%ecx #result=0.L2: #loop:movl %edx,%eaxandl $1,%eax #t=x&1addl %eax,%ecx #result+=tshrl %edx #x>>=1jne .L2 #If!0,gotoloopHunanUniversityintpcount_do(unsignedx){intresult=0;do{result+=x&0x1;x>>=1;}while(x);returnresult;}CCodeforwhileloopCcodefordoloop“While”LoopExampleIswhileloopcodeequivalenttothedo-whileversion?Mustjumpoutofloopiftestfailsintpcount_while(unsignedx){intresult=0;

while(x){result+=x&0x1;x>>=1;}returnresult;}intpcount_do(unsignedx){intresult=0;do{result+=x&0x1;x>>=1;}

while(x)returnresult;}HunanUniversityCCodeGotoversion“While”LoopExampleIsthiscodeequivalenttothegotoversion?Mustjumpoutofloopiftestfailsintpcount_while(unsignedx){intresult=0;

while(x){result+=x&0x1;x>>=1;}returnresult;}intpcount_do(unsignedx){intresult=0;if(!x)gotodoneLoop:result+=x&0x1;x>>=1;if(x)gotoloopDone:returnresult;}HunanUniversityCCode“For”LoopExampleIsthiscodeequivalenttootherversions?#defineWSIZE8*sizeof(int)intpcount_for(unsignedx){inti;intresult=0;

for(i=0;i<WSIZE;i++){unsignedmask=1<<i;result+=(x&mask)!=0;}returnresult;}HunanUniversity“For”LoopFormfor(Init;Test;Update)BodyGeneralFormfor(i=0;i<WSIZE;i++){unsignedmask=1<<i;result+=(x&mask)!=0;}i=0i<WSIZEi++{unsignedmask=1<<i;result+=(x&mask)!=0;}InitTestUpdateBodyHunanUniversity“For”Loop…Gotofor(Init;Test;Update)BodyForVersionInit;while(Test){BodyUpdate;}WhileVersionInit;if(!Test)gotodone;doBodyUpdatewhile(Test);done:Init;if(!Test)gotodone;loop:BodyUpdateif(Test)gotoloop;done:HunanUniversityDo-whileVersionGotoVersionTodayControl:ConditioncodesConditionalbranchesandmovesLoopsSwitchstatementsSwitchStatementExampleMultiplecaselabelsHere:5&6FallthroughcasesHere:2MissingcasesHere:4longswitch_eg(longx,longy,longz){longw=1;switch(x){case1:w=y*z;break;case2:w=y/z;/*FallThrough*/case3:w+=z;break;case5:case6:w-=z;break;default:w=2;}returnw;}JumpTableStructureCodeBlock0Targ0:CodeBlock1Targ1:CodeBlock2Targ2:CodeBlockn–1Targn-1:???Targ0Targ1Targ2Targn-1???jtab:target=JTab[x];goto*target;switch(x){caseval_0:Block0caseval_1:Block1?

?

?caseval_n-1:Blockn–1}SwitchFormApproximateTranslationJumpTableJumpTargetsSwitchStatementExample(IA32)Setup:longswitch_eg(longx,longy,longz){longw=1;switch(x){...}returnw;}switch_eg:pushl %ebp #Setupmovl %esp,%ebp #Setupmovl 8(%ebp),%eax #%eax=xcmpl $6,%eax #Comparex:6ja .L8 #Ifunsigned>gotodefaultjmp *.L4(,%eax,4)#Goto*JTab[x]Whatrangeofvaluestakesdefault?NotethatwnotinitializedhereSwitchStatementExample(IA32)longswitch_eg(longx,longy,longz){longw=1;switch(x){...}returnw;}Indirect

jumpJumptable.section .rodata .align4.L4: .long .L8 #x=0 .long .L3 #x=1 .long .L5 #x=2 .long .L9 #x=3 .long .L8 #x=4 .long .L7 #x=5 .long .L7 #x=6Setup:switch_eg:pushl %ebp #Setupmovl %esp,%ebp #Setupmovl 8(%ebp),%eax #eax=xcmpl $6,%eax #Comparex:6ja .L8 #Ifunsigned>gotodefaultjmp *.L4(,%eax,4) #Goto*JTab[x]AssemblySetupExplanationTableStructureEachtargetrequires4bytesBaseaddressat.L4JumpingDirect：jmp.L2Jumptargetisdenotedbylabel.L2Indirect：jmp*.L4(,%eax,4)Startofjumptable：.L4Mustscalebyfactorof4(labelshave32-bits=4BytesonIA32)FetchtargetfromeffectiveAddress.L4+eax*4Onlyfor0≤x≤6Jumptable.section .rodata .align4.L4: .long .L8 #x=0 .long .L3 #x=1 .long .L5 #x=2 .long .L9 #x=3 .long .L8 #x=4 .long .L7 #x=5 .long .L7 #x=6.section .rodata .align4.L4: .long .L8 #x=0 .long .L3 #x=1 .long .L5 #x=2 .long .L9 #x=3 .long .L8 #x=4 .long .L7 #x=5 .long .L7 #x=6JumpTableJumptableswitch(x){case1://.L3w=y*z;break;case2://.L5w=y/z;/*FallThrough*/case3://.L9w+=z;break;case5:case6://.L7w-=z;break;default://.L8w=2;}CodeBlocks(x==1).L3:#x==1movl 12(%ebp),%eax#yimull 16(%ebp),%eax#w=y*zjmp .L2 #Gotodoneswitch(x){case1: //.L3w=y*z;break;...}HandlingFall-Throughlongw=1;...switch(x){... case2:w=y/z;/*FallThrough*/case3:w+=z;break;...}case2:w=y/z;gotomerge;case3:w=1;merge:w+=z;CodeBlocks(x==2,x==3).L5: #x==2movl 12(%ebp),%eax#ycltdidivl16(%ebp)#y/z

jmp.L6.L9: #x==3movl $1,%eax #w=1.L6: #merge:addl 16(%ebp),%eax#+=zjmp .L2 #Gotodonelongw=1;...switch(x){...case2: //.L3w=y*z;/*FallThrough*/case3://.L5w+=z;break;...}CodeBlocks(x==5,x==6,default).L7: #x==5,6movl $1,%eax#w=1subl 16(%ebp),%eax#w=1-zjmp.L2#gotodone.L8: #defaultmovl$2,%eax#w=2.L2: #doneswitch(x){...case5://.L7case6://.L7w-=z;break;default://.L8w=2;}SwitchCode(Finish)NoteworthyFeaturesJumptableavoidssequencingthroughcasesConstanttime,ratherthanlinearUsejumptabletohandleholesandduplicatetagsUseprogramsequencingtohandlefall-throughDon’tinitializew=1unlessreallyneeditreturnw;.L2: #done:popl

%ebpretIA32ObjectCodeSetupLabel.L8becomesaddress0x80484b8Label.L4becomesaddress0x804868008048480<switch_eg>:...8048489: 772d

ja80484b8<switch_eg+0x38>804848b: ff248580860408jmp*0x8048680(,%eax,4)switch_eg:...ja.L8 #Ifunsigned>gotodefaultjmp*.L4(,%eax,4) #Goto*JTab[x]AssemblyCodeDisassembledObjectCodeIA32ObjectCode(cont.)JumpTableDoesn’tshowupindisassembledcodeCaninspectusingGDBgdbswitch(gdb)x/7xw0x8048680Examine7hexadecimalformat“words”(4-byteseach)Usecommand“helpx”togetformatdocumentation0x8048680: 0x080484b8 0x08048492 0x0804849b 0x080484a40x8048690: 0x080484b8 0x080484ae 0x080484ae.section .rodata .align4.L4: .long .L8 #x=0 .long .L3 #x=1 .long .L5 #x=2 .long .L9 #x=3 .long .L8 #x=4 .long .L7 #x=5 .long .L7 #x=6IA32ObjectCode(cont.)DecipheringJumpTable0x8048680: 0x080484b8 0x08048492 0x0804849b 0x080484a40x8048690: 0x080484b8 0x080484ae 0x080484aeAddressValuex0x80486800x80484b800x80486840x804849210x80486880x804849b20x804868c0x80484a430x80486900x80484b840x80486940x80484ae50x80486980x80484ae6DisassembledTargets8048492:b8450c mov0xc(%ebp),%eax