cmd/compile: bounds check not eliminated

[rsc]

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)

[mvdan]

Also CC @zdjones

[josharian]

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]

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]

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.