RESULT := (A + B) * ((C + D) / (E + F))
can be compiled into one-address instructions as shown in the figure.
Two temporary variables have to be allocated and these are re-used in the opposite order to that in which they were created. This corresponds to a last-in, first-out, or push-down stack arrangement, and where a multiplicity of base registers is provided, this stack is usually implemented by using one of the base registers as a stack pointer. Indeed, on the PDP-11, the auto-increment and auto-decrement addressing modes are specifically designed for this purpose.
An alternative arrangement is for the accumulator itself to be implicitly treated as the top-of-stack location, and for successive load orders to push previously loaded operands down into the stack automatically. Arithmetic orders then operate between the two most recently loaded operands, and leave their result on the stack, so that no address specification is required. These are therefore zero-address instructions, and systems which use this arrangement are frequently known as stacking machines.
Stacking machines offer particular advantages to compiler writers, since the algorithm for translating into Reverse Polish notation, and thence into stacking machine code, is very simple. The expression in the example above becomes, in Reverse Polish
A B + C D + E F + / * RESULT =>
Thus operands carry over into Reverse Polish without any relative change of position, and the rule for arithmetic operators is that the operator follows the two arithmetic values on which it is designated to work. Burroughs computers from the B5500 upwards are based on this system [1]. The push-down stack hardware consists of two or three registers at the top of the stack and a contiguous area of memory that permits the stack to extend beyond the registers.
Instructions in these machines are 12 bits long (packed four to a word), and fall into four categories: literal calls, operand calls and address calls (all of which involve pushing words into the stack), and operators. The operand calling mechanism is complex, since the actions which occur depend on the type of object found in store at the operand address (formed by treating part of the instruction or the top-of-stack word as an index, and adding it to the contents of a base register). The full word length is 51 bits, 48 bits of operand, instructions, etc, together with a 3-bit tag field which specifies the kind of information contained within the word. As examples, a word accessed by an operand call may be an operand (in which case it is simply stacked), a data descriptor (in which case the word addressed by the descriptor is stacked), or a program descriptor (in which case the program branches to a subroutine). Operators also use the tag field and treat words according to their tagged nature, so that there is only one ADD operator, for example, which takes any combination of single and double precision, integer or floating-point operands, and produces the appropriate result. Some operators require particular word types as operands, however, for which hardware checks are carried out, and an interrupt generated in case of error.
The designers of both the System/360 and the PDP-10 gave serious consideration to the use of a stacking machine, but both rejected it on a number of grounds. The IBM team argued that the performance advantage of a push-down stack derived principally from the presence of several fast registers, rather than the way in which they were used or specified. Furthermore, they claimed that the proportion of occasions on which the top-of-stack location contained the item actually needed next was only about one-half in general use, so that operations such as TOP (extract from within stack) and SWAP (exchange top two stack items) would be needed. As a result, the static code requirements would be comparable with that obtained from a system with a small set of addressable registers.
The DEC team were concerned about high cost and possible poor performance in executing the operating system, LISP and FORTRAN. Burroughs' commitment to the essentially Algol-orientated stacking architecture was largely an act of faith, based on a belief held in several quarters in the early 1960s, that FORTRAN would disappear. It did not, has not, and probably will not for many years to come. It has been a constant source of difficulty for computer designers, and on Burroughs' machines most FORTRAN programs execute more slowly than corresponding Algol-like programs.