From bb5ff5342d31723ecf245e8e53b79bce23b88839 Mon Sep 17 00:00:00 2001 From: Jakub Ciolek Date: Mon, 3 Oct 2022 18:08:29 +0200 Subject: [PATCH] cmd/compile: make loopbce handle 8, 16 and 32 bit induction variables Compute limits and increment values for all integer widths. Resolves 2 TODO's in loopbce.go compilecmp linux/amd64: compress/flate compress/flate.(*huffmanEncoder).bitCounts 1235 -> 1207 (-2.27%) cmd/internal/obj/wasm cmd/internal/obj/wasm.assemble 7443 -> 7303 (-1.88%) cmd/internal/obj/wasm.assemble.func1 165 -> 138 (-16.36%) cmd/link/internal/ld cmd/link/internal/ld.(*Link).findfunctab.func1 1646 -> 1627 (-1.15%) Change-Id: I2d79b7376eb67d6bcc8fdaf0c197c11e631562d0 Reviewed-on: https://go-review.googlesource.com/c/go/+/435258 Reviewed-by: Benny Siegert Run-TryBot: Keith Randall TryBot-Result: Gopher Robot Reviewed-by: Keith Randall Reviewed-by: Keith Randall --- src/cmd/compile/internal/ssa/loopbce.go | 49 ++++++++++++++----------- test/loopbce.go | 24 ++++++++++++ 2 files changed, 51 insertions(+), 22 deletions(-) diff --git a/src/cmd/compile/internal/ssa/loopbce.go b/src/cmd/compile/internal/ssa/loopbce.go index d92566f2d3..273ead4942 100644 --- a/src/cmd/compile/internal/ssa/loopbce.go +++ b/src/cmd/compile/internal/ssa/loopbce.go @@ -6,8 +6,8 @@ package ssa import ( "cmd/compile/internal/base" + "cmd/compile/internal/types" "fmt" - "math" ) type indVarFlags uint8 @@ -44,9 +44,9 @@ func parseIndVar(ind *Value) (min, inc, nxt *Value) { return } - if n := ind.Args[0]; n.Op == OpAdd64 && (n.Args[0] == ind || n.Args[1] == ind) { + if n := ind.Args[0]; (n.Op == OpAdd64 || n.Op == OpAdd32 || n.Op == OpAdd16 || n.Op == OpAdd8) && (n.Args[0] == ind || n.Args[1] == ind) { min, nxt = ind.Args[1], n - } else if n := ind.Args[1]; n.Op == OpAdd64 && (n.Args[0] == ind || n.Args[1] == ind) { + } else if n := ind.Args[1]; (n.Op == OpAdd64 || n.Op == OpAdd32 || n.Op == OpAdd16 || n.Op == OpAdd8) && (n.Args[0] == ind || n.Args[1] == ind) { min, nxt = ind.Args[0], n } else { // Not a recognized induction variable. @@ -80,8 +80,6 @@ func parseIndVar(ind *Value) (min, inc, nxt *Value) { // goto loop // // exit_loop: -// -// TODO: handle 32 bit operations func findIndVar(f *Func) []indVar { var iv []indVar sdom := f.Sdom() @@ -96,15 +94,14 @@ func findIndVar(f *Func) []indVar { var limit *Value // ending value // Check thet the control if it either ind 0 { - if limit.Op == OpConst64 { + if limit.isGenericIntConst() { // Figure out the actual largest value. v := limit.AuxInt if !inclusive { - if v == math.MinInt64 { + if v == minSignedValue(limit.Type) { return false // < minint is never satisfiable. } v-- } - if init.Op == OpConst64 { + if init.isGenericIntConst() { // Use stride to compute a better lower limit. if init.AuxInt > v { return false @@ -205,7 +202,7 @@ func findIndVar(f *Func) []indVar { } if inclusive && v != limit.AuxInt || !inclusive && v+1 != limit.AuxInt { // We know a better limit than the programmer did. Use our limit instead. - limit = f.ConstInt64(f.Config.Types.Int64, v) + limit = f.constVal(limit.Op, limit.Type, v, true) inclusive = true } return true @@ -227,18 +224,18 @@ func findIndVar(f *Func) []indVar { return step <= k } // ind < knn - k cannot overflow if step is at most k+1 - return step <= k+1 && k != math.MaxInt64 + return step <= k+1 && k != maxSignedValue(limit.Type) } else { // step < 0 if limit.Op == OpConst64 { // Figure out the actual smallest value. v := limit.AuxInt if !inclusive { - if v == math.MaxInt64 { + if v == maxSignedValue(limit.Type) { return false // > maxint is never satisfiable. } v++ } - if init.Op == OpConst64 { + if init.isGenericIntConst() { // Use stride to compute a better lower limit. if init.AuxInt < v { return false @@ -250,7 +247,7 @@ func findIndVar(f *Func) []indVar { } if inclusive && v != limit.AuxInt || !inclusive && v-1 != limit.AuxInt { // We know a better limit than the programmer did. Use our limit instead. - limit = f.ConstInt64(f.Config.Types.Int64, v) + limit = f.constVal(limit.Op, limit.Type, v, true) inclusive = true } return true @@ -361,14 +358,14 @@ func findKNN(v *Value) (*Value, int64) { var x, y *Value x = v switch v.Op { - case OpSub64: + case OpSub64, OpSub32, OpSub16, OpSub8: x = v.Args[0] y = v.Args[1] - case OpAdd64: + case OpAdd64, OpAdd32, OpAdd16, OpAdd8: x = v.Args[0] y = v.Args[1] - if x.Op == OpConst64 { + if x.isGenericIntConst() { x, y = y, x } } @@ -380,10 +377,10 @@ func findKNN(v *Value) (*Value, int64) { if y == nil { return x, 0 } - if y.Op != OpConst64 { + if !y.isGenericIntConst() { return nil, 0 } - if v.Op == OpAdd64 { + if v.Op == OpAdd64 || v.Op == OpAdd32 || v.Op == OpAdd16 || v.Op == OpAdd8 { return x, -y.AuxInt } return x, y.AuxInt @@ -419,3 +416,11 @@ func printIndVar(b *Block, i, min, max *Value, inc int64, flags indVarFlags) { } b.Func.Warnl(b.Pos, "Induction variable: limits %v%v,%v%v, increment %d%s", mb1, mlim1, mlim2, mb2, inc, extra) } + +func minSignedValue(t *types.Type) int64 { + return -1 << (t.Size()*8 - 1) +} + +func maxSignedValue(t *types.Type) int64 { + return 1<<((t.Size()*8)-1) - 1 +} diff --git a/test/loopbce.go b/test/loopbce.go index db830daf5c..fcf0d8d90d 100644 --- a/test/loopbce.go +++ b/test/loopbce.go @@ -63,6 +63,30 @@ func f5(a [10]int) int { return x } +func f5_int32(a [10]int) int { + x := 0 + for i := int32(-10); i < int32(len(a)); i += 2 { // ERROR "Induction variable: limits \[-10,8\], increment 2$" + x += a[i] + } + return x +} + +func f5_int16(a [10]int) int { + x := 0 + for i := int16(-10); i < int16(len(a)); i += 2 { // ERROR "Induction variable: limits \[-10,8\], increment 2$" + x += a[i] + } + return x +} + +func f5_int8(a [10]int) int { + x := 0 + for i := int8(-10); i < int8(len(a)); i += 2 { // ERROR "Induction variable: limits \[-10,8\], increment 2$" + x += a[i] + } + return x +} + func f6(a []int) { for i := range a { // ERROR "Induction variable: limits \[0,\?\), increment 1$" b := a[0:i] // ERROR "(\([0-9]+\) )?Proved IsSliceInBounds$" -- 2.50.0