cmd/compile: bounds check elimination for len(x) - 1 #23354

Closed
opened this issue Jan 5, 2018 · 9 comments
Closed

cmd/compile: bounds check elimination for len(x) - 1#23354

opened this issue Jan 5, 2018 · 9 comments
Labels
Milestone

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

go version devel +1a9f27d503 Thu Jan 4 02:17:33 2018 +0000 linux/amd64

Yes.

What did you do?

```package main

var x []int

func main() {
if n := len(x); n > 0 {
x[n-1] = 0
}
}```

What did you expect to see?

There should be no bounds check for `x[n-1]`.

There is a bounds check.

This comes up in practice for two reasons:

1. The range loop construction @dr2chase experimented with to eliminate the out-of-bounds pointer produces exactly this sort of pattern, which in turn causes additional bounds checks to be produced.

2. This pattern appears in `runtime.newdefer`, which must be recursively `go:nosplit`. I'm adding a static check of this for #21314. Unfortunately, while I can see that the generated call to `panic` here can't happen dynamically, the linker can't, so the static check fails. I can contort the code to the following, but it would be nicer if I didn't have to:

```	if n := len(x) - 1; n >= 0 && n < len(x) {
x[n-1] = 0
}```

/cc @dr2chase

added this to the Go1.11 milestone Jan 5, 2018

aclements commented Jan 6, 2018

 In general the prove pass doesn't know about arithmetic, but I wonder if it could cover several more cases if we just taught it about n-1 and n+1. In particular: ``````n > m ==> n-1 >= m n+1 > m ==> n >= m n < m ==> n+1 <= m n-1 < m ==> n <= m `````` If I understand the pass correctly, cases 2 and 4 could be done by adding the RHS to the fact set if we see the LHS. Cases 1 and 3 could be done by looking for the LHS in the fact set if we're trying to prove the RHS. I went down this path because of another similar case: ```package main var x []int func main() { if len(x) < cap(x) { x = append(x, 1) } }``` In this case, we fail to eliminate the `growslice` path of `append` because the lowering generates a condition of the form `len(x) + 1 > cap(x)`. As an experiment, I modified the `append` lowering for the case of a single argument to produce `len(x) >= cap(x)` and the prove pass was able to eliminate the `growslice`.

