原文はこちら。
The original article was written by Paul Sandoz (Architect, Java at Oracle).
https://openjdk.org/projects/babylon/articles/code-models
コードリフレクション（code reflection）はJavaリフレクションの拡張であり、メソッド本体やラムダ本体内のJavaコードのシンボリック表現へのアクセスを可能にするものです。「Javaコードのシンボリック表現」というのは、一見すると難解に思えるかもしれませんが、その意味は簡単に理解できるでしょう。 これは、メソッド本体やラムダ本体のコードが、適切な構造で配置された特定のJavaクラスのインスタンスとして表現されたJavaコードのモデルです。これにより、Javaプログラムを操作するJavaプログラムを作成できます。コードリフレクションがどのようにしてJavaコードをモデリングするかを詳しく説明する前に、Javaコードのモデル化に関する2つの既存のアプローチについて説明する必要があります。
Java開発者は、Javaコンパイラと呼ばれる、Javaプログラムを操作するJavaプログラムを日々使用しています。Javaコンパイラは独自のJavaコードの内部モデルを持っており、そのインスタンスは抽象構文木(AST)と呼ばれます。ASTモデルは、Java言語仕様で規定されているJava文法と密接に整合しています。Javaコンパイラはソースプログラムのテキストを解析し、ASTを形成する特定のJavaクラスのインスタンスに変換します。そして、ASTを走査および操作してソースプログラムが正しいことを確認し、正しい場合はバイトコード命令を含むクラスファイルを生成します。
バイトコードはJavaコードの別のモデルです。Java仮想マシン仕様によって標準化されており、Javaランタイムが利用します。Javaコンパイラは、ASTモデルで特定のJavaクラスのインスタンスとして表現されたJava コードを、バイトコードモデルで特定のクラスとして表現されたJavaコードに変換します。その後、クラスファイルのコード属性を生成できます。OpenJDK HotSpotランタイムはC++プログラムであり、バイトコードを操作して解釈したり、その一部を実行可能なマシンコードにコンパイルしたりします。
ASTモデルとバイトコードモデルは、それぞれ異なる目的のためにあるため、両者は非常に異なる性質を持っています。しかし、ソースプログラム、AST、バイトコード、さらには生成された機械語コードは、すべて同じJavaプログラムを表しています。JavaコンパイラとHotSpotランタイムは、Javaコードの表現を操作する際に、Javaプログラムの意味を保持します。
ASTモデルもバイトコードモデルも、コードリフレクションの目的に適したモデルではありません。コードリフレクションのモデルは、Javaコードを取り込んで派生Javaコードや他言語コード（特別なJavaコード、GPUコード、SQL文など）を生成する多くのユースケースに広く適用できるものでなければなりません。ASTモデルだと、多くの情報（構文の詳細）を含むソースに近すぎ、バイトコードモデルは、有益な情報が削除された実行形式に近すぎ（型が消去され、構造が平坦化されている）るため、どちらも解析や変換が困難です。そのため、最新のコンパイラでは一般的に、ASTベースのモデルや命令ベース（スタックマシン）のモデルを解析や変換が容易なより適切なモデルに翻訳することが一般的です。 コードリフレクションのモデルの設計に関する重要な手がかりはここにあります。
Code model design
コードリフレクションにより、Javaコードの3番目のモデルが考案されました。そのインスタンスはコードモデルと呼ばれます。特定されたメソッドとラムダ本体のコードモデルは、Javaコンパイラが生成し、クラスファイルに格納され、リフレクションAPIを使い実行時にアクセス可能になります。Javaコンパイラは、バイトコード命令を生成するだけでなく、ASTをJavaコードモデルに変換します。このようなコードモデルでは、Javaプログラムの意味を保持しています。コードモデルには、ASTに存在するようなすべての構文の詳細は含まれませんが、バイトコードには存在しない型情報や構造情報は存在しています。コードモデルは、ASTとバイトコードの中間にあると考えるのがよいでしょう。最初の段階ではバイトコードよりはASTに近いものです（後ほど、コードモデルがどのように変換され、バイトコードに近づくかを説明します）。
コードモデルのデザインは、コードを表現するために多くの最新のコンパイラで使用されているデータ構造のデザインに大きく影響を受けています。これらのデータ構造は一般的に中間表現（Intermediate Representations、IR）と呼ばれています。デザインは、LLVM Compiler Infrastructureプロジェクトのサブプロジェクトであるマルチレベル中間表現（Multi-Level Intermediate Representation、MLIR）にも影響を受けていますが、このようなコンパイラと競合することを意図していません。コードモデルでは、Javaコードの忠実度の高いモデリング、中間レベルから高レベルでのコード操作、そして他のモデルやコンパイラツールチェーン（ネイティブまたはそれ以外）とのやりとりに注力します。コードリフレクションの特に難しい側面は、プログラミング言語理論やコンパイラの博士号を持たない有能なJava開発者にも、コードモデルのデザインとそれぞれのJava APIが広く利用可能であることを保証することです（ただし、博士号を持つ方々にもコードリフレクションを楽しんでいただけることを期待しています）。
コードモデルには、コード要素（code element）、オペレーション（operation）、本体（body）、ブロック（block）が含まれ、これらがツリーを形成します。オペレーションにはゼロ個以上の本体が、本体には1個以上のブロックが、ブロックには1個以上のオペレーションのシーケンスが含まれます。ブロックでは、ゼロ個以上のブロックパラメータである値を宣言できます。オペレーションでは、演算結果である値を宣言します。オペレーションでは、値を宣言後、その値をオペランドとして使用できます。値には型があります。
コードモデルは静的単一代入（Static Single Assignment、SSA）形式であり、値は1回のみ割り当てが可能です。本体内のブロックは相互に結びついており、制御フローグラフを形成します。 値も相互に結びついており、式グラフ（expression graph）または利用グラフ（use graph）を形成します。 演算結果とオペランドの関係は、式グラフの一部を形成します。 値とその値の利用の関係は、利用グラフの一部を形成します。
コードモデルのJava APIには、オペレーション、本体、ブロック、ブロックパラメータ、演算結果、値、および値の型に対応する Java クラスがあります。コードモデルは、ツリー走査をサポートするツリー構造に配置されたこれらのJavaクラスのインスタンスで構成されます。さらに、ブロックとブロック、演算結果とオペランド、および値と依存する値（依存する値の利用）を接続することで、モデルはグラフ走査もサポートします。
このシンプルなツリー構造を使用して、あるオペレーションに関連付けられたJavaクラスから拡張し、多くのJava言語構造をモデル化する特定のオペレーションを定義できます。したがって、多くのJavaプログラムをモデル化するコードモデルを構築できます。これは、一見意外に思えるかもしれません。みなさんは、operation（操作、演算）という用語を算術演算などのより一般的な意味で理解しているかもしれません。しかし、上述の構造を考慮すれば、この慣用的な意味に限定する必要はありません。 演算セマンティクスにより、メソッド宣言をモデル化するオペレーション、ラムダ式をモデル化するオペレーション、あるいは try 文をモデル化するオペレーションを定義することもできます。
コードモデルはイミュータブルです。コードモデルはビルドまたは既存のコードモデルを変換することで生成できます。変換（transform）は入力コードモデルを受け取り、出力コードモデルを生成します。入力コードモデルで遭遇する各入力オペレーションについて、出力コードモデルのビルダーにそのオペレーションを追加する（コピー）、追加しない（削除）、または新しい出力オペレーションの追加（置換または追加）を選択できます。
少し抽象的に思えるかもしれませんので、いくつかの例を見てみましょう。
この記事で紹介するすべてのコードは、Babylonリポジトリ内のテストソースで入手できます。
Code model access
2つの値を減算する以下のメソッド、subを考えてみましょう。
@CodeReflection
static double sub(double a, double b) {
return a - b;
}
メソッドのコードモデルがコンパイラによりビルドされ、リフレクションAPIを使用して実行時にアクセス可能であることを示すために、@CodeReflectionというアノテーションを付けます。
subのjava.lang.reflect.Methodインスタンスを見つけ、getCodeModelメソッドを呼び出してそのコードモデルを取得します。@CodeReflectionで注釈を付けたメソッドのみにコードモデルが存在するため、このメソッドは部分的なものです。
// Get the reflective object for method sub
Method m = ExpressionGraphs.class.getDeclaredMethod(
"sub", double.class, double.class);
// Get the code model for method sub
Optional<CoreOp.FuncOp> oModel = m.getCodeModel();
CoreOp.FuncOp model = oModel.orElseThrow();
Traversal of code model elements
subのコードモデルは、Javaメソッド宣言をモデル化する関数宣言のオペレーションに対応する、CoreOp.FuncOpのインスタンスとして表現されます。subのコードモデルはどのようなものになるでしょうか？モデル、ツリーを順にたどり、すべてのコード要素を出力することで、その様子を把握できます。
// Depth-first search, reporting elements in pre-order
model.traverse(null, (acc, codeElement) -> {
// Count the depth of the code element by
// traversing up the tree from child to parent
int depth = 0;
CodeElement<?, ?> parent = codeElement;
while ((parent = parent.parent()) != null) depth++;
// Print out code element class
System.out.println(" ".repeat(depth) + codeElement.getClass());
return acc;
});
traverseメソッドに渡される最初の引数は、結果を蓄積するために使用できるオブジェクトの初期値です。最終的に蓄積された結果が返されます。今回の場合蓄積する必要がないため、null値を渡します。
traverseメソッドは、モデル内で検出された各コード要素に対してラムダ式を呼び出し、要素のツリーの深さに比例したスペースを前置したクラス名を出力します。出力は以下のようになります。
class java.lang.reflect.code.op.CoreOp$FuncOp
class java.lang.reflect.code.Body
class java.lang.reflect.code.Block
class java.lang.reflect.code.op.CoreOp$VarOp
class java.lang.reflect.code.op.CoreOp$VarOp
class java.lang.reflect.code.op.CoreOp$VarAccessOp$VarLoadOp
class java.lang.reflect.code.op.CoreOp$VarAccessOp$VarLoadOp
class java.lang.reflect.code.op.CoreOp$SubOp
class java.lang.reflect.code.op.CoreOp$ReturnOp
ツリーの最上位は CoreOp.FuncOp であり、その中にBodyという1つの子要素があり、さらにその中に Blockという1つの子要素があり、さらにその中に一連のオペレーションが含まれていることがわかります。
traverseの実装では、コード要素を関数パラメータに適用し、その後、コード要素の子要素を再帰的に走査します。
default <T> T traverse(T t, BiFunction<T, CodeElement<?, ?>, T> v) {
t = v.apply(t, this);
for (C r : children()) {
t = r.traverse(t, v);
}
return t;
}
これまでに、コードモデルAPIがコード要素の2種類のツリー走査をサポートしていることを確認しました。
- up the tree （ツリーを上方向に走査）：コード要素の深さを計算した際に子から親に向かって走査
- down the tree（ツリーを下方向に走査）：
traverseメソッドの実装において親から子に向かって走査
コードモデルにおける値の走査については後述します。
Explanation of code models by printing them
コード要素のクラスを出力する走査は、特に有益なものではありません。コードモデルがどのようなものかを確認する優れた方法は、モデルを走査し、各コード要素についてより詳細な情報を出力することです。ありがたいことに、私たちはそのしくみを自作する必要はありません。モデルに対してtoTextメソッドを呼び出すと、文字列表現を返すので、それを出力すればよいのです。
System.out.println(model.toText());
以下のようなテキストが出力されます。
func @"sub" @loc="19:5:file:/.../ExpressionGraphs.java" (%0 : double, %1 : double)double -> {
%2 : Var<double> = var %0 @"a" @loc="19:5";
%3 : Var<double> = var %1 @"b" @loc="19:5";
%4 : double = var.load %2 @loc="21:16";
%5 : double = var.load %3 @loc="21:20";
%6 : double = sub %4 %5 @loc="21:16";
return %6 @loc="21:9";
};
コードモデルのテキストは人間が読めるように設計されており、モデルのデバッグやテストに非常に役立ちます。また、コードモデルの説明にも非常に有用です。本記事でも、このテキストを多用していきます。
デバッグを支援するために、各演算には行番号の情報があり、ルート演算にはコードモデルのソース情報もあります。
コードモデルのテキストから、コードモデルのルートは関数宣言（func）の演算であることがわかります。ラムダ式のような表現は、関数宣言演算の単一のボディと、エントリブロックと呼ばれるボディの最初で唯一のブロックの融合を表しています。次に、エントリブロックには一連の演算があります。各演算には対応するJavaクラスのインスタンスがあり、それらはすべて抽象クラスjava.lang.reflect.code.Opを継承します。これらは、クラスのコードモデルテキストを出力した際にすでに見ています。当然ながら、出力された演算とオペレーションクラスは、toTextメソッドがモデルをトラバースしたのと同じ順序でたどるため、同じ順序で発生します。
関数宣言の演算には、他のすべての演算と同様に演算結果がありますが、これはツリーのルートであり使用されないため、ここでは表示しません。
エントリブロックには、2つのブロックパラメータ、%0と%1があり、それぞれdouble型です。これは、パラメータaとbに対するメソッドsubの初期値を表します。メソッドパラメータ（変数）自体は、対応するブロックパラメータで初期化されるvar演算としてモデル化されます。var演算の結果は値（変数値）で、その型は変数型である Var<T> です。変数値は、変数の値である型Tの別の値を保持します。変数アクセス命令を使用してこの値をロードまたは格納でき、それぞれ変数を表す式と変数への代入をモデル化します。
Var<T>は一般的なJavaの型のように見えますが、そうではありません。コード・モデルで使用する演算の集合を定義できるように、型の集合も定義できます。Javaコードをモデル化するための演算の集合があり、Java型をモデル化するためのコード・モデルの型の集合もあります。さらに、ローカル変数のモデリングや、Java型のルールが適用されない複数の値（タプル）のグループ化など、Java以外の型も必要です。
パラメータaとbを表す式は、var.load演算としてモデル化されています。これらの演算の結果は、他の演算のオペランドとして使われます。同様に、後続の演算も結果を生成します。例えば、減算演算の結果である%6は、return演算のオペランドとして使用されます。
return演算には他の演算同様結果がありますが、この結果は意味のある使い方ができないため、デフォルトでは表示しません。
ここで、2つのスカラー値間の距離という単純な数式を計算する、少し複雑なメソッドdistance1について考えてみましょう。
@CodeReflection
static double distance1(double a, double b) {
return Math.abs(a - b);
}
これは先ほどのsubメソッドと似ていますが、引き算の結果を操作するMath.absを呼び出している点が異なります。この呼び出し（クラス呼び出しの式）は、コードモデルではどのように表現されるのでしょうか？あるいは、呼び出し式はどのようにモデル化されるのでしょうか？この質問に答えるために、前にやったようにコードモデルを出力してみましょう。
func @"distance1" @loc="24:5:file:/.../ExpressionGraphs.java" (%0 : double, %1 : double)double -> {
%2 : Var<double> = var %0 @"a" @loc="24:5";
%3 : Var<double> = var %1 @"b" @loc="24:5";
%4 : double = var.load %2 @loc="26:25";
%5 : double = var.load %3 @loc="26:29";
%6 : double = sub %4 %5 @loc="26:25";
%7 : double = invoke %6 @"java.lang.Math::abs(double)double" @loc="26:16";
return %7 @loc="26:9";
};
呼び出しはinvoke演算としてモデル化され、その結果をreturn演算のオペランドとして使用します。また、オペランドとしてsub演算の結果を受け取ります。invoke演算はメソッド参照を宣言し、Math.absメソッドをシンボリックに記述します。
この場合、オペランドの個数が記述されたメソッドパラメータの個数に一致するため、
invoke演算はクラス呼び出し式（静的メソッドの呼び出し）のモデルであることがわかります。インスタンス呼び出し式は、記述されたメソッドパラメーターの数より1つ多い数のオペランドを持ちます。ここで最初のオペランドはレシーバーです。
Code models and Static Single Assignment (SSA)
コードモデルはStatic Single Assignment (SSA) 形式であり、ソース・コードにあるような文（statement）と式（expression）の明確な区別はありません。ブロック・パラメーターと演算結果は、使用前に宣言され、再割り当てできません（したがって、変数をモデル化するには特別な演算と型が必要です）。メソッドdistance1をdistance1aのように書き換え、単純な式ごとに結果を新しいfinalローカル変数に代入し、その後その変数を使用するようなものです。
@CodeReflection
static double distance1a(final double a, final double b) {
final double diff = a - b;
final double result = Math.abs(diff);
return result;
}
開発者に対し、このようなコードを書くことを推奨しているわけではありません。ソースコードは読みやすく、保守しやすいものでなければなりません。コードモデルには異なる要件があるため、当然ながらモデルのテキスト（出力結果）は、その元となったソースコードほど読みやすく保守しやすいようにはデザインされていません。
メソッドdistance1aのコードモデルを出力してみましょう。
func @"distance1a" @loc="29:5:file:/.../ExpressionGraphs.java" (%0 : double, %1 : double)double -> {
%2 : Var<double> = var %0 @"a" @loc="29:5";
%3 : Var<double> = var %1 @"b" @loc="29:5";
%4 : double = var.load %2 @loc="31:29";
%5 : double = var.load %3 @loc="31:33";
%6 : double = sub %4 %5 @loc="31:29";
%7 : Var<double> = var %6 @"diff" @loc="31:9";
%8 : double = var.load %7 @loc="32:40";
%9 : double = invoke %8 @"java.lang.Math::abs(double)double" @loc="32:31";
%10 : Var<double> = var %9 @"result" @loc="32:9";
%11 : double = var.load %10 @loc="33:16";
return %11 @loc="33:9";
};
このモデルはdistance1のモデルとよく似ていますが、ローカル変数diffとresultをモデリングするvar演算が追加されている点が異なります。違いがあるにせよ、両メソッドとそのモデルは、（デバッグの影響を無視すれば）プログラムの動作という点では同等です。両モデルに対して純粋なSSA変換を実行し、それらを比較して確認してみましょう。
CoreOp.FuncOp ssaModel = SSA.transform(model);
このような変換は変数演算を取り除き、その結果の使用をオペランドに置き換えます。
以下は、変換後の2つのモデルです。
func @"distance1" @loc="24:5:file:/.../ExpressionGraphs.java" (%0 : double, %1 : double)double -> {
%2 : double = sub %0 %1 @loc="26:25";
%3 : double = invoke %2 @"java.lang.Math::abs(double)double" @loc="26:16";
return %3 @loc="26:9";
};
func @"distance1a" @loc="29:5:file:/.../ExpressionGraphs.java" (%0 : double, %1 : double)double -> {
%2 : double = sub %0 %1 @loc="31:29";
%3 : double = invoke %2 @"java.lang.Math::abs(double)double" @loc="32:31";
return %3 @loc="33:9";
};
場所の詳細の違いを除けば、2つのモデルは同一であり、特定のユースケースの分析が容易になっています。
SSA変換では、コピーされた演算の位置情報が保持されていることに注目してください。
Code models with simple control flow
Math.absのメソッド呼び出しを、条件演算子 ? : を使った（ほぼ）等価なインライン式に置き換えて、distance1bをさらに修正してみましょう。
@CodeReflection
static double distance1b(final double a, final double b) {
final double diff = a - b;
// Note, incorrect for negative zero values
final double result = diff < 0d ? -diff : diff;
return result;
}
これで、結果がローカル変数resultに代入される式の制御フローができました。条件演算子 ?: をどのようにモデリングしているのでしょうか？それを知るために、distance1bのモデルを出力してみましょう。
func @"distance1b" @loc="36:5:file:/.../ExpressionGraphs.java" (%0 : double, %1 : double)double -> {
%2 : Var<double> = var %0 @"a" @loc="36:5";
%3 : Var<double> = var %1 @"b" @loc="36:5";
%4 : double = var.load %2 @loc="38:29";
%5 : double = var.load %3 @loc="38:33";
%6 : double = sub %4 %5 @loc="38:29";
%7 : Var<double> = var %6 @"diff" @loc="38:9";
%8 : double = java.cexpression @loc="40:31"
()boolean -> {
%9 : double = var.load %7 @loc="40:31";
%10 : double = constant @"0.0" @loc="40:38";
%11 : boolean = lt %9 %10 @loc="40:31";
yield %11 @loc="40:31";
}
()double -> {
%12 : double = var.load %7 @loc="40:44";
%13 : double = neg %12 @loc="40:43";
yield %13 @loc="40:31";
}
()double -> {
%14 : double = var.load %7 @loc="40:51";
yield %14 @loc="40:31";
};
%15 : Var<double> = var %8 @"result" @loc="40:9";
%16 : double = var.load %15 @loc="41:16";
return %16 @loc="41:9";
};
java.cexpression演算が、条件演算子?:をモデル化しています。 java.cexpression演算は3つのボディを持ち、それぞれが1つのブロックを持ちます。条件演算子 ? : の各式はボディとしてモデル化されるため、制御フローに関連するコード構造を捕捉します。演算は、Java言語仕様で規定されているJavaプログラムの動作に従って、ボディ間で制御がどのように流れるかを指定します。より複雑なJava言語式や文をモデル化する多くの操作は、同じようなパターンに従います。
java.cexpression演算でモデルを処理するのが便利な場合もあれば、演算の振る舞いを理解する必要があるため、問題になる場合もあります。java.cexpression演算を、より基本的で一般的な形で操作の制御フローを明示的にモデル化する他のコード要素で置き換えることができます。そうした演算を低レベル化する変換を実行できます。
CoreOp.FuncOp loweredModel = model.transform(OpTransformer.LOWERING_TRANSFORMER);
transformメソッドはモデルを走査し、新しいモデルを構築します。これは、変換を実装する変換関数を引数として受け取ります。この場合、LOWERING_TRANSFORMERという変換関数は、java.cexpression演算のような、低レベル化可能な演算を低レベル化します（後で説明するforループをモデリングする演算など、低レベル化できる操作は他にもたくさんあります）。
低レベル化されたモデルを出力すると、置換されたコード要素がわかります。
func @"distance1b" @loc="36:5:file:/.../ExpressionGraphs.java" (%0 : double, %1 : double)double -> {
%2 : Var<double> = var %0 @"a" @loc="36:5";
%3 : Var<double> = var %1 @"b" @loc="36:5";
%4 : double = var.load %2 @loc="38:29";
%5 : double = var.load %3 @loc="38:33";
%6 : double = sub %4 %5 @loc="38:29";
%7 : Var<double> = var %6 @"diff" @loc="38:9";
%8 : double = var.load %7 @loc="40:31";
%9 : double = constant @"0.0" @loc="40:38";
%10 : boolean = lt %8 %9 @loc="40:31";
cbranch %10 ^block_1 ^block_2;
^block_1:
%11 : double = var.load %7 @loc="40:44";
%12 : double = neg %11 @loc="40:43";
branch ^block_3(%12);
^block_2:
%13 : double = var.load %7 @loc="40:51";
branch ^block_3(%13);
^block_3(%14 : double):
%15 : Var<double> = var %14 @"result" @loc="40:9";
%16 : double = var.load %15 @loc="41:16";
return %16 @loc="41:9";
};
func演算のボディに、^block_1、^block_2、^block_3という3つの新しいブロックが追加され、それらが相互につながっているのがよくわかります。これらが制御フローグラフを形成しています。
func演算のボディのエントリ・ブロックには、java.cexpression演算までの先行モデルと同じ演算が含まれています。そして、java.cexpression演算の最初のボディにある、最後の演算以外のすべての演算が、エントリ・ブロックに追加されています。java.cexpression演算の2番目のボディのすべての演算（最後の演算を除く）が^block_1に追加されています。java.cexpression演算の 3 番目のボディのすべての演算（最後の演算を除く）が ^block_2 に追加されています。最後に、^block_3には、java.cexpression演算の後に発生する先行モデルの同じ演算が含まれます。
java.cexpression演算の各ボディの最後の演算、yield演算は、分岐演算に置き換えられます。エントリ・ブロックは、ブーリアン・オペランドに基づいて、条件付きで^block_1または^block_2のいずれかの後継ブロックに分岐します。これらのブロックは両方とも無条件に後継の^block_3に分岐し、それぞれブロック引数として得た結果を渡します。^block_3には、java.cexpression演算の結果を置き換えるブロック・パラメータ %14 があります。
ブロック・パラメータ
%14は、2 つの制御フロー・パスから得られる値を表します。このような値は、他の中間表現におけるPHI(Φ)ノードやPHI命令に相当します。ブロック引数とブロック・パラメータは、関数の引数と関数パラメータのように見えます。ブロックは関数のように見えます。そして、ブロックへの分岐は、関数呼び出しや末尾呼出し（tail call）のように見えます。これは開発者にとって、PHIノードよりもはるかに理解しやすいものです。
ボディの子ブロックは、特定の順序、つまり、一般的にブロックがその後継（複数可）の前に発生する逆順で発生することが観察できます。この順序は制御フロー解析に有用です。
逆順は、制御フローグラフのブロックの位相的並べ替えです。
低レベル化されたモデルをSSA変換（先に紹介済み）で変換すると、よりシンプルなモデルになります。
func @"distance1b" @loc="36:5:file:/.../ExpressionGraphs.java" (%0 : double, %1 : double)double -> {
%2 : double = sub %0 %1 @loc="38:29";
%3 : double = constant @"0.0" @loc="40:38";
%4 : boolean = lt %2 %3 @loc="40:31";
cbranch %4 ^block_1 ^block_2;
^block_1:
%5 : double = neg %2 @loc="40:43";
branch ^block_3(%5);
^block_2:
branch ^block_3(%2);
^block_3(%6 : double):
return %6 @loc="41:9";
};
SSA変換は、lowering変換と同様にコード・モデル変換として実装されており、
SSA.transformメソッドで実装されているだけです。
3つのモデルとも、元のJavaプログラムと同じプログラム動作をします。
Code models with more complex control flow
距離関数を拡張し、N次元の2点間の距離を計算できるようにしてみましょう。
@CodeReflection
static double distanceN(double[] a, double[] b) {
double sum = 0d;
for (int i = 0; i < a.length; i++) {
sum += Math.pow(a[i] - b[i], 2d);
}
return Math.sqrt(sum);
}
次元数をループして、各次元間の距離の二乗を合計して、最終的な合計の平方根を返します。
for文をどのようにモデル化するのでしょうか？理解のために、distanceNのモデルを出力してみましょう。
func @"distanceN" @loc="44:5:file:/.../ExpressionGraphs.java" (%0 : double[], %1 : double[])double -> {
%2 : Var<double[]> = var %0 @"a" @loc="44:5";
%3 : Var<double[]> = var %1 @"b" @loc="44:5";
%4 : double = constant @"0.0" @loc="46:22";
%5 : Var<double> = var %4 @"sum" @loc="46:9";
java.for @loc="47:9"
()Var<int> -> {
%6 : int = constant @"0" @loc="47:22";
%7 : Var<int> = var %6 @"i" @loc="47:14";
yield %7 @loc="47:9";
}
(%8 : Var<int>)boolean -> {
%9 : int = var.load %8 @loc="47:25";
%10 : double[] = var.load %2 @loc="47:29";
%11 : int = array.length %10 @loc="47:29";
%12 : boolean = lt %9 %11 @loc="47:25";
yield %12 @loc="47:9";
}
(%13 : Var<int>)void -> {
%14 : int = var.load %13 @loc="47:39";
%15 : int = constant @"1" @loc="47:39";
%16 : int = add %14 %15 @loc="47:39";
var.store %13 %16 @loc="47:39";
yield @loc="47:9";
}
(%17 : Var<int>)void -> {
%18 : double = var.load %5 @loc="48:13";
%19 : double[] = var.load %2 @loc="48:29";
%20 : int = var.load %17 @loc="48:31";
%21 : double = array.load %19 %20 @loc="48:29";
%22 : double[] = var.load %3 @loc="48:36";
%23 : int = var.load %17 @loc="48:38";
%24 : double = array.load %22 %23 @loc="48:36";
%25 : double = sub %21 %24 @loc="48:29";
%26 : double = constant @"2.0" @loc="48:42";
%27 : double = invoke %25 %26 @"java.lang.Math::pow(double, double)double" @loc="48:20";
%28 : double = add %18 %27 @loc="48:13";
var.store %5 %28 @loc="48:13";
java.continue @loc="47:9";
};
%29 : double = var.load %5 @loc="50:26";
%30 : double = invoke %29 @"java.lang.Math::sqrt(double)double" @loc="50:16";
return %30 @loc="50:9";
};
java.for演算はfor文をモデル化したものです。Java言語仕様で規定されている文法では、4つの非終端記号に対応する4つのボディがあります。
BasicForStatement:
for ( [ForInit] ; [Expression] ; [ForUpdate] ) Statement
14.14.1には、14.14.1. The basic for Statementには、以下のような記述もあります。
The basic for statement executes some initialization code, then executes an Expression, a Statement, and some update code repeatedly until the value of the Expression is false.（基本
for文は、初期化コードを実行し、式、文、および更新コードを、式の値がfalseになるまで繰り返し実行する。）
14.14.1. The basicforStatement (https://docs.oracle.com/javase/specs/jls/se22/html/jls-14.html#jls-14.14.1)
最初のボディが初期化コードに対応していることがわかります。これは、ローカル変数iをモデリングする変数値を生成します。この変数値は、他のすべてのボディにパラメータとして渡されるため、他のボディはiにアクセスできます。
一般に、
forループはゼロ個以上のローカル変数を宣言できるので、最初のボディはゼロ個以上の変数値を生成できます。コードモデルは、複数の戻り値のグループ化や、複数の結果を生成する演算を明示的にサポートしていないため、2つ以上の変数値は、収得されたタプル値にラップされます。
2番目のボディは、ローカル変数iが配列の長さより小さいかどうかをチェックするコードをモデル化した式に対応します。3番目のボディは、iをインクリメントする更新のためのコードに対応します。そして、4番目のボディは、各次元の中間計算を実行する文に対応します。
distance1bのコードモデルと同じように、java.for演算を他のコード要素に置き換えることができます。低レベル化されたモデルをプリントアウトすると、置換されたコード要素がわかります。
func @"distanceN" @loc="44:5:file:/.../ExpressionGraphs.java" (%0 : double[], %1 : double[])double -> {
%2 : Var<double[]> = var %0 @"a" @loc="44:5";
%3 : Var<double[]> = var %1 @"b" @loc="44:5";
%4 : double = constant @"0.0" @loc="46:22";
%5 : Var<double> = var %4 @"sum" @loc="46:9";
%6 : int = constant @"0" @loc="47:22";
%7 : Var<int> = var %6 @"i" @loc="47:14";
branch ^block_1;
^block_1:
%8 : int = var.load %7 @loc="47:25";
%9 : double[] = var.load %2 @loc="47:29";
%10 : int = array.length %9 @loc="47:29";
%11 : boolean = lt %8 %10 @loc="47:25";
cbranch %11 ^block_2 ^block_4;
^block_2:
%12 : double = var.load %5 @loc="48:13";
%13 : double[] = var.load %2 @loc="48:29";
%14 : int = var.load %7 @loc="48:31";
%15 : double = array.load %13 %14;
%16 : double[] = var.load %3 @loc="48:36";
%17 : int = var.load %7 @loc="48:38";
%18 : double = array.load %16 %17;
%19 : double = sub %15 %18 @loc="48:29";
%20 : double = constant @"2.0" @loc="48:42";
%21 : double = invoke %19 %20 @"java.lang.Math::pow(double, double)double" @loc="48:20";
%22 : double = add %12 %21 @loc="48:13";
var.store %5 %22 @loc="48:13";
branch ^block_3;
^block_3:
%23 : int = var.load %7 @loc="47:39";
%24 : int = constant @"1" @loc="47:39";
%25 : int = add %23 %24 @loc="47:39";
var.store %7 %25 @loc="47:39";
branch ^block_1;
^block_4:
%26 : double = var.load %5 @loc="50:26";
%27 : double = invoke %26 @"java.lang.Math::sqrt(double)double" @loc="50:16";
return %27 @loc="50:9";
};
java.for演算とjava.cexpression演算は、それぞれ独自の置換を実装しています。対応する演算クラスは、各演算が実装する抽象メソッドlowerを宣言するOp.Lowerableインターフェースを継承しています。
func演算のボディには制御フローグラフが含まれています。^block_3が^block_1に分岐している点に着目してください。これは一般的に後方分岐（back branch）と呼ばれるもので、ループの継続をモデル化しています。
単純化されたモデルを再度SSA変換すると、さらに単純化されたモデルが得られます。
func @"distanceN" @loc="44:5:file:/.../ExpressionGraphs.java" (%0 : double[], %1 : double[])double -> {
%2 : double = constant @"0.0" @loc="46:22";
%3 : int = constant @"0" @loc="47:22";
branch ^block_1(%2, %3);
^block_1(%4 : double, %5 : int):
%6 : int = array.length %0 @loc="47:29";
%7 : boolean = lt %5 %6 @loc="47:25";
cbranch %7 ^block_2 ^block_4;
^block_2:
%8 : double = array.load %0 %5;
%9 : double = array.load %1 %5;
%10 : double = sub %8 %9 @loc="48:29";
%11 : double = constant @"2.0" @loc="48:42";
%12 : double = invoke %10 %11 @"java.lang.Math::pow(double, double)double" @loc="48:20";
%13 : double = add %4 %12 @loc="48:13";
branch ^block_3;
^block_3:
%14 : int = constant @"1" @loc="47:39";
%15 : int = add %5 %14 @loc="47:39";
branch ^block_1(%13, %15);
^block_4:
%16 : double = invoke %4 @"java.lang.Math::sqrt(double)double" @loc="50:16";
return %16 @loc="50:9";
};
^block_1には現在2個のブロックパラメータ（%4と%5）があり、これらはそれぞれ現在のループ反復のローカル変数sumとiの値に対応しています。^block_3 の後方分岐では、次のループ反復で使用される値がブロック引数として渡されます。
同じブロック内で先に定義されている場合、またはドミネートブロック内で定義されている場合、値を演算で使用できます。これゆえ、
^block_1が^block_2および^block_4を支配しているため、^block_2のadd演算または^block_4のinvoke演算で%4を使用できます。構造化制御フロー操作と純粋なSSA形式は、互いに排他的ではありません。コードモデル設計自体にはそのような制限はありませんが、コードフローを持つJava式や文をモデル化することはありません（コードモデルを使用して非Javaプログラムをモデル化する例として、Tritonを参照してください）。
Exploring Triton GPU programming for neural networks in Java
https://openjdk.org/projects/babylon/articles/triton
https://logico-jp.io/2024/04/07/exploring-triton-gpu-programming-for-neural-networks-in-java/
Expression graphs and use graphs
これまでは、コードモデルの要素（オペレーション、ボディ、ブロック）のツリー走査について説明してきました。コードモデルの項目を走査する方法は他にもあり、具体的には値の走査があります。 操作結果が与えられれば、その演算のオペランドである値などを走査し式グラフを生成できます。 また、その逆も考えられます。 値が与えられれば、その値をオペランドとして使用する操作の結果を走査し、さらに利用グラフを生成できます。
複数の演算が同じ値をオペランドとして使用することがあるため、これは式グラフです。式グラフには循環はあり得ないため、非循環グラフです。概念的には、式グラフはコードモデルを上方向にたどります。
値が複数の演算で使用され、それらの演算結果がすべて別の演算で使用されることがあるため、これは利用グラフです。利用グラフにも循環は存在しないため、非循環グラフでもあります。概念的には、利用グラフはコードモデルを下方向にたどります。
このセクションでは、式グラフと利用グラフの走査方法、単純なグラフ構造の構築方法を紹介しましょう。まず、グラフのノードを表すrecordクラスを宣言します。ノードには、ノードに関連付けられた値と、他のノードへの出発エッジのリストという2つのコンポーネントがあります。
record Node<T>(T value, List<Node<T>> edges) {
}
次に、与えられた値に対する式グラフを計算するメソッド、expressionGraphを実装します。
static Node<Value> expressionGraph(Value value) {
return expressionGraph(new HashMap<>(), value);
}
static Node<Value> expressionGraph(Map<Value, Node<Value>> visited, Value value) {
// If value has already been visited return its node
if (visited.containsKey(value)) {
return visited.get(value);
}
// Find the expression graphs for each operand
List<Node<Value>> edges = new ArrayList<>();
for (Value operand : value.dependsOn()) {
edges.add(expressionGraph(operand));
}
Node<Value> node = new Node<>(value, edges);
visited.put(value, node);
return node;
}
ある値が与えられた場合、その値に対応するノードのエッジは、その値が依存する値の集合に対して式グラフを再帰的に計算することで生成されるノードです。値が演算結果である場合、その集合は演算のオペランドの集合です。集合である理由は、演算が2つ以上のオペランドとして2回以上値を使用することがあるからです。値がブロックパラメータである場合、他の値に依存しないため、集合は空です。グラフを作成しているため、すでにその値を走査済みであるかどうかも確認する必要があります。走査済みであれば、対応するノードを再利用します。
expressionGraphの代替実装として、値のチェックを明示的に実行するものを示すことは有益ではあるのですが、一般的には代わりにValue.dependsOnメソッドを使用することが推奨されます。
static Node<Value> expressionGraph(Map<Value, Node<Value>> visited, Value value) {
// If value has already been visited return its node
if (visited.containsKey(value)) {
return visited.get(value);
}
List<Node<Value>> edges;
if (value instanceof Op.Result result) {
edges = new ArrayList<>();
// Find the expression graphs for each operand
Set<Value> valueVisited = new HashSet<>();
for (Value operand : result.op().operands()) {
// Ensure an operand is visited only once
if (valueVisited.add(operand)) {
edges.add(expressionGraph(operand));
}
}
// TODO if terminating operation find expression graphs
// for each successor argument
} else {
assert value instanceof Block.Parameter;
// A block parameter has no outgoing edges
edges = List.of();
}
Node<Value> node = new Node<>(value, edges);
visited.put(value, node);
return node;
}
所与の値に対して、演算結果のインスタンスであるかどうかをテストします。インスタンスであったとすれば、対応するノードのエッジは、演算のオペランドに対する式グラフを再帰的に計算して生成されたノードです。違ったとすれば、値はブロックパラメータのインスタンスであり、エッジを持たないノードが作成されます。
これは演算がブロック内で終了、もしくは継続する演算である場合、TODOコメントは、演算結果が演算のオペランドと後続の引数に依存することを示しています。メソッド
Op.Result.dependsOnはオペランドと後続の引数の集合を返します。メソッドdistance1bとdistanceNの低レベルコードモデルを調べたときにすでにこうした演算、分岐演算、を見てきました。
最後に、メソッドuseGraphを実装します。これは所与の値に対する利用グラフを計算するものです。
static Node<Value> useGraph(Value value) {
return useGraph(new HashMap<>(), value);
}
static Node<Value> useGraph(Map<Value, Node<Value>> visited, Value value) {
// If value has already been visited return its node
if (visited.containsKey(value)) {
return visited.get(value);
}
// Find the use graphs for each use
List<Node<Value>> edges = new ArrayList<>();
for (Op.Result use : value.uses()) {
edges.add(useGraph(visited, use));
}
Node<Value> node = new Node<>(value, edges);
visited.put(value, node);
return node;
}
メソッドuseGraphは、メソッドexpressionGraphと類似の構造ではありますが、対応するノードのエッジは、利用された値に対する利用グラフを再帰的に計算することで作成されたノードである点が異なります。
それでは、以前紹介したモデルの一部について、グラフを生成してみましょう。distance1をもう一度見てみましょう。return演算の式グラフはどのようなものになるでしょうか。グラフを計算してコードモデルとともに比較のために出力してみましょう。
CoreOp.FuncOp model = ...;
// Create the expression graph for the terminating operation result
Op.Result returnResult = model.body().entryBlock().terminatingOp().result();
Node<Value> returnGraph = expressionGraph(returnResult);
// Transform from Node<Value> to Node<String> and print the graph
System.out.println(returnGraph.transformValues(v -> printValue(names, v)));
@CodeReflection
static double distance1(double a, double b) {
return Math.abs(a - b);
}
func @"distance1" @loc="24:5:file:/.../ExpressionGraphs.java" (%0 : double, %1 : double)double -> {
%2 : Var<double> = var %0 @"a" @loc="24:5";
%3 : Var<double> = var %1 @"b" @loc="24:5";
%4 : double = var.load %2 @loc="26:25";
%5 : double = var.load %3 @loc="26:29";
%6 : double = sub %4 %5 @loc="26:25";
%7 : double = invoke %6 @"java.lang.Math::abs(double)double" @loc="26:16";
%8 : void = return %7 @loc="26:9";
};
%8 : void = return %7 @loc="26:9";
└── %7 : double = invoke %6 @"java.lang.Math::abs(double)double" @loc="26:16";
└── %6 : double = sub %4 %5 @loc="26:25";
├── %4 : double = var.load %2 @loc="26:25";
│ └── %2 : Var<double> = var %0 @"a" @loc="24:5";
│ └── %0 <block parameter>
└── %5 : double = var.load %3 @loc="26:29";
└── %3 : Var<double> = var %1 @"b" @loc="24:5";
└── %1 <block parameter>
グラフをツリーとして出力している点に着目してください。ノードに複数の出力（外向）エッジがある場合、複数回以上出力されますが、今回はサイクルがないため問題ではありません。この場合、式グラフはツリーで、それぞれのルートではないノードには入力（内向）エッジがあります。
式グラフが抽象構文木（abstract syntax tree）と非常に似ていることがわかります。このようなツリーは、最初はそれほど明白ではないとしても、コードモデルにも存在していることが分かります。 出力した式ツリーの行を逆にして、ブロックパラメータに関連する行を削除すると、関数宣言操作の操作と似た順序が現れます。
各関数パラメータの利用グラフはどのようなものになるでしょうか？ 同様に、2つの利用者グラフを計算して出力してみましょう。
for (Block.Parameter parameter : model.parameters()) {
Node<Value> useNode = useGraph(parameter);
System.out.println(useNode.transformValues(v -> printValue(names, v)));
}
@CodeReflection
static double distance1(double a, double b) {
return Math.abs(a - b);
}
%0 <block parameter>
└── %2 : Var<double> = var %0 @"a" @loc="24:5";
└── %4 : double = var.load %2 @loc="26:25";
└── %6 : double = sub %4 %5 @loc="26:25";
└── %7 : double = invoke %6 @"java.lang.Math::abs(double)double" @loc="26:16";
└── %8 : void = return %7 @loc="26:9";
%1 <block parameter>
└── %3 : Var<double> = var %1 @"b" @loc="24:5";
└── %5 : double = var.load %3 @loc="26:29";
└── %6 : double = sub %4 %5 @loc="26:25";
└── %7 : double = invoke %6 @"java.lang.Math::abs(double)double" @loc="26:16";
└── %8 : void = return %7 @loc="26:9";
利用グラフは、関数宣言演算における演算と同じ順序に従います。また、利用グラフは式グラフのサブグラフ（この場合は逆パス）であることもわかります。
コードモデル内のすべての値について式グラフを計算したい場合はどうすればよいでしょうか。expressionGraphメソッドをすべての値に適用したり、あるいは、コードモード要素を走査して、コード要素クラスを出力するのと同じやり方ですべての式グラフを計算する、といったアプローチがあります。
static Map<Value, Node<Value>> expressionGraphs(CoreOp.FuncOp f) {
return expressionGraphs(f.body());
}
static Map<Value, Node<Value>> expressionGraphs(Body b) {
// Traverse the model building structurally shared expression graphs
return b.traverse(new LinkedHashMap<>(), (graphs, codeElement) -> {
switch (codeElement) {
case Body _ -> {
// Do nothing
}
case Block block -> {
// Create the expression graphs for each block parameter
// A block parameter has no outgoing edges
for (Block.Parameter parameter : block.parameters()) {
graphs.put(parameter, new Node<>(parameter, List.of()));
}
}
case Op op -> {
// Find the expression graphs for each operand
List<Node<Value>> edges = new ArrayList<>();
for (Value operand : op.result().dependsOn()) {
// Get expression graph for the operand
// It must be previously computed since we encounter the
// declaration of values before their use
edges.add(graphs.get(operand));
}
// Create the expression graph for this operation result
graphs.put(op.result(), new Node<>(op.result(), edges));
}
}
return graphs;
});
}
switch文は網羅的であり、default節は必要ありません。、Body、Blockは、それらの先行クラスのみを許可する、シールされた抽象クラスOpCodeElementから拡張しています。
このアプローチが機能するのは、コード要素が特定の順序で走査され、値が使用前に宣言されるためです。したがって、以前のように訪問済みの値を追跡する必要はありません。オペランドのノードは、グラフに存在することが保証されています（ノードへの値のマップ）。このアプローチでは、ノードのインスタンスを共有できるため、各値に対して直接式グラフを作成するよりも効率的です。
コードモデルがイミュータブルなので、計算された式グラフは安定しており、関連付けられたモデルと同期が取れなくなることはありません。
両方法で同じグラフを生成されたかどうかを確認するには、両方法で計算したreturn演算の式グラフを比較すれば簡単にできます。
// Create the expression graphs for all values
Map<Value, Node<Value>> graphs = expressionGraphs(model);
// The graphs for the terminating operation result are the same
assert returnGraph.equals(graphs.get(returnGraph.value()));
equalsメソッドを自動的に実装するレコードの機能に依存しています。
Root expression graphs and trees
式グラフを作成する方法がわかったので、例えば、コードモデルの文や式をモデル化した部分を特定するような、特定のルールに基づいてグラフを分類し、操作することができるようになりました。なぜこのようなことが必要なのでしょうか？解析のためにコードモデルを解析する方法の詳細を提示する以外に、これには実用的な使い道があるからです。具体的には、コード・モデルのCソース・コードへの変換です。2個のユースケースが思い浮かびます。
Babylon GPUの研究では、コード・モデルをGPUカーネル（GPUハードウェア上で実行されるメソッド）に変換する必要があります。
HAT (Heterogeneous Accelerator Toolkit) Project
https://github.com/openjdk/babylon/tree/code-reflection/hat
1つのアプローチは、コード・モデルをOpenCL CソースまたはCUDA Cソースに変換し、GPU固有のツールチェーンを使ってコンパイルすることです。変換されたソースは、デバッグを容易にし、コンパイラが最適化しやすいように、idiomatic（手書きとほぼ同じ）であることが望ましいのです（idiomatic、慣用的なコードの方が最適化しやすいため）。文をモデル化する式グラフを特定することは、慣用的なCコードの生成に有用です。
バビロンGPUの研究では、SPIRVまたはPTX命令で構成されるカーネルへのコードモデルの変換も探求しています。それによって、多くの選択肢を徹底的に探求し、コード・リフレクションが目的に適合していることを確認することに貢献しています。
Foreign Function and Memory API (Project Panama) は、Javaメソッドとネイティブ関数ポインタのバインディングをサポートし、Javaメソッドをその関数ポインタ経由でネイティブに呼び出すことができます。このような呼び出しは一般にアップコールと呼ばれます。Panamaのアップコールは非常に効率的ですが、ネイティブからJavaへ、そしてまたJavaからネイティブへという遷移にはコストがかかります。Javaメソッドのコード・モデルにアクセスし、それをCコードに変換し、ネイティブ・コードにコンパイルし、関数ポインタをそのネイティブ・コードにバインドすることができれば、この移行をなくすことができます。これは、単純な式と文を持つJavaメソッド、例えば、振る舞いが入力の関数であるメソッドにのみ適用できる可能性が高いと思われます。繰り返しになりますが、文をモデル化する式グラフの特定は、Javaメソッドが変換やイディオマティックなCコードの生成に適用できるかどうかを判断するのに役立ちます。
これら2つのユースケースを念頭に置いて、さらに式の分析に集中しましょう。すべての式グラフが与えられたら、それらをフィルタリングして、ルートとみなされるグラフを選択できます。最初にルート式グラフを、ルート・ノードの値に用途がないグラフと定義しましょう。すると、以下のようにグラフをフィルターできます。
// Filter for root graphs, operation results with no uses
List<Node<Value>> rootGraphs = graphs.values().stream()
.filter(n -> n.value() instanceof Op.Result opr &&
switch (opr.op()) {
// An operation result with no uses
default -> opr.uses().isEmpty();
})
.toList();
後ほど、
switch文に別のcaseを追加する予定です。
このセクションでは、2個の平方間の差を計算するもう一つのメソッドであるsquareDiffに着目します。
@CodeReflection
static double squareDiff(double a, double b) {
// a^2 - b^2 = (a + b) * (a - b)
final double plus = a + b;
final double minus = a - b;
return plus * minus;
}
同様に、distance1aのように、複数の変数宣言文を使ってメソッドを構成します。さらに、パラメータaとbが複数回使われています。これらの特徴により解析がうまく行きます。squareDiffメソッドには、return操作に関連する、以下のようなルート式グラフが1つ含まれています。
%15 : void = return %14 @loc="58:9";
└── %14 : double = mul %12 %13 @loc="58:16";
├── %12 : double = var.load %7 @loc="58:16";
│ └── %7 : Var<double> = var %6 @"plus" @loc="56:9";
│ └── %6 : double = add %4 %5 @loc="56:29";
│ ├── %4 : double = var.load %2 @loc="56:29";
│ │ └── %2 : Var<double> = var %0 @"a" @loc="53:5";
│ │ └── %0 <block parameter>
│ └── %5 : double = var.load %3 @loc="56:33";
│ └── %3 : Var<double> = var %1 @"b" @loc="53:5";
│ └── %1 <block parameter>
└── %13 : double = var.load %11 @loc="58:23";
└── %11 : Var<double> = var %10 @"minus" @loc="57:9";
└── %10 : double = sub %8 %9 @loc="57:30";
├── %8 : double = var.load %2 @loc="57:30";
│ └── %2 : Var<double> = var %0 @"a" @loc="53:5";
│ └── %0 <block parameter>
└── %9 : double = var.load %3 @loc="57:34";
└── %3 : Var<double> = var %1 @"b" @loc="53:5";
└── %1 <block parameter>
このメソッドには3つの文、2つの変数宣言文とreturn文がありますが、ルート式グラフは1つしかないことに注意してください。
また、このグラフには変数宣言演算の結果が含まれています。ローカル変数宣言文（値%7と%11はそれぞれローカル変数plusとminusを表す）と、メソッドのパラメータ宣言（値%2と%3はそれぞれパラメータaとbを表す）がモデル化されています。この結果は、ローカル変数とパラメータを表す式をモデリングする変数ロード演算で使用されます。変数宣言はreturn文の一部ではありませんが、モデル化された演算はルート式グラフに存在します。
グラフがツリーとして描画されるため、メソッドのパラメータ宣言をモデル化した演算は2回発生します。
各文に対して明確なルート式グラフを作成するには、
- ルート式グラフの集合を拡張する
- 文に直接関連しない変数宣言演算に対応するノードを削除してグラフを刈り込む
の2つを行う必要があります。
ルート式グラフのセットを拡張して、操作が変数宣言操作であるもの、より具体的には、変数値を初期化するために使用される値が操作結果である場合のみを含めます（それによって、初期化するために使用される値がブロック・パラメータであるメソッド・パラメータをモデル化する変数値を含めないようにします）。
List<Node<Value>> rootGraphs = graphs.values().stream()
.filter(n -> n.value() instanceof Op.Result opr &&
switch (opr.op()) {
// Variable declarations modeling local variables
case CoreOp.VarOp vop ->
vop.operands().get(0) instanceof Op.Result;
// An operation result with no uses
default -> opr.uses().isEmpty();
})
.toList();
メソッドexpressionGraphsを拡張し、コピーと修正を行い、新しいメソッドprunedExpressionGraphsを作成して、グラフを刈り込みます。
static Map<Value, Node<Value>> prunedExpressionGraphs(CoreOp.FuncOp f) {
return prunedExpressionGraphs(f.body());
}
static Map<Value, Node<Value>> prunedExpressionGraphs(Body b) {
// Traverse the model building structurally shared expression graphs
return b.traverse(new LinkedHashMap<>(), (graphs, codeElement) -> {
switch (codeElement) {
case Body _ -> { ... }
case Block block -> { ... }
// Prune graph for variable load operation
case CoreOp.VarAccessOp.VarLoadOp op -> {
// Ignore edge for the variable value operand
graphs.put(op.result(), new Node<>(op.result(), List.of()));
}
// Prune graph for variable store operation
case CoreOp.VarAccessOp.VarStoreOp op -> {
// Ignore edge for the variable value operand
// Add edge for value to store
List<Node<Value>> edges = List.of(graphs.get(op.operands().get(1)));
graphs.put(op.result(), new Node<>(op.result(), edges));
}
case Op op -> { ... }
}
return graphs;
});
}
コード要素がそれぞれ、変数ロード演算または変数ストア演算のインスタンスであるかどうかをチェックする 2 つの新しいケースが追加されました。変数ロード演算の場合、単一のオペランドが変数値に対応するため、エッジを持たない新しいノードを作成します。変数ストア演算では、最初のオペランド（ストアする値）に対応する1つのエッジを持つ新しいノードを作成します。
スイッチはまだ網羅的であることに注意してください。新しい2つのケースは、より一般的な演算のケースを支配しています。あるいは、より一般的な演算のケースで、従属値が演算結果のインスタンスであるかどうか、演算が変数宣言のインスタンスであるかどうかをチェックして、同じ動作を実装することもできました。しかし、上記の実装の方がより有益だと考えています。
これらの拡張により、3つのルート式グラフを計算できるようになりました。
@CodeReflection
static double squareDiff(double a, double b) {
// a^2 - b^2 = (a + b) * (a - b)
final double plus = a + b;
final double minus = a - b;
return plus * minus;
}
%7 : Var<double> = var %6 @"plus" @loc="56:9";
└── %6 : double = add %4 %5 @loc="56:29";
├── %4 : double = var.load %2 @loc="56:29";
└── %5 : double = var.load %3 @loc="56:33";
%11 : Var<double> = var %10 @"minus" @loc="57:9";
└── %10 : double = sub %8 %9 @loc="57:30";
├── %8 : double = var.load %2 @loc="57:30";
└── %9 : double = var.load %3 @loc="57:34";
%15 : void = return %14 @loc="58:9";
└── %14 : double = mul %12 %13 @loc="58:16";
├── %12 : double = var.load %7 @loc="58:16";
└── %13 : double = var.load %11 @loc="58:23";
3つのルート式グラフが、squareDiffメソッドの3つの文に順番に対応していることに注目してください。これらのグラフはルート式ツリーでもあり、このようなツリーから慣用的なC言語のコードを生成することも可能なはずです。
代入式をサポートし、代入式の文と区別したい場合は、ルールを拡張する必要があります。その調査はまた別の日にしましょう。
Logico Inside 