cmd/compile: bounds check not eliminated #45078

rsc · 2021-03-17T09:56:28Z

I am writing code to count how long a common prefix two slices have, and I can't seem to make it bounds-check-free.

At current master, this function does not eliminate the bounds check for y[j], although it does for x[i]:

func f1(x, y []int, i, j int) int {
	i0 := i
	if i >= 0 && i < len(x) && j >= 0 && j < len(y) {
		for i < len(x) && j < len(y) && x[i] == y[j] {
			i++
			j++
		}
	}
	return i - i0
}

If I remove the i < len(x) && and the i++, then the y[j] bounds check is eliminated:

func f2(x, y []int, i, j int) int {
	i0 := i
	if i >= 0 && i < len(x) && j >= 0 && j < len(y) {
		for j < len(y) && x[i] == y[j] {
			j++
		}
	}
	return i - i0
}

If I leave out the i++ but bring back the (unnecessary) i < len(x), the y[j] bounds check returns:

func f3(x, y []int, i, j int) int {
	i0 := i
	if i >= 0 && i < len(x) && j >= 0 && j < len(y) {
		for i < len(x) && j < len(y) && x[i] == y[j] {
			j++
		}
	}
	return i - i0
}

This is a simpler case that also has a bounds check and may share the same root cause:

func g1(x, y []int, i, j int) int {
	i0 := i
	if i >= 0 {
		for ; ; i++ {
			if i >= len(x) {
				break
			}
			if x[i] != 0 {
				break
			}
		}
	}
	return i - i0
}

This equivalent program has no check:

func g2(x, y []int, i, j int) int {
	i0 := i
	if i >= 0 {
		for ; i < len(x) && x[i] != 0; i++ {
		}
	}
	return i - i0
}

This suggests the problem has to do with either the inverted condition or the use of a short-circuit to exit the loop, neither of which should fundamentally change what is being proved.

The same happens counting backward: h0 and h1 have checks (h0 has just one), but h2 is check-free:

func h0(x, y []int, i, j int) int {
	i0 := i
	if i <= len(x) && j <= len(y) {
		for i > 0 && j > 0 && x[i-1] == y[j-1] {
			i--
			j--
		}
	}
	return i0 - i
}

func h1(x, y []int, i, j int) int {
	i0 := i
	if i <= len(x) {
		for ; ; i-- {
			if i <= 0 {
				break
			}
			if x[i-1] != 0 {
				break
			}
		}
	}
	return i - i0
}

func h2(x, y []int, i, j int) int {
	i0 := i
	if i <= len(x) {
		for ; i > 0 && x[i-1] != 0; i-- {
		}
	}
	return i - i0
}

/cc @aclements @randall77 @rasky @brtzsnr (prove authors as best I can tell from git blame)

The text was updated successfully, but these errors were encountered:

mvdan · 2021-03-17T13:47:14Z

Also CC @zdjones

josharian · 2021-03-18T19:54:00Z

Does this work for you?

func f(x, y []int, i, j int) int {
	i0 := i
	for i >= 0 && i < len(x) && j >= 0 && j < len(y) && x[i] == y[j] {
		i++
		j++
	}
	return i - i0
}

Seems to be equivalent, has no bounds checks, generates considerably shorter code. The key piece is the addition of && j >= 0 to the inner loop condition. (Note that this should have no cost, as the compiler should optimize 0 <= j < len(y) into a single unsigned comparison.) Then I removed the outer if statement, as it was almost entirely redundant with the inner loop.

adonovan · 2023-05-17T18:30:57Z

Another example (on ARM): in this function the order of i and j in the loop body statement affects the number of bounds checks.

func reverse(s []int) {
	for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
		s[i], s[j] = s[j], s[i]
	}
}

The natural order, s[i], s[j] = s[j], s[i], produces two checks:

// 0x0028 00040 (a.go:5)	MOVD	(R0)(R2<<3), R5
// 0x002c 00044 (a.go:5)	MOVD	R5, (R0)(R3<<3)
// 0x0030 00048 (a.go:5)	MOVD	R4, (R0)(R2<<3)
// 0x0034 00052 (a.go:4)	ADD	$1, R3, R3
// 0x0038 00056 (a.go:4)	SUB	$1, R2, R2
// 0x003c 00060 (a.go:4)	CMP	R3, R2
// 0x0040 00064 (a.go:4)	BLE	92 ; out of bounds
// 0x0044 00068 (a.go:5)	CMP	R3, R1
// 0x0048 00072 (a.go:5)	BLS	112 ; out of bounds
// 0x004c 00076 (a.go:5)	MOVD	(R0)(R3<<3), R4
// 0x0050 00080 (a.go:5)	CMP	R2, R1
// 0x0054 00084 (a.go:5)	BHI	40

The reversed order, s[j], s[i] = s[i], s[j], produces only one check:

// 0x0028 00040 (a.go:5)	MOVD	(R0)(R3<<3), R4
// 0x002c 00044 (a.go:5)	MOVD	(R0)(R2<<3), R5
// 0x0030 00048 (a.go:5)	MOVD	R4, (R0)(R2<<3)
// 0x0034 00052 (a.go:5)	MOVD	R5, (R0)(R3<<3)
// 0x0038 00056 (a.go:4)	ADD	$1, R3, R3
// 0x003c 00060 (a.go:4)	SUB	$1, R2, R2
// 0x0040 00064 (a.go:4)	CMP	R3, R2
// 0x0044 00068 (a.go:4)	BLE	84 ; out of bounds
// 0x0048 00072 (a.go:5)	CMP	R2, R1
// 0x004c 00076 (a.go:5)	BHI	40 // continue
// 0x0050 00080 (a.go:5)	; out of bounds

brtzsnr · 2023-06-12T18:07:29Z

Because i < j then there are two bound checks at s[i] and s[j] for s[i], s[j] since you s[i] doesn't tell you anything about s[j]. For the second example a passed bound check for s[j] implies s[i] won't panic because j > i. I don't think the compiler can / should reorder the operations.

rsc added the NeedsFix The path to resolution is known, but the work has not been done. label Mar 17, 2021

rsc added this to the Go1.17 milestone Mar 17, 2021

ianlancetaylor modified the milestones: Go1.17, Backlog Apr 19, 2021

gopherbot added the compiler/runtime Issues related to the Go compiler and/or runtime. label Jul 13, 2022

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

cmd/compile: bounds check not eliminated #45078

cmd/compile: bounds check not eliminated #45078

rsc commented Mar 17, 2021

mvdan commented Mar 17, 2021

josharian commented Mar 18, 2021

adonovan commented May 17, 2023

brtzsnr commented Jun 12, 2023

cmd/compile: bounds check not eliminated #45078

cmd/compile: bounds check not eliminated #45078

Comments

rsc commented Mar 17, 2021

mvdan commented Mar 17, 2021

josharian commented Mar 18, 2021

adonovan commented May 17, 2023

brtzsnr commented Jun 12, 2023