SOに関するこの魅力的な（そして最も投票数の多い質問）を読んで、ソートされていない配列よりもソートされた配列を処理する方が速いのはなぜですか？コンパイラコードの正当性について疑問に思いました。
たとえば、答えは次のように述べています。
インテル®コンパイラー11は奇跡的なことをします。それは2つのループを交換します...
コンパイラープログラマーは、ループを交換しても問題がないことをどのようにして知ることができますか？
そして、一般的に、彼らは結論を実証するために数学的証明を使用していますか？
コンパイラープログラマーは、コンパイラーが正しいコードを生成することをどのようにして知るのでしょうか？彼らはどのように結論をテストしますか？コンパイラを実行し、生成されたコードが正しいことを確認するテストスイートを作成する必要がありますか？
コンパイラープログラマーは、ループを交換しても問題がないことをどのようにして知ることができますか？
コンパイラーは、コードに対して一連のチェックを実行して、ループを交換しても安全かどうかを判断します。たとえば、コードが完全にインライン化されていない場合、ループを交換できない可能性があります。コードが揮発性変数を変更する場合、ループは交換されません。コードが前のループ反復で計算された値を格納している場合、コンパイラーはループを交換しません。これらの条件のいずれもトリガーされないために安全であると確信できる場合、コンパイルはループを交換できます。
そして、一般的に、彼らは結論を実証するために数学的証明を使用していますか？
いいえ。最適化と一連の保守的なテストを実行して、最適化が安全であることを確認します。時間の経過とともに、彼らはより多くの最適化とより洗練されたアルゴリズムを開発して、それがあまり明白でない場合でも最適化が安全であるときを検出します。
コンパイラープログラマーは、コンパイラーが正しいコードを生成することをどのようにして知るのでしょうか？
彼らはできる限り最善を尽くします。時折、彼らは間違いを犯します。人々はバグレポートを提出し、それを修正します。
彼らはどのように結論をテストしますか？コンパイラを実行し、生成されたコードが正しいことを確認するテストスイートを作成する必要がありますか？
彼らは絶対にテストスイートを使用します。GCCでバグが検出されると、テストがテストスイートに特別に追加され、バグが修正されて再導入されていないことを確認します。
コンパイラープログラマーは、ループを交換しても問題がないことをどのようにして知ることができますか？
変更が言語標準に従ってプログラムの動作を変更しない場合、変更が標準自体に反しない場合。
たとえば、CおよびC ++標準では、関数パラメータと部分式の評価の順序が指定されていないことがいくつかの場所で示されています。これにより、コンパイラーは、適切と思われる順序でそれらを評価するためのコードを生成する自由が与えられます。プログラムが特定の順序に依存している場合、それは標準に準拠しておらず、コンパイラがそれを「破った」と非難する権利はありません。
コンパイラーは、コードを最適化するために、これらすべての定理でコード分析、論理、および数学を使用する場合があります。
実際には、テストはコンパイラが正しい仕事をしたかどうかを示します。
独自の言語で記述されたコンパイラーの主な健全性テストの1つは、コンパイラーをコンパイルしてから、結果の新しいコンパイラーを使用して再度コンパイルすることです。結果として得られる2つのコンパイラは、タイムスタンプを法として同一である必要があります。
コンパイルは複雑なプロセスです。プログラムはグラフとして構造化されており、コンパイラは、開発者が考え出したルールに従って、このグラフを「最適化」しようと最善を尽くします。
ただし、生成されたコードが「最適」に近いという保証はありません。自動化された証明エンジンを使用して真に最適なコードを生成しようとする、いわゆる「スーパーオプティマイザー」に関する研究が行われています...つまり、「このアルゴリズムをコンパイルして X よりも時間がかからないようにする方法はありますか?」などの質問に答えることができます。サイクル」。Denaliは、私が読んだスーパー オプティマイザーの 1 つです。この手法は、一部のアーキテクチャでは他のアーキテクチャよりも簡単です。欠点は、これらのスーパーオプティマイザが単純なルーチンをコンパイルするのに、数日ではないにしても数時間かかることです。これは、ほとんどの人にとって受け入れられません。