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

Jump to bottom

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

Closed
FallenKhadgar opened this issue Jun 16, 2022 · 5 comments
Closed

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

FallenKhadgar opened this issue Jun 16, 2022 · 5 comments
Labels
FrozenDueToAge NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. Performance
Milestone
Unplanned

Comments

@FallenKhadgar
Copy link

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

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 Issue is not actionable because of missing required information, which needs to be provided. label Jun 16, 2022
@FallenKhadgar
Copy link
Author

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

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 Issue is not actionable because of missing required information, which needs to be provided. label Jun 16, 2022
@FallenKhadgar
Copy link
Author

FallenKhadgar commented Jun 16, 2022 •
edited

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.

go/src/cmd/compile/internal/walk/range.go

Lines 19 to 33 in ef808ae

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
}

go/src/cmd/compile/internal/walk/range.go

Lines 114 to 137 in ef808ae

// 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 Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Jun 17, 2022
@gopherbot
Copy link

Change https://go.dev/cl/414876 mentions this issue: cmd/compile: don't use OFORUNTIL when implementing range loops

@golang golang locked and limited conversation to collaborators Aug 18, 2023
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Assignees
No one assigned
Labels
FrozenDueToAge NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. Performance
Projects
None yet
Milestone
Unplanned
Development

No branches or pull requests
6 participants
@mvdan @randall77 @gopherbot @seankhliao @thanm @FallenKhadgar