diff options
author | Austin Clements <austin@google.com> | 2018-01-11 16:32:02 -0500 |
---|---|---|
committer | Austin Clements <austin@google.com> | 2018-03-08 22:25:28 +0000 |
commit | 6436270dadb232e3ef1afc0d4cf714bcb9434910 (patch) | |
tree | 143f097abbe291268925934ccc1a77b0bf5ff89f /src/cmd/compile/internal/ssa/prove.go | |
parent | 941fc129e2f059a5fb9f5ab77f5cb12aedecd145 (diff) | |
download | go-6436270dadb232e3ef1afc0d4cf714bcb9434910.tar.gz go-6436270dadb232e3ef1afc0d4cf714bcb9434910.zip |
cmd/compile: add fence-post implications to prove
This adds four new deductions to the prove pass, all related to adding
or subtracting one from a value. This is the first hint of actual
arithmetic relations in the prove pass.
The most effective of these is
x-1 >= w && x > min ⇒ x > w
This helps eliminate bounds checks in code like
if x > 0 {
// do something with s[x-1]
}
Altogether, these deductions prove an additional 260 branches in std
and cmd. Furthermore, they will let us eliminate some tricky
compiler-inserted panics in the runtime that are interfering with
static analysis.
Fixes #23354.
Change-Id: I7088223e0e0cd6ff062a75c127eb4bb60e6dce02
Reviewed-on: https://go-review.googlesource.com/87480
Reviewed-by: Keith Randall <khr@golang.org>
Reviewed-by: Alexandru Moșoi <alexandru@mosoi.ro>
Diffstat (limited to 'src/cmd/compile/internal/ssa/prove.go')
-rw-r--r-- | src/cmd/compile/internal/ssa/prove.go | 73 |
1 files changed, 73 insertions, 0 deletions
diff --git a/src/cmd/compile/internal/ssa/prove.go b/src/cmd/compile/internal/ssa/prove.go index 10a16917b6..f723ea5e90 100644 --- a/src/cmd/compile/internal/ssa/prove.go +++ b/src/cmd/compile/internal/ssa/prove.go @@ -305,6 +305,53 @@ func (ft *factsTable) update(parent *Block, v, w *Value, d domain, r relation) { v.Block.Func.Warnl(parent.Pos, "parent=%s, new limits %s %s %s", parent, v, w, lim.String()) } } + + // Process fence-post implications. + // + // First, make the condition > or >=. + if r == lt || r == lt|eq { + v, w = w, v + r = reverseBits[r] + } + switch r { + case gt: + if x, delta := isConstDelta(v); x != nil && delta == 1 { + // x+1 > w ⇒ x >= w + // + // This is useful for eliminating the + // growslice branch of append. + ft.update(parent, x, w, d, gt|eq) + } else if x, delta := isConstDelta(w); x != nil && delta == -1 { + // v > x-1 ⇒ v >= x + ft.update(parent, v, x, d, gt|eq) + } + case gt | eq: + if x, delta := isConstDelta(v); x != nil && delta == -1 { + // x-1 >= w && x > min ⇒ x > w + // + // Useful for i > 0; s[i-1]. + lim, ok := ft.limits[x.ID] + if ok && lim.min > opMin[v.Op] { + ft.update(parent, x, w, d, gt) + } + } else if x, delta := isConstDelta(w); x != nil && delta == 1 { + // v >= x+1 && x < max ⇒ v > x + lim, ok := ft.limits[x.ID] + if ok && lim.max < opMax[w.Op] { + ft.update(parent, v, x, d, gt) + } + } + } +} + +var opMin = map[Op]int64{ + OpAdd64: math.MinInt64, OpSub64: math.MinInt64, + OpAdd32: math.MinInt32, OpSub32: math.MinInt32, +} + +var opMax = map[Op]int64{ + OpAdd64: math.MaxInt64, OpSub64: math.MaxInt64, + OpAdd32: math.MaxInt32, OpSub32: math.MaxInt32, } // isNonNegative returns true if v is known to be non-negative. @@ -803,3 +850,29 @@ func isNonNegative(v *Value) bool { } return false } + +// isConstDelta returns non-nil if v is equivalent to w+delta (signed). +func isConstDelta(v *Value) (w *Value, delta int64) { + cop := OpConst64 + switch v.Op { + case OpAdd32, OpSub32: + cop = OpConst32 + } + switch v.Op { + case OpAdd64, OpAdd32: + if v.Args[0].Op == cop { + return v.Args[1], v.Args[0].AuxInt + } + if v.Args[1].Op == cop { + return v.Args[0], v.Args[1].AuxInt + } + case OpSub64, OpSub32: + if v.Args[1].Op == cop { + aux := v.Args[1].AuxInt + if aux != -aux { // Overflow; too bad + return v.Args[0], -aux + } + } + } + return nil, 0 +} |