From 4dcbb00be200bc1f88b534c311ed4289eb2fbdd5 Mon Sep 17 00:00:00 2001 From: Keith Randall Date: Sat, 26 Oct 2024 14:19:32 -0700 Subject: [PATCH] cmd/compile: teach prove about min/max phi operations If there is a phi that is computing the minimum of its two inputs, then we know the result of the phi is smaller than or equal to both of its inputs. Similarly for maxiumum (although max seems less useful). This pattern happens for the case n := copy(a, b) n is the minimum of len(a) and len(b), so with this optimization we know both n <= len(a) and n <= len(b). That extra information is helpful for subsequent slicing of a or b. Fixes #16833 Change-Id: Ib4238fd1edae0f2940f62a5516a6b363bbe7928c Reviewed-on: https://go-review.googlesource.com/c/go/+/622240 Reviewed-by: Carlos Amedee LUCI-TryBot-Result: Go LUCI Reviewed-by: Josh Bleecher Snyder Reviewed-by: David Chase --- src/cmd/compile/internal/ssa/block.go | 9 +++ src/cmd/compile/internal/ssa/prove.go | 79 ++++++++++++++++++++++++++- test/prove.go | 42 ++++++++++++++ 3 files changed, 129 insertions(+), 1 deletion(-) diff --git a/src/cmd/compile/internal/ssa/block.go b/src/cmd/compile/internal/ssa/block.go index 02733eaf16..0c9aea8f96 100644 --- a/src/cmd/compile/internal/ssa/block.go +++ b/src/cmd/compile/internal/ssa/block.go @@ -366,6 +366,15 @@ func (b *Block) removePhiArg(phi *Value, i int) { phielimValue(phi) } +// uniquePred returns the predecessor of b, if there is exactly one. +// Returns nil otherwise. +func (b *Block) uniquePred() *Block { + if len(b.Preds) != 1 { + return nil + } + return b.Preds[0].b +} + // LackingPos indicates whether b is a block whose position should be inherited // from its successors. This is true if all the values within it have unreliable positions // and if it is "plain", meaning that there is no control flow that is also very likely diff --git a/src/cmd/compile/internal/ssa/prove.go b/src/cmd/compile/internal/ssa/prove.go index e955dc5f0f..c0ab38139d 100644 --- a/src/cmd/compile/internal/ssa/prove.go +++ b/src/cmd/compile/internal/ssa/prove.go @@ -2026,8 +2026,85 @@ func addLocalFacts(ft *factsTable, b *Block) { if v.Args[0].Op == OpSliceMake { ft.update(b, v, v.Args[0].Args[2], signed, eq) } - } + case OpPhi: + addLocalFactsPhi(ft, v) + } + } +} + +func addLocalFactsPhi(ft *factsTable, v *Value) { + // Look for phis that implement min/max. + // z: + // c = Less64 x y (or other Less/Leq operation) + // If c -> bx by + // bx: <- z + // -> b ... + // by: <- z + // -> b ... + // b: <- bx by + // v = Phi x y + // Then v is either min or max of x,y. + // If it is the min, then we deduce v <= x && v <= y. + // If it is the max, then we deduce v >= x && v >= y. + // The min case is useful for the copy builtin, see issue 16833. + if len(v.Args) != 2 { + return + } + b := v.Block + x := v.Args[0] + y := v.Args[1] + bx := b.Preds[0].b + by := b.Preds[1].b + var z *Block // branch point + switch { + case bx == by: // bx == by == z case + z = bx + case by.uniquePred() == bx: // bx == z case + z = bx + case bx.uniquePred() == by: // by == z case + z = by + case bx.uniquePred() == by.uniquePred(): + z = bx.uniquePred() + } + if z == nil || z.Kind != BlockIf { + return + } + c := z.Controls[0] + if len(c.Args) != 2 { + return + } + var isMin bool // if c, a less-than comparison, is true, phi chooses x. + if bx == z { + isMin = b.Preds[0].i == 0 + } else { + isMin = bx.Preds[0].i == 0 + } + if c.Args[0] == x && c.Args[1] == y { + // ok + } else if c.Args[0] == y && c.Args[1] == x { + // Comparison is reversed from how the values are listed in the Phi. + isMin = !isMin + } else { + // Not comparing x and y. + return + } + var dom domain + switch c.Op { + case OpLess64, OpLess32, OpLess16, OpLess8, OpLeq64, OpLeq32, OpLeq16, OpLeq8: + dom = signed + case OpLess64U, OpLess32U, OpLess16U, OpLess8U, OpLeq64U, OpLeq32U, OpLeq16U, OpLeq8U: + dom = unsigned + default: + return + } + var rel relation + if isMin { + rel = lt | eq + } else { + rel = gt | eq } + ft.update(b, v, x, dom, rel) + ft.update(b, v, y, dom, rel) } var ctzNonZeroOp = map[Op]Op{OpCtz8: OpCtz8NonZero, OpCtz16: OpCtz16NonZero, OpCtz32: OpCtz32NonZero, OpCtz64: OpCtz64NonZero} diff --git a/test/prove.go b/test/prove.go index 2265b637ba..edfd8908a2 100644 --- a/test/prove.go +++ b/test/prove.go @@ -1670,6 +1670,48 @@ func neg64mightOverflowDuringNeg(a uint64, ensureAllBranchesCouldHappen func() b return z } +func phiMin(a, b []byte) { + _ = a[:min(len(a), len(b))] // ERROR "Proved IsSliceInBounds" + _ = b[:min(len(a), len(b))] // ERROR "Proved IsSliceInBounds" + _ = a[:max(len(a), len(b))] + _ = b[:max(len(a), len(b))] + x := len(a) + if x > len(b) { + x = len(b) + useInt(0) + } + _ = a[:x] // ERROR "Proved IsSliceInBounds" + y := len(a) + if y > len(b) { + y = len(b) + useInt(0) + } else { + useInt(1) + } + _ = b[:y] // ERROR "Proved IsSliceInBounds" +} + +func issue16833(a, b []byte) { + n := copy(a, b) + _ = a[n:] // ERROR "Proved IsSliceInBounds" + _ = b[n:] // ERROR "Proved IsSliceInBounds" + _ = a[:n] // ERROR "Proved IsSliceInBounds" + _ = b[:n] // ERROR "Proved IsSliceInBounds" +} + +func clampedIdx1(x []int, i int) int { + if len(x) == 0 { + return 0 + } + return x[min(max(0, i), len(x)-1)] // ERROR "Proved IsInBounds" +} +func clampedIdx2(x []int, i int) int { + if len(x) == 0 { + return 0 + } + return x[max(min(i, len(x)-1), 0)] // TODO: can't get rid of this bounds check yet +} + //go:noinline func useInt(a int) { } -- 2.48.1