cmd/compile: internal compiler error: panic during prove while compiling: unexpected induction with too many parents #63955

fzipp · 2023-11-05T17:41:28Z

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

$ go version
go version devel go1.22-d72f4542fe Fri Nov 3 19:58:00 2023 +0000 darwin/arm64

Does this issue reproduce with the latest release?

It does not reproduce with the 1.21 release, only with the 1.22 development version.

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

go env Output

$ go env
GO111MODULE=''
GOARCH='arm64'
GOBIN=''
GOCACHE='/Users/frederik/Library/Caches/go-build'
GOENV='/Users/frederik/Library/Application Support/go/env'
GOEXE=''
GOEXPERIMENT=''
GOFLAGS=''
GOHOSTARCH='arm64'
GOHOSTOS='darwin'
GOINSECURE=''
GOMODCACHE='/Users/frederik/go/pkg/mod'
GONOPROXY=''
GONOSUMDB=''
GOOS='darwin'
GOPATH='/Users/frederik/go'
GOPRIVATE=''
GOPROXY='https://proxy.golang.org,direct'
GOROOT='/Users/frederik/go/src/go.googlesource.com/go'
GOSUMDB='sum.golang.org'
GOTMPDIR=''
GOTOOLCHAIN='auto'
GOTOOLDIR='/Users/frederik/go/src/go.googlesource.com/go/pkg/tool/darwin_arm64'
GOVCS=''
GOVERSION='devel go1.22-d72f4542fe Fri Nov 3 19:58:00 2023 +0000'
GCCGO='gccgo'
AR='ar'
CC='clang'
CXX='clang++'
CGO_ENABLED='1'
GOMOD='/Users/frederik/bugdemo/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/9g/vgkswhbn2tn8r6h6f6ry7wl80000gn/T/go-build2774285608=/tmp/go-build -gno-record-gcc-switches -fno-common'

What did you do?

I tried to compile a minimal program using the oto library with the devel version of Go 1.22 on Darwin:

package main

import "github.com/ebitengine/oto/v3"

func main() {
	_ = &oto.NewContextOptions{}
}

module bugdemo

go 1.22

require (
        github.com/ebitengine/oto/v3 v3.1.0 // indirect
        github.com/ebitengine/purego v0.5.0 // indirect
        golang.org/x/sys v0.12.0 // indirect
)

% go build

What did you expect to see?

Successful compilation as with Go 1.21.

What did you see instead?

An internal compiler error:

/Users/frederik/go/pkg/mod/github.com/ebitengine/oto/v3@v3.1.0/driver_darwin.go:203:2: internal compiler error: '(*context).Resume': panic during prove while compiling (*context).Resume:

unexpected induction with too many parents

goroutine 1 [running]:
cmd/compile/internal/ssa.Compile.func1()
	/Users/frederik/go/src/go.googlesource.com/go/src/cmd/compile/internal/ssa/compile.go:49 +0x6c
panic({0x10555e3a0?, 0x1055fe660?})
	/Users/frederik/go/src/go.googlesource.com/go/src/runtime/panic.go:763 +0x124
cmd/compile/internal/ssa.prove(0x14000b549c0)
	/Users/frederik/go/src/go.googlesource.com/go/src/cmd/compile/internal/ssa/prove.go:808 +0x1da8
cmd/compile/internal/ssa.Compile(0x14000b549c0)
	/Users/frederik/go/src/go.googlesource.com/go/src/cmd/compile/internal/ssa/compile.go:97 +0x93c
cmd/compile/internal/ssagen.buildssa(0x1400073b9e0, 0x0)
	/Users/frederik/go/src/go.googlesource.com/go/src/cmd/compile/internal/ssagen/ssa.go:575 +0x1ddc
cmd/compile/internal/ssagen.Compile(0x1400073b9e0, 0x0)
	/Users/frederik/go/src/go.googlesource.com/go/src/cmd/compile/internal/ssagen/pgen.go:216 +0x34
