Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

[インデックス 14572] ファイルの概要

このコミットは、Goコンパイラの6c（amd64向け）と8c（i386向け）に、regopt（レジスタ最適化）ステップの一部としてfixjmpという最適化を追加するものです。fixjmpは、コンパイラのコード生成時に生成される冗長なJMP（ジャンプ）命令の連鎖を排除することを目的としています。この機能は既にgc（Goで書かれたGoコンパイラ）に実装されており、6c/8cに移植されました。ただし、6c/8cではJMPがポインタではなくプログラムカウンタ（PC）によって宛先を参照するため、アルゴリズムはProg（プログラム）構造ではなくReg（レジスタ）構造で動作するように変更されています。

コミット

commit 5cb1ed218944e7ce54384b7af0a7beed3965be56
Author: Rémy Oudompheng <oudomphe@phare.normalesup.org>
Date:   Thu Dec 6 07:20:03 2012 +0100

    cmd/6c, cmd/8c: add fixjmp step to regopt.
    
    The fixjmp step eliminates redundant chains of JMP
    instructions that are produced by the compiler during
    code generation.
    
    It is already implemented in gc, and can be adapted to 6c/8c with
    the exception that JMPs refer to destination by pc instead of by
    pointer. The algorithm is modified to operate on Regs instead of Progs
    for this reason. The pcs are already restored later by regopt.
    
    R=goalng-dev, rsc
    CC=golang-dev
    https://golang.org/cl/6865046

GitHub上でのコミットページへのリンク

https://github.com/golang/go/commit/5cb1ed218944e7ce54384b7af0a7beed3965be56

元コミット内容

cmd/6c, cmd/8c: add fixjmp step to regopt.

The fixjmp step eliminates redundant chains of JMP
instructions that are produced by the compiler during
code generation.

It is already implemented in gc, and can be adapted to 6c/8c with
the exception that JMPs refer to destination by pc instead of by
pointer. The algorithm is modified to operate on Regs instead of Progs
for this reason. The pcs are already restored later by regopt.

R=goalng-dev, rsc
CC=golang-dev
https://golang.org/cl/6865046

変更の背景

コンパイラがコードを生成する際、特に最適化の初期段階や中間表現の変換時に、複数のJMP命令が連続して配置される、いわゆる「冗長なJMP命令の連鎖」が生成されることがあります。例えば、JMP L1の後にL1: JMP L2が続くような場合、最初のJMPは直接L2にジャンプするように変更することで、中間的なJMP L1を削除できます。このような冗長なジャンプは、生成されるバイナリコードのサイズを不必要に増加させ、実行時の命令フェッチやキャッシュ効率に悪影響を与える可能性があります。

Goコンパイラの主要な実装であるgc（Go言語で書かれたコンパイラ）には、既にこのような冗長なジャンプを排除するfixjmpステップが実装されていました。しかし、当時のGoコンパイラツールチェーンには、C言語で書かれた6c（amd64アーキテクチャ向け）と8c（i386アーキテクチャ向け）という、異なるアーキテクチャをターゲットとするコンパイラも存在していました。これらのC言語ベースのコンパイラにも同様の最適化を適用することで、生成されるコードの品質と効率を向上させることが、この変更の背景にあります。

特に、6c/8cではジャンプの宛先がポインタではなくプログラムカウンタ（PC）のオフセットで表現されるという違いがあり、この特性に合わせてfixjmpアルゴリズムを適応させる必要がありました。

前提知識の解説

6cと8cコンパイラ

6cと8cは、Go言語の初期のバージョンで使用されていたC言語で書かれたコンパイラです。

  • 6c: 64ビットx86 (amd64) アーキテクチャ向けのGoコンパイラ。
  • 8c: 32ビットx86 (i386) アーキテクチャ向けのGoコンパイラ。 これらはPlan 9のツールチェーンに影響を受けており、Go 1.5以降、Goコンパイラ自体がGo言語で書かれる（セルフホスト化される）ようになったため、現在では歴史的な存在となっています。しかし、このコミットが作成された2012年当時は、これらのコンパイラがGo言語の主要なビルドプロセスの一部でした。

regopt (レジスタ最適化)

regoptは「レジスタ最適化」の略で、コンパイラにおける重要な最適化フェーズの一つです。CPUのレジスタは非常に高速な記憶領域であり、頻繁にアクセスされる値をレジスタに保持することで、メモリへのアクセス回数を減らし、プログラムの実行速度を向上させます。regoptフェーズでは、コード内の変数をどのレジスタに割り当てるか、あるいはメモリに保持するかを決定し、レジスタの使用効率を最大化するための様々な変換を行います。fixjmpのようなジャンプ最適化は、このregoptフェーズの一部として、またはその前後に実行されることがあります。

JMP命令