aclements commented Jan 6, 2018

 Hmm. Those implications are enough for the append case, but not quite enough for the original case. You can use them to prove `n-1 >= 0`, but not to prove `n-1 < len(x)`. For that you need a slightly stronger condition because of wrap-around: `n <= m && n > min ==> n-1 < m` (where `min` is the minimum value representable by n). In other words, to prove `n-1 < len(x)`, you need to prove both that `n > min` (which follows from `n > 0` and that `n <= len(x)` (which follows from `n == len(x)`). It looks like the facts table tracks relations with constants, too, so I think this is actually pretty easy. The full set of pseudo-inverses is: ``````n-1 >= m && n > min ==> n > m n >= m && n < max ==> n+1 > m n+1 <= m && n < max ==> n < m n <= m && n > min ==> n-1 < m ``````
added the label Jan 6, 2018

gopherbot commented Jan 11, 2018

 Change https://golang.org/cl/87478 mentions this issue: `cmd/compile: make prove pass use unsatisfiability`

gopherbot commented Jan 11, 2018

 Change https://golang.org/cl/87477 mentions this issue: `cmd/compile: simplify limit logic in prove`

gopherbot commented Jan 11, 2018

 Change https://golang.org/cl/87480 mentions this issue: `cmd/compile: add fence-post implications to prove`

dgryski commented Feb 14, 2018

 In dgryski/go-metro@1308eab I got a major performance boost by changing the loop to remove the reassignments to `ptr` which, even though they were still within range, I assume invalidated somehow the bounds checks for that were valid for `ptr` before the assignment. Does the new prover handle this case? Should it?

aclements commented Feb 15, 2018

 @dgryski, unfortunately the new prover still won't understand this. I taught it about x+1 and x-1 in some very limited cases, but in general the prover doesn't do arithmetic. For example, going into the loop, it knows that `len(ptr) >= 32`, but when it sees the effective `len(ptr1) = len(ptr) - 8` caused by the slice, it can't follow the subtraction, so it doesn't know that that implies `len(ptr1) >= 24`. It's an interesting test case, though. You could file a bug if you haven't already, though I don't know if/when we'd get to it. (I did spend a while thinking about how to teach it more generally about x ± C, but since it's on a modular ring, it gets really complicated really fast.)

dr2chase commented Feb 16, 2018

 You can work with the modular ring, but it requires additional facts to prove that x ± C doesn't "go around" the ring.

aclements commented Feb 16, 2018

 Then you're not really working with the modular ring. :) I mostly worked out a way to do with it general intervals on the modular ring (including intervals that wrapped). It had some nice properties, like supporting any fact of the form "x ± C op y ± D" in both signed and unsigned under one unified umbrella, but that umbrella got quite complicated so I didn't finish working out all the details.
pushed a commit that referenced this issue Mar 8, 2018
``` cmd/compile: simplify limit logic in prove ```
``` 2e9cf5f ```
```This replaces the open-coded intersection of limits in the prove pass
with a general limit intersection operation. This should get identical
results except in one case where it's more precise: when handling an
equality relation, if the value is *outside* the existing range, this
will reduce the range to empty rather than resetting it. This will be
important to a follow-up CL where we can take advantage of empty
ranges.

For #23354.

Change-Id: I3d3d75924f61b1da1cb604b3a9d189b26fb3a14e
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Keith Randall <khr@golang.org>
Reviewed-by: Alexandru Moșoi <alexandru@mosoi.ro>```
pushed a commit that referenced this issue Mar 8, 2018
``` cmd/compile: make prove pass use unsatisfiability ```
``` 669db2c ```
```Currently the prove pass uses implication queries. For each block, it
collects the set of branch conditions leading to that block, and
queries this fact table for whether any of these facts imply the
block's own branch condition (or its inverse). This works remarkably
well considering it doesn't do any deduction on these facts, but it
has various downsides:

1. It requires an implementation both of adding facts to the table and
determining implications. These are very nearly duals of each
other, but require separate implementations. Likewise, the process
of asserting facts of dominating branch conditions is very nearly
the dual of the process of querying implied branch conditions.

2. It leads to less effective use of derived facts. For example, the
prove pass currently derives facts about the relations between len
and cap, but can't make use of these unless a branch condition is
in the exact form of a derived fact. If one of these derived facts
contradicts another fact, it won't notice or make use of this.

This CL changes the approach of the prove pass to instead use
branch condition, it simply adds branch conditions to the fact table.
If this leads to a contradiction (specifically, it makes the fact set
unsatisfiable), that branch is impossible and can be cut. As a result,

1. We can eliminate the code for determining implications
(factsTable.get disappears entirely). Also, there is now a single
implementation of visiting and asserting branch conditions, since
we don't have to flip them around to treat them as facts in one
place and queries in another.

2. Derived facts can be used effectively. It doesn't matter *why* the
fact table is unsatisfiable; a contradiction in any of the facts is
enough.

3. As an added benefit, it's now quite easy to avoid traversing beyond
provably-unreachable blocks. In contrast, the current
implementation always visits all blocks.

The prove pass already has nearly all of the mechanism necessary to
compute unsatisfiability, which means this both simplifies the code
and makes it more powerful.

The only complication is that the current implication procedure has a
hack for dealing with the 0 <= Args[0] condition of OpIsInBounds and
OpIsSliceInBounds. We replace this with asserting the appropriate fact
when we process one of these conditions. This seems much cleaner
anyway, and works because we can now take advantage of derived facts.

This has no measurable effect on compiler performance.

Effectiveness:

There is exactly one condition in all of std and cmd that this fails
to prove that the old implementation could: (int64(^uint(0)>>1) < x)
in encoding/gob. This can never be true because x is an int, and it's
basically coincidence that the old code gets this. (For example, it
fails to prove the similar (x < ^int64(^uint(0)>>1)) condition that
immediately precedes it, and even though the conditions are logically
unrelated, it wouldn't get the second one if it hadn't first processed
the first!)

It does, however, prove a few dozen additional branches. These come
from facts that are added to the fact table about the relations
between len and cap. These were almost never queried directly before,
able to use.

There are exactly two branches in std and cmd that this implementation
proves in the *other* direction. This sounds scary, but is okay
because both occur in already-unreachable blocks, so it doesn't matter
what we chose. Because the fact table logic is sound but incomplete,
it fails to prove that the block isn't reachable, even though it is
able to prove that both outgoing branches are impossible. We could
turn these blocks into BlockExit blocks, but it doesn't seem worth the
trouble of the extra proof effort for something that happens twice in
all of std and cmd.

Tests:

This CL updates test/prove.go to change the expected messages because
it can no longer give a "reason" why it proved or disproved a
condition. It also adds a new test of a branch it couldn't prove
before.

It mostly guts test/sliceopt.go, removing everything related to slice
bounds optimizations and moving a few relevant tests to test/prove.go.
Much of this test is actually unreachable. The new prove pass figures
this out and doesn't try to prove anything about the unreachable
parts. The output on the unreachable parts is already suspect because
anything can be proved at that point, so it's really just a regression
test for an algorithm the compiler no longer uses.

This is a step toward fixing #23354. That issue is quite easy to fix
once we can use derived facts effectively.

Change-Id: Ia48a1b9ee081310579fe474e4a61857424ff8ce8
Reviewed-by: Keith Randall <khr@golang.org>```
closed this in ``` 6436270 ``` Mar 8, 2018
mentioned this issue Apr 15, 2018
locked and limited conversation to collaborators Mar 8, 2019
added the label Mar 8, 2019