ハクソク

世界を動かす技術を、日本語で。

レジスタを自分自身とXORすることは、それをゼロにするための慣用句です。なぜ減算ではないのでしょうか？

18日前原文(devblogs.microsoft.com)

概要

x86アーキテクチャ でレジスタをゼロクリアする代表的な方法について解説。 xor eax, eax 命令がなぜ主流になったのか、その理由と歴史的経緯を整理。 sub eax, eax との比較や、CPU設計上の最適化事情も紹介。 Intelなどの CPUメーカーの対応 や、他アーキテクチャ（Itanium）との違いも触れる。 実際のアセンブリコードの現場でのエピソードも交えて解説。

x86コンパイラがxor eax, eaxを好む理由

  • xor eax, eax は、x86でレジスタをゼロにする最も コンパクトな方法
  • mov eax, 0 よりも 命令サイズが小さい （movは即値エンコードで4バイト必要）
  • x86には ゼロレジスタが存在しない ため、都度ゼロ化が必要
  • xor 命令のほかにも sub eax, eax などゼロ化できる命令は存在
  • ただし、xorが主流になった理由は明確ではなく、 慣習や偶然 が影響した可能性

xor eax, eaxとsub eax, eaxの比較

  • バイト数、 実行サイクル数 ともに同じ
  • フラグレジスタ（EFLAGS）の影響
    • xor eax, eax：AF（補助キャリーフラグ）は 未定義
    • sub eax, eax：AFは クリア される
  • その他のフラグ（OF, SF, ZF, PF, CF）はどちらもゼロ化に適切な状態

なぜxorが主流になったのか

  • 初期のコンパイラが xorを選択 したことで、そのまま 慣習化
  • 「コンパイラがそうしているから正しいはず」という 集団心理
  • Intelは両命令に 特別な最適化（命令デコーダでの検出・依存性解消） を実装
    • 入力に依存せず、 ゼロレジスタへのリネーム で実質「0サイクル」動作
  • ただし他のCPUベンダーは xorのみ特別扱い のケースがあるため、xorの優位性が確定

余談・実際の現場エピソード

  • sub r, r を使う開発者も存在し、アセンブリコードで 個性が出る
  • Itaniumアーキテクチャ ではxorトリックは NaTビットがリセットされない ため無効
    • Itaniumには 専用ゼロレジスタ が存在し、直接ゼロを代入可能

著者・背景情報

  • 著者 Raymond はWindows開発に30年以上携わるエンジニア
  • The Old New Thing というWebサイト・書籍の作者
  • Windows Dev Docs Twitterアカウントでも活動
  • 技術的な話題から雑談まで幅広く発信

Hackerたちの意見

レイモンドのコンピュータの些細なことについての文章が、こんなに面白いなんて驚きだよね。

└

マイクロソフトが今どれだけ叩かれてるかは別として、彼らには低レベルコンピューティングについて書くのが上手い人たちがいるよ。ジェームズ・ミケンズの文章は、これについて読んでて本当に笑っちゃった。チェンが彼を「マイクロソフトリサーチで一番面白い男」と表現したのが一番的確だね。

明らかな答えは、XORの方が速いってこと。減算をするには、最下位ビットから最上位ビットにキャリービットを伝播させなきゃいけないけど、XORだとそれをしなくていいんだ。各ビットの出力が隣接するビットに依存しないからね。たぶん、明示的なペナルティがないALUパイプラインの設計もあるけど、全てではないから、XORの方が速いんだよね。レイモンド・チェンみたいなすごい人はそれを知ってるはず。こんなに明白で基本的なことなのに、何か見落としてるのかな？

└

TFAが言ってる通り、x86では sub eax, eax は同じバイト数でエンコードされ、同じサイクル数で実行されるよ。

└

「答えは明らかだ」 ちょっと脱線するけど、「明らか」ってのは自分が知ってることによるんだよね。専門家は自分が「明らか」だと思ってることを説明しないことが多いけど、それは彼らにとってだけ「明らか」なことだから。みんな親切にして、知らない人にも「明らか」なことを説明すべきだよね。

└

