XCSG解説集 — データフロー

解説集の索引はこちらをご参照下さい。

この記事では、データフローに関する XCSG スキーマの部分を扱います。データフローは XCSG の中で最も大きな部分であり、継続的に改善されています。特に、ポインタが関わるデータフローについて改善が進んでいます。スキーマの改善に合わせて、弊社はこの記事を定期的に更新します。

まず、データフローが XCSG でどのように表現されるかを確認します。

• XCSG.DataFlow_Edge: あるメモリ位置から別のメモリ位置へのデータ転送を表す XCSG.Edge です。ここでいうメモリ位置は、ソースコード中の定数または変数に対応します。これが次の説明につながります。
• XCSG.DataFlow_Node: メモリ位置に格納された値に対応する XCSG.Node です。値が定数であれば、それは変数または定数です。値がアドレスであれば、それはポインタです。

XCSG.DataFlow_Edge の a->b は、プログラムが a に対応する値にアクセスし、その後その値を b に格納することを表します。

データフローノードの構成

各 XCSG.ControlFlow_Node は、データフローが関与することがある実行文を表します。XCSG では、このデータフローは制御フローの中に「含まれる」ことになります。つまり、関係する変数を表す XCSG.DataFlow_Node は、XCSG.Contains エッジによって XCSG.ControlFlow_Node に接続されます。

クエリの例:

var dfg = <function>.contained().nodes(XCSG.DataFlow_Node).induce(universe.edges(XCSG.DataFlow_Edge)

このクエリは、関数の中に含まれるデータフローをすべて取得します。Mark Weiser が説明した手続き内スライスの計算を可能にします。

XCSG のデータフローノードは、おおよそ 3 つの分類に分けられます。1 つ目は読み書き操作に関するもの、2 つ目は算術演算に関するもの、3 つ目は論理演算に関するものです。加えて、読み書き操作は、ポインタまたは配列が関与するかどうかによって、さらに区別できます。この記事では、これらを同じ順序で説明します。読み書き、算術と論理、ポインタと配列です。

読み書き

• XCSG.Assignment: 変数への代入を表す XCSG.DataFlow_Node です。スライシングの文献では、これは「Definition」と呼ばれます。
• XCSG.Constant: ソースコード中の定数値を表す XCSG.DataFlow_Node です。

算術演算子と論理演算子

• XCSG.Operator: 1 つ以上の XCSG.DataFlow_Node に対する演算を表す XCSG.DataFlow_Node です。
• XCSG.UnaryOperator: 否定などの単項演算を表す XCSG.Operator ノードです。
• XCSG.BinaryOperator: 加算などの二項演算を表す XCSG.Operator ノードです。
• XCSG.leftOperand: XCSG.DataFlow_Node を XCSG.BinaryOperator ノードに接続する XCSG.DataFlow_Edge です。接続元のデータフローノードは左オペランドを表します。
• XCSG.rightOperand: XCSG.DataFlow_Node を XCSG.BinaryOperator ノードに接続する XCSG.DataFlow_Edge です。接続元のデータフローノードは右オペランドを表します。
• XCSG.Addition: 加算の演算を表す XCSG.Operator ノードです。

ポインタと配列

• XCSG.Pointer: ポインタ変数を表す XCSG.DataFlow_Node です。
• XCSG.ArrayRead: 配列の読み取りを表す XCSG.DataFlow_Node です。
• XCSG.ArrayWrite: 配列の書き込みを表す XCSG.DataFlow_Node です。