アルゴリズムをインライン化する論文の議論を知っている人はいますか? そして密接に関連しているのが、親子グラフとコールグラフの関係です。
背景:主にこれと他のいくつかの最適化の結果として、関数を積極的にインライン化するコンパイラーを作成しましたOcaml。これは、多くの状況で他のほとんどのプログラミング言語よりも高速なコードを生成します ( C.
問題 #1:アルゴリズムに再帰の問題があります。このため、私のルールは、無限再帰を防ぐために、子を親にインライン化することだけですが、これにより、兄弟関数が相互にインライン化されることはなくなります。
問題 #2:インライン操作を最適化する簡単な方法を知りません。私のアルゴリズムは、関数本体の可変表現を使用することが不可欠です。効率的な関数型インライン化アルゴリズムを作成することは、リモートでさえ可能ではないように思われるからです。呼び出しグラフがツリーの場合、ボトムアップのインライン化が最適であることは明らかです。
技術情報:インライン化は、いくつかのインライン化ステップで構成されます。問題は、ステップの順序です。
各ステップは次のように機能します。
- 型パラメーターと値パラメーターの両方を引数に置き換えることにより、関数のコピーをインライン化してベータ削減します。
- 次に、return ステートメントを新しい変数への代入に置き換え、その後に関数本体の末尾にジャンプします。
- 関数への元の呼び出しは、この本体に置き換えられます。
- しかし、まだ終わっていません。また、関数のすべての子を複製し、それらもベータ削減し、複製を呼び出し元の関数に再親化する必要があります。
複製操作により、再帰関数をインライン化することが非常に困難になります。すでに進行中のもののリストを保持し、この呼び出しを既に処理しているかどうかを確認するだけの通常のトリックは、単純な形式では機能しません。関数、および再帰ターゲットが複製された子に変更された可能性があります。ただし、その子は、親を呼び出す際に、その子を呼び出す元の親を呼び出しているため、再帰の展開は停止しません。前述のように、子への再帰呼び出しのインライン化のみを許可し、兄弟の再帰がインライン化されないようにすることで、この回帰を打破しました。
インライン化のコストは、garbage collect未使用の関数が必要になるため、さらに複雑になります。インライン化は潜在的に指数関数的であるため、これは不可欠です。関数へのすべての呼び出しがインライン化されている場合、関数がまだインライン化されていない場合は削除する必要があります。そうしないと、使用されなくなった関数にインライン化する時間が無駄になります。誰が何を呼び出しているかを実際に追跡することは非常に困難です。なぜなら、インライン化するとき、実際の関数表現ではなく、「解明されていない」表現で作業しているためです。たとえば、命令のリストが順次処理され、新しいリストが構築されます。また、一貫した命令リストが存在しない可能性もあります。
彼の ML コンパイラで、Steven Weeks は繰り返し適用される多数の小さな最適化を使用することを選択しました。これにより、最適化が記述しやすく、制御しやすくなりましたが、残念ながら、これは再帰アルゴリズムと比較して多くの最適化の機会を逃しています。
問題 #3:関数呼び出しをインライン化しても安全なのはいつですか?
この問題を一般的に説明すると、遅延関数型言語では、引数がクロージャでラップされ、アプリケーションをインライン化できます。これは Haskell の標準モデルです。ただし、なぜHaskellこんなに遅いのかについても説明しています。引数が既知の場合、クロージャーは必要ありません。その場合、パラメーターは、発生する引数で直接置き換えることができます (これは通常の順序beta-reductionです)。
ただし、引数の評価が終了しないことがわかっている場合は、代わりに熱心な評価を使用できます。パラメーターには式の値が一度割り当てられ、その後再利用されます。これら 2 つの手法のハイブリッドは、クロージャーを使用するが、結果をクロージャー オブジェクト内にキャッシュすることです。それでも、GHC は非常に効率的なコードを生成することに成功していません。特に、個別にコンパイルする場合は、明らかに非常に困難です。
Felix では、逆のアプローチを取りました。正確さを要求し、最適化がセマンティクスを保持していることを証明することによって徐々に効率を改善する代わりに、最適化がセマンティクスを定義することを義務付けます。これにより、特定のコードがどのように動作するかについての不確実性を犠牲にして、オプティマイザーの正しい動作が保証されます。この考え方は、デフォルトの最適化戦略が積極的すぎる場合に、オプティマイザーを意図したセマンティクスに強制的に準拠させる方法をプログラマーに提供することです。
たとえば、デフォルトのパラメーター受け渡しモードでは、コンパイラーは引数をクロージャーでラップするか、パラメーターを引数で置き換えるか、または引数をパラメーターに割り当てるかを選択できます。プログラマーがクロージャーを強制したい場合は、クロージャーを渡すだけです。プログラマーが熱心な評価を強制したい場合は、パラメーターをマークしますvar。
ここでの複雑さは、関数型プログラミング言語よりもはるかに大きくなります。Felix は、変数とポインターを使用する手続き型言語です。Haskell スタイルの型クラスもあります。これにより、インライン化ルーチンが非常に複雑になります。たとえば、型クラスのインスタンスは、可能な限り抽象関数を置き換えます (ポリモーフィック関数を呼び出すときの型の特殊化により、インライン化中にインスタンスを見つけることができる場合があるため、新しい関数があります。インライン化できます)。
明確にするために、さらにメモを追加する必要があります。
インライン化と、ユーザー定義の用語削減、型クラスのインスタンス化、変数削除のための線形データ フロー チェック、テール レコードの最適化などの他のいくつかの最適化が、指定された関数に対して一度に実行されます。
順序付けの問題は、さまざまな最適化を適用する順序ではなく、関数を順序付けすることです。
脳死アルゴリズムを使用して再帰を検出します。各関数によって直接使用されるすべてのリストを作成し、クロージャーを見つけて、関数が結果に含まれているかどうかを確認します。使用セットは最適化中に何度も構築されることに注意してください。これは深刻なボトルネックです。
関数が再帰的であるかどうかは、残念ながら変わる可能性があります。tail rec の最適化後、再帰関数が非再帰になる可能性があります。しかし、もっと難しいケースがあります: 型クラスの「仮想」関数をインスタンス化すると、再帰的でないように見えたものを再帰的にすることができます。
兄弟呼び出しに関しては、問題は、f が g を呼び出し、g が f を呼び出す f と g を指定すると、実際には f を g に、g を f .. に 1 回インライン化したいことです。私の無限回帰停止規則は、f が g の子である場合に相互に再帰的である場合にのみ、f の g へのインライン展開を許可することです。これにより、兄弟のインライン展開は除外されます。
基本的に、すべてのコードを「可能な限り」「平坦化」したいと考えています。