How to implement CALL & RET to an assembler?

Question

According to this made-up microprocessor architecture's instruction set: https://github.com/mertyildiran/DASM

In our toy assembler written in C, we have implemented PUSH & POP instructions as shown below:

PUSH:

Which is basically the combination of 4 DEC and 1 ST instruction.

        else if (strcmp(token,"push")==0) // PUSH instruction: combination of 4 DEC and 1 ST instruction on Stack Pointer (SP)
        {
            op1 = strtok(NULL,"\n\t\r ");
            op2[0] = sp; // Let's say address of SP is 9
            printf("\n\t%s\t%s\n",strupr(token),op1);
            ch = (op2[0]-48) | ((op2[0]-48)<<3); // Prepare bitwise instruction format for DEC instructions
            program[counter]=0x7800+((ch)&0x00ff); // Decrease Stack Pointer 4 times
            printf("> %d\t%04x\n",counter,program[counter]);
            counter++;
            program[counter]=0x7800+((ch)&0x00ff); // Decrease Stack Pointer 4 times
            printf("> %d\t%04x\n",counter,program[counter]);
            counter++;
            program[counter]=0x7800+((ch)&0x00ff); // Decrease Stack Pointer 4 times
            printf("> %d\t%04x\n",counter,program[counter]);
            counter++;
            program[counter]=0x7800+((ch)&0x00ff); // Decrease Stack Pointer 4 times
            printf("> %d\t%04x\n",counter,program[counter]);
            counter++;

            ch = ((op1[0]-48) << 2) | ((op2[0]-48) << 6); // Prepare bitwise instruction format for ST instruction
            program[counter]=0x3000+((ch)&0x00ff); // Store the value in Stack
            printf("> %d\t%04x\n",counter,program[counter]);
            counter++;
        }

POP:

Which is basically the combination of 1 LD and 4 INC instructions.

        else if (strcmp(token,"pop")==0) // POP instruction: combination of 1 LD and 4 INC instructions on Stack Pointer (SP)
        {
            op1 = strtok(NULL,"\n\t\r ");
            op2[0] = sp; // Let's say address of SP is 9
            printf("\n\t%s\t%s\n",strupr(token),op1);

            ch = (op1[0]-48) | ((op2[0]-48) << 3); // Prepare bitwise instruction format for LD instruction
            program[counter]=0x2000+((ch)&0x00ff); // Store the value in Stack
            printf("> %d\t%04x\n",counter,program[counter]);
            counter++;

            ch = (op2[0]-48) | ((op2[0]-48)<<3); // Prepare bitwise instruction format for INC instructions
            program[counter]=0x7700+((ch)&0x00ff); // Decrease Stack Pointer 4 times
            printf("> %d\t%04x\n",counter,program[counter]);
            counter++;
            program[counter]=0x7700+((ch)&0x00ff); // Decrease Stack Pointer 4 times
            printf("> %d\t%04x\n",counter,program[counter]);
            counter++;
            program[counter]=0x7700+((ch)&0x00ff); // Decrease Stack Pointer 4 times
            printf("> %d\t%04x\n",counter,program[counter]);
            counter++;
            program[counter]=0x7700+((ch)&0x00ff); // Decrease Stack Pointer 4 times
            printf("> %d\t%04x\n",counter,program[counter]);
            counter++;
        }

So my question is how can we implement CALL & RET instructions with using a stack?

I'm aware that CALL instruction will store current state of PC in the stack so the program will be able to return where it left with RET instruction. But it's leading me to two subquestions:

1. After CALL executed, how the program get address previously stored in the stack if in the subprocedure, an instruction PUSHed something to the stack or overwrite the return address of CALL.
2. How can we pass the related label's address to CALL in machine code level? In our assembler JMP & jZ instructions are also not completed, because of the same reason.

If you want to look at the whole picture: https://github.com/mertyildiran/DASM/blob/master/assembler.c

For 2. subquestion(JMP/CALL) you can explain it over this example with maybe jmp lpp line:

.data
     count: 60
     array: .space 10
     char: 0xfe
.code
        ldi 0 count
        ld  0 0
        ldi 1 array
        ldi 2 char
        ld  2 2
lpp     st 1 2
        inc 1
        dec 0
        jz loop
        jmp lpp
loop    sub 1 2 3
lp1     jmp lp1  

Answer 1

"how an assembler pass label address to JMP instruction?"

