問題タブ [ssa]

私はスタック マシン (具体的にはCIL ) のコンパイラに取り組んでおり、コードを基本ブロックのグラフに解析しました。ここからメソッドにSSAを適用しようとしていますが、なかなかうまくいきません。私の最初の試み (グラフではなくフラットなリストで作業している間) は、コードを反復処理し、SSA ID のスタック (つまり、割り当てターゲット用) を保持し、割り当てを生成するときにそれらをプッシュし、割り当て時にそれらをポップすることでした。それらは使用されています。これは、単一の基本ブロックに対しては問題なく機能しますが、Φ 関数の生成を処理する方法がわかりません。

私が思いついたアイデアは、SSA ID にスタック位置をアタッチし、コード パスが収束したときにまだスタック上にあるものを調べることですが、これは物事を行う正しい方法 (TM) とは思えません。

複数のコード パスにわたるスタック操作を追跡し、それらが収束したときに衝突を判断するための単純なアルゴリズムはありますか?

これは私がこれまでに思いついたものです：

gcc 関連:

• ツリーの SSA
• Tree SSA – GCC の新しい最適化フレームワーク
• Tree SSA GCC の新しい最適化インフラストラクチャ
• ツリー SSA の設計と実装

他の：

• マシン SUIF のスパース条件付き定数伝播の実装
• 明示的並列プログラムのための同時静的単一代入形式と定数伝搬

私はこれをコミュニティ wiki にしました。ご自由に独自のリソースを追加してください - ありがとう!

例：

次のx86をSSA形式で表す方法：

いくつかの疑似関数を導入することで、私は次のことを思いつきます。

しかし、私はそれがあまりにも冗長だと思います

RSASSA-PKCS1-v1.5Javaで署名を生成する方法を誰か教えてもらえますか?

私は、実際、java.security.Signatureクラスでどのようにすればよいか知りたいです。

サードパーティのライブラリを使用する必要がありますか?

静的単一代入（SSA）形式のIRへのレジスタベースのバイトコード用のコンパイラを作成しています（具体的には、DalvikVMバイトコードからLLVMIRまでですが、一般的なトピックについて質問が受けられることを期待しています）。これを実行するための最良の、または理論的に最もクリーンな方法を考えています。

たとえば、レジ​​スタベースの命令がある場合：

そうすると、vAの古い値は上書きされてvD --vEに置き換えられたため、使用できなくなります。

SSA形式では、次のようなものがあります

各変数は1回だけ割り当てられるためです。

問題は、レジスタベースの言語からのマッピングでは、各レジスタの最新の値のみを使用するため、SSAフォームが追跡するこれらの以前の値を必要としないことです。私には、決して使用しない新しい変数を作成し続けることは悪い習慣、または単に「汚い」ように思えますが、それが表現で得られるものだと思います。

したがって、私の質問は、このマッピングを実現するための最良の方法は何ですか（少し主観的です、申し訳ありません）。私の当初の考えは、各メソッドに使用される（固定された）レジスタの数を知っているので、各レジスタの最新の値を追跡し、それだけを使用できるというものでしたが、それがどのように行われるかはわかりません。実践的に働きます。

ご意見をお待ちしております。

私は自分が書いているコンパイラーのためにSSA構築を実装しています。SSAアルゴリズムには理解できないことがあります（Cytronの論文とAWAppelによる第2版の本「 ModernCompilerImplementation inJava」を使用）。変数yが1つの直線制御フローパスで初めて定義された（そして使用された）が、別の並列パスでは定義されなかった場合はどうなりますか。ジョインポイント（定義するブロックの支配辺境y）にPHI関数を挿入する必要がありますか？

たとえば、ブロックBには、の最初の定義がありyます。ブロックCの先頭に2つのオペランド（入力制御フローパスごとに1つ）を持つPHI命令を挿入する必要がありますか？次に、SSAの名前変更について：定義されA -> Cていないパス（Bを経由しない）からのオペランドにどのように名前を付けますか？y

私は、SSA を使用して指定された IR コードを調べてきました。特に、この形式で LLVM IR を生成しています。ただし、自明ではないコピー セマンティクスを持つ型が提示された場合に、これが効果的かどうかについては混乱しています。例えば、

この SSA 形式では、少なくとも最も明白なレベルでは、(C++ の場合でも) 厄介なコピーの混乱が生じます。LLVM などのオプティマイザーは、実際にこのケースを正確に最適化できますか? SSA は、重要なコピー/代入/etc セマンティクスを持つ型でも使用できますか?

編集:問題は、LLVM SSA レジスタを使用して複雑な型 (この場合は) を表す場合、ここでは手動で SSA を作成することによって表される場合、LLVM はこれを一般的なケースで基になるアセンブリの変更呼び出しにstd:string自動的に変換できるかということです。+=厄介なコピーを避けますか？

私はJavaバイトコードのオプティマイザーに取り組んでおり、SSAを使用することにしました。ただし、ほとんどの最適化ではすべての操作が純粋に機能する必要があるため、副作用を処理するために、副作用を引き起こす可能性のあるすべての操作に不透明な状態パラメーターと戻り値を追加することにしました。これにより、副作用のある操作の最適化や並べ替えを防ぐことができます。たとえば、例外処理を無視すると、この擬似コードのようなものが得られます。

私がしていることの名前はありますか？それは良いアプローチですか？関数型言語にはモナドと呼ばれる概念があると聞きました。これは似ているように聞こえますが、同じではありません。モナドを使用する方が良いアプローチですか？もしそうなら、どうすればモナドを使用するようにこれを変更できますか？

Cコードのデータフローグラフを作成する必要があります。データフローグラフとは、グラフ内のノードが加算や乗算などの演算を表し、エッジがノード間のオペランド（データ）フローを表すグラフを意味します。私の目標は、計算集約型カーネルのデータフローグラフの並列処理と実行時間を分析することです。Trimaran、Oink、GCCなどのCプログラムからデータフローグラフを生成するために多くのツールを使用しました。これらのツールの中で、GCCのGimple内部表現は、SSAの各基本ブロックのデータフロー分析を提供します（静的単一割り当て）フォーム。SSAフォームは私の分析を単純化します。GCCの使用方法は次のとおりです。

-fdump-tree-cfg各関数の制御フローグラフを生成します。ノードは基本ブロックを表し、エッジは制御依存性を表します。各基本ブロックのデータ依存性も示されています。ただし、各基本ブロックのデータフローグラフは提供されません。各基本ブロックのデータフローを分析するには、データの依存関係を視覚化する必要があります。

-fdump-tree-cfg例として、次のコードに適用する場合

あなたはこれを手に入れます：

-fdump-tree-vcg制御フローグラフをVCGフォーマットで生成しますが、データ依存情報は保持しません。

ただし、GCCにはいくつかの制限があります。たとえば、GCCは、基本ブロックごとに視覚化されたデータフローグラフを生成しません。Cプログラムのデータフローグラフを生成するツールがあるかどうか疑問に思いましたか？または、Gimple表現からデータフローグラフを生成するGCCプラグインがあるかもしれません。

PS：ツールはプラットフォームに依存せず、特定のアーキテクチャに限定されない必要があります。たとえば、GCCでのGimple表現はアーキテクチャに依存しません。