JMPはアセンブリ言語における「無条件ジャンプ」命令です。プログラムの実行フローを、指定されたアドレス（宛先）に無条件で移動させます。これは、関数呼び出し、ループ、条件分岐の終了など、様々な制御フロー構造を実装するために使用されます。 コンパイラがコードを生成する際、特定の最適化やコード変換の過程で、以下のような冗長なJMP命令の連鎖が発生することがあります。

    JMP L1
L1: JMP L2
L2: ...

この場合、最初のJMP L1は直接JMP L2に書き換えることができ、L1: JMP L2という中間的な命令を削除できます。

プログラムカウンタ (PC) とポインタによるジャンプ宛先

ジャンプ命令の宛先を指定する方法には、主に以下の2つがあります。

  • ポインタ (絶対アドレス): メモリ上の特定のアドレスを直接指定する方法です。これは、プログラムのロードアドレスに依存しないように、通常はリロケーション可能な形式で表現されます。
  • プログラムカウンタ (PC) 相対オフセット: 現在のプログラムカウンタ（次に実行される命令のアドレスを指すレジスタ）からの相対的なオフセットで宛先を指定する方法です。例えば、JMP +10であれば、現在のPCから10バイト先にジャンプします。これは、コードがメモリ上のどこにロードされても正しく動作するため、位置独立コード（PIC）の生成に適しています。

このコミットでは、gcがポインタベースでジャンプ宛先を扱っていたのに対し、6c/8cがPC相対オフセットで宛先を扱っていたため、fixjmpアルゴリズムを6c/8cの特性に合わせて調整する必要がありました。

技術的詳細

fixjmpは、冗長なJMP命令の連鎖を排除し、到達不能なコードを削除することで、生成されるアセンブリコードを最適化するステップです。この最適化は、主に以下の4つのパス（段階）で構成されています。

  1. パス1: AJMPへのジャンプの解決とコードのアクティブ状態の初期化

    • このパスでは、まずすべてのコードブロックを「非アクティブ」（到達不能）としてマークします。
    • 次に、ACALL命令ではないD_BRANCHタイプのジャンプ（つまりJMP命令）が、別のAJMP命令にジャンプしている場合、そのジャンプの宛先を解決します。具体的には、chasejmp関数を使用して、ジャンプの連鎖をたどり、最終的に到達する非JMP命令を見つけ出します。
    • ジャンプの宛先が解決されたら、元のJMP命令の宛先オフセットを、最終的な命令のPC値に更新します。これにより、中間的なJMP命令をスキップして直接最終目的地にジャンプできるようになります。
    • chasejmp関数は、ジャンプの連鎖が10回を超えた場合にループを検出するメカニズムも持っています。

  2. パス2: 到達可能なコードのマーク

    • mark関数を使用して、プログラムのエントリポイント（firstr）から到達可能なすべてのコードブロックを「アクティブ」としてマークします。
    • mark関数は再帰的に呼び出され、ACALLではないD_BRANCH（ジャンプ）命令の宛先や、通常の命令の次の命令をたどって、到達可能なすべてのReg構造体をアクティブにします。
    • AJMP、ARET（リターン）、AUNDEF（未定義）命令に到達すると、そのパスでのマーク処理は終了します。

  3. パス3: デッドコード（主に冗長なJMP）の削除

    • このパスでは、パス2で「非アクティブ」とマークされたすべてのコードブロックを走査します。
    • 非アクティブなコードブロックが見つかった場合、その命令をANOP（No Operation）命令に置き換えます。ANOP命令は、後続の最適化パスで削除されるか、実行時に何もしない命令として扱われます。
    • ただし、プログラムの最後のARET命令については特別な処理が行われます。もしそれが唯一のARETであり、かつその前の命令がARETではない場合、そのARETは削除されずに残されます。これは、プログラムが必ず何らかの形で終了する必要があるためです。

  4. パス4: 次の命令へのJMPの削除

    • このパスは、ジャンプループが検出されなかった場合にのみ実行されます。
    • AJMP命令が、その直後の命令にジャンプしている場合（r->s2 == r->link）、そのAJMP命令も冗長であるため、ANOPに置き換えて削除します。

  5. バックポインタの修正

    • すべてのパスが完了した後、Reg構造体間のバックポインタ（p2、p2link）を再計算し、コード構造の整合性を保ちます。これは、最適化によって命令の順序や関係が変更された場合に必要となります。

このアルゴリズムは、Reg構造体（レジスタ割り当て情報を含む命令の表現）上で動作するように設計されており、6c/8cコンパイラの内部表現に適合しています。pc（プログラムカウンタ）ベースのジャンプオフセットの扱いは、Dconv関数の変更（offset-pcからoffsetへの変更）にも現れており、ジャンプ宛先の表現方法の調整が行われています。

コアとなるコードの変更箇所

