1.

Introduction

Information about the way computers are actually

used is of great importance to computer architects,
p r o g r a m m i n g language designers, and compiler
writers. Whether or not a certain semantic primitive
Computer G. Bell, S. H. Fuller, and should be included in a machine's instruction set, made
Systems D. Siewiorek, Editors a language construct, or carefully optimized depends
primarily upon its projected frequency of usage. This
Implications of information can only be obtained empirically, since
there is no way to predict a priori, whether, for
Structured example, R E P E A T . . . U N T I L statements are more
useful than C A S E statements.
Programming for The ways in which certain programming languages
are used has already been studied: Knuth [6] has
Machine Architecture examined Fortran; Salvadori, G o r d o n , and Capstick
[9] have examined Cobol; Alexander and W o r t m a n
Andrew S. Tanenbaum [1] have examined X P L ; W o r t m a n [15] has examined
Vrije Universiteit, The Netherlands student PL.
In recent years unstructured programs have fallen
into disrepute. A growing n u m b e r of people have
Based on an empirical study of more than 10,000 come to recognize the importance of structuring pro-
lines of program text written in a GOTO-less grams so that they can be easily understood. Although
language, a machine architecture specifically designed there is no generally accepted definition of structured
for structured programs is proposed. Since p r o g r a m m i n g yet (see [2] for discussion), most pro-
assignment, CALL, RETURN, and IF statements g r a m m e r s intuitively realize that breaking programs
together account for 93 percent of all executable up into small, easily understood procedures, and drast-
statements, special care is given to ensure that these ically reducing or even eliminating G O T O statements
statements can be implemented efficiently. A highly greatly improves readability. We are even beginning
compact instruction encoding scheme is presented, to see the development of new programming languages
which can reduce program size by a factor of 3. Unlike which have been intentionally designed without a
a Huffman code, which utilizes variable length fields, G O T O statement [16].
In order to determine what characteristics struc-
this method uses only fixed length (1-byte) opcode
tured programs have, it is necessary to collect and
and address fields. The most frequent instructions
consist of a single 1-byte field. As a consequence, dissect a n u m b e r of them. These data can then be used
as a basis for designing computer architectures that
instruction decoding time is minimized, and the
machine is efficient with respect to both space and can execute structured programs efficiently. The next
section of this article describes a G O T O - l e s s language
time.
Key Words and Phrases: machine architecture, we have developed to encourage good p r o g r a m m i n g
style. The third and fourth section contain an analysis
computer architecture, computer organization,
instruction set design, program characteristics of a collection of procedures written in this language.
The fifth and sixth sections propose and discuss a
CR Categories: 4.12, 4.22, 4.9, 6.21
machine architecture based upon our findings.

2. The Experiment

We have developed a typeless G O T O - l e s s language

(SAL) specifically intended for system p r o g r a m m i n g
[10]. It has been i m p l e m e n t e d [11] on a PDP-11/45,
General permission to make fair use in teaching or research of
all or part of this material is granted to individual readers and to and used, a m o n g other things, to construct a general
nonprofit libraries acting for them provided that ACM's copyright purpose time sharing system for that computer. The
notice is given and that reference is made to the publication, to its language resembles BcPI~ [8]; its control structures are
date of issue, and to the fact that reprinting privileges were granted
by permission of the Association for Computing Machinery. To similar to those of Pascal [5]. A s u m m a r y of the
otherwise reprint a figure, table, other substantial excerpt, or the executable statements follows.
entire work requires specific permission as does republication, or
systematic or multiple reproduction. Assignment
Author's address: Computer Science Group, Vrije Universteit, Am- CALL
sterdam, The Netherlands. I F . . . T H E N . . .ELSE . . .FI
© 1978 ACM 0001-0782/78/0300-0237 $00.75 RETURN

237 Communications March 1978

of Volume 21
the ACM Number 3
F O R . . . F R O M . . . T O . . . B Y . . . D O . ..OD grammers to produce short, well structured proce-
WHILE...DO...OD dures. (The mean number of executable statements
REPEAT... UNTIL . . . LITNU
per procedure turned out to be 18.2). The combination
DO FOREVER . . . OD
EXITLOOP
of the GOTO-less language, the quality of the pro-
CASE...IN...,..., . . . ,OUT...ESAC grammers, an environment with a long Algol tradition
PRINT and no Fortran tradition, and our deliberate efforts to
produce intelligible programs has resulted in what we
Expressions are evaluated strictly left to right, with
believe to be state-of-the-art structured programs.
no precedence or parentheses. E L S E parts in IF state-
ments are optional. R E T U R N statements exit the
current procedure, and optionally return a value, so
that a procedure may be used as a function. Procedures 3. Characteristics of the Programs
not returning an explicit value may terminate by "fall-
ing through", i.e. the END statement implies RE- For this study we have used a specially instrumented
TURN. compiler to collect information on more than 300
The W H I L E statement tests at the top of the loop, procedures used in various system programs. Most of
whereas the R E P E A T statement tests at the end of these were related to the time sharing system project.
the loop. D O F O R E V E R statements are the same as The results presented should be interpreted keeping in
W H I L E T R U E D O ; they are useful in operating mind that operating system modules may systematically
system modules that endlessly get and carry out service differ from say, applications programs, in certain ways,
requests, the "get" primitive blocking the process in e.g. they have little i/o.
the absence of a message. E X I T L O O P is a forward Where relevant, both static and dynamic measure-
jump out of one level of enclosing loop of any kind ments are given. Static measurements were obtained
( F O R , W H I L E , R E P E A T , or D O F O R E V E R ) . Our by having the compiler count the number of occur-
experience indicates that this, plus R E T U R N , is suffi- rences of the item in the source text. Dynamic meas-
cient most of the time. The CASE statement contains urements were obtained by having the compiler insert
an integer expression that selects one of the clauses to code into the object program to increment counters
be executed, or the O U T clause if the integer is out of during program execution. The results are given in
range (as in Algol 68 [12]). There is no G O T O Tables I-VIII.
statement.
In addition to the above statements, there are a
variety of declarations, debugging facilities and com- 4. Discussion of the Results
piler directives.
The basic data types are machine words (including According to our data, a typical procedure consists
the general registers and the i/o device registers, acces- of 8 or 9 assignment statements, 4 calls to other
sible as the top 4K memory words), one-dimensional procedures, 3 IF statements, 1 loop, and 1 escape
arrays of words and characters, bit fields, and program- ( R E T U R N or E X I T L O O P ) . Two of the assignment
mer defined data structures consisting of a collection statements simply assign a constant to a scalar variable,
of named fields, each field being a word, character, bit one assigns one scalar variable to another, and 3 or 4
field, or array. There are two scope levels, local (stack more involve only one operand on the right hand size.
storage, reserved upon procedure entry, and released The entire procedure probably contains only 2 arith-
upon procedure exit), and global (static storage). A metic operators. Two of the three conditions in the IF
program consists of one or more procedures, and zero statements involve only a single relational operator,
or more modules that declare and initialize external probably -- or :P.
variables. The general conclusion that can be drawn from this
The programs examined for this research were all data is the same as Knuth drew from his Fortran
written by the faculty and graduate students of the study: programs tend to be very simple. Combining
Computer Science G r o u p at the Vrije Universiteit. All this conclusion with the Bauer principle (If you do not
the programmers involved made a very deliberate use a feature, you should not have to pay for it), we
effort to produce "clean," well structured programs, suggest that most present day machine architectures
knowing full well that succeeding generations of stu- could be considerably improved by catering more to
dents would pore over their code line by line. This is the commonly occurring special cases. This will be
clearly a different situation than one finds in the discussed in detail in the next section. First we have a
average, garden variety, computer center. few more comments about the measurements.
The amount of m e m o r y available on our PDP-11/ In some cases there are significant differences be-
45 was so small that the initial compiler could not tween the static and dynamic measurements. Some of
handle procedures much larger than two pages of these differences are genuine, e.g. the operating system
source code. This defect was remedied by. declaring it is constantly looking for internal inconsistencies in its
to be a virtue, and by continually exhorting the pro- tables. If an error is detected, an error handling
238 Communications March 1978
of Volume 21
the ACM Number 3
Table I. Percent Distribution of Executable Statements. Table V. Percent Distribution of Relational Operators.

