計(jì)算機(jī)組成與結(jié)構(gòu)：第二部分-程序和數(shù)據(jù)的機(jī)器級表達(dá) 07-程序的機(jī)器級表示：過程

第3章程序的機(jī)器級表示

——

過程

計(jì)算機(jī)組成與結(jié)構(gòu)

2016年4月主講教師HunanUniversityTodayIA32ProceduresStackStructureCallingConventionsIllustrationsofRecursion&PointersIA32StackRegionofmemorymanagedwithstackdisciplineGrowstowardloweraddressesRegister%esp

contains

loweststackaddressaddressof“top”elementStackPointer:%espStackGrowsDownIncreasingAddressesStack“Top”Stack“Bottom”IA32Stack:Pushpushl

SrcFetchoperandatSrcDecrement%espby4Writeoperandataddressgivenby%esp-4StackGrowsDownIncreasingAddressesStack“Bottom”StackPointer:%espStack“Top”StackPointer:%espStackGrowsDownIncreasingAddressesStack“Top”Stack“Bottom”IA32Stack:Pop+4popl

DestReadvalueataddressgivenby%espIncrement%espby4StorevalueatDest(mustberegister)ProcedureControlFlowUsestacktosupportprocedurecallandreturnProcedurecall:calllabelPushreturnaddressonstackJumptolabelReturnaddress:AddressofthenextinstructionrightaftercallExamplefromdisassembly804854e:e83d060000call8048b90<main>8048553:50pushl%eaxReturnaddress=0x8048553Procedurereturn:retPopaddressfromstackJumptoaddress%esp%esp0x80485530x104%esp%eip%esp%eip0x8048b900x1080x10c0x1100x1040x804854e123ProcedureCallExample0x1080x10c0x1101230x108call8048b90804854e: e83d060000 call8048b90<main>8048553: 50 pushl%eax%eip:programcounter%esp%esp%esp%eip0x104%esp%eip0x80485910x1040x1080x10c0x1100x8048553123ProcedureReturnExample0x1080x10c0x110123ret8048591: c3 ret 0x1080x80485530x8048553%eip:programcounter0x104804854e: e83d060000 call8048b90<main>8048553: 50 pushl%eaxStack-BasedLanguagesLanguagesthatsupportrecursione.g.,C,Pascal,JavaCodemustbe“Reentrant”MultiplesimultaneousinstantiationsofsingleprocedureNeedsomeplacetostorestateofeachinstantiationArgumentsLocalvariablesReturnpointerStackdisciplineStateforgivenprocedureneededforlimitedtimeFromwhencalledtowhenreturnCalleereturnsbeforecallerdoesStackallocatedinFramesstateforsingleprocedureinstantiationFramePointer:%ebpStackFramesContentsLocalvariablesReturninformationTemporaryspaceManagementSpaceallocatedwhenenterprocedure“Set-up”codeDeallocatedwhenreturn“Finish”codeStackPointer:%espStack“Top”PreviousFrameFramefor

procCallChainExampleyoo(…){??who();??}who(…){???amI();???amI();???}amI(…){??amI();??}yoowhoamIamIamIExampleCallChainamIProcedureamI()

isrecursiveExampleyoowhoamIamIamIamIyoo%ebp%espStackyooyoo(…){??who();??}yoo(…){??who();??}ExampleyoowhoamIamIamIamIyoo%ebp%espStackyoowhowho(…){???amI();???amI();???}yoo(…){??who();??}who(…){???amI();???amI();???}ExampleyoowhoamIamIamIamIyoo%ebp%espStackyoowhoamIamI(…){??amI();??}ExampleyoowhoamIamIamIamIyoo%ebp%espStackyoowhoamIamIyoo(…){??who();??}who(…){???amI();???amI();???}amI(…){??amI();??}amI(…){??amI();??}ExampleyoowhoamIamIamIamIyoo%ebp%espStackyoowhoamIamIamIyoo(…){??who();??}who(…){???amI();???amI();???}amI(…){??amI();??}amI(…){??amI();??}amI(…){??amI();??}ExampleyoowhoamIamIamIamIyoo%ebp%espStackyoowhoamIamIyoo(…){??who();??}who(…){???amI();???amI();???}amI(…){??amI();??}amI(…){??amI();??}ExampleyoowhoamIamIamIamIyoo%ebp%espStackyoowhoamIyoo(…){??who();??}who(…){???amI();???amI();???}amI(…){??amI();??}ExampleyoowhoamIamIamIamIyoo%ebp%espStackyoowhoyoo(…){??who();??}who(…){???amI();???amI();???}ExampleyoowhoamIamIamIamIyoo%ebp%espStackyoowhoamIyoo(…){??who();??}who(…){???amI();???amI();???}amI(…){??amI();??}ExampleyoowhoamIamIamIamIyoo%ebp%espStackyoowhoyoo(…){??who();??}who(…){???amI();???amI();???}ExampleyoowhoamIamIamIamIyoo%ebp%espStackyooyoo(…){??who();??}IA32/LinuxStackFrameCurrentStackFrame(“Top”toBottom)“Argumentbuild:”

