ベクター配列によるリターンスタック

前稿までのリターンスタックrsはレジスタファイルで構成しましたが、別法のベクター配列を試してみます。 まずベクターをインポートします。

import Vector::*;

次に、リターンスタックrsを3段インスタンシエートします。

   // return stack
   Vector#(3, Reg#(State_t)) rs <- replicateM(mkRegU);

さらにマクロ命令定義を書き換えます。ベクター配列はrs[sp]として扱えるので、直感的に分かりやすいです。

`define call(SUB)          `_pushNext; state <= State_t {func:SUB, step:S0}
`define _pushNext          rs[sp] <= State_t {func:state.func, step:nextStep()}; sp <= sp + 1
`define return             state <= rs[sp-1]; sp <= sp - 1
`define next               state.step <= nextStep()

説明は表248.1と同一です。これを用いて、前稿の検証FSMを実行してみます。

$ bsc -sim -u TestFSM3.bsv
checking package dependencies
compiling TestFSM3.bsv
code generation for mkTestFSM starts
Elaborated module file created: mkTestFSM.ba
All packages are up to date.
$ bsc -sim -e mkTestFSM -o mkTestFSM
Bluesim object created: mkTestFSM.{h,o}
Bluesim object created: model_mkTestFSM.{h,o}
Simulation shared library created: mkTestFSM.so
Simulation executable created: mkTestFSM
$ ./mkTestFSM -m 15 -V dump.vcd | tee result
L1 S0
L1 S1
　L2 S0
　L2 S1
　L2 S2
　　L3 S0
　　L3 S1
　　　L4 S0
　　　L4 S1
　　L3 S2
　L2 S3
　L2 S4
L1 S2
L1 S2
$

正しく実行することが検証できました。波形を図249.1に示します。内部信号を見ると、rs_0, rs_1, rs_2という3個のレジスタインスタンスが生成されています。これが3段のリターンスタックを構成しています。

図249.1 検証用FSMのBsim波形(ベクター配列使用)

合成結果

Vivadoによる合成結果は21 LUTのサイズでした。レジスタファイルよりもベクター配列のほうが、わずかに小さくなることが分かりました。レジスタファイルは下位モジュールのレジスタファイルをインスタンスする必要がありますが、ベクター配列は上記のようにレジスタが展開されるだけです。従って、インタフェースが簡略化されるため、小さくなると考えられます。

---

前のブログ 次のブログ

マクロ命令定義

以上の議論から再定義したマクロ命令のコードです。

`define call(SUB)           `_pushNext; state <= State_t {func:SUB, step:S0}
`define _pushNext           rs.upd(sp, State_t {func:state.func, step:nextStep()}); sp <= sp + 1
`define pushCall(FUNC,SUB)  _pushFunc(FUNC); state <= State_t {func:SUB, step:S0}
`define _pushFunc(FUNC)     rs.upd(sp, State_t {func:FUNC, step:S0}); sp <= sp + 1
`define nextFunc            state <= State_t {func:nextFunc(), step:S0}
`define return              state <= rs.sub(sp-1); sp <= sp - 1
`define next                state.step <= nextStep()

今回、アプリ(インベーダサウンドFSM)の必要上pushCallを定義しています。これは、call命令の一般化であり、次ステートではなく任意のファンクションに戻るコールを実装するものです。以上のマクロ命令の説明を表248.1に示します。

表248.1　マクロ命令の説明

マクロ命令名	説明
call(SUB)	サブルーチンコールです。次ステートをプッシュして、サブルーチンSUBをコールします。
_pushNext	callに使用されており、次のステートをプッシュする内部マクロ命令です。nextStep()関数を使用しています。ユーザは陽に使う必要は無いため、先頭にアンダースコアを付けています。
pushCall(FUNC,SUB)	サブルーチンコールです。戻り先ファンクションFUNCをプッシュして、サブルーチンSUBをコールします。戻り先は指定されたファンクションFUNCの先頭S0となります。
_pushFunc(FUNC)	pushCallに使用されており、戻り先ファンクションFUNCをプッシュする内部マクロ命令です。ユーザは陽に使う必要は無いため、先頭にアンダースコアを付けています。
nextFunc	次のファンクションに進めるためのマクロ命令です。nextFunc()関数を使用しています。
return	呼び出し元(の次のステート)に戻るためのマクロ命令です。
next	次のステートに進めるためのマクロ命令です。nextStep()関数を使用しています。

合成結果

Vivadoによる合成結果は22 LUTのサイズでした。

---

前のブログ 次のブログ

リファクタリング(1)(プッシュとリターンの統合)

前稿でpushRetとcallをまとめるアイデアを記載しましたが、それを実装してみます。まとめたマクロ命令をpushCallと名付けます。

`define _pushRet          rs.upd(sp, ret); sp <= sp + 1
`define popRet            state <= rs.sub(sp-1); sp <= sp - 1
`define pushCall(SUB)     `_pushRet; `_saveNext; state <= State_t {func:SUB, step:S0}
`define _saveNext         ret <= State_t {func:state.func, step:nextStep()}
`define return            state <= ret

