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

このコミットは、Goコンパイラの主要部分であるsrc/cmd/gcディレクトリ内の複数のファイルを変更しています。gcはGo言語のフロントエンドコンパイラであり、ソースコードの字句解析、構文解析、型チェック、中間表現への変換、最適化、そして最終的なマシンコード生成の前段階の処理を担当します。

変更されたファイルとその役割は以下の通りです。

• src/cmd/gc/const.c: コンパイル時定数評価に関する処理を定義しています。
• src/cmd/gc/go.h: コンパイラ全体で共有されるデータ構造、列挙型、関数プロトタイプなどを定義するヘッダファイルです。
• src/cmd/gc/go.y: Go言語の文法を定義するYacc（またはBison）の入力ファイルです。構文解析器がこの定義に基づいてGoコードを解析します。
• src/cmd/gc/lex.c: 字句解析器（lexer）の実装ファイルです。ソースコードをトークンに分割する役割を担います。
• src/cmd/gc/mparith2.c: 多倍長整数（multi-precision integer）の算術演算に関するヘルパー関数を定義しています。コンパイル時定数評価などで使用されます。
• src/cmd/gc/subr.c: コンパイラの様々なユーティリティ関数や補助ルーチンが含まれています。
• src/cmd/gc/walk.c: 中間表現ツリーを走査（walk）し、最適化やコード生成のための変換を行う部分です。

コミット

このコミットは、Go言語に新しいビットクリア演算子 &^ およびその複合代入演算子 &^= を追加するものです。これにより、特定のビットをクリアする操作がより簡潔に記述できるようになります。

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

https://github.com/golang/go/commit/bb02e481d200c16e5a3e7ddc6b73b6ea43362267

元コミット内容

added bitclear operators &^ and &^=

R=r
OCL=26152
CL=26152
---
 src/cmd/gc/const.c    |  3 +++
 src/cmd/gc/go.h       |  3 ++-
 src/cmd/gc/go.y       |  8 ++++++--
 src/cmd/gc/lex.c      |  9 +++++++++
 src/cmd/gc/mparith2.c | 34 ++++++++++++++++++++++++++++++++++
 src/cmd/gc/subr.c     |  1 +
 src/cmd/gc/walk.c     | 18 +++++++++++++++++-
 7 files changed, 72 insertions(+), 4 deletions(-)

変更の背景

ビットクリア演算子 &^ は、Go言語の設計思想である「明示的であること」と「簡潔であること」を両立させるために導入されました。

ビットクリア操作（A &^ B）は、Aのビットのうち、Bでセットされているビットをクリアする（0にする）操作です。これは論理的には A AND (NOT B) と等価です。多くのプログラミング言語では、この操作を A & (~B) のように、ビットごとのAND演算子とビットごとのNOT演算子を組み合わせて表現します。しかし、この形式は冗長であり、特に~（ビットごとのNOT）演算子がGo言語には存在しないため、GoではA & (^B)のような表現もできませんでした。

Go言語は、C言語のような低レベル操作をサポートしつつも、より安全で読みやすいコードを目指しています。ビット操作はシステムプログラミングやハードウェアとのインタフェースにおいて不可欠ですが、A & (~B)のような表現は、特にビットごとのNOT演算子のセマンティクス（符号付き整数の場合など）を考慮すると、直感的でない場合や、意図しない結果を招く可能性がありました。

そこで、Go言語の設計者たちは、この頻繁に行われるビット操作をより明確かつ簡潔に表現するための専用の演算子 &^ を導入することを決定しました。これにより、コードの可読性が向上し、プログラマが意図するビット操作がより明確になります。

前提知識の解説

ビット演算

ビット演算は、数値を2進数として扱い、個々のビットに対して論理演算を行うものです。

• AND (&): 両方のビットが1の場合にのみ結果が1になります。
  • 例: 1010 & 1100 = 1000
• OR (|): 少なくとも一方のビットが1の場合に結果が1になります。
  • 例: 1010 | 1100 = 1110