Statement Type Static Dynamic Operator Static Dynamic

Assignment 46.5 41.9 = 48.3 50.6
CALL 24.6 12.4 4: 22.1 18.6
IF 17.2 36.0 > 11.8 10.2
RETURN 4.2 2.6 < 9.5 9.0
FOR 3.4 2.1 -> 4.5 8.4
EXITLOOP 1.4 1.6 < 3.8 3.3
WHILE 1.1 1.5
REPEAT 0.5 0.1
DO FOREVER 0.5 0.8 Table VI. Percent of all Procedures with N Formal Parameters.
CASE 0.3 1.2
PRINT 0.3 <0.05 N Static Dynamic
0 41.0 21.2
Table II. Percent Distribution of Assignment Statement Types. 1 19.0 27.6
2 15.0 23.3
Type Static Dynamic 3 9.3 10.8
variable = constant 21.7 19.2 4 7.3 8.8
variable =variable 9.5 9.1 5 5.3 6.6
variable=function call 4.4 1.9 6 2.3 0.6
variable=array element 4.3 3.3 7 0.3 0.2
array element=constant 4.1 2.8 8 0.3 <0.05
array element=variable 4.1 2.9 ->9 <0.05 1.0
array element=array element 0.9 1.8
array element=function call 0.5 0.1
Table VII. Percent of all Procedures with N Local Scalar Variables.
other forms with 1 rhs term 30.5 25.2
forms with 2 rhs terms 15.2 20.4 N Static Dynamic
forms with 3 rhs terms 3.0 6.9
forms with 4 rhs terms 1.5 5.9 0 21.5 30.7
forms with ->5 rhs terms 0.3 0.3 1 17.2 26.5
2 19.8 15.4
3 13.5 4.2
Table III. Percent Distribution of Operand Types
4 8.3 4.9
Type Static Dynamic 5 5.3 10.0
6 4.6 1.6
constant 40.0 32.8 7 3.6 1.0
simple variable 35.6 41.9 8 1.3 1.6
array element 9.3 9.2 9 1.0 0.8
field of structure 7.1 11.1 10 0.7 <0.05
function call 4.8 1.6 ->11 3.3 3.0
bit field 3.2 3.3

Table IV. Percent Distribution of Arithmetic Operators. Table VIII. Percent Distribution of Number of Statements in
"THEN" Part of IF Statements.
Operator Static Dynamic
Statements Static
+ 50.0 57.4
- 28.3 25.5 1 47.4
x 14.6 13.2 2 20.5
/ 7.0 3.8 3 9.9
4 5.8
p r o c e d u r e is called. D u r i n g n o r m a l o p e r a t i o n t h e r e 5 2.3
6 3.4
a r e no i n c o n s i s t e n c i e s , so t h e s e e r r o r h a n d l e r s are n o t
7 1.2
called. T h e s e C A L L s t a t e m e n t s i n c r e a s e the static 8 1.1
n u m b e r of C A L L ' s but not the dynamic number. 9 2.0
F u r t h e r m o r e , an I F s t a t e m e n t c o n t a i n i n g a single -->10 6.1
C A L L s t a t e m e n t in its T H E N part and a single C A L L
s t a t e m e n t in its E L S E p a r t will be c o u n t e d as o n e I F m u c h s m a l l e r s a m p l e t h a n the m o r e t h a n 1 0 , 0 0 0 lines
a n d t wo C A L L ' s in t h e static statistics, b u t o n e I F an d o f s o u r c e text used to d e r i v e the static statistics. F o r
o n e C A L L in t h e d y n a m i c statistics, since only o n e this r e a s o n the static statistics are p r o b a b l y m o r e
b r a n c h is actually t a k e n p e r e x e c u t i o n . This effect m e a n i n g f u l . In t h e r e m a i n d e r o f this p a p e r w e will use
i n c r e a s e s t h e p r o p o r t i o n o f I F s t a t e m e n t s r e l a t i v e to t h e static statistics.
o t h e r s t a t e m e n t s in th e d y n a m i c statistics. F r o m t h e fact t h a t 5.5 p e r c e n t of t h e s t a t e m e n t s
O n t h e o t h e r h a n d , a single l o o p e x e c u t e d 1 0 , 0 0 0 are l o o p s , and 1.4 p e r c e n t are E X I T L O O P ' s , we
t i m e s gives grossly d i s p r o p o r t i o n a t e w e i g h t to t h e state- e s t i m a t e that at least 25 p e r c e n t o f the l o o p s are
m e n t s in t h e l o o p in (only) the d y n a m i c statistics. T h u s " a b n o r m a l l y " t e r m i n a t e d . (In a d d i t i o n , an u n k n o w n
the d y n a m i c statistics m a y in fact be b a s e d o n a v e r y n u m b e r o f l o o p s ar e t e r m i n a t e d by R E T U R N ) . T h e
239 Communications March 1978
of Volume 21
the ACM Number 3
Table IX. Comparison of Static Executable Statement Distribution Our data gives an average of 0.45 arithmetic oper-
(percent). ators per expression, which agrees well with Alex-
Statement type SAL XPL Fortran ander's and W o r t m a n ' s figure of 0.41. Likewise, our
Assignment 47 55 51 measurement of 1.22 operators per conditional expres-
CALL 25 17 5 sion agrees with their value of 1.19 logical plus rela-
IF 17 17 10 tional operators. Such good agreement enhances one's
Loops 6 5 9 confidence in the universality of the results.
RETURN 4 4 4
GOTO 0 1 9

