みなさん、こんにちは。この「Synthesijer と高位合成ツールの作り方」のシリーズでは、全5回を通じて Synthesijer をベースに FPGA 向けの簡単な高位合成処理系を作る方法を紹介していきます。例は Java ですが、お気に入りの言語向けの処理系を開発する足がかりとして利用できるように紹介できればと思ってます。
前回は、Synthesijer のコンセプトを紹介し、Synthesijer が Java をハードウェア・ロジックに変換する処理の流れを紹介しました。第1回、第2回と前置きが長くなりましたが、今回は、実際にプログラムがハードウェア・ロジックに変換される過程を紹介します。
入力プログラム
以下の Java プログラムを例に変換フローの各ステップを紹介します。変換のフロー全体の概要は、前回の記事もあわせてご覧ください。
public class Test{
public boolean flag;
private int count;
public void run(){
while(true){
count++;
if(count > 5000000){
count = 0;
flag = !flag;
}
}
}
}メンバ変数として flag と count が定義されています。Java では、public がついている flag だけがクラスの中からも外からアクセスでき、private がついている count 変数はクラスの中でだけしか利用できません。生成するハードウェアでも、flag に相当する信号だけが読み書きできるようにしましょう。
処理本体は public void run(){...} で、これは count をインクリメントし、5000000 を越えるたびに flag を反転します。
Java プログラムの AST を取得
Java は、Java コンパイラをプラグインで拡張できる仕組みを持っています。プラグインは Plugin インターフェースと、TaskListener を実装して作ります。
Synthesijer が Java プログラムを読み出すプラグインは SynthesijerPlugin.java です。以下がコードの抜粋です。
// Javaコンパイラにプラグインとして挿し込むクラスの実装
// PluginとTaskListenerを実装する
public class SynthesijerPlugin implements Plugin, TaskListener{
// Pluginの実装に必要。プラグイン名
@Override
public String getName(){
return "Synthesijer";
}
// Pluginの実装に必要。初期化。
@Override
public void init(JavacTask task, String... args){
// このクラス自身をJavaのコンパイル中に呼び出すよう登録
task.addTaskListener(this);
}
// TaskListenerの実装に必要。タスク開始時に呼ばれる
@Override
public void started(TaskEvent e){
if (e.getKind() == TaskEvent.Kind.GENERATE){
// コンパイルタスクのうち GENERATE
// (コンパイル処理の最終処理) の時に、Synthesijerの処理に
// プログラム情報(e.getCompilationUnit())を引き渡す
System.out.println("source: " + e.getSourceFile().getName());
newModule(e.getCompilationUnit());
}
}
// TaskListenerの実装に必要。タスク終了時に呼ばれる
@Override
public void finished(TaskEvent e){
}
...
// 以降に処理本体の newModule を実装e.getCompilationUnit() は、コンパイル済みの Java のクラスに相当する情報が格納されている CompilationUnitTree のインスタンスを返します。プラグインを活用すると、Java プログラムの字句解析・構文解析を実装することなくプログラムにアクセスできます。
Java の AST を辿る
Java コンパイラの中では、プログラムがコンパイルの単位であるファイル毎の CompilationUnitTree をルートとする AST で保持されています。Java プログラム中にでてくる import や package などのすべての情報を CompilationUnitTree のインスタンスから取り出せます。
CompilationUnitTree は、accept メソッドが規定された Tree を継承しています。AST を辿ってプログラムにアクセスするには accept を利用したビジターパターンを利用します。
Synthesijer では、JCTopVisitor を使ってプログラムを走査します。クラス→メソッド→文→式と Java の AST を辿ることで与えられた Java プログラムの構造を読み取っています。
AST から内部情報を生成
現在の Synthesijer では、Java プログラムから SchedulerInfo をルートとする内部情報を生成します。SchedulerInfo は、必要な変数とステートマシンで構成されています。次の図は、前述の例から生成されたステートマシンです。
メソッドが呼び出されると METHOD_ENTRY から状態遷移がスタートし、while ループに相当する状態をぐるぐる回った後、METHOD_EXIT で処理が終わります。
内部情報の変形(最適化)
生成したばかりのステートマシンは、Java プログラムをステップ実行するような素朴な構造をしています。プログラムで意図した通りの動作をするとは言え、より短い時間で実行できるようにする、より小さいハードウェアロジックで実装できるようにするといった最適化を施したくなります。
Synthesijer では実行時のオプションで適用する変換処理の有効・無効をセットできます。たとえば、SSA 変換、基本ブロック内の並列化、チェイニングを有効にした場合の変換の様子を紹介します。
最初に、与えられたプログラムを SSA 形式に変換します。これは、変数への代入を一箇所だけに制限することで、変数が定義される場所と使用される場所の解析をしやすくする基本的な変換です。次のように変換されます。
与えられたプログラムで変数の値が上書きされるたびに別名の変数を生成します。分岐後の合流地点で、適切な変数を採用する PHI 関数が追加されています (ステート2とステート9)。
次の図が、基本ブロック内の並列化を行なった結果です。同時実行可能なステート4のインクリメントとステート5の代入文が、一つのステート4にまとめられました。
次がチェイニングを適用した結果です。ここでは、Java プログラムにあった while の条件に必要なインクリメントと比較を一つのステップで実行するようにまとめています。上の図で4、6、7に分かれていたステートが4にまとめられました。
HDLの生成
変換後の内部情報から VHDL や Verilog に対応した AST (HDL-AST) を生成します。モジュール→入出力ポート→組合せ回路、レジスタ代入、ステートマシンという構造を生成します。
HDL-AST から最終生成物の VHDL と Verilog を生成します。次はモジュール定義部分を抜粋したものです。
module Test
(
input clk,
input reset,
input flag_in,
input flag_we,
output flag_out,
output run_busy,
input run_req
);
...与えられた Java プログラムの Test クラスに対応して Test という名前のついたモジュールが生成されました。flag_in、flag_we、flag_out が元のプログラムで public 変数として定義されていた flag を、クラスの外から読み書きできる入出力ポートです。private 変数の count に相当するポートは宣言されていないことにも注意してください。
モジュール内には、下のようなプログラムの振舞いに相当するステートマシンと各ステートでレジスタの値を確定する always 文が生成されます。
...
// プログラムから抽出したステートマシンを always 文で作る
always @(posedge clk) begin
if(reset == 1'b1) begin
run_method <= run_method_IDLE;
run_method_delay <= 32'h0;
end else begin
case (run_method)
run_method_IDLE : begin
run_method <= run_method_S_0000;
end
run_method_S_0000 : begin
run_method <= run_method_S_0001;
end
run_method_S_0001 : begin
if (tmp_0005 == 1'b1) begin
run_method <= run_method_S_0002;
end
end
run_method_S_0002 : begin
if (tmp_0007 == 1'b1) begin
run_method <= run_method_S_0004;
end else if (tmp_0008 == 1'b1) begin
run_method <= run_method_S_0000;
end else begin
run_method <= run_method_S_0004;
end
end
run_method_S_0004 : begin
...
// 適切なステートで必要なレジスタの値をアップデートする
always @(posedge clk) begin
if(reset == 1'b1) begin
unary_expr_00009_1 <= 1'b0;
end else begin
if (run_method == run_method_S_0002) begin
unary_expr_00009_1 <= tmp_0015;
end
end
end
...ステートマシンや信号名に残っている run という文字列は、Java プログラム中の run メソッドのメソッド名からきています。
まとめ
簡単なプログラムを例に、プログラムがハードウェア・ロジックに変換される過程を紹介しました。Synthesijerの内部情報が変換する様子で、処理の雰囲気を味わっていただけたでしょうか。
次回は、いくつかの内部情報の変形処理の実装の詳細を説明する予定です。
わさらぼ・みよしたけふみ