From 7ac756f74b1a7dfc984152d863b3e3c86f90b2c7 Mon Sep 17 00:00:00 2001
From: Heschi Kreinick <heschi@google.com>
Date: Mon, 29 Jan 2018 16:09:11 -0500
Subject: [PATCH] cmd/compile/internal/ssa: use math/bits for register sets

Using bits.TrailingZeroes instead of iterating over each bit is a small
but easy win for the common case of only one or two registers being set.

I copied in the implementation for use with pre-1.9 bootstraps.

Change-Id: Ieaa768554d7d5239a5617fbf34f1ee0b32ce1de5
Reviewed-on: https://go-review.googlesource.com/92395
Run-TryBot: Heschi Kreinick <heschi@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: David Chase <drchase@google.com>
---
 .../compile/internal/ssa/bits_bootstrap.go    | 24 ++++++
 src/cmd/compile/internal/ssa/bits_go19.go     | 13 +++
 src/cmd/compile/internal/ssa/debug.go         | 82 +++++++++++--------
 3 files changed, 85 insertions(+), 34 deletions(-)
 create mode 100644 src/cmd/compile/internal/ssa/bits_bootstrap.go
 create mode 100644 src/cmd/compile/internal/ssa/bits_go19.go

diff --git a/src/cmd/compile/internal/ssa/bits_bootstrap.go b/src/cmd/compile/internal/ssa/bits_bootstrap.go
new file mode 100644
index 0000000000..060ed5ca69
--- /dev/null
+++ b/src/cmd/compile/internal/ssa/bits_bootstrap.go
@@ -0,0 +1,24 @@
+// Copyright 2018 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// +build !go1.9
+
+package ssa
+
+const deBruijn64 = 0x03f79d71b4ca8b09
+
+var deBruijn64tab = [64]byte{
+	0, 1, 56, 2, 57, 49, 28, 3, 61, 58, 42, 50, 38, 29, 17, 4,
+	62, 47, 59, 36, 45, 43, 51, 22, 53, 39, 33, 30, 24, 18, 12, 5,
+	63, 55, 48, 27, 60, 41, 37, 16, 46, 35, 44, 21, 52, 32, 23, 11,
+	54, 26, 40, 15, 34, 20, 31, 10, 25, 14, 19, 9, 13, 8, 7, 6,
+}
+
+// TrailingZeros64 returns the number of trailing zero bits in x; the result is 64 for x == 0.
+func TrailingZeros64(x uint64) int {
+	if x == 0 {
+		return 64
+	}
+	return int(deBruijn64tab[(x&-x)*deBruijn64>>(64-6)])
+}
diff --git a/src/cmd/compile/internal/ssa/bits_go19.go b/src/cmd/compile/internal/ssa/bits_go19.go
new file mode 100644
index 0000000000..a131b0aa42
--- /dev/null
+++ b/src/cmd/compile/internal/ssa/bits_go19.go
@@ -0,0 +1,13 @@
+// Copyright 2018 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// +build go1.9
+
+package ssa
+
+import "math/bits"
+
+func TrailingZeros64(x uint64) int {
+	return bits.TrailingZeros64(x)
+}
diff --git a/src/cmd/compile/internal/ssa/debug.go b/src/cmd/compile/internal/ssa/debug.go
index 048ff7e230..8a71d725c9 100644
--- a/src/cmd/compile/internal/ssa/debug.go
+++ b/src/cmd/compile/internal/ssa/debug.go
@@ -70,10 +70,16 @@ func (state *stateAtPC) reset(live []liveSlot) {
 		if live.loc.Registers == 0 {
 			continue
 		}
-		for reg, regMask := 0, 1; reg < len(registers); reg, regMask = reg+1, regMask<<1 {
-			if live.loc.Registers&RegisterSet(regMask) != 0 {
-				registers[reg] = append(registers[reg], SlotID(live.slot))
+
+		mask := uint64(live.loc.Registers)
+		for {
+			if mask == 0 {
+				break
 			}
+			reg := uint8(TrailingZeros64(mask))
+			mask &^= 1 << reg
+
+			registers[reg] = append(registers[reg], SlotID(live.slot))
 		}
 	}
 	state.slots, state.registers = slots, registers
@@ -90,10 +96,14 @@ func (b *BlockDebug) LocString(loc VarLoc) string {
 		storage = append(storage, "stack")
 	}
 
-	for reg := 0; reg < 64; reg++ {
-		if loc.Registers&(1<<uint8(reg)) == 0 {
-			continue
+	mask := uint64(loc.Registers)
+	for {
+		if mask == 0 {
+			break
 		}
+		reg := uint8(TrailingZeros64(mask))
+		mask &^= 1 << reg
+
 		if registers != nil {
 			storage = append(storage, registers[reg].String())
 		} else {
@@ -513,10 +523,15 @@ func (state *debugState) mergePredecessors(b *Block, blockLocs []*BlockDebug) *B
 		if slotLoc.Registers == 0 {
 			continue
 		}
-		for reg, regMask := 0, 1; reg < len(state.registers); reg, regMask = reg+1, regMask<<1 {
-			if slotLoc.Registers&RegisterSet(regMask) != 0 {
-				state.currentState.registers[reg] = append(state.currentState.registers[reg], SlotID(slotID))
+		mask := uint64(slotLoc.Registers)
+		for {
+			if mask == 0 {
+				break
 			}
+			reg := uint8(TrailingZeros64(mask))
+			mask &^= 1 << reg
+
+			state.currentState.registers[reg] = append(state.currentState.registers[reg], SlotID(slotID))
 		}
 	}
 	result.startState = state.cache.GetLiveSlotSlice()
@@ -539,28 +554,29 @@ func (state *debugState) processValue(v *Value, vSlots []SlotID, vReg *Register)
 	// Handle any register clobbering. Call operations, for example,
 	// clobber all registers even though they don't explicitly write to
 	// them.
-	if clobbers := opcodeTable[v.Op].reg.clobbers; clobbers != 0 {
-		for reg := 0; reg < len(state.registers); reg++ {
-			if clobbers&(1<<uint8(reg)) == 0 {
-				continue
-			}
-
-			for _, slot := range locs.registers[reg] {
-				if state.loggingEnabled {
-					state.logf("at %v: %v clobbered out of %v\n", v.ID, state.slots[slot], &state.registers[reg])
-				}
+	clobbers := uint64(opcodeTable[v.Op].reg.clobbers)
+	for {
+		if clobbers == 0 {
+			break
+		}
+		reg := uint8(TrailingZeros64(clobbers))
+		clobbers &^= 1 << reg
 
-				last := locs.slots[slot]
-				if last.absent() {
-					state.f.Fatalf("at %v: slot %v in register %v with no location entry", v, state.slots[slot], &state.registers[reg])
-					continue
-				}
-				regs := last.Registers &^ (1 << uint8(reg))
-				setSlot(slot, VarLoc{regs, last.OnStack, last.StackOffset})
+		for _, slot := range locs.registers[reg] {
+			if state.loggingEnabled {
+				state.logf("at %v: %v clobbered out of %v\n", v.ID, state.slots[slot], &state.registers[reg])
 			}
 
-			locs.registers[reg] = locs.registers[reg][:0]
+			last := locs.slots[slot]
+			if last.absent() {
+				state.f.Fatalf("at %v: slot %v in register %v with no location entry", v, state.slots[slot], &state.registers[reg])
+				continue
+			}
+			regs := last.Registers &^ (1 << uint8(reg))
+			setSlot(slot, VarLoc{regs, last.OnStack, last.StackOffset})
 		}
+
+		locs.registers[reg] = locs.registers[reg][:0]
 	}
 
 	switch {
@@ -692,14 +708,12 @@ func canMerge(pending, new VarLoc) bool {
 
 // firstReg returns the first register in set that is present.
 func firstReg(set RegisterSet) uint8 {
-	for reg := 0; reg < 64; reg++ {
-		if set&(1<<uint8(reg)) != 0 {
-			return uint8(reg)
-		}
+	if set == 0 {
+		// This is wrong, but there seem to be some situations where we
+		// produce locations with no storage.
+		return 0
 	}
-	// This is wrong, but there seem to be some situations where we
-	// produce locations with no storage.
-	return 0
+	return uint8(TrailingZeros64(uint64(set)))
 }
 
 // buildLocationLists builds location lists for all the user variables in
-- 
2.50.0