清华大学：《编译原理》课程教学资源（PPT课件）RUN-Time Organization

RUN-Time Organization Compiler phase- Before writing a code generator,we must decide how to marshal the resources of the target machine (instructions,storage,and system software)in order to implement the source language.This is called run-time organization

RUN-Time Organization Compiler phase— Before writing a code generator, we must decide how to marshal the resources of the target machine (instructions, storage, and system software) in order to implement the source language. This is called run-time organization

The key issues in run-time organization 1 Data representation:How should we represent the values of each source-language type in the target machine? Expression evaluation:How should we organize the evaluation of expressions,taking care of intermediate results? 1 Storage allocation:How should we organize storage for variables,taking into account the different lifetimes of global,local and heap variables? 1 Routines:How should we implement procedures,functions, and parameters,in terms of low-level routines? Run-time organization for object-oriented languages:How should we represent objects and methods?

The key issues in run-time organization l Data representation: How should we represent the values of each source-language type in the target machine? Expression evaluation: How should we organize the evaluation of expressions, taking care of intermediate results? l Storage allocation: How should we organize storage for variables, taking into account the different lifetimes of global, local and heap variables? l Routines: How should we implement procedures, functions, and parameters, in terms of low-level routines? Run-time organization for object-oriented languages: How should we represent objects and methods?

Storage classes global:exist throughout lifetime of entire program and can be referenced anywhere. static:exist throughout lifetime of entire program but can only be referenced in the function (or module)in which they are declared. local:(also called automatic)exist only for the duration of a call to the routine in which they are declared;a new variable is created each time the routine is entered (and destroyed on exit). dynamic:variables that are created during program execution;usually represented by an address held in a variable of one of the above classes

Storage classes global: exist throughout lifetime of entire program and can be referenced anywhere. static: exist throughout lifetime of entire program but can only be referenced in the function (or module) in which they are declared. local: (also called automatic) exist only for the duration of a call to the routine in which they are declared; a new variable is created each time the routine is entered (and destroyed on exit). dynamic: variables that are created during program execution; usually represented by an address held in a variable of one of the above classes

Both global and static variables have a single instance that persists throughout life of program and the usual implementation for these is a collection of memory locations in the global/static data segment of the executable.These locations are fixed at the end of the compilation process. Local variables only come into existence on entry to a routine and persist until its exit.To handle these we use a runtime stack that holds the values of locals.The area of memory used to hold all the locals of a routine is called the stack frame(active record).The stack frame for the routine currently executing will be on top of the stack. Dynamic allocation of further storage during the run of a program is done by calling library functions (e.g.,malloc()).This storage is obtained from memory in a different segment than the program code, global/static,or stack.Such memory is called the heap

Both global and static variables have a single instance that persists throughout life of program and the usual implementation for these is a collection of memory locations in the global/static data segment of the executable. These locations are fixed at the end of the compilation process. Local variables only come into existence on entry to a routine and persist until its exit. To handle these we use a runtime stack that holds the values of locals. The area of memory used to hold all the locals of a routine is called the stack frame(active record). The stack frame for the routine currently executing will be on top of the stack. Dynamic allocation of further storage during the run of a program is done by calling library functions (e.g., malloc()). This storage is obtained from memory in a different segment than the program code, global/static, or stack. Such memory is called the heap

Here's a map depicting the address space of an executing program: Stack Heap Global/static data Code

Here’s a map depicting the address space of an executing program:

In a stack frame (activation record)we hold the following information: 1)frame pointer:pointer value of the previous stack frame so we can reset the top of stack when we exit this function.This is also sometimes called the dynamic link 2)static link:in languages (like Pascal but not C or Decaf)that allownested function declarations,a function may be able to access the variables of the function(s)within which it is declared.In the static link,we hold the pointer value of the stack frame in which the current function was declared. 3)return address:point in the code to which we return at the end of execution of the current function. 4)values of arguments passed to the function and locals and temporaries used in the function

In a stack frame (activation record) we hold the following information: 1) frame pointer: pointer value of the previous stack frame so we can reset the top of stack when we exit this function. This is also sometimes called the dynamic link. 2) static link: in languages (like Pascal but not C or Decaf) that allow nested function declarations, a function may be able to access the variables of the function(s) within which it is declared. In the static link, we hold the pointer value of the stack frame in which the current function was declared. 3) return address: point in the code to which we return at the end of execution of the current function. 4) values of arguments passed to the function and locals and temporaries used in the function