cmd/compile/internal/gc.compileFunctions.func5.1(0x12cc4f101?)
	/Users/frederik/go/src/go.googlesource.com/go/src/cmd/compile/internal/gc/compile.go:182 +0x3c
cmd/compile/internal/gc.compileFunctions.func2(0x14000060600?)
	/Users/frederik/go/src/go.googlesource.com/go/src/cmd/compile/internal/gc/compile.go:136 +0x28
cmd/compile/internal/gc.compileFunctions.func5({0x140009ca600?, 0x24, 0x1055fc4f0?})
	/Users/frederik/go/src/go.googlesource.com/go/src/cmd/compile/internal/gc/compile.go:181 +0x64
cmd/compile/internal/gc.compileFunctions()
	/Users/frederik/go/src/go.googlesource.com/go/src/cmd/compile/internal/gc/compile.go:192 +0x1f4
cmd/compile/internal/gc.Main(0x1055fc380)
	/Users/frederik/go/src/go.googlesource.com/go/src/cmd/compile/internal/gc/main.go:318 +0x1200
main.main()
	/Users/frederik/go/src/go.googlesource.com/go/src/cmd/compile/main.go:57 +0x110

goroutine 1 [running]:
runtime/debug.Stack()
	/Users/frederik/go/src/go.googlesource.com/go/src/runtime/debug/stack.go:24 +0x64
cmd/compile/internal/base.FatalfAt({0x5e2248?, 0x140?}, {0x14000b48a00, 0x32}, {0x14000a9f590?, 0x5, 0x5})
	/Users/frederik/go/src/go.googlesource.com/go/src/cmd/compile/internal/base/print.go:225 +0x200
cmd/compile/internal/base.Fatalf(...)
	/Users/frederik/go/src/go.googlesource.com/go/src/cmd/compile/internal/base/print.go:194
cmd/compile/internal/ssagen.(*ssafn).Fatalf(0x12cc5d110?, {0x18?, 0x0?}, {0x1053dbadd, 0x2c}, {0x14000b5e840?, 0x4, 0x0?})
	/Users/frederik/go/src/go.googlesource.com/go/src/cmd/compile/internal/ssagen/ssa.go:8225 +0x154
cmd/compile/internal/ssa.(*Func).Fatalf(0x14000b549c0, {0x1053dbadd, 0x2c}, {0x14000b5e840?, 0x4, 0x4})
	/Users/frederik/go/src/go.googlesource.com/go/src/cmd/compile/internal/ssa/func.go:742 +0x260
cmd/compile/internal/ssa.Compile.func1()
	/Users/frederik/go/src/go.googlesource.com/go/src/cmd/compile/internal/ssa/compile.go:54 +0x1a4
panic({0x10555e3a0?, 0x1055fe660?})
	/Users/frederik/go/src/go.googlesource.com/go/src/runtime/panic.go:763 +0x124
cmd/compile/internal/ssa.prove(0x14000b549c0)
	/Users/frederik/go/src/go.googlesource.com/go/src/cmd/compile/internal/ssa/prove.go:808 +0x1da8
cmd/compile/internal/ssa.Compile(0x14000b549c0)
	/Users/frederik/go/src/go.googlesource.com/go/src/cmd/compile/internal/ssa/compile.go:97 +0x93c
cmd/compile/internal/ssagen.buildssa(0x1400073b9e0, 0x0)
	/Users/frederik/go/src/go.googlesource.com/go/src/cmd/compile/internal/ssagen/ssa.go:575 +0x1ddc
cmd/compile/internal/ssagen.Compile(0x1400073b9e0, 0x0)
	/Users/frederik/go/src/go.googlesource.com/go/src/cmd/compile/internal/ssagen/pgen.go:216 +0x34
cmd/compile/internal/gc.compileFunctions.func5.1(0x12cc4f101?)
	/Users/frederik/go/src/go.googlesource.com/go/src/cmd/compile/internal/gc/compile.go:182 +0x3c
