cmd/compile: CSE has quadratic running time

[Jorropo]

Details

What version of Go are you using (go version)?

$ go version
go version go1.27-devel_9777ceceec Sat Feb 7 15:11:25 2026 -0800 linux/amd64

Does this issue reproduce with the latest release?

yes

What operating system and processor architecture are you using (go env)?

go env Output

$ go env
AR='ar'
CC='gcc'
CGO_CFLAGS='-O2 -g'
CGO_CPPFLAGS=''
CGO_CXXFLAGS='-O2 -g'
CGO_ENABLED='1'
CGO_FFLAGS='-O2 -g'
CGO_LDFLAGS='-O2 -g'
CXX='g++'
GCCGO='gccgo'
GO111MODULE=''
GOAMD64='v3'
GOARCH='amd64'
GOAUTH='netrc'
GOBIN=''
GOCACHE='/tmp/go-build'
GOCACHEPROG=''
GODEBUG=''
GOENV='/home/hugo/.config/go/env'
GOEXE=''
GOEXPERIMENT=''
GOFIPS140='off'
GOFLAGS=''
GOGCCFLAGS='-fPIC -m64 -pthread -Wl,--no-gc-sections -fmessage-length=0 -ffile-prefix-map=/tmp/go-build1000996818=/tmp/go-build -gno-record-gcc-switches'
GOHOSTARCH='amd64'
GOHOSTOS='linux'
GOINSECURE=''
GOMOD='/dev/null'
GOMODCACHE='/home/hugo/go/pkg/mod'
GONOPROXY=''
GONOSUMDB=''
GOOS='linux'
GOPATH='/home/hugo/go'
GOPRIVATE=''
GOPROXY='https://proxy.golang.org,direct'
GOROOT='/home/hugo/k/go'
GOSUMDB='sum.golang.org'
GOTELEMETRY='local'
GOTELEMETRYDIR='/home/hugo/.config/go/telemetry'
GOTMPDIR=''
GOTOOLCHAIN='local'
GOTOOLDIR='/home/hugo/k/go/pkg/tool/linux_amd64'
GOVCS=''
GOVERSION='go1.27-devel_9777ceceec Sat Feb 7 15:11:25 2026 -0800'
GOWORK=''
PKG_CONFIG='pkg-config'
GOROOT/bin/go version: go version go1.27-devel_9777ceceec Sat Feb 7 15:11:25 2026 -0800 linux/amd64
GOROOT/bin/go tool compile -V: compile version go1.27-devel_9777ceceec Sat Feb 7 15:11:25 2026 -0800
uname -sr: Linux 6.18.7-arch1-1
LSB Version:	n/a
Distributor ID:	Arch
Description:	Arch Linux
Release:	rolling
Codename:	n/a
/usr/lib/libc.so.6: GNU C Library (GNU libc) stable release version 2.42.
lldb --version: lldb version 21.1.6
gdb --version: GNU gdb (GDB) 17.1

What did you do?

Here is a script generating a minimized example:

// /tmp/a.go
package main

import "os"
import "bufio"
import "strconv"

func run() error {
	iterations, err := strconv.ParseUint(os.Args[1], 10, 64)
	if err != nil {
		return err
	}

	f, err := os.Create("/tmp/result.go")
	if err != nil {
		return err
	}
	defer f.Close()

	w := bufio.NewWriter(f)
	w.WriteString(`package a

type T *T

func a(n T) T {
`)
	for range iterations {
		w.WriteString("\tn = *n\n")
	}
	w.WriteString(`	return n
}
`)
	err = w.Flush()
	if err != nil {
		return err
	}

	err = f.Close()
	if err != nil {
		return err
	}
	return nil
}

func main() {
	if err := run(); err != nil {
		os.Stderr.WriteString(err.Error())
		os.Exit(1)
	}
	os.Exit(0)
}

Example of the result.go program with go run a.go 5:

package a

type T *T

func a(n T) T {
	n = *n
	n = *n
	n = *n
	n = *n
	n = *n
	return n
}

Bug repro:

> go run a.go 10000
> time go build results.go

What did you expect to see?

Compilation finishes quickly (maybe a second or two).

What did you see instead?

Compilation scales poorly:

[Jorropo]

After taking a profile here is the outlier:

go/src/cmd/compile/internal/ssa/cse.go

Lines 115 to 137 in 9777cec

	slices.SortFunc(e, func(v, w *Value) int {
	_, idxMem, _, _ := isMemUser(v)
	for i, a := range v.Args {
	var aId, bId ID
	if i != idxMem {
	b := w.Args[i]
	aId = a.ID
	bId = b.ID
	} else {
	// A memory user's mem argument may be remapped to allow matching
	// identical load-like instructions across disjoint stores.
	aId, _ = getEffectiveMemoryArg(memTable, v)
	bId, _ = getEffectiveMemoryArg(memTable, w)
	}
	if valueEqClass[aId] < valueEqClass[bId] {
	return -1
	}
	if valueEqClass[aId] > valueEqClass[bId] {
	return +1
	}
	}
	return 0
	})

[Jorropo]

Actually I did not checked that this compare function is > O(1), it could be that slices.SortFunc is called too often.

Edit: The cost of that compare function isn't the problem, the outer algorithm is calling slices.SortFunc O(n²) time.

[gabyhelp]

Related Issues

• cmd/compile: compile time increased greatly in 1.25rc1 with commit ed24bb4e60 #74615 (closed)
• cmd/compile: slow escape analysis in large package in the typescript compiler #72815 (closed)
• cmd/compile/internal/escape: performance issue #67313 (closed)
• cmd/compile: consider speeding up compile of large ast package in microsoft/typescript-go #73044
• cmd/compile: compileSSA takes a long time on very large (generated) functions #30077
• cmd/compile: exponential behavior for deeply nested structs #65540
• cmd/compile: excessive time spent in line numbering #75001
• cmd/compile: infinite loop in the inliner #73425 (closed)
• cmd/compile: compiling nested generics consumes a lot of memory and takes a long time #76661