非リーフでのコールとリターンが完成したので動作確認を行います。非リーフでのcallをpushCallに、リターンはそのままpopRetとします。リーフではcallは無く、リターンはそのままreturnとします。

ソースコード内のpushRetを削除し、それぞれのcallをL1ルール内において、

             `pushCall(L2);

L2ルール内において、

             `pushCall(L3);

L3ルール内において、

             `pushCall(L4);

のように修正します。動作確認した結果、expectedと一致し正常動作が確認されました。

リファクタリング(2)(リーフと非リーフの共通化)

そもそもリターンレジスタのretがあるためリーフと非リーフの区別がありました。スタック操作はハードウエアであり、性能へのインパクトがほとんど無いことから、リーフ・非リーフで統一したやり方を考えます。それにはretレジスタを廃止します。従って、callとreturnは以下のようにリターンスタックのみで操作します。 retレジスタの削除の他、マクロの修正を次のように行います。

`define return           state <= rs.sub(sp-1); sp <= sp - 1
`define call(SUB)        `_pushNext; state <= State_t {func:SUB, step:S0}
`define _pushNext        rs.upd(sp, State_t {func:state.func, step:nextStep()}); sp <= sp + 1
`define next             state.step <= nextStep()

としました。これにより、サブルーチンコールの場合は常にcall()を用い、リターンの場合は常にreturnを用います。このように修正した結果、正常動作することを確認しました。ただし、returnレジスタを削除したため、rsはL1~L3で使用により3段、従ってspは2bitとなりました。

以上から、内部マクロを除くユーザーに見えるマクロは、call()、return、nextの3種となります。

---

前のブログ 次のブログ

コンパイルと実行

ソースプログラムをコンパイルします。

$ bsc -u -sim TestFSM.bsv
checking package dependencies
compiling TestFSM.bsv
code generation for mkTestFSM starts
Elaborated module file created: mkTestFSM.ba
All packages are up to date.

次にリンクします。

$ bsc -sim -e mkTestFSM -o mkTestFSM
Bluesim object created: mkTestFSM.{h,o}
Bluesim object created: model_mkTestFSM.{h,o}
Simulation shared library created: mkTestFSM.so
Simulation executable created: mkTestFSM

15サイクル実行します。

$  ./mkTestFSM -V dump.vcd -m 15 | tee result
L1 S0
L1 S1
　L2 S0
　L2 S1
　L2 S2
　　L3 S0
　　L3 S1
　　　L4 S0
　　　L4 S1
　　L3 S2
　L2 S3
　L2 S4
L1 S2
L1 S2

検証結果

結果を比較することにより検証します。

$ diff -c result expected

出力結果がサイクルベースで一致したことにより、正しく動作していることが検証されました。実は階層が4レベルあってもL1では戻り先が無いのでスタックを使いませんし、L4もリーフなのでスタックを使いません。従ってL2とL3だけでpush/popするため、スタックは2段(retを含めて3段)となり、spは1bitで良いことになります。これはたまたま前稿と同じ設計です。

このように変更し、上記のコンパイル、実行、一致検証まで実施したところ、期待した動作をすることが確認されました。rsが2段の場合のBsimの波形を図246.2に示します。spは1bitしかないので、sp==2の際にsp==0という不正な値となっていますが、sp==2の場合のspは使用しないため、問題ありません。

図246.2 検証用FSMのBsim波形 次にiverilogによるVerilogシミュレーション波形を図246.3示します。Bsimではrsを見ることができませんでしたが、verilogでは下位モジュールにrsがRAMとして配置されるので、push時にはステート'h08(L2 S0)とステート'h10(L3 S0)の2回、RAMのWEがアサートされていることが分かります。 図246.3 検証用FSMのIverilog波形

---

前のブログ 次のブログ

マクロ命令の使用

過去記事のCalee Savedコールリターンを前稿で作成したマクロ命令を使用して書き直すと、図245.1のようになります。青字がマクロ命令です。Caller Savedでは入らなかった余分なpushRetがルーチン先頭に入っています。あるいは次のcallとまとめてしまい、非リーフからのcallを別に設ければこれは見かけ上無くなります。こうすれば、リーフと非リーフで、コールもリターンも別になるのでかえってすっきりするかもしれません。