Table X. Summary of EM-1 Instructions and Number of Opcodes 5. A Proposal for a Machine Architecture
Allocated to Each.
Instruction description Format 1 2 3A Most present day computers have an architecture
designed in the early 1960's. They have remained
push constant onto stack 3 2
push local onto stack 12 1 substantially unchanged for a decade in the name of
push external onto stack 8 1 compatibility in spite of their obstacles to generating
pop local from stack 12 1 efficient code from high level languages. A machine
pop external from stack 8 1 architecture based on the characteristics of the pro-
zero address ADD, SUB, MUL, DIV 4 grams described in the previous sections is sketched
increment local 12 1
zero local 12 1 below. The architecture is specifically intended for
increment top word on stack 1 block structured languages that permit recursion, i.e.
push array element onto stack 2 Algol-like languages.
pop array element from stack 2 Our architecture has two explicit goals: 1. minimiz-
call 1 ing program size, and 2. providing a target language to
load address 1
load indirect 1 which compilation is straightforward. We choose to
mark 3 1 minimize program size rather than maximize execution
advance stack pointer 1 speed for several reasons. First, execution speed de-
return 1 pends not only on the raw clock rate, but also on the
for instruction characteristics of the underlying microinstruction set.
branch forward unconditionally 34 1
branch backward unconditionally 1 Given a high level language benchmark program and
branch if operand 1=operand 2 12 1 two proposed instruction sets, it is possible to deter-
branch if operand 1:~operand 2 20 1 mine unambiguously which object program is smaller,
branch if operand 1-<operand 2 8 1 but not which is faster. (By hypothesizing a faster clock
branch if operand 1->operand 2 8 1
or better microarchitecture either machine can be
branch if operand 1< operand 2 4 1
branch if operand l>operand 2 4 1 speeded up). In other words, minimizing size is a more
branch if operand = 0 12 1 clearly defined goal than maximizing speed.
branch if operandi0 20 1 Second, size and speed are highly intertwined. All
branch if operand~ 0 8 1 other factors being equal, a shorter program will exe-
branch if operandi-0 8 1 cute faster than a longer one since fewer bits need be
branch if operand< 0 4 1
branch if operand> 0 4 1 processed. If the m e m o r y bandwidth is N bits/see and
opcode 255 (i.e. use formats 3B, 4) 1 the mean instruction size is L bits, the maximum
instruction execution rate will be N/L instructions/see.
The smaller L is, the faster the machine can be.
discussion currently raging in the literature [7] about Furthermore, on a machine with virtual m e m o r y , re-
how premature loop termination should be incorpo- ducing program size reduces the number of page faults,
rated into language syntax is not irrelevant. which, in turn, reduces the time required to process
Since measurements of the type presented in this the page faults, thereby speeding up execution.
paper are obviously very sensitive to idiosyncracies of Third, on large computers with sophisticated multi-
one's programming style, it is interesting to compare programming systems, a decrease in program size
our results to previously published work. Table IX means an increase in the degree of multiprogramming,
compares executable statement distribution for 3 stud- hence a higher C P U utilization, as well as less swap-
ies cited in Section 1. One difference between Fortran ping.
and the other languages stands out immediately: For- Fourth, the small amount of m e m o r y available on
tran programs have relatively few procedure calls. This minicomputers is often a serious limitation. Making
suggests that they are not well modularized. From the program fit into the memory may take precedence
Knuth's data (his Table I) we compute that the average over all other considerations.
Fortran subroutine has 86.3 executable statements, vs. Fifth, on mini and micro computer systems, the
28.6 for X P L and 18.2 for SAL, which agrees with cost of m e m o r y frequently is much larger than the
this hypothesis. C P U cost. Reducing m e m o r y requirements has a much
240 Communications March 1978
of Volume 21
the ACM Number 3
greater effect on total system cost than reducing exe- Fig. I.
cution time. sP__~
The fact that few compilers for third generation
computers can produce code that even comes close to elements of n 6

what a skilled assembly language programmer can

generate argues strongly for redesigning machine archi-
tectures so that compilers can do their job better. (See
e l e m e n t s of n 5
[11] for some statistics). It is for this reason that we
consider a stack machine, since generating efficient
reverse Polish is simpler than generating efficient code descriptor f o r n6
for a register oriented machine. We assume the pres- descriptor for n5
ence of a cache to eliminate the need for memory
cycles when referencing the stack. n4 current
stack
The design described below is intended for imple- n3 frame

menting modern programming languages such as Algol

n2
60, Algol 68, Pascal, XPL, BCPL, SAL, and others of
this genre, since they tend to facilitate rather than nl
hinder the writing of well structured programs.
actual parameter 2
The proposed machine, which we shall call EM-1
(Experimental Machine-l) has a paged, segmented actual parameter 1

virtual memory. The program and data reside in differ- LB---~

ent address spaces (like the PDP-11/45), so that in- administration
information
struction space segment 0 is distinct from data segment f o r call to p 2

0. An instruction space segment is a sequence of 8-bit

bytes, each with a unique address. A data space k2

segment is a sequence of words of N bits each (N is kl

left unspecified here). The word length for data space previous
stack
segments may be different from that of instruction administration
frame
space segments. (See Table X.) information
f o r cell to p 1
One data space segment is special: the stack. The
stack has associated with it a stack pointer register
(SP) that points to the top word on it. Whenever a
elements of e 4
procedure is entered, a new frame is allocated on the
stack for the administration, actual parameters, and
locals. The frame is released upon procedure exit. descriptor for e4 external
variables
Figure 1 depicts the stack for the following Algol 60 and a r r a y s
e3
program.
e2

