go: cmd/compile: unexpected prove/BCE regressions when building encoding/json

$ go version
go version devel +f947c4dcfe Fri Apr 5 00:52:55 2019 +0000 linux/amd64
$ go1 version
go version go1.12.1 linux/amd64
$ cd tip/src/encoding/json
$ go1 build -gcflags='-d=ssa/check_bce/debug=1' &>before
$ go build -gcflags='-d=ssa/check_bce/debug=1' &>after
$ diff before after
1c1
< # std/encoding/json
---
> # encoding/json
49a50
> ./encode.go:728:19: Found IsSliceInBounds
91a93
> ./scanner.go:151:29: Found IsSliceInBounds
100a103
> ./stream.go:386:35: Found IsSliceInBounds
101a105
> ./stream.go:405:35: Found IsSliceInBounds

So it seems like BCE is actually getting worse in 1.13 for this particular package. It has over a hundred bounds checks, a dozen of which are in hot decode functions, so I’d like for the number to go down, not up 😃

I used encoding/json from the master version on both cases, to make the comparison fair and simple.

/cc @zdjones @aclements @rasky @josharian

About this issue

Original URL
State: closed
Created 5 years ago
Comments: 15 (15 by maintainers)

Most upvoted comments

OpIsSliceInBounds will ultimately be three instructions, each of which will check both the upper and lower bounds of one of i, j, k. The instruction used for each of those checks requires that the upper bound value be non-negative.

IsSliceInBounds is a single instruction. For s[i:j:k] we issue 3 of them:

   IsSliceInBounds k cap(s)
   IsSliceInBounds j k
   IsSliceInBounds i j

In the previous implementation, in addition to actually doing the bounds check, we needed to first check whether each upper bound value was non-negative. The non-negative check(s) was an additional OpGeq64 in the SSA, just before the OpSliceIsInBounds proper. Prove was learning from that additional op (which, like you said, is actually half of the bounds check) before arriving at the OpIsSliceInBounds, at which point it was legitimately able to remove the bounds check as a whole in the examples at hand.

In the current implementation, because we know that the cap(s) upper bound is guaranteed non-negative, we can bootstrap that guarantee down the chain of checks. That means the non-negative check is no longer necessary, and has therefore been removed. The slice bounds check, in it’s entirety, is now represented by just the OpIsSliceInBounds in the SSA.

Exactly.

@randall77 As an aside because I’d like to learn more about it: which instruction do we use to check both the lower and upper bounds? Is it just done as an unsigned comparison?

Yes.

randall77 on Apr 8, 2019