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に記載されている別のアルゴリズムがあります（免責事項：私は著者の一人です）。このアルゴリズムは、libFirm、OpenJDK、およびGoコンパイラで使用されています。

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