Beginning Logic Design – Part 14

Hello and welcome to Part 14 of my Beginning Logic Design series! In the last episode, I added my ALU operations. For this round, I want to add implement some operators for manipulating a stack and some handling for calling subroutines. Let’s jump to it!

My Stack System

The stack pointer of my cpu will keep track of the “top” of the stack. Most CPUs have a stack that grows “down”, but my CPU already has a lot of inefficiencies and I’m feeling rebellious so my stack will grow up! I current reset the stack to 0 on reset, so at the start of a program it should be ready to go.

I’ll use the first few available opcodes from my EXTRA operation family for my stack related functions.

  1. F0: push A
  2. F1: push B
  3. F2: push C
  4. F3: pop A
  5. F4: pop B
  6. F5: pop C
F0: push A
F1: push B
F2: push C
F3: pop A
F4: pop B
F5: pop C

As before I’ll start by roughly mocking out this organization in my PERFORM state

  1. EXTRA: begin
  2. case (instruction[3:0])
  3. // Push A
  4. 0: begin
  6. end
  7. // Push B
  8. 1: begin
  10. end
  11. // Push C
  12. 2: begin
  14. end
  15. // Pop A
  16. 3: begin
  18. end
  19. // Pop B
  20. 4: begin
  22. end
  23. // Pop C
  24. 5: begin
  26. end
  27. endcase
  28. end
EXTRA: begin
  case (instruction[3:0])
    // Push A
    0: begin
      
    end
    // Push B
    1: begin
      
    end
    // Push C
    2: begin
      
    end
    // Pop A
    3: begin
      
    end
    // Pop B
    4: begin
      
    end
    // Pop C
    5: begin
      
    end
  endcase
end

Now I’ll start on the PUSH A operations. I’ll need to write A to the memory address my stack pointer is currently set to, then increment the stack pointer. Since this involves some bus interactions it’ll take two cycles.

On the first I’ll put the A register value in the write_data register, set the address_bus to my stack pointer and enable write.

For the second cycle, I’ll clear my write signal, increment my stack and return to FETCH to continue my program, easy as that!

  1. 0: begin
  2. case (cycle)
  3. 0: begin
  4. write_data <= a;
  5. address_bus <= stack;
  6. write <= 1;
  7. end
  8. 1: begin
  9. write <= 0;
  10. stack++;
  11. state <= FETCH;
  12. program_counter++;
  13. end
  14. endcase
  15. end
0: begin
  case (cycle)
    0: begin
      write_data <= a;
      address_bus <= stack;
      write <= 1;
    end
    1: begin
      write <= 0;
      stack++;
      state <= FETCH;
      program_counter++;
    end
  endcase
end

And by the magic of copy-pasta, I extend this to my other two registers.

  1. // Push B
  2. 1: begin
  3. case (cycle)
  4. 0: begin
  5. write_data <= b;
  6. address_bus <= stack;
  7. write <= 1;
  8. end
  9. 1: begin
  10. write <= 0;
  11. stack++;
  12. state <= FETCH;
  13. program_counter++;
  14. end
  15. endcase
  16. end
  17. // Push C
  18. 2: begin
  19. case (cycle)
  20. 0: begin
  21. write_data <= c;
  22. address_bus <= stack;
  23. write <= 1;
  24. end
  25. 1: begin
  26. write <= 0;
  27. stack++;
  28. state <= FETCH;
  29. program_counter++;
  30. end
  31. endcase
  32. end
// Push B
1: begin
  case (cycle)
    0: begin
      write_data <= b;
      address_bus <= stack;
      write <= 1;
    end
    1: begin
      write <= 0;
      stack++;
      state <= FETCH;
      program_counter++;
    end
  endcase
end
// Push C
2: begin
  case (cycle)
    0: begin
      write_data <= c;
      address_bus <= stack;
      write <= 1;
    end
    1: begin
      write <= 0;
      stack++;
      state <= FETCH;
      program_counter++;
    end
  endcase
end

Now for the inverse operation POP. This means performing a read with the decremented stack pointer and storing that into the desired register, which will also be two cycles. On the first I’ll predecrement stack as I set the address_bus to it. On the second I’ll clear my read, store the returned value and go back into FETCH.

  1. // Pop A
  2. 3: begin
  3. case (cycle)
  4. 0: begin
  5. address_bus <= --stack;
  6. read <= 1;
  7. end
  8. 1: begin
  9. read <= 0;
  10. a <= data_bus;
  11. state <= FETCH;
  12. program_counter++;
  13. end
  14. endcase
  15. end
// Pop A
3: begin
  case (cycle)
    0: begin
      address_bus <= --stack;
      read <= 1;
    end
    1: begin
      read <= 0;
      a <= data_bus;
      state <= FETCH;
      program_counter++;
    end
  endcase
end

I honestly didn’t think implementing push and pop would be quite so easy, everything was working well on the first attempt.  As before I’ll copy my way through to implement this for B and C.

  1. // Pop B
  2. 4: begin
  3. case (cycle)
  4. 0: begin
  5. address_bus <= --stack;
  6. read <= 1;
  7. end
  8. 1: begin
  9. read <= 0;
  10. b <= data_bus;
  11. state <= FETCH;
  12. program_counter++;
  13. end
  14. endcase
  15. end
  16. // Pop C
  17. 5: begin
  18. case (cycle)
  19. 0: begin
  20. address_bus <= --stack;
  21. read <= 1;
  22. end
  23. 1: begin
  24. read <= 0;
  25. c <= data_bus;
  26. state <= FETCH;
  27. program_counter++;
  28. end
  29. endcase
  30. end