彼の言いたいことは、x86ではパフォーマンスの違いはないけど、同僚や友人以外はみんなXORを使ってるってこと。実際、subはクリーンなフラグを残すから、彼はこれが何かの社会的慣習で、ランダムに選ばれて、支持するための根拠のない議論で広まったんじゃないかと思ってる（あるいは「見た目がクール」っていうアート用語の一部として）。また、アセンブリで働くほとんどの人が論理ゲートの特性を知っているから、内部的には何かしら良いかもしれないという理解を持っているのかもしれない。

└

実際、XORがSUBより速いCPUは知らないな。もっと重要なのは、8086ではタイミングが同じだってこと。これがこのパターンの出所なんだよね。

└

そのコメントは、SUBがXORより高コストな実際のCPUを指摘しないとあまり役に立たないよね ;) 例えば、Z80と6502では両方とも同じサイクル数だし。

└

8086アセンブリを学んでるとき、if x==yを正しくやるにはCMP命令を使うって知ったとき、似たような反応をしたよ。CMPは引き算をしてフラグだけを設定するんだよね。（その本には、さまざまな比較演算子に使うブランチ命令のセクションがあった。）XORを使って、引き算を避けるような二つの値を比較してブランチするマクロを作れるか試してみたのに、数分かかったな。

└

FPGAやASICで単独でXORをやると速いよ。でも、ALU（算術論理ユニット）で他の多くの操作と一緒にXORをやると、スピードは一番遅い操作によって決まるから、速い操作のスピードは関係なくなるんだ。つまり、ほとんどのCPUではXORと加算、引き算は同じスピードなんだよ。XORは速くできるのにね。現代のパイプラインCPUでは、クロック周波数は通常、64ビットの加算が1クロックサイクルでできるように選ばれるんだ。レジスタや多重化器、ALUステージの外の回路によるオーバーヘッドを含めてね。64ビットの加算/引き算よりも複雑な操作は、1クロックサイクル以上のレイテンシがあるけど、実行パイプラインの1クロックサイクルごとに1つの操作を開始できるんだ。64ビットの加算/引き算よりも単純な操作、例えばXORは1クロックサイクルで実行されるから、スピードのアドバンテージはないんだ。いわゆるスーパーパイプラインCPUもあって、クロック周波数が上がると、加算/引き算でも2サイクル以上のレイテンシが出ることがある。スーパーパイプラインCPUでは、引き算よりも速いXOR命令が可能かもしれないけど、実際に実装されたかはわからない。性能向上が微々たるものだから、実行パイプラインが複雑になるかもしれないしね。最初はDECがスーパースカラプロセッサに対するより良い代替品としてスーパーパイプラインを推進してたけど、後にスーパーパイプラインは放棄されたんだ。スーパースカラ方式の方が同じ性能でより良いエネルギー効率を提供するからね。（つまり、数年間はスピードデーモンがブレイニアックに勝つと思われてたけど、最終的にはブレイニアックがスピードデーモンに勝つことが証明されたんだ。AppleのCPUのようにね。）主流のCPUはスーパーパイプラインを使ってないけど、比較的最近のIBM POWER CPUにはスーパーパイプラインがあったんだ。ただし、元々提案された理由とは違う理由でね。そのPOWER CPUは、SMTを使ったマルチスレッドワークロードでのみ良い性能を発揮するように設計されていて、シングルスレッドアプリケーションではそうじゃなかったんだ。だから、同じALUで同時にスレッドを実行することで、加算/引き算のマルチサイクルレイテンシが隠されてた。この技術により、IBMは5GHz以上で動作するCPUを簡単に実装できたんだ。シングルスレッド性能だけを劣化させて、SMT性能には影響を与えないようにね。SMTを使うときに何の利点もなかっただろうから、そのPOWER CPUではXORが引き算より速く作られることはなかったと思う。理論的には可能だったかもしれないけど。

└

TFAによると、これらのイディオムがレジスタをゼロにする方法として広く使われているため、Intelは命令デコーディングのフロントエンドに特別なxor r、r検出とsub r、r検出を追加し、宛先を内部ゼロレジスタに名前変更して、命令の実行を完全にバイパスすることにしたんだ。

└

