计算机组成与结构：第二部分-程序和数据的机器级表达 07-程序的机器级表示：过程

第3章程序的机器级表示

——

过程

计算机组成与结构

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（此为高级内容）/*Recursivepopcount*/intpcount_r(unsignedx){if(x==0)return0;elsereturn(x&1)+pcount_r(x>>1);}RecursiveFunction黄色：调用者保存寄存器Registers%eax,%edxusedwithoutfirstsaving%ebxused,butsavedatbeginning&restoredatend绿色：被调用者保存寄存器pcount_r:pushl %ebpmovl %esp,%ebppushl %ebxsubl $20,%esp;ebx已占用栈4个字节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(%