コンパイラとハイエンドのプロセッサパイプラインでのブール式最適化

Question

ブール式を計算したい。理解を容易にするために、式がであると仮定しよう。

O =（A & B & C）| （D &E &F）

ここで、A、B、C、D、E、Fはランダムビットである。現在、私のターゲットプラットフォームは、64ビットデータ型をサポートするハイエンドのIntel i7-Haswellプロセッサであるため、ビットスライスを使用してこれをもっと効率的にすることができます。 だから今、O、A、B、C、D、E、Fは64ビットのデータタイプである、

O_64 =（A_64 & & B_64 C_64）| （D_64 &E_64 &F_64）---（式2）、&および|ビット演算子はC言語に似ています。

ここで、実行するのに一定の時間がかかるようにする必要があります。つまり、数式の計算を意味します。 2は、A_64、B_64、C_64、D_64、E_64、およびF_64の値に関係なく、プロセッサの正確なステップ数を取る必要があります。値は、実行時にランダムジェネレータを使用して埋められます。今私の質問は、

1. 私は-O3とGCCまたはGCC-7を使用しています検討している

   は、どこまでのコンパイラは、発現を最適化することができますか？たとえば、A_64がすべてゼロになる（確率2^{ - 64}で起こりうる）場合、式2の最初の部分を計算する必要はなく、O_64はD_64 & E_64 & F_64に等しくなります。そのような方法で最適化することは可能ですか？値は実行時に満たされ、ブール式には約120の変数があることを覚えておく必要があります。

2. 実行時にこのような最適化（リスト1）を行うことは可能ですか？ブール式が非常に長いので、実行は大量にパイプライン化されますが、このような状況が発生した場合にプロセッサがパイプラインから操作を引き出すことは可能ですか？

質問のいずれかの部分が理解できない場合は教えてください。 私はあなたの助けに感謝します。

Answer 1

このような方法で最適化することは可能ですか？

これは許可されていますが、おそらくそうではありません。一般的には何も得られません。式の一部が静的にゼロであることが分かっていれば、それが使用されます。しかし、ビット単位の計算の中にブランチを挿入することは、ほとんど常に非生産的です。コンパイラがANDのシーケンスを「早期に挿入する価値があるほど長い」と判断することは決してありませんでした。あなたが確かに私はあなたにそれを与えることはできません難しい保証が必要な場合を確認する場合は、常にアセンブリをチェックする必要があります。

（おそらくもっと長い表現のために）これは、より多くの命令レベルの並列性のために式を再結合します。ですから、おそらくそのようなコードは、おそらく2つの長い（しかし互いに平行な）依存ANDのチェーンではなく、より多くのチェーンに分割されるでしょう。それでも時間は値に依存しません。

実行時にこのような最適化を行うことは可能ですか？

非常に仮説的にはい。私が知っているプロセッサアーキテクチャはありません。これはややこしいメカニズムであり、一般的にはほとんど役に立ちません。

これは、AND命令のオペランドが参照され、そのうちの1つ（または両方）がハードワイヤードゼロレジスタに名前が変更されたことが判明したときに、 （結果に新しいレジスタを割り当てるのではなく）ゼロにして、そのAND命令に0レイテンシを効果的に与えます。フラグ出力も分かっているので、μopは実行する必要さえありません。それはおおむね、コピー除去とゼロ化イディオムとの間のクロスです。

入力がであり、誤ってが検出されない場合は、入力の1つがゼロに設定されたイディオムでゼロに設定されていない限り、そのメカニズムは起動しません。また、冗長AND命令の影響を完全に取り除くこともできません。プロセッサのフロントエンドを通過させなければならないのは、結局のところ実行する必要がないことがわかったとしても。