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

このコミットは、Goコンパイラのsrc/cmd/gc/walk.cファイルに対する変更です。walk.cはGoコンパイラのバックエンドの一部であり、抽象構文木（AST）を走査し、コード生成のための準備を行う役割を担っています。具体的には、スライス操作に関する最適化、特に冗長な境界チェックの削除を目的としています。

コミット

• コミットハッシュ: 19e292268896c245c781e711ae3fff5ff5e127e5
• Author: Keith Randall khr@golang.org
• Date: Mon Aug 5 13:24:33 2013 -0700

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

https://github.com/golang/go/commit/19e292268896c245c781e711ae3fff5ff5e127e5

元コミット内容

cmd/gc: get rid of redundant slice bound check.

For normal slices a[i:j] we're generating 3 bounds
checks: j<={len(string),cap(slice)}, j<=j (!), and i<=j.
Somehow snuck in as part of the [i:j:k] implementation
where the second check does something.
Remove the second check when we don't need it.

R=rsc, r
CC=golang-dev
https://golang.org/cl/12311046

変更の背景

Go言語のスライス操作、特にa[i:j]のような通常の形式では、コンパイラは実行時に安全性を保証するために複数の境界チェックを生成します。このコミット以前のcmd/gcコンパイラでは、a[i:j]形式のスライスに対して、以下の3つの境界チェックが冗長に生成されていました。

1. j <= len(string) または j <= cap(slice): スライスの上限jが、基底配列の長さまたは容量を超えていないかを確認するチェック。
2. j <= j: これは常に真となる自明なチェックであり、冗長です。
3. i <= j: スライスの下限iが上限jを超えていないかを確認するチェック。

コミットメッセージによると、この2番目の冗長なj <= jチェックは、a[i:j:k]形式のフルスライス式の実装の一部として、何らかの理由で紛れ込んでしまったようです。a[i:j:k]形式では、3番目のインデックスkがスライスの容量を決定するため、特定の条件下でこのチェックが意味を持つ可能性がありましたが、通常のa[i:j]形式では不要でした。

この冗長なチェックは、コンパイルされたバイナリのサイズをわずかに増加させ、実行時のパフォーマンスに微細な影響を与える可能性があります。Goコンパイラは、生成されるコードの効率性を重視するため、このような冗長な処理は排除されるべきでした。このコミットは、この不要な境界チェックを特定し、削除することで、コンパイラが生成するコードの品質を向上させることを目的としています。

前提知識の解説

Go言語のスライス

Go言語のスライスは、配列をラップした動的なデータ構造です。スライスは、基底となる配列の一部を参照し、その「ビュー」を提供します。スライスは、以下の3つの要素で構成されます。

• ポインタ: 基底配列のどこからスライスが始まるかを示すポインタ。
• 長さ (Length): スライスに含まれる要素の数。len()関数で取得できます。
• 容量 (Capacity): スライスの開始位置から基底配列の末尾までの要素の数。cap()関数で取得できます。スライスが拡張される際に、この容量の範囲内であれば新しい基底配列の割り当てなしに要素を追加できます。

スライス式 a[i:j] と a[i:j:k]

Goでは、既存の配列やスライスから新しいスライスを作成するためにスライス式を使用します。

• a[i:j] (標準スライス式):

  • i: 新しいスライスの開始インデックス（含む）。省略された場合は0。
  • j: 新しいスライスの終了インデックス（含まない）。省略された場合は元のスライスの長さ。
  • 新しいスライスの長さは j - i。
  • 新しいスライスの容量は cap(a) - i。

• a[i:j:k] (フルスライス式):

  • i: 新しいスライスの開始インデックス（含む）。
  • j: 新しいスライスの終了インデックス（含まない）。
  • k: 新しいスライスの容量の最大インデックス（含まない）。j <= kでなければなりません。
  • 新しいスライスの長さは j - i。
  • 新しいスライスの容量は k - i。 この形式は、新しいスライスの容量を明示的に制限したい場合に使用されます。例えば、append操作によって基底配列の意図しない部分が変更されるのを防ぐことができます。

Goの境界チェック (Bound Checks)

Goはメモリ安全性を重視しており、スライスや配列へのアクセス時には自動的に境界チェックを行います。これにより、プログラムが配列の範囲外のメモリにアクセスする（バッファオーバーフローなど）ことを防ぎ、パニック（runtime error: index out of range）を発生させます。

コンパイラは、これらの境界チェックをコードに挿入しますが、Go 1.7以降では「境界チェックの削除 (Bounds Check Elimination - BCE)」という最適化が行われます。これは、コンパイラがコードフローを分析し、特定のアクセスが必ず境界内にあると証明できる場合に、冗長な境界チェックを省略するものです。これにより、安全性を損なうことなくパフォーマンスが向上します。