cmd/compile/internal/gc.compileFunctions.func2(0x14000060600?)
	/Users/frederik/go/src/go.googlesource.com/go/src/cmd/compile/internal/gc/compile.go:136 +0x28
cmd/compile/internal/gc.compileFunctions.func5({0x140009ca600?, 0x24, 0x1055fc4f0?})
	/Users/frederik/go/src/go.googlesource.com/go/src/cmd/compile/internal/gc/compile.go:181 +0x64
cmd/compile/internal/gc.compileFunctions()
	/Users/frederik/go/src/go.googlesource.com/go/src/cmd/compile/internal/gc/compile.go:192 +0x1f4
cmd/compile/internal/gc.Main(0x1055fc380)
	/Users/frederik/go/src/go.googlesource.com/go/src/cmd/compile/internal/gc/main.go:318 +0x1200
main.main()
	/Users/frederik/go/src/go.googlesource.com/go/src/cmd/compile/main.go:57 +0x110

The text was updated successfully, but these errors were encountered:

mauri870 · 2023-11-05T19:04:21Z

/cc @golang/compiler

randall77 · 2023-11-05T19:17:09Z

@Jorropo That error is from your CL from July. Not sure it is the culprit, but looks likely, as there's not much else that has changed about prove lately.

Jorropo · 2023-11-05T19:19:41Z

I'll take a look thx.

Jorropo · 2023-11-05T19:31:33Z

After a quick 2 step bisection, I confirm that bac4e2f is the faulty commit.

Jorropo · 2023-11-05T21:05:27Z

I think this is a latent bug in findIndVar.

See right here:

		if b.Kind != BlockIf || len(b.Preds) != 2 { // it tries to only match blocks with 2 preds
			continue
		}

		var ind *Value   // induction variable
		var init *Value  // starting value
		var limit *Value // ending value

		// Check that the control if it either ind </<= limit or limit </<= ind.
		// TODO: Handle unsigned comparisons?
		c := b.Controls[0]
		inclusive := false
		switch c.Op {
		case OpLeq64, OpLeq32, OpLeq16, OpLeq8:
			inclusive = true
			fallthrough
		case OpLess64, OpLess32, OpLess16, OpLess8:
			ind, limit = c.Args[0], c.Args[1]
		default:
			continue
		}

It then extract ind and limit from the control.
And it assume they are local-ish, because if they were not there would be a φ between ind and the control value which would become ind.

However consider that this wouldn't be true if there are blocks between ind and b an in all successors ind exists.
May I now present to you:

	b15:
		v270 = Phi <int> v134 v179 v270 (count[int], retryCount[int])
		v136 = Phi <mem> v68 v177 v185
		v137 = Copy <*context> v15
		v138 = OffPtr <*_AudioQueueRef> [0] v137
		v139 = Load <_AudioQueueRef> v138 v136
		v141 = Load <func(_AudioQueueRef, *_AudioTimeStamp) uintptr> v140 v136
		v143 = Load <uintptr> v141 v136
		v144 = ClosureLECall <uintptr,mem> {AuxCall{nil}} [16] v143 v141 v139 v142 v136
		v146 = SelectN <uintptr> [0] v144 (osstatus[uintptr])
		v147 = Neq64 <bool> v146 v39
		v145 = SelectN <mem> [1] v144
	If v147 -> b17 b45
	b17:
		v150 = Eq64 <bool> v149 v146
	If v150 -> b20 b18
	b18:
		v153 = Eq64 <bool> v152 v146
	If v153 -> b20 b22
	b20:
		v157 = Less64 <bool> v270 v156
	If v157 -> b23 b22
	b22:
		v182 = Eq64 <bool> v181 v146
	If v182 -> b39 b38
	b23:
		v162 = InlMark <void> [4] v145
		v163 = Eq64 <bool> v270 v134
	If v163 -> b28 b27
	b27:
		v166 = Eq64 <bool> v270 v165
	If v166 -> b32 b31
	b28:
	Plain -> b37
	b31:
		v169 = Eq64 <bool> v270 v168
	If v169 -> b35 b36
	b32:
	Plain -> b37
	b35:
	Plain -> b37
	b36:
	Plain -> b37
	b37:
		v174 = Phi <time.Duration> v170 v171 v172 v173 (~r0[time.Duration])
		v176 = StaticLECall <mem> {AuxCall{time.Sleep}} [8] v174 v145
		v177 = SelectN <mem> [0] v176
		v179 = Add64 <int> v270 v165 (retryCount[int])
	Plain -> b15