Related Code Changes

• cmd/compile: compile more complex functions first

_{(Emoji vote if this was helpful or unhelpful; more detailed feedback welcome in this discussion.)}

[Jorropo]

Ok so, I've hoisted the sort function with the idea that the loops it is a part of preserve the []eqclass order.

This makes time go down from 53s to 29s.

However the >= O(n^2) behavior continues happening.
Also I don't think this change is correct since the valueEqClass is being changed in the loop I've hoisted it from, so I guess the sort isn't correct if we don't rerun it.

After reviewing the code this comment looks to be completely wrong:

		// partition can grow in the loop. By not using a range loop here,
		// we process new additions as they arrive, avoiding O(n^2) behavior.

It probably were true 10 years ago when it was written but isn't anymore.

Worst case analysis

Note I've added debug statements and this is what I am observing:

Start with 1 very long partition:

This first loop:

go/src/cmd/compile/internal/ssa/cse.go

Lines 140 to 172 in 9777cec

	splitPoints = append(splitPoints[:0], 0)
	for j := 1; j < len(e); j++ {
	v, w := e[j-1], e[j]
	// Note: commutative args already correctly ordered by byArgClass.
	eqArgs := true
	_, idxMem, _, _ := isMemUser(v)
	for k, a := range v.Args {
	if v.Op == OpLocalAddr && k == 1 {
	continue
	}
	var aId, bId ID
	if k != idxMem {
	b := w.Args[k]
	aId = a.ID
	bId = b.ID
	} else {
	// A memory user's mem argument may be remapped to allow matching
	// identical load-like instructions across disjoint stores.
	aId, _ = getEffectiveMemoryArg(memTable, v)
	bId, _ = getEffectiveMemoryArg(memTable, w)
	}
	if valueEqClass[aId] != valueEqClass[bId] {
	eqArgs = false
	break
	}
	}
	if !eqArgs {
	splitPoints = append(splitPoints, j)
	}
	}
	if len(splitPoints) == 1 {
	continue // no splits, leave equivalence class alone.
	}

Iterate over all es in the partition.

Then assuming it finds split points this loop pushes them onto partition:

go/src/cmd/compile/internal/ssa/cse.go

Lines 180 to 193 in 9777cec

	splitPoints = append(splitPoints, len(e))
	for j := 0; j < len(splitPoints)-1; j++ {
	f := e[splitPoints[j]:splitPoints[j+1]]
	if len(f) == 1 {
	// Don't add singletons.
	valueEqClass[f[0].ID] = -f[0].ID
	continue
	}
	for _, v := range f {
	valueEqClass[v.ID] = pNum
	}
	pNum++
	partition = append(partition, f)
	}

In the worst case we will pop a single eqclass from e. We push that slice with one less element onto partition

However later we are then gonna loop on the new partition entry we just pushed and rescan all the es.

In the worst case we remove one e from the []eqclass at each outer loop iteration giving us f(n) = n + f(n-1) = (n²+n)/2.

---

I think the fix would be to interleave theses two loops somehow:

go/src/cmd/compile/internal/ssa/cse.go

Lines 139 to 193 in 9777cec

	// Find split points.
	splitPoints = append(splitPoints[:0], 0)
	for j := 1; j < len(e); j++ {
	v, w := e[j-1], e[j]
	// Note: commutative args already correctly ordered by byArgClass.
	eqArgs := true
	_, idxMem, _, _ := isMemUser(v)
	for k, a := range v.Args {
	if v.Op == OpLocalAddr && k == 1 {
	continue
	}
	var aId, bId ID
	if k != idxMem {
	b := w.Args[k]
	aId = a.ID
	bId = b.ID
	} else {
	// A memory user's mem argument may be remapped to allow matching
	// identical load-like instructions across disjoint stores.
	aId, _ = getEffectiveMemoryArg(memTable, v)
	bId, _ = getEffectiveMemoryArg(memTable, w)
	}
	if valueEqClass[aId] != valueEqClass[bId] {
	eqArgs = false
	break
	}
	}
	if !eqArgs {
	splitPoints = append(splitPoints, j)
	}
	}
	if len(splitPoints) == 1 {
	continue // no splits, leave equivalence class alone.
	}
	// Move another equivalence class down in place of e.
	partition[i] = partition[len(partition)-1]
	partition = partition[:len(partition)-1]
	i--
	// Add new equivalence classes for the parts of e we found.
	splitPoints = append(splitPoints, len(e))
	for j := 0; j < len(splitPoints)-1; j++ {
	f := e[splitPoints[j]:splitPoints[j+1]]
	if len(f) == 1 {
	// Don't add singletons.
	valueEqClass[f[0].ID] = -f[0].ID
	continue
	}
	for _, v := range f {
	valueEqClass[v.ID] = pNum
	}
	pNum++
	partition = append(partition, f)
	}

Such that we would find all the split points of an []eqclass in one pass rather than popping off elements one at a time.

I'm not instantly picturing how this would look.
I don't yet know how the CSE algorithm work, tbh I would expect a two-pass O(v+e) (e = Value.Args) graph based algorithm.

[Jorropo]

cc @randall77

[Jorropo]

After a bit of searching, it looks like the optimal algorithm ¿ Paige-Tarjan ? is O(e log v) so a bit worst than O(e + v) but needless to say today we extremely far away from writing a compiler without using a comparative sort so O(n log n) is acceptable.

Also practically speaking e = O(v) since the amount of argument per ssa node is capped (¿ assuming non regabi calls are spilled early ?).