begin integer e 1, e 2, e 3; integer array e 4 [ 1: 3];

el
proc p 1 ; O ~
begin integer k l , k2; p 2 ( k l , k2)
end; to the beginning of the local variables. Local variables
proc p 2(formall, formal2); are specified by giving their positions relative to LB.
begin integer k 1, k2;p2(kl, k2) The administration area contains the calling proce-
integer array n 5 [1:4], n 6 [0:1 ];
comment snapshot of Figure 1 taken here; dure's return address, the previous value of LB, and
end; other (language dependent) information. It is assumed
pl that the microprogram knows the size and organization
end of the administration area; a special instruction could
be executed at the beginning of each program to tell
When p 2 returns, SP will be reset to point to k2, thus it. Actual parameters can be addressed by giving their
removing that part of the stack marked "current stack distance from LB, just as locals. Note that the admin-
frame" in Figure 1. istration area is not counted in order to reduce the size
The stack frame for a procedure consists of 4 areas: of the constants needed.
(1) the administration information; (2) the actual pa- A procedure call takes place in the following steps:
rameters; (3) the local scalar variables and array de-
scriptors; and (4) the elements of local arrays. The 1. A M A R K instruction is executed to deposit the
sizes of areas (1-3) are always known at compile time; static and dynamic links on the stack. The M A R K
the size of area (4) may not be known until run time. instruction has one operand which tells how much
A special hardware register, LB (Local Base) points the static depth of nesting is increased or decreased.
241 Communications March 1978
of Volume 21
the ACM Number 3
 This is needed to update the static chain. The register optimization needed. High execution speed
