J1 Forth CPU 研究之四：資料堆疊和返回堆疊

這是一系列文章中的第四篇，這系列的文章是要解讀 J1 CPU 的設計以及在其上的 Forth 語言的使用法。

這篇談的是 j1 CPU 的 Verilog 程式中和資料堆疊 (Data Stack) 和返回堆疊 (Return Stack) 有關的部份，請見以下檔案：

src/hardware/verilog/j1.v

一般的 CPU 在設計上只有一個堆疊，這個堆疊在副程式呼叫時有三個功能：

1. 存放副程式的的參數 (parameters)。
2. 存放副程式的返回位址。
3. 存放區域變數 (local variables)。

當副程式有回傳值時，這值會被放在一個特定的暫存器中，大多數的程式語言的副程式最多只有一個回傳值，理由在此。

Forth CPU 和的一般 CPU 在設計上有個不同之處： Forth CPU 有兩個堆疊，回傳的資料不放暫存器，而是放在堆疊上。因此可以回傳多值。這兩個堆疊的名稱及功能是：

1. 資料堆疊 (Data Stack)：存放副程式的的參數 (parameters) 以及副程式產生的資料。
2. 返回堆疊 (Return Stack)： 存放副程式的返回位址。有時會在副程式計算過程中用來暫時保存資料堆疊上的資料。

某些 Forth 會使用第三個堆疊處理區域變數，但是許多 Forth 語言的愛好者摒棄區域變數這樣的概念。J1 Forth CPU 在設計上只有兩個堆疊。

資料堆疊最上面的資料常被稱為 T (Top)，在其下的資料常被稱為 N (Next)。由於 ALU 的計算大量使用 T 和 N，許多 Forth CPU 或是 Forth virtual machine 的設計中，T 會被設計成暫存器，以加快 ALU 的計算速度。當要使用 T 時，直接讀取對應的暫存器，當要使用 N 時，讀取資料堆疊的堆疊指標指向的堆疊頂端。這使得 T 和 N 可以同時被讀取。在這樣的設計下，雖然 T 是寫 Forth 程式時的資料堆疊頂，但是以 Verilog 實作時，N 才是實作的資料堆疊的疊頂。因此要實現 Forth 程式中將數值資料推上資料堆疊的行為時，除了寫資料到 T 中，還必須把 T 中的資料推上堆疊(也就是機器碼編譯中的 T->N)。因為 Verilog 平行處理的特性，這兩個行為可以同時發生。

要注意，和資料堆疊不同，返回堆疊最上面的資料並未放在一個獨立的暫存器中，這使得將數值推上資料堆疊與推上返回堆疊的程式略有不同。以下是 Verilog 的宣告：

  reg [4:0] dsp;  // 資料堆疊指標，指向 N
  reg [4:0] _dsp;  // 下一時刻的資料堆疊指標
  reg [15:0] st0;  // T，存放 Forth 資料堆疊最頂端資料的暫存器
  reg [15:0] _st0; // 下一時刻的 T
  wire [15:0] st1; // N，Forth 資料堆疊中在 T 之下的資料，Verilog 中資料堆疊的疊頂。請參考以下程式中的 assign 敍述。
  wire _dstkW;     // D stack write

  reg [4:0] rsp; // 返回堆疊指標
  reg [4:0] _rsp; // 下一時刻的返回堆疊指標
  wire [15:0] rst0; // 返回堆疊的疊頂，請見以下程式中的 assign 敍述。
  reg _rstkW;     // R stack write
  reg [15:0] _rstkD; // 要寫入返回堆疊的資料

  reg [15:0] dstack[0:31]; // 資料堆疊，深度為 32，加上 st0，深度為 33
  reg [15:0] rstack[0:31]; // 返回堆疊，深度為 32

以下程式處理寫入堆疊的動作。在 sys_clk_i 的上升緣，如果資料堆疊寫入訊號 _dstkW 為真，則執行 T->N 的行為，把 st0 的資料寫入 dstack[_dsp]。_dsp 為下一時刻的資料堆疊指標。所以是未來的 N 的位置。同樣的，如果返回堆疊寫入訊號 _rstkW 為真，則把 _rstkD 的內容寫到返回堆疊中 _rsp 指到的位置。_rsp 為下一時刻的返回堆疊指標。
  always @(posedge sys_clk_i)  begin
    if (_dstkW)
      dstack[_dsp] = st0;
    if (_rstkW)
      rstack[_rsp] = _rstkD;
  end
  assign st1 = dstack[dsp];
  assign rst0 = rstack[rsp];

以下程式決定寫入訊號 _dstkW、_rstkW，及下一刻堆疊指標 _dsp, _rsp 的值。請參考機器碼的編碼：

其中，要寫入資料堆疊的時機(_diskW為真)是當機器碼最高位元為 1，也就是 literal 時，或是機器碼為 ALU，且第 7 位元為 1 (也就是 T->N) 時。此時都要做 T->N 的動作。

  assign _dstkW = is_lit | (is_alu & insn[7]);

以下資料決定執行 ALU 後資料堆疊和返回堆疊指標增減的量。
  wire [1:0] dd = insn[1:0];  // D stack delta
  wire [1:0] rd = insn[3:2];  // R stack delta

  always @*
  begin
    if (is_lit) begin                       // 如果是 literal，數值資料
      _dsp = dsp + 1;                  // 此時因要推資料上資料堆疊，資料堆疊指標加 1
      _rsp = rsp;                          // 返回堆疊指標不變。
      _rstkW = 0;                         // 不寫入返回堆疊
      _rstkD = _pc;                      // 因為不寫入，這行其實沒有作用。
    end else if (is_alu) begin        // 如果是 ALU 運算
      _dsp = dsp + {dd[1], dd[1], dd[1], dd};   // 依 dd 增減資料堆疊指標
      _rsp = rsp + {rd[1], rd[1], rd[1], rd};        // 依 rd 增減返回堆疊指標
      _rstkW = insn[6];                                  // 由 T->R 欄位決定要不要寫入返回堆疊
      _rstkD = st0;                                        // 如果要寫入，被寫入的資料是 T
    end else begin                      // 如果是 jump/call
      // predicated jump is like DROP
      if (insn[15:13] == 3'b001) begin    // 如果是 conditional jump，拋棄堆疊上用來做判斷的資料，因此堆疊指標減一。
        _dsp = dsp - 1;
      end else begin                              // 如果只是單純的 jump，維持原來的堆疊指標。
        _dsp = dsp;
      end
      if (insn[15:13] == 3'b010) begin    // 如果是 call，呼叫副程式
        _rsp = rsp + 1;                            // 此時把 program counter + 1 堆上返回堆疊。
        _rstkW = 1;                                 // 因此要寫入返回堆疊。
        _rstkD = {pc_plus_1[14:0], 1'b0}; // 實際上推入的值必須乘以二，轉成 byte 位址。
                                                         // 轉成 byte 位址的理由在未來討論 Xilinx 的內部 RAM 時說明。
      end else begin                    // 當以上皆非
        _rsp = rsp;                        // 不改變返回堆疊
        _rstkW = 0;
        _rstkD = _pc;
      end
    end
  end

以上總共 60 行，加上第三篇的 30 行，我們已經看懂了 j1.v 的 90/200，接近一半的程式了。