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: No BCE for str[len(str):] #53409

Open
FallenKhadgar opened this issue Jun 16, 2022 · 4 comments
Open

cmd/compile: No BCE for str[len(str):] #53409

FallenKhadgar opened this issue Jun 16, 2022 · 4 comments
Labels
NeedsInvestigation Performance
Milestone

Comments

@FallenKhadgar
Copy link

@FallenKhadgar FallenKhadgar commented Jun 16, 2022

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

go version go1.18.3 windows/amd64

Does this issue reproduce with the latest release?

Yes.

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

go env Output
set GO111MODULE=
set GOARCH=amd64
set GOBIN=
set GOCACHE=C:\Users\user\AppData\Local\go-build
set GOENV=C:\Users\user\AppData\Roaming\go\env
set GOEXE=.exe
set GOEXPERIMENT=
set GOFLAGS=
set GOHOSTARCH=amd64
set GOHOSTOS=windows
set GOINSECURE=
set GOMODCACHE=C:\user\workspace\go\pkg\mod
set GONOPROXY=
set GONOSUMDB=
set GOOS=windows
set GOPATH=C:\user\workspace\go
set GOPRIVATE=
set GOPROXY=https://proxy.golang.org,direct
set GOROOT=c:\go
set GOSUMDB=sum.golang.org
set GOTMPDIR=
set GOTOOLDIR=c:\go\pkg\tool\windows_amd64
set GOVCS=
set GOVERSION=go1.18.3
set GCCGO=gccgo
set GOAMD64=v1
set AR=ar
set CC=gcc
set CXX=g++
set CGO_ENABLED=1
set GOMOD=NUL
set GOWORK=
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=C:\Users\user\AppData\Local\Temp\go-build1234567890=/tmp/go-build -gno-record-gcc-switches

What did you do?

package main

func foo(s []string) {
	for i, si := range s {
		for range s[i+1:] { // IsSliceInBounds but i<len(s) and s[len(s):] is always valid
			println(si)
		}
	}
}

func main() {
	foo(nil)
	foo([]string{"a", "b", "c"})
}

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

What did you expect to see?

I expected the bounds check on for range s[i+1:] to be eliminated, since 0 < i+1 <= len(s), and s[len(s):] is always valid.
It works as expected for []byte instead of []string.

What did you see instead?

# main
.\main.go:5:14: Found IsSliceInBounds
@randall77 randall77 added this to the Unplanned milestone Jun 16, 2022
@randall77
Copy link
Contributor

@randall77 randall77 commented Jun 16, 2022

It works as expected for []byte instead of []string.

Could you explain? Replacing []string with [][]byte still has the bounds check. I'm not sure how you would replace []string with []byte.

@mvdan mvdan added the WaitingForInfo label Jun 16, 2022
@FallenKhadgar
Copy link
Author

@FallenKhadgar FallenKhadgar commented Jun 16, 2022

It works as expected for []byte instead of []string.

Could you explain? Replacing []string with [][]byte still has the bounds check.

Oh, I literally meant []byte.

  • []byte, []bool, []rune, []uint64, []uintptr, []float64, []complex64, []chan int, []func, []func()bool, []func()string BCE
  • []complex128 IsSliceInBounds
  • []string IsSliceInBounds
  • []error IsSliceInBounds
  • []struct{} IsSliceInBounds
  • []interface{} IsSliceInBounds
  • []any IsSliceInBounds

@randall77
Copy link
Contributor

@randall77 randall77 commented Jun 16, 2022

Ah, ok, I see what you're saying.

Looks like the BCE is defeated by converting from a for loop to a foruntil loop, which we do to avoid past-the-end pointers. We were just talking about getting rid of foruntil, now that we have conservatively scanned top-of-stack frames.

We don't do for -> foruntil when the element size is 1, 2, 4 or 8 (for amd64, at least). That explains the pattern you're seeing.

@seankhliao seankhliao removed the WaitingForInfo label Jun 16, 2022
@FallenKhadgar
Copy link
Author

@FallenKhadgar FallenKhadgar commented Jun 16, 2022

We don't do for -> foruntil when the element size is 1, 2, 4 or 8 (for amd64, at least). That explains the pattern you're seeing.

🤦 [8]byte BCE, [9]byte IsSliceInBounds.

func cheapComputableIndex(width int64) bool {
switch ssagen.Arch.LinkArch.Family {
// MIPS does not have R+R addressing
// Arm64 may lack ability to generate this code in our assembler,
// but the architecture supports it.
case sys.PPC64, sys.S390X:
return width == 1
case sys.AMD64, sys.I386, sys.ARM64, sys.ARM:
switch width {
case 1, 2, 4, 8:
return true
}
}
return false
}

// for v1, v2 := range ha { body }
if cheapComputableIndex(t.Elem().Size()) {
// v1, v2 = hv1, ha[hv1]
tmp := ir.NewIndexExpr(base.Pos, ha, hv1)
tmp.SetBounded(true)
// Use OAS2 to correctly handle assignments
// of the form "v1, a[v1] := range".
a := ir.NewAssignListStmt(base.Pos, ir.OAS2, []ir.Node{v1, v2}, []ir.Node{hv1, tmp})
body = []ir.Node{a}
break
}
// TODO(austin): OFORUNTIL is a strange beast, but is
// necessary for expressing the control flow we need
// while also making "break" and "continue" work. It
// would be nice to just lower ORANGE during SSA, but
// racewalk needs to see many of the operations
// involved in ORANGE's implementation. If racewalk
// moves into SSA, consider moving ORANGE into SSA and
// eliminating OFORUNTIL.
// TODO(austin): OFORUNTIL inhibits bounds-check
// elimination on the index variable (see #20711).
// Enhance the prove pass to understand this.

@thanm thanm added the NeedsInvestigation label Jun 17, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
NeedsInvestigation Performance
Projects
None yet
Development

No branches or pull requests

5 participants