cmd/compile: break false dependencies for x86 BSF/BSR instructions #82133

Go version

go1.27.1 amd64/linux

Output of go env in your module/workspace:

GOVERSION='go1.27.1'
GOOS=linux
GOARCH=amd64
GOAMD64=v1

What did you do?

Ran a benchmark of bits.TrailingZeros64, inspected the generated assembly, and recorded performance counters on an Intel Core Ultra 7 258V processor.

package main

import (
	"flag"
	"fmt"
	"math/bits"
)

var result uint64

//go:noinline
func scanLow(iterations uint64) uint64 {
	mask := uint64(1)
	var sum uint64
	for i := uint64(0); i < iterations; i++ {
		sum += uint64(bits.TrailingZeros64(mask))
		mask = bits.RotateLeft64(mask, 1)
	}
	return sum
}

//go:noinline
func scanHigh(iterations uint64) uint64 {
	mask := uint64(1)
	var sum uint64
	for i := uint64(0); i < iterations; i++ {
		sum += uint64(bits.Len64(mask) - 1)
		mask = bits.RotateLeft64(mask, 1)
	}
	return sum
}

func main() {
	mode := flag.String("mode", "low", "bit scan to exercise: low or high")
	iterations := flag.Uint64("iterations", 1_000_000_000, "number of bit scans")
	flag.Parse()
	if flag.NArg() != 0 {
		panic("unexpected positional arguments")
	}
	switch *mode {
	case "low":
		result = scanLow(*iterations)
	case "high":
		result = scanHigh(*iterations)
	default:
		panic("mode must be low or high")
	}
	tail := *iterations % 64
	want := (*iterations/64)*2016 + tail*(tail-1)/2
	if result != want {
		panic(fmt.Sprintf("incorrect result: got %d, want %d", result, want))
	}
	fmt.Printf("mode=%s iterations=%d checksum=%d\n", *mode, *iterations, result)
}

Build with:

GOARCH=amd64 GOAMD64=v1 go build -o main-amd64 main.go
GOARCH=386 GO386=sse2 go build -o main-386 main.go

Inspect the generated scans with:

go tool objdump -s 'main.scan(Low|High)' main-amd64
go tool objdump -s 'main.scanLow' main-386

scanHigh exercises BSRQ on amd64, but bits.Len64 does not generate BSRL on 386.

Measure the performance:

perf stat ./main-amd64
perf stat ./main-amd64 -mode=high
perf stat ./main-386

What did you see happen?

BSF and BSR have a dependency on the previous value of the destination register. The amd64 compiler emits BSFQ DX, SI without first breaking this dependency.

When register allocation reuses the destination register across loop iterations, otherwise independent bit scans become serialized, significantly reducing throughput.

What did you expect to see?

When the source and destination registers differ, the compiler should emit a zeroing idiom before BSF/BSR to break the false destination dependency:

XORL SI, SI
BSFQ DX, SI

The amd64 backend already uses this technique for POPCNT, TZCNT, and LZCNT. The same should be done for BSFQ, BSFL, BSRQ, and BSRL, with corresponding changes in the 386 backend.

I tested with a local compiler patch to emit the XORL instructions. One before/after measurement per target produced:

That is a 2.74× speedup on amd64 and 2.25× on 386, despite executing more instructions.

Real-world impact

I encountered this while optimizing the GC. Scanning performance was highly sensitive to whether register allocation produced dependencies between loop iterations. In one comparison, a build with the dependency showed the following regression relative to a baseline without it:

Tweaking the source code could make the compiler produce BSFQ src, src, avoiding the dependency. However, small source changes can cause the compiler to choose different registers and reintroduce the dependency. This makes performance improvements fragile; changes that reduce instructions or register pressure can still introduce a costly dependency between loop iterations and cause regressions.