何故RISC-Vのアトミック操作命令はLR/SCでCASではないのか

RISC-Vの仕様書を読んでいて、アトミックアクセスの所に色々書いていったので自分でも勉強してみることにした。

まず、大前提としてRISC-Vではアトミックアクセスのための命令としてLR/SC(Load-Reserved / Store-Conditional)の命令を採用している。 この命令自体は非常にありふれた命令で、基本的な動作はここではあまり説明しない。

アトミックアクセスの例題として良く用いられるものに「ABA問題」というものがある。これは何かの略称ではなく、「共有メモリの値をAからBに書き換える」問題だと思えば良い。 あるスレッドがとあるメモリ位置からデータをロードし(これを値Aとする)、それをもとに新しい値を計算し(これを値Bとする)、同じメモリ位置にストアする。 しかしこのAのロードとBの書き換え、ストアはある一定の時間をかけて行われるので、その間に別のスレッドによって同じ場所のメモリを書き換えられてしまった場合、データの矛盾が発生することになる。これがABA問題である。

これを解決するためのいくつかの方法があるが、ここではLR/SCとCASの2つの方法を挙げる。

• Load Reserved(LR)はとあるメモリ領域からデータをロードし、それと同時にそのメモリアドレスを「予約セット(Reservation Set)」に登録する。
• Store Conditional(SC)は同じ場所にデータをストアするが、予約セット内にそのメモリアドレスがまだ存在していれば成功し、そうでなければ失敗する。
• 予約セットは、別のスレッドやCPUデバイスが同じアドレスにアクセスすると外されてしまう。つまり、LRとSCの間に別のCPUデバイスやスレッドがそのアドレスにアクセスを行わない場合、SCは成功する。

もう一つ別の方法として"Compare and Swap"(CAS)という方法がある。CASの使い方は、まずとあるメモリアドレスからデータをロードし、それを古い値としてどこかに格納しておく。古い値をもとに計算を行い新しい値を算出し、最後にCAS命令によってその値をストアする。その際、ストア時に事前に取ってきた古い値と新しい値が一致していない場合(つまり別のCPUデバイスやスレッドによってその値が更新された場合)に、CASは失敗し、最初からやり直すことになる。

という訳で、CAS命令自体には「元の値」「更新した値」「ストアアドレス」の3つのオペランドを用意する必要があり、これがRISC-Vの標準的なオペランドフォーマットのどれにも当てはまらない。これにより、CASの定義をやめたというのが理由の一つに挙げられている。

LR/SCのCASに対する欠点として、ライブロックが回避できないということが挙げられている。ライブロックの詳細は別の文献に譲るが、有名なイメージとしては「正面から向かってきた2人が同じ方向に避けようとしていつまでたっても交差することができない」というやつだ。 イメージだが、LR/SCの場合は、2つのスレッドがLRとSCを交互に進めるとどちらとも成功せずにライブロック状態になるが、CASの場合は最新の値を持っているどちらかが常に勝つのでライブロックは発生しない、という理解であっているかな？

もう一つ、CASにはDW-CAS(double-word CAS)という仕組みがあり、2つのメモリアドレスに対してCAS操作を実行することによりリンクリストの操作を容易にするというものがある。

このLR/SCの実装についてはかなりいろんなコメントが残されているので、さらに続く。

Verilatorのコンパイルフローを観察する (11. V3Const.cppについて)

Verilatorの解析続き。

V3Const.cppには、いくつかの定数最適化が加わっているようだ。astgenというPythonスクリプトによってソースコードが拡張されている。展開用のスクリプトは長くてすぐには理解できないのだが、生成されたソースコードを読んでみる。