That should be obvious from the machine/CPU architecture, how it does decode the instructions. I'm a bit confused from your question, whether the made-up CPU is already final (then it should describe, how you can load pc register = that's basically what jump does, plus it may be conditional), or you are doing two projects in one, creating both the HW machine specs, and an assembler for it. And I'm too lazy to read it again, so I will just show you common ways from real world.

ARM - RISC-like instruction set, fixed opcode size:

Both in 16b (thumb) and 32b mode the first few bits of opcode specify the instruction (B, BL, BLX, B is pure jump, BL is similar to CALL, but not using stack, a "link" register is used instead to store return address), the rest of bits specify either register holding the target address (so to call function foo you can do load r0,foo bl r0), or immediate value which is relative to current PC.

Which means, that in 16b mode you can jump +-2kiB unconditionally, or -252 to +258 conditionally (the condition variant is encoded in further bits, taking away some from the immediate).

This leads sometimes to situation, where high level compilers either use the register variant, or jump near enough to another jump instruction which hops even further.

In 32b mode the remaining bits reserved for immediate give you much better range, about +-32MiB for all variants. (there's one more mode, 32b "thumb" which has one more different encoding, but that's irrelevant in this example).

Fun fact, the bit-0 in address does specify whether the instruction there is in thumb mode, or full 32b mode, as all addresses must be aligned on ARM, so jump to address 0x00000001 is jump to 0x00000000 with switch of CPU to thumb mode.

x86 - CISC-like historically extended beyond good taste

this one has almost all possible variants (except the one you really need in that long .asm you have been writing last 3 months). Instructions encoding has variable length, so the instruction does use as many bytes, as decided by Intel to be needed.

• relative jumps (short with single byte -128 ... +127) - check
• absolute jumps to address (encoded as jmp opcode byte, then as many bytes as needed to encode the address)
• register jumps (to the address stored in register)
• conditional relative jumps (not just "extended" jmp encoding as in ARM case, but specific opcodes)
• extras like loop, jcxz/jecxz and maybe some more I even forgot.

---

So it boils down either to load the value into some register, or encode the immediate into the instruction opcode, then either treat it as an absolute address (which for example on 32b platform, where you manage to encode 25 bits for address, would allow you to address 32MiB of RAM; instead of 4GiB), or as relative address (25bits => pc+-16Mi).

---

Addendum, which is maybe part of your problem? Like how to "know" what address will be at some future label?

Most of the assemblers are two-pass, so they first generate the instruction opcodes (and can calculate the length of each part of source), and collect all symbols in symbol table, then all address symbols are defined according to the opcodes lengths and org directives. Then in second pass you fill up all immediate values in opcodes by the particular symbol value.

This also shows, why two-pass assemblers can't handle jmp rel8/rel16 (relative jump defined either by 8b or 16b immediate) automatically, but programmer has to specify which one he wants to use. (or use multi-pass assembler, which will try rel8 first, when failed, it will recode the jmp with rel16 and move+recompile everything beyond that point).

Looking at the example source of your push encoding I feel like there's some work for you to change the way your assembler works... (it's ugly anyway, like both creating opcodes and also printing output on screen - don't hesitate to write it one more time, I bet it will turn out more clean and simpler).

---

edit: finally, I probably understand that piece of assembler better.

So program is uint16_t[], right? (should have been part of question).

And the instruction machine codes are fixed size, 16b too.

But then your counter counts in 16b words... so is that the addressing mode of the target architecture?

That at address 0 is stored 16b word, and on address 1 is stored the next 16b word? (and it's not overlapping, as at x86, where addresses are counted in 8b bytes => in such case first instruction word would be at addresses 0 and 1 and second word would be at addresses 2 and 3. Make sure your counter follows correct addressing scheme (or you will have to convert it when defining value of label symbols).

And your asm is producing output like 0x0000 0x7802: address 0, word 7802, doing some instruction 78 with params 2 (unclear endianness! Either you will be lucky to have the same one on compiling host, or you will end with wrong machine code with swapped bytes in each word), next opcode 0x0001 0x7803, ... etc...

So it looks like you have fixed 16b size for instruction encoding, not sure if jmp will eat whole 8b like store/load instructions, or that one is special, keeping more bits for immediate encoding. If only other byte is available, only meaningful way to use it is as signed 8b -128..+127 relative jump.

If addressing works with 16b words, then you can effectively jump -128..+127 instructions back/forward. If addressing works with 8b bytes, your range is down to -64..+63 instructions only. Hard to tell, as I didn't figure out any details about target platform (you should have added some link or something, at least example how jmp is encoded and how memory is mapped).