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: Prove doesn't understand division of slice length #57077

Closed
Nigma1337 opened this issue Dec 4, 2022 · 5 comments
Closed

cmd/compile: Prove doesn't understand division of slice length #57077

Nigma1337 opened this issue Dec 4, 2022 · 5 comments
Assignees
Labels
compiler/runtime Issues related to the Go compiler and/or runtime.
Milestone

Comments

@Nigma1337
Copy link

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

$ go version
go version go1.19.3 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/magnus/.cache/go-build"
GOENV="/home/magnus/.config/go/env"
GOEXE=""
GOEXPERIMENT=""
GOFLAGS=""
GOHOSTARCH="amd64"
GOHOSTOS="linux"
GOINSECURE=""
GOMODCACHE="/home/magnus/go/pkg/mod"
GONOPROXY=""
GONOSUMDB=""
GOOS="linux"
GOPATH="/home/magnus/go"
GOPRIVATE=""
GOPROXY="https://proxy.golang.org,direct"
GOROOT="/usr/lib/go"
GOSUMDB="sum.golang.org"
GOTMPDIR=""
GOTOOLDIR="/usr/lib/go/pkg/tool/linux_amd64"
GOVCS=""
GOVERSION="go1.19.3"
GCCGO="gccgo"
GOAMD64="v1"
AR="ar"
CC="gcc"
CXX="g++"
CGO_ENABLED="1"
GOMOD="/home/magnus/go.mod"
GOWORK=""
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 -Wl,--no-gc-sections -fmessage-length=0 -fdebug-prefix-map=/tmp/go-build1748103025=/tmp/go-build -gno-record-gcc-switches"

What did you do?

I took the length of an object, to split it into halves, and there were IsSliceInBounds checks

What did you expect to see?

The IsSliceInBounds checks eliminatied

What did you see instead?

They were not eliminated

Short program showing issue

package main

func SplitInHalf(s []int) (left, right []int) {
	middle := len(s) / 2
	left = s[:middle]
	right = s[middle:]
	return
}

func main() {}

$ go build -gcflags="-d=ssa/check_bce/debug=1" main.go

command-line-arguments

./main.go:5:10: Found IsSliceInBounds
./main.go:6:11: Found IsSliceInBounds

@gopherbot gopherbot added the compiler/runtime Issues related to the Go compiler and/or runtime. label Dec 4, 2022
@gopherbot
Copy link

Change https://go.dev/cl/455095 mentions this issue: cmd/compile: teach prove about unsigned division, modulus and rhs

@go101
Copy link

go101 commented Dec 5, 2022

This is a correct behavior. See #16595

Also see the "Example 3" section in https://go101.org/article/bounds-check-elimination.html

@go101
Copy link

go101 commented Dec 5, 2022

Ah, it looks this is a different problem.
What about the length of s is zero?

[update] Sorry, the bounds should be eliminated here.

@Jorropo
Copy link
Contributor

Jorropo commented Dec 5, 2022

I've seen your:

[update] Sorry, the bounds should be eliminated here.

But I'm responding anyway for posterity and future readers. 🙂

This is a correct behavior. See #16595
Also see the "Example 3" section in https://go101.org/article/bounds-check-elimination.html

Thoses examples you linked are different, they incorrectly assume that slice[:i] should prove slice[i:].
This is wrong because go use [x,y) ranging, that means :i is one past the index that will be taken, while i: is the last index that will be taken. In other words i <= cap(slice) does not prove i < cap(slice).

Here we have a different issue, actually it reproduce just like this without this double left / right reslicing:

func SplitInHalfRight(s []int) (right []int) {
	middle := len(s) / 2
	right = s[middle:]
	return
}

It should BCE but it doesn't, hopefully this can convaince you, if we feed a 0 length slice in the original function we will get this after folding out all constants:

func SplitInHalf(s []int) (left, right []int) {
	middle := len(s) / 2 // 0 / 2 = 0
	left = s[:middle] // []int{}[0:0] -> []int{}
	right = s[middle:] // []int{}[0:0] -> []int{}
	return
}

In other words feeding an empty slice produce two empty slices.


This was easy to fix, I just had to teach the compiler that for unsigned divisions z := x / y and unsigned right shifts (which are really just divisions by powers of two) z := x >> y, z is always smaller or equal to x.

@prattmic prattmic added this to the Backlog milestone Dec 5, 2022
@prattmic prattmic added the NeedsFix The path to resolution is known, but the work has not been done. label Dec 5, 2022
@prattmic
Copy link
Member

prattmic commented Dec 5, 2022

cc @golang/compiler

@prattmic prattmic removed this from the Backlog milestone Dec 5, 2022
@prattmic prattmic added this to the Backlog milestone Dec 14, 2022
@prattmic prattmic changed the title cmd/compile: Prove fails bce when taking the division of length as index cmd/compile: Prove doesn't understand division of slice length Dec 14, 2022
@randall77 randall77 removed the NeedsFix The path to resolution is known, but the work has not been done. label Dec 14, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
compiler/runtime Issues related to the Go compiler and/or runtime.
Projects
Status: Done
Development

No branches or pull requests

6 participants