• XOR (^): どちらか一方のビットのみが1の場合に結果が1になります（排他的論理和）。
  • 例: 1010 ^ 1100 = 0110
• NOT (~): ビットを反転させます（0は1に、1は0に）。Go言語には単項の~演算子はありません。
  • 例: ~1010 = 0101 (ただし、これはビット幅に依存します)

ビットクリア演算子 (&^)

A &^ B は、「Aのビットのうち、Bで1になっているビットを0にする」という操作です。これは A AND (NOT B) と等価です。

例: A = 1010 (10進数の10), B = 0101 (10進数の5)

1. NOT B を計算します。Goには単項NOTがないため、これは概念的なものです。もし8ビット整数なら ~00000101 = 11111010。

2. A AND (NOT B) を計算します。 1010 & 1010 = 1010 (もし NOT B が 1010 だと仮定した場合) より正確には、A = 1010, B = 0101 の場合、 A &^ B は、Aの各ビットとBの対応するビットを比較し、Bのビットが1であればAのビットを0にし、Bのビットが0であればAのビットをそのままにします。

   A: 1010 B: 0101

   結果: 1010 (Aの2番目のビットがBの2番目のビットによってクリアされる) 1010 &^ 0101 = 1010

   これは、A & (~B) と同じ結果になります。 ~0101 (4ビットの場合) は 1010 1010 & 1010 = 1010

コンパイラの主要なフェーズ

Goコンパイラ（gc）は、ソースコードを機械語に変換するためにいくつかの段階を踏みます。

1. 字句解析 (Lexical Analysis): ソースコードをトークン（キーワード、識別子、演算子、リテラルなど）のストリームに分割します。lex.cがこの役割を担います。
2. 構文解析 (Syntactic Analysis): トークンのストリームを解析し、言語の文法規則に従って抽象構文木（AST: Abstract Syntax Tree）を構築します。go.yが文法定義、go.yから生成されるパーサがこの役割を担います。
3. 意味解析 (Semantic Analysis): ASTを走査し、型チェック、名前解決、定数評価などを行います。const.c（定数評価）やwalk.c（AST走査と変換）がこのフェーズの一部です。
4. 中間コード生成 (Intermediate Code Generation): ASTを、より低レベルで最適化しやすい中間表現に変換します。
5. 最適化 (Optimization): 中間表現に対して様々な最適化を適用し、実行効率を向上させます。walk.cの一部も最適化に関わります。
6. コード生成 (Code Generation): 最適化された中間表現をターゲットアーキテクチャの機械語に変換します。

技術的詳細

このコミットは、Go言語に新しいビットクリア演算子 &^ と複合代入演算子 &^= を追加するために、コンパイラの複数の層にわたる変更を加えています。

1. 字句解析器 (src/cmd/gc/lex.c):

   • &^ という文字の並びを新しいトークン LANDNOT として認識するように変更されました。
   • &^= という文字の並びを複合代入演算子 OANDNOT として認識するように変更されました。これは、a &^= b が a = a &^ b と等価であることを示します。

2. ヘッダファイル (src/cmd/gc/go.h):

   • enum OANDNOT が追加され、新しいビットクリア演算子を表す内部的なオペレーションコードとして定義されました。これは、ASTノードのopフィールドなどで使用されます。
   • 多倍長整数演算のための新しい関数プロトタイプ void mpandnotfixfix(Mpint *a, Mpint *b); が追加されました。これは、コンパイル時定数評価のために必要です。

3. 構文解析器 (src/cmd/gc/go.y):

   • 新しいトークン LANDNOT が %token ディレクティブに追加されました。
   • 演算子の優先順位を定義する %left ディレクティブに LANDNOT が追加され、* / % & LLSH LRSH と同じ優先順位を持つように設定されました。これは、ビットクリア演算子が乗算や他のビットシフト演算子と同じ優先順位を持つことを意味します。
   • expr LANDNOT expr という新しい文法規則が追加され、これに対応するASTノード nod(OANDNOT, $1, $3) が生成されるようになりました。これにより、パーサが A &^ B の形式を正しく解析し、OANDNOTオペレーションを持つASTノードを構築できるようになります。

