Stack machine architecture

iunie 30, 2024

Stack machine architecture

The simple architecture described here is sufficient to implement most imperative programming languages.

Stack machine architecture

A generic Von Neumann architecture computer has a processor and memory; a few special-purpose registers are used to implement a stack for function calls and to track the current instruction. A simulator for this architecture might look like the following Java declarations:

byte[] memory;
 
int[] stack;
 
/** Stack pointer */
int sp;
 
/** Frame pointer for function call activation records */
int fp;
 
/** Instruction pointer register */
int ip;

Assume that the data/code memory is byte addressable but that the stack is 32-bit word-addressable.

    ----------------
 0: |  data memory |
    |              |
    |              |
    ----------------
 cp:|  code memory |    begins right after data
    |              |
    ----------------

Instructions are placed in memory relative to a known address; by placing that address in a register instructions are relocatable.

/** For relocatable code, set "code pointer" */
int cp;

For this discussion assume there are only integer data types. From an interpreter point of view there are only global (stored in memory) and local variables (stored on the stack; parameters are like locals).

Operations all occur on the stack rather than in registers. The stack holds either integers, booleans, or saved registers. You may call functions and use their results in expressions. The stack is word-addressible and always holds an int . There is no "type tag" associated with the stack elements. That means that the result of boolean operation LT ("less than") must be converted to an integer. Instructions are usually provided to do data conversions such as BOOLEAN_TRUE and BOOLEAN_FALSE for this purpose.

Instruction execution

Instructions are encoded in memory as opcodes. Opcodes are 8 bits and their operands are 32-bits. Operands of instructions are either data/code addresses or integer constants. For example, here are three instructions that perform 3+4 :

const 3
const 4
add
halt

That is assembly code. In code memory, they are represented by machine code:

Code memory (offset 0):
00000000:  0E 00 00 00 03 0E 00 00
00000008:  00 04 01 15

where const is opcode 0x0E and its operand as a 32-bit number is 0x00000003 . The opcode for add is 0x01; halt is 0x15.

Execution of a program proceeds by fetching an instruction and then jumping to some code that implements that instruction:

/** Simulate the fetch-execute cycle */
protected void cpu() throws Exception {
    byte opcode = memory[cp+ip];
    int v = 0;
    int addr = 0;
    while (opcode!=INSTR_HALT) {
        ip++; //jump to next instruction (or first byte of operand)
        switch (opcode) {
            ....
        }
        opcode = memory[cp+ip];
    }
}

For example, the ADD instruction looks like this:

case INSTR_ADD :
    v = stack[sp+1] + stack[sp]; // get two operands
    sp += 2; // remove operands
    stack[--sp] = v;  // push result
    break;

The Java code will look very much microcode, the "subatomic" instructions used to implement actual machine instructions in many older processors.

Global variable access

Global variable access is a matter of load and store instructions whose operand are addresses in data memory.

int i;
f() {
  i = 3;
}

would result in:

; data declarations go first
    .decl i
;
; then instructions
;
f:
    const 3
    store i
    ret 0

After execution the memory with look like:

Data memory (offset 0):
00000000:  00 00 00 03
 
Code memory (offset 4):
00000004:  0E 00 00 00 03 11 00 00
0000000C:  00 00 0A 00 00 00 00 09
00000014:  00 00 00 00 15

You can see that function f begins at address 4 after the data memory.

Method calls, frames

Most instructions are easy to implement. The function call and return instructions are easy to understand, but difficult to implement. This section describes the information flow from one function to another and back as well as how this information is encoded on the stack.

Simple call/return

To call another function, the program must record where it's at now so that it can return to the same spot upon completion of the subprogram. Pushing the return address on the stack and then doing a branch to the function implements call nicely. The ret (return) instruction can simply pop off the return address and set the instruction pointer to that location. The following C code:

void f() { g(); }
void g() { ; }

would result in the following instructions:

f:
    call g
    ret 0
g:
    ret 0

Ignore the 0 operand for now. Before the call instruction the stack would look like:

    | f work space |
sp: |     ...      |

After the call but before the return in method g :

       |     ...      |
       ----------------
       |    f+0x05    | (return address; 4 bytes beyond f() start)
sp,fp: |    old fp    | (saved fp used by f)
       ----------------
       | g work space |
       |     ...      |

To perform the return instruction, the interpreter pops the old frame pointer and sets the instruction pointer to the return address on the stack (popping it off). Ignore the frame pointer for now.

Functions with return values

What about return values? The return value is left on top the stack and then the function call stack activation record is cleaned up and the return value is pushed back on the stack:

void f() { g(); }
int g() { return 3; }

would result in the following instructions:

f:
    call g
    ret 0
g:
    const 3
    retv 0

After the call but before the return in method g :

    |     ...      |
    ----------------
    |    f+0x05    | (return address)