引き算をするには、最下位ビットから最上位ビットにキャリービットを伝播させる必要がある。そうだけど、それはビット数に対して線形にスケールする必要はないよ。https://en.wikipedia.org/wiki/Carry-lookahead_adder: 「キャリー先読み加算器（CLA）またはファストアダーは、デジタルロジックで使用される電子加算器の一種です。キャリー先読み加算器は、より単純で通常は遅いリップルキャリー加算器（RCA）と対比されます。RCAでは、キャリービットは合計ビットと一緒に計算され、各ステージは前のキャリービットが計算されるまで自分の合計ビットとキャリービットの計算を開始できません。キャリー先読み加算器は、合計の前に1つ以上のキャリービットを計算するため、加算器の大きな値のビットの結果を計算する待機時間が短縮されます。 […] すでに1800年代半ばに、チャールズ・バベッジは彼の差分機関で使用されていたリップルキャリーによる性能ペナルティを認識し、彼の未完成の解析機関のためにキャリーを予測するメカニズムを設計しました。[1][2] コンラート・ツーゼは、1930年代の彼のバイナリ機械コンピュータZuse Z1で最初のキャリー先読み加算器を実装したと考えられています。」今のALUはほとんど、いや全てがこういう加算器を実装してると思うよ。

└

キャリーバイパス加算器っていう構造があって、これを使うとO(√n)の時間で2つの数をO(n)のゲートで加算できるんだ。それか似たような構造が現代のCPUで使われていて、ソフトウェアの観点からは、1つのクロックサイクルで2つの数を加算できるのが重要なんだよね。O(log(n))の時間で加算するツリー加算器もあるけど、速度が必要ならO(n^2)のゲートを使うことになるから、実際には誰もそんなに必要としてないと思うよ。

「ボーナスボーナス雑談：XORトリックはItaniumでは機能しない。なぜなら数学的操作はNaTビットをリセットしないから。幸いにも、Itaniumには専用のゼロレジスタがあるから、このトリックは必要ない。ゼロを目的の場所に移動させるだけでいい。」次回Itanium用のアセンブリを書くときに覚えておくよ！

└

結構多くのアーキテクチャには専用の0レジスタがあるよね。

└

Itaniumの失敗はコンパイルの難しさだったから、実際にはすごく速く動くんじゃないかな。（x86命令をItanium命令に翻訳することを含めてね。）

XORは他の用途であまり使われないから（静的カウントの観点では、動的にはホットループの中でよく見かけるけど）、手動アセンブリを書くときに「特別」として簡単に見つけて識別できるのかもしれないね。

└

SMTに役立つよ。追記：どうやらそうじゃないみたい、スレッドの下にある@tliltocatlのコメントを見てみて。

└

XORは暗号化に関わるコードではよく使われるね。追記：静的カウントと動的カウントって何？

└

確かに、これが一番の説明だね！

関連して、機械コードに情報を隠すために「XOR rax,rax」を「ゼロ」として、「SUB rax,rax」を「1」として使うステガノグラフィーの機会があるよ。出力にエンコードしたい文字列を指定できるコンパイラ機能を追加するのはそんなに難しくないはず。

└

これ、Paged Outの記事っぽいね ;)

└

もっと良い方法があるよ。X86にはほとんどの命令の「op [mem], reg」と「op reg, [mem]」のバリアントがあって、「[mem]」はレジスタにもなるからね。「xor eax, eax」をエンコードする方法が二つあるわけで、オペランドのどちらが「可能なメモリアペンダント」スロットに入るかで違うんだ。

└

それもスタイルの指標になるかもね。若い頃にMS-DOSのウイルスを逆アセンブルしてた時、アセンブラプログラマーたちが自分のコードに明確なスタイルを持っているのを見たよ。決定的な帰属には弱いけど、例えばThe Dark Avengerが書いたウイルスの間に「韻」を見つけるのは面白かったな。

大学の時、アセンブリに関わる授業で、レジスタをゼロにするのにムーブ命令じゃなくて引き算を使うように求められたんだ。サイクル数が少なかったからね。その後調べたら、XORもそのアーキテクチャでレジスタをゼロにするための有効な命令だったし、引き算よりもさらに少ないサイクルで済んだ。でも、その授業で使えるアセンブリ言語の命令のサブセットには載ってなかったんだ。ちょっと話がそれるからだと思う。数学のXOR操作を説明する必要があるし（他の授業で習ってなかったら）、その授業は全然別のことについてだったから。でも、引き算はみんな知ってるし、自分自身から数を引くとゼロになるのは明らかだからね。[0] x86じゃないし、正確なアーキテクチャは覚えてない。