図245.1 マクロ命令を使用したサブルーチン呼び出し

検証用FSMソースコード

検証用FSMのBSVの全ソースコードを示します(既紹介部分は除く)。

import RegFile::*;

(* synthesize, always_ready, always_enabled *)
module mkTestFSM();

   Reg#(State_t) state <- mkReg(State_t{func:L1, step:S0}),
                 ret <- mkRegU;

   // L1
   rule rule_L1 (state.func == L1);
      rule rule_S0 (state.step == S0);
         $display("L1 S%d", state.step);
         `next;
      endrule // S0
      rule rule_S1 (state.step == S1);
         $display("L1 S%d", state.step);
         `call(L2);
      endrule // S1
      rule rule_S2 (state.step == S2);
         $display("L1 S%d", state.step);
      endrule // S2
   endrule // L1

   // L2
   rule rule_L2 (state.func == L2);
      rule rule_S0 (state.step == S0);
         $display("  L2 S%d", state.step);
         `pushRet; // L2 is not a leaf routine
         `next;
      endrule // S0
      rule rule_S1 (state.step == S1);
         $display("  L2 S%d", state.step);
         `next;
      endrule // S1
      rule rule_S2 (state.step == S2);
         $display("  L2 S%d", state.step);
         `call(L3);
      endrule // S2
      rule rule_S3 (state.step == S3);
         $display("  L2 S%d", state.step);
         `next;
      endrule // S3
      rule rule_S4 (state.step == S4);
         $display("  L2 S%d", state.step);
         `popRet;
      endrule // S4
   endrule // L2

   // L3
   rule rule_L3 (state.func == L3);
      rule rule_S0 (state.step == S0);
         $display("    L3 S%d", state.step);
         `pushRet; // L3 is not a leaf routine
         `next;
      endrule // S0
      rule rule_S1 (state.step == S1);
         $display("    L3 S%d", state.step);
         `call(L4);
      endrule // S1
      rule rule_S2 (state.step == S2);
         $display("    L3 S%d", state.step);
         `popRet;
      endrule // S2
   endrule // L3

   // L4 (Leaf)
   rule rule_L4 (state.func == L4);
      rule rule_S0 (state.step == S0);
         $display("      L4 S%d", state.step);
         `next;
      endrule // S0
      rule rule_S1 (state.step == S1);
         $display("      L4 S%d", state.step);
         `return;
      endrule // S1
   endrule // L4

endmodule: mkTestFSM

---

前のブログ 次のブログ

BSVコード

nextStep()関数は以下のとおりです。

    function nextStep;
       case (state.step)
          S0: nextStep = S1;
          S1: nextStep = S2;
          S2: nextStep = S3;
          S3: nextStep = S4;
       endcase
    endfunction: nextStep

以下に4段のスタックとスタックポインタの実装(インスタンシエーション)を示します。

    // return stack
    RegFile#(UInt#(2), State_t) rs <- mkRegFile(0, 3);
    // stack pointer
    Reg#(UInt#(2)) sp <- mkReg(0);

検証用FSMの設計

これらのステート遷移の検証用FSMを設計します。全部でL1~L4の4レベルのコールネスティング関係を持ち、各ステートでは、主にステート変数の表示を行います。図244.1～図244.4に、レベル1からレベル4のステート遷移図を図示します。

図244.1 L1ステート遷移

図244.2 L2ステート遷移

図244.3 L3ステート遷移

図244.4 L4ステート遷移

検証結果の作成

expectedというファイル名で実行結果を作成しておきます。レベルとステートをサイクル毎に表示するFSMの動きを示します。

    L1 S0
    L1 S1
      L2 S0
      L2 S1
      L2 S2
        L3 S0
        L3 S1
          L4 S0
          L4 S1
        L3 S2
      L2 S3
      L2 S4
    L1 S2
    L1 S2

---

前のブログ 次のブログ

スタック操作のBSV記述

共通シーケンスをコールする場合、これまで見てきたように、スタック操作をする必要がありますが、煩雑なのでこれを隠蔽することを考えます。と言ってもソフトウェアでやるように、push, pop, call, return等の概念を使います。また、これまでハードウェアという意識から「共通シーケンス」と称してきた概念を、ソフトウエアに合わせてサブルーチンと呼びます。

対象となる検証用FSMのステート定義を示します。例として4レベルのFSMを考えます。state変数は構造体で定義しています。