Here b is b20 and ind is b.Controls[0].Args[0] so v270.
Then my code tries to figure out which blocks is the loop header.
However in reality the header is really multiple blocks which stretch between b15, b17, b18 and b20.
What lead me to think this is a bug in findIndVar is the || len(b.Preds) != 2.
Let's assume the code were written this way instead:

	b17:
		v150 = Eq64 <bool> v149 v146
-	If v150 -> b20 b18
+	If v150 -> b20 b22
-	b18:
-		v153 = Eq64 <bool> v152 v146
-	If v153 -> b20 b22
	b20:
		v157 = Less64 <bool> v270 v156
	If v157 -> b23 b22

This changes nothing in term of loop semantics, I removed an || clause from an if ... { break } yet findIndVar wouldn't be able to match it anymore because b20 would only have one predecessor.

After a quick review of findIndVar and indVars I think this is safe, as in they can handle code where ind is disjointed from the last loop header block, even tho this was not intended.
So || len(b.Preds) != 2 should be removed and my code should be made more resistant to handle cases where the ind variable has many predecessors. This particular function should be rewritable even tho it has a branch which continue without incrementing the induction variable.

I'll submit a patch later, if I didn't in a few days feel free to revert.

Jorropo · 2023-11-05T21:26:14Z

Update:
No it does not look very safe, see:

func parseIndVar(ind *Value) (min, inc, nxt *Value) {
	if ind.Op != OpPhi {
		return
	}

	if n := ind.Args[0]; (n.Op == OpAdd64 || n.Op == OpAdd32 || n.Op == OpAdd16 || n.Op == OpAdd8) && (n.Args[0] == ind || n.Args[1] == ind) {
		min, nxt = ind.Args[1], n
	} else if n := ind.Args[1]; (n.Op == OpAdd64 || n.Op == OpAdd32 || n.Op == OpAdd16 || n.Op == OpAdd8) && (n.Args[0] == ind || n.Args[1] == ind) {
		min, nxt = ind.Args[0], n
	} else {
		// Not a recognized induction variable.
		return
	}

	if nxt.Args[0] == ind { // nxt = ind + inc
		inc = nxt.Args[1]
	} else if nxt.Args[1] == ind { // nxt = inc + ind
		inc = nxt.Args[0]
	} else {
		panic("unreachable") // one of the cases must be true from the above.
	}

	return
}

If this were safe it should iterate over ind.Args, it also currently assume that min is which ever one nxt is not out of ind.Args[:2], which is wrong, they could both be induced by the loop and min could be ind.Args[2].
I'll update findIndArgs so that it does not match this pattern anymore.
I guess prove and loopbce.go could be extended to handle disjointed loop headers and multi-entry loop headers, but then some new map or CFG traversal would be needed in parseIndVar to figure out which one is induced from the loop. min would also a []*Value.
And I'm gonna rule this out as unlikely optimization to trigger given no one reported a miss-compilation of this before my code asserted the latent bug loudly.

gopherbot · 2023-11-05T21:46:07Z

Change https://go.dev/cl/539977 mentions this issue: cmd/compile: fix findIndVar so it does not match disjointed loop headers

Jorropo · 2023-11-05T22:11:25Z

