Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site ulysses.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!smb
From: smb@ulysses.UUCP (Steven Bellovin)
Newsgroups: net.arch
Subject: Re: Stack architectures - why not?
Message-ID: <1094@ulysses.UUCP>
Date: Wed, 11-Sep-85 12:30:38 EDT
Article-I.D.: ulysses.1094
Posted: Wed Sep 11 12:30:38 1985
Date-Received: Thu, 12-Sep-85 12:20:48 EDT
References: <796@kuling.UUCP> <172@myriasa.UUCP>
Organization: AT&T Bell Laboratories, Murray Hill
Lines: 53

> First, keep in mind that I'm a compiler writer by trade, so I like the
> idea of a pure stack architecture because it's so easy to generate code
> for (I did it for a machine I designed and emulated).
> 
> I've been told by a couple of people who are normally well informed that
> a pure stack architecture just isn't practical. They have NOT been able
> to convince me of this. Anybody out there want to try?

Well, I'll give it a shot, though it's been a few years since I
seriously studied this.  Note that some of the traditional objections
-- listed in the original article -- no longer apply, because of the
decreasing cost of hardware.

The primary advantage of a stack machine from an architectural point of
view is that it provides good address abbreviation.  (Registers serve a
similar function, even when caches and the like make their speed
advantage minimal.) Given that the memory to CPU bandwidth is a
critical limiting factor on performance, such abbreviation is useful
indeed.  So far, so good.  Unfortunately, with an optimizing compiler
stack machines lose their advantage.  Common subexpressions and the
like require a sufficiently large number of DUPLICATE-TOP, SWAP-TOP-2,
and COPY-ELEMENT-TO-TOP operations that the advantage in terms of total
memory bandwidth is lost.  We thus have a situation where simple
compilers are easier to write, and produce better code;
production-quality compilers are not easier and produce no better
code.

There is also a conflict between the subroutine stack and the expression
stack.  Unless you add some truly oddball instructions, you'll need two
separate stacks, which can complicate your operating system storage management.
(Admittedly, this is less of a problem today with 32-bit name spaces
becoming routine; as we start using them up, we'll have to think about the
issue again....)

Finally, although stack machines are useful for arithmetic processing,
they're far less natural for non-numeric work -- string processing,
record-oriented commercial goo, LISP, etc.  Look at, say, the UNIX kernel --
very little of it would benefit from a stack architecture, and much of it
would suffer.

My conclusion:  the right answer, at least for now, is a machine with a good
subroutine stack.  Other issues, notably the complexity of the instruction
set, are open.

		--Steve Bellovin

P.S.  Many of these points, especially those concerning memory bandwidth, are
from Fred Brooks' Computer Architecture course.  I believe he attributed
that particular argument to Gene Amdahl.  Brooks wanted to make the 360 a
stack machine (yes, big bad IBM seriously considered that), but Amdahl
showed that it wouldn't fly.  Some of his arguments turned on the cost of
the necessary hardware at the time; these, of course, are much less
interesting today.