4. 多倍長整数演算 (src/cmd/gc/mparith2.c):

   • mpandnotfixfix(Mpint *a, Mpint *b) 関数が新しく実装されました。この関数は、多倍長整数 a と b に対してビットクリア演算 a &^ b を実行し、結果を a に格納します。
     • 符号の処理: 負の数のビット表現を考慮し、必要に応じて一時的に絶対値に変換して演算を行い、最後に正しい符号に戻すロジックが含まれています。
     • 実際の演算: *a1 & ~*b1++ の部分で、各ワード（long型）に対してビットクリア操作を行っています。~*b1 は b のビットを反転させる操作であり、これと a のビットをANDすることでビットクリアを実現しています。

5. 定数評価 (src/cmd/gc/const.c):

   • evconst 関数内の switch 文に case TUP(OANDNOT, Wlitint): が追加されました。これにより、コンパイル時に両方のオペランドがリテラル整数である &^ 演算を評価できるようになりました。
   • mpandnotfixfix(xval, nr->val.u.xval); が呼び出され、多倍長整数演算関数を使用して定数値を計算します。

6. 補助ルーチン (src/cmd/gc/subr.c):

   • opnames 配列に [OANDNOT] = "ANDNOT", が追加されました。これは、デバッグやエラーメッセージなどで内部的なオペレーションコード OANDNOT を人間が読める文字列に変換するために使用されます。

7. ASTウォーカー (src/cmd/gc/walk.c):

   • walk 関数内の switch 文に case OANDNOT: が追加されました。
   • OANDNOT ノードが検出された場合、これは OAND と OCOM (ビットごとの補数、つまりNOT) の組み合わせに変換されます。具体的には、n->op = OAND; と n->right = nod(OCOM, n->right, N); によって、A &^ B が A & (~B) という形式に変換されます。これは、コンパイラのバックエンドが OAND と OCOM を処理できることを前提とした最適化または正規化のステップです。
   • 複合代入演算子 OASOP の処理にも変更が加えられ、n->etype == OANDNOT の場合に同様の変換が行われるようになりました。

これらの変更により、Goコンパイラは &^ 演算子を正しく字句解析、構文解析、意味解析、そして最終的なコード生成へとつなげることができるようになります。

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

このコミットのコアとなる変更は、以下の3つの側面に見られます。

1. 字句解析と構文解析での認識:

   • src/cmd/gc/lex.c の l0: ラベル内の if(c1 == '^') ブロック。ここで &^ と &^= がそれぞれ LANDNOT と OANDNOT トークンとして識別されます。
   • src/cmd/gc/go.y の %token LANDNOT と %left ... LANDNOT の定義、そして expr LANDNOT expr の文法規則。これにより、パーサが新しい演算子を認識し、ASTを構築します。

2. 多倍長整数演算の実装:

   • src/cmd/gc/mparith2.c に新しく追加された mpandnotfixfix 関数。この関数は、コンパイル時定数評価のために、多倍長整数に対するビットクリア演算の具体的なロジックを提供します。特に x = *a1 & ~*b1++; の行がビットクリアの核心部分です。

3. AST変換と最適化:

   • src/cmd/gc/walk.c の case OANDNOT: ブロック。ここで A &^ B というASTノードが、A & (~B) という形式に変換されます。これは、コンパイラの後のフェーズで処理しやすいように、より基本的な演算子の組み合わせに分解するステップです。

コアとなるコードの解説

src/cmd/gc/lex.c (字句解析)

// ...
l0:
    // ...
    if(c1 == '^') {
        c = LANDNOT; // &^ を LANDNOT トークンとして認識
        c1 = getc();
        if(c1 == '=') {
            c = OANDNOT; // &^= を OANDNOT トークンとして認識 (複合代入)
            goto asop;
        }
        break;
    }
    // ...