このコミットでは、主に以下の4つのファイルが変更されています。

  • src/cmd/6c/list.c および src/cmd/8c/list.c:

    • Dconv関数（デバッグ出力などで命令のオペランドを文字列に変換する関数）において、D_BRANCHタイプ（ジャンプ命令の宛先）の表示方法が変更されました。
    • 変更前: sprintf(str, "%lld(PC)", a->offset-pc); (6c) または sprintf(str, "%d(PC)", a->offset-pc); (8c)
    • 変更後: sprintf(str, "%lld", a->offset); (6c) または sprintf(str, "%d", a->offset); (8c)
    • これは、ジャンプの宛先がPC相対オフセットではなく、絶対的なオフセット（またはPCからの相対オフセットが既に計算された値）として扱われるようになったことを示唆しています。fixjmpがPC値を直接使用してジャンプ先を更新するため、表示もそれに合わせる形です。

  • src/cmd/6c/reg.c および src/cmd/8c/reg.c:

    • regopt関数（レジスタ最適化のメインルーチン）内に、fixjmp(firstr);の呼び出しが追加されました。これは、regoptのパス2.1としてfixjmpステップが組み込まれたことを意味します。
    • 以下の新しい静的関数が追加されました。
      • static void fixjmp(Reg*);: 上記で説明したジャンプ最適化のメイン関数。
      • static Reg* chasejmp(Reg *r, int *jmploop);: ジャンプの連鎖をたどり、最終的なジャンプ先を見つけるヘルパー関数。
      • static void mark(Reg *firstr);: 到達可能なコードをマークするヘルパー関数。
    • これらの関数は、fixjmpアルゴリズムの各パスを実装しています。

コアとなるコードの解説

fixjmp関数

fixjmpは、このコミットで追加されたジャンプ最適化の中心となる関数です。Reg構造体のリスト（firstr）を受け取り、以下の4つのパスを実行します。

  1. パス1: ジャンプの解決と初期マーク:

    • jmploopフラグを初期化し、ジャンプループの検出に使用します。
    • すべてのRegをactive = 0（非アクティブ）に設定します。
    • 各命令を走査し、ACALLではないD_BRANCH（ジャンプ）命令が別のAJMPにジャンプしている場合、chasejmpを呼び出して最終的なジャンプ先を解決し、そのPC値をp->to.offsetに設定します。

  2. パス2: 到達可能なコードのマーク:

    • mark(firstr)を呼び出し、プログラムのエントリポイントから到達可能なすべての命令をactive = 1（アクティブ）に設定します。

  3. パス3: デッドコードの削除:

    • 再びすべての命令を走査し、activeが0（非アクティブ）の命令を見つけます。
    • これらの命令は冗長なジャンプや到達不能なコードであるため、p->as = ANOP;としてANOP（No Operation）命令に置き換えます。
    • ただし、プログラムの最後のARET命令（リターン命令）は、たとえ非アクティブであっても、プログラムの終了を保証するために削除されない場合があります。

  4. パス4: 次の命令へのジャンプの削除:

    • jmploopが0（ジャンプループが検出されなかった）の場合にのみ実行されます。
    • AJMP命令がその直後の命令にジャンプしている場合、そのAJMPも冗長であるため、ANOPに置き換えます。

最後に、Reg構造体間のバックポインタ（p2, p2link）を修正し、デバッグモードが有効な場合は最適化後のコードを出力します。

chasejmp関数

chasejmp関数は、与えられたReg構造体rから始まるJMP命令の連鎖をたどり、最終的にジャンプが着地する非JMP命令を見つけ出す役割を担います。

  • r=r->s2という形で、Reg構造体のs2フィールド（ジャンプ先のRegを指す）をたどっていきます。
  • 途中でAJMP命令ではない命令に遭遇するか、D_BRANCHタイプではないジャンプ（例: ACALL）に遭遇した場合、その命令が最終的なジャンプ先であると判断し、そのRegを返します。
  • ジャンプの連鎖が10回を超えた場合、無限ループの可能性を考慮してjmploopフラグを1に設定し、現在のRegを返して処理を中断します。これは、コンパイラの無限ループを防ぐための安全策です。

mark関数

mark関数は、与えられたReg構造体firstrから始まるコードパスを再帰的にたどり、到達可能なすべての命令を「アクティブ」としてマークします。

  • 既にアクティブな命令に遭遇した場合、そのパスは既に処理済みであるため、再帰を停止します。
  • 現在のRegをactive = 1に設定します。
  • 命令がACALLではなく、かつD_BRANCHタイプ（ジャンプ）である場合、そのジャンプ先のReg（r->s2）に対して再帰的にmarkを呼び出します。
  • 命令がAJMP、ARET、またはAUNDEFである場合、そのパスは終了とみなし、再帰を停止します。
  • それ以外の通常の命令については、次の命令（r->link）に対して再帰的にmarkを呼び出します。

これらの関数が連携することで、コンパイラが生成した冗長なジャンプ命令を効率的に削除し、より最適化されたアセンブリコードを生成します。

関連リンク

参考にした情報源リンク