Assembly language - Stack machine

Question

I am learning assembly language in my spare time to become a better developer.

I understand the difference between stack-based machines and register-based machines at a conceptual level, but I am wondering how stack-based machines are actually implemented. If a virtual machine, e.g. JVM or .NET, runs on a register-based architecture, e.g. x86 or x64, then it must use registers at the assembly level (as far as I am concerned). I am obviously missing something here. Therefore I am unsure of the distinction at assembly language.

I have read articles on here e.g. Stack-based machine depends on a register-based machine? and also on Wikipedia, but I don't believe they answer my question directly.

Preheat

They could emulate it in software, older JVM's did that. Typically though the stack-machine code is compiled to native code (whatever architecture that may be). Stack machine code is nice because it has a concise encoding, it's easy to generate from ASTs and relatively easy to analyze. – Cuffs

Answer 1

then it must use registers at the assembly level

That's not a requirement, processors have a cpu stack that behaves a lot like the virtual stack in the intermediary language. You can translate the instructions almost one-to-one to cpu instructions. Certainly one of the reasons that stack based VMs are popular, the jitter is easy to implement.

The only hangup with doing it that way is that the machine code isn't very efficient. It is the job of the jitter optimizer to find ways to use the cpu registers efficiently and make the code faster that way.

The opposite problem is present in register-based VMs. It is a harder problem to solve since the real CPU doesn't have as many registers as the VM. So the jitter must find ways to use the stack to spill registers that the hardware doesn't provide.

Sowder

Answer 2

Stack based machines are rarely implemented in hardware - I've only every heard of one such implementation, and have never had the chance to work on one.

In reality Stack machines are implemented on real register based processors by native interpreters. In essence, the theoretical Stack machine is emulated by the real Register based machine.

So to answer your question: although the machine code of the stack machine doesn't have registers, the native interpreter that executes these instructions does have registers and will be using them.

Q: So why the indirection? A: Portability - the instruction set of the stack machine can be emulated on any number of different register based machines. This means that the same JVM application can be run on any machine that has an interpreter, hence the old Java slogan "Write once, Run anywhere"

Dictograph

what do you mean by "native interpreter". Are you referring to the JIT compiler (in the case of .NET)? – Preheat

By "native interpreter" I mean a the application that runs on your local machine that reads the Stack machine instructions are executes them. Each type of machine (and OS) will have a different "native interpreter". In the case of Java the "native interpreter" is the JVM. JIT's are something slightly different. – Dictograph

Just for your reference, a JIT is something that turns the stack machine instructions into an equivalent set of instructions for the native machine (the register based one). This is an attempt to give the application a performance that is close to that of the native processor, but at the same time keep the advantages to portability. – Dictograph

Hans Passant@ It's certainly true that the native processor isn't required to use registers, but in practice 1) Registers are much faster than stacks, so for performance you'd probably want to. 2) On many CISC based processors not all instruction can be carried out on stack data. The data would have to loaded into a register before it can be manipulated. That said, it's up to the interpreter developer to decide how to implement the instructions. – Dictograph

thanks. You refer to an interpreter, which has confused me a little as I know that .NET and Java are compiled languages; unlike PHP, which is interpreted. Could you clarify this? Thanks again. – Preheat

No Problem. As you rightly say, Java and the .Net languages are compiled. What they are compiled into is a "byte code" - this basically an assembly language for an abstract processor. What it is not is x86 assembly language; your PC's processor can not directly understand these instructions. What in needs to do is launch an interpreter (e.g. the JVM) which will read these instructions and perform the desired actions. So one way to think about the JVM is that it's a interpreter for a really low level language! – Dictograph

just for completeness, the alternative approach is the JIT. These take the byte codes and compiles them, at run time, into native machine code, which in turn is executed by the processor directly. No interpreter is required - just a second compiler! – Dictograph

thanks. Therefore it is reasonable to say that the JIT uses assembly registers when it compiles the bytecode. – Preheat

It's not strictly required, but it almost certainly does – Dictograph

For reference, Burroughs B5000 and Inmos Transputer were stack machines. DEC PDP11 had such flexible addressing modes that it could be used as a stack machine. I think Niklaus Wirth's Lilith may have been a stack machine (more than 20 years ago, my mind is slipping :-) – Furfur

Answer 3

For reference, Burroughs B5000 and Inmos Transputer were stack machines. DEC PDP11 had such flexible addressing modes that it could be used as a stack machine. I think Niklaus Wirth's Lilith may have been a stack machine (more than 20 years ago, my mind is slipping :-)

They really did not have any register name/number in instructions to find operands, because they were on the stack.

Instructions could load immediate (constant) values onto the stack, or load/store to memory.

So their was no add.w r0, r1, r5 or add.w eax, [#fe34]. There was add.w.

So an example (not at all accurate, it was more complex) of an assembler sequence might be

loadstack 0xfe34   -- got fe34 onto stack
loadstackindirect  -- use address on the stack, to load the value at that address
add.w              -- assumes we already have the other operand on the stack
                   -- result back onto the stack

To calculate and load a value in an array, the stack might be used because there might be no indexed addressing mode.

So instructions were small, and lots of work was done implicitly with the stack and stack pointer. IIRC Transputers actually had a stack of only three values, and the compiler (or developers) had to ensure that was maintained.

XMOS now sell a modern 'equivalent', and employ some of the same people.

It is over 20 years since I wrote Transputer code, so sorry for being a bit vague.

The UCSD Pascal system used a software defined virtual machine, which was a stack machine. The idea was to make something which was portable to new computers, but also easy to write, easy to compile to, and reasonable performance. It's virtual machine was defined in its own Pascal dialect. When it was ported to real computers, registers would be used to hold the stack pointer, and likely some ingenuity in how the top of stack was handled (by registers), in order to get reasonable performance.

Furfur