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: bounds check elimination thwarted by if-foruntil idiom #22236

Closed
dr2chase opened this issue Oct 12, 2017 · 3 comments
Closed

cmd/compile: bounds check elimination thwarted by if-foruntil idiom #22236

dr2chase opened this issue Oct 12, 2017 · 3 comments
Labels
FrozenDueToAge NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. Performance
Milestone
Go1.12

Comments

@dr2chase
Copy link
Contributor

Please answer these questions before submitting your issue. Thanks!

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

go1.10devel

Does this issue reproduce with the latest release?

yes

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

linuxamd64

What did you do?

This code is an example of how for i,x := range array loops are rewritten when
a loop preemption check is inserted, for two variants of the range check (unsigned
and signed -- unsigned should be easier, but because 0 <= i < len(l), signed i+1 is also
guaranteed to be greater than zero).

package foo

func f1(p []byte) bool {
	i := uint(0)
	l := uint(len(p))
	if i < l {
		for {
			if p[i] != 0 {
				return true
			}
			i++
			if i >= l {
				break
			}
		}
	}
	return false
}

func f2(p []byte) bool {
	i := int(0)
	l := int(len(p))
	if i < l {
		for {
			if p[i] != 0 {
				return true
			}
			i++
			if i >= l {
				break
			}
		}
	}
	return false
}

When compiled, it would be nice if the bounds checks for the array access were eliminated, but the rewritten loops does not match of the idioms that are checked for (it is more difficult, since the bounds check fact arrives on two predecessors, and one of those is a backedge).

What did you expect to see?

Bounds checks removed (well, I didn't really expect to see them...)

What did you see instead?

genssa f1
   	00000 (.../ifuntilbounds.go:3)	TEXT	"".f1(SB)
   	00001 (.../ifuntilbounds.go:3)	FUNCDATA	$0, gclocals·...(SB)
   	00002 (.../ifuntilbounds.go:3)	FUNCDATA	$1, gclocals·...(SB)
v8	00003 (.../ifuntilbounds.go:3)	MOVQ	"".p+8(SP), AX
v12	00004 (.../ifuntilbounds.go:6)	TESTQ	AX, AX
b1	00005 (.../ifuntilbounds.go:6)	JLS	16
v23	00006 (.../ifuntilbounds.go:6)	MOVQ	"".p(SP), CX
v19	00007 (.../ifuntilbounds.go:6)	MOVL	$0, DX

v25	00008 (.../ifuntilbounds.go:8)	CMPQ	DX, AX   <- not necessary
b5	00009 (.../ifuntilbounds.go:8)	JCC	20             <- never taken
v21	00010 (.../ifuntilbounds.go:8)	MOVBLZX	(CX)(DX*1), BX
v9	00011 (.../ifuntilbounds.go:8)	TESTB	BX, BX
b10	00012 (.../ifuntilbounds.go:8)	JNE	18
v30	00013 (.../ifuntilbounds.go:11)	INCQ	DX
v6	00014 (.../ifuntilbounds.go:12)	CMPQ	DX, AX
b9	00015 (.../ifuntilbounds.go:12)	JCS	8      <- obviously redundant w/ JCC at 9

v35	00016 (.../ifuntilbounds.go:17)	MOVB	$0, "".~r1+24(SP)
b3	00017 (.../ifuntilbounds.go:17)	RET
v27	00018 (.../ifuntilbounds.go:9)	MOVB	$1, "".~r1+24(SP)
b8	00019 (.../ifuntilbounds.go:9)	RET
v17	00020 (.../ifuntilbounds.go:8)	PCDATA	$0, $1
v17	00021 (.../ifuntilbounds.go:8)	CALL	runtime.panicindex(SB)
b11	00022 (.../ifuntilbounds.go:8)	UNDEF
   	00023 (<unknown line number>)	END


genssa f2
   	00000 (.../ifuntilbounds.go:20)	TEXT	"".f2(SB)
   	00001 (.../ifuntilbounds.go:20)	FUNCDATA	$0, gclocals·...(SB)
   	00002 (.../ifuntilbounds.go:20)	FUNCDATA	$1, gclocals·...(SB)
v8	00003 (.../ifuntilbounds.go:20)	MOVQ	"".p+8(SP), AX
v12	00004 (.../ifuntilbounds.go:23)	TESTQ	AX, AX
b1	00005 (.../ifuntilbounds.go:23)	JLE	16
v23	00006 (.../ifuntilbounds.go:23)	MOVQ	"".p(SP), CX
v19	00007 (.../ifuntilbounds.go:23)	MOVL	$0, DX

v25	00008 (.../ifuntilbounds.go:25)	CMPQ	DX, AX   <- not necessary
b5	00009 (.../ifuntilbounds.go:25)	JCC	20             <- never taken
v21	00010 (.../ifuntilbounds.go:25)	MOVBLZX	(CX)(DX*1), BX
v9	00011 (.../ifuntilbounds.go:25)	TESTB	BX, BX
b10	00012 (.../ifuntilbounds.go:25)	JNE	18
v30	00013 (.../ifuntilbounds.go:28)	INCQ	DX
v6	00014 (.../ifuntilbounds.go:29)	CMPQ	DX, AX
b9	00015 (.../ifuntilbounds.go:29)	JLT	8

v35	00016 (.../ifuntilbounds.go:34)	MOVB	$0, "".~r1+24(SP)
b3	00017 (.../ifuntilbounds.go:34)	RET
v27	00018 (.../ifuntilbounds.go:26)	MOVB	$1, "".~r1+24(SP)
b8	00019 (.../ifuntilbounds.go:26)	RET
v17	00020 (.../ifuntilbounds.go:25)	PCDATA	$0, $1
v17	00021 (.../ifuntilbounds.go:25)	CALL	runtime.panicindex(SB)
b11	00022 (.../ifuntilbounds.go:25)	UNDEF
   	00023 (<unknown line number>)	END
@ianlancetaylor ianlancetaylor changed the title Bounds check elimination thwarted by if-foruntil idiom cmd/compile: bounds check elimination thwarted by if-foruntil idiom Oct 12, 2017
@ianlancetaylor ianlancetaylor added this to the Go1.10 milestone Oct 12, 2017
@ianlancetaylor ianlancetaylor added the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Oct 12, 2017
@bradfitz bradfitz modified the milestones: Go1.10, Go1.11 Nov 28, 2017
@dr2chase dr2chase modified the milestones: Go1.11, Go1.12 Jun 15, 2018
@dr2chase
Copy link
Contributor Author

I thought perhaps this had been fixed by all the work done on prove, but apparently not.
(I investigated.)

@aclements I think added some code that was supposed to catch just this idiom; the point is that this should match the rewrites used to avoid off-the-end pointers with preemptible loops, so perhaps the actual rewrite (the one that we care about) is different from this.

That the unsigned case is not caught is unsurprising, because signed is far and away the usual case, but the signed case is also not caught.

@aclements
Copy link
Member

This is definitely caught for the real OFORUNTIL. There are some tests at the bottom of test/prove.go, including one "hand coded" foruntil pattern. I'm not sure what's different about your cases.

@dr2chase
Copy link
Contributor Author

I need to investigate my case, but the important case is the one we generate automatically, which is what this bug is/was about. So closed.

@golang golang locked and limited conversation to collaborators Jun 29, 2019
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
Go1.12
Development

No branches or pull requests
5 participants
@bradfitz @dr2chase @aclements @ianlancetaylor @gopherbot