cmd/gc

cmd/gcは、Go言語の標準コンパイラツールチェーンの一部であり、Goソースコードをコンパイルする主要なコンポーネントです。通常、「gc」はGoコンパイラを指し、ガベージコレクション（Garbage Collection）とは異なります。cmd/gcは、ソースコードの解析、型チェック、中間表現の生成、そして最終的な機械語コードの生成（バックエンド）を担当します。src/cmd/gc/walk.cは、このコンパイラのバックエンド部分、特にASTの走査とコード生成の準備に関連する処理を担うファイルです。

技術的詳細

このコミットは、Goコンパイラがスライス式を処理する際の内部ロジックに焦点を当てています。特に、sliceany関数は、任意のスライス式（a[i:j]またはa[i:j:k]）を処理する役割を担っています。

コミットメッセージが示唆するように、通常のa[i:j]形式のスライスでは、j <= jというチェックは常に真であり、実行時に意味を持ちません。しかし、a[i:j:k]形式のスライスが導入された際に、この冗長なチェックが誤ってa[i:j]形式にも適用されるようになってしまったと考えられます。

walk.c内のsliceany関数は、スライス式の各部分（下限、上限、容量上限）に対応するノードを処理します。変更前のコードでは、a[i:j]形式の場合、容量上限（cb）が上限（hb）と同じノードを指すように設定されていました。これは、a[i:j]がa[i:j:cap(a)]と等価であるという概念に基づいている可能性がありますが、結果としてj <= jという冗長な境界チェックが生成される原因となっていました。

このコミットの変更は、a[i:j]形式のスライスにおいて、容量上限のノードcbを明示的にN（nilまたはnullノードを意味するGoコンパイラ内部の定数）に設定することで、この冗長なチェックの生成を停止させます。これにより、コンパイラはj <= jという無意味なチェックを生成しなくなり、結果として生成されるバイナリコードがわずかに小さく、効率的になります。この変更は、Goのメモリ安全性保証を損なうことなく、コンパイラの最適化を改善するものです。

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

diff --git a/src/cmd/gc/walk.c b/src/cmd/gc/walk.c
index 892d73bc6f..033b041f3c 100644
--- a/src/cmd/gc/walk.c
+++ b/src/cmd/gc/walk.c
@@ -2623,7 +2623,7 @@
 		cb = n->right->right->right;
 	} else {
 		hb = n->right->right;
-		cb = hb;
+		cb = N;
 	}
 
 	bounded = n->etype;

コアとなるコードの解説

変更はsrc/cmd/gc/walk.cファイルのsliceany関数内にあります。

• 変更前:

  	} else {
  		hb = n->right->right;
  		cb = hb;
  	}
  

  このコードブロックは、スライス式がa[i:j]形式（つまり、3番目のインデックスkが指定されていない場合）を処理しています。hbはスライスの「上限」（j）に対応するノードを指します。変更前は、容量上限（cb）もこのhbと同じノードを指すように設定されていました。これにより、コンパイラはjを容量上限としても扱い、結果としてj <= jという冗長な境界チェックが生成されていました。

• 変更後:

  	} else {
  		hb = n->right->right;
  		cb = N;
  	}
  

  変更後、a[i:j]形式のスライスの場合、容量上限（cb）は明示的にNに設定されます。NはGoコンパイラの内部で「nil」または「null」を意味するノードであり、これにより容量上限が指定されていないことをコンパイラに伝えます。その結果、コンパイラはj <= jという冗長な境界チェックを生成しなくなり、コードの効率が向上します。

この変更は、a[i:j:k]形式のスライスが導入された際に生じた、a[i:j]形式における不必要な境界チェックの生成というバグを修正するものです。

関連リンク

• Go CL 12311046: https://golang.org/cl/12311046

参考にした情報源リンク

• Go slice bound checks:
  • https://unskilled.blog/
  • https://go101.org/
  • https://medium.com/
  • https://labex.io/
  • https://stackoverflow.com/
• Go compiler cmd/gc:
  • https://cheney.net/
  • https://go.dev/
  • https://stackoverflow.com/
  • https://github.com/
• Go slice a[i:j] vs a[i:j:k]:
  • https://codecademy.com/
  • https://golang.ch/
  • https://go.dev/
  • https://tutorialsteacher.com/
  • https://syntaxdb.com/
  • https://stackoverflow.com/
  • https://hashnode.dev/
  • https://geeksforgeeks.org/
  • https://reddit.com/