3

私は分岐予測について読んでいますが、私が見つけた唯一の実装は、ほとんどがコンピューターのハードウェア側にあります。プロセッサーがほとんどの予測を処理しているようです。私の質問は、コンパイラは分岐予測を行うことができるかということです。私が見つけた唯一のものは、関数のインライン展開とループ展開の 2 つのメソッドです。これらは正しいと考えられますか? それらはまだ使用されていますか？

4

1 に答える 1

8

もちろん。コンパイラは、次のことを知っていれば予測情報を取得できます。

  • インストルメンテーションの実行によって収集された統計的分岐確率
  • インストルメンテーションの実行によって収集された変数値の統計分布。その後、条件分岐の平均結果を予測できるため、分岐
  • 条件の頻度またはバイアスに関するプログラマーの主張
  • 範囲に基づくループ境界の推定 (または、不明な場合はデフォルトで「10」になります :)
  • 分岐がループの先頭に逆行しているという知識 ("taken" を予測する)

このような情報を使用して、条件の可能性のある結果を予測し、ハードウェアによって正しく「予測」される傾向がある分岐命令を生成できます。

一部のコンパイラによって行われる特に興味深い最適化のセットは、トレース スケジューリングです。これは、順番に遭遇する分岐の確率に基づいて、コードを通る一連のパスを決定します。最も確率の高いパスを決定することにより、コンパイラは、基本ブロック内だけでなく、そのパス全体にわたって最適化を行うことができます。

コンパイラは、ハードウェアの分岐予測機能を間接的に使用する分岐コードを生成する場合があります。コンパイルされた OO 言語 (静的または JITted) は、メソッド呼び出しをコンパイルする必要があり、ジャンプ間接は高価です。安価な方法は、各呼び出しサイトで最近呼び出されたメソッドの小さな動的キャッシュを保持し、ディスパッチされるオブジェクト タイプをチェックすることです。同じタイプのオブジェクトが呼び出しサイトでのディスパッチに頻繁に使用される場合、キャッシュ内の最初のエントリ (および 2 番目のエントリはやや少ない) の比較/分岐シーケンスが発生する可能性が高く、実行されたコードは予測ミスを回避します。これは、ジャンプ間接よりもはるかに優れています。

最後の標準的なトリック: 分岐を避けることができれば、それを正しく予測する必要はありません! 多くのコード シーケンスは次のようになります。

  if (exp1 relop exp2)
      X = Y
  endif

最新の CPU には、「MOV_if_relop A to B」という「述語」命令があり、すべての関係条件が等しい、等しくない、より小さいなどです。したがって、上記の構造の分岐を生成するのではなく、コンパイラは次を生成します。

  <compute exp1 and exp2>
  CMP  exp1,exp2 ; sets condition code
  MOVif_relop  X,Y
于 2012-05-12T08:31:18.033 に答える