cmd/compile: intrinsics for math/bits.TrailingZerosX

Implement math/bits.TrailingZerosX using intrinsics.

Generally reorganize the intrinsic spec a bit.
The instrinsics data structure is now built at init time.
This will make doing the other functions in math/bits easier.

Update sys.CtzX to return int instead of uint{64,32} so it
matches math/bits.TrailingZerosX.

Improve the intrinsics a bit for amd64.  We don't need the CMOV
for <64 bit versions.

Update #18616

Change-Id: Ic1c5339c943f961d830ae56f12674d7b29d4ff39
Reviewed-on: https://go-review.googlesource.com/38155
Run-TryBot: Keith Randall <khr@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Robert Griesemer <gri@golang.org>

6 files changed, 22 insertions, 24 deletions

diff --git a/src/runtime/internal/sys/intrinsics.go b/src/runtime/internal/sys/intrinsics.go
index db2cbecc0e..4e119b0470 100644
--- a/src/runtime/internal/sys/intrinsics.go
+++ b/src/runtime/internal/sys/intrinsics.go
@@ -32,22 +32,22 @@ var deBruijnIdx32 = [32]byte{
 
 // Ctz64 counts trailing (low-order) zeroes,
 // and if all are zero, then 64.
-func Ctz64(x uint64) uint64 {
+func Ctz64(x uint64) int {
 	x &= -x                      // isolate low-order bit
 	y := x * deBruijn64 >> 58    // extract part of deBruijn sequence
-	y = uint64(deBruijnIdx64[y]) // convert to bit index
-	z := (x - 1) >> 57 & 64      // adjustment if zero
-	return y + z
+	i := int(deBruijnIdx64[y])   // convert to bit index
+	z := int((x - 1) >> 57 & 64) // adjustment if zero
+	return i + z
 }
 
 // Ctz32 counts trailing (low-order) zeroes,
 // and if all are zero, then 32.
-func Ctz32(x uint32) uint32 {
+func Ctz32(x uint32) int {
 	x &= -x                      // isolate low-order bit
 	y := x * deBruijn32 >> 27    // extract part of deBruijn sequence
-	y = uint32(deBruijnIdx32[y]) // convert to bit index
-	z := (x - 1) >> 26 & 32      // adjustment if zero
-	return y + z
+	i := int(deBruijnIdx32[y])   // convert to bit index
+	z := int((x - 1) >> 26 & 32) // adjustment if zero
+	return i + z
 }
 
 // Bswap64 returns its input with byte order reversed
diff --git a/src/runtime/internal/sys/intrinsics_386.s b/src/runtime/internal/sys/intrinsics_386.s
index bc63e5ebdf..4bb4cd63f8 100644
--- a/src/runtime/internal/sys/intrinsics_386.s
+++ b/src/runtime/internal/sys/intrinsics_386.s
@@ -4,14 +4,12 @@
 
 #include "textflag.h"
 
-TEXT runtime∕internal∕sys·Ctz64(SB), NOSPLIT, $0-16
-	MOVL	$0, ret_hi+12(FP)
-
+TEXT runtime∕internal∕sys·Ctz64(SB), NOSPLIT, $0-12
 	// Try low 32 bits.
 	MOVL	x_lo+0(FP), AX
 	BSFL	AX, AX
 	JZ	tryhigh
-	MOVL	AX, ret_lo+8(FP)
+	MOVL	AX, ret+8(FP)
 	RET
 
 tryhigh:
@@ -20,12 +18,12 @@ tryhigh:
 	BSFL	AX, AX
 	JZ	none
 	ADDL	$32, AX
-	MOVL	AX, ret_lo+8(FP)
+	MOVL	AX, ret+8(FP)
 	RET
 
 none:
 	// No bits are set.
-	MOVL	$64, ret_lo+8(FP)
+	MOVL	$64, ret+8(FP)
 	RET
 
 TEXT runtime∕internal∕sys·Ctz32(SB), NOSPLIT, $0-8
diff --git a/src/runtime/internal/sys/intrinsics_stubs.go b/src/runtime/internal/sys/intrinsics_stubs.go
index d351048f86..4d991f43bf 100644
--- a/src/runtime/internal/sys/intrinsics_stubs.go
+++ b/src/runtime/internal/sys/intrinsics_stubs.go
@@ -6,7 +6,7 @@
 
 package sys
 
-func Ctz64(x uint64) uint64
-func Ctz32(x uint32) uint32
+func Ctz64(x uint64) int
+func Ctz32(x uint32) int
 func Bswap64(x uint64) uint64
 func Bswap32(x uint32) uint32
diff --git a/src/runtime/internal/sys/intrinsics_test.go b/src/runtime/internal/sys/intrinsics_test.go
index 1f2c8daa96..0444183e9d 100644
--- a/src/runtime/internal/sys/intrinsics_test.go
+++ b/src/runtime/internal/sys/intrinsics_test.go
@@ -6,17 +6,17 @@ import (
 )
 
 func TestCtz64(t *testing.T) {
-	for i := uint(0); i <= 64; i++ {
-		x := uint64(5) << i
-		if got := sys.Ctz64(x); got != uint64(i) {
+	for i := 0; i <= 64; i++ {
+		x := uint64(5) << uint(i)
+		if got := sys.Ctz64(x); got != i {
 			t.Errorf("Ctz64(%d)=%d, want %d", x, got, i)
 		}
 	}
 }
 func TestCtz32(t *testing.T) {
-	for i := uint(0); i <= 32; i++ {
-		x := uint32(5) << i
-		if got := sys.Ctz32(x); got != uint32(i) {
+	for i := 0; i <= 32; i++ {
+		x := uint32(5) << uint(i)
+		if got := sys.Ctz32(x); got != i {
 			t.Errorf("Ctz32(%d)=%d, want %d", x, got, i)
 		}
 	}
diff --git a/src/runtime/malloc.go b/src/runtime/malloc.go
index 25ae261bb2..344771c899 100644
--- a/src/runtime/malloc.go
+++ b/src/runtime/malloc.go
@@ -491,7 +491,7 @@ func nextFreeFast(s *mspan) gclinkptr {
 			if freeidx%64 == 0 && freeidx != s.nelems {
 				return 0
 			}
-			s.allocCache >>= (theBit + 1)
+			s.allocCache >>= uint(theBit + 1)
 			s.freeindex = freeidx
 			v := gclinkptr(result*s.elemsize + s.base())
 			s.allocCount++
diff --git a/src/runtime/mbitmap.go b/src/runtime/mbitmap.go
index 4e1a3e29f9..b48dbff7f6 100644
--- a/src/runtime/mbitmap.go
+++ b/src/runtime/mbitmap.go
@@ -248,7 +248,7 @@ func (s *mspan) nextFreeIndex() uintptr {
 		return snelems
 	}
 
-	s.allocCache >>= (bitIndex + 1)
+	s.allocCache >>= uint(bitIndex + 1)
 	sfreeindex = result + 1
 
 	if sfreeindex%64 == 0 && sfreeindex != snelems {