fp: |    old fp    |
    ----------------
sp: |      3       |
    |     ...      |

Parameters and local variables

What is a the end of the frame pointer? It is used access local variables and parameters off the stack.

Here is a stack activation record in its full glory for a function call right after the execution of a call instruction:

    |     ...      |
    ----------------
    |     arg 1    |
    |     arg 2    |
    |     ...      |
    |     arg n    |
    |   ret addr   |
 fp:|    old fp    |
    |   local 1    |
    |   local 2    |
    |     ...      |
    |   local m    |
    ----------------
    |  work space  |
    |     ...      |

void f() { g(3,4); }
void g(int a, int b) {
  int i;
  i = a+b;
}

would result in the following instructions:

f:
    const 3 ; push args
    const 4
    call g
    ret 0
g:
; int i;
    lalloc 1 ; allocate 1 local
; i = a + b
    fpload 3 ; load 1st parameter
    fpload 2 ; load 2nd parameter
    add
    fpstore -1 ; store in 1st local
    ret 2

Parameters are placed in order on top of the stack before the called is executed. The frame pointer points in to the middle of the stack frameAnd parameters are at positive all sets while local variables or add negative offsets. The first local variable is add negative one. The last parameter is an offset 2, the second to last parameter is an offset 3, and so on.

In general parameter i is at stack[fp+2+(n-i)] since we push args in specified order rather than reverse. Local i is at stack[fp-i] . The compiler is required to compute an integer constant such as 2 that accesses the first argument or -1 that accesses the first local.

call. The call instruction then does the following:

fetch the target address operand
save the instruction pointer by pushing on the stack
save the old frame pointer
set the frame pointer to point to the current stack top, sp.
perform a branch to the target address by setting the instruction pointer.

And now the ret and retv instructions operand. The operand indicates how many parameters there are to pop off before pushing the return value (if any). retv will first save the top of stack, since that is the function return value, and then pop the activation record off. After the stack is cleaned up, retv will push the return value back onto the stack.

return. The ret instruction does the following:

fetch the operator and that indicates how many arguments, n , to pop off
set the stack pointer to the frame pointer
pop the frame pointer off the stack; set fp
pop the return address off the stack; set ip
pop n arguments off the stack

Complete instruction set

ADD
SUB
MULT
DIV
LT
GT
EQ
NOT
CALL
RET
RETV
BR
BRT
CONST
LOAD
FPLOAD
STORE
FPSTORE
LALLOC
PRINT
HALT

Program Loading and Launching

To execute code one must first loaded into memory at the appropriate spot, which is just after the data memory. The following 2 functions are in the interpreter.

/** Load program into memory, set up data memory, set ip etc... */
protected void loader(byte[] code, int ip, int dataMemorySize) {
    this.dataMemorySize = dataMemorySize;
    // make enough room for code + data
    memory = new byte[code.length+dataMemorySize];
    // load code just above data memory
        cp = dataMemorySize; // code pointer base right after data memory
    for (int i=0; i
        memory[cp+i] = code[i];
    }
    this.ip = ip; // ip is relative to cp when executing
}

To begin execution, one simulates a call from the operating system to the main program start address.

/** Execute the bytecodes in "code" starting at ip; alloc
 *  enough static memory for dataMemorySize bytes.  You cannot
 *  define data memory before execution--must set with code.
 */ 
public void exec(byte[] code, int ip, int dataMemorySize)
        throws Exception
{   
    loader(code,ip,dataMemorySize);
    // set up stack environment
    stack = new int[DEFAULT_STACK_SIZE];
    sp = DEFAULT_STACK_SIZE; // empty to start, grows downward
 
    // SIMULATE "call main"; manually set up stack as if we called main()
    stack[--sp] = ip; // save ip
    stack[--sp] = fp; // save fp
    fp = sp;          // new fp points to saved fp
 
    cpu(); // launch the process at ip
}

A generic assembler

An assembler for stack machine is usually very simple. It is a function note a list of instructions and an instruction to opcode mapping. After assembly, the invoking program pulls out the machine code, the data memory size, and the address of the main program:

AssemblerLexer assemblerLexer = new AssemblerLexer(System.in);
Assembler assembler = new Assembler(assemblerLexer,
instructions);
assembler.program();
byte[] program = assembler.getMachineCode();
int dataSize = assembler.getDataMemorySize();
int startip = assembler.getMainInstructionAddress();

Inside the interpreter is a set of opcode definitions that are sent to the assembler:

// INSTRUCTION BYTE CODES
public static final int INSTR_ADD = 1;
public static final int INSTR_SUB = 2;
...

An array of strings representing the names of all valid opcodes is sent to the assembler so that it knows how to assemble. The position in the string array is the opcode. In this way, your assembler/interpeter is easily extendable:

