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

ncw · 2019-01-02T12:51:13Z

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.

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

odeke-em · 2019-01-02T13:24:16Z

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 · 2019-01-02T13:57:14Z

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

Bisect log:

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 · 2019-01-02T14:09:48Z

@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 · 2019-01-02T14:10:01Z

@gopherbot please open a backport issue for 1.11.

gopherbot · 2019-01-02T14:10:08Z

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 · 2019-01-02T16:50:18Z

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 · 2019-01-02T17:28:55Z

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

FiloSottile · 2019-01-02T19:04:24Z

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

gopherbot · 2019-02-25T21:42:55Z

Change https://golang.org/cl/163724 mentions this issue: [release-branch.go1.11] cmd/compile: fix deriving from x+d >= w on overflow in prove pass

…erflow in prove pass In the case of x+d >= w, where d and w are constants, we are deriving x is within the bound of min=w-d and max=maxInt-d. When there is an overflow (min >= max), we know only one of x >= min or x <= max is true, and we derive this by excluding the other. When excluding x >= min, we did not consider the equal case, so we could incorrectly derive x <= max when x == min. Updates #29502. Fixes #29503. Change-Id: Ia9f7d814264b1a3ddf78f52e2ce23377450e6e8a Reviewed-on: https://go-review.googlesource.com/c/156019 Reviewed-by: David Chase <drchase@google.com> (cherry picked from commit 2e217fa) Reviewed-on: https://go-review.googlesource.com/c/163724 Run-TryBot: Cherry Zhang <cherryyz@google.com> Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org> TryBot-Result: Gobot Gobot <gobot@golang.org>

FiloSottile added NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. release-blocker labels Jan 2, 2019

FiloSottile added this to the Go1.12 milestone Jan 2, 2019

gopherbot mentioned this issue Jan 2, 2019

cmd/compile: incorrect code generation bug when taking slice[:0] [1.11 backport] #29503

Closed

FiloSottile assigned cherrymui Jan 2, 2019

gopherbot closed this as completed in 2e217fa Jan 2, 2019

randall77 mentioned this issue Jan 25, 2019

Panic due 'slice bounds out of range' after upgrading to Go 1.11.4 #29942

Closed

golang locked and limited conversation to collaborators Feb 25, 2020

gopherbot added the FrozenDueToAge label Feb 25, 2020

rsc unassigned cherrymui Jun 23, 2022

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

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

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

ncw commented Jan 2, 2019

odeke-em commented Jan 2, 2019

mark-rushakoff commented Jan 2, 2019

FiloSottile commented Jan 2, 2019

FiloSottile commented Jan 2, 2019

gopherbot commented Jan 2, 2019

cherrymui commented Jan 2, 2019

gopherbot commented Jan 2, 2019

FiloSottile commented Jan 2, 2019

gopherbot commented Feb 25, 2019

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

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

Comments

ncw commented Jan 2, 2019

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?

odeke-em commented Jan 2, 2019

mark-rushakoff commented Jan 2, 2019

FiloSottile commented Jan 2, 2019

FiloSottile commented Jan 2, 2019

gopherbot commented Jan 2, 2019

cherrymui commented Jan 2, 2019

gopherbot commented Jan 2, 2019

FiloSottile commented Jan 2, 2019

gopherbot commented Feb 25, 2019

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

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