@randall77
I'm fairly sure someone could construct some hellish goto, break, continue, if, for mess such that they could get 1.21.3 and go1.20.10 to match a disjointed loop header in order to have a 3 argument ind φ where parseIndVar would incorrectly extract min.
Which could cause prove to remove checks in the loop body where it must not. Potentially creating out of bound array accesses.

I don't think the particular code pattern required is likely to be seen in the wild.
But given the fix is so simple this would be nice to include in the next backport release.

randall77 · 2023-11-07T17:36:40Z

@gopherbot please open backport issues.

I agree that if this could cause a miscompilation we should backport.
It does seem exceedingly rare though.

gopherbot · 2023-11-07T17:36:55Z

Backport issue(s) opened: #63983 (for 1.20), #63984 (for 1.21).

Remember to create the cherry-pick CL(s) as soon as the patch is submitted to master, according to https://go.dev/wiki/MinorReleases.

gopherbot · 2024-02-03T08:10:08Z

Change https://go.dev/cl/560975 mentions this issue: cmd/compile: remove bug workarounds in prove's loop inverstion

I wrote theses checks because I got bad panics on some innocent functions, turns out I was working around #63955 but I was not aware of that at the time. The proper fix was included in CL 539977 this is now doing nothing. Change-Id: I89329329933527b6f3cb817dc1e039a38f58da9a Reviewed-on: https://go-review.googlesource.com/c/go/+/560975 Reviewed-by: Keith Randall <khr@golang.org> Reviewed-by: Keith Randall <khr@google.com> Auto-Submit: Keith Randall <khr@golang.org> Reviewed-by: Michael Knyszek <mknyszek@google.com> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>

gopherbot added the compiler/runtime Issues related to the Go compiler and/or runtime. label Nov 5, 2023

mauri870 added the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Nov 5, 2023

gopherbot closed this as completed in 8b4e125 Nov 7, 2023

dmitshur added NeedsFix The path to resolution is known, but the work has not been done. and removed NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. labels Nov 27, 2023

dmitshur added this to the Go1.22 milestone Nov 27, 2023

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

cmd/compile: internal compiler error: panic during prove while compiling: unexpected induction with too many parents #63955

cmd/compile: internal compiler error: panic during prove while compiling: unexpected induction with too many parents #63955

fzipp commented Nov 5, 2023

mauri870 commented Nov 5, 2023

randall77 commented Nov 5, 2023

Jorropo commented Nov 5, 2023

Jorropo commented Nov 5, 2023 •

edited

Jorropo commented Nov 5, 2023 •

edited

Jorropo commented Nov 5, 2023 •

edited

gopherbot commented Nov 5, 2023

Jorropo commented Nov 5, 2023 •

edited

randall77 commented Nov 7, 2023

gopherbot commented Nov 7, 2023

gopherbot commented Feb 3, 2024

cmd/compile: internal compiler error: panic during prove while compiling: unexpected induction with too many parents #63955

cmd/compile: internal compiler error: panic during prove while compiling: unexpected induction with too many parents #63955

Comments

fzipp commented Nov 5, 2023

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

Does this issue reproduce with the latest release?

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

What did you do?

What did you expect to see?

What did you see instead?

mauri870 commented Nov 5, 2023

randall77 commented Nov 5, 2023

Jorropo commented Nov 5, 2023

Jorropo commented Nov 5, 2023 • edited

Jorropo commented Nov 5, 2023 • edited

Jorropo commented Nov 5, 2023 • edited

gopherbot commented Nov 5, 2023

Jorropo commented Nov 5, 2023 • edited

randall77 commented Nov 7, 2023

gopherbot commented Nov 7, 2023

gopherbot commented Feb 3, 2024

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

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

Jorropo commented Nov 5, 2023 •

edited

Jorropo commented Nov 5, 2023 •

edited

Jorropo commented Nov 5, 2023 •

edited

Jorropo commented Nov 5, 2023 •

edited