Previous: Concept of a Stack.
Up: The Stacksystem
Next: Implementation of the Stack System.
Previous Page: Concept of a Stack.
Next Page: Implementation of the Stack System.

Stack Overflow/Underflow.

A stack overflow occurs when the on--chip stack capacity is exceeded. This can be detected by a comparison of the top-pointer, the last-pointer and the index specified for a create-frame operation ( for push). Initially the top-pointer is set to 1 and the last-pointer to 0, placing a dummy element on the stack.

There are two invariants which hold due to the conventions made above:

and

The number of used cells is , so the number of free elements is . Therefore, a stack overflow occurs iff . There are different algorithms to handle this. The cut--back--k algorithm turned out to be very well suited during a lot of tests with different methods and was later found in [5]. It moves elements from the on--chip stack to the swap--area if a stack overflow occurs.

If an index specified for a read access is greater than the number of valid on--chip stack elements, a stack underflow occurs, i.e. iff .

The usage of the cut--back--k algorithm to handle stack spillings causes some problems with indexed read/writes. If the index specifies an element which is currently not available in the on--chip stack, a trap is generated. The trap handler must now resolve this situation. The index has to be in the range from 0 up to . To access an element which is located more than positions from the top, another instruction sequence must be used, which directly accesses the swap--area. Otherwise we have to distinguish two cases:

1. ,
2. : is in the critical region.

The first situation is easy to handle, because there is enough space on the on--chip stack to load the desired element by means of the cut--back--k algorithm. In the latter situation less than elements are free in the on--chip stack. Different solutions are possible, but hardware changes or modifications of the trap handler have severe drawbacks. The problem can completely be handled by a compiler: If an indexed access in the ``critical region'' must be generated, another code sequence should be issued. This involves an instruction, which ensures that the desired element is not located in the on--chip stack but in the swap area: simply a create-frame operation with . Thus, the appropriate memory location can be accessed without any further problem. Such an access is likely to happen so infrequently that it cannot be justified to add any hardware resources or to change the trap handler, which would slow down the normal execution.