The stack controversy

|

picture of stacking plates
Just when you think an old misconception is dead...

The "stack/no stack" discussion has arisen again. We've heard renewed
claims that C programs require a hardware stack, and that a software
stack is unacceptably slow. Both ideas are patently false.

Sure, silicon manufacturers offer hardware stacking for context
preservation, parameter passing, and local variables. But that doesn't
mean it's optimum, or even needed.

When we design a Code Development System for an embedded target
architecture, we analyze the CPU resources and instruction set. We
look at how memory resources and clock cycles are consumed in typical
programming. If conventional stack operations are too costly, we can
often avoid them.

So, keep these thoughts in mind:

1. Software stacks are not slow.

Runtime function frames, that live on a stack of some kind, only need
to be allocated for the functions that are recursive, either directly
or "long path". Minimizing the number of recursive functions through
compiler optimizations significantly improves performance.

We have metrics that show that, in real life embedded system
applications, fewer than 1% of the applications need recursive support
(6 in 2000 applications in our sample).

Tail end recursion and other optimizations eliminate most of the
recursive functions. Tail calls have been described as "GOTO with
parameters", obviously not needing stacking. The internet has numerous
resources on how to encourage tail call optimization.

Non-recursive functions can use the full instruction set for data
access and manipulations. Our experience is that this improves
performance enough to justify using similar techniques on processors
that have a full data stack.

2. Stackless processors are being used now.

We don't look at cores the way assembly programmers do. We're happy
with bare-bones programmer's models, so long as the required
fundamentals are present. A stack is not one of them: we've run into
several stackless cores recently, and have had no problems developing
C compilers for them.

The eTPU is a 24-bit enhanced time processing unit, used in automotive
and general aviation engine control, and process control. eTPU may be
a co-processor, but it has a complete instruction set and a full CPU
core, and it's stackless. It is a mid-volume processor: chances are
you'll drive or fly home tonight courtesy of C on a stackless
processor.

We have a C compiler for the eTPU based on C99 and ISO/IEC 18037.
We run standard C test suites on this processor.

The Freescale RS08 is a more traditional MCU that is stackless. In the
process of "reducing" the HC08/HCS08 core, Freescale removed the CPU
stack. We consulted on the architecture of RS08, and we never felt the
need to insist on a hardware stack.

To mention another co-processor we consulted on, the Freescale XGATE
has a very friendly ISA and programmer's model, but it doesn't have a
stack.

Then there are the "nearly stackless". Microchip PIC never had data
stacking, with only an 8-entry (or 16-entry in the enhanced 14-bit
core) call-return stack. Nobody doubts that C is available for PICs.

These parts, especially the eTPU, were designed to be compiler
friendly and encourage machine-generated code.

There are other non-stack-based processors, some created recently,
spanning a range of applications and enjoying their own C
compilers. There are mid- to high-volume stackless parts. Performance
is usually the primary reason that parts do not have a stack.

3. Stacks are an academic question

It's true that most of the stackless processors that we are aware of
have RISC architectures. Designers are constantly trying and retrying
different tradeoffs in the search for a strong processor design.

There are stackless processor designs and stackless code
implementation papers. Googling "stackless processors" gets about
16,000 hits, many of them on Stackless Python.

There are also many processors that do have an effective hardware
stack. Our experience tells us when a vendor has gotten their hardware
stack model right, and when it won't be of much use. If it improves
performance and saves resources, we're happy to use it.

But the misconception about C and stacks has gone on a little too
long. Hardware stacks aren't obligatory. Software stacking is a
perfectly viable alternative.