On 7/30/2011 8:19 AM, David Barbour wrote:
On Sat, Jul 30, 2011 at 3:40 AM, BGB <cr88...@gmail.com
<mailto:cr88...@gmail.com>> wrote:
one could have a stack machine, implemented in terms of lists of
cons-cells, and this still works.
the stack can in-fact be mapped purely to machine registers, and
this also works.
Neither would help with concurrency.
concurrency doesn't care, because both multithreading and message queues
can be readily used with the stack machine abstraction.
concurrent execution of functions does not effect the model, since the
different threads of execution operate independently of each other.
for example, a language such as Erlang could likely also be readily
compiled using a stack-machine IL, despite being a language primarily
designed for concurrent systems.
the "stack" the compiler sees, in effect, doesn't actually exist
at runtime.
I'll grant that by 'stack machine' I am referring to a typical
implementation technique - not 'abstract' stack machine. Nonetheless,
many abstractions - such as pipelines, streams, and dataflow concepts,
for example - are not well modeled using a stack, whether intermediate
or final. The control-flow stack is too far from the target abstraction.
ok, but the "machine stack" model can be ignored here, for being
technically unrelated (and there is little merit in arguing if/how
x86/ARM/PPC/... implement their machine stacks is "ideal" or "universal").
the "abstract" stack machine is generally the only one which really
matters when it comes to using an RPN based IL.
this is because, the native machine stack, and the RPN stack, are
sufficiently unrelated that the machine-stack isn't even usable "as an
implementation of" the RPN stack, rather they are unrelated concepts
(typically, the machine stack is more just treated as a region for
reserving fixed-size frames in which one can put their temporary
variables and similar).
also, if one tried to naively map RPN operations to the machine stack
(say, using push and pop), this both wouldn't really work very well, and
would also perform poorly. so, they are not really directly related even
when both exist on the same target machine.
more common is to allocate a fixed-size frames (on x86, usually accessed
via offsets relative to EBP or ESP, and typically with regions for saved
callee-save registers, for temporaries, and for arguments to be passed
to called functions).
not *everything* needs to be a stack in a stack machine either.
nor does the model require that there be some single unified stack
ruling the entire system (typically there is not, usually there are many
independent micro-stacks).
operations like message passing / ... need not be all that much
different from ordinary function calls (and may be easily enough
implemented this way).
more commonly, the stack abstraction only really directly applies to a
small collection of blocks (often a single block at a time). typically,
a larger program may be split into any number of blocks (a given
function may itself contain multiple blocks).
also, stack-machines can model dataflow problems, it is just a matter of
"what" the computation is, how it is being used, and how it is handled.
a stack working with discrete values is not actually a requirement (nor,
for that matter, is sequential execution).
in fact, in a compiler, one typically does not work with discrete
values, but rather with the interrelationships between physical storage
locations (value movements, arithmetic operations, type conversions, ...).
the main convenience it has, over, say, TAC (Three Address Code) is,
roughly:
lifetime analysis is trivial (no forward scans needed);
operators typically only operate on directly adjacent values
(spatial/temporal);
handling "phi" operations can be much easier (there is no ambiguity as
to when and where to insert phi operators, as every value still on the
stack during a jump is its own 'phi');
much easier to produce by a frontend;
if needed, RPN may be readily translated to TAC (for example, this is
common with LLVM, which uses TAC internally);
...
the bounded lifetime of values, combined with their adjacent access,
tends to make tasks such as register allocation and handling temporaries
easier.
but, there are drawbacks:
may not fully express true machine capabilities (a stack machine is
naturally more constrained than an abstract register machine);
operations like expression simplification and common sub-expression
elimination are not as easily workable (these are left to the front-end);
one has to take note of stack-element ordering and how many values are
on the stack and similar (sometimes requiring operations to manipulate
stack layout, such as exch, index, and roll);
...
_______________________________________________
fonc mailing list
fonc@vpri.org
http://vpri.org/mailman/listinfo/fonc