IBMの小型プロセッサ、例えばチャネルコントローラやSystem/38以前のミッドレンジラインで使われていたCSPでは、同じソースと宛先を使った場合にxor命令が特別な機能を持っていたんだ。これにより、リードサイクルでパリティやECCエラーチェックを抑制できたから、悪いパリティで保存されたレジスタやメモリの位置をクリアするのにxorを使えるってわけ。マシンチェックやプロセッサチェックを受けずにね。

└

面白いね、IBMの一般的な文化はXORよりもSUBを好んでたみたいだし。彼らの初期のビジネス向けマシンにはXOR命令すらなかったし、後の機種でもSUBの使用が続いてる、IBM PCやAT BIOSでもね。（このスレッドのどこかに、IBMがSUBを好むというコメントがあったけど、それは削除されたみたい。発言の出所はクロードだけど、正しい可能性が高いと思う。自分が確認したBIOSコードも、'SUB AX,AX'がたくさんあって、XORはなかった。）

でも、xorはちょっとした偶然でリードを取ったかも。多分、もっと「賢い」感じがしたからだね。そうだね。でも、算術よりも「ちょっとしたハック」って感じがするから、もっと効率的だと思う。結局、すべての「データ依存性」（キャリーとか、ALUがそれに時間をかけるのは別として）を回避できるからね！XORスワップにも似たような感覚があると思う。 > 一度命令がわずかでも優位に立つと、それがスケールを傾けてみんなをその側に引き寄せるんだ。ネットワーク効果はソーシャルメディアよりもずっと古いよね。

XORはシンプルな論理ゲートの操作だよ。SUBはALUの操作になる。1ビット加算器（逆にした引き算）は信号を2つのゲートを通過させるんだ。https://en.wikipedia.org/wiki/Adder_(electronics) 加算や引き算にはキャリーを気にするから2つのゲートが必要なんだ。だから、8ビット、16ビット、もっと大きなビットを加算・引き算する場合、これを複数つなげて、キャリーがすべてのゲートを一つずつ通過しなきゃいけない。追加の回路なしでは並列化できないから、他の方法でコストが増えるんだ。キャリーに必要なANDゲートがなければ、すべてのXORが同時に発火できる。もし、XORと同じくらい速くするために並列化可能な加算・引き算のための追加回路を加えたら、実際の並列XORはより少ない電力を消費するだろうね。

└

結局、クロックサイクルの数は同じなんじゃない？SUBの時にちょっと余分な回路を使ってるけど、XORの時はその回路はただ待機してるだけだから、結局は同じことだよね。

└

それは確かにそうなんだけど、現代のx86プロセッサでは、XOR用のゲートのペアと、キャリーバイパスを使った64ビット幅の引き算用の約10個のゲートが、どちらも単一のクロックサイクルで処理されるから、プログラマーの視点から見ると同じってことになるんだよね。エネルギーの差はあるけど、レジスタファイルやバイパスネットワークが使うエネルギーに比べたらほんのわずかだし、OoO構造のことを考えたらもっと小さい。

└

自分もそう思ったけど、記事によるとIntelは両方を検出したらしいよ。

└

ALUは論理関数とハードウェアを共有してるんだよね。内部では、加算器（引き算にも使えるけど、入力の一つを1の補数にして初期のキャリーを反転させることで実現する）でXORを使ってるし、同じゲートでXORの論理演算も実装できるんだ。最近のALUはリップルキャリーをあんまり使わなくなって、代わりにコッゲ・ストーン加算器みたいなもの（実際には、いろんな技術を組み合わせた階層的なセット）を使ってるよ。

1980年代初頭、自分で学んだZ80アセンブリのスキルを上げるために、シンクレアスペクトラムのROMを逆アセンブルして解説しようとした本を読んだんだ。最初のROM命令がXOR Aだったのを覚えてる。これには驚いたな、だってアキュムレーターをクリアするのにLD A,0以外のことを考えたことなかったから。