Run Time Environment Fig 7.1 07April08 and
Fig 7.14 examples 09April2008

14April09 Update
RTE1.html 09April08
RTE2.html 09April09
Examples of Spim code for Proc Calls 14Apr08, where SPIM procedure mechanisms are used, A.6 Proc Call Convention, p. A-22 to A-32
Access (dynamic) links for RTE 14Apr08
Ch 7 Procedure calls 16apr08

In Chapter 7, our text provides illustrations of the sorts of run-time environment that are used in translation. Following our text, we assume the run-time storage comes in blocks of contiguous bytes, where a byte is the smallest unit of addressable memory. A bytes is eight bits and four bytes forms a machine word.

Ch 6 presented storage for elementary data types such as character and integer. Our project has strings and integers.

Storage layout for data objects is strongly influenced by addressing constraints of the target machine - SPIM and its RISC assembly language. If we were writing a compiler to generate target code for a CISC IBM PC family, we would have different conversations.

7.1 Storage Organizaton

From compiler writer perspective, executing target program runs in its own logical address space in which each program values has a location. The management and organization of this logical address space is shared between the compiler, operating system and target machine. The OS maps the logical addresses into physical addresses, which are usually spread through the memory.

Fig. 7.1 is especially useful and is recreated here:

	|  Code          |   static target code
	|  Static        |   global variables
	|  Heap          |   dynamic storage - storage for data outlives the proc call
	|       |        |
	|       |        |
	|      \|/       |
	|   Free Memory  |      is filled by the Heap or the Stack growing 
	|      /|\       |
	|       |        |
	|       |        |
	|   Stack        |   Names local to a procedure and call/return info - data for proc call

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 at the low end of memory. Similarly, the size of some program data objects, such as global constants, may be known at compile time and can be placed in a statically determined area called Static.

7.1.1 Static Versus Dynamic Storage Allocation

The compiler must layout and allocatino data to memory locations in the run-time environent. Static info is known at compile time. Dynamic info is know at run time. We will look at the Activation Records (AR), we might construct to handle the translation of procedures (possibly nested and possible recursively called). The two techniques we focus on in this course are:

using a Display (7.3.8) to manage these AR's
using Static and Dynamic Links (7.3.5) to manage the AR's

7.2 Stack allocation of Space and 7.2.2 Activation Records

In the early days of computing, 1960's say, assembly language and FORTRAN were the main tools and they used static storage allocation. Space for data objects is allocated in a fixed locations for the lifetime of the program. Use of static allocation is only possible when the number and j size of all objects to be allocated is known at compilie time. Static allocation make storage allocation trivial, but it can also be quite wasteful of space. Therefore programmers would overlay variables, for example in FORTRAN the equivalence statement. This helped reduced storage needs, but also reduced the readability (understandability) of a program.

In modern languages, static allocation is used both for global variables that are fixed in size and accessible throughout the program execution and for program literals (constants) that needs to be fixed throughout execution.

Conceptually, we can bind static objects to absolute addresses. It is often preferable to address a static data object as a pair
(DataArea, Offset)

Offset is fixed at compile-time, but the address of DataArea can be deferred to link- or run-time.

Alternatively, the address of DataArea can be loaded into a register, which allows a static data item to be addresssed as

This addressing form is avaiable on almost every machine. The advantage of addressing a piece of static data this way is that we can defer deciding on where a static object will be loaded until just before execution begins.

Almost all modern programming language include recursive procedures, a feature that requires dynamic allocation. Each recursive call requires the allocation of a new copy of a procedure's local variables; thus the number of data objects required during program execution is not known at compile time.

procedure p (a: integer) is
   b: real;
   c: array (1..10) of real;
   b := c(a) * 2.51;

Activation Records for Subroutines

Figure 7.5 provides a General Activation Record
	| Actual parameters     |      often use registers for this, but show space to add to discussion
	| Returned values       |      space for returned values of a function
	| Control link          |      points to AR of caller
	| Access link           |      may be needed to locate data needed by called proc (say in another proc's AR)
	|  Saved machine status |      status of machine just before proc call
	|  Local Data           |      variable names declared in proc
	|  Temporaries          |      evaluation of expressions (not using registers)

Return to Run Time Environments