M A R K instruction also reserves space for the re- can be attained by a hardware cache memory that
turn address to be deposited subsequently. retains the most recently referenced words (i.e. the
2. The calling procedure pushes the actual parameters top of the stack) in high speed storage, or by having
onto the stack. the microprogram keep them in its scratchpad memory.
3. A call instruction is executed, transferring control If the arithmetic expressions evaluated are simple,
to the called procedure. The call instruction has as little cache or scratchpad storage will be needed. Our
operand the index of a procedure descriptor, dis- data indicate that 80 percent of all expressions consist
cussed later. This instruction must deposit the re- of a single term, 95 percent consists of 1 or 2 terms
turn address in the place reserved for it by the and 99.7 percent consists of 4 or fewer terms, meaning
M A R K instruction, update LB and transfer control. that rarely will more than 4 operands be on the stack
4. The called procedure executes a single instruction simultaneously.
that increments SP to reserve as much local storage Most of the instructions require an opcode and a
as is initially needed; this instruction could also small constant, which we call the "offset." The offset
initialize the local variables to 0 or a special "unde- is generally used to select one of the local variables,
fined" value such as 1000 . . . 000 (two's comple- one of the external variables, the number of bytes to
ment - 0 ) . If more local storage is needed during skip (branch instructions), etc. The following five in-
execution of the procedure, e.g. for an Algol 68 struction formats are used by EM-1.
local generator, SP can simply be advanced again.
Format Bytes Description
We propose an addressing mechanism with distinct 1 1 byte 1 = opcode + offset (arithmetic sum)
instructions for the 2 most important cases: local and 2 2 byte 1 = opcode, byte 2 = offset
3A 3 byte 1 = opcode, bytes 2,3 = offset
external variables. Each instruction must provide an 3B 3 byte 1 = 255, byte 2 = opcode, byte 3 = offset
integer offset telling which variable is intended. Locals 4 4 byte 1 = 255, byte 2 = opcode, bytes 3,4 = offset
are offset above LB, and externals are offset from
address 0 of the stack segment. For the purposes of The choice of machine instructions, and their as-
addressing, procedure parameters are the same as signment to formats, should be carefully arranged to
locals. minimize program size (based on the data of Section
Two other addressing forms are needed but are 3). In particular, an effort should be made to insure
much less important. One is for full virtual addresses that the most common statements can be translated
consisting of a segment and word within the segment. into 1 byte instructions most of the time. The scheme
The other is for accessing intermediate lexicographical described below is constrained by the fact that the
levels in block structured languages by means of a total number of format 1 instructions plus format 2
(relative lexicographical level, offset) pair. Rather than instructions plus format 3A instructions must not ex-
using a display, which must be frequently u p d a t e d at ceed 255. Some instructions, may occur several times
considerable cost, we propose that at some position in the order code, e.g. push constant onto the stack
within the administration area known to the micropro- occurs in formats 1, 2, and 4, with a different range of
gram is the LB value of the most recent incarnation of constants provided in each form.
the procedure in which the current procedure is nested The idea of using shorter bit patterns for common
(i.e. the static link). Given a (relative lexicographical instructions and longer bit patterns for infrequent
level, offset) pair, the microprogram can follow the instructions is not new. Huffman [4] gives a method
chain and locate variables at any outer static level. for encoding items whose probabilities of occurrence
Note that the penalty for accessing intermediate levels are known, in the minimum number of bits. An ap-
is only a few microinstructions and one m e m o r y refer- proximation of this technique has been used in the
ence for each level of nesting followed. The combina- design of the Burroughs B1700 S-machines (Wilner,
tion of infrequent usage and a small penalty per use [13, 14]). In the SDL S-machine, opcodes can be 4, 6,
makes this method attractive since it reduces procedure or 10 bits, and addresses 8, 11, 13, or 16 bits. A
call overhead, which is far more crucial. single address instruction can have a length of 12, 14,
The stack is also used for all arithmetic and logical 15, 17, 18, 19, 20, 21, 22, 23, or 26 bits. Since the
operations, shifting, etc. An assignment is performed B1700 microarchitecture is extremely flexible (among
by first pushing the value to be assigned onto the stack other things being able to read an arbitrary length bit
(or perhaps its descriptor, if provision is made for s t r i n g - u p to 24 b i t s - o u t of memory beginning at an
assigning entire arrays in one instruction), and then arbitrary bit, in a single microinstruction) the use of
popping it to its destination, a total of 2 instructions. peculiar length instructions does not slow down inter-
The statement A = B x C is handled by 4 instructions: pretation.
P U S H B; P U S H C; M U L T I P L Y ; POP A . Howeyer, nearly all other computers are based
The advantage of a stack type architecture for upon a memory organization using fixed length words.
arithmetic is clear: compilers can translate expressions For a microprogram with internal registers, bus widths
to reverse Polish very simply, with no complicated etc. of 8, 16, or 32 bits interpreting a " m a c h i n e "
242 Communications March 1978
of Volume 21
the ACM Number 3
language whose instructions came in units of 12, 14, where the strides can be computed once and for all as
15, 17, 18, 19, 20, 21, 22, 23, or 26 bits would be soon as the bounds are known, at compile time in
unbearably slow, since nearly every instruction would many cases, and at run time in the others. The descrip-
straddle word or byte boundaries, necessitating time tor must also contain the number of dimensions and
consuming shifting and masking operations to extract the element size (and the segment number, for nonlocal
the opcode and address fields. The scheme described arrays).
by Wilner is only feasible if every single bit in memory Array elements are accessed as follows. First the
has a unique address, a situation which is rarely the subscripts are stacked, requiring at least one instruction
case. per subscript. Then a P U S H E L E M E N T instruction is
The instruction set of EM-1, in contrast, also pro- executed, specifying the offset of the descriptor from
vides a very efficient method for encoding instructions, LB. This instruction removes all the subscripts from
but is based on a memory in which every 8-bit byte the stack, and replaces them with the selected element.
has a unique address, rather than every bit having a The instruction also performs all bounds checking
unique address. This makes the principles of the EM-1 (unless disabled) and traps upon detecting a subscript
design applicable to a much larger number of com- error. A second opcode is needed for a P O P E L E -
puters than one utilizing arbitrary length bit fields. M E N T instruction that first pops the subscripts and
From Table I we see that the assignment, IF, then the value. With these two instructions, the state-
C A L L , R E T U R N and F O R statements together ac- ment A [I] := B [J] can usually be compiled into only 6
count for 96 percent of the source statements. There- bytes of object code, including all bounds checking
fore we will design an instruction set to handle the (PUSH J; P U S H E L E M ; P U S H I; POP E L E M ) . This
object code from these statements efficiently. To push is a substantial improvement over most conventional
local variables (including parameters) onto the stack, designs. Four format 2 instructions are needed for
we propose 12 distinct 1-byte (format 1) opcodes, one pushing and popping local and external array elements.
each for offsets 0-11. Twelve instructions allow access Note that this addressing scheme is not affected by
to all the locals (and parameters) in 94.6 percent of the size of the arrays. Assuming that a descriptor can
the procedures, and to more than 50 percent of the fit in a single machine word, a procedure with < 2 5 6
locals in the remaining procedures. For example, op- large arrays could nevertheless perform all array ac-
codes 114-125 might be used for P U S H L O C A L 0, cesses using exclusively format 2 instructions.
PUSH LOCAL 1..... P U S H L O C A L 11. There is For calling procedures, we envision one format 2
no need to have distinct " o p c o d e " and "address" bits. instruction whose offset is an index into a table held in
Eight opcodes will be allocated to stacking the 8 a special data segment. Each table entry could contain
external variables at the base of the stack segment. the segment and address of the object code, possibly a
Since 81.4 percent of the constants in our data were "not yet linked" bit, to implement dynamic linking as
either 0, 1, or 2, we allocate 3 opcodes for pushing in M U L T I C S , and possibly some protection machinery
these constants onto the stack. to keep less privileged procedures from calling more
At this point 23 of the 255 available 1 byte instruc- privileged ones. The symbolic name might also be
tions have been used. Another 20 are needed for present for debugging purposes and a counter to be
popping values from the stack. To handle programs incremented by the microprogram upon each call might
with up to 256 locals, or externals, 4 format 2 instruc- be provided for performance monitoring.
tions are needed: 2 push and 2 pop. Two more opcodes
To allow the instruction to locate the administration
(format 2) are needed to push positive and negative area in order to deposit the return address there, and
constants up to 256 onto the stack. Format 4 (16 bit
to update LB, the number of words of parameters is
offset) can contain instructions with larger offsets for
also needed. For programs with up to 256 procedures,
truly pathological programs. By including zero address
the call instruction will be 2 bytes, although a method
(stack) instructions for add, subtract, multiply, and
to reduce this to 1 byte in most cases will be described
divide, we have sufficient instructions to evaluate most
below.
scalar expressions, using 53 of the opcodes.
No additional instructions are needed for call-by-
Setting local variables to zero, and incrementing
value. For call-by-reference an additional format 2
them by 1, are so common that we allocate 24 format
instruction to push an address onto the stack would be
1 and two format 2 opcodes for this purpose. Incre-
useful, along with one to fetch a parameter passed by
menting the top of the stack is also worth an opcode.
reference (i.e. load indirect). The three most common
Array accesses are accomplished using descriptors
types of procedure calls are to increase the depth of
on the stack. Each descriptor (which may be 1 or
static nesting by 1, leave it unchanged, and decrease it
more words, depending on N, the word length) con-
by 1. Three opcodes are devoted to the three corre-
tains the bounds and strides, Si, for the array. For
sponding M A R K instructions.
example, the address o f A [i, j, k] can be found from
After a M A R K instruction the distribution of the
address = S o + $1 × i + $2 × j + $3 × k next few instructions is radically more different than
243 Communications March 1978
of Volume 21
the A C M Number 3
the normal one. This fact can be exploited to reduce guished by the number of operands they remove from
the procedure call instruction to 1 byte in many cases, the stack. The unconditional branch forward and back-
using a generalization of the idea of Foster and G o n t e r ward instructions do not remove any operands from
[3]. The only instructions than can follow a M A R K the stack. The second group removes one operand and
instruction are those needed to pass the parameters, if compares it to zero, branching forward if the condition
any, and the C A L L itself. Most parameters are con- specified by the opcode ( = , ~ , < , > , - , or ->) is met.
stants, variables, or simple expressions, which can This group is useful for statements such as IF N = 0
usually be passed using only a limited number of T H E N . . . If Boolean variables represent F A L S E by
different instructions, mostly load type instructions. 0 and T R U E by 1, this group can also be used for
About 200 opcodes could be reserved for CALL's, statements such as IF F L A G T H E N . . . .
each corresponding to a specific procedure descriptor. The third group of branch instructions removes
These C A L L instructions would each require only 1 two operands from the stack, compares them, and
byte. branches forward if the specified condition is met.
The simplest way to implement this would be to Backward conditional branches are not needed for
have the microprogram maintain the microaddress of translating IF statements (or W H I L E statements
the start of the instruction fetch loop in one of its either).
registers. At the end of the execution phase of each Each branch instruction specifies an offset which is
interpreted instruction the microprogram would jump the branch distance in bytes relative to the instruction
indirectly to this register. The M A R K instruction itself. (Offset = k means skip k + 1 bytes.) Interseg-
would reload this register with the address of an ment branches are prohibited, so that the procedure
alternative fetch loop, which would merely use a differ- call mechanism can be used to limit access to privileged
ent branch table, in effect temporarily remapping the procedures. The size of the offsets required can be
opcodes. The C A L L instruction could restore the estimated from the data of Table VIII. Based upon
normal opcodes by resetting just one internal register. the design proposed above, we estimate that the aver-
The use of opcode remapping can also be used in any age source statement will require not more than 4
other context with explicit first and last instructions. bytes of object code. This means that an offset with a
An instruction with a 1-byte offset is needed by the range of 0-3 (i.e. 4 instructions) is sufficient for nearly
called program to advance SP. The return instruction, half the IF statements, and a range of 0-15 (i.e. 16
which needs no offset, restores the stacked program instructions) is sufficient for more than 4/s of the cases.
counter and previous LB value (which are at known We need 14 opcodes to provide format 2 instructions
positions below the current LB) and resets SP. for the unconditional branch, 1 operand conditional
Our proposed F O R statement instructions are branch, and 2 operand conditional branch instructions.
based upon our measurement that 95 percent of the This leaves 141 opcodes over for the format 1
loops have a BY part of + 1 or - 1 . Before the loop, opcodes. A possible allocation covering most of the
the controlled variable is initialized, and the T O part frequently occurring cases is given in the summary of
is evaluated and pushed onto the stack. The EM-1 opcode usage below. If the average statement needs 4
F O R instruction reads the T O part and the controlled bytes of object code, the division proposed below will
variable. If the termination condition is met, a forward handle 77 percent of the IF tests in a single byte. Note
branch out of the loop occurs. Otherwise the controlled that "IF A = B " compiles into a branch N O T equal
variable is updated and the next instruction is executed. instruction to skip over the T H E N part.
The T O part is only removed from the stack when the We will not discuss the instruction set further here.
loop is terminated. To allow both tests for both upward Suffice to say that all the instructions that could not be
and downward counting, two opcodes are needed. included in format 1 or format 2 for lack of encoding
(For languages in which the T O and BY parts may room, are included in format 3B. Also versions of all
change during execution of the loop, variants of these the above instructions should be provided as format 4
instructions will be needed). Both instructions use instructions (16-bit offset). Instructions needed, but
format 3A. The offset of the controlled variable is in not discussed above, e.g. accessing intermediate lexi-
the second byte of the instruction, and the forward cographical levels of block structured languages should
branch distance is specified in the third byte. The body also be provided as format 3B and 4 instructions.
of the loop is terminated by an unconditional branch There should also be instructions for multiple precision
backward to the F O R instruction. arithmetic, floating point, shifting, rotating, Boolean
At this point we must devise instructions to handle operations, etc.
IF statements. A number of third generation machines It should be obvious that our design is not optimal
perform conditional branching by first setting condition in the information theory sense. More data and de-
code bits, and then testing them in a subsequent tailed simulation are needed to fine tune the choice of
instruction. EM-1, in contrast, combines these func- format 1 opcodes. On a user microprogrammable
tions, and eliminates the need for condition codes. computer, one can envision tuning the format 1 instruc-
There are three types of branch instructions, distin- tion set to match the measured characteristics of impor-
244 Communications March 1978
of V ol ume 21
the A C M Number 3
tant production programs, and loading a special highly Table XI. A Comparison of EM-1, PDP-11, and Cyber Object
Code Size (in Bits).
optimized microprogram before beginning program
execution. Alternately, a whole collection of single Ratios
chip microprocessors could be kept in house, each
with a read only microprogram tuned to a different PDP-
11/ Cyber/
application.
Statements EM-1 PDP-11 Cyber EM-1 EM-1
I := 0 8 32 45 4.0 5.6
I := 3 16 48 60 3.0 3.8
6. Discussion of the Machine Architecture I := J 16 48 75 3.0 4.7
I := I + 1 8 16 60 2.0 7.5
Our major point in this whole discussion is to I := I + J 32 48 90 1.5 2.8
illustrate that 1 byte instructions in this design can I := J + K 32 96 105 3.0 3.3
I := J + 1 24 80 75 3.3 3.1
often do the work of 4 byte or longer instructions in
I := A[J] 32 128 120 4.0 3.8
conventional machines. To illustrate the savings of A[I] := 0 32 112 105 3.5 3.3
EM- 1, Table XI gives some examples of the size of the A[I] := B[J] 48 192 180 4.0 3.8
EM-1 code compared to DEC PDP-11 code and CDC A[I] := B[J] + C[K] 80 304 285 3.8 3.6
Cyber code, as examples of mini and mainframe com- A[I, J, K] := 0 48 176 165 3.7 3.4
IF I = J T H E N . . . 24 64 105 2.7 4.4
puters. The PDP-11 and Cyber code sequences used
IF I = 0 T H E N . . . 16 48 60 3.0 3.8
for comparison are those a good compiler might rea- IFI = J + KTHEN... 40 112 150 2.8 3.8
sonably expect to generate in order to minimize object IF F L A G T H E N . . . 16 48 60 3.0 3.8
program size. It is assumed that these are fragments CALL P 16 64 60 4.0 3.8
from a block structured language that permits recursion C A L L P I ( I ) (by value) 24 96 90 4.0 3.8
C A L L P2(I, J) (by value) 32 128 120 4.0 3.8
and requires subscript checking. All local variables are
C A L L P3(I) (by reference) 32 112 90 3.5 2.8
assumed to be on the stack, not in registers (except FOR I FROM 1 TO N DO
loop indices) and EM-1 is assumed to be able to use A [I] := 0 0 D 88 176 225 2.0 2.6
the shortest instruction format. Both the PDP-11 and
Cyber make use of calls to run-time subroutines whose fast. The microprogram would fetch the opcode and
size is not counted here. then execute a 256-way branch. Since each of the
As a second test, 4 programs were carefully coded format 1 instructions is relatively simple, each instruc-
in assembly language for EM-1, the PDP-11 and the tion could be handled by a small number of microin-
Cyber. In contrast to the above examples, these were structions. In contrast microprograms for machines
complete programs, and the ground rules permitted like the PDP-11 and IBM 370 must do considerable
the use of registers. There was no run time system extraction and manipulation of short fields within the
(i.e. everything was coded in-line) and subscripts were target instruction. This is avoided in EM-1. By having
not checked. The results are given in Table XII. It a distinct microroutine for each of the twelve instruc-
should be noted that the PDP-11 and Cyber test tions that push a local variable onto the stack, none of
programs were carefully hand coded by an experienced these microroutines would have to do any decoding or
assembly language programmer. Few compilers could bit extraction, providing for very fast execution. The
ever generate object code this compact, whereas it other format 1 instructions would also be fast for the
would be easy to have a compiler generate the EM-1 same reason. Alternately, to reduce the size of the
code used in the examples due to the close match microprogram at the expense of execution speed, all
between the EM-1 instruction set and reverse Polish. the target instructions of a given type could share one
This means that EM-1 is actually much better than the microroutine.
above data might at first indicate. At first it may appear that producing code for EM-
It is important to realize that in an environment 1 would give compiler writers nightmares, due to the
consisting of many short procedures, the register sets multiple instruction formats. This problem can be
provided by a third generation machine are of little easily solved by first writing an optimizing assembler
value. They can be used for temporary results during that has a single mnemonic for "load local variable
expression evaluation, but from our data, that of onto the stack" (e.g. L O D L O C SYM), etc. The assem-
Alexander and Wortman, and also Knuth's, one regis- bler, and not the compilers, chooses the shortest feasi-
ter is usually enough. The registers cannot be used ble instruction format. The assembler should also rec-
effectively to hold local variables, because they must ognize sequences such as PUSH 0; POP X and PUSH
be constantly saved and restored upon procedure calls. X; PUSH 1, A D D , POP X and replace them by
This save-restore overhead will be very severe if, as Z E R O X and INCR X respectively. Compilers might
our data shows, one out of every four statements is a also leave the task of sorting the local variables on
procedure call. number of occurrences, and assigning the most heavily
Although we have not emphasized execution speed, used ones lower offsets to the assembler. Once such
a microprogrammed EM-1 machine is potentially very an assembler was written, it could be used as the last
245 Communications March 1978
of Volume 21
the A C M Number 3
Table XII. A Comparison of EM-1, PDP-11 and Cyber Object man coding. This leads to object programs that require
Code Size (in Bits) little memory and are capable of being executed very
Ratios easily (i.e. fast).

