党支部工作细则第一章.ppt

7. Runtime Environments,Zhang Zhizheng seu_,7. 0 Overview,1.Program vs program execution A program consists of several procedures (functions) An execution of a program is called as a process An execution of a program would cause the activation of the related procedures A name (e.g, a variable name)in a procedure would be related to different data objects,Notes: An activation may manipulate data objects allocated for its use.,2. Allocation and de-allocation of data objects Managed by the run-time support package Allocation of a data object is just to allocate storage space to the data object relating to the name in the procedure,Notes: The representation of a data object at run time is determined by its type.,3.Activation Trees A tree to depict the control flow enters and leaves activation of a procedure f(4) f(3) f(2) f(2) f(1) f(1) f(0) f(1) f(0),Enter f(4) Enter f(3) Enter f(2) Enter f(1) Leave f(1) Enter f(0) Leave f(0) Leave f(2) Enter f(1) Leave f(1) Leave f(3),Enter f(2) Enter f(1) Leave f(1) Enter f(0) Leave f(0) Leave f(2) Leave f(4),Each node represents an activation of a procedure The root represents the activation of the main program The node for a is the parent of the node for b if and only if the control flows from activation of a to b, and The node for a is to the left of the node for b if and only if the lifetime of a occurs before the lifetime of b.,So, the flow of control in a program corresponds to a depth-first traversal of the activation tree that starts at the root. Printing enter when the node for an activation is reached for the first time, and Printing leave after the entire subtree of the node has been visited during the traversal.,4.Control stacks A stack to keep track of live procedure activations: Push the node for an activation onto the control stack as the activation begins and to pop the node when the activation ends. Actually, PUSH=ENTER; POP=LEAVE,5.Bindings of Names When an environment associates storage location s with a name x, we say that x is bound to s; the association itself is referred to as a binding of x.,Notes: 1)Even each name is declared once in a program, the same name may denote different object at run time 2)The “ data object” corresponds to a storage location that can hold values,3)In programming language semantics, the term “environment” refers to a function that maps a name to a storage location, and term “state” refers to a function that maps a storage location to the value held there. environment state name storage value,4)Environments and states are different; an assignment changes the state, but not the environment 5)If x is not of a basic type, the storage s for x may be a collection of memory words 6)A binding is the dynamic counterpart of a declaration,6.Factors that determines the run time environment of a program Recursive definition Local name storage space allocation strategy global name storage space allocation strategy Parameter passing mechanism A function is whether allowed to be a parameter of or return value of a function,7. 1 Storage organization,1.Subdivision of Runtime Memory Typical subdivision of runtime memory into code and data areas,The generated target code; Data objects; A counterpart of the control stack to keep track of procedure activations,2.Activation Records/Frames 1) Definition A contiguous block of storage that stores information needed by a single execution of a procedure,2) A general activation record,Such as those values in the evaluation of expressions,Data that is local to the execution of a procedure,Information about the state of the machine just before the procedure is called,Refer to non-local data held in other activation records/fixed place,Point to the activation record of the caller,Used by the caller to supply parameters to the callee,The value that the callee return to caller,7. 2 Storage allocation strategies,1.Storage allocation strategies Static allocation Lays out storage for all data objects at compile time. Stack allocation Manages the run-time storage as a stack. Heap allocation Allocates and de-allocates storage as needed at run time from a heap.,2.Static allocation Names are bound to storage as the program is compiled, so there is no need for a run-time support package. Since the bindings do not change at run time, every time a procedure is activated, its names are bound to the same storage locations.,Some Limitations The size of a data object and constraints on its position in memory must be known at compile time. Recursive procedures are restricted, because all activations of a procedure use the same bindings for local name. Data structures cannot be created dynamically.,3.Heap allocation A separate area of run-time memory, called a heap. Heap allocation parcels out pieces of contiguous storage, as needed for activation records or other objects. Pieces may be de-allocated in any order.,Heap allocation is useful if either of the following is possible. The value of local names must be retained when an activation ends. A called activation outlives the caller.,4. Stack allocation 1)Main idea Based on the idea of a control stack; storage is organized as a stack, and activation records are pushed and popped as activations begin and end, respectively. Storage for the locals in each call of a procedure is contained in the activation record for that call. Locals are bound to fresh storage in each activation,Position in AT,AR on the stack,Remark,s,S a: array,S a: array,r i: integer,s,r,s,r,q(1, 9),S a: array,q(1 9) i: integer,s,r,q(1, 9),S a: array,q(1 9) i: integer,q(1 3) i: integer,p(1, 9),q(1, 3),p(1, 3),q(1, 0),2)Calling sequences A call sequence allocates an activation record and enters information into its fields A return sequence restores the state of the machine so the calling procedure can continue execution.,Parameters & returned value,Control link links and saved status,Temporaries and local data,Parameters & returned value,Control link links and saved status,Temporaries and local data,Top-sp,Callers Responsibility,Callees Responsibility,Callers activation record,Callees activation record,Division of tasks between caller and callee,The register top-sp points to the end of the machine status field,Steps: (1)The caller evaluates actual parameters. (2)The caller stores a return address and the old value of top-sp into the callees activation record. (3)The callee saves register values and other status information (4)the callee initializes its local data and begins execution.,A possible return sequence : (1)The callee places a return value next to the activation record of the caller (2)Using the information in the status field, the callee restores top-sp and other registers and branches to a return address in the callers code. (3)Although top-sp has been decremented, the caller can copy the returned value into its own activation record and use it to evaluate an expression.,ACCESS TO NONLOCAL NAMES,P411-415 Algol(Alan J.Perlis),3)Stack allocation for non-nested procedure -for C,In C, a procedure definition cannot appear within another. If there is a nonlocal reference to a name a in some function, then a must be declared outside any function.,Stack allocation for C When entering a procedure, the activation record of the procedure is set up on the top of the stack Initially, put the global(static) variables and the activation record of the Main function,e.g. the calling sequence is like the following: main () q( ); p( ) q( ) p( ); ,Main AR,Q AR,P AR,TOP,SP,global Var,#include int x,y; int main() x=5; y=f(x); ,int f(int n) if (n=1) return 1; else int t1,t2,t; t1=f(n-1); t2=f(n-2); t=t1+t2; return t , Activation Record of the function called by Main function Activation Record of Main function Global Variable Data Area,Storage Organization of C Language,The Form of Activation Record of any a function in C,Unit for Returned Value of function Internal Temporary Work Units Local Variable Data Storage Units Formal parameter Storage Units Number of Formal Parameters Returned Address Callers SP (Start Address of callers activation record),TOP,SP,1) Here we assume that the callers sp of Main function is the start address of global variable data area, and the returned address in the activation record of a function (including Main function) is filled by the operating system automatically, you might not care it. 2) The start address of stack used in the program is K.,How about the stack map of the above c program?,4)Stack allocation for nested procedures (1) the nesting of procedure definitions in the Pascal program,(2) nesting depth,i1,P0,Pi-1,Pi,i,0,(3) access links,P0,P1,P2,Call P2,Call P1,TOP,Top-SP,P2,P1,P0,Access link,Access link,Access link,TOP,Top-SP,P2,P1,P0,Access link,Access link,Access link,(4) displays Faster access to global than with access links can be obtained using an array d of pointers to activation records, called a display.,Access non-local name by display. Suppose control is in an activation of a procedure p at nesting depth j. Then, the first j-1 elements of the display point to the most recent activations of the procedure that lexically enclose procedure p, and dj points to the activation of p.,When a new activation record for a procedure at nesting depth i is setup, we A) save the value of di in the new activation record; B) set di to point to the new activation record.,Example: Program M; var A,B:integer function F(N:integer):integer; if N=2 then return(N) else return (N*F(N-1); begin read(A); /*Let A=5*/ B:=F(A); write (B); end. Please write down the display of the above program,M,F(5) Saved d1,F(4) Saved d1,F(3) Saved d1,F(2) Saved d1,d1,d2,7. 3 Parameter passing,1.Parameter-passing methods Call-by-value Call-by-reference Copy-restore Call-by-name,2.Call-by-value 1) in C and Pascal 2)implementation A formal parameter is treated just like a local name, so the storage for the formals is in the activation record of the called procedure. The caller evaluates the actual parameters and places their r-values in the storage for the formals.,3.Call-by-Reference 1) also known as call-by-address or call-by-location. 2)implementation If an actual parameter is a name or an expression having an l-value, then that l-value itself is passed. If the actual parameter is an expression that has no l-value, then the expression is evaluated in a new location, and the address of that location is passed.,4.Copy-Restore 1)a hybrid between call-by-value and call-by-reference is copy-restore linkage. 2)implementation Before control flows to the called procedure, the actual parameters are evaluated.(copy-in) When control returns,the current r-value of the formal parameters are copied back into the l-values of the actuals, using the l-values computed before the call(copy-out) Notes: Only actuals having l-values are copied.,5.Call-by-Name Traditionally defined by the copy-rule of Algol It is just as macro-expansion or in-line expansion,7. 4 Symbol Tables,1.Functions of symbol tables Keep track of scope and binding information about names Allow us to add new entries and find existing entries efficiently,Notes: 1)Changes to the table occur if a new name or new information about an existing name is discovered 2)The table may be a linear list or a hash table 3)It is useful for a compiler to be able to grow the symbol table dynamically, if necessary, at compile time,2.Symbol-table entries Each entry in the symbol table is for the declaration of a name Each entry can be implemented as a record consisting of a sequence of consecutive words of memory,Notes: 1)Inform