Verilog Stack or LIFO

A stack, or LIFO (last in, first out), is a memory structure in which the most recently stored item is the first one removed. In Verilog, a stack is built from a register array and a single stack pointer: a push writes at the pointer and increments it, and a pop decrements it and returns the item on top.

12 min read | Intermediate Level

What You'll Learn

• How push and pop work, and how a LIFO differs from a FIFO
• Write a parameterized stack with a stack pointer and full and empty flags
• Why the pointer needs one more bit than the address, and what the read logic synthesizes into
• Test the stack with random push and pop operations

What is a stack or LIFO ?

LIFO is a way of organizing data, used in both digital design and software, in which the item added last is the first one taken out. A stack of plates works the same way: you place new plates on top, and you always take the top plate first.

A FIFO is the opposite: it returns items in the order they were written. A FIFO needs two pointers, one for each end of the queue, while a stack only ever works at one end, its top, so it needs just one pointer.

How does it work ?

A stack supports two operations:

• Push adds an item on top of the stack.
• Pop removes the item on top and returns it.

The most recently pushed item is always on top. In hardware, a stack pointer holds the index of the next free entry, which is also the number of items stored. A push writes at stack[stack_ptr] and increments the pointer; a pop decrements it, so the top item is always at stack[stack_ptr - 1].

A popped entry is not cleared; it is simply above the pointer and will be overwritten by the next push, as C is overwritten by D in the table.

Where is a stack mostly used ?

Stacks appear in memory management and program execution, and most commonly in function calls. When a program calls a function, the return address and parameters are pushed onto the stack. When the function returns, they are popped off, so execution continues where it left off. Because nested calls return in the reverse order they were made, a stack is exactly the right structure.

What are the advantages of LIFO ?

• Simple implementation: one memory array and one pointer, with no wrap-around logic
• Constant-time operations: push and pop each take one step, O(1), regardless of how full the stack is
• Natural fit for nested or recent data: whenever the most recent item must be handled first, such as nested calls, nested interrupts or undo history

Verilog Stack Example