PDP-11/ Cyber/ Received February 1976; revised January 1977

Program EM/1 PDP-11 Cyber EM-1 EM-1
References
Towers of Hanoi 352 992 2205 2.8 6.3
1. A l e x a n d e r , W . G . , and W o r t m a n , D.B. Static and dynamic
sort integer array 562 1248 1260 2.2 2.2
characteristics of X P L programs. Computer 8 (1975), 4 1 - 4 6 .
dot product 552 832 1140 1.5 2.0 2. D e nni ng, P.J. Is it not time to define 'structured p r o g r a m m i n g ' ?
find primes 306 704 1020 2.3 3.3 Operating Syst. Rev. 8 (Jan. 1974), 6-7.
3. Foster, C.C., and G o n t e r , R . H . Conditional i n t e r p r e t a t i o n of
ope ra t i on codes. I E E E Trans. Comptrs. C-20, 1 (1971), 1 0 8 - 1 1 1 .
4. Huffman, D. A m e t h o d for the construction of m i n i m u m
pass of all compilers, allowing them to produce redundancy codes. Proc. I R E 40 (1952), 1 0 9 8 - 1 1 0 1 .
straightforward reverse Polish, and still get locally 5. Jensen, K., and Wirth, N. P A S C A L User Manual and Report.
Springer-Verlag, New Y ork, 1974.
optimal code.
6. Knuth, D . E . A n empirical study of F O R T R A N programs.
Software-Practice and Experience l (1971), 105-133.
7. Knuth, D . E . Structured p r o g r a m m i n g with go to s tatem en ts ,
7. Summary Computing Surveys 6 (1974), 2 6 1 - 3 0 1 .
8. Richards, M. BCPL: A tool for compiler writing and system
progra mmi ng. Proc. A F I P S SJCC, Vol. 34, A F IP S Press,
There is a certain analogy between a Huffman Mont va l e , N.J., 1969, pp. 5 5 7 - 5 6 6 .
code used to encode text in a minimal number of bits, 9. Salvadori, A ., G o r d o n , J., and Capstick, C. Static profile of
C O B O L programs. Sigplan Notices ( A C M ) 10 (1975), 2 0 - 3 3 .
and our proposal for a machine language with a com- 10. T a n e n b a u m , A.S. A p r o g r a m m i n g language for writing
pact instruction set. In both cases it is necessary to operating systems. R e p. IR-3, Wiskundig Seminarium, Vrije U.,
determine the frequencies of occurrence of the data to A m s t e r d a m , 1974.
11. T a n e n b a u m , A.S. A general purpose macro processor as a poor
be encoded (letters and instructions, respectively) by m a n ' s compiler. I E E E Trans. Software Eng. SE-2 (1976), 1 2 1 - 1 2 5 .
empirical measurements. We have done this and re- 1 2 . van W i j n g a a r d e n , A ., Mailloux, B., Peck, J . E . L . , and Koster,
ported the results in Section 3. Then an encoding C . H . A . R e p o r t on the algorithmic language A L G O L 68, N u m .
Math. 14 (1969), 7 9 - 2 1 8 .
scheme must be devised in which the most commonly 13. Wilner, W.T. Design of the Burroughs B1700. Proc. A F I P S
occurring cases are assigned the shortest bit patterns, FJCC, Vol. 4 1 , 4 9 7 , A F I P S Press, Montvale, N.J., 1972, pp. 4 8 9 -
and the least commonly occurring cases are assigned 497.
14. Wilner, W.T. B urroughs B 1700 M e m o r y Utilization. Proc.
the longest bit patterns. This is in contrast to a scheme A F I P S FJCC, Vol. 41, A F I P S Press, Montvale, N.J., 1972, 5 7 9 -
in which all cases are assigned the same length bit 586.
pattern. In EM-1 the most frequently occurring instruc- 15. W o r t m a n , D.B. A study of language directed c o m p u t e r design.
C S R G - 2 0 , U. of Toront o, Toront o, Ont. (1972).
tions are encoded in a single byte, which is both 16. Wulf, W . A . , Russell, D . B . , and H a b e r m a n n , A . N . BLISS: A
efficient in storage and avoids the problems associated language for systems p r o g r a m m i n g : Comm. A C M 14 (1971), 7 8 0 -
with variable length bit strings produced by true Huff- 790.

