編譯原理英文版課件：Chapter7 Runtime Environments

1、7. Runtime Environments Target codeSource codeScannerParserSemantic analyzerSource code optimizerCode generatorTarget code optimizerTokensSyntax TreeAnnotated TreeIntermediate codeTarget codeThe previous chapters studied the phases of a compiler that perform static analysis of the source languageSca

2、nning, parsing, and static semantic analysisDepends only on the properties of the source languageThis chapter and the next turn to the task of studying how a compiler generates executable codeMuch of the task of code generation dependents on the details of the target machineNevertheless, the general

3、 characteristics of code generation remain the same across a wide variety of architectures, such as runtime environmentRuntime EnvironmentRuntime Environment is The structure of the target computers registers and memory that serves to manage memory and maintain the information needed to guide the ex

4、ecution processRuntime EnvironmentExecution of a program is initially under the control of the operationg system (OS)When a program is invoked: The OS allocates space for the programThe code is loaded into part of the spaceThe OS jumps to the entry point (i.e., “main”)Runtime EnvironmentNote:Registe

5、rs and memory allocation is performed during executionThe compiler can only maintain an environment indirectlyIt must generate code to perform the necessary maintenance operations during program executionThree kinds of runtime environments(1) Fully static environment: FORTRAN77(2) Stack-Based enviro

6、nment: C, C+(3) Fully dynamic environment: LISPContents7.1 Memory Organization During Program ExecutionMore7.3 Stack-Based Runtime EnvironmentsMore7.1 Memory Organization During Program ExecutionMemory OrganizationThe memory of a typical computer may be divided into:A register area A slower directly

7、 addressable random access memory (RAM)The RAM area may be further divided into a code areaa data areaMemory OrganizationThe RAM area may be further divided into a code areaa data areaMemoryLow AddressHigh AddressCodeDataMemory OrganizationCompiler is responsible for :Generating codeOrchestrating us

8、e of the data areaThe code and the layout of the data need to be designed together so that the generated program will function correctlyCode area is fixed prior to executionall code address are computable at compile timecan be visualized as follows:In particular, the entry point for each procedure a

9、nd function is known at compile timecode for procedure ncode for procedure 2code for procedure 1 Code memoryEntry point for procedure 1Entry point for procedure 2Entry point for procedure nMemory OrganizationData areaThe memory area used for the allocation of data that code will access during execut

10、ionGlobal/Static areaStack areaHeap areadynamic data areaGlobal/Static AreaData that can be fixed in memory prior to execution Such data are usually allocated separately in a fixed area in a similar fashion to the codeMemoryLow AddressHigh AddressCodeStatic DataGlobal/Static AreaComprises the global

11、 and static data of a programIn Fortran77, all data are in this class;In Pascal, global variables are in this class;In C, the external and static variables are in this classvoid func() static int x = 0; printf(%dn, x); x = x + 1; extern int GlobalVariable; void SomeFunction(void) +GlobalVariable; Dy

12、namic Data AreaTypically, this memory can be divided into a stack area and a heap area;A stack area used for data whose allocation occurs in LIFO (last-in, first-out) fashion;A heap area used for dynamic allocation occurs not in LIFO fashion, such as pointer allocation and deallocationnew and delete

13、 in C+malloc and free in Cchar*Ptr=NULL;Ptr=(char*)malloc(100*sizeof(char);free(Ptr);The general organization of runtime storagefree spacestackheapglobal/static areaCode area Stack and heap occupy the same areaThe arrows indicate the direction of growth of the stack and heapMemoryLow AddressHigh Add

14、ressProcedure activation recordAn important unit of memory allocationAn invocation of procedure P is an activation of PProcedure activation record is the memory allocated for the local data of a procedure or function when it is calledAn activation record must contain the following sections in minimu

15、mNote: this picture only illustrates the general organization of an activation recordspace for arguments(parameters)space for bookkeeping information, including return addressspace for local dataspace for local temporariesActivation Record (AR) “space for bookkeeping information”Example: F calls GF

16、is suspended until G completes, at which point F resumesGs AR contains information needed to Complete execution of GResume execution of F7.3 Stack-Based Runtime EnvironmentsStack-Based Runtime EnvironmentsThe most common forms of environment among the standand imperative languages such as C, Pascal.

17、For a language, in whichRecursive calls are allowed;Activation records cannot be allocated staticallyLocal variables are newly allocated at each callStack-Based Runtime EnvironmentsExample of recursive functionfacto ( int n )int r;if (n=0) r=1;else r=facto(n-1)*n;return (r);BackStack-Based Runtime E

18、nvironmentsObservationWhen P calls Q, then Q returns before P returnsLifetimes of procedure activations are properly nestedg ( ) return 1 ;f ( ) g ( ) ;main ( ) g ( ); f ( ); ;Stack-Based Runtime EnvironmentsSince activations are properly nested, a stack can track currently active proceduresg ( ) re

19、turn 1 ;f ( ) g ( ) ;main ( ) g ( ); f ( ); ;StackmaingfgActivation records must be allocated in a stack-based fashionThe stack of activation records grows and shrinks with the chain of calls in the executing program.New activation record is allocated at the top of the stack as a new procedure call

20、is madeand deallocated again when the call exitsEach procedure may have several different activation records on the call stack at one time, each representing a distinct call.In a language where all procedures are global (such as C language), the stack-based environment requires two things:(1) Frame

21、pointer (fp)a pointer to the current activation record to allow access to local variable; usually kept in register(2) Control link or dynamic linka point to the previous activation record to allow that activation record to be recovered when the current call endsusually kept in the current activation

22、 recordStack-Based EnvironmentsAdditionally, stack-based environment requires Stack pointer(sp)Points to the last location allocated on the call stackis also called the top of stack pointerstackglobal/static areaCode area spExample: The simple recursive implementation of Euclids algorithm to compute

23、 the greatest common divisor of two non-negative integer # include int x,y;int gcd(int u, int v) if (v=0) return u;else return gcd(v,u%v);main( )scanf(“%d%d”,&x,&y);printf(“%dn”,gcd(x,y);return 0;Suppose the user inputs the values 15 and 10 to this program. u: 5v:0control linkreturn addressx: 15y: 1

24、0u: 15v:10control linkreturn addressu: 10v:5control linkreturn addressGlobal/static areaActivation record of mainActivation record of first call to gcdActivation record of second call to gcdActivation record of third call to gcdfree spaceDirection of stack growthfpspExplanation:Control linkpoints to the location of the control link of the previous activation recordusually kept in the current activation record, between the parameter area and the local variable area fp: points