module lifo #(parameter WIDTH = 32, parameter DEPTH = 16)(
    input wire              clk,
    input wire              rst,          // Active-high asynchronous reset
    input wire              push,
    input wire              pop,
    input wire [WIDTH-1:0]  data_in,
    output reg [WIDTH-1:0]  data_out,
    output reg              empty,
    output reg              full
);

    reg [WIDTH-1:0]        stack [0:DEPTH-1];
    reg [$clog2(DEPTH):0]  stack_ptr;      // 0 to DEPTH: one bit wider than an address

    always @(posedge clk or posedge rst) begin
        if (rst) begin
            stack_ptr <= 0;
            empty <= 1;
            full <= 0;

        end else begin
            if (push && !full) begin                 // Push has priority over pop
                stack[stack_ptr] <= data_in;         // Write at the next free entry
                stack_ptr        <= stack_ptr + 1;
                empty            <= 0;

                if (stack_ptr == DEPTH - 1) begin    // This push fills the last entry
                    full <= 1;
                end

            end else if (pop && !empty) begin
                stack_ptr <= stack_ptr - 1;          // Remove the top entry
                full      <= 0;

                if (stack_ptr == 1) begin            // This pop removes the last entry
                    empty <= 1;
                end
            end
        end
    end

    // The top entry is visible on data_out during the cycle in which pop is requested
    always @(*) begin
      if (!empty & pop)
            data_out = stack[stack_ptr - 1];
        else
            data_out = {WIDTH{1'b0}};
    end

endmodule

Pushes are ignored while the stack is full, and pops are ignored while it is empty, so a value pushed onto a full stack is lost. If push and pop are both 1 in the same cycle, the push is performed and the pop is ignored.

The full and empty flags are registers updated together with the pointer. They are set when a push fills the last entry or a pop removes the last item, so they are valid in the cycle right after that operation.

Synthesis result: The tool builds the pointer as a $clog2(DEPTH)+1-bit up/down counter, two flag flip-flops, comparators on the pointer, and the storage array. Because data_out reads the array combinationally, the array cannot be mapped to a block RAM, which only supports registered reads. For small stacks this is fine: the entries become flip-flops or distributed LUT RAM, and the top entry is selected by a mux driven by stack_ptr - 1.

Testbench

The testbench uses a 4-entry stack of 16-bit words so that it fills up quickly. After reset, it runs 20 clock cycles, choosing push or pop at random on each one, and prints the operation and flags each cycle.

module lifo_tb;

    // Parameters for the LIFO
    parameter WIDTH = 16;
    parameter DEPTH = 4; // Set a smaller depth for testing

    // Testbench signals
    reg clk;
    reg rst;
    reg push;
    reg pop;
    reg [WIDTH-1:0] data_in;
    wire [WIDTH-1:0] data_out;
    wire empty;
    wire full;
    integer i;

    // Instantiate the LIFO module
    lifo #(
        .WIDTH(WIDTH),
        .DEPTH(DEPTH)
    ) uut (
        .clk(clk),
        .rst(rst),
        .push(push),
        .pop(pop),
        .data_in(data_in),
        .data_out(data_out),
        .empty(empty),
        .full(full)
    );

    // Clock generation
    initial begin
        clk = 0;
        forever #5 clk = ~clk; // 10 ns clock period
    end

    // Test sequence
    initial begin
        // Initialize signals
        rst <= 1;
        push <= 0;
        pop <= 0;
        data_in <= 0;

        $display("Pushing values onto the stack:");

        // Wait for a few clock cycles
        #10;

        // Release reset
        rst <= 0;

      for (i = 0; i < 20; i = i + 1) begin
            @(posedge clk);
        	if ($random % 2) begin             // Randomly choose push or pop
        		push <= $random;               // Bit 0 of a random number
              	pop <= 0;
              	data_in <= $random;
            end else begin
        		pop  <= $random;
              	push <= 0;
            end

        $display("[%0t] Operation push=%0d pop=%0d data_in=0x%0h empty=%0b full=%0b", $time, push, pop, data_in, empty, full);
        end

        #100;
        $finish;
    end
endmodule

The $display runs in the same time step as the non-blocking assignments, before they take effect. Each line therefore shows the operation that was presented at that clock edge, together with the flags as they were just before it.

Simulation

Push and pop requests add data to and remove data from the stack. Any data pushed while the stack is full is lost.

xcelium> run
Pushing values onto the stack:
[15000] Operation push=0 pop=0 data_in=0x0 empty=1 full=0
[25000] Operation push=0 pop=1 data_in=0x0 empty=1 full=0
[35000] Operation push=1 pop=0 data_in=0x7b0d empty=1 full=0
[45000] Operation push=1 pop=0 data_in=0x5212 empty=0 full=0
[55000] Operation push=1 pop=0 data_in=0xf176 empty=0 full=0
[65000] Operation push=1 pop=0 data_in=0xf78c empty=0 full=0
[75000] Operation push=0 pop=0 data_in=0x84c5 empty=0 full=1
[85000] Operation push=0 pop=1 data_in=0x84c5 empty=0 full=1
[95000] Operation push=0 pop=0 data_in=0xdb8f empty=0 full=0
[105000] Operation push=0 pop=0 data_in=0xdb8f empty=0 full=0
[115000] Operation push=0 pop=1 data_in=0xdb8f empty=0 full=0
[125000] Operation push=0 pop=1 data_in=0xdb8f empty=0 full=0
[135000] Operation push=1 pop=0 data_in=0x6263 empty=0 full=0
[145000] Operation push=0 pop=0 data_in=0x6263 empty=0 full=0
[155000] Operation push=0 pop=0 data_in=0x6263 empty=0 full=0
[165000] Operation push=0 pop=0 data_in=0xb813 empty=0 full=0
[175000] Operation push=1 pop=0 data_in=0xdd6b empty=0 full=0
[185000] Operation push=0 pop=0 data_in=0x3eae empty=0 full=0
[195000] Operation push=1 pop=0 data_in=0x4923 empty=0 full=0
[205000] Operation push=0 pop=0 data_in=0x4923 empty=0 full=1
Simulation complete via $finish(1) at time 305 NS + 0

The times are printed in picoseconds, so [15000] is 15 ns. Reading the log:

• Pop on an empty stack: at 25 ns a pop is requested while empty=1, so it is ignored.
• Filling the stack: four pushes in a row, of 0x7b0d, 0x5212, 0xf176 and 0xf78c, fill all four entries, and full is 1 from the 75 ns line onward.
• Leaving full: the pop at 85 ns removes 0xf78c, the last value pushed, and full is 0 again on the next line.
• Full again: after two more pops and three more pushes, the stack is full again by 205 ns.

Common Beginner Mistakes

always @(posedge clk or posedge rst) begin
    if (rst) begin
        stack_ptr <= 0;
        empty     <= 1;
        full      <= 0;
    end else begin
        if (push && pop && !empty) begin
            // Replace the top entry; pointer and flags do not change
            stack[stack_ptr - 1] <= data_in;

        end else if (push && !full) begin
            stack[stack_ptr] <= data_in;
            stack_ptr        <= stack_ptr + 1;
            empty            <= 0;
            if (stack_ptr == DEPTH - 1) full <= 1;

        end else if (pop && !empty) begin
            stack_ptr <= stack_ptr - 1;
            full      <= 0;
            if (stack_ptr == 1) empty <= 1;
        end
    end
end