Compiler Design Runtime Environment
Run Time Environment
- Run Time Environment establishes relationships between names and data objects.
- The allocation and de-allocation of data objects are managed by the Run Time Environment
- Each execution of a procedure is referred to as an activation of the procedure.
- If the procedure is recursive, several of its activations may & alive at the same time. Each call of a procedure leads to an activation that may manipulate data objects allocated for its use.
- The representation of a data object at run time is determined by its type.
- Elementary data types, such as characters, integers, and reals can be represented by equivalent data objects in the target machine.
- However, aggregates, such as arrays, strings , and structures, are usually represented by collections of primitive objects.
Run Time Environment
Source Language Issues
- Procedure
- Activation Trees
- Control Stack
- The Scope of a Declaration
- Bindings of Names
Procedure
- A procedure definition is a declaration that associates an identifier with a statement. The identifier is the procedure name and the statement is the procedure body.
- A procedure returns value for the called function.
- A complete program will also be treated as a procedure.
- When a procedure name appears within an executable statement, we say that the procedure is called at that point.
- The basic idea is that a procedure call executes the procedure body.
- Some of the identifiers appearing in a procedure definition are special, and are called formal parameters of the procedure.
- Actual parameters may be passed to a called procedure.
- Procedures can contains local and global variables .
Procedure
Activation Trees
- Each execution of procedure is referred to as an activation of the procedure.
- Lifetime of an activation is the sequence of steps present in the execution of the procedure.
- If ‘a’ and ‘b’ be two procedures then their activations will be non-overlapping (when one is called after other) or nested (nested procedures).
- A procedure is recursive if a new activation begins before an earlier activation of the same procedure has ended.
- An activation tree shows the way control enters and leaves activations.
Rules to Construct an Activation Tree
- Each node represents an activation of a procedure.
- The root node represents the activation of the main program.
- The node for a is the parent of the node for b if and only if control flows from activation a to b.
- 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.
Sample Code for Quick sort
main()
{
Int n;
readarray();
quicksort(1,n);
}
quicksort(int m, int n)
{
Int i= partition(m,n);
quicksort(m,i-1);
quicksort(i+1,n);
}
The activation tree for this program
Activation Tree
Stack Control
- We can use a stack , called a control stack to keep track of live procedure activations.
- The idea is to push the node for activation onto the control stack as the activation begins and to pop the node when the activation ends.
- Then the contents of the control stack are related to paths to the root of the activation tree.
- When node n is at the top of the control stack, the stack contains the nodes along the path from n to the root.
Example
- The activation tree that have been reached when control enters the activation represented by q(2,3 ) . Activations with labels r, p(1, 9), p(1, 3), and q(1, 3) have executed to completion, so the figure contains dashed lines to their nodes. The solid lines mark the path from q(2, 3) to the root.
Control stack contains nodes along a path to the root
Scope of Declaration
- A declaration in a language is a syntactic construct that associates information with a name. Declarations may be explicit, as in the Pascal fragment var i : integer; or they may be Implicit.
- For example, any variable name starting with I is assumed to denote an integer in a Fortran program, unless otherwise declared.
- The scope rules of a language determine which declaration of a name applies when the name appears in the text of a program.
- The portion of the program to which a declaration applies is called the scope of that declaration. An occurrence of a name in a procedure is said to be local to the procedure if it is in the scope of a declaration within the procedure; otherwise, the occurrence is said to be nonlocal.
- At compile time, the symbol table can be used to find the declaration that applies to an occurrence of a name.
- Special, static, global, volatile, final and so on are also used to declare variables.
Scope of Declaration
Binding of Names
- Even if each name is declared once in a program, the same name may denote different data objects at run time. The informal term "data object" corresponds to a storage location that can hold values.
- In programming language semantics, the term environment refers to a function that maps a name to a storage location, and the term state refers to a function that maps a storage location to the value held here
- Environments and states are different; an assignment changes the state, but not the environment. For example, suppose that storage address 100, associated with variable pi, holds 0. After the assignment pi := 3. 14, the same storage address is associated with pi, but the value held there is 3.14.
Binding of Names
Storage Organization
- The executing target program runs in its own logical address space in which each program value has a location. The management and organization of this logical address space is shared between the compiler, operating system, and target machine. The operating system maps the logical addresses into physical addresses, which are usually spread throughout memory.
- The run-time representation of an object program in the logical address space consists of data and program areas.
- The run time storage is subdivided to hold code and data as follows:
- The generated target code
- Data objects
- Control stack(which keeps track of information of procedure activations0)
- The size of the generated target code is fixed at compile time, so the compiler can place the executable target code in a statically determined area Code, usually in the low end of memory.
- The size of some program data objects, such as global constants, and data generated by the compiler, such as information to support garbage collection, may be known at compile time, and these data objects can be placed in another statically determined area called Static.
- One reason for statically allocating as many data objects as possible is that the addresses of these objects can be compiled into the target code.
- In early versions of Fortran, all data objects could be allocated statically.
Activation Records
Activation Records
- Procedure calls and returns are usually managed by a run-time stack called the control stack. Each live activation has an activation record (sometimes called a frame) on the control stack. The contents of activation records vary with the language being implemented.
- The following are the contents in an activation record
- Temporary values, such as those arising from the evaluation of expressions, in cases where those temporaries cannot be held in registers.
- Local data belonging to the procedure whose activation record this is.
- A saved machine status, with information about the state of the machine just before the call to the procedure. This information typically includes the return address and the contents of registers that were used by the calling procedure and that must be restored when the return occurs.
- An "access link" may be needed to locate data needed by the called procedure but found elsewhere, e.g., in another activation record.
- A control link, pointing to the activation record of the caller.
- Space for the return value of the called function, if any. Again, not all called procedures return a value, and if one does, we may prefer to place that value in a register for efficiency.
- The actual parameters used by the calling procedure. Commonly, these values are not placed in the activation record but rather in registers.