cmd/compile: rerwrite cycle detection logic taking too long for large functions

[CodFrm]

Go version

go version go1.21.9 darwin/arm64

Output of go env in your module/workspace:

GO111MODULE='on'
GOARCH='arm64'
GOBIN=''
GOCACHE='/Users/codfrm/Library/Caches/go-build'
GOENV='/Users/codfrm/Library/Application Support/go/env'
GOEXE=''
GOEXPERIMENT=''
GOFLAGS=''
GOHOSTARCH='arm64'
GOHOSTOS='darwin'
GOINSECURE=''
GOMODCACHE='/Users/codfrm/go/pkg/mod'
GONOPROXY=''
GONOSUMDB=''
GOOS='darwin'
GOPATH='/Users/codfrm/go'
GOPRIVATE=''
GOPROXY='https://goproxy.cn,direct'
GOROOT='/Users/codfrm/go/go1.21.9'
GOSUMDB='sum.golang.org'
GOTMPDIR=''
GOTOOLCHAIN='auto'
GOTOOLDIR='/Users/codfrm/go/go1.21.9/pkg/tool/darwin_arm64'
GOVCS=''
GOVERSION='go1.21.9'
GCCGO='gccgo'
AR='ar'
CC='clang'
CXX='clang++'
CGO_ENABLED='1'
GOMOD='****/test/go.mod'
GOWORK=''
CGO_CFLAGS='-O2 -g'
CGO_CPPFLAGS=''
CGO_CXXFLAGS='-O2 -g'
CGO_FFLAGS='-O2 -g'
CGO_LDFLAGS='-O2 -g'
PKG_CONFIG='pkg-config'
GOGCCFLAGS='-fPIC -arch arm64 -pthread -fno-caret-diagnostics -Qunused-arguments -fmessage-length=0 -ffile-prefix-map=/var/folders/xr/2xv9m3_j4vd3hp0bdjx52z7m0000gn/T/go-build1074337786=/tmp/go-build -gno-record-gcc-switches -fno-common'

What did you do?

The code gets stuck when building it with go1.21, but it builds fine with go1.18

What did you see happen?

It keeps getting stuck when building the source code below using the command:

go build -x -work -v main.go

WORK=/var/folders/xr/2xv9m3_j4vd3hp0bdjx52z7m0000gn/T/go-build2102151065
test/src
mkdir -p $WORK/b043/
cat >/var/folders/xr/2xv9m3_j4vd3hp0bdjx52z7m0000gn/T/go-build2102151065/b043/importcfg << 'EOF' # internal
# import config
EOF
cd /****/test
/Users/codfrm/go/go1.21.9/pkg/tool/darwin_arm64/compile -o $WORK/b043/_pkg_.a -trimpath "$WORK/b043=>" -p test/src -lang=go1.18 -complete -buildid BVwUNF2ANdz8supqWmvy/BVwUNF2ANdz8supqWmvy -goversion go1.21.9 -c=4 -shared -nolocalimports -importcfg $WORK/b043/importcfg -pack ./src/t.go

code.zip

What did you expect to see?

It can be built normally using go1.21 or higher version

[seankhliao]

have you considered not having 10000 lines of i = append(i, 1) in a function?

cc @golang/compiler

[CodFrm]

Of course, this is meaningless. It's just that I'm curious why it's possible in go1.18

[thanm]

Ordinarily it would be as @seankhliao says ... "don't do that".

However there is actually something interesting going on here. I patched this change into my Go repo:

diff --git a/src/cmd/compile/internal/gc/util.go b/src/cmd/compile/internal/gc/util.go
index dcaca892db..7f0d5fad64 100644
--- a/src/cmd/compile/internal/gc/util.go
+++ b/src/cmd/compile/internal/gc/util.go
@@ -5,13 +5,16 @@
 package gc
 
 import (
+	"fmt"
 	"net/url"
 	"os"
+	"os/signal"
 	"path/filepath"
 	"runtime"
 	"runtime/pprof"
 	tracepkg "runtime/trace"
 	"strings"
+	"syscall"
 
 	"cmd/compile/internal/base"
 )
@@ -39,6 +42,17 @@ func startProfile() {
 		if err := pprof.StartCPUProfile(f); err != nil {
 			base.Fatalf("%v", err)
 		}
+		sigs := make(chan os.Signal, 1)
+		signal.Notify(sigs, syscall.SIGUSR1)
+		go func() {
+			sig := <-sigs
+			fmt.Fprintf(os.Stderr, "=-= received %v, writing cpu profile\n",
+				sig)
+			pprof.StopCPUProfile()
+			if err = f.Close(); err != nil {
+				base.Fatalf("error closing cpu profile: %v", err)
+			}
+		}()
 		base.AtExit(func() {
 			pprof.StopCPUProfile()
 			if err = f.Close(); err != nil {

Then I did a test compile, e.g.

$ go tool compile -p=p -cpuprofile=cpu.p t.go &
[1] 205845
$ sleep 60 ; kill -USR1 205845

Looking at this profile, I see:

                                            71.42s   100% |   cmd/compile/internal/ssa.opt
     4.98s  6.68% 71.52%     71.42s 95.85%                | cmd/compile/internal/ssa.applyRewrite
                                            62.70s 87.79% |   cmd/compile/internal/ssa.(*Func).rewriteHash
                                             2.44s  3.42% |   cmd/compile/internal/ssa.rewriteValuegeneric
                                             0.74s  1.04% |   cmd/compile/internal/ssa.phielimValue (inline)
                                             0.43s   0.6% |   cmd/compile/internal/ssa.(*Value).removeable (inline)

It looks as though what's happening is that this code here is kicking in:

https://go.googlesource.com/go/+/45b641ce15159e29fa4494b837493042d1e10384/src/cmd/compile/internal/ssa/rewrite.go#158

E.g. because of the enormous size of the function, the rewriter notices that there have been a large number of rewrites, so it turns on the cycle-detection logic. For this enormous func, however, the cycle detection logic takes a couple of orders of magnitude more time than the rewriting itself.

If I comment out the cycle detection logic, the file compiles in about 90 seconds.

I think this is probably actionable, we can change things to skip the cycle detection logic if the function itself is over some size limit.

[gopherbot]

Change https://go.dev/cl/578215 mentions this issue: cmd/compile/internal/ssa: disable rewrite cycle detection for huge funcs