cmd/compile: incorrect code generation bug when taking slice[:0]

[ncw]

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

go version devel +204a8f55dc Tue Jan 1 20:15:48 2019 +0000 linux/amd64

Also reproduces on go1.11.4

Does this issue reproduce with the latest release?

Yes

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

go env Output

GOARCH="amd64"
GOBIN=""
GOCACHE="/home/ncw/.cache/go-build"
GOEXE=""
GOFLAGS=""
GOHOSTARCH="amd64"
GOHOSTOS="linux"
GOOS="linux"
GOPATH="/home/ncw/go"
GOPROXY=""
GORACE=""
GOROOT="/opt/go/go-tip"
GOTMPDIR=""
GOTOOLDIR="/opt/go/go-tip/pkg/tool/linux_amd64"
GCCGO="gccgo"
CC="gcc"
CXX="g++"
CGO_ENABLED="1"
GOMOD=""
CGO_CFLAGS="-g -O2"
CGO_CPPFLAGS=""
CGO_CXXFLAGS="-g -O2"
CGO_FFLAGS="-g -O2"
CGO_LDFLAGS="-g -O2"
PKG_CONFIG="pkg-config"
GOGCCFLAGS="-fPIC -m64 -pthread -fmessage-length=0 -fdebug-prefix-map=/tmp/go-build968399806=/tmp/go-build -gno-record-gcc-switches"

What did you do?

I compile and ran this program (simplified from a larger project)

package main

func Bug() (e int64, err error) {
	var stack []int64
	stack = append(stack, 123)
	// Commenting the next 3 lines causes the function to work
	if len(stack) > 1 {
		panic("too many elements")
	}
	last := len(stack) - 1
	e = stack[last]
	stack = stack[:last]
	return e, nil
}

func main() {
	Bug()
}

What did you expect to see?

I expected it to run without error

What did you see instead?

$ go run bug2-inline.go
panic: runtime error: slice bounds out of range

goroutine 1 [running]:
main.Bug(...)
	/home/ncw/Go/bug2-inline.go:12
main.main()
	/home/ncw/Go/bug2-inline.go:17 +0x70
exit status 2

Compilation exited abnormally with code 1 at Wed Jan  2 12:32:47

This is incorrectly complaining that stack[:last] is out of range where last == 0 and len(stack) == cap(stack) == 1.

A tip-off that this is a compiler bug is that commenting out the if statement causes the program to work.

The > 1 is important in the if statement, > 2 does not provoke the bug - I conjecture the compiler is learning something about the length of the slice from that if statement but what it learnt is incorrect in some way - off by one maybe.

I note that this example does not fail on the playground.

[odeke-em]

Thank you for this report @ncw and thank you @FiloSottile for the triaging!

@FiloSottile how come we've marked this freshly opened bug for Go1.12 yet it also exists for Go1.11 but also when Go1.12 is just about to be released(at least according to the schedule)? Perhaps we can mark this for backport?

I'll also kindly page @randall77 @cherrymui @dr2chase @rasky

[mark-rushakoff]

I've bisected this to bdc7d56 on the 1.11 branch.

Bisect log:

Details

git bisect start
# bad: [4601a4c1b1c00fbe507508f0267ec5a9445bb7e5] [release-branch.go1.11] go1.11.4
git bisect bad 4601a4c1b1c00fbe507508f0267ec5a9445bb7e5
# good: [90c896448691b5edb0ab11110f37234f63cd28ed] [release-branch.go1.11-security] go1.11.3
git bisect good 90c896448691b5edb0ab11110f37234f63cd28ed
# good: [71b7b4fad3ac6d9ee543b27a9516a9d63ccd9596] [release-branch.go1.11] cmd/link: close input files when copying to temporary directory
git bisect good 71b7b4fad3ac6d9ee543b27a9516a9d63ccd9596
# bad: [928a4b69195f1f408e4cdb6ad4ee41f5f91f4e86] [release-branch.go1.11] cmd/cgo: preserve type information across loadDWARF loop
git bisect bad 928a4b69195f1f408e4cdb6ad4ee41f5f91f4e86
# good: [b86522faa54413930d6e9164973166490babc5de] [release-branch.go1.11] cmd/go/internal/modfetch: skip symlinks in (*coderepo).Zip
git bisect good b86522faa54413930d6e9164973166490babc5de
# bad: [a1d388ebf217d5582c24057cec4ccd053239dfc9] [release-branch.go1.11] doc/go1.11: add note about go run supporting for go run pkg or go run .
git bisect bad a1d388ebf217d5582c24057cec4ccd053239dfc9
# bad: [bdc7d5677edd1dab21cdaa1f6498e0c2a6c9d7bf] [release-branch.go1.11] cmd/compile: check for negative upper bound to IsSliceInBounds
git bisect bad bdc7d5677edd1dab21cdaa1f6498e0c2a6c9d7bf
# first bad commit: [bdc7d5677edd1dab21cdaa1f6498e0c2a6c9d7bf] [release-branch.go1.11] cmd/compile: check for negative upper bound to IsSliceInBounds

And then I confirmed that on master, the bug is present at ea6259d (fixing issue #28797), but is not present in the parent commit 179909f.

[FiloSottile]

@odeke-em release-branch.go1.12 has not been cut yet, so we haven't started opening separate 1.12 backport issues yet. Many release-blocker issues will become backports, though.

[FiloSottile]

@gopherbot please open a backport issue for 1.11.

[gopherbot]

Backport issue(s) opened: #29503 (for 1.11).

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

[cherrymui]

Before the prove pass, we have

v70 (12) = Geq64 <bool> v56 v10
...
If v70 → b9 b10 (likely) (12)

where b10 will panic. v10 is constant 0, and v56 is the slice len, which is

v56 (+10) = Add64 <int> v66 v45 (last[int])

where

v66 (10) = Const64 <int> [-1]
v45 (+7) = SliceLen <int> v44
v44 (5) = SliceMake <[]int64> v29 v34 v33 (stack[[]int64])
v34 (5) = Add64 <int> v12 v31
v31 (5) = Load <int> v30 v27
v12 (?) = Const64 <int> [1]

i.e. v45 = v31 + 1. This looks correct.

The prove pass derives that v70 (Geq64) is false, therefore unconditionally goes to the panic block.

The prove pass' debug output is below, which looks ok to me until the last line.

x.go:12:15: parent=b7, new limits v69 v10 >= sm,SM,um,UM=0,9223372036854775807,0,18446744073709551615
x.go:12:15: parent=b7, new limits v56 v10 >= sm,SM,um,UM=0,9223372036854775807,0,18446744073709551615
x.go:12:15: parent=b7, new limits v45 v10 > sm,SM,um,UM=1,1,1,1
x.go:12:15: parent=b7, new limits v69 v10 > sm,SM,um,UM=1,9223372036854775807,1,18446744073709551615
x.go:12:15: x+d >= w; x:v45 b7 delta:-1 w:0 d:signed
x.go:12:15: Disproved Geq64 (v70)

I'm not familiar enough with the prove code to tell where it actually does wrong. The "disprove" seems to come from an unsatisfiable condition v63 >= v45, where

v63 (12) = Const64 <int64> [-9223372036854775808]

So it seems something related to overflow...

[gopherbot]

Change https://golang.org/cl/156019 mentions this issue: cmd/compile: fix deriving from v+d >= w on overflow in prove pass

[FiloSottile]

@cherrymui Thanks for mailing a fix. We are planning on cutting the RC this week, so please submit it as soon as possible.