Skip to content

Run Time Data Structures & Storage Allocation

1. Introduction & The Storage Allocation Problem

When compiling or interpreting a program (such as in the Experimental Language ExpL), the compiler/interpreter must allocate memory for:

  1. Global variables
  2. Local variables and function parameters
  3. Control information (return addresses, old frame pointers)
  4. Intermediate expression temporaries
  5. Dynamic heap structures

A. Static Allocation (Global Variables & Functions)

  • Global Variables:

    • Requirements are known entirely during the analysis phase (compile time) because all global variables are explicitly declared with fixed sizes.

    • Memory addresses can be statically assigned during the analysis phase.

    • The assigned memory address is recorded in the binding field of the variable's entry in the Global Symbol Table (GST).

    • The code generator references this binding address whenever the variable is accessed in code.

  • Functions & Pseudo-Addresses:

    • During the analysis phase, the compiler cannot fix the physical memory address in the code area where a function's instructions will be loaded.

    • Solution: The compiler assigns a pseudo address (a symbolic label like F0, F1, etc.) to each function and stores it in the binding field of the function’s entry in the GST.

    • Calls to the function are emitted as assembly-level calls to this pseudo address.

    • These pseudo addresses are resolved to actual physical machine addresses later during the Label Translation phase.

B. Stack Allocation (Local Variables, Parameters & Activation Records)

  • The Local Variable Problem:

    • Local variables and function arguments cannot be assigned static memory addresses at compile time because:

      1. A function may be invoked multiple times (e.g., in recursion).
      2. Each active invocation requires its own distinct storage space for parameters and local variables.
      3. The total number of invocations is unknown at compile time (depends on user input at run time).

  • Illustrative Example: Factorial Function

    Code snippet

    decl
    int result, factorial(int n);
enddecl

int factorial(int n){
    decl
        int f;
    enddecl
    begin
        if( n==1 || n==0 ) then
            f = 1;
        else
            f = n * factorial(n-1);  /* Recursive call */
        endif;
        return f;
    end
}

int main(){
    decl
        int a;
    enddecl
    begin
        read(a);
        result = factorial(a);
        write(result);
        return 1;
    end
}
    • Analysis: If $n = 5$, factorial(5) calls factorial(4). The value $n = 5$ must be retained because execution resumes to calculate $5 \times \text{factorial}(4)$ after the recursive call returns. Statically allocating a single memory location to $n$ would overwrite $5$ with $4$, destroying the caller's state.

  • The Classical Solution: Run-Time Stack:

    • A Run-Time Stack dynamically grows and shrinks as functions are called and return.

    • Upon each function invocation, an Activation Record (Stack Frame) is created on the stack with space for:

      1. Function arguments.

      2. Return value.

      3. Return address (saved instruction pointer IP).

      4. Control pointers (saved Base Pointer BP).

      5. Local variables declared within the function scope.

    • When a function returns, its activation record is popped off the stack, and control returns to the activation record of the caller at the top of the stack.

  • Stack Discipline & Language Semantics:

    • ExpL semantics permit stack allocation because data stored in an activation record can be discarded once execution of the function call finishes (stack discipline).

    • Contrast: Languages supporting higher-order functions or closures (like LISP) cannot rely solely on stack-based allocation because local variables may need to outlive the function execution that created them.

    • Compile-time vs. Run-time: The size of an individual activation record is known at compile time, but the number of activation records allocated concurrently is known only at run time.

    C. Heap Allocation (Dynamic Allocation)

  • The Need for Dynamic Allocation:

    • ExpL supports dynamic memory allocation via alloc().

    • Static allocation is impossible because the exact size/number of requests is unknown at compile time.

    • Stack allocation is impossible because memory allocated by alloc() inside a function must persist after the function returns.

  • Solution: Maintain a contiguous block of memory called the Heap Memory.

    • Dynamic memory routines (alloc(), free(), Initialize()) manage memory blocks in the heap.

    • Common management algorithms: Fixed-Size Allocator or Buddy System Allocator.

