Verylへの中間表現の導入
はじめに
VerylとはSystemVerilogの代替言語を目指して開発中の新しいハードウェア記述言語です。現在、Verylへ中間表現の導入を進めているので、その動機や進捗状況について書いてみます。
Verylの処理の流れ
中間表現の話をする前に、Verylの処理の流れを説明しておきます。
VerylはSystemVerilogソースコードをターゲットとするトランスパイラなので、入力はVerylのソースコード、出力はSystemVerilogのソースコードとなり、以下のような流れで出力を生成します。
- Verylソースコードを構文解析し、具象構文木（CST）を生成
- CSTを走査してシンボルテーブルを構築
- CSTを走査してエラーチェック
- CSTを走査してSystemVerilogソースコードを生成
このようにVerylコンパイラはその処理の大半を具象構文木ベースで行っています。一般的な言語処理系の構成では、構文解析後は早々に抽象構文木（AST）や何等かの中間表現に情報を落としてしまうことが多いと思います。Verylがこのようにしているのは、SystemVerilog生成やフォーマッターなどの機能を提供するために、空白やコメントなどソースコードの全要素を含んだ状態で処理したいためです。
一方でCSTベースの処理が明らかに向いていない部分もあります。「CSTを走査してエラーチェック」の部分ですね。このエラーチェックというのは例えば「未割り当て変数のチェック」といったものですが、変数の割り当て状況を確認するためにCSTを走査する場合、ほとんどのノードは変数割り当てと無関係なのでとても効率が悪いです。また、インスタンス化やループなどによって評価時に発生する変数はソースコードの字面には表れないので、構文木にも当然現れず、こちらも処理が面倒です。現在のVerylコンパイラでは一部のインスタンス化について部分木をコピーしてくることで簡易的に対応していますが、完全な対応はできていません。
中間表現の導入
というわけで「CSTを走査してエラーチェック」の部分に絞った形での中間表現の導入を行っています。導入後の処理の流れは以下のようになります。
- Verylソースコードを構文解析し、具象構文木（CST）を生成
- CSTを走査してシンボルテーブルを構築
- CSTを走査して中間表現を生成
- 中間表現を用いてエラーチェック
- CSTを走査してSystemVerilogソースコードを生成
一般的な言語処理系では、一度中間表現に変換した後は最終成果物までその中間表現をベースに処理を進めることが多いと思いますが、Verylではソースコード生成部の処理はCSTベースを維持します。
中間表現によってできるようになること
ビット単位でのラッチ検出
Verylはハードウェア記述言語なので、一般的なプログラミング言語とは異なるエラーを検出したい場合があります。その1つがラッチ生成の検出です。
例えば以下のような if 文を考えます。これはプログラミング言語としてみると何の問題もないように見えますが、ハードウェア記述言語としては問題があります。
always_comb {
if x {
a = 1;
b = 1;
} else {
a = 2;
// b がない
}
}
詳細は省略しますが、else 節に b への代入が書かれていない場合、ラッチ生成という問題が発生し、これを検出したいということです。
すなわち、条件文のある節で代入される変数は、それ以外の全ての節でも代入される必要がある、ということです。さらにVerylでは各変数に対してビット単位で代入できるので、この検出はビット単位で行う必要があります。
var a: logic<2>; // a は2ビットの変数
always_comb {
if x {
a = 1; // a の2ビットに0を代入
} else {
// a の 1ビット目は代入されているが
// 0ビット目は代入されていないのでラッチ生成エラー
a[1] = 1;
}
}
構文木をたどりながらこの検出を行うのはかなり面倒で、従来はビット単位での検出はできていませんでした。また、ここでは if 文を例に挙げましたが、実際には case switch など複数の条件分岐構文があるのでそれらに対しても同様にチェックする必要があります。
中間表現の導入により、条件分岐は全て if X then Y else Z という単純な形式に変換されます。これにより分岐構文毎の対応が不要になり、構造が大幅に簡素化されたことでビット単位での検出もできるようになりました。
ジェネリクス・パラメータオーバーライドを考慮した型検査
Verylではジェネリクスやパラメータオーバーライドによってモジュールのインスタンス化のときに定義済のパラメータを変更することができます。
module ModuleA #(
param X: u32 = 1, // パラメータ X の値は 1
) {}
module ModuleB {
inst u: ModuleA #(
X: 10 // パラメータ X の値を10に変更
);
}
パラメータを変更すると、そのパラメータを用いた型定義も変わってくるので、型検査もそれを考慮して行う必要があります。従来の実装では構文木を部分的にコピーすることでこの対応を行っていましたが、完全は対応はできていませんでした。
中間表現の導入後は、ジェネリクスやパラメータオーバーライドを考慮しながら中間表現へと展開していくので、単に生成された中間表現をチェックするだけで自動的に変更されたパラメータが反映されます。
パフォーマンスの向上
エラーチェックのパフォーマンスも向上します。これは複雑なチェックを構文木ベースで行っていたことや部分木のコピーにかかるコストが削減されるためです。
以下のflamegraphは現在作業中のものですが、左側の緑の部分が構文木ベースの処理、右側の青の部分が中間表現ベースの処理になっています。これから構文木ベースのチェックを中間表現の方に移動していきますが、中間表現側で重い処理は実装済みなのでこれ以上増えることはなく、左側だけが減っていく予定です。
いまのところ元の3倍程度のパフォーマンス向上が得られる見込みです。
ネイティブシミュレータ
すでに述べた通り、中間表現では複雑な条件分岐構文や、ジェネリクス・パラメータオーバーライドが全て解決・展開された状態になります。そのため、その中間表現を単純に評価していくだけでRTLシミュレーションを行うことができるようになります。
さらに、型検査のために式の評価器自体は実装済みなので、中間表現の導入が完了した時点でネイティブシミュレータの実装に必要な部品は全て揃うことになります。
実際にシミュレーションを行うためにはテストベンチ記述の方法を検討する必要がありますが、以下の記事で書いた通りある程度のアイデアはある状態なので、ネイティブシミュレータの実装は比較的早期に実現するのではないかと考えています。
現在の状況
現在以下のPRで作業中です。すでに1か月以上経過、1万行以上の追加となる大規模なPRですが、現時点で言語機能の大半は対応済です。今後、構文木ベースのチェックを中間表現ベースに移行し、年明けくらいのマージを目指しています。
Discussion