From 62861889863d3d61f546d01aa7bd9824df1b33df Mon Sep 17 00:00:00 2001 From: Josh Bleecher Snyder Date: Thu, 26 May 2016 18:08:24 -0700 Subject: [PATCH] cmd/compile: optimize integer "in range" expressions MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit Use unsigned comparisons to reduce from two comparisons to one for integer "in range" checks, such as a <= b && b < c. We already do this for bounds checks. Extend it to user code. This is much easier to do in the front end than SSA. A back end optimization would be more powerful, but this is a good start. This reduces the power of some of SSA prove inferences (#16653), but those regressions appear to be rare and not worth holding this CL for. Fixes #15844. Fixes #16697. strconv benchmarks: name old time/op new time/op delta Atof64Decimal-8 41.4ns ± 3% 38.9ns ± 2% -5.89% (p=0.000 n=24+25) Atof64Float-8 48.5ns ± 0% 46.8ns ± 3% -3.64% (p=0.000 n=20+23) Atof64FloatExp-8 97.7ns ± 4% 93.5ns ± 1% -4.25% (p=0.000 n=25+20) Atof64Big-8 187ns ± 8% 162ns ± 2% -13.54% (p=0.000 n=24+22) Atof64RandomBits-8 250ns ± 6% 233ns ± 5% -6.76% (p=0.000 n=25+25) Atof64RandomFloats-8 160ns ± 0% 152ns ± 0% -5.00% (p=0.000 n=21+22) Atof32Decimal-8 41.1ns ± 1% 38.7ns ± 2% -5.86% (p=0.000 n=24+24) Atof32Float-8 46.1ns ± 1% 43.5ns ± 3% -5.63% (p=0.000 n=21+24) Atof32FloatExp-8 101ns ± 4% 100ns ± 2% -1.59% (p=0.000 n=24+23) Atof32Random-8 136ns ± 3% 133ns ± 3% -2.83% (p=0.000 n=22+22) Atoi-8 33.8ns ± 3% 30.6ns ± 3% -9.51% (p=0.000 n=24+25) AtoiNeg-8 31.6ns ± 3% 29.1ns ± 2% -8.05% (p=0.000 n=23+24) Atoi64-8 48.6ns ± 1% 43.8ns ± 1% -9.81% (p=0.000 n=20+23) Atoi64Neg-8 47.1ns ± 4% 42.0ns ± 2% -10.83% (p=0.000 n=25+25) FormatFloatDecimal-8 177ns ± 9% 178ns ± 6% ~ (p=0.460 n=25+25) FormatFloat-8 282ns ± 6% 282ns ± 3% ~ (p=0.954 n=25+22) FormatFloatExp-8 259ns ± 7% 255ns ± 6% ~ (p=0.089 n=25+24) FormatFloatNegExp-8 253ns ± 6% 254ns ± 6% ~ (p=0.941 n=25+24) FormatFloatBig-8 340ns ± 6% 341ns ± 8% ~ (p=0.600 n=22+25) AppendFloatDecimal-8 79.4ns ± 0% 80.6ns ± 6% ~ (p=0.861 n=20+25) AppendFloat-8 175ns ± 3% 174ns ± 0% ~ (p=0.722 n=25+20) AppendFloatExp-8 142ns ± 4% 142ns ± 2% ~ (p=0.948 n=25+24) AppendFloatNegExp-8 137ns ± 2% 138ns ± 2% +0.70% (p=0.001 n=24+25) AppendFloatBig-8 218ns ± 3% 218ns ± 4% ~ (p=0.596 n=25+25) AppendFloatBinaryExp-8 80.0ns ± 4% 78.0ns ± 1% -2.43% (p=0.000 n=24+21) AppendFloat32Integer-8 82.3ns ± 3% 79.3ns ± 4% -3.69% (p=0.000 n=24+25) AppendFloat32ExactFraction-8 143ns ± 2% 143ns ± 0% ~ (p=0.177 n=23+19) AppendFloat32Point-8 175ns ± 3% 175ns ± 3% ~ (p=0.062 n=24+25) AppendFloat32Exp-8 139ns ± 2% 137ns ± 4% -1.05% (p=0.001 n=24+24) AppendFloat32NegExp-8 134ns ± 0% 137ns ± 4% +2.06% (p=0.000 n=22+25) AppendFloat64Fixed1-8 97.8ns ± 0% 98.6ns ± 3% ~ (p=0.711 n=20+25) AppendFloat64Fixed2-8 110ns ± 3% 110ns ± 5% -0.45% (p=0.037 n=24+24) AppendFloat64Fixed3-8 102ns ± 3% 102ns ± 3% ~ (p=0.684 n=24+24) AppendFloat64Fixed4-8 112ns ± 3% 110ns ± 0% -1.43% (p=0.000 n=25+18) FormatInt-8 3.18µs ± 4% 3.10µs ± 6% -2.54% (p=0.001 n=24+25) AppendInt-8 1.81µs ± 5% 1.80µs ± 5% ~ (p=0.648 n=25+25) FormatUint-8 812ns ± 6% 816ns ± 6% ~ (p=0.777 n=25+25) AppendUint-8 536ns ± 4% 538ns ± 3% ~ (p=0.798 n=20+22) Quote-8 605ns ± 6% 602ns ± 9% ~ (p=0.573 n=25+25) QuoteRune-8 99.5ns ± 8% 100.2ns ± 7% ~ (p=0.432 n=25+25) AppendQuote-8 361ns ± 3% 363ns ± 4% ~ (p=0.085 n=25+25) AppendQuoteRune-8 23.3ns ± 3% 22.4ns ± 2% -3.79% (p=0.000 n=25+24) UnquoteEasy-8 146ns ± 4% 145ns ± 5% ~ (p=0.112 n=24+24) UnquoteHard-8 804ns ± 6% 771ns ± 6% -4.10% (p=0.000 n=25+24) Change-Id: Ibd384e46e90f1cfa40503c8c6352a54c65b72980 Reviewed-on: https://go-review.googlesource.com/27652 Run-TryBot: Josh Bleecher Snyder Reviewed-by: Matthew Dempsky TryBot-Result: Gobot Gobot --- src/cmd/compile/internal/gc/subr.go | 31 ------- src/cmd/compile/internal/gc/type.go | 22 +++++ src/cmd/compile/internal/gc/walk.go | 131 +++++++++++++++++++++++++++- test/checkbce.go | 4 +- 4 files changed, 155 insertions(+), 33 deletions(-) diff --git a/src/cmd/compile/internal/gc/subr.go b/src/cmd/compile/internal/gc/subr.go index a11d39b9b0..d8f9732bae 100644 --- a/src/cmd/compile/internal/gc/subr.go +++ b/src/cmd/compile/internal/gc/subr.go @@ -2130,37 +2130,6 @@ func powtwo(n *Node) int { return -1 } -// return the unsigned type for -// a signed integer type. -// returns T if input is not a -// signed integer type. -func tounsigned(t *Type) *Type { - // this is types[et+1], but not sure - // that this relation is immutable - switch t.Etype { - default: - fmt.Printf("tounsigned: unknown type %v\n", t) - t = nil - - case TINT: - t = Types[TUINT] - - case TINT8: - t = Types[TUINT8] - - case TINT16: - t = Types[TUINT16] - - case TINT32: - t = Types[TUINT32] - - case TINT64: - t = Types[TUINT64] - } - - return t -} - func ngotype(n *Node) *Sym { if n.Type != nil { return typenamesym(n.Type) diff --git a/src/cmd/compile/internal/gc/type.go b/src/cmd/compile/internal/gc/type.go index 460b395c2e..9da83a3435 100644 --- a/src/cmd/compile/internal/gc/type.go +++ b/src/cmd/compile/internal/gc/type.go @@ -1076,6 +1076,28 @@ func (t *Type) IsBoolean() bool { return t.Etype == TBOOL } +var unsignedEType = [...]EType{ + TINT8: TUINT8, + TUINT8: TUINT8, + TINT16: TUINT16, + TUINT16: TUINT16, + TINT32: TUINT32, + TUINT32: TUINT32, + TINT64: TUINT64, + TUINT64: TUINT64, + TINT: TUINT, + TUINT: TUINT, + TUINTPTR: TUINTPTR, +} + +// toUnsigned returns the unsigned equivalent of integer type t. +func (t *Type) toUnsigned() *Type { + if !t.IsInteger() { + Fatalf("unsignedType(%v)", t) + } + return Types[unsignedEType[t.Etype]] +} + func (t *Type) IsInteger() bool { switch t.Etype { case TINT8, TUINT8, TINT16, TUINT16, TINT32, TUINT32, TINT64, TUINT64, TINT, TUINT, TUINTPTR: diff --git a/src/cmd/compile/internal/gc/walk.go b/src/cmd/compile/internal/gc/walk.go index 114f1b0962..1ba2f7ba4b 100644 --- a/src/cmd/compile/internal/gc/walk.go +++ b/src/cmd/compile/internal/gc/walk.go @@ -631,6 +631,7 @@ opswitch: n.Right = walkexpr(n.Right, &ll) n.Right = addinit(n.Right, ll.Slice()) + n = walkinrange(n, init) case OPRINT, OPRINTN: walkexprlist(n.List.Slice(), init) @@ -3406,6 +3407,134 @@ func walkrotate(n *Node) *Node { return n } +// isIntOrdering reports whether n is a <, ≤, >, or ≥ ordering between integers. +func (n *Node) isIntOrdering() bool { + switch n.Op { + case OLE, OLT, OGE, OGT: + default: + return false + } + return n.Left.Type.IsInteger() && n.Right.Type.IsInteger() +} + +// walkinrange optimizes integer-in-range checks, such as 4 <= x && x < 10. +// n must be an OANDAND or OOROR node. +// The result of walkinrange MUST be assigned back to n, e.g. +// n.Left = walkinrange(n.Left) +func walkinrange(n *Node, init *Nodes) *Node { + // We are looking for something equivalent to a opl b OP b opr c, where: + // * a, b, and c have integer type + // * b is side-effect-free + // * opl and opr are each < or ≤ + // * OP is && + l := n.Left + r := n.Right + if !l.isIntOrdering() || !r.isIntOrdering() { + return n + } + + // Find b, if it exists, and rename appropriately. + // Input is: l.Left l.Op l.Right ANDAND/OROR r.Left r.Op r.Right + // Output is: a opl b(==x) ANDAND/OROR b(==x) opr c + a, opl, b := l.Left, l.Op, l.Right + x, opr, c := r.Left, r.Op, r.Right + for i := 0; ; i++ { + if samesafeexpr(b, x) { + break + } + if i == 3 { + // Tried all permutations and couldn't find an appropriate b == x. + return n + } + if i&1 == 0 { + a, opl, b = b, Brrev(opl), a + } else { + x, opr, c = c, Brrev(opr), x + } + } + + // If n.Op is ||, apply de Morgan. + // Negate the internal ops now; we'll negate the top level op at the end. + // Henceforth assume &&. + negateResult := n.Op == OOROR + if negateResult { + opl = Brcom(opl) + opr = Brcom(opr) + } + + cmpdir := func(o Op) int { + switch o { + case OLE, OLT: + return -1 + case OGE, OGT: + return +1 + } + Fatalf("walkinrange cmpdir %v", o) + return 0 + } + if cmpdir(opl) != cmpdir(opr) { + // Not a range check; something like b < a && b < c. + return n + } + + switch opl { + case OGE, OGT: + // We have something like a > b && b ≥ c. + // Switch and reverse ops and rename constants, + // to make it look like a ≤ b && b < c. + a, c = c, a + opl, opr = Brrev(opr), Brrev(opl) + } + + // We must ensure that c-a is non-negative. + // For now, require a and c to be constants. + // In the future, we could also support a == 0 and c == len/cap(...). + // Unfortunately, by this point, most len/cap expressions have been + // stored into temporary variables. + if !Isconst(a, CTINT) || !Isconst(c, CTINT) { + return n + } + + if opl == OLT { + // We have a < b && ... + // We need a ≤ b && ... to safely use unsigned comparison tricks. + // If a is not the maximum constant for b's type, + // we can increment a and switch to ≤. + if a.Int64() >= Maxintval[b.Type.Etype].Int64() { + return n + } + a = Nodintconst(a.Int64() + 1) + opl = OLE + } + + bound := c.Int64() - a.Int64() + if bound < 0 { + // Bad news. Something like 5 <= x && x < 3. + // Rare in practice, and we still need to generate side-effects, + // so just leave it alone. + return n + } + + // We have a ≤ b && b < c (or a ≤ b && b ≤ c). + // This is equivalent to (a-a) ≤ (b-a) && (b-a) < (c-a), + // which is equivalent to 0 ≤ (b-a) && (b-a) < (c-a), + // which is equivalent to uint(b-a) < uint(c-a). + ut := b.Type.toUnsigned() + lhs := conv(Nod(OSUB, b, a), ut) + rhs := Nodintconst(bound) + if negateResult { + // Negate top level. + opr = Brcom(opr) + } + cmp := Nod(opr, lhs, rhs) + cmp.Lineno = n.Lineno + cmp = addinit(cmp, l.Ninit.Slice()) + cmp = addinit(cmp, r.Ninit.Slice()) + cmp = typecheck(cmp, Erv) + cmp = walkexpr(cmp, init) + return cmp +} + // walkmul rewrites integer multiplication by powers of two as shifts. // The result of walkmul MUST be assigned back to n, e.g. // n.Left = walkmul(n.Left, init) @@ -3694,7 +3823,7 @@ func walkdiv(n *Node, init *Nodes) *Node { var nc Node Nodconst(&nc, Types[Simtype[TUINT]], int64(w)-int64(pow)) - n2 := Nod(ORSH, conv(n1, tounsigned(nl.Type)), &nc) + n2 := Nod(ORSH, conv(n1, nl.Type.toUnsigned()), &nc) n.Left = Nod(OADD, nl, conv(n2, nl.Type)) } diff --git a/test/checkbce.go b/test/checkbce.go index fa0ea12803..59bd41b360 100644 --- a/test/checkbce.go +++ b/test/checkbce.go @@ -21,7 +21,9 @@ func f1(a [256]int, i int) { if 4 <= i && i < len(a) { useInt(a[i]) useInt(a[i-1]) // ERROR "Found IsInBounds$" - useInt(a[i-4]) // ERROR "Found IsInBounds$" + // TODO: 'if 4 <= i && i < len(a)' gets rewritten to 'if uint(i - 4) < 256 - 4', + // which the bounds checker cannot yet use to infer that the next line doesn't need a bounds check. + useInt(a[i-4]) } } -- 2.48.1