public static String[] instructions = new String[] {
    "",
    "ADD", // index is the opcode
    "SUB",
    ...
};

Finally, in order to disassemble code, it is useful to define which opcodes have operands:

public static int[] operands = new int[] {
    0, // 
    0, // ADD
    0, // SUB 
    ...
};

As instructions are read, the location in data memory and code memory are incremented:

/** Data address pointer */
    protected int dp = 0;
     
    /** Instruction address pointer */
    protected int ip = 0;
   
    /** where to store machine code while assembling */
    protected byte[] code = new byte[MAX_CODE_SIZE];

Here is the assembly grammar, similar to what to build for your project in the grammar marathon.

program
    :   ( data )* // data first
        ( instr | label )+
    ;
 
data:   ".decl" ID NEWLINE    
    ;
 
instr
    :   ID operand NEWLINE
    |   ID NEWLINE
    ;
 
operand 
    :   ID
    |   INT
    ;
 
label
    :   ID COLON (NEWLINE)?
    ;

There are a number of methods triggered by the grammar to implement assembly:

protected void gen(Token instrToken) {;}
    protected void gen(Token instrToken, int operand) {;}
    protected void checkForUnresolvedReferences() {;}
    protected void declareData(Token idToken) {;}
    protected int getOperandAddress(Token idToken) { return 0;}
    protected void defineLabel(Token idToken) {;}

A subclass of the grammar defines them.

Symbol table management

There are three classes of interest: Symbol , CodeSymbol , and DataSymbol . A symbol is just a name with and associated address. For implementation sake, the symbol also knows whether or not it's a forward reference and whether or not it has been defined. This allows us to implement the standard scheme of forward reference and we discussed previously:

public class Symbol {
    String name;
 
    /** Address in data / instruction memory */
    int address;
 
    /** Is this ref'd before def'd. */
    boolean forwardRef = false;
 
    boolean defined = true;
...
}

The 2 concrete symbol table classes do everything in their constructors:

public class DataSymbol extends Symbol {
    public DataSymbol(String name, int address) {
        super(name);
        this.address = address;
    }   
}       
 
public class CodeSymbol extends Symbol {
    public CodeSymbol(String name, int address, boolean forward) {
        super(name);
        forwardRef = forward;
        if ( forward ) {
            // if forward reference, then address is address to update
            addForwardReference(address);
        }
        else {
            this.address = address;
        }
    }
}

Byte-code interpreter for C-like language

The above architecture is sufficient for C w/o structs. Here are some relevant questions:# Why not simulate a register machine instead of a stack machine?

Would your stack be typed (in other words, if you push 34 on the stack would you know it's an int later on)?
What could you do to make the interpreter more efficient (including reorganizing byte codes)?
Consider how you might compile the byte code on the fly. In particular, how you would generate and execute the following:
1. a threaded interpreter
2. native stack code
3. register code

Byte-code interpreter with data aggregates

Assuming you have a basic interpreter that handles simple primitives like int and float , how would you add data aggregate support? In other words, how would you translate

struct payment {
  int employeeID;
  float amount;
};
 
struct payment pay;
 
void f() {
  pay.amount = 330;
}

Would you need a new instruction?

Byte-code interpreter with pointers

Ok, now add pointers like the following:

int *p;
int x;
void f() {
  p = &x;
  *p = 99;
}

What would the bytecodes look like
What would the bytecodes for pay->payment=330; look like if pay were a pointer to a payment structure from above Assume pay is at address 0?

Byte-code interpreter with polymorphism

Method calls are pretty simple for a non-object-oriented language like C. If you call function foo() , you can generate the simple:

call f

instruction. What if you want to call method getEmployeeID() on a Payment object defined as follows?

class Object {
  // methods defined in all classes
  public Class getClass() { ... }
  public String toString() { ... }
}
 
class Payment extends Object {
  int employeeID;
  float amount;
  public int getEmployeeID() {
    return employeeID;
  }
}
 
...
Payment p = new Payment();
int ID = p.getEmployeeID();

Is the layout of an object any different in memory than a struct ? Does an object require more memory space for the same list of fields?
What byte codes would you generate for p.getEmployeeID() for local p ?
Do you need to have symbol table information around at run-time to implement polymorphism? Do you need type information stored in each object?

Faceți căutări pe acest blog

Software Engineer Laboratory

Stack machine architecture

Stack machine architecture

Instruction execution

Global variable access

Method calls, frames

Simple call/return

Functions with return values

Parameters and local variables

Complete instruction set

Program Loading and Launching

A generic assembler

Symbol table management

Byte-code interpreter for C-like language

Byte-code interpreter with data aggregates

Byte-code interpreter with pointers

Byte-code interpreter with polymorphism

Comentarii

Trimiteți un comentariu

Postări populare

Cum să-ți faci propriul hosting acasa

Instalare magazin online NopCommerce(open source) pe Linux