compiler-construction - AST を SSA に変換できますか、それとも CFG に変換してから SSA に変換する必要がありますか?

Question

抽象構文ツリーを SSA フォームに直接変換できますか?それとも、制御フロー グラフを作成してから、CFG から静的単一割り当てフォームを作成する必要がありますか?

制御フロー グラフのコンテキストでは、これを C ライクなプログラムでどのように表現すればよいでしょうか。すべての関数のすべての基本ブロックの CFG のグラフを保存できると考えていますが、たとえば関数を呼び出すと、事態が複雑になる可能性があります。私が考えることができる別の方法は、プログラム全体、つまりすべてのソースファイルの CFG ですが、関数に関する情報をどのように保存すればよいでしょうか? 関数へのポインターを基本ブロック (つまり、親ノード) に格納できますか?

CFG から SSA を生成する場合、ステートメントの制御フローを表す CFG について心配する必要はありますか? 基本的なブロック制御フローを表すだけでよいと考えています。

Answer 1

はい、最初に CFG を構築せずに SSA フォームを作成できますが、Cytron らによる従来の SSA 構築アルゴリズムを使用してそれを行うことはできません。論文Simple and Efficient Construction of Static Single Assignment Form で説明されている別のアルゴリズムがあります(免責事項: 私は著者の 1 人です)。このアルゴリズムは、libFirm、OpenJDK、および Go コンパイラで使用されます。

ほとんどのコンパイラ (afaik) は、関数ごとに 1 つの CFG モデルを使用します。各基本ブロックはノードです。ステートメント (操作/命令など) は、1 つの基本ブロックに属します。一部の命令は、各基本ブロック内にリストとして格納されます。一部の命令は、CFG に似た部分的に順序付けられたグラフとして格納されます。