このコードは、字句解析器が & の次に ^ が来た場合に、それを LANDNOT トークンとして認識するように拡張しています。さらに、その後に = が続く場合は、複合代入演算子 &^= を表す OANDNOT トークンとして扱います。

src/cmd/gc/go.y (構文解析)

// ...
%token           LLSH LRSH LINC LDEC LCOMM LANDNOT // LANDNOT トークンの追加
// ...
%left            '*' '/' '%' '&' LLSH LRSH LANDNOT // 優先順位の定義
// ...
expr:
    // ...
|   expr LANDNOT expr
    {
        $$ = nod(OANDNOT, $1, $3); // OANDNOT ノードの生成
    }
// ...

go.yでは、LANDNOTが新しいトークンとして宣言され、その優先順位が他のビット演算子や乗除算と同じレベルに設定されています。そして、expr LANDNOT exprという新しい文法規則が追加され、このパターンが検出された場合に、OANDNOTというオペレーションコードを持つASTノードが生成されるようになります。$1と$3はそれぞれ左オペランドと右オペランドのASTノードを指します。

src/cmd/gc/mparith2.c (多倍長整数演算)

void
mpandnotfixfix(Mpint *a, Mpint *b)
{
    int i;
    long x, *a1, *b1;

    // ... 符号の処理 ...

    a1 = &a->a[0];
    b1 = &b->a[0];
    for(i=0; i<Mpprec; i++) {
        x = *a1 & ~*b1++; // ビットクリア演算の核心
        *a1++ = x;
    }

    // ... 符号の再調整 ...
}

mpandnotfixfix関数は、多倍長整数 a と b に対してビットクリア演算を実行します。ループ内で *a1 & ~*b1++ という式が使われています。これは、aの現在のワードと、bの現在のワードのビットを反転させたもの（~*b1）との論理ANDを取ることで、ビットクリア操作を実現しています。Mpprecは多倍長整数のワード数を示します。

src/cmd/gc/walk.c (ASTウォーカー)

// ...
    case OANDNOT:
        n->op = OAND; // OANDNOT を OAND に変換
        n->right = nod(OCOM, n->right, N); // 右オペランドを OCOM (NOT) でラップ
        n->right->type = n->right->left->type;
        break;

    case OASOP: // 複合代入演算子
        if(n->etype == OANDNOT) { // &^= の場合
            n->etype = OAND; // OAND に変換
            n->right = nod(OCOM, n->right, N); // 右オペランドを OCOM (NOT) でラップ
            n->right->type = n->right->left->type;
            break;
        }
        // ...

walk.cでは、OANDNOTノードが検出されると、それを OAND ノードと OCOM (complement、ビットごとのNOT) ノードの組み合わせに変換します。具体的には、A &^ B というASTは、A & (~B) というASTに書き換えられます。これは、コンパイラの後のフェーズで OAND と OCOM というより基本的な演算子を処理できるため、コード生成を簡素化するための正規化ステップです。複合代入演算子 &^= (OASOP かつ etype == OANDNOT) も同様に変換されます。

関連リンク

• Go言語仕様: https://go.dev/ref/spec (ビット演算子に関するセクションを参照)
• Go言語のソースコード: https://github.com/golang/go

参考にした情報源リンク

• Go言語のビットクリア演算子 &^ の導入に関する議論や背景は、GoのIssueトラッカーやメーリングリストで確認できますが、このコミットが非常に初期のものであるため、当時の具体的な議論を見つけるのは困難な場合があります。一般的には、Goの設計原則（明示性、簡潔性）に沿ったものと理解されています。
• Go言語のコンパイラ構造に関する一般的な情報:
  • "Go Compiler Internals" (様々なブログ記事やプレゼンテーション)
  • "Go Programming Language" (書籍)
• Yacc/Bisonの基本的な使い方と文法定義:
  • Yacc/Bisonのドキュメントやチュートリアル
• 多倍長整数演算の概念:
  • コンピュータサイエンスの教科書やオンラインリソース