ParametersforfunctionabouttocallLocalvariables

Ifcan’tkeepinregistersSavedregistercontextOldframepointerCallerStackFrameReturnaddressPushedbycallinstructionArgumentsforthiscallReturnAddrSavedRegisters+LocalVariablesArgumentBuildOld%ebpArgumentsCallerFrameFramepointer

%ebpStackpointer%espCurrentFrameRevisitingswapvoidswap(int*xp,int*yp){intt0=*xp;intt1=*yp;*xp=t1;*yp=t0;}intcourse1=15213;intcourse2=18213;voidcall_swap(){swap(&course1,&course2);}call_swap: ???subl $24,%espmovl $course2,4(%esp)movl $course1,(%esp) call swap ???&course2&course1Rtnadr%espResultingStack???Callingswapfromcall_swap%esp%espsublcallRevisitingswapvoidswap(int*xp,int*yp){intt0=*xp;intt1=*yp;*xp=t1;*yp=t0;}swap:pushl %ebpmovl %esp,%ebppushl %ebxmovl 8(%ebp),%edxmovl 12(%ebp),%ecxmovl (%edx),%ebxmovl (%ecx),%eaxmovl %eax,(%edx)movl %ebx,(%ecx)popl %ebxpopl %ebp retBodySetUpFinishswapSetup#0swap:pushl%ebpmovl%esp,%ebppushl%ebxResultingStack&course2&course1Rtnadr%espEnteringStack???%ebpypxpRtnadr%ebp???%espswapSetup#1swap:pushl%ebpmovl%esp,%ebppushl%ebxResultingStack&course2&course1Rtnadr%espEnteringStack???%ebpypxpRtnadrOld%ebp%ebp???%espswapSetup#2swap:pushl%ebpmovl%esp,%ebppushl%ebxResultingStack&course2&course1Rtnadr%espEnteringStack???%ebpypxpRtnadrOld%ebp%ebp???%espswapSetup#3swap:pushl%ebpmovl%esp,%ebppushl%ebxResultingStack&course2&course1Rtnadr%espEnteringStack???%ebpypxpRtnadrOld%ebp%ebp???%espOld%ebxswapBodymovl8(%ebp),%edx#getxpmovl12(%ebp),%ecx#getyp...ResultingStack&course2&course1Rtnadr%espEnteringStack???%ebpypxpRtnadrOld%ebp%ebp???%espOld%ebxOffsetrelativeto%ebp1284swapFinishStackBeforeFinishpopl %ebxpopl %ebpypxpRtnadrOld%ebp%ebp???%espOld%ebxResultingStackypxpRtnadr???%ebp%espObservationSavedandrestoredregister%ebxNotsofor%eax,%ecx,%edxDisassembledswap08048490<swap>:8048490: 55 push%ebp8048491: 89e5 mov%esp,%ebp8048493: 53 push%ebx8048494: 8b5508 mov0x8(%ebp),%edx8048497: 8b4d0c mov0xc(%ebp),%ecx804849a: 8b1a mov(%edx),%ebx804849c: 8b01 mov(%ecx),%eax804849e: 8902 mov%eax,(%edx)80484a0: 8919 mov%ebx,(%ecx)80484a2: 5b pop%ebx80484a3: 5d pop%ebp80484a4: c3 ret8048426: c7442404189804movl$0x8049818,0x4(%esp)804842d: 08804842e:c704241c980408movl$0x804981c,(%esp) 8048435: e856000000call8048490<swap> 804843a: c9leave 804843b: c3ret CallingCodeTodayIA32ProceduresStackStructureCallingConventionsIllustrationsofRecursion&PointersRegisterSavingConventionsWhenprocedureyoocallswho:yooisthecallerwhoisthecalleeCanregisterbeusedfortemporarystorage?Contentsofregister%edxoverwrittenbywhoThiscouldbetrouble?somethingshouldbedone!Needsomecoordinationyoo: ???movl$15213,%edxcallwhoaddl%edx,%eax ???retwho: ???movl8(%ebp),%edxaddl$18213,%edx ???retRegisterSavingConventionsWhenprocedureyoocallswho:yooisthecallerwhoisthecalleeCanregisterbeusedfortemporarystorage?Conventions“CallerSave”Callersavestemporaryvaluesinitsframebeforethecall“CalleeSave”CalleesavestemporaryvaluesinitsframebeforeusingIA32/Linux+WindowsRegisterUsage%eax,%edx,%ecxCallersavespriortocallifvaluesareusedlater%eaxalsousedtoreturnintegervalue%ebx,%esi,%ediCalleesavesifwantstousethem%esp,%ebpspecialformofcalleesaveRestoredtooriginalvaluesuponexitfromprocedure%eax%edx%ecx%ebx%esi%edi%esp%ebpCaller-SaveTemporariesCallee-SaveTemporariesSpecialTodayIA32ProceduresStackStructureCallingConventions*IllustrationsofRecursion&Pointers（此為高級內(nèi)容）/*Recursivepopcount*/intpcount_r(unsignedx){if(x==0)return0;elsereturn(x&1)+pcount_r(x>>1);}RecursiveFunction黃色：調(diào)用者保存寄存器Registers%eax,%edxusedwithoutfirstsaving%ebxused,butsavedatbeginning&restoredatend綠色：被調(diào)用者保存寄存器pcount_r:pushl %ebpmovl %esp,%ebppushl %ebxsubl $20,%esp;ebx已占用棧4個(gè)字節(jié)movl 8(%ebp),%ebxmovl $0,%eaxtestl %ebx,%ebxje .L3movl %ebx,%eaxshrl %eaxmovl %eax,(%esp)call pcount_rmovl %ebx,%edxandl $1,%edxaddl %edx,%eax.L3:addl $20,%esppopl %ebxPopl %ebpret/*Recursivepopcount*/intpcount_r(unsignedx){if(x==0)return0;elsereturn(x&1)+pcount_r(x>>1);}RecursiveCall#1ActionsSaveoldvalueof%ebxonstackAllocatespaceforargumenttorecursivecallStorexin%ebxpcount_r:pushl %ebpmovl %esp,%ebppushl %ebxsubl $20,%espmovl 8(%ebp),%ebx???xRtnadrOld%ebp%ebp???%espOld%ebxx%ebx/*Recursivepopcount*/intpcount_r(unsignedx){if(x==0)return0;elsereturn(x&1)+pcount_r(x>>1);}RecursiveCall#2ActionsIfx==0,returnwith%eaxsetto0???movl $0,%eaxtestl%ebx,%ebxje .L3???.L3:???retx%ebx/*Recursivepopcount*/intpcount_r(unsignedx){if(x==0)return0;elsereturn(x&1)+pcount_r(x>>1);}RecursiveCall#3ActionsStorex>>1onstackMakerecursivecallEffect%eaxsettofunctionresult%ebxstillhasvalueofx???movl%ebx,%eaxshrl%eaxmovl%eax,(%esp)callpcount_r???RtnadrOld%ebp%ebp???%espOld%ebxx>>1x%ebx/*Recursivepopcount*/intpcount_r(unsignedx){if(x==0)return0;elsereturn(x&1)+pcount_r(x>>1);}RecursiveCall#4Assume%eaxholdsvaluefromrecursivecall%ebxholdsxActionsCompute(x&1)+computedvalueEffect%eaxsettofunctionresult???movl%ebx,%edxandl$1,%edxaddl%edx,%eax???x%ebx/*Recursivepopcount*/intpcount_r(unsignedx){if(x==0)return0;elsereturn(x&1)+pcount_r(x>>1);}RecursiveCall#5ActionsRestorevaluesof%ebxand%ebpRestore%esp???L3:addl $20,%esppopl %ebxpopl %ebpretRtnadrOld%ebp%ebp???%espOld%ebxOld%ebx%ebx%ebp???%espObservationsAboutRecursionHandledWithoutSpecialConsiderationStackframesmeanthateachfunctioncallhasprivatestorageSavedregisters&localvariablesSavedreturnpointerRegistersavingconventionspreventonefunctioncallfromcorruptinganother’sdataStackdisciplinefollowscall/returnpatternIfPcallsQ,thenQreturnsbeforePLast-In,First-OutAlsoworksformutualrecursionPcallsQ;QcallsPPointerCode/*Computex+3*/intadd3(intx){intlocalx=x;incrk(&localx,3);returnlocalx;}GeneratingPointeradd3createspointerandpassesittoincrk/*Incrementvaluebyk*/voidincrk(int*ip,intk){*ip+=k;}ReferencingPointer%espCreatingandInitializingLocalVariableintadd3(intx){intlocalx=x;incrk(&localx,3);returnlocalx;}VariablelocalxmustbestoredonstackBecause:NeedtocreatepointertoitComputepointeras-4(%ebp)Firstpartofadd3xRtnadrOld%ebp%ebp048-4localx=xUnused-12-8-16add3:pushl%ebpmovl %esp,%ebpsubl $24,%esp #Alloc.24bytesmovl 8(%