Recently, I had an application that needed a LIFO rather than a FIFO. Where FIFO stands for “first in first out”, LIFO stands for “”last in first out”. LIFOs are not as common as FIFOs but, they are used whenever you need to remember something you are currently working on and start on something new. When the new thing is done, you can go back to what it was you were doing before you were interrupted. Due to the sequential nature of software, LIFOs are used a lot in processors as parameter or return “stacks”, and the write operation is called a “push” and the read operation is a “pop”.

A simple implementation

At first blush, implementing a LIFO should be pretty much the same as implementing a FIFO. You have a read pointer and a write pointer and a dual port RAM. Here is a LIFO figure with two entries:

A LIFO with two entries.

You can see that we will read from Location 2 if necessary, and we will write to Location 3. However, unlike a FIFO, a pop operation will affect the write pointer, and worse yet, it will affect the write pointer before the write takes place. In this example, if we were to perform a pop and push operation simultaneously, then we would need to write to Location 2 after doing the read. Afterwards, the read and write pointers would have the same values as before.

Digging deeper

One other thing to think about is that it seems wasteful to use a dual port RAM here. We could use a single port RAM if it weren’t for the pesky case of simultaneous pushes and pops. However, when we do a simultaneous push and pop, the pointers don’t change. We only read and write the location pointed to by the read pointer, taking care to do the read operation before the write operation. Also, if you think about it, we don’t even need two pointers. The pointers always need to move in lock step with each other. The write pointer is always the read pointer if you are pushing and popping, and the read pointer plus one if you are just pushing.

A better approach

The “aha!” moment comes when you realize that the critical memory location is the top of the stack. We need to read and write to this location if we are pushing and popping at the same time. Otherwise, we’re only going to need to read or write the RAM, and never both. If we keep the top of the stack in a register instead of the RAM, then we can do a simultaneous push and pop without using the memory at all. If we do just a push, then we need to write the top of the stack register to the RAM and store the pushed value in the top of the stack register. For a pop without a push, we just need to read the RAM and store the result in the top of the stack register, while simultaneously providing the current top-of-stack register value as the pop result. The figure below shows a stack with two entries using a top of stack register:

A stack with two entries using a top of stack register

The code

Ports for the LIFO are the usual clock and reset. We have status outputs empty and full, as well as a count of the number of data items in the LIFO. In addition, we have a signal indicating a push with its associated data, and another indicating a pop. A top-of-stack value rounds out the ports. Just a note, you can use the top-of-stack value all you want without popping the stack.

`timescale 1ns/1ns
module lifo
  #(
    parameter depth = 32,
    parameter width = 32,
    parameter log2_depth = log2(depth),
    parameter log2_depthp1 = log2(depth+1)
    )
  (
   input clk,
   input reset,
   output reg empty,
   output reg full,
   output reg [log2_depthp1-1:0] count,
   input push,
   input [width-1:0] push_data,
   input pop,
   output [width-1:0] tos
   );

You can read my other posts about the synchronous FIFO or constant functions to find out more about the log2 parameters. Here’s the log2 function for completeness, though:

   function integer log2;
      input [31:0] value;
      begin
	 value = value-1;
	 for (log2=0; value>0; log2=log2+1)
	   value = value>>1;
      end
   endfunction

Next, we’re going to use a flag to tell us when we’re writing. That is, when we are asked to push and we have room for the data. This means that either we are not full, or if we are full, we are also popping. Reading is similar, but a little simpler. We read if we’re asked to pop and there is data available.

  wire writing = push && (count < depth || pop);
  wire reading = pop && count > 0;

Now we count the data. We compute a combinational next_count value because that allows us to register the empty and full outputs. The logic is really quite simple. The count goes up when we write and don’t read, and it goes down if we read and don’t write. Otherwise, it just stays the same.

  reg [log2_depthp1-1:0] next_count;
  always @(*)
    if (reset)
      next_count = 0;
    else if (writing && !reading)
      next_count = count+1;
    else if (reading && !writing)
      next_count = count-1;
    else
      next_count = count;

  always @(posedge clk)
    count <= next_count;

Full and empty are pretty self explanatory:

  always @(posedge clk)
    full <= next_count == depth;

  always @(posedge clk)
    empty <= next_count == 0;

For the memory pointer, if we are writing, then we use the location pointed to by the count, and if we are reading, we use the location one before.

  wire [log2_depth-1:0] ptr = writing ? count [log2_depth-1:0] : (count [log2_depth-1:0])-1;

Writing to the memory is simple enough. If we are writing and not reading, we write the current top-of-stack into the RAM. The top-of-stack will be replaced with what we are pushing onto the stack. If we are writing and reading, we don’t want to write anything. The top of stack register will do all the work in this case.

  reg [width-1:0] mem [depth-1:0];

  always @(posedge clk)
    if (writing && !reading)
      mem[ptr] <= tos;

Reading is a little more tricky. It would be great if we could just say

 always @(posedge clk)
   if (reading && !writing)
     tos <= mem[ptr];
   else if (writing)
     tos <= push_data;

However, this won’t work. You can’t map that into the read output register of a BRAM. Synthesis tools aren’t smart enough to map part of this onto the RAM and the rest onto outside logic. We’re going to have to give it a little hint. First we can just use a simple register that can map onto the read output register:

  reg [width-1:0] mem_rd;
  always @(posedge clk)
    if (reading)
      mem_rd <= mem[ptr];

Now, we’ll create a top-of-stack “shadow” register. This will hold the value being written to the top of the stack, since we can’t store it in the RAM output register. Only the RAM can do that.

  reg [width-1:0] tos_shadow;
  always @(posedge clk)
    if (writing)
      tos_shadow <= push_data;

Finally, we need a MUX to select who really holds the top-of-stack value.

  reg use_mem_rd;
  always @(posedge clk)
    if (reset)
      use_mem_rd <= 0;
    else if (writing)
      use_mem_rd <= 0;
    else if (reading)
      use_mem_rd <= 1;

  assign tos = use_mem_rd ? mem_rd : tos_shadow;

Wrapup

With this design, you’re going to get an efficient LIFO using a single port RAM. Why is it important to do this in a single port? I’ll answer that question in a future post. For now, you can download the entire LIFO module here.