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: avoid unnecessary bounds check in range loop #52019

Closed
dsnet opened this issue Mar 29, 2022 · 3 comments
Closed

cmd/compile: avoid unnecessary bounds check in range loop #52019

dsnet opened this issue Mar 29, 2022 · 3 comments
Labels
FrozenDueToAge NeedsFix The path to resolution is known, but the work has not been done. Performance

Comments

@dsnet
Copy link
Member

dsnet commented Mar 29, 2022 •
edited

Using go1.18.0

Consider the following:

var source = []int{1, 2, 3}
var sink *int

func main() {
	for i := range source {
		sink = &source[i]
	}
}

This currently compiles to code that includes:

...
0x0027 00039 (/tmp/sandbox1101920711/main.go:9) 	MOVQ	"".source+8(SB), CX
0x002e 00046 (/tmp/sandbox1101920711/main.go:9) 	MOVQ	"".source(SB), BX
0x0035 00053 (/tmp/sandbox1101920711/main.go:9) 	CMPQ	AX, CX
0x0038 00056 (/tmp/sandbox1101920711/main.go:9) 	JCC	104
0x003a 00058 (/tmp/sandbox1101920711/main.go:9) 	LEAQ	(BX)(AX*8), BX
0x003e 00062 (/tmp/sandbox1101920711/main.go:9) 	PCDATA	$0, $-2
0x003e 00062 (/tmp/sandbox1101920711/main.go:9) 	CMPL	runtime.writeBarrier(SB), $0
0x0045 00069 (/tmp/sandbox1101920711/main.go:9) 	JNE	80
0x0047 00071 (/tmp/sandbox1101920711/main.go:9) 	MOVQ	BX, "".sink(SB)
0x004e 00078 (/tmp/sandbox1101920711/main.go:9) 	JMP	31
0x0050 00080 (/tmp/sandbox1101920711/main.go:9) 	LEAQ	"".sink(SB), DI
0x0057 00087 (/tmp/sandbox1101920711/main.go:9) 	CALL	runtime.gcWriteBarrierBX(SB)
0x005c 00092 (/tmp/sandbox1101920711/main.go:9) 	JMP	31
0x005e 00094 (/tmp/sandbox1101920711/main.go:11)	PCDATA	$0, $-1
0x005e 00094 (/tmp/sandbox1101920711/main.go:11)	MOVQ	16(SP), BP
0x0063 00099 (/tmp/sandbox1101920711/main.go:11)	ADDQ	$24, SP
0x0067 00103 (/tmp/sandbox1101920711/main.go:11)	RET
0x0068 00104 (/tmp/sandbox1101920711/main.go:9) 	PCDATA	$1, $0
0x0068 00104 (/tmp/sandbox1101920711/main.go:9) 	CALL	runtime.panicIndex(SB)
...

where line 9 is:

sink = &source[i]

Given that i comes from the range over source, there should be no reason that source[i] should ever panic.
@mvdan mvdan added the NeedsFix The path to resolution is known, but the work has not been done. label Mar 29, 2022
@katsusan
Copy link

katsusan commented Mar 29, 2022 •
edited

Hi, I have a question. Is your case only applicable to loop body sink = &source[i]?

If there is only sink = &source[i], then the loop should be optimized to a single store in DSE,
as the first len(source)-2 times of assignments are not read by anyone.

If there are other functions in loop, as the slice length is taken snapshot at beginning of the loop,
once the slice is modified inside loop(unreasonable but permitted), the bounds check is still necessary.

@randall77
Copy link
Contributor

We're pretty conservative about global variables. Although it would be allowed (data races allow any behavior), we currently don't assume that globals are unmodified between two reads.

@dsnet
Copy link
Member Author

dsnet commented Mar 30, 2022 •
edited

Thanks @randall77. Disregard this. I was observing a bounds check in for range code in a larger part of complex code. I was trying to reduce it to a smaller reproduction and accidentally introduced the bounds check for a different reason (i.e., using a global variable for the slice).

Looking more into my specific example, it appears that the compiler is unable to prove that some deeply recursive function calls will not mutate the slice, and thus cause the length to change.

@dsnet dsnet closed this as completed Mar 30, 2022
@golang golang locked and limited conversation to collaborators Mar 30, 2023
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Assignees
No one assigned
Labels
FrozenDueToAge NeedsFix The path to resolution is known, but the work has not been done. Performance
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
5 participants
@mvdan @dsnet @randall77 @gopherbot @katsusan