From 73f92f9b0405e98427bbb445f24cffb5d3c4d01b Mon Sep 17 00:00:00 2001 From: Keith Randall Date: Sun, 27 Nov 2016 11:43:08 -0800 Subject: [PATCH] cmd/compile: use len(s)<=cap(s) to remove more bounds checks MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit When we discover a relation x <= len(s), also discover the relation x <= cap(s). That way, in situations like: a := s[x:] // tests 0 <= x <= len(s) b := s[:x] // tests 0 <= x <= cap(s) the second check can be eliminated. Fixes #16813 Change-Id: Ifc037920b6955e43bac1a1eaf6bac63a89cfbd44 Reviewed-on: https://go-review.googlesource.com/33633 Run-TryBot: Keith Randall TryBot-Result: Gobot Gobot Reviewed-by: Alexandru Moșoi Reviewed-by: David Chase --- src/cmd/compile/internal/ssa/prove.go | 65 +++++++++++++++++++++++++-- test/checkbce.go | 2 +- test/prove.go | 12 +++++ 3 files changed, 74 insertions(+), 5 deletions(-) diff --git a/src/cmd/compile/internal/ssa/prove.go b/src/cmd/compile/internal/ssa/prove.go index 541033e2de..37c92ae544 100644 --- a/src/cmd/compile/internal/ssa/prove.go +++ b/src/cmd/compile/internal/ssa/prove.go @@ -97,6 +97,12 @@ type factsTable struct { // known lower and upper bounds on individual values. limits map[ID]limit limitStack []limitFact // previous entries + + // For each slice s, a map from s to a len(s)/cap(s) value (if any) + // TODO: check if there are cases that matter where we have + // more than one len(s) for a slice. We could keep a list if necessary. + lens map[ID]*Value + caps map[ID]*Value } // checkpointFact is an invalid value used for checkpointing @@ -432,7 +438,8 @@ var ( } ) -// prove removes redundant BlockIf controls that can be inferred in a straight line. +// prove removes redundant BlockIf branches that can be inferred +// from previous dominating comparisons. // // By far, the most common redundant pair are generated by bounds checking. // For example for the code: @@ -455,6 +462,31 @@ var ( // else branch of the first comparison is executed, we already know that i < len(a). // The code for the second panic can be removed. func prove(f *Func) { + ft := newFactsTable() + + // Find length and capacity ops. + for _, b := range f.Blocks { + for _, v := range b.Values { + if v.Uses == 0 { + // We don't care about dead values. + // (There can be some that are CSEd but not removed yet.) + continue + } + switch v.Op { + case OpSliceLen: + if ft.lens == nil { + ft.lens = map[ID]*Value{} + } + ft.lens[v.Args[0].ID] = v + case OpSliceCap: + if ft.caps == nil { + ft.caps = map[ID]*Value{} + } + ft.caps[v.Args[0].ID] = v + } + } + } + // current node state type walkState int const ( @@ -472,7 +504,6 @@ func prove(f *Func) { state: descend, }) - ft := newFactsTable() idom := f.Idom() sdom := f.sdom() @@ -559,8 +590,34 @@ func updateRestrictions(parent *Block, ft *factsTable, t domain, v, w *Value, r r = (lt | eq | gt) ^ r } for i := domain(1); i <= t; i <<= 1 { - if t&i != 0 { - ft.update(parent, v, w, i, r) + if t&i == 0 { + continue + } + ft.update(parent, v, w, i, r) + + // Additional facts we know given the relationship between len and cap. + if i != signed && i != unsigned { + continue + } + if v.Op == OpSliceLen && r< == 0 && ft.caps[v.Args[0].ID] != nil { + // len(s) > w implies cap(s) > w + // len(s) >= w implies cap(s) >= w + // len(s) == w implies cap(s) >= w + ft.update(parent, ft.caps[v.Args[0].ID], w, i, r|gt) + } + if w.Op == OpSliceLen && r> == 0 && ft.caps[w.Args[0].ID] != nil { + // same, length on the RHS. + ft.update(parent, v, ft.caps[w.Args[0].ID], i, r|lt) + } + if v.Op == OpSliceCap && r> == 0 && ft.lens[v.Args[0].ID] != nil { + // cap(s) < w implies len(s) < w + // cap(s) <= w implies len(s) <= w + // cap(s) == w implies len(s) <= w + ft.update(parent, ft.lens[v.Args[0].ID], w, i, r|lt) + } + if w.Op == OpSliceCap && r< == 0 && ft.lens[w.Args[0].ID] != nil { + // same, capacity on the RHS. + ft.update(parent, v, ft.lens[w.Args[0].ID], i, r|gt) } } } diff --git a/test/checkbce.go b/test/checkbce.go index 59bd41b360..4f9574d420 100644 --- a/test/checkbce.go +++ b/test/checkbce.go @@ -50,7 +50,7 @@ func f5(a []int) { if len(a) > 5 { useInt(a[5]) useSlice(a[6:]) - useSlice(a[:6]) // ERROR "Found IsSliceInBounds$" + useSlice(a[:6]) } } diff --git a/test/prove.go b/test/prove.go index 9ef8949e1c..5f4de604c6 100644 --- a/test/prove.go +++ b/test/prove.go @@ -451,6 +451,18 @@ func f14(p, q *int, a []int) { useInt(a[i2+j]) // ERROR "Proved boolean IsInBounds$" } +func f15(s []int, x int) { + useSlice(s[x:]) + useSlice(s[:x]) // ERROR "Proved IsSliceInBounds$" +} + +func f16(s []int) []int { + if len(s) >= 10 { + return s[:10] // ERROR "Proved non-negative bounds IsSliceInBounds$" + } + return nil +} + //go:noinline func useInt(a int) { } -- 2.50.0