typedef enum { L1, L2, L3, L4 } Function_t deriving(Bits,Eq);
typedef enum { S0, S1, S2, S3, S4 } Step_t deriving(Bits,Eq);
    
typedef struct {
     Function_t func;
     Step_t step;
} State_t deriving(Bits,Eq);

rsはリターンスタック配列で、BSVでの実装例として、今回はRegFileで構成します。spはスタックポインタで配列インデックスです。Verilogにおける配列のdata変数への読み出し

    data <= rs[sp]

は、この実装では、

    data <=rs.sub(sp)

となり、逆にVerilogにおける配列へのdataの書き込み

    rs[sp] <= data

は、この実装では

    rs.upd(sp, data)

となります。

マクロ命令定義

これらを用いて作成したマクロ命令の定義文のコードです。

`define pushRet           rs.upd(sp, ret); sp <= sp + 1
`define popRet            state <= rs.sub(sp-1); sp <= sp - 1
`define call(SUB)         `_saveNext; state <= State_t {func:SUB, step:S0}
`define _saveNext         ret <= State_t {func:state.func, step:nextStep()}
`define return            state <= ret
`define next              state.step <= nextStep()

その説明を表243.1に示します。

表243.1　マクロ命令の定義

マクロ命令名	説明
pushRet	非リーフルーチン中で、他のルーチンを呼ぶ際に破壊されるretをスタックにプッシュするマクロ命令で、必ず先頭でpushするものとします。
popRet	非リーフ内で呼び出し元に戻るためのマクロ命令で、retを回復せずに、スタック中の戻りステートに直接戻るマクロ命令です。
call(SUB)	サブルーチンコールです。次のステートをretに入れ、コール先にジャンプします。
_saveNext	callに使用されており、次のステートをretに入れる内部マクロ命令です。後述のnextStep()関数を使用しています。ユーザが陽に使う必要は無いため、アンダースコアを付けています。
return	リーフ内で呼び出し元に戻るためのマクロ命令です。
next	次のステートに進めるためのマクロ命令です。後述のnextStep()関数を使用しています。

---

前のブログ 次のブログ

Direct Return

ついでに前稿で検討したダイレクトリターンがどうなるかを見ておきます。まず図で書けば、前稿のCaller Savedでは図242.1のようになります。左が一般的な、非リーフからのリーフのコール、右がダイレクトリターンです。コール先がリーフであると分かっている時は、リターンレジスタに戻り先を入れる代わりに、スタックをポップして戻り先をリターンレジスタに入れてからコールします。

図242.1 Caller Savedダイレクトリターン 一方、Callee Saved方式では、図242.2のようになります。同じく、左が一般的な、非リーフからのリーフのコール、右がダイレクトリターンです。 図242.2 Calee Savedダイレクトリターン 同じくコール先がリーフであると分かっている場合には、リターンレジスタに戻り先を入れる代わりに、そのままジャンプします。コール先を見ないという利点は無いものの、処理が単純化されます。

---

前のブログ 次のブログ

Caller Saved

今回GameFSMを開発するにあたり、過去記事で開発したコール方式を踏襲しますが、今回はCaller Saved方式に変えてみたいと思います。これを図示すると、呼び出し側では、必ずリーフと思ってリターンレジスタにネクストステートを格納して共通シーケンスをコールします。BSVコードで書けば、コール先をtarget_state、戻り先ステートをnext_stateとして、

    return <= next_state;
    state <= target_state;

となります。

リーフシーケンス

呼ばれた側は、さらにサブ共通シーケンスをコールするかどうかは分かっているので、さらに呼ばない場合、つまりリーフシーケンスである場合は何もせずに

    state <= return;

を実行して戻ります。

非リーフシーケンス

他方、さらにサブ共通シーケンスの場合は、呼ばれた側ではまずリターンレジスタをプッシュします。

    return_stack[sp] <= return;
    sp <= sp + 1;

呼び出し元と同様に、サブ共通シーケンスをコールします。

    return <= next_state2;
    state <= sub_sequence;

戻る場合は、本来はリターンレジスタを回復してからそれをステートに入れるのですが、処理を簡略化して、

    state <= return_stack[sp - 1];
    sp <= sp - 1;

として戻ります。

最後に、前稿で実施したCaller Savedと今回実施予定のCallee Savedの方式の違いを図でまとめます。Caller Savedの利点は前述のとおり、呼ぶ側では同じシーケンスで良いことです。さらにreturnレジスタを壊すか壊さないかは自分の情報なので、判断し易いことが挙げられます。

図241.1 Caller SavedとCalee Savedの処理の違い

---

前のブログ 次のブログ

mkConnection

BSVにはmkConnectionという機能があり、インターフェースの接続を効率的に行えます。

図240.1 Vivado sound階層ブロック図

図240.1にmkConnectionによる信号の接続及び、BSVで言うメソッドとVerilogで言う信号端子の関係を示します。

Verilogで表すと、モジュールefsmの端子out_code[4:0]から出力した信号code[4:0]が、モジュールsfsmの端子in_code[4:0]に接続されるものとします。この接続を実現するのは上位でのmkConnectionメソッドです。

まず、出力側モジュールefsmの読み出しメソッドは、interfaceブロックにおいてout_code()メソッドで記述されます。メソッドのリターンタイプはCode_tです。BSVのメソッド名がそのままVerilogの端子名になります。

    interface EFSM_ifc;
        method Code_t out_code();

上位での接続のための識別子は、"モジュール名"+"."+"BSVメソッド名(=Verilog端子名)"となります。EFSMモジュールのインスタンス名をefsmとすると、以下のようになります。

    efsm.out_code

一方、入力側モジュールsfsmへの書き込みメソッドには副作用があるため、interfaceブロックにおいて、method Actionとします。書き込みとVerilog端子は少々複雑で、Verilog端子名は"BSVメソッド名_入力パラメータ"となります。

    interface SFSM_ifc;
        method Action in(Code_t code);

上位での接続のための識別子は出力側と同じく、"モジュール名"+"."+"BSVメソッド名"となります。Verilog端子名とは若干異なります。

    sfsm.in

ここでは分かりやすさのため、メソッド名をinとしましたが、重なることはできないため、現実的にはinXXXXのように、意味のあるメソッド名を付けることになります。最後に上位での接続を示します。

    import Connectable::*;

    mkConnection(efsm.out_code, sfsm.in);

inとoutのどちらを先に書いても文法的には問題ありませんが、回路図の記法の通例として左から右に信号の流れを書くため、左側に出力メソッド、右側に入力メソッドを書くルールとします。

Verilog端子名の制御

注意:端子名制御はVerilogのみに影響を与えるため、mkConnection等のBSVの世界では影響を与えません。

defaultのVerilog端子生成ルールはコントロールすることができ、

• 出力側の端子名をOUTPORTとしたい場合は(* result="OUTPORT" *)とインタフェースに記述します。
• 入力側の端子名をINPORTとしたい場合は(* prefix="" *)としてメソッド名を消去し、さらに(* port="INPORT" *)とインタフェースに記述します。

メソッド名は大文字で始まることが許されていないため、任意のポート名を付けるにはこの制御指示子を用います。例えば、出力インタフェース部に

    method Bool fifo_ren();

という出力インタフェースがある場合、

    (* result="FIFO_REN" *)
    method Bool fifo_ren();              // output terminal "fifo_ren" -> "FIFO_REN"

という指示を与えることで、生成されるverilogにはFIFO_RENという端子が生成されます。

    // value method fifo_ren
    output FIFO_REN;

また、入力インタフェース

    method Action rom(Data_t indata);

においては、メソッド名がromでアーギュメントがindataであるため、defaultでは端子名はrom_indataとなります。これに対して、

    (* prefix="" *)
    method Action rom((* port="INDATA" *) // input terminal "rom_indata" -> "INDATA"
       Data_t indata);

という指示を与えることで、生成されるverilogにはINDATAという端子が生成されます。

    // action method rom
    input  [7 : 0] INDATA;

最後にmethod名を生かしたい場合には次のようにします。例えば

    method ActionValue#(Bit#(8)) read(); // パラレル出力メソッド
    method Action write(Bit#(8) nodata); // パラレル入力メソッド

のようにread及びwriteというパラレル入出力が有った場合、readという出力インタフェースに対して生成されたverilogは以下のようにmethod名がそのまま端子名になります。

    // read                           O     8 reg
    // RDY_read                       O     1
    // EN_read                        I     1

反対にwriteという入力インタフェースに対してはmethod名を消去しなければmethod名と変数名の結合となります。または、上記のようにmethod名を消去すると入力変数名が生きることになります。

そこで、method名を生かすには一度method名を消去して再度method名をポートで定義することで対処します。

    (* prefix="" *) // delete write
    method Action write((* port="write" *) Bit#(8) nodata); // パラレル入力メソッド

これにより生成されたverilogのコメント部は以下のとおりです。

    // write                          I     8
    // RDY_write                      O     1
    // EN_write                       I     1

---

前のブログ 次のブログ