cmd/compile: function compiled without bounds checking and -1 index access

[mariecurried]

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

go version go1.11 windows/amd64

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

set GOARCH=amd64
set GOBIN=
set GOCACHE=...
set GOEXE=.exe
set GOFLAGS=
set GOHOSTARCH=amd64
set GOHOSTOS=windows
set GOOS=windows
set GOPATH=...
set GOPROXY=
set GORACE=
set GOROOT=C:\Go
set GOTMPDIR=
set GOTOOLDIR=C:\Go\pkg\tool\windows_amd64
set GCCGO=gccgo
set CC=gcc
set CXX=g++
set CGO_ENABLED=1
set GOMOD=
set CGO_CFLAGS=-g -O2
set CGO_CPPFLAGS=
set CGO_CXXFLAGS=-g -O2
set CGO_FFLAGS=-g -O2
set CGO_LDFLAGS=-g -O2
set PKG_CONFIG=pkg-config
set GOGCCFLAGS=-m64 -mthreads -fmessage-length=0 -fdebug-prefix-map=... -gno-record-gcc-switches

What did you do?

I compiled the following functions: https://play.golang.org/p/FstWIAwJwdg

What did you expect to see?

I expected two things:

1. The test function to have bounds checking code, having in mind that a slice can have len == 0.
2. When I run the program and enter 0 as input, the program should crash (because of index out of range) instead of returning me 0.

What did you see instead?

1. The test function was compiled without bounds checking code.
2. When I ran the program with input 0, everything went fine and 0 was printed to the console.

[fhs]

This is a regression. On linux/amd64:

$ cat b.go 
package main

func main() {
	var size int
	a := make([]int, size)
	println(a[len(a)-1])
}
$ go1.10.3 run b.go 
panic: runtime error: index out of range

goroutine 1 [running]:
main.main()
	/tmp/b.go:6 +0x7e
exit status 2
$ go1.11 run b.go 
140722543884928
$ go version
go version devel +42cc4ca30a Sun Aug 26 21:52:27 2018 +0000 linux/amd64
$ go run  b.go 
140731573480064

[cherrymui]

This correctly panics with Go 1.10. I think this needs to be fixed in the next release of Go 1.11.

cc @rasky @dr2chase @aclements (who I think worked on bound check elimination.)

[as]

-1 index access is too specific, the error is cumulative. The example below outputs -25 in go1.11.

https://play.golang.org/p/pvSfKcoi6_2

// output on go1.11

i: 0, len: -1, cap: 0, val: a
i: 1, len: -2, cap: 0, val: b
i: 2, len: -3, cap: 0, val: c
.... you get the point
i: 23, len: -24, cap: 0, val: x
i: 24, len: -25, cap: 0, val: y
end1 f
exit status 3221225477

[theckman]

A few of us in the Gofrs group were talking about this, and managed to bisect it down to e0d37a3:

e0d37a33ab6260f5acc68dbb9a02c3135d19bcbb is the first bad commit
commit e0d37a33ab6260f5acc68dbb9a02c3135d19bcbb
Author: Giovanni Bajo <[email protected]>
Date:   Sun Apr 15 16:52:49 2018 +0200

    cmd/compile: teach prove to handle expressions like len(s)-delta

    When a loop has bound len(s)-delta, findIndVar detected it and
    returned len(s) as (conservative) upper bound. This little lie
    allowed loopbce to drop bound checks.

    It is obviously more generic to teach prove about relations like
    x+d<w for non-constant "w"; we already handled the case for
    constant "w", so we just want to learn that if d<0, then x+d<w
    proves that x<w.

    To be able to remove the code from findIndVar, we also need
    to teach prove that len() and cap() are always non-negative.

    This CL allows to prove 633 more checks in cmd+std. Most
    of them are cases where the code was already testing before
    accessing a slice but the compiler didn't know it. For instance,
    take strings.HasSuffix:

        func HasSuffix(s, suffix string) bool {
            return len(s) >= len(suffix) && s[len(s)-len(suffix):] == suffix
        }

    When suffix is a literal string, the compiler now understands
    that the explicit check is enough to not emit a slice check.

    I also found a loopbce test that was incorrectly
    written to detect an overflow but had a off-by-one (on the
    conservative side), so it unexpectly passed with this CL; I
    changed it to really trigger the overflow as intended.

    Change-Id: Ib5abade337db46b8811425afebad4719b6e46c4a
    Reviewed-on: https://go-review.googlesource.com/105635
    Run-TryBot: Giovanni Bajo <[email protected]>
    TryBot-Result: Gobot Gobot <[email protected]>
    Reviewed-by: David Chase <[email protected]>

:040000 040000 4c1845786825d163b0898714be5170b2f2ab47b7 dd316f5e7b25876f3c9f0578777ea250cfc27611 M      src
:040000 040000 997bce7a0ca61a42c0c3cb6b328194674170fef1 2f59946242bade07efa6651ee815e4ef1f17d7b3 M      test
bisect run success

[dr2chase]

I've got a revert ready, not skilled at submitting CLs off head, also doing a round of benchmarking just in case it's got horrible effects.

[josharian]

@dr2chase if you want a hand wrangling the CL, ping me (google chat? email?) and we can meet up

[gopherbot]

Change https://golang.org/cl/131936 mentions this issue: cmd/compile: Revert "teach prove to handle expressions like len(s)-delta"

[FiloSottile]

@gopherbot please file this for backport against 1.11. This is a regression.

@dr2chase please make a cherry-pick CL once your change is merged in master.

[gopherbot]

Backport issue(s) opened: #27378 (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.

[gopherbot]

Change https://golang.org/cl/132436 mentions this issue: cmd/compile: Revert "teach prove to handle expressions like len(s)-delta"

[gopherbot]

Change https://golang.org/cl/132495 mentions this issue: cmd/compile: fix fence-post implications for unsigned domain.