Here is what typically happens when we call a function Before a function call,the calling routine: 1)saves any necessary registers During a function call,the target 2)pushes the arguments onto the routine: stack for the target call 1)saves any necessary registers 3)set up the static link (if 2)sets up the new frame pointer appropriate) 3)makes space for any local 4)pushes the return address onto variables the stack 4)does its work 5)jumps to the target After a function call,the calling 5)tears down frame pointer and routine: static link 1)removes return address and 7)restores any saved registers parameters from the stack 8)jumps to saved return address 2)restores any saved registers 3)continues executing

Here is what typically happens when we call a function Before a function call, the calling routine: 1) saves any necessary registers 2) pushes the arguments onto the stack for the target call 3) set up the static link (if appropriate) 4) pushes the return address onto the stack 5) jumps to the target After a function call, the calling routine: 1) removes return address and parameters from the stack 2) restores any saved registers 3) continues executing During a function call, the target routine: 1) saves any necessary registers 2) sets up the new frame pointer 3) makes space for any local variables 4) does its work 5) tears down frame pointer and static link 7) restores any saved registers 8) jumps to saved return address

Parameter passing Pass by value:This is the mechanism supportedby C.Value of parameters are copied into called routine. Pass by reference:No copying is done,but a reference(usually implemented as a pointer)is given to the value.In addition to allowing the called routine to change the values,it is also efficient means for passing large variables(such as structs). Pass by value-result:This interesting variant supported by languages such as Ada copies the value of the parameter into the routine,and then copies the (potentially changed) value back out.This has an effect similar to pass-by-reference,but not exactly. Pass by name:This rather unusual mechanism acts somewhat like C preprocessor macros and was introduced in Algol.Rather than evaluating the parameter value, the name or expression is actually substituted into the calling sequence and each access to the parameter in the calling body re-evaulates it

Parameter passing Pass by value: This is the mechanism supported by C . Value of parameters are copied into called routine. Pass by reference: No copying is done, but a reference (usually implemented as a pointer) is given to the value. In addition to allowing the called routine to change the values, it is also efficient means for passing large variables (such as structs). Pass by value-result: This interesting variant supported by languages such as Ada copies the value of the parameter into the routine, and then copies the (potentially changed) value back out. This has an effect similar to pass-by-reference, but not exactly. Pass by name: This rather unusual mechanism acts somewhat like C preprocessor macros and was introduced in Algol. Rather than evaluating the parameter value, the name or expression is actually substituted into the calling sequence and each access to the parameter in the calling body re-evaulates it

Dynamic arrays A dynamic array is an array whose index bounds are not known until run-time.Dynamic arrays are found in Algol and Ada.In such languages,different dynamic arrays of the same type may have different index bounds,and therefore different numbers of elements. How then can we make dynamic arrays satisfy the constant-size requirement? We are forced to adopt an indirect representation,in which the dynamic array's handle (also called an array descriptor or array information vector)contains not only a pointer to the array's elements but also the array's index bounds.The handle has a constant size

Dynamic arrays A dynamic array is an array whose index bounds are not known until run-time. Dynamic arrays are found in Algol and Ada. In such languages, different dynamic arrays of the same type may have different index bounds, and therefore different numbers of elements. How then can we make dynamic arrays satisfy the constant-size requirement? We are forced to adopt an indirect representation, in which the dynamic array’s handle (also called an array descriptor or array information vector) contains not only a pointer to the array’s elements but also the array’s index bounds. The handle has a constant size

Run-time organization for object-oriented languages Object-oriented (OO)languages give rise to interesting and special problems in run-time organization.An object is a special kind of record.Attached to each object are some methods,each method being a kind of procedure or function that is able to operate on that object.Objects are grouped into classes, such that all objects of the same class have identical structure and identical methods

Run-time organization for object-oriented languages Object-oriented (OO) languages give rise to interesting and special problems in run-time organization. An object is a special kind of record. Attached to each object are some methods, each method being a kind of procedure or function that is able to operate on that object. Objects are grouped into classes, such that all objects of the same class have identical structure and identical methods