Skip to content

Bird: In Logisim

Bird adds four instructions to the basic Reptile design: push, pop, call and return. All these instructions use stack.

Review of Stack Operations

For stack operations we need a specific register called stack pointer(SP). Stack pointer always points to the empty location at the top of the stack. When the CPU is initialized, we have to also initialize the SP. The programmer has the freedom to place the stack anywhere in the memory.

  • When data is pushed into the stack, the contents of the source register is written to the memory address pointed by the SP. Then SP is decremented by 1.
  • When data is popped from the stack, SP is incremented by 1. Then the content of the memory location pointed by SP is read into the destination register.

Normally we would like to do ALU operations on SP. Hence we designate register 7 of the RegBank  as the SP of Bird.  We will add two new control signals, SP++ and SP–, to the RegBank. SP++ is used when we pop data from the stack and SP– is used when we push data into stack.

(new RegBank to be drawn here)

Bird Instruction Formats

Old Reptile instructions like Add, Inc, Ld, etc. has the same format in Bird. Therefore we will only explain the format of the new instructions.

PUSH Instruction
Assembly format: Push r
Writes the contents of the register r into the memory location pointed by the  SP. Then decrements SP by one.
Machine code format:

POP Instruction
Assembly format: Pop r
Pop increments SP by 1, then transfers the content of the memory location pointed by SP into register r.
Machine code format:

CALL Instruction
Assembly format: Call x
Pushes the content of the Program Counter (PC) into the stack and jumps to memory address PC+x, i.e, loads the number PC+x into PC. (PC<=PC+x). Recall that PC is already incremented when we start to execute the Call instruction.
Machine code format:

RET Instruction
Assemby format: Ret
Pops the top of the stack into PC.
Machine code format:

Bird FSM

Bird adds 6 new states to the FSM.

Note that as a novelty we now have instructions which take 3 clock cycles:

  • Pop instruction takes 3 clock cycles / 3 states: FETCH, POP1, POP2.
  • Ret instruction takes 3 clock cycles / 3 states: FETCH, RET1, RET2.

All the other instructions take 2 clock cycles / 2 states like in Reptile.

The new instructions work in the usual way. After FETCH state;

  • If the instruction is Push (OPCODE=0x8) control unit jumps to PUSH state. PUSH state pushes the contents of register r into stack and decrements SP. Then in the next clock cycle Control returns to FETCH state.
  • If the instruction is Pop (OPCODE=0x9)  control unit executes in sequence;
    • POP1 state: which increments SP.
    • POP2 state: copy the content of the memory location pointed by SP into register r.
      Then in the next clock cycle Control returns to FETCH state.
  • If the instruction is Call (OPCODE=0xA) control unit Jumps to CALL state. CALL state copies the content of PC into the stack(at this point, PC contains the address of next instruction to be executed), and, at the same time loads PC+IR into PC and decrements SP. Then in the next clock cycle Control returns to FETCH state.
  • If the instruction is Ret (OPCODE=0xB) control unit executes in sequence;
    • RET1 state: Increments SP.
    • RET2 state: Copy the content pointed by SP into PC
      Then in the next clock cycle Control returns to FETCH state.

(Contents of IR is to be explained)

Hardware Implementation of the new Bird States

Recall that Bird adds 6 new states to the FSM. Some of these new states cannot be realized in Reptile Hardware, as many of the required hardware connections do not exist. Below, we will add all the required connections for all these new states one by one to the Reptile Hardware.

First step in implementing Bird is to define a stack pointer. For this purpose, we reserve the 7th register of the RegBank as the stack pointer. From this point on, we will not use RegBank[7] for any other purpose.

PUSH:

To push a register to stack, we have to send the SP’s contents to memory as address. For this, we have added the green lines to the hardware figure given below. In addition, we have to be able to decrement the contents of SP. To do this, RegBank[7] must be changed to a register with increment/decrement (See Chapter 2). Two control signals, SP++ and SP–, are added to RegBank.

  • When SP++ becomes 1, RegBank[7] will be incremented in the next clock edge.
  • When SP– becomes 1, RegBank[7] will be decremented in the next clock edge.

Push added hardware design

POP1:

No new control signal is needed.

POP2:

No new control signal is needed.

CALL:

Call added hardware design

RET1:

 

RET2:

Ret2 added Hardware design 

Final hardware design

Bird Control Unit

 

Let us start by writing the necessary control signals as we derived above back in to the FSM.

Bird Microcode

Hardware Design of Bird’s Control Unit

Bird With Control Unit

Now we can convert this FSM into a tabular form where each state corresponds to a line, as we have done in Reptile. But there is a difference with Reptile: In Reptile, all states return back to FETCH as soon as they execute. In Bird, they can go to a following state. An example of this is POP1 state, which doesn’t return to FETCH after execution but goes to POP2. To keep track of this we add a NEXT STATE field to each state which will keep the line number of the next state to execute. Note that as in Reptile the line numbers correspond to opcodes of the instructions.

A second difference with Reptile is that there are 4 new control signals (DATAMUX, SP++, SP–, PCMUX) and the ARMUX signal is now  2-bits rather than 1. This means that the data bus width of our Control Unit ROM will be 18-bits.