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 <bsiegert@gmail.com>
Run-TryBot: Keith Randall <khr@golang.org>
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Keith Randall <khr@golang.org>
Reviewed-by: Keith Randall <khr@google.com>

1 files changed, 27 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 </<= limit or limit </<= ind.
-		// TODO: Handle 32-bit comparisons.
 		// TODO: Handle unsigned comparisons?
 		c := b.Controls[0]
 		inclusive := false
 		switch c.Op {
-		case OpLeq64:
+		case OpLeq64, OpLeq32, OpLeq16, OpLeq8:
 			inclusive = true
 			fallthrough
-		case OpLess64:
+		case OpLess64, OpLess32, OpLess16, OpLess8:
 			ind, limit = c.Args[0], c.Args[1]
 		default:
 			continue
@@ -131,7 +128,7 @@ func findIndVar(f *Func) []indVar {
 		}
 
 		// Expect the increment to be a nonzero constant.
-		if inc.Op != OpConst64 {
+		if !inc.isGenericIntConst() {
 			continue
 		}
 		step := inc.AuxInt
@@ -184,16 +181,16 @@ func findIndVar(f *Func) []indVar {
 		// This function returns true if the increment will never overflow/underflow.
 		ok := func() bool {
 			if step > 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
+}