// Pop B
4: begin
  case (cycle)
    0: begin
      address_bus <= --stack;
      read <= 1;
    end
    1: begin
      read <= 0;
      b <= data_bus;
      state <= FETCH;
      program_counter++;
    end
  endcase
end
// Pop C
5: begin
  case (cycle)
    0: begin
      address_bus <= --stack;
      read <= 1;
    end
    1: begin
      read <= 0;
      c <= data_bus;
      state <= FETCH;
      program_counter++;
    end
  endcase
end



Subroutines

The next two instructions I want to implement are an operation that jumps into a subroutine and a paired operator that returns from that subroutine. I’ll try to keep these operations pretty simple. I’ll first stub out my opcodes.

  1. // Jump subroutine
  2. 6: begin
  3. case (cycle)
  5. endcase
  6. end
  7. // Return from subroutine
  8. 7: begin
  9. case (cycle)
  11. endcase
  12. end
// Jump subroutine
6: begin
  case (cycle)
    
  endcase
end
// Return from subroutine
7: begin
  case (cycle)
    
  endcase
end

For my JSR operation (jump to subroutine), I’ll first push my next instruction address to the top of my stack, then jump the program to the next address. This will take 4 total bus interactions so my current 2-bit cycle variable will not allow for this, I’ll modify my cycle to 3-bits so it can count to 8 and start implementing.

Pretty quickly intro drafting my implementation of this, and right after gloating how easy push/pop was to implement, I noticed this one was going to be a bit trickier! The first thing I need to do is calculate the address of the next instruction and push the most significant byte to the stack.

  1. 0: begin
  2. write <= 1;
  3. address_bus <= stack;
  4. program_counter += 3;
  5. write_data <= program_counter[15:8];
  6. end
0: begin
  write <= 1;
  address_bus <= stack;
  program_counter += 3;
  write_data <= program_counter[15:8];
end

On the next cycle, I complete the return address right by setting the next stack byte to the least significant byte.

  1. 1: begin
  2. address_bus <= stack + 1;
  3. write_data <= program_counter[7:0];
  4. end
1: begin
  address_bus <= stack + 1;
  write_data <= program_counter[7:0];
end

With the pointer written to the stack, I’ll begin reading the next pointer to jump to and increment my stack by the length of the pointer (2 bytes). Since my program counter is now ahead of the pointer to jump to, I need to look back 2 bytes for the most significant byte of the subroutine’s address.

  1. 2: begin
  2. write <= 0;
  3. read <= 1;
  4. address_bus <= program_counter - 2;
  5. stack += 2;
  6. end
2: begin
  write <= 0;
  read <= 1;
  address_bus <= program_counter - 2;
  stack += 2;
end

I’ll store the returned most signifcant byte for the subroutine in my x register and request the next byte.

  1. 3: begin
  2. x <= data_bus;
  3. address_bus <= program_counter - 1;
  4. end
3: begin
  x <= data_bus;
  address_bus <= program_counter - 1;
end

Then finally I’ll be done with the bus and can jump into the subroutine.

  1. 4: begin
  2. read <= 0;
  3. program_counter <= {x, data_bus};
  4. state <= FETCH;
  5. end
4: begin
  read <= 0;
  program_counter <= {x, data_bus};
  state <= FETCH;
end

Phew! I had a few issues with implementing this at first, primarily from not managing my pointers properly. With time, patience and debugging in the simulator it did eventually work out.

The ReTurn from Subroutine (RTS) thankfully is a bit easier, and will only take three cycles. First I’ll begin the read for the least significant byte of where to jump back to.

  1. 0: begin
  2. read <= 1;
  3. address_bus <= --stack;
  4. end
0: begin
  read <= 1;
  address_bus <= --stack;
end

On the second cycle, I’ll store that byte in x and read the most significant byte of the return pointer.

  1. 1: begin
  2. address_bus <= --stack;
  3. x <= data_bus;
  4. end
1: begin
  address_bus <= --stack;
  x <= data_bus;
end

On the last cycle we can stop the read and jump to the return pointer!

  1. 2: begin
  2. read <= 0;
  3. program_counter <= {data_bus, x};
  4. state <= FETCH;
  5. end
2: begin
  read <= 0;
  program_counter <= {data_bus, x};
  state <= FETCH;
end

That’ll do it! I’ll use this program to test it, annotated with addresses and comments for brevity:

  1. 8000: c0 de ; Set A = 0xDE
  2. 8002: f0 ; Push A to stack
  3. 8003: f6 80 07 ; Jump into subroutine at 0x8007
  4. 8006: e0 ; Halt machine
  5. 8007: c1 20 ; Set B = 0x20
  6. 8009: c2 17 ; Set C = 0x12
  7. 800b: f7 ; Return
8000: c0 de     ; Set A = 0xDE
8002: f0        ; Push A to stack
8003: f6 80 07  ; Jump into subroutine at 0x8007
8006: e0        ; Halt machine
8007: c1 20     ; Set B = 0x20
8009: c2 17     ; Set C = 0x12
800b: f7        ; Return

In simulation it works like a charm!

With that working I am done with the initial set of goals I had for this CPU, and this series along with that! I hope some folks have found this series interesting and/or useful. If you have any improvements to suggest or would like me to cover the implementation of any of this in further detail please leave a note in the comments. Keep tinkering!!

Leave a Reply