• verilator/src/obj_dbg/V3Const__gen.cpp

     // Generated by astgen
     virtual void visit(AstAdd* nodep) override {
         iterateChildren(nodep);
         if (match_NodeBiop_0(nodep)) return;
         if (match_NodeBiCom_0(nodep)) return;
         if (match_NodeBiComAsv_0(nodep)) return;
         if (match_NodeBiComAsv_1(nodep)) return;
         if (match_NodeBiComAsv_2(nodep)) return;
         if (match_NodeBiComAsv_3(nodep)) return;
         if (match_Add_0(nodep)) return;
         if (match_Add_1(nodep)) return;
     }

AstAddノードに遭遇すると、これらの最適化を行うようだ。

• match_Add_0 / match_Add_1 どちらかのオペランドが0の場合は加算ノードを省略する。

     bool match_Add_0(AstAdd* nodep) {
     // TREEOP ("AstAdd   {$lhsp.isZero, $rhsp}",   "replaceWRhs(nodep)")
     if (m_doNConst && nodep->lhsp()->isZero()) {
         UINFO(7,cvtToHex(nodep)<<" TREEOP ( AstAdd $lhsp.isZero, $rhsp , replaceWRhs(nodep) )\n");
         replaceWRhs(nodep);
         return true;
     }
     return false;
     }

この条件はこのマクロから来ているようだ。

     // Zero on one side or the other
     TREEOP ("AstAdd   {$lhsp.isZero, $rhsp}",   "replaceWRhs(nodep)");
     TREEOP ("AstAdd   {$lhsp, $rhsp.isZero}",   "replaceWLhs(nodep)");