D. Temporary Allocation (Machine Registers)

  • Intermediate evaluations (e.g., evaluating $(a + b) \times (c + d)$) require temporary memory for intermediate results.

  • Machine Registers ($R_0, R_1, \dots, R_{19}$) are used for temporary storage.

  • When a function calls another function, caller registers currently in use are saved to the stack (inside the caller's activation record) so the callee has free registers available. They are restored upon returning.

2. Summary of Memory Allocation Types

Allocation Type Purpose / Data Managed Memory Region Lifetime Fixed At
Static Allocation Global variables Static Data Area (Initial Stack/Data region) Entire program execution Compile Time
Stack Allocation Local variables, parameters, return value, return address, saved context Run-time Stack Duration of function invocation Frame size fixed at Compile Time; count determined at Run Time
Heap Allocation Dynamic objects created via alloc() Heap Region (Addresses 1024–2047) Explicit allocation until freed via free() Run Time
Temporary Allocation Intermediate expression results Machine Registers ($R_0 - R_{19}$) Single expression / instruction scope Run Time

3. The Memory Model (eXpOS Architecture / XSM Machine)

The application address space defined by the eXpOS ABI on the XSM machine architecture is partitioned as follows:

Memory Address Space Partitioning

Address Range Size Memory Region / Content Key Details
0 – 1023 1024 words Shared Library / OS Routines Pre-loaded routines (alloc(), free(), Initialize(), read(), write()) linked at runtime.
1024 – 2047 1024 words Heap Area Reserved exclusively for dynamic memory allocation managed by library functions.
2048 – 4095 2048 words Code Area Target machine instructions. Each XSM instruction takes 2 words $\implies$ Max 1024 machine instructions.
4096 – 5119 1024 words Static Data & Run-Time Stack Global variables stored at the beginning (4096+); Run-Time Stack starts above global variables and grows upwards. 
Address Space Layout (0 to 5119):
+------------------------------------+ 5119
|         Run-time Stack             | (Grows upwards)
|  . . . . . . . . . . . . . . . .   |
|         Global Static Data         | (Starts at address 4096)
+------------------------------------+ 4096
|             Code Area              | (Target Machine Code: Max 1024 instructions / 2048 words)
+------------------------------------+ 2048
|             Heap Area              | (Dynamic Memory: 1024 words, managed by OS Library)
+------------------------------------+ 1024
|           Shared Library           | (System routines & I/O wrappers: alloc, free, read, write)
+------------------------------------+ 0

Architectural & Implementation Rules:

  1. Instruction Limitation: Max target binary length is 1024 instructions (2048 words).

  2. Stack Initialization: eXpOS does not automatically initialize the Stack Pointer (SP) on program load. The compiled binary must include explicit setup instructions at entry to initialize SP to point above static global variables.

  3. Executable Header & Library Linking:

    • An XEXE executable starts with an 8-word header.

    • Setting the Library Flag bit in the header instructs the OS loader to link shared library routines (addresses 0–1023) upon loading.

    • High-level read(), write(), alloc(), free(), Initialize() constructs translate directly into calls to library entry points.

    • The compiler must never allocate static variables or stack frames inside the Heap area (1024–2047).

  4. Registers: XSM provides 20 general-purpose registers ($R_0 \dots R_{19}$) for temporary operations. All arithmetic/logical operations require operands to be loaded into registers first.

4. Sub-Section Implementation Details

A. Temporary Allocation (Register Allocation)

  • Managed via two compiler helper functions:

    • int get_register(): Allocates an unused register from $R_0 \dots R_{19}$ and returns its index. Returns -1 if no registers are available.

    • int free_register(): Releases the last allocated register back to the pool. Returns 0 on success, -1 on failure.

B. Static Allocation

  • Global variables declared in decl...enddecl are assigned sequential addresses starting at 4096.

  • Global Symbol Table Entry Structure:

    C

    struct Gsymbol {
    char *name;       // Variable / Function name
    int type;         // Data type (Integer, String, etc.)
    int size;         // Space required (for arrays)
    int binding;      // Static memory address or function pseudo-address
    struct Paramstruct *paramlist; // Function parameters
    struct Gsymbol *next;
};

C. Run-Time Stack Allocation & Calling Convention

When function $A$ calls function $B$:

Calling Steps (Caller - $A$):

  1. Save Context: Pushes active registers ($R_0 \dots R_k$) onto the stack.

  2. Push Arguments: Pushes parameters for $B$ in order of declaration.

  3. Push Return Slot: Pushes an empty word reserved for $B$'s return value.

  4. Invoke Callee: Executes CALL B (pushes return instruction pointer IP to stack and jumps to $B$).

Setup Steps (Callee - $B$):

  1. Save Old Frame Pointer: Pushes old Base Pointer (BP of $A$) onto the stack.

  2. Update Frame Pointer: Sets BP to point to the base of $B$'s new activation record (BP = SP).

  3. Allocate Locals: Advances SP to allocate space for $B$'s local variables in declaration order.

Return Steps (Callee - $B$):

  1. Writes result into the return value slot (BP - 2).

  2. Resets SP to deallocate local variables.

  3. Restores old BP from stack.

  4. Executes RET (pops return address into IP).

Resume Steps (Caller - $A$):

  1. Retrieves return value from stack slot.

  2. Pops arguments off stack.

  3. Restores saved registers ($R_k \dots R_0$).

Activation Record Layout on Stack

Stack Top (Higher Memory Address)
+-----------------------------------+ <-- SP (Stack Pointer)
| Local Variable 2                  | BP + 2
| Local Variable 1                  | BP + 1
+-----------------------------------+
| Saved Old Base Pointer (BP of A)  | <-- BP (Base Pointer)
+-----------------------------------+
| Saved Return Address (Saved IP)   | BP - 1
| Space for Return Value            | BP - 2
| Argument n                        | BP - 3
| ...                               |
| Argument 1                        | BP - (n + 2)
+-----------------------------------+
| Saved Caller Registers (R0, ...)  |
+-----------------------------------+ (Lower Memory Address)

D. Heap Allocation Algorithms

Managed in memory range 1024 to 2047:

  1. Fixed-Size Free List Allocator:

    • The initial index of each free block stores the address of the next free block (ending in -1).

    • Initialize(): Sets up the free list pointers across the heap space.

    • alloc(): Reads the head index $v$. If $v \neq -1$, allocates block at $v$ and updates head pointer to $v$'s next pointer.

    • free(s): Clears block $s$ and prepends $s$ to the front of the free list.

  2. Buddy System Allocator:

    • Block sizes are restricted to powers of two ($2^k$, ranging from $2^3 = 8$ to $1024$).

    • alloc(S): Calculates required size $2^k \ge S$. Finds a matching free block; if unavailable, recursively splits a higher-order free block into equal "buddy" halves until reaching size $2^k$.

    • free(p): Frees block $p$, checks if its buddy block is also free, merges them back into a single $2^{k+1}$ block, and repeats coalescing up the order hierarchy.