Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

cmd/compile: index out of bounds in code the compiler can prove is never executed #56667

Closed
ncw opened this issue Nov 9, 2022 · 5 comments
Closed
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. FrozenDueToAge NeedsDecision Feedback is required from experts, contributors, and/or the community before a change can be made.
Milestone

Comments

@ncw
Copy link
Contributor

ncw commented Nov 9, 2022

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

go version devel go1.20-3a41094107 Wed Nov 9 06:30:59 2022 +0000 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
GO111MODULE=""
GOARCH="amd64"
GOBIN=""
GOCACHE="/home/ncw/.cache/go-build"
GOENV="/home/ncw/.config/go/env"
GOEXE=""
GOEXPERIMENT=""
GOFLAGS=""
GOHOSTARCH="amd64"
GOHOSTOS="linux"
GOINSECURE=""
GOMODCACHE="/home/ncw/go/pkg/mod"
GONOPROXY=""
GONOSUMDB=""
GOOS="linux"
GOPATH="/home/ncw/go"
GOPRIVATE=""
GOPROXY="https://proxy.golang.org,direct"
GOROOT="/opt/go/go-tip"
GOSUMDB="sum.golang.org"
GOTMPDIR=""
GOTOOLDIR="/opt/go/go-tip/pkg/tool/linux_amd64"
GOVCS=""
GOVERSION="devel go1.20-3a41094107 Wed Nov 9 06:30:59 2022 +0000"
GCCGO="gccgo"
GOAMD64="v1"
AR="ar"
CC="gcc"
CXX="g++"
CGO_ENABLED="1"
GOMOD="/dev/null"
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 -m64 -pthread -Wl,--no-gc-sections -fmessage-length=0 -fdebug-prefix-map=/tmp/go-build3118064585=/tmp/go-build -gno-record-gcc-switches"

What did you do?

I attempted to compile this program which implements fixed point arithmetic. The number of terms is a compile time constant and I was attempting to unroll the loop. Playground.

package main

import "math/bits"

// terms in fixed point - compile time constant
const terms = 2

// fixed point 0..1
type fixed [terms]uint64

// Add a + b mod 1
func add(a, b fixed) (result fixed) {
	var carry uint64
	// Attempt to unroll loop
	result[0], carry = bits.Add64(a[0], b[0], 0)
	if terms > 1 {
		result[1], carry = bits.Add64(a[1], b[1], carry)
	}
	if terms > 2 {
		result[2], carry = bits.Add64(a[2], b[2], carry)
	}
	if terms > 3 {
		result[3], carry = bits.Add64(a[3], b[3], carry)
	}
	// ignore carry
	return result
}

What did you expect to see?

I hoped it would compile as terms is a compile time constant (2), so the compiler should be able to prove that this code is never executed, and hence the out of bounds array accesses never happen

	if terms > 2 {
		result[2], carry = bits.Add64(a[2], b[2], carry) // line 20
	}
	if terms > 3 {
		result[3], carry = bits.Add64(a[3], b[3], carry) // line 23
	}

What did you see instead?

I get the following compiler errors

./compile-unroll-bug.go:20:35: invalid argument: index 2 out of bounds [0:2]
./compile-unroll-bug.go:23:35: invalid argument: index 3 out of bounds [0:2]
@gopherbot gopherbot added the compiler/runtime Issues related to the Go compiler and/or runtime. label Nov 9, 2022
@mknyszek
Copy link
Contributor

mknyszek commented Nov 9, 2022

CC @golang/compiler

@mknyszek
Copy link
Contributor

mknyszek commented Nov 9, 2022

I believe this restriction of failing to index into an array with a constant is something that's come up before and I think it's actually part of the spec (https://go.dev/ref/spec#Index_expressions). However, I cannot find an issue discussing this in more detail.

I'm not certain there's anything to do here short of filing a proposal for a language change.

@mknyszek mknyszek added the NeedsDecision Feedback is required from experts, contributors, and/or the community before a change can be made. label Nov 9, 2022
@mknyszek mknyszek added this to the Backlog milestone Nov 9, 2022
@mknyszek mknyszek closed this as not planned Won't fix, can't repro, duplicate, stale Nov 9, 2022
@mdempsky
Copy link
Contributor

mdempsky commented Nov 9, 2022

Yeah this is working according to the spec.

@mknyszek
Copy link
Contributor

mknyszek commented Nov 9, 2022

Just to give a slightly more satisfying answer: I believe the reason why is because the Go compiler generally disallows programs that are statically known to panic (e.g. divide by constant zero will fail to compile). (Thanks to @cherrymui for pointing that out.) While it is possible to write code that the compiler can prove won't panic statically, making the language spec depend on that mixes semantic specification and implementation in a way that's restrictive.

Perhaps someone with better knowledge of the history of this and the spec can chime in.

@ncw
Copy link
Contributor Author

ncw commented Nov 9, 2022

Thanks for the explanation.

The spec says this about index expressions of the form a[x]

For a of array type A:

Which does indeed seem very clear.

I guess I've been writing too much Zig code!

@golang golang locked and limited conversation to collaborators Nov 9, 2023
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. FrozenDueToAge NeedsDecision Feedback is required from experts, contributors, and/or the community before a change can be made.
Projects
None yet
Development

No branches or pull requests

4 participants