AstNodeBiOpは2項演算のノードにはすべて適用されるようだ。つまり、両方のオペランドが定数の場合はこれを置き換える。

     // Generic constants on both side.  Do this first to avoid other replacements
     TREEOPA("AstNodeBiop {$lhsp.castConst, $rhsp.castConst, nodep->isPredictOptimizable()}",  "replaceConst(nodep)");

     // Generated by astgen
     bool match_NodeBiop_0(AstNodeBiop* nodep) {
     // TREEOPA("AstNodeBiop {$lhsp.castConst, $rhsp.castConst, nodep->isPredictOptimizable()}",  "replaceConst(nodep)")
     if (VN_IS(nodep->lhsp(),Const) && VN_IS(nodep->rhsp(),Const) && nodep->isPredictOptimizable()) {
         UINFO(7,cvtToHex(nodep)<<" TREEOPA( AstNodeBiop $lhsp.castConst, $rhsp.castConst, nodep->isPredictOptimizable() , replaceConst(nodep) )\n");
         replaceConst(nodep);
         return true;
     }

BiComというのは2項演算の可換な演算のようだ。これに対する最適化も定義されている。

         if (match_NodeBiComAsv_0(nodep)) return;
         if (match_NodeBiComAsv_1(nodep)) return;
         if (match_NodeBiComAsv_2(nodep)) return;
         if (match_NodeBiComAsv_3(nodep)) return;

Vivado Simulatorを使ってUVMに入門する (4. master と slave に分けてシミュレーション)

以下のサイトを読みながらUVMについて勉強をしている。

sites.google.com

次はUVMの環境をマスターとスレーブに分けて環境を構築する。これまで作ったsequencer / driver / monitor をそれぞれmasterとslaveに分けた。

• sample_master_agent.sv

class sample_master_agent extends uvm_agent;
  `uvm_component_utils(sample_master_agent)
  sample_master_driver    driver;
  sample_master_monitor   monitor;
  sample_master_sequencer sequencer;
  function new (string name, uvm_component parent);
    super.new(name, parent);
  endfunction

  function void build_phase(uvm_phase phase);
    super.build_phase(phase);
    driver    = sample_master_driver::type_id::create("driver", this);
    monitor   = sample_master_monitor::type_id::create("monitor", this);
    sequencer = sample_master_sequencer::type_id::create("sequencer", this);
  endfunction

  function void connect_phase (uvm_phase phase);
    if (get_is_active() == UVM_ACTIVE) begin
      driver.seq_item_port.connect(sequencer.seq_item_export);
    end
  endfunction // connect_phase

  task run_phase(uvm_phase phase);
    uvm_report_info("AGENT", "Hi");
  endtask // run_phase

endclass

• sample_slave_agent.sv

class sample_slave_agent extends uvm_agent;
  `uvm_component_utils(sample_slave_agent)
  sample_slave_driver    driver;
  // sample_slave_monitor   monitor;
  sample_slave_sequencer sequencer;
  function new (string name, uvm_component parent);
    super.new(name, parent);
  endfunction

  function void build_phase(uvm_phase phase);
    super.build_phase(phase);
    driver    = sample_slave_driver::type_id::create("driver", this);
    // monitor   = sample_slave_monitor::type_id::create("monitor", this);
    sequencer = sample_slave_sequencer::type_id::create("sequencer", this);
  endfunction

  function void connect_phase (uvm_phase phase);
    if (get_is_active() == UVM_ACTIVE) begin
      driver.seq_item_port.connect(sequencer.seq_item_export);
    end
  endfunction // connect_phase

  task run_phase(uvm_phase phase);
    uvm_report_info("AGENT", "Hi");
  endtask // run_phase

endclass

解説の通りに実装してVivado Simulatorでコンパイルしてみたのだが、どうも上手く行っていない気がする？masterからのリクエストが出ていないのか、ちゃんとメッセージが返ってきていないような気がする。

UVM_INFO @ 0: uvm_test_top.env [ENV] Hello ENV
UVM_INFO @ 0: uvm_test_top.env.slave [AGENT] Hi
UVM_INFO @ 0: uvm_test_top.env.slave.sequencer [SEQR] Hi
UVM_INFO @ 0: uvm_test_top.env.slave.driver [DRIVER] Hi
UVM_INFO @ 0: uvm_test_top.env.master [AGENT] Hi
UVM_INFO @ 0: uvm_test_top.env.master.sequencer [SEQR] Hi
UVM_INFO @ 0: uvm_test_top.env.master.monitor [MONITOR] Hi
UVM_INFO @ 0: uvm_test_top.env.master.driver [DRIVER] Hi
Hello SEQ
UVM_INFO @ 0: uvm_test_top.env.master.sequencer@@write_seq [SEQ] read data is 00f
UVM_INFO /proj/xbuilds/SWIP/2020.2_0711_1805/installs/lin64/Vivado/2020.2/data/system_verilog/uvm_1.2/xlnx_uvm_package.sv(13673) @ 0: reporter [UVM/REPORT/SERVER] [UVMTOP]     1

うーん、もうちょっと解析したい。

Vivado Simulatorを使ってUVMに入門する (3. sequence / sequence_item / driver)

UVMの勉強をしている。UVMを使ったもう少し踏み込んだデザインについて勉強中。以下のページを参考にしている。

sites.google.com

UVMのテストパタンがどのようにテストターゲットに向けて流されるのかという話だが、とりあえずは、

• sequnceというユニットがあり、この中ではsequence_itemというユニットが入っておりここでテストを生成する。
• sequence_itemで生成したテストをsequencerに渡す。
• sequencerはテストをdriverに渡す。

という流れになっているようだ。それぞれについてよく見ていくことにする。

sequence_itemについて

sequence_itemクラスによってテストを生成するらしい。uvm_sequence_itemクラスを派生してクラスを作成する。

class sample_seq_item extends uvm_sequence_item;
  byte addr, data;
  bit  write;
  `uvm_object_utils(sample_seq_item)
  function new (string name="sample_seq_item_inst");
    super.new(name);
  endfunction
endclass

sequenceを記述する

sequence内にテストベクタを記述するということになる。

virtual class sample_base_seq extends uvm_sequence #(sample_seq_item);
    // sample_bas_seqのコンストラクタみたいなもの
    // do_not_randomize は上記参考サイトで使っているModelSimの制約
    // VivadoSimだときっとうまくいく
    function new(string name="sample_base_seq");
        super.new(name);
        do_not_randomize = 1;
    endfunction

 virtual task pre_body();
        // pre_body()はbodyの前に呼び出されるメソッド
        // pre_body() --> body() --> post_body() の順番に呼び出されるらしい
        if (starting_phase!=null) begin
            `uvm_info(get_type_name(),
                $sformatf("%s pre_body() raising %s objection",
                           get_sequence_path(),
                           starting_phase.get_name()), UVM_MEDIUM);
            // これの意味はよくわからないが、objectionをriseさせるというのは、
            // Queueに何かを設定するくらいの意味合いで良い気がしてきた。
            // このQueueが空になったら、きっとUVMは終了する。
            starting_phase.raise_objection(this);
        end
    endtask

 virtual task post_body();
        if (starting_phase!=null) begin
            `uvm_info(get_type_name(),
                      $sformatf("%s post_body() dropping %s objection",
                                get_sequence_path(),
                                starting_phase.get_name()), UVM_MEDIUM);
            // body()の実行が終わったら呼び出されるメソッド
            // objectionからdropさせて、テストを終わらせる、ということだと思われる。
            starting_phase.drop_objection(this);
        end
    endtask

そして、上記のsample_base_seqを継承してwrite_seqクラスを作成する。ここにbody()を記述することで、いろんなテストでpre_body(), post_body()を共有する、ということか。

// このクラスは上記のsample_base_seqを派生させたもの
// sample_base_seqはuvm_sequenceの派生なので、結果的にこれもuvm_sequenceになる
class write_seq extends sample_base_seq;
    `uvm_object_utils(write_seq)
    function new (string name="write_seq");
        super.new(name);
    endfunctio
    // ここに本物のbody()が置かれる
    virtual task body();
        $display("Hello SEQ");
        `uvm_create(req)
        req.write <= 1'b1;
        req.addr  <= 8'h10;
        req.data  <= 8'h55;
        `uvm_send(req)
        #1000;
    endtask
endclass

driverを更新する

sequenceとsequencerを実装すれば、次はそれをモデルに渡すドライバだ。sample_driverを更新する。

seq_item_port.get_next_item()で取得した情報をここでドライバに設定する。s

 task run_phase(uvm_phase phase);
        uvm_report_info("DRIVER", "Hi");
        vif.valid <= 1'b0;
        @(posedge vif.rstz);  // wait reset negate
        forever begin
            seq_item_port.get_next_item(req);  // wait seq_item from sequence (via sequencer)
            @(posedge vif.clk); // sync clk
            vif.valid <= 1'b1;
            // reqで取得した情報をここで設定する
            vif.write <= req.write;
            vif.addr  <= req.addr;
            vif.data  <= req.data;
            @(posedge vif.clk);
            vif.valid <= 1'b0;
            seq_item_port.item_done(rsp);
        end
    endtask

Verilatorのコンパイルフローを観察する (10. Veritalor Internalsのドキュメントを読む)

VerilatorのInternalドキュメントを読む。ソースコードを読んでいるだけではだんだん良く分からなくなってきたので、一応概要を確認しておく。 概要の続き。

github.com

コーディング規約

インデントスタイル

Verilator C++ソースのインデントをマッチさせるために、レベル毎に4つのスペースを使用し、タブは8列にして、1つおきのインデントレベルがタブストップになるようにする。

全てのファイルは標準的なインデントを保証するために、以下のマジックヘッダを挿入するべきである：

// -*- mode: C++; c-file-style: "cc-mode" -*-

このコメントにより、インデントスタイルはcc-modeに設定される(Verilatorは数年前のCC-modeの変更に先立って、GNUスタイルのインデントでデフォルトを上書きしていたが、c-set-styleはそれを元に戻す)。

astgenスクリプト

いくつかのPassの実装は非常に多くの繰り返しが含まれているのと、AstNodeのサブクラスを実装する必要がある。しかし、繰り返しの最中の最中にはこれらは非常に可動的であり、C++のマクロにより処理される。

VerilatorではこれはPerlスクリプトastgenを使って実装されており、C++コードをプリプロセスする。例えばV3Const.cppはvisit()を関数を、各バイナリ演算をTREEOPマクロを使って実装してある。

オリジナルのC++ソースコードはobj_optとobj_dbgサブディレクトリ(前者はVerilator向けに最適化されたもの、後者はデバッグ版)に変換される。例えば、V3Const.cppはV3Const__gen.cppに変換される。

Visitor関数

VerilatorはVisitorデザインパタンを使ってPassのリファインと最適化を行う。これによりPassのアルゴリズムとそれが動作するASTを分離することができる。WikipediaではVisitorのコンセプトについての説明がある (http://en.wikipedia.org/wiki/Visitor_pattern: 日本語のページは https://ja.wikipedia.org/wiki/Visitor_%E3%83%91%E3%82%BF%E3%83%BC%E3%83%B3)。

上記で示したよううに、すべてのVisitorはAstNVisitorからの派生クラスである。すべてのAstNodeの派生クラスはacceptメソッドを実装する。acceptメソッドはAstNVisitorの派生クラスのインスタンスへの参照を渡し、AstNVisitorのvisitメソッドを実行してAstNodeインスタンス(例えばthis)を誘起する。

困難な点としては、accept の呼び出しが、引数として受け取ったノードを破壊するような編集を実行する可能性がある。AstNodeのacceptSubtreeReturnEditsメソッドは、acceptを適用し、元のノードが破壊されても結果のノードを返すために用意されている（破壊されない場合は元のノードが返されるだけ）。

visitorクラスの動作は、さまざまな AstNode 派生クラスの visit 関数をオーバーロードすることで実現している。特定の実装が見つからない場合、システムは継承階層上でオーバーロードされた実装を順に探していきます。たとえば、AstIf の accept を呼び出すと、順に以下のようになる。

void visit (AstIf* nodep, AstNUser* vup)
void visit (AstNodeIf* nodep, AstNUser* vup)
void visit (AstNodeStmt* nodep, AstNUser* vup)
void visit (AstNode* nodep, AstNUser* vup)

visitor関数間のデータの受け渡しには3つの方法がある。

1. visitorクラスのメンバー変数である。これは一般的には「親」の情報を子供に渡すために使用される。m_modp がその例である。この変数はコンストラクタで NULL に設定され、そのノード（AstModule のビジター）が設定し、その後、子供たちが反復され、クリアされる。AstModule 以下の子供には NULL が設定され、それ以外のノードには NULL が消去される。ネストしたアイテムがある場合（例えば、AstForの下にAstForがある場合）、変数はAstForのビジターでsave-set-restoreされる必要があり、そうしないと下のforを終了すると上のforの設定が失われます。

2. ユーザー属性。各AstNode（注：visitorではなく AST ノード）は、5 つのユーザ属性を持ち、 user1() ～ user5() メソッドを用いて整数値でアクセスしたり、 user1p() ～ user5p() メソッドを用いてポインタ（AstNUser 型）でアクセスしたりすることができる（グラフ探索パッケージからの一般的な手法である）。 visitorは、まず AstNode::user#ClearTree() を呼び出して使用したいノードをクリアし、その後、任意のノードの user()に必要なデータをマークすることができる。読者は単に nodep->user() を呼び出すだけであるが、適切にキャストする必要がある場合もあるので、nodep->userp()->castSOMETYPE() をよく見かけます。各ビジターの先頭には、user()の内容がそのビジタークラスにどのように適用されるかを説明するコメントがある。例えば、以下のようになる。

   cpp // NODE STATE // Cleared entire netlist // AstModule::user1p() // bool. True to inline this module

   これは、AstNetlistでuser1ClearTree()が呼ばれることを表している。各 AstModule の user1() は、インライン化するかどうかを示すために使用される。

   これらのコメントは、特定の AstNode タイプの user#() が 2 つの異なる目的に使用されることがないようにするために重要である。

   user#ClearTree の呼び出しは高速で、ツリーを歩くわけではないので、かなり頻繁に呼び出しても問題ないことに注意してください。たとえば、すべてのモジュールで共通して呼び出される。

3. パラメータは、「通常の」関数の呼び出し側から呼び出し側への方法に近い形で、ビジター間で渡すことができる。これは、ほとんどのvisitor関数で無視されるAstNUser型の2番目のvupパラメータである。V3Widthはこれを行いるが、上記の方法よりも面倒であることがわかり、非推奨となりました。(V3Widthはほぼ最初に書かれたモジュールでした。vupをいたるところで通さなければならないのはプログラムが遅くなるので、いつかはこの方式が削除されるかもしれません)

イテレータ

AstNodeはツリー内を歩き回るためにいくつかのイテレータを提供している。それぞれは2つの引数、visitorv, (AstNVisitor型)、オプションであるユーザデータのポインタvup(`AstNUser*型)である。2番目の引数はVisitor関数の節で説明したパラメータを渡すための方法であるが、この方式は廃止されており新しいvisitorクラスでは使用するべきではない。

iterate()

AstNodeのacceptメソッドを実行し、visitor関数を実行する

IterateAndNextIgnoreEdit()

リスト中のAstNodeに対してacceptメソッドを実行する(例えば、nextpとbackpポインタに接続されているリストなど)

iterateAndNext()

リスト中のAstNodeに対してacceptメソッドを実行する。もしノードがacceptにより変更されるのであれば、ノードが変更されなくなるまでacceptを適用し続ける。

iterateListBackwards()

リスト中のAstNodeに対してacceptメソッドを、最後の要素から順番に適用する。

iterateChildren()

iterateAndNextメソッドをop1pからop4pまでの各子供要素に適用する。

iterateChildrenBackwards()

iterateListBackwardsメソッドをop1pからop4pまでの各子供要素適用する。

派生クラスの識別

一般的な要件として、特定のAstNodeクラスを識別することが挙げられる。例えばVisitorはAstIfとAstGenIfに対して個別のvisitメソッドを実装するのではなく、ベースクラスに対して1つのメソッドを実装する場合がある：

void visit (AstNodeIf* nodep, AstNUser* vup)

しかし、このメソッドは、AstGenIf のために呼び出された場合、追加のコードを指定したい場合がある。Verilator は、C++ の dynamic_cast を使用して、可能なノードタイプごとに castSOMETYPE() メソッドを提供することでこれを実現している。このメソッドは、その型にキャストされたオブジェクトへのポインタを返すか（SOMETYPE クラスまたは SOMETYPE の派生クラスの場合）、さもなければ NULL を返す。よって、私たちのvisitorメソッドは次のようになる:

if (nodep->castAstGenIf()) {
    <code specific to AstGenIf>
}

共通のテストはAstNetlistのためのもので、これはASTのルートとなるノードである。

Verilatorのコンパイルフローを観察する (9. Veritalor Internalsのドキュメントを読む)

VerilatorのInternalドキュメントを読む。ソースコードを読んでいるだけではだんだん良く分からなくなってきたので、一応概要を確認しておく。

github.com

Verilator Internals

このファイルではVerilatorの内部構造とプログラミングの詳細について議論する。これは開発者が問題をデバッグするときに参照するためのものである。

Verilator Internalsのプレゼンテーション http://www.veripool.org も参照のこと。

コードフロー

Verilatorフロー

Verilatorのメインフローは、Verilator.cppのprocess()関数を追いかけることができる。

最初に、コマンドラインで指定されたファイルが読み込まれる。ファイルを読み込んだことでプリプロセッシングが動作しFlexによる字句解析とBisonによる構文解析が行われる。これによりデザインを表現する抽象文法木(Abstract Syntax Tree: AST)表現が生成され、以降で説明する.teeファイルで可視化される。

Verilatorは次にAST上でいくつかのPassを形成し、ASTのリファインと最適化を行う。

AST内のCellが最初にリンクされ、上記のさらに別のファイルが読み込まれ構文解析が行われる。

パラメータが解決され、デザインがエラボレートされる。

次に、Verilatorは階層デザインに対して様々な変更や最適化を行う。これにはカバレッジやアサーション、Xの除去、インライン化、定数伝搬、不使用コードの削除などが含まれる。

デザイン中の参照は次に疑似的にフラット化される。各モジュールの変数と関数は「スコープ」参照を持つようになる。スコープ参照はフラット化された階層内でフラット化されていない変数を発生させる。階層構造中に一度しか現れないモジュールは各変数に対して単一のスコープと単一のVarScopeしか持たない。2回登場するデザインはそれぞれの登場に対して1つのスコープと、各変数につき2つのVarScopeを持つ。これによりフラット化されたデザインに対して、階層を維持しつつ最適化を実行することができるようになる。

更なる変更と最適化は疑似的にフラット化されたデザイン中で実行される。これらの処理にはモジュール参照、関数のインライン化、ループアンローリング、変数のライフタイム解析、ルックアップテーブルの作成、alwaysの分割、論理ゲートの簡単化(インバータの挿入、など)が含まれる。

Verilatorはコードを順番化する。最良のケースでは、この結果により単一のeval()関数によりすべてのalways文が上から下にループすることなく実行される。

Verilatorはフラット化したもののほとんどを捨てる、これにより同じモジュールが複数回呼び出されたときには、コードが共有化される。これにより変数がローカライズされ、個々の関数が組み合わさり、マクロがCのプリミティブに展開され、分岐予測のヒントが与えられ、さらに定数伝搬が実行される。

Verilatorは最終的にC++のモジュールを生成する。

Verilatorのフローで使用されるカギとなるクラス

AstNode

ASTはAstNodeクラスのトップレベルで表現される。この抽象クラスから、個々のコンポーネント(例えば、AstGenerateはgenerateブロックのためのコンポーネントである)やコンポーネントのグループ(例えば、AstNodeFTaskは関数とタスクのためのクラスであり、AstFuncとAstTaskクラスに置き換えられる)。

各AstNodeは4つの子供へのポインタを持っている。これらはop1pからop4pと呼ばれる。これらのメソッドは次に特定のAst*ノードクラスにより抽象化される。例えば、AstIfノード(if文用のノード)では、ifspはop2pを呼び出すことでthenブロックのASTへのポインタを取得しelsespはop3pを返すことでelseブロックのASTか、elseブロックが無い場合はNULLを取得することができる。

AstNodeクラスは次と前のASTのコンセプトを持っている。例えばブロック中の前後の文などである。これらの文のASTへのポインタは（もし存在すれば）backやnextメソッドを用いることで取得することができる。

AstNetListはツリーのトップに配置されており、もしツリーのトップにいる場合はこのクラスをチェックすることが内部をチェックす標準的な方法であることを覚えておくとよい。

慣習により、各関数やメソッドはnodepという変数を、現在処理しているAstNodeへのポインタとして使用している。

AstNVisitor

PASSはASTビジタークラス(「ビジター関数」を参照のこと)により実装されている。これらは抽象クラスであるAstNVisitorのサブクラスとして実装してある。各PASSはビジタークラスのインスタンスを生成し、PASSの処理を実装することになる。

V3Graph

いくつかのPASSはグラフアルゴリズムを使うことになり、V3Graphクラスがグラフを表現するために使用される。グラフは有向グラフであり、グラフを操作するためのアルゴリズムと、その結果をGraphVizのdotフォーマット(http://www.graphviz.org を参照のこと)を出力する。V3Graph.hにクラスのドキュメントが格納されている。

V3GraphVertex

これはグラフの頂点を示すためのベースクラスである。頂点はfanout、 color、rank属性が付けられており、グラフを処理するためのアルゴリズムで使用される。汎用的なuser/userpメンバ変数も提供される。

dotファイルを出力するための名前、色、形、スタイルを指定するための仮想メソッドが提供される。典型的にはユーザはV3GraphVertexからの派生クラスを作成し、これらのメソッドを再実装することになる。

エッジの入出力に対してアクセスするためのイテレータが提供されている。典型的にはこれらな以下の形式で使用される。

for (V3GraphEdge *edgep = vertexp->inBeginp();
     edgep;
     edgep = edgep->inNextp()) {

V3GraphEdge

これはグラフの頂点を有向エッジを表現するためのクラスである。エッジにはweightとcutabe属性が付けられている。汎用的なuser/userpメンバ変数も提供されている。

frompとtopアクセサはそれぞれエッジのfromとtoの頂点を返す。

dotファイルを出力するためのラベル、色、スタイルを指定するための仮想めそっだが提供される。典型的には、ユーザはV3Graphedgeからの派生クラスを作成し、これらのメソッドを再実装することになる。

V3GraphAlg

これはグラフアルゴリズムのベースとなるクラスである。このクラスではboolを返すメソッドであるfollowEdgeメソッドを実装し、アルゴリズムがエッジをどのように追いかけていくかどうかを決めることができる。このメソッドはあるユーザ関数(edgeFuncp()：コンストラクタにより提供する)よりも重みが大きければtrueを返す。

あらかじめ定義されたアルゴリズムのクラスとメソッドはV3GraphAlg.cppから取得可能である。

Verilatedフロー

Verilatorにより生成された評価ループは、殆どの状況において、評価を実行するために実行する単一の関数としてデザインされている。

最初の評価では、Verilatedなコードはinitialブロックを呼び出し、すべての信号が安定化するまで(alwaysステートメントにより)関数を評価するモジュールを"settle"状態にする。

他の評価では、Verilatedコードはどの入力信号が変化したかをチェックする。クロックである場合、(alwyas @ posedgeステートメントから)適切なシーケンシャル関数を呼び出す。シーケンシャル関数の間には、組み合わせ回路関数(always @より)が呼び出される。これが終わると、組み合わせループや内部で生成されたクロックによる変化を検出し、それが見つかった場合にはモデルを再評価しなければならない。

SystemCコードでは、eval()関数はSystemC SC_METHODによりラップされる。これはすべての入力に対して反応する(理想的にはクロックと組み合わせ入力について伸び反応すれば良いが、トレースのためにはすべての信号に対して評価が必要であり、また性能への影響も小さい)。

トレースが有効である場合、コールバック関数はすべての変数の変化をチェックし、それぞれの変化をトレースに書き込む。頃プロセスを高速化するためには評価プロセスは変数うのビットマスクを評価し、変化を検出する; もしクリアされている場合には、その信号の変化に対するチェックはスキップする。

HPVM: Heterogeneous Parallel Virtual Machine についてのメモ

LLVM Maling Listで流れてきたのでメモ：イリノイ大学の開発したHPVMについて。 ヘテロジニアスアーキテクチャ向けのIR Representationのことを示しているようだ。論文は以下。まだ全部読み切っていないけど。

• HPVM: Heterogeneous Parallel Virtual Machine

https://dl.acm.org/doi/pdf/10.1145/3200691.3178493

コンパイルフロー。論文から参照。

GitLabのリポジトリは以下のようだ。

gitlab.engr.illinois.edu

ビルド方法は以下から参照。

hpvm.readthedocs.io