clam: James S. Cameron, Dept. of Mathematical Sponsor: ACM SIGCSE in cooperation with
Professional Activities Sciences, Denison University, Granville, OH IEEE-CS. Conf. chm: Alfs T. Berztiss. Dept. of
43023; 614 587-0810. Computer Science, University of Pittsburgh, Pitts-
Calendar of Events 20-21 April 1978 burgh, PA 15260; 412 624-6458.
ACM's calendar policy is to list open com- 1978 Computer Users Conference, East Texas 29 October-1 November 1978
puter science meetings that are held on a not-for- State University, Commerce, Tex. Sponsor: East N e w Orleans '78 International Data Process-
profit basis. Not included in the calendar are edu- Texas State University. Contact: Donna Hutche- ing Conference and Business Exposition, New
cational seminars, institutes, and courses. Sub- son, Dept. of Computer Science, East Texas State Orleans Hilton Hotel, New Orleans, La. Sponsor:
mittals should be substantiated with name of the University, Commerce, TX 75428; 214 468-2954. DPMA. Contact: Conference Coordinator, DPMA
sponsoring organization, fee schedule, and chair- 30 April-3 May 1978 International Headquarters, 505 Busse Highway,
man's name and full address. C o m p u t e r s in A c t i v a t i o n A n a l y s i s and Park Ridge, IL 60068; 312 825-8124.
One telephone number contact for those in- Gamma-Ray Spectroscopy, Mayaguez, Puerto 5-8 November 1978
terested in attending a meeting will be given when Rico. Sponsor: American Nuclear Society. Gen. Second Annual Symposium on Computer
a number is specified for this purpose. chm: B. Stephen Carpenter, NBS, Activation Applications in Medical Care, Washington, D.C.
All requests for ACM sponsorship or coop- Analysis, Bl18-Bldg. 235, Washington, DC 20234. Sponsor: George Washington University. Contact:
eration should be addressed to Chairman, Con- F. Helmuth Orthner, Dept. of Clinical Engineer-
ferences and Symposia Committee, Seymour J. 17-19 May 1978 ing, School of Medicine and Health Sciences,
Workshop on Petrl-Nets, Erlangen, Ger- 2300 K St., NW, The George Washington Uni-
Wolfson. 643 MacKenzie Hall. Wayne State Uni- many. Sponsor: Gesellschaft fiir Informatik in
versity, Detroit, MI 48202, with a copy to Louis cooperation with Institut fiir Mathematische Ma- versity, Washington, DC 20037.
Fiora, Conference Coordinator, ACM Head- schinen und Datenverarbeitung. Contact: Work- 15-17 November 1978
quarters, 1133 Avenue of the Americas, New York, shop uber Petrinetze, c/o Institut ftir Mathema- • Software Quality Assurance Workshop:
NY 10036; 212 265-6300. For European events, a tische Maschinen und Datenverarbeitung, Uni- Functional and Performance Issues, San Diego,
copy of the request should also be sent to the versit~it Erlangen-Niirenberg, Martensstrasse 3, Calif. Sponsors: ACM SIGMETRICS, SIGSOFT,
European Representative. Technical Meeting Re- 8520 Erlangen, Germany. and Los Angeles Chapter. Gen. chm: A.C. (Toni)
quest Forms for this purpose can be obtained Shetler, Xerox Corp., A3-49, 701 South Aviation
from ACM Headquarters or from the European 19-21 July 1978 Blvd., E1 Segundo, CA 90245; 213 679-4511 x1968.
Regional Representative. Lead time should include • Conference of Canadian Society for Compu-
2 months (3 months if for Europe) for processing tational Studies of Intelligence, Toronto, Canada. 4-6 December 1978
Sponsor: Canadian Society for Computational Winter Simulation Conference, Miami Beach,
of the request, plus the necessary months (mini- Studies of Intelligence in cooperation with ACM Fla. Sponsors: NBS, AIIE, IEEE Systems, Man,
mum 2) for any publicity to appear in Communi- and Cybernetics Society, ORSA, TIMS, SCS.
cations. SIGART, Conf. chm: C. Raymond Perrault,
Dept. of Computer Science, University of To- Prog. chin: Norman R. Nielsen, Information
Events for which ACM or a subunit of ACM ronto, Toronto, Ont., Canada M5S 1A1. Science Laboratory, (J-1041). SRI International,
is a sponsor or collaborator are indicated by 1. 333 Ravenswood Ave., Menlo Park, CA 94025;
Dates precede titles. 23-28 July 1978 415 326-6200 x 2859.
International Users Conference on Com-
In this issue the calendar is given in its entirety. puter Mapping Software and Data Bases, Harvard 20-22 February 1979
New Listings are shown first; they will appear University, Cambridge, Mass. Sponsor: Harvard • A C M Computer Science Conference, Day-
next month as Previous Listings. University Laboratory for Computer Graphics ton, Ohio. Sponsor: ACM. Conf. chm: Lawrence
and Spatial Analysis. Conf. chm: Allan Schmidt, A. Jehn, Computer Science Dept.. University of
520 Gund Hall, Harvard University, Cambridge, Dayton, Dayton, OH 45467; 513 229-3831.
NEW LISTINGS MA 02138; 617 495-2526. 14-16 March 1979
15 April 1978 14-15 August 1978 • Twelfth Annual Simulation Symposium,
• East Central SIGCSE Regional Conference, • A C M SIGCSE 9th Technical Symposium on Tampa, Fla. Sponsors: ACM SIGSIM, IEEE-CS,
Granville, Ohio. Sponsor: ACM SIGCSE. Conf. Computer Science Education, Pittsburgh, Pa. (Calendar continued on p. 249)

246 Communications M a r c h 1978

